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.