Deadlocks - Universitetet i oslo

Deadlocks - Universitetet i oslo

Deadlocks Tore Larsen With slides from T. Plagemann, C. Griwodz, K. Li, A. Tanenbaum and M. van Steen Resources Resource allocation is a central OS concern Examples of computer resources CPU Memory Disk drive Tape drives Printers Plotter Loudspeaker 2 OS Resource allocation Want to uphold some policies Effective use Fairness If possible, allow processes to complete

Want to avoid deadlocks Topics Modeling resource allocation Conditions for deadlocks Strategies to deal with deadlocks 3 Resources Processes Typical way to use a resource Need access to resources in reasonable order Request Use Release Suppose a process holds resource A and requests resource B

At same time another process holds B and requests A Both are blocked and remain so 4 Resources Active resource Passive resource System capabilities that are required by active resources E.g. memory, network bandwidth Exclusive resource Provides a service E.g. CPU, network adaptor Only one process at a time can use it E.g. loudspeaker, processor Shared resource

Can be used by multiple processes E.g. memory, bandwidth 5 Resources Single resource Multiple resource Exists several time in the system E.g. processor in a multiprocessor system Preemptable resource Exists only once in the system E.g. loudspeaker Resource that can be taken away from a process E.g. CPU can be taken away from processes in user space Non-preemptable resource

Taking it away will cause processes to fail E.g. Disk, files 6 Resources acquire block Process must wait if request is denied Requesting process may be blocked May fail with error code use Deadlocks Occur only when acquire processes are granted exclusive access to resources use 7 Deadlocks Formal definition : A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause

Usually the event is release of a currently held resource None of the processes can Run Release resources Be awakened 8 Four Conditions for Deadlock 1. Mutual exclusion condition Each resource is either assigned to one process or it is available 2. Hold and wait condition Process holding resources may request more resources 3. No preemption condition Previously granted resources cannot be taken away by force 4. Circular wait condition Must be at least one circular chain involving two

or more processes Each is waiting for resource held by next member9 Deadlock Modeling Modeled with directed graphs A S C T R B U D Resource R assigned to process A Process B is requesting/waiting for resource S Process C and D are in deadlock over 10 Deadlock Example A utility program

A deadlock Copies a file from a tape to disk Prints the file to a printer Resources Tape Disk Printer A tape disk printer B 11 Deadlock Modeling How deadlock occurs

A Requests R Requests S Releases S Releases R B Requests S Requests T Releases T Releases S C Requests T Requests R Releases R Releases T Processes A B C Resources R S T A requests R B requests S C requests T A requests S B requests T C requests R 12

Deadlock Modeling How deadlock can be avoided A Requests R Requests S Releases S Releases R B Requests S Requests T Releases T Releases S C Requests T Requests R Releases R Releases T Processes A B C Resources R S T A requests R C requests T A requests S B requests S

B requests T C requests R A releases S A releases R C releases R C releases T 13 Deadlocks: Strategies Ignore the problem Detection and recovery Fix the problem afterwards Dynamic avoidance It is users fault Careful allocation Prevention Negate one of the four conditions 14 The Ostrich Algorithm

Pretend there is no problem Reasonable if Deadlocks occur very rarely Cost of prevention is high UNIX and Windows take this approach It is a trade-off between Convenience Correctness 15 Deadlock Detection and Recovery One Resource of Each Type R A B C S D

F U W G T E V A cycle can be found within the graph, denoting deadlock 16 One Resource of Each Type, do for each node init notebook L add current node CN to L cycle detected is CN two times in L? backtracking CN = previous node follow the arc CN = next node is an unmarked outgoing arc at CN? 17 Deadlock Detection and Recovery Multiple Resources of Each Type Existing resources

Available resources E1, E2 , E3 ,..., Em A1 , A2 , A3 ,..., Am C - Current allocation matrix C11 C12 C C22 21 ... ... Cn1 Cn 2 C13 C23 ... Cn 3 ... C1m ... C2 m ... ... ... Cnm R - Request matrix R11 R 21 ... Rn1 R12 R22 ...

