1©Magee/Kramer 2nd EditionCSCI 5828: Foundationsof Software EngineeringLecture 17: DeadlockSlides created by Mageeand Kramer for theConcurrency textbookConcurrency: Deadlock 2©Magee/Kramer 2nd EditionChapter 6DeadlockConcurrency: Deadlock 3©Magee/Kramer 2nd EditionDeadlockConcepts: system deadlock: no further progressfour necessary & sufficient conditions Models: deadlock - no eligible actionsPractice: blocked threadsAim: deadlock avoidance - to designsystems where deadlock cannot occur.Concurrency: Deadlock 4©Magee/Kramer 2nd EditionDeadlock: four necessary and sufficient conditions♦ Serially reusable resources:the processes involved share resources which they use under mutualexclusion.♦ Incremental acquisition:processes hold on to resources already allocated to them while waitingto acquire additional resources.♦ No pre-emption:once acquired by a process, resources cannot be pre-empted (forciblywithdrawn) but are only released voluntarily.♦ Wait-for cycle:a circular chain (or cycle) of processes exists such that each processholds a resource which its successor in the cycle is waiting to acquire.Concurrency: Deadlock 5©Magee/Kramer 2nd EditionWait-for cycleABCDEHas A awaits BHas B awaits CHas C awaits DHas D awaits EHas E awaits AConcurrency: Deadlock 6©Magee/Kramer 2nd Edition6.1 Deadlock analysis - primitive processes♦ deadlocked state is one with no outgoing transitions♦ in FSP: STOP processMOVE = (north->(south->MOVE|north->STOP)).Trace to DEADLOCK:northnorth♦ animation to produce a trace.♦analysis using LTSA: (shortest trace to STOP)MOVEnorth northsouth0 1 2Concurrency: Deadlock 7©Magee/Kramer 2nd Editiondeadlock analysis - parallel composition♦ in systems, deadlock may arise from theparallel composition of interacting processes.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 ).printer:RESOURCEgetputSYSscanner:RESOURCEgetputp:Pprinterscannerq:QprinterscannerDeadlock Trace?Avoidance?Concurrency: Deadlock 8©Magee/Kramer 2nd Editiondeadlock 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? Progress?Concurrency: Deadlock 9©Magee/Kramer 2nd Edition6.2 Dining PhilosophersFive philosophers sit around acircular table. Each philosopherspends his life alternatelythinking and eating. In the centreof the table is a large bowl ofspaghetti. A philosopher needstwo forks to eat a helping ofspaghetti.0123401234One fork is placed between eachpair of philosophers and they agreethat each will only use the fork to hisimmediate right and left.Concurrency: Deadlock 10©Magee/Kramer 2nd EditionDining Philosophers - model structure diagramphil[4]:PHILphil[1]:PHILphil[3]:PHILphil[0]:PHILphil[2]:PHILFORKFORKFORKFORKFORKlef trightrightrightrightlef tlef trightlef tlef tEach FORK is ashared resourcewith actions getand put.When hungry,each PHIL mustfirst get hisright and leftforks before hecan start eating.Concurrency: Deadlock 11©Magee/Kramer 2nd EditionDining Philosophers - modelFORK = (get -> put -> FORK).PHIL = (sitdown ->right.get->left.get ->eat ->right.put->left.put ->arise->PHIL).||DINERS(N=5)= forall [i:0..N-1] (phil[i]:PHIL || {phil[i].left,phil[((i-1)+N)%N].right}::FORK).Table of philosophers:Can this system deadlock?Concurrency: Deadlock 12©Magee/Kramer 2nd EditionDining Philosophers - model analysisTrace to DEADLOCK:phil.0.sitdownphil.0.right.getphil.1.sitdownphil.1.right.getphil.2.sitdownphil.2.right.getphil.3.sitdownphil.3.right.getphil.4.sitdownphil.4.right.getThis is the situation whereall the philosophers becomehungry at the same time, sitdown at the table and eachphilosopher picks up thefork to his right.The system can make nofurther progress since eachphilosopher is waiting for afork held by his neighbor i.e.a wait-for cycle exists!Concurrency: Deadlock 13©Magee/Kramer 2nd EditionDining PhilosophersDeadlock is easilydetected in ourmodel.How easy is it todetect a potentialdeadlock in animplementation?Concurrency: Deadlock 14©Magee/Kramer 2nd EditionDining Philosophers - implementation in Java♦philosophers:active entities- implement asthreads♦forks: sharedpassive entities- implement asmonitors♦displayAppletDinersThreadPhilosopher1nFork1nPhilCanvasdisplaycontrollerviewdisplayConcurrency: Deadlock 15©Magee/Kramer 2nd EditionDining Philosophers - Fork monitorclass Fork { private boolean taken=false; private PhilCanvas display; private int identity; Fork(PhilCanvas disp, int id) { display = disp; identity = id;} 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); }}takenencodes thestate of theforkConcurrency: Deadlock 16©Magee/Kramer 2nd EditionDining Philosophers - Philosopher implementationclass 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); sleep(500); left.get(); // eating view.setPhil(identity,view.EATING); sleep(controller.eatTime()); right.put(); left.put(); } } catch (java.lang.InterruptedException e){} }}Followsfrom themodel(sittingdown andleaving thetable havebeenomitted).Concurrency: Deadlock 17©Magee/Kramer 2nd EditionDining Philosophers - implementation in Javafor (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();}Code to create the philosopherthreads and fork monitors:Concurrency: Deadlock 18©Magee/Kramer 2nd EditionDining PhilosophersTo ensure deadlockoccurs eventually,the slider controlmay be moved to theleft. This reducesthe time eachphilosopher spendsthinking and eating.This
View Full Document
Unlocking...