Deadlock Flashcards
What’s the definition of a deadlock?
A set of processes is deadlocked if each process in the set is waiting
for an event that only a process in the set can cause
In the context of synchronization, the event is a resource.
In a Resource allocation graph what are the 2 types of edges?
- Request = edge from process to
resource type - Allocation = edge from resource
instance to a process
How can we simplify the Resource allocation graph When there’s only one
instance per resource type?
By eliminating resources and only marking dependencies between processes.
e.g: P1 requests resource R1 which is held by P2.
so we will just have a directed edge from P1 to P2.
What are the 4 Necessary conditions for deadlock?
All of these must hold in order for a deadlock to occur:
- Mutual exclusion
• Some resource is (i) used by more than one process, but is
(ii) exclusively allocated one process at a time (cannot be shared)
• If used by only one process, or can be shared => can’t deadlock - Hold & wait
• Processes may hold one resource and wait for another
• If resources allocated atomically altogether => can’t deadlock - Circular wait
• P(i) waits for resource held by P((i+1) % n) // some enumeration
• Otherwise, recursively, there exists one process that need not wait - No resource preemption
• If resources held can be released (e.g., after some period of time),
then can break circular wait
Who is responsible for dealing with deadlocks?
– Typically, you (the programmer)
• You need to be aware and do it yourself
What are the 2 ways of dealing with deadlocks?
- Design the system such that it is never allowed to enter into
a deadlock situation
– Example: this is how we’ll acquire locks - Allow the system to experience deadlock, but put in
mechanisms to detect & recover
– Example: memory exhaustion
=> kill random process
(or write it to disk and leave it there for a long while)
What’s deadlock prevention?
violate 1 of the 4 conditions
How can we detect a deadlock?
If there’s only one instance of each resource type
– Search for a cycle in the (simplified) resource allocation graph
• Found deadlock
In the general case, which allows multiple instances per type
– Necessary conditions for deadlock != sufficient conditions for deadlock
– A graph can have a cycle while the system is not deadlocked
- Still algorithms for detection exist.
What’s deadlock avoidance?
System stays away from deadlocks by being careful
on a per resource-allocation decision basis
Bankers algorithm.
How the bankers algorithm works?
Banker’s data structure
– max[p] = (m_1,m_2, …, m_k) = max resource requirements for process p
– cur[p] = (c_1,c_2, …, c_k) = current resource allocation for process p
– R = (r_1, r_2, …, r_k) = the current resource request (for process p)
– avail = (a_1, a_2, …., a_k) = currently available (free) resources (global)
Tentatively assume that request R was granted
– cur[q] += R // vector addition
– avail -= R // vector subtraction
• Check if “safe state” (= can satisfy all processes in some order)
– initialize P to hold all non-terminated process
– while( P isn’t empty ) {
found = false
for each p in P { // find one p that can be satisfied
if( max[p] – cur[p] <= avail ) // p’s biggest request
avail += cur[p] // pretend p terminates
P -= {p}
found = true
}
if( ! found ) return FAILURE
}
return SUCCESS
What’s a safe state in the bankers algorithm?
A state whereby we’re sure that all processes can be executed, in a
certain order, one after the other, such that each will obtain all the
resources it needs to complete its execution
Thus the bankers algorithms is conservative?
Yes. as there’s a possibility for no
deadlock even if allocation is made, but OS doesn’t take that chance
What’s the time complexity of the bankers algo?
O(n^2)
– Even though number of possible orders is n!
– Since resources increase monotonically as processes terminate
– As long as it’s possible to execute any set of processes
• Execution order not important
• (There is never any need to backtrack and try another order)
