RESOURCE ALLOCATION GRAPH

• P1 is holding an instance of R2 and requeas instance os R1
• P2 is holding an instance of R1
• P3 is holding an instance of R1 and instance of R2
• P4 is holding instance of R2

• P1 is holding instance of R2 and request instance of R2 and requeast of R1
• P2 is holding instance of R1 and R2 then requeat of instance of R3
• P3 is holding instance of R3 and request instance of R2
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  

deadlock

1.Deadlock Characterization

necessary conditions:

1) Mutual exclusion:
• at least one shared resource is held

2) Hold and wait:
• a process must be holding at least one resource andwaiting for another

3) No preemption:
• cannot steal a resource away from a process

4) Circular wait:
• E.g., A is waiting for B who is waiting for C who iswaiting for A.

deadlock

2.methods for handling deadlock

3.deadlock prevention

*negate one of the necessary conditionsNegating Mutual Exclusion :

example:shared use of a printer

»give exclusive use of the printer to each user in turn wanting to print?
»deadlock possibility if exclusive access to another resource also allowed
»better to have a spooler process to which print jobs are sent

-­complete output file must be generated first

example: file system actions

»give a process exclusive access rights to a file directory

example: moving a file from one directory to another

­-possible deadlock if allowed exclusive access to two directories simultaneously
­-should write code so as only to need to access one directory at a time

deadlock

4.deadlock detection

• Allow system to enter deadlock state

• Detection algorithm

•Recovery scheme

5.deadlock recovery
•Pre-emption–take resources from a process and give to others

–how to select a victim?

»order of precedence for pre-empting
»number of resources already held
»how many more will it need to complete?
»amount of CPU time already used–swapping process out of memory may be sufficient
»but may still hold resources involved in deadlock

–may need to roll pre-empted process back

»back to some safe restart point or go back to beginning
»may need to checkpoint processes
»not convenient for user interaction!

–need to avoid starvation of a low priority process always being pre-empted

»include number of previous pre-emptions as a choice factor