CS241 Operating Systems Deadlock Issues (1)ContentAdministrative NotesResource (1)Resource (2)Using Semaphore to Share ResourceBut Deadlock can Happen!DeadlockDeadlock DefinitionConditions for DeadlockNecessary and Sufficient Conditions for DeadlockMutual ExclusionWait-for ConditionSlide 14No Preemption ConditionSlide 16Circular Wait ConditionSlide 18ReminderCS241 Operating SystemsDeadlock Issues (1)Klara NahrstedtLecture 162/24/200601/14/19 CS 241 - System Programming, Klara Nahrstedt2ContentDeadlock ConceptDeadlock Conditions01/14/19 CS 241 - System Programming, Klara Nahrstedt3Administrative NotesMP2 on scheduling is runningQuiz 4 todayRead Tanenbaum Chapter 3.3.1 and 3.3.201/14/19 CS 241 - System Programming, Klara Nahrstedt4Resource (1)A resource is a commodity needed by a process. Resources can be either: –serially reusable: e.g., CPU, memory, disk space, I/O devices, files. acquire use release –consumable: produced by a process, needed by a process; e.g., messages, buffers of information, interrupts. create acquire use Resource ceases to exist after it has been used, so it is not released.01/14/19 CS 241 - System Programming, Klara Nahrstedt5Resource (2)Resources can also be either: –preemptible: e.g., CPU, central memory or–non-preemptible: e.g., tape drives. And resources can be either: –shared among several processes or–dedicated exclusively to a single process.01/14/19 CS 241 - System Programming, Klara Nahrstedt6Using Semaphore to Share ResourceProcess P();{ A.Down(); B.Down(); use both resource B.Up(); A.Up(); }Process Q();{ A.Down(); B.Down(); use both resource B.Up(); A.Up(); }423External Semaphore A(1), B(1);External Semaphore A(0), B(1);2External Semaphore A(0), B(0);3External Semaphore A(0), B(1);4External Semaphore A(1), B(1);550601/14/19 CS 241 - System Programming, Klara Nahrstedt7But Deadlock can Happen!Process P();{ A.Down(); B.Down(); use both resources B.Up(); A.Up(); }Process Q();{ B.Down(); A.Down(); use both resources A.Up(); B.Up(); }3211External Semaphore A(1), B(1);1External Semaphore A(0), B(1);2External Semaphore A(0), B(0);301/14/19 CS 241 - System Programming, Klara Nahrstedt8DeadlockMechanism for DeadlockControl01/14/19 CS 241 - System Programming, Klara Nahrstedt9Deadlock DefinitionWhat is a deadlock?–A process is deadlocked if it is waiting for an event that will never occur. –Typically, but not necessarily, more than one process will be involved together in a deadlock (the deadly embrace). Is deadlock the same as starvation (or indefinitely postponed)? –A process is indefinitely postponed if it is delayed repeatedly over a long period of time while the attention of the system is given to other processes. I.e., logically the process may proceed but the system never gives it the CPU.01/14/19 CS 241 - System Programming, Klara Nahrstedt10Conditions for DeadlockWhat conditions should exist in order to lead to a deadlockReal life analogy such as“You take the monitor, I grab the keyboard”Cars in intersection01/14/19 CS 241 - System Programming, Klara Nahrstedt11Necessary and Sufficient Conditions for DeadlockMutual exclusion–Processes claim exclusive control of the resources they requireWait-for condition–Processes hold resources already allocated to them while waiting for additional resourcesNo preemption condition–Resources cannot be removed from the processes holding them until used to completionCircular wait condition–A circular chain of processes exists in which each process holds one or more resources that are requested by the next process in the chain01/14/19 CS 241 - System Programming, Klara Nahrstedt12Mutual ExclusionProcesses claim exclusive control of the resources they require01/14/19 CS 241 - System Programming, Klara Nahrstedt13Wait-for ConditionProcesses hold resources already allocated to them while waiting for additional resources01/14/19 CS 241 - System Programming, Klara Nahrstedt14P(s1)P(s2)WorkV(s2)V(s1)P(s2)P(s3)WorkV(s3)V(s2)P(s3)P(s1)WorkV(s1)V(s3)BlockedProcess 1 Process 2 Process 301/14/19 CS 241 - System Programming, Klara Nahrstedt15No Preemption ConditionResources cannot be removed from the processes holding them until used to completion01/14/19 CS 241 - System Programming, Klara Nahrstedt16Its difficult to take a tape drive away from a process that is busy writing a tape01/14/19 CS 241 - System Programming, Klara Nahrstedt17Circular Wait ConditionA circular chain of processes exists in which each process holds one or more resources that are requested by the next process in the chain01/14/19 CS 241 - System Programming, Klara Nahrstedt18P(s1)P(s2)WorkV(s2)V(s1)P(s2)P(s3)WorkV(s3)V(s2)P(s3)P(s1)WorkV(s1)V(s3)BlockedProcess 1 Process 2 Process 301/14/19 CS 241 - System Programming, Klara Nahrstedt19ReminderMP2 is running, deadline Feb 27Read Tanenbaum 3.3.1 and
View Full Document
Unlocking...