Rn 2 R13 ... R1m R23 ... R2 m ... ... ... Rn 3 ... Rnm 18 E=( 4 2 3 )1 Ta pe Pl driv ot te ers rs Sc an n C ers D -R om s Ta pe Pl driv ot te ers rs Sc an n C ers D

-R om s Deadlock Detection and Recovery Multiple Resources of Each Type A=( Current allocation matrix C= 0 0 1 0 2 0 0 1 0 1 2 0 2 1 0 )0 Request matrix R= 2 0 0 1 1 0 1 0 2 1 0 0 19 Deadlock Detection and Recovery Recovery Recovery through preemption Recovery through rollback

Take a resource from some other process Depends on nature of the resource Checkpoint a process periodically Use this saved state Restart the process if it is found deadlocked Recovery through killing processes Crudest but simplest way to break a deadlock Kill one of the processes in the deadlock cycle The other processes get its resources Choose process that can be rerun from the beginning 20 Deadlock Avoidance Resource Trajectories finished B Printer release Plotter release request request start Two process

resource trajectories A request request release release Printer Plotter 21 Deadlock Avoidance Safe and Unsafe States, example 1 has max A 3 B 2 C 2 Free: 3 has max 9 4 7 A 3 B 4 C 2 Free: 1 has max 9 4

7 A 3 B 0 C 2 Free: 5 has max 9 A 3 B 0 7 C 7 Free: 0 has max 9 7 A 3 B 0 C 0 Free: 7 9 state is safe 22 Deadlock Avoidance Safe and Unsafe States, example 2 A 3 B 2 C 2 Free: 3

has max has max has max 9 4 7 A 4 B 2 C 2 Free: 2 9 4 7 A 4 B 4 C 2 Free: 0 has max 9 4 7 A 3 B 0 C 2 Free: 4 9 7 state is safe but unsafe here here We goofed allocating one more to A!

23 Deadlock Avoidance Bankers Algorithm for a Single Resource Each process has a credit System knows how many resources a process requests at most before releasing resources Total resources may not satisfy all credits Keep track of resources assigned and needed Check on each allocation whether it is safe Safe: there exists a sequence of other 24 Deadlock Avoidance Banker's Algorithm for a Single Resource Resource allocation state has max has max has max A 0

6 6 A 6 3 5 1 6 A 1 6 B 5 0 5 B 5 3 1 5 B 2 5 C 4 0 4 C 4 2 4 C 2

4 D 7 0 7 D 7 4 7 D 4 7 Free: 10 Free: Free:6 22 4 5 Free: 1 Safe Unsafe 25 Ta pe Pl driv ot te ers rs Sc an n

C ers D -R om s Deadlock Detection and Recovery Bankers Algorithm for Multiple Resources Assigned resources A B C D E 3 0 1 1 0 0 1 1 1 0 1 0 1 0 0 Resources still needed 1 0 0 1

0 A B C D E 1 0 3 0 2 1 1 1 0 1 0 1 0 1 1 0 2 0 0 0 E=( 6 3 4 )2 P=( 5 3 2 )2 A=(

1 0 2 )0 An example for the deadlock detection algorithm 26 Ta pe Pl driv ot te ers rs Sc an n C ers D -R om s Deadlock Detection and Recovery Bankers Algorithm for Multiple Resources Assigned resources A B C D E 3 0 1 0 0 0 1

1 0 0 1 0 1 0 0 Resources still needed 1 0 0 0 0 A B C D E 1 0 3 2 1 1 1 1 0 1 0 1 0 2

0 0 E=( 6 3 4 )2 P=( 4 2 2 )1 A=( 2 1 2 )1 An example for the deadlock detection algorithm 27 Ta pe Pl driv ot te ers rs Sc an n C ers D -R om s Deadlock Detection and Recovery Bankers Algorithm for Multiple Resources Assigned resources A B

C D E 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 Resources still needed 0 0 0 0 0 A B C D E 0 3 2 1

