CSCI 5828: Foundations Of Software Engineering
CSCI 5828: Foundationsof Software EngineeringLecture 17: DeadlockSlides created by Mageeand Kramer for theConcurrency textbook1 Magee/Kramer 2nd Edition
Chapter 6DeadlockConcurrency: Deadlock2 Magee/Kramer 2nd Edition
DeadlockConcepts:system deadlock: no further progressfour necessary & sufficient conditionsModels:deadlock - no eligible actionsPractice:blocked threadsAim: deadlock avoidance - to designsystems where deadlock cannot occur.Concurrency: Deadlock3 Magee/Kramer 2nd Edition
Deadlock: 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: Deadlock4 Magee/Kramer 2nd Edition
Wait-for cycleHas A awaits BAHas E awaits AEBDHas D awaits EConcurrency: DeadlockHas B awaits CCHas C awaits D5 Magee/Kramer 2nd Edition
6.1 Deadlock analysis - primitive processes deadlocked state is one with no outgoing transitions in FSP: STOP processMOVE (north- (south- MOVE north- STOP)).northMOVE0north12south animation to produce a trace. analysis using LTSA:(shortest trace to STOP)Concurrency: DeadlockTrace to DEADLOCK:northnorth6 Magee/Kramer 2nd Edition
deadlock analysis - parallel composition in systems, deadlock may arise from theparallel composition of interacting dlock Trace?Avoidance?Concurrency: utRESOURCE (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).7 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: DeadlockProgress?8 Magee/Kramer 2nd Edition
6.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.3134One fork is placed between eachpair of philosophers and they agreethat each will only use the fork to hisimmediate right and left.Concurrency: Deadlock2214009 Magee/Kramer 2nd Edition
Dining Philosophers - model structure diagramrightEach FORK is ashared resourcewith actions getand put.When hungry,each PHIL mustfirst get hisright and leftforks before hecan start eating.Concurrency: DeadlockFORKphil[0]:PHILlef trightlef tphil[4]:PHILphil[1]:PHILlef trightFORKFORKrightlef tphil[2]:PHILFORKrightFORKlef tphil[3]:PHIL10 Magee/Kramer 2nd Edition
Dining Philosophers - modelFORK (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: Deadlock11 Magee/Kramer 2nd Edition
Dining Philosophers - model analysisTrace to right.getConcurrency: DeadlockThis 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!12 Magee/Kramer 2nd Edition
Dining PhilosophersDeadlock is easilydetected in ourmodel.How easy is it todetect a potentialdeadlock in animplementation?Concurrency: Deadlock13 Magee/Kramer 2nd Edition
Dining Philosophers - implementation in ntrollerForkPhilCanvasdisplay philosophers:active entities- implement asthreads forks: sharedpassive entities- implement asmonitors displayConcurrency: Deadlock14 Magee/Kramer 2nd Edition
Dining Philosophers - Fork monitorclass Fork {private boolean taken false;private PhilCanvas display;private int identity;takenencodes thestate of theforkFork(PhilCanvas disp, int id){ display disp; identity id;}synchronized void put() {taken nchronized void get()throws java.lang.InterruptedException {while (taken) wait();taken true;display.setFork(identity,taken);}Concurrency: Deadlock}15 Magee/Kramer 2nd Edition
Dining Philosophers - Philosopher implementationclass Philosopher extends Thread {.public void run() {try {while (true) {// (controller.sleepTime()); // ();// gotright p(500);Followsleft.get();// eatingfrom ontroller.eatTime());(sittingright.put();down andleft.put();leaving the}table have} catch (java.lang.InterruptedException e){} been}omitted).Concurrency: Deadlock16} Magee/Kramer 2 Editionnd
Dining Philosophers - implementation in JavaCode to create the philosopherthreads 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: Deadlock17 Magee/Kramer 2nd Edition
Dining PhilosophersTo ensure deadlockoccurs eventually,the slider controlmay be moved to theleft. This reducesthe time eachphilosopher spendsthinking and eating.This "speedup"increases theprobability ofdeadlock occurring.Concurrency: Deadlock18 Magee/Kramer 2nd Edition
Deadlock-free PhilosophersDeadlock can be avoided by ensuring that a wait-for cyclecannot exist. How?PHIL(I 0)Introduce an (when (I%2 0) sitdownasymmetry into our- left.get- right.getdefinition of- eatphilosophers.- left.put- right.putUse the identity I ofa philosopher to makeeven numberedphilosophers gettheir 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- arise- PHIL).19 Magee/Kramer 2nd Edition
Maze example - shortest path to “deadlock”We can exploit the shortest path trace produced by thedeadlock detection mechanism of LTSA to find theshortest path out of a maze to the STOP process!STOP012northWe first model theMAZE.Each position iswesteast modelled by the345moves that itsouthpermits. The MAZE786parameter gives thestarting position.eg. MAZE(Start 8) P[Start],P[0] (north- STOP east- P[1]),.Concurrency: Deadlock20 Magee/Kramer 2nd Edition
Maze example - shortest path to “deadlock”Shortest pathescape trace fromposition 7 ? GETOUT MAZE(7).STOP012345678Concurrency: DeadlocknorthwesteastsouthTrace toDEADLOCK:eastnorthnorthwestwestnorth21 Magee/Kramer 2nd Edition
Summary Concepts deadlock: no futher progress four necessary and sufficient conditions: serially reusable resources incremental acquisition no preemption wait-for cycleAim: deadlock avoidance- to design systems wheredeadlock cannot occur. Models no eligable actions (analysis gives shortest path trace) Practice blocked threadsConcurrency: Deadlock22 Magee/Kramer 2nd Edition
of Software Engineering Lecture 17: Deadlock Slides created by Magee and Kramer for the Concurrency textbook. Concurrency: Deadlock 2 Magee/Kramer 2nd Edition Chapter 6 Deadlock. Concurrency: Deadlock 3 Magee/Kramer 2nd Editio
CSCI 561 – Theory of Computation Dr. Neil T. Dantam CSCI-561, Colorado School of Mines Fall 2021 Dantam (Mines CSCI-561) Intro Fall 2021 1/32
This Software Requirements Specification details the software requirements for the FS CSCI. The FS CSCI is composed of the following Computer Software Components (CSCs): 1. Executive (0/S services, Device Drivers, Interrupt Handling, Initialization) 2. Prom Capability an.d System Initialization 3. Command Processing
Software Engineering Lecture 20, 21, and : Software Design Slides created by Pfleeger and Atlee for the SE textbook Some modifications to the original slides have been made by Ken Anderson for clarity of presentation 03/20/2008 — 04/01/2008 — 04/08/2008. ISBN -13-146913-4 Prentice-Hall, 2006
Service Oriented Architecture is a paradigm for organizing and utilizing distributed capabilities that may be under the control of different ownership domains. 6. SOA Components of SOA Ref: Element of SOA 7 Front End Service Service Repository Service Bus Contract Implementation Interface
J. Eric Oliver is Professor of Political Science, University of Chicago, Pick Hall 518, 5828 South University Avenue, Chicago, IL 60637 (eoliver@uchicago.edu). Thomas J. Wood is a Ph.D. candidate in Political Science, University of Chicago, Pick Hall 518A, 5828 South University, Chicago, IL 60637 (tomwood@uchicago.edu).
SRS Software Requirements Specification DM Dialogue Management CSCI MP Mapping CSCI . Section 1 identifies the scope of this document, the purpose of the software, and lists the definitions, acronyms and reference documents. Section 2 lists the documents referred to elsewhere in this document. . For
git config --global user.name "David Parker" git config --global user.email davidwparker@gmail.com Editor: git config --global core.editor emacs Check Settings git config --list. How to: Getting Help Any of the following commands work: git help
a paper animal. She tried over and over until she could finally fold a paper dog and wished that she could see Son just once more even though she knew that it was not possible. Looking at the paper dog she had made, she felt so weird that the paper dog seemed smiling at her. She felt that she would make more, many more animals out of paper. She collected all the papers in the house and started .
