- Hello everyone! In my previous two posts I had explained some basic information regarding “Deadlock” and “Necessary Conditions to occur Deadlock”. if you haven’t read those posts yet, I strongly suggest you to read that first before proceeding to this post.
- 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.
- If necessary conditions for a deadlock are about to occur, it is still possible to avoid deadlock by taking care when resources are allocated.
- The following features should be considered to avoid deadlock as per baker’s algorithm:
- Each process declares maximum number of each resource type that it may need.
- Keep the system in a safe state in which we can allocate resources to each type in some order to avoid deadlock.
- 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:
- It is time consuming to execute on every request of each resource.
- If the claim information [information about resource] is not accurate, system resources may be underutilized.
- When a system is heavily loaded, very few safe sequences remain as so many resources are granted.
- Arrival of new process may create problems:
- The requested resources by the process must be less than the total number of available resources.
- 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.
- To avoid starvation problem among processes it require a little more work but it not much harder.
- If resource becomes unavailable [for example damage in tap drive], it can result in an unsafe state.
- Please read my next post Deadlock Detection fore more information.