1 1 1 0 1 2 0 0 E=( 6 3 4 )2 P=( 1 2 1 )0 A=( 5 1 3 )2 An example for the deadlock detection algorithm 28 Ta pe Pl driv ot te ers rs Sc an n C ers D -R om s

Deadlock Detection and Recovery Bankers Algorithm for Multiple Resources Assigned resources A B C D E 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 Resources still needed 0 0 0 0 0 A B C

D E 3 2 1 1 0 1 0 0 E=( 6 3 4 )2 P=( 1 1 1 )0 A=( 5 2 3 )2 An example for the deadlock detection algorithm 29 Ta pe Pl driv ot te ers rs Sc an n C ers

D -R om s Deadlock Detection and Recovery Bankers Algorithm for Multiple Resources Assigned resources A B C D E 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Resources still needed 0 0 0 0 0

A B C D E 2 1 1 0 E=( 6 3 4 )2 P=( 0 0 0 )0 A=( 6 3 4 )2 An example for the deadlock detection algorithm 30 Ta pe Pl driv ot te ers rs Sc an n C ers

D -R om s Deadlock Detection and Recovery Bankers Algorithm for Multiple Resources SAFE Assigned resources A B C D E 3 0 1 1 0 0 1 1 1 0 1 0 1 0 0 Resources still needed 1 0 0 1 0

A B C D E 1 0 3 0 2 1 1 1 0 1 0 1 0 1 1 0 2 0 0 0 E=( 6 3 4 )2 P=( 5 3 2 )2 A=(

1 0 2 )0 An example for the deadlock detection algorithm 31 Deadlock Avoidance Practical Avoidance Two Phase Locking Phase I Phase II Process tries to lock all resources it needs, one at a time If needed resources found locked, release everything and start over (no real work done in phase one) Run Releasing locks Note similarity to requesting all resources at once Algorithm works where programmer can 32

Deadlock Prevention R: Conditions for Deadlock 1. Mutual exclusion condition Each resource assigned to 1 process or is available 2. Hold and wait condition Process holding resources can request additional 3. No preemption condition Previously granted resources cannot forcibly taken away 4. Circular wait condition Must be a circular chain of 2 or more processes Each is waiting for resource held by next member of the chain 33 Deadlock Prevention Mutual Exclusion Condition Some resources are not sharable Printer, tape, etc

Some resources can be made sharable Some resources can be made virtual Spooling - Printer Does spooling apply to all non-sharable resources? Mixing - Soundcard Principle: Avoid assigning resource when not absolutely necessary A few processes as possible actually claim the resource 34 Deadlock Prevention Hold and Wait Condition Require processes to request resources before starting Problems

A process never has to wait for what it needs Telephone companies do this May not know required resources at start of run Also ties up resources other processes could be using Variation: Process must give up all resources Then request all immediately needed 35 Deadlock Prevention No Preemption Condition This is not a viable option Consider a process given the printer Halfway through its job No forcibly take away printer !!?? 36 Deadlock Prevention Circular Wait Condition

1. 2. 3. 4. 5. A CD Rom drive Tape drive Plotter Scanner Imagesetter 1 2 3 4 5 Normally ordered resources A resource graph 37 Deadlock Prevention Circular Wait Condition Impose an order of requests for all resources Method

Assign a unique id to each resource All resource requests must be in an ascending order of the ids Release resources in a descending order Can you prove this method has no circular wait? Is this generally feasible? 38 Deadlock Prevention Overview Condition Approach Mutual exclusion Spool everything Hold and wait Request all resource initially No preemption Take resources away Circular wait Order resources numerically 39 Which is your favorite?

Ignore the problem Detection and recovery Fix the problem afterwards Dynamic avoidance Its the users fault Careful allocation Prevention (Negate one of four conditions) Avoid mutual exclusion Avoid hold and wait No preemption No circular wait 40 Tradeoffs and applications Ignore the problem for applications

