• In this post I will explain deadlock avoidance techniques in brief. So lets start!
  • This method uses different algorithms to avoid deadlocks in advance before it could occur.
  • It uses algorithms to check the possibility of deadlock and takes action accordingly.
  • This method is different from deadlock prevention which guarantees that deadlock cannot occur by breaking one of the necessary conditions for deadlock.

Banker’s Algorithm

  • One of the most commonly used deadlock avoidance algorithms is the Banker’s algorithm introduced by Dr. D.W. Dikjistra in 1965.
  • It uses similar concept used by banker to decide if the loan can be granted or not.
  • Banker’s algorithm is based on banking system. A bank never allocates its available can in such a manner that it can no longer satisfy the needs of all its customers.
  • The system must have the advance knowledge of the maximum possible requests for each process which is limited by available resources.
  • During the system run we should keep monitoring the status of the resource allocation to ensure that no circular wait condition become true.
  • The following features should be considered to avoid deadlock as per baker’s algorithm:
  1. Each process declares maximum number of each resource type that it may need.
  2. Keep the system in a safe state in which we can allocate resources to each type in some order to avoid deadlock.
  3. Check for the safe state by finding a safe sequence: <P1,P2,….Pn>
  • The resource allocation status is defined by the number of available and allocated resources and the maximum demands of the process.
  • The system can be in one of the following status:

Safe State

A state is safe if the system can allocate resources to each process (up to its maximum need) in some order without creating deadlock.

A system is said to be in a safe state only if there exists a safe sequence.

Unsafe State

If a system does not have any safe sequence to follow for resources allocation and it is in a situation which may result to a deadlock then system is in unsafe state.

Deadlock State

  • If there exists circular wait condition for some processes in the system then it is a deadlock state and we can say that system is in a deadlock state.
  • Now let’s study the following example to understand this concept.

Example

Consider a situation in which 4 processes [P1,P2,P3,P4] can be compared with the customers in a bank, resources such as printers as a cash available in the bank and the operating system as a banker. Let assume that total number of available resources are 10.

Processes Resouces used Max. resource
P1 0 6
P2 0 5
P3 0 4
P4 0 7
  • As we can see that the operating system has only 10 resources available. So all request cannot be granted at once.At some later stage the situation becomes as follow:
Processes Resources used Max. resource
P1 1 6
P2 1 5
P3 2 4
P4 4 7

Now total available resurcesare : 2

Safe State

  • For a system to be in a safe state there must exists at least one way for all process to finish.
  • The state of the above table is safe because with available 2 resources the operating system can allocate both resources to P3 first. After completion of P3 it will release all 4 resources. Now with 4 resources the operating system can either grant request of P4 or P2 and so on.

Unsafe State

  • consider what would happen if a request from P2 for one more unit was granted? We would then have the following situation: 
Processes RESOURCES used Max. resource
P1 1 6
P2 2 5
P3 2 4
P4 4 7

 Now available resource is 1:

  • This is an unsafe state because the operating system could not satisfy any of them and system would have deadlock.

Note: It should be noted that an unsafe state does not means that system is in a deadlock or it will have deadlock. Unsafe state means only that system may have possibility for a deadlock because of unsafe sequence.

  • This way baker’s algorithm is used to consider each request and check that after granting it the system will be in a safe state not.
  • If system it does then request is granted otherwise it is postponed for later.

Limitations of the Banker’s Algorithm:

  • Habeman shown that since algorithm is executed each time a resource request arrives, the overhead is quit high.
  • The main limitations of the banker’s algorithm are as follow:
  1. It is time consuming to execute on every request of each resource.
  2. If the claim information [information about resource] is not accurate, system resources may be underutilized.
  3. When a system is heavily loaded, very few safe sequences remain as so many resources are granted.
  4. Arrival of new process may create problems:
  5. The requested resources by the process must be less than the total number of available resources.
  6. Since the state without the new process is safe, it would be also safe with the new process. A the new process will be added at the end.
  7. To avoid starvation problem among processes it require a little more work but it not much harder.
  8. If resource becomes unavailable [for example damage in tap drive], it can result in an unsafe state.