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