Is the application developers job to deal with their deadlocks OS provides mechanism to break applications deadlocks Kernel should not have any deadlocks Use prevention Most popular is preventing circular wait 41 Non-resource Deadlocks Possible for two processes to deadlock Each is waiting for the other to do some task Can happen with semaphores Each process required to do a down() on two semaphores (mutex and another) If done in wrong order, deadlock results 42 Preempting Scheduler Activations

Scheduler activations are completely preemptable User space Kernel space 43 Preempting Scheduler Activations Maintaining the run queue needs to be a protected critical section Lets use spin locks for protection Thread 1 Upcall Acquire spin lock Start queue maintenance Interrupt Thread 1 Acquire spin lock -> block 44 Preempting Scheduler Activations So how do they handle this deadlock? Thread 1 Upcall Acquire spin lock

Start queue maintenance Interrupt Thread 1 Acquire spin lock -> block 45 Preempting Scheduler Activations Detection and recovery (like in Mach) Basic idea: Upcall handler checks first the state of each interrupted thread If it is in a critical section allow it to finish this Implementation: Protect critical sections with spin locks Acquire_spin_lock() increments a counter in the threads descriptor Upcall handler checks spin lock count of all interrupted threads If there are threads that hold spin locks set flag Switch to the context of these threads Afterwards switch back to upcall handler

46 Summary Modelling resource allocations Introduction to deadlocks Strategies Ostrich algorithm Deadlock detection and recovery Deadlock avoidance Deadlock prevention Non-resource deadlocks 47

Recently Viewed Presentations

  • Essay Writing FAQ - Trinity College, Dublin

    Essay Writing FAQ - Trinity College, Dublin

    Things to avoid: Being off subject—i.e. discussing a topic not related to the one proposed by the essay question.. Writing a chaotic essay —i.e. a piece of writing in which the elements of your argument are not logically linked (1)...
  • Chapter 17:classification of matter

    Chapter 17:classification of matter

    Section 1—Composition of Matter. Chapter 17:classification of matter. MATERIALS ARE MADE OF A PURE SUBSTANCEOR A MIXTURE OF SUBSTANCES. A PURE SUBSTANCE, or simply a substance, is either an element ( iron or silver) or a compound (NaCl, H2O).
  • Chapter 9

    Chapter 9

    Josie. Andy. Clara. Joe. Sofia. Validity. ... Jensen- reaction time and inspection time. Brain Size & IQ. Intelligence and longevity. Cognitive processes. Triarchic Theory of Human Intelligence . Contextual subtheory- intelligence is a culturally defined concept.
  • Preventing Family Homelessness

    Preventing Family Homelessness

    Preventing Family Homelessness Presentation Outline Homelessness Prevention New York City's Mayor, Bloomberg's 5 year plan to reduce homelessness. HomeBase is a key component of that plan. What Is HomeBase? HomeBase is a creative, data-driven approach to preventing homelessness. HomeBase in...
  • A reconstruction of Phidias' statue of Zeus, in an engraving ...

    A reconstruction of Phidias' statue of Zeus, in an engraving ...

    Made from Parian marble it stands 2,10m in height. It is thought to be an original of the great sculptor and it is dated to ca. 330 B.C PRAXITELES Cridian Aphrodite 350- 40 B.C. marble Munich, Glyptothek Apoxyomenos, Roman marble...
  • Performance Task Overview Introduction PERFORMANCE TASK  This training

    Performance Task Overview Introduction PERFORMANCE TASK This training

    The online system provides many common word-processing tools such as an embedded dictionary and thesaurus,bold, italics, underlining, copy, paste, and spell check to assist the student with the writing assignment.
  • Lego Mindstorms and NXT-G

    Lego Mindstorms and NXT-G

    Lego Mindstorms and NXT-G Magnus Eriksson, Mid Sweden University 2012 ... Parking NXT Program your NXT car to drive forward until you "find a parking spot" (hit a touch sensor) The car should then turn into the spot, and stop...
  • Transcription and Translation

    Transcription and Translation

    corresponds to an amino acid. There are more codons than amino acids (64 codons, only 20 amino acids) so most amino acids have more than one codon specific to them. For example, four different codons—ACG, ACA, ACC, ACU—specify the amino...