11CSC 4103 - Operating SystemsSpring 2007Tevfik KoşarLouisiana State UniversityFebruary 13th, 2007Lecture - VIIIDeadlocks - I2Roadmap• Synchronization– Monitors• Deadlocks– Deadlock Characterization• Resource Allocation Graphs– Deadlock Prevention3Dining Philosophers Problem• Five philosophers spend their time eating and thinking. • They are sitting in front of a round table with spagett served. •There are five plates at the table and five chopsticks set between the plates. • Eating the spaghetti requires the use of two chopsticks which the philosophers pick up one at a time.•Philosophers do not talk to each other.•Semaphore chopstick [5] initialized to 14Dining-Philosophers Problem (Cont.)• The structure of Philosopher i:Do { wait ( chopstick[i] );wait ( chopStick[ (i + 1) % 5] );// eatsignal ( chopstick[i] );signal (chopstick[ (i + 1) % 5] );// think} while (true) ;5Problems with Semaphores• Wrong use of semaphore operations:– semaphores A and B, initialized to 1P0P1wait (A); wait(B)wait (B); wait(A)Deadlock– signal (mutex) …. wait (mutex) violation of mutual exclusion– wait (mutex) … wait (mutex)Deadlock– Omitting of wait (mutex) or signal (mutex) (or both) violation of mutual exclusion or deadlock6Semaphores• inadequate in dealing with deadlocks• do not protect the programmer from the easy mistakes of taking a semaphore that is already held by the same process, and forgetting to release a semaphore that has been taken • mostly used in low level code, eg. operating systems• the trend in programming language development, though, is towards more structured forms of synchronization, such as monitors and channels27Monitors• A high-level abstraction that provides a convenient and effective mechanism for process synchronization• Only one process may be active within the monitor at a timemonitor monitor-name{// shared variable declarationsprocedure P1 (…) { …. }…procedure Pn (…) {……}Initialization code ( ….) { … }…}}• A monitor procedure takes the lock before doing anything else, and holds it until it either finishes or waits for a condition8Monitor - ExampleAs a simple example, consider a monitor for performing transactions on a bank account.monitor account { int balance := 0 function withdraw(int amount) { if amount < 0 then error "Amount may not be negative" else if balance < amount then error "Insufficient funds" else balance := balance - amount } function deposit(int amount) { if amount < 0 then error "Amount may not be negative" else balance := balance + amount }} 9Schematic view of a Monitor10Condition Variables• Provide additional synchronization mechanism• condition x, y;• Two operations on a condition variable:– x.wait () – a process invoking this operation is suspended– x.signal () – resumes one of processes (if any) thatinvoked x.wait ()If no process suspended, x.signal() operation has no effect.11Solution to Dining Philosophers using Monitorsmonitor DP{ enum { THINKING; HUNGRY, EATING) state [5] ;condition self [5]; //to delay philosopher when he is hungry but unable to get chopsticksinitialization_code() { for (int i = 0; i < 5; i++)state[i] = THINKING;}void pickup (int i) { state[i] = HUNGRY;test(i);//only if both neighbors are not eatingif (state[i] != EATING) self [i].wait;}12Solution to Dining Philosophers (cont)void test (int i) { if ((state[i] == HUNGRY) &&(state[(i + 1) % 5] != EATING) &&(state[(i + 4) % 5] != EATING) ) { state[i] = EATING ;self[i].signal () ;}}void putdown (int i) { state[i] = THINKING;// test left and right neighborstest((i + 4) % 5);test((i + 1) % 5);}} No two philosophers eat at the same time No deadlock But starvation can occur!313DeadlocksDeadlocksDeadlocksDeadlocks14The Deadlock Problem - revisiting• A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.• Example – System has 2 tape drives.– P1and P2each hold one tape drive and each needs another one.• Example – semaphores A and B, initialized to 1P0P1wait (A); wait(B)wait (B); wait(A)15Bridge Crossing Example• Traffic only in one direction.• Each section of a bridge can be viewed as a resource.• If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback).• Several cars may have to be backed up if a deadlock occurs.• Starvation is possible.16Deadlock Characterization1. Mutual exclusion: nonshared resources; only one process at a time can use a specific resource2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes3. No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its taskDeadlock can arise if four conditions hold simultaneously.17Deadlock Characterization (cont.)4. Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1is waiting for a resource that is held by P2, …, Pn–1is waiting for a resource that is held by Pn, and Pnis waiting for a resource that is held by P0.Deadlock can arise if four conditions hold simultaneously.18Resource-Allocation Graph• V is partitioned into two types:– P = {P1, P2, …, Pn}, the set consisting of all the processes in the system.– R = {R1, R2, …, Rm}, the set consisting of all resource types in the system.• P requests R – directed edge P1 → Rj• R is assigned to P – directed edge Rj→ Pi• Used to describe deadlocks• Consists of a set of vertices V and a set of edges E.419Resource-Allocation Graph (Cont.)• Process• Resource Type with 4 instances• Pirequests instance of Rj• Piis holding an instance of RjPiPiRjRj20Example of a Resource Allocation Graph21Basic Facts• If graph contains no cycles ⇒ no deadlock.• If graph contains a cycle ⇒ there may be a deadlock– if only one instance per resource type, then deadlock.– if several instances per resource type, possibility of deadlock.22Resource Allocation Graph – Example 1 No Cycle, no Deadlock23Resource Allocation Graph – example 2 DeadlockWhich Processes deadlocked? P1 & P2 & P324Resource Allocation Graph – Example 3 Cycle, but no Deadlock525Rule of Thumb• A cycle in the resource allocation graph– Is a necessary condition for a deadlock– But not a sufficient condition26Methods for Handling