CS241 Operating SystemsDeadlock 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 ConditionNo Preemption ConditionCircular Wait ConditionReminderCS241 Operating SystemsDeadlock Issues (1)Klara NahrstedtLecture 162/24/20062/20/2006CS 241 - System Programming, Klara Nahrstedt2Contentz Deadlock Conceptz Deadlock Conditions2/20/2006CS 241 - System Programming, Klara Nahrstedt3Administrative NoteszMP2 on scheduling is runningz Quiz 4 todayz Read Tanenbaum Chapter 3.3.1 and 3.3.22/20/2006CS 241 - System Programming, Klara Nahrstedt4Resource (1)zA resource is a commodity needed by a process. z 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.2/20/2006CS 241 - System Programming, Klara Nahrstedt5Resource (2)z Resources can also be either: –preemptible: e.g., CPU, central memory or– non-preemptible: e.g., tape drives. zAnd resources can be either: – shared among several processes or– dedicated exclusively to a single process.2/20/2006CS 241 - System Programming, Klara Nahrstedt6Using Semaphore to Share ResourceProcess Q();{ A.Down();B.Down();use both resourceB.Up();A.Up(); }Process P();{ A.Down();B.Down();use both resourceB.Up();A.Up(); }02 6345External 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);52/20/2006CS 241 - System Programming, Klara Nahrstedt7But Deadlock can Happen!Process P();{ A.Down();B.Down();use both resourcesB.Up();A.Up(); }Process Q();{ B.Down();A.Down();use both resourcesA.Up();B.Up(); }3211External Semaphore A(1), B(1);1External Semaphore A(0), B(1);2External Semaphore A(0), B(0);32/20/2006CS 241 - System Programming, Klara Nahrstedt8DeadlockMechanism for DeadlockControl2/20/2006CS 241 - System Programming, Klara Nahrstedt9Deadlock DefinitionzWhat 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). zIs 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.2/20/2006CS 241 - System Programming, Klara Nahrstedt10Conditions for DeadlockzWhat conditions should exist in order to lead to a deadlockz Real life analogy such asz“You take the monitor, I grab the keyboard”zCars in intersection2/20/2006CS 241 - System Programming, Klara Nahrstedt11Necessary and Sufficient Conditions for DeadlockzMutual exclusion–Processes claim exclusive control of the resources they requirezWait-for condition–Processes hold resources already allocated to them while waiting for additional resourceszNo preemption condition–Resources cannot be removed from the processes holding them until used to completionzCircular wait condition–A circular chain of processes exists in which each process holdsone or more resources that are requested by the next process in the chain2/20/2006CS 241 - System Programming, Klara Nahrstedt12Mutual ExclusionzProcesses claim exclusive control of the resources they require2/20/2006CS 241 - System Programming, Klara Nahrstedt13Wait-for ConditionzProcesses hold resources already allocated to them while waiting for additional resources2/20/2006CS 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 32/20/2006CS 241 - System Programming, Klara Nahrstedt15No Preemption ConditionzResources cannot be removed from the processes holding them until used to completion2/20/2006CS 241 - System Programming, Klara Nahrstedt16Its difficult to take a tape drive away from a process that is busy writing a tape2/20/2006CS 241 - System Programming, Klara Nahrstedt17Circular Wait ConditionzA circular chain of processes exists in which each process holds one or more resources that are requested by the next process in the chain2/20/2006CS 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 32/20/2006CS 241 - System Programming, Klara Nahrstedt19ReminderzMP2 is running, deadline Feb 27z Read Tanenbaum 3.3.1 and
View Full Document