Operating Systems (OS) : Operating Systems (OS) Deadlock
Lecture 11
Dag Nyström
Outline : Outline What is deadlock?
Strategies for handling deadlock
What is deadlock? : What is deadlock? Consider the following example: A B S1 S2 Process Resource Legend: A B A owns B A B A wants B “The arrow points at the
controlling node”
Formal definition of Deadlock : Formal definition of Deadlock 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
Resources : Resources A hardware device or a piece of data
Two types of resources
Preemptable
Non-preemptable
Deadlock can only occur with non-preemptable resources.
The following show how a resource is used:
Claim the resource
Use the resource
Release the resource
Conditions for deadlock : Conditions for deadlock Mutual exclusion
A resource is either assigned to 1 process or available
Hold and wait condition
Possible to own one resource while claiming another
No preemption condition
granted resources cannot taken away by force
Circular wait condition
Each waiting process is waiting for the next in the chain
All four conditions must be met in order for a deadlock to occur
Dining philosophers problem : Dining philosophers problem 5 philosophers
1 table
5 forks
A philosopher can either think or eat
Eating procedure:
Pick up left fork
Pick up right fork
Eat
Return both forks
How can we deal
with the problem?
Deadlock management strategies : Deadlock management strategies The Ostrich algorithm
Deadlock detection
Deadlock avoidance
Deadlock prevention
The ostrich algorithm : The ostrich algorithm The easiest way to deal with the problem:
Stick your head in the sand and
pretend that there is no problem
How is it possible to use such an algorithm?
Other errors are much more frequent
To not add limitations to the operating system The ostrich algorithm is both Windows and UNIX approved!!
Deadlock Detection : Deadlock Detection No limitations to resource allocations
Use algorithm to detect possible deadlock
Two cases:
One resource of each type
Multiple resources of each type
Resolve any deadlock found
When should algorithm be run?
When resource is claimed
Periodically, every n time unit
During idle periods
Deadlock Detection - One resource of each type : Deadlock Detection - One resource of each type Make a resource graph
Locate any cycles
Break the cycles found Exercise:
PA owns R and wants S
PB wants T
PC owns S
PD owns U and wants S and T
PE owns T and wants V
PF owns W and wants S
PG owns V and wants U
Is there deadlock in the system? Process Resource A B A owns B A B A wants B “The arrow points at the
controlling node”
Deadlock Detection - One resource of each type : Deadlock Detection - One resource of each type
Deadlock Detection - One resource of each type : Deadlock Detection - One resource of each type Algorithm for finding cycle:
For every node N in the graph, perform the following steps using N as starting node.
Initiate L as an empty set and unmark all arrows
If current node is NOT in the set, add current node to set, else deadlock is detected and the algorithm is terminated
If there are unmarked arrows from the current node go to 5 else go to 6
Randomly select one arrow and follow it.Set the new node as the current node. Go to 3
We have reached a dead end. Backtrack to previous node. If previous node is starting node go to 1 using a new starting node. If not, go to 4
Deadlock Detection - One resource of each type : Deadlock Detection - One resource of each type N=PB L={} =>L={PB} =>L={PB, T} =>L={PB, T, PE} =>L={PB, T, PE, V} =>L={PB, T, PE, V, PG} =>L={PB, T, PE, V, PG, U} =>L={PB, T, PE, V, PG, U, PD ,T} =>L={PB, T, PE, V, PG, U, PD}
Deadlock Detection - Many resources of each type : Solved using Matrices Deadlock Detection - Many resources of each type A vector of existing resources of type ex A vector of available resources of type ax A matrix containing the # of resources of
Type n claimed by process m. A matrix containing the # of resources of
Type n requested by process m. We see that:
Deadlock Detection - Many resources of each type : For two vectors, X and Y Deadlock Detection - Many resources of each type iff for
Deadlock Detection - Many resources of each type : The detection algorithm is applied periodically
Find an unmarked process Pi for which Ri A.
If such a process is found, add Ci to A. Mark the process and go to step 1.
If no such process is found, terminate.
All unmarked processes are deadlocked Deadlock Detection - Many resources of each type How on earth does this algorithm work?!?!?
Deadlock Detection - Many resources of each type : Exercise: Deadlock Detection - Many resources of each type Is there deadlock in the system?? 1 2 3 NO!!!
Deadlock Detection : Deadlock Detection How to recover from deadlock
Preemption
Process rollback
Kill one of the deadlocked process’s
Deadlock Avoidance : Deadlock Avoidance Avoids deadlock by cautious allocations
Safe and unsafe states
An allocation can only be granted if it puts the system in a safe state.
Deadlock Avoidance - Safe and unsafe states : Deadlock Avoidance - Safe and unsafe states
Deadlock Avoidance - Safe and unsafe states : Deadlock Avoidance - Safe and unsafe states Algorithms to determine the state
Based on the E,A,C and R matrices.
Example:
A total of 10 resources, with the following allocations:
Is the system in a safe or unsafe state?? Free 3 1 2 3 SAFE!!!
Deadlock Avoidance -Bankers Algorithm : Deadlock Avoidance -Bankers Algorithm Made by Dijkstra
Originating from loan allocations in a bank
Examines if an allocation leads to a safe or unsafe state
Is run when resource is requested
Two cases
One type of resource
Multiple types of resources
Deadlock Avoidance -Bankers Algorithm : Deadlock Avoidance -Bankers Algorithm Example using one type of resource:
SAFE! A requests 1 UNSAFE! NOT GRANTED! B requests 1 SAFE! GRANTED! C requests 1 SAFE! GRANTED!
Deadlock Prevention : Deadlock Prevention Very difficult to achieve
Attack one of the conditions for deadlock
Attack Mutual Exclusion
Attack Hold and Wait
Attack No preemption
Attack Circular wait