Concurrency Deadlock 1 Magee Kramer 2nd Edition Concurrency Deadlock 2 Magee Kramer 2nd Edition Chapter 6 Deadlock Concurrency Deadlock 3 Magee Kramer 2nd Edition Deadlock Concepts system deadlock no further progress four necessary sufficient conditions Models deadlock no eligible actions Practice blocked threads Aim deadlock avoidance to design systems where deadlock cannot occur Concurrency Deadlock 4 Magee Kramer 2nd Edition Deadlock four necessary and sufficient conditions Serially reusable resources the processes involved shared resources which they use under mutual exclusion Incremental acquisition processes hold on to resources already allocated to them while waiting to acquire additional resources No pre emption once acquired by a process resources cannot be pre empted forcibly withdrawn but are only released voluntarily Wait for cycle a circular chain or cycle of processes exists such that each process holds a resource which its successor in the cycle is waiting to acquire Concurrency Deadlock 5 Magee Kramer 2nd Edition Wait for cycle Has A awaits B A Has E awaits A E B D Has D awaits E Concurrency Deadlock Has B awaits C C Has C awaits D 6 Magee Kramer 2nd Edition 6 1 Deadlock analysis primitive processes deadlocked state is one with no outgoing transitions in FSP STOP process MOVE north south MOVE north STOP north MOVE 0 north 1 2 south animation to produce a trace analysis using LTSA shortest trace to STOP Concurrency Deadlock Trace to DEADLOCK north north 7 Magee Kramer 2nd Edition deadlock analysis parallel composition in systems deadlock may arise from the parallel composition of interacting processes SYS p P printer scanner q Q printer scanner Deadlock Trace Avoidance Concurrency Deadlock printer RESOURCE get put scanner RESOURCE get put RESOURCE get put RESOURCE P printer get scanner get copy printer put scanner put P Q scanner get printer get copy scanner put printer put Q SYS p P q Q p q printer RESOURCE p q scanner RESOURCE 8 Magee Kramer 2nd Edition deadlock analysis avoidance acquire resources in the same order Timeout P printer get GETSCANNER GETSCANNER scanner get copy printer put scanner put P timeout printer put P Q scanner get GETPRINTER GETPRINTER printer get copy printer put scanner put Q timeout scanner put Q Deadlock Concurrency Deadlock Progress 9 Magee Kramer 2nd Edition 6 2 Dining Philosophers Five philosophers sit around a circular table Each philosopher spends his life alternately thinking and eating In the centre of the table is a large bowl of spaghetti A philosopher needs two forks to eat a helping of spaghetti 3 1 3 4 One fork is placed between each pair of philosophers and they agree that each will only use the fork to his immediate right and left Concurrency Deadlock 2 2 1 4 0 0 10 Magee Kramer 2nd Edition Dining Philosophers model structure diagram right Each FORK is a shared resource with actions get and put When hungry each PHIL must first get his right and left forks before he can start eating Concurrency Deadlock FORK phil 0 PHIL lef t right lef t phil 4 PHIL phil 1 PHIL lef t right FORK FORK right lef t phil 2 PHIL FORK right FORK lef t phil 3 PHIL 11 Magee Kramer 2nd Edition Dining Philosophers model FORK get put FORK PHIL sitdown right get left get eat right put left put arise PHIL Table of philosophers DINERS N 5 forall i 0 N 1 phil i PHIL phil i left phil i 1 N N right FORK Can this system deadlock Concurrency Deadlock 12 Magee Kramer 2nd Edition Dining Philosophers model analysis Trace to DEADLOCK phil 0 sitdown phil 0 right get phil 1 sitdown phil 1 right get phil 2 sitdown phil 2 right get phil 3 sitdown phil 3 right get phil 4 sitdown phil 4 right get Concurrency Deadlock This is the situation where all the philosophers become hungry at the same time sit down at the table and each philosopher picks up the fork to his right The system can make no further progress since each philosopher is waiting for a fork held by his neighbor i e a wait for cycle exists 13 Magee Kramer 2nd Edition Dining Philosophers Deadlock is easily detected in our model How easy is it to detect a potential deadlock in an implementation Concurrency Deadlock 14 Magee Kramer 2nd Edition Dining Philosophers implementation in Java Applet Diners display Thread 1 n Philosopher view 1 n controller Fork PhilCanvas display philosophers active entities implement as threads forks shared passive entities implement as monitors display Concurrency Deadlock 15 Magee Kramer 2nd Edition Dining Philosophers Fork monitor class Fork private boolean taken false private PhilCanvas display private int identity Fork PhilCanvas disp int id display disp identity id taken encodes the state of the fork synchronized void put taken false display setFork identity taken notify synchronized void get throws java lang InterruptedException while taken wait taken true display setFork identity taken Concurrency Deadlock 16 Magee Kramer 2nd Edition Dining Philosophers Philosopher implementation class Philosopher extends Thread public void run try while true thinking view setPhil identity view THINKING sleep controller sleepTime hungry view setPhil identity view HUNGRY right get gotright chopstick view setPhil identity view GOTRIGHT Follows sleep 500 from the left get eating view setPhil identity view EATING model sleep controller eatTime sitting right put down and left put leaving the table have catch java lang InterruptedException e been omitted Concurrency Deadlock 17 Magee Kramer 2 Edition nd Dining Philosophers implementation in Java Code to create the philosopher threads and fork monitors for int i 0 i N i fork i new Fork display i for int i 0 i N i phil i new Philosopher this i fork i 1 N N fork i phil i start Concurrency Deadlock 18 Magee Kramer 2nd Edition Dining Philosophers To ensure deadlock occurs eventually the slider control may be moved to the left This reduces the time each philosopher spends thinking and eating This speedup increases the probability of deadlock occurring Concurrency Deadlock 19 Magee Kramer 2nd Edition Deadlock free Philosophers Deadlock can be avoided by ensuring that a wait for cycle cannot exist How PHIL I 0 Introduce an when I 2 0 sitdown asymmetry into our left get right get definition of eat philosophers left put right put Use the identity I of a philosopher to make even numbered philosophers get their left forks first odd their right first Other strategies Concurrency Deadlock arise PHIL when I 2 1 sitdown right get left get eat left put right put
View Full Document
Unlocking...