Operating System

Deadlock Avoidance


Deadlock Avoidance

Deadlock Avoidance approach to the deadlock problem anticipates deadlock before it actually occurs. This approach employs an algorithm to access the possibility that deadlock could occur and acting accordingly. If the necessary conditions for a deadlock are in place, it is still possible to avoid deadlock by being careful when resources are allocated. It employs the most famous deadlock avoidance algorithm that is the Banker’s algorithm.

A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that a circular wait condition can never exist. The resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

Safe and Unsafe States

A system is said to be in a Safe State if there is a safe execution sequence. An execution sequence is an ordering for process execution such that each process runs until it terminates or blocked and all request for resources are immediately granted if the resource is available.

A system is said to be in an Unsafe State if there is no safe execution sequence. An unsafe state may not be deadlocked, but there is at least one sequence of requests from processes that would make the system deadlocked.

safe state

(Relation between Safe, Unsafe and Deadlocked States)

Resource-Allocation Graph Algorithm


The deadlock avoidance algorithm uses a variant of the resource-allocation graph to avoid the deadlocked state. It introduces a new type of edge, called a claim edge. A claim edge Pi àRj indicates that process Pi may request resource Rj at some time in the future. This edge resembles a request edge in direction but is represented by a dashed line. When process Pi requests resource Rj, the claim edge Pi àRj is converted to a request edge. Similarly, when a resource Rj is released by Pi, the assignment edge Rj àPi is reconverted to a claim edge Pià Rj.

Suppose that process Pi requests resource Rj. The request can be granted only if converting the request edge Pi à Rj to an assignment edge Rjà Pi that does not result in the formation of a cycle in the resource-allocation graph. An algorithm for detecting a cycle in this graph is called the cycle detection algorithm.

If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is found, then the allocation will put the system in an unsafe state. Therefore, process Pi will have to wait for its requests to be satisfied.

Leave a Reply

Your email address will not be published. Required fields are marked *