Deadlocks in a system causes it to stop working because all the process depend on each other to take the first step which causes the processes to starve. So in order to not let deadlocks from happening we can either prevent them or avoid them in the first place. We have already looked at how we can prevent deadlocks from occuring in Day 90 and now we learn how we can avoid the deadlocks in the first place.
Deadlock Avoidance is a technique to avoid deadlock. It requires the information about how different processes would request different resources. When given with several resources we can organise them in some order that will not let any deadlock to appear. Some of the methods of avoiding deadlocks are explained below.
Safe State
A state is said to be in a safe state when the system allocates the required resources to the user process up to a maximum required limit in a particular sequence and also avoiding deadlocks. In safe state no deadlock can occur and if one occurs it is said to be in an unsafe state. So we need avoid the system from going into an unsafe state in order to avoid a deadlock from occuring.
For example consider there are 24 output devices and three processes executing. Now process P0, P1 and P2 may require up to 20, 8 and 18 output devices respectively during execution. All of them are given access to 10, 4, 4 output devices at the same time respectively. The system is said to be in a safe state since there is a safe sequence that avoids the deadlock.
Safe Sequence
P0, P1 and P2 need 10, 4 and 14 more resources respectively to complete their execution and there are 6 extras that are left untouched up until now. So we can allocate four to P1 which we complete its execution and releases all the 8 resources and after that we can allocate 10 resources to P0 which will complete its execution as well. All this while avoiding any deadlock. and so on to P2.
Unsafe Sequence
Now if we were to give 6 resources initially to P2 the system will enter in an unsafe state. Now if P1 is given 4 remaining resources to complete its execution and release them after the exection. Now we have only eight free resources which are not enough for any remaining process to complete its exection. So a deadlock will occur in the system.
Resource Allocation Graph Algorithm
Resource Allocation Graph Algorithm is used to avoid deadlocks. This algorithm uses an edge in the resource allocation graph called calim edge to avoid deadlocks. The claim edge is a dashed line on the graph and indicates that a process may request the resource in future. If the process requests that resource in the future, claim edge is converted to assignemnt edge which is a solid line on the graph. This indicates that the resource has been allocated to the porcess.
When a process releases a resource the assignment edge is again converted into a claim edge.
Image Courtesy: Wikipedia
zainsci