Short Note on Deadlock avoidance algorithm in Distributed Systems.
1 Answer
  • Deadlock avoidance methods use some advance knowledge of the resource usage of process to predict the future state of the system for avoiding allocations that can eventually lead to a deadlock.
  • Deadlock avoidance algorithms are usually in the following steps:

i.When a process requests for a resource, if the resource is available for allocation it is not immediately allocated to the process rather the system assumes that the request is granted.

ii.Using advance knowledge of resource usage of processes and assumptions of step 1 the system analysis whether granting the process request is safe or unsafe.

iii.The resource is allocated to the process only if the analysis of step 2 shows that it is safe to do so otherwise the request is deferred.

  • It is important to look at the notion of safety in resource allocation because all the algorithms for deadlock avoidance are based on the concept of safe and unsafe states.
  • A system is said to be in safe state if it is not in a deadlock state and there exists some ordering of the process in which the requests are granted to run all of them to completion.
  • Any ordering of the process that can guarantee the completion of all the processes is called safe sequence.
  • The formation of safe sequence should satisfy the condition that for any process Pi in a safe sequence, the resource that Pi can still request and can be satisfied by currently available resources plus the resources held by all processes lying before Pi in the safe sequence.
  • This condition guarantees that the process Pi can be run to completion if the resource that Pi needs are not immediately available and Pi can wait until all the processes in the sequence lying before Pi have finished. When they have finished Pi can obtain all its needed resource and run to completion.
  • A system is said to be unsafe if no safe sequence exists for that state.
  • Example:

enter image description here

  • Assume a system having 8 units of a particular resource type for which three processes P1, P2 and P3 are competing and the maximum units of the resource required by them are 4, 5, and 6 respectively.
  • Each of the three resources is holding 2 units of the resource therefore in the current state of the system 2 units of resource are free. The aim is to find whether stat in fig(a) is safe or unsafe. The figure shows that the state is safe because sequence of allocations to allow process completion exists and the safe sequences are (P1, P2, P3) and (P1, P3, P2).
  • In fig(a) the scheduler could simple run P1 until it asked for and got two more units of the resource that are currently free leading to state of fig(b). When P1 completes and releases the resource held by it the state in fig(c) is achieved. Then the scheduler chooses to run P2 which leads to the next state of fig (d). When P2 completes and releases resources held by it the system enters the state of fig(e). P3 can now run to completion with the available resources.
  • The initial state of fig(a) is safe state because the system can avoid deadlock by careful scheduling. If resource allocation is not done carefully the system can move from a safe state to unsafe state.
  • Deadlock avoidance algorithm basically perform resource allocation is such a manner that ensures the system will always remain in safe state.
  • Since initial state is always safe state, when a process requests a resource that is available, the system checks if allocation causes the shift from safe to unsafe state. If no then the request is granted or else it is deferred.
Please log in to add an answer.