Deadlock avoidance
Definition
Deadlock avoidance is less restrictive than deadlock prevention.
None of the deadlock conditions is denied at a priori.
The resource system is monitored in order to decide what to do in terms of resource allocation.
Requires knowledge in advance of maximum process resource requests.
The intervening processes have to declare at start their needs in terms of resources.
Two possible approaches.
Process Initiation Denial
Do not start a process if its demands might lead to deadlock.
Resource Allocation Denial
Do not grant an incremental resource request to a process if this allocation might lead to deadlock.
Process initiation denial
The system prevents a new process to start if its termination can not be guaranteed.
Let.
R = (R1 , R2 , · · · , Rn ) be a vector of the total amount of each resource.
P be the set of processes competing for resources.
Cp be a vector of the total amount of each resource declared by process p ∈ P.
A new process q(q 6∈ P ) is only started if
It is a quite restrictive approach.
Resource allocation denial
A new resource is allocated to a process if and only if there is at least one sequence of future allocations that does not result in deadlock.
In such cases, the system is said to be in a safe state.
Let.
R = (R1 , R2 , · · · , Rn) be a vector of the total amount of each resource.
V = (V1 , V2 , · · · , Vn) be a vector of the amount of each resource available.
P be the set of processes competing for resources.
Cp be a vector of the total amount of each resource declared by process p ∈ P.
Ap be a vector of the amount of each resource already allocated to process p ∈ P.
A new request of a process q is only granted if, after it, there is a sequence s(k), with s(k) ∈ P and k = 1, 2, · · · , |P |, of processes, such that.
This approach is called the banker’s algorithm.
Banker’s algorithm
Consider the system state described by the table. Is it a safe state?
P2 may still request 2 R2, but only one is available.
P3 may still request 4 R3, but only one is available.
All resources that P1 can still request are available.
Consider the following sequence:
P1 requests all the resources it can still; the request is granted; then terminates.
P2 requests all the resources it can still; the request is granted; then terminates.
P3 requests all the resources it can still; the request is granted; then terminates.
If P3 requests 2 resources of type R3, the grant is postponed. Why?
Because only 1 is available.
If P3 requests 1 resource of type R2, the grant is also postponed. Why?
Because, if the grant is given, the system transitions to an unsafe state.
Example
Every philosopher first gets the left fork and then gets the right one.
However, in a specific situation the request of the left fork is postponed.
Last updated