Deadlock avoidance is a very important topic in operating system. So, first let us understand the basics related to deadlock.
What is a deadlock?
In a multiprogramming environment, there are several processes running concurrently. Each of these processes may compete for a limited or finite number of resources. If a process requests resource, and it is not available, then it has to wait for the resource, and so it enters into wait state. But the waiting process may never change state, because the resources they have requested are held by other waiting processes. Such a situation is called deadlock.
Safe state
A system is in a safe state if it can allocate resources to each process in some order and still avoids a deadlock.
ILLUSTRATION
Let us consider a system with 12 magnetic tape drives and 3 processes. p0,p1 and p2. Process p0 requires 10 tape drives, process p1 requires 4 tape drives and process p2 may need up to 9 tape drives. Suppose, at time t0, process p0 is holding 5 tape drives, process p1 is holding 2 tape drives and process p2 is holding 2 tape drives.
|
MAXIMUM NEEDS |
CURRENT NEEDS |
| p0 |
10 |
5 |
| p1 |
4 |
2 |
| p2 |
9 |
2 |
Now, the systems is in safe state. The question is, can the sequence,<p1,p0,p2> satisfy the safety condition.
EXPLANATION
TOTAL NUMBER OF TAPE DRIVES = 12
NUMBER OF FREE TAPE DRIVES = 12-9=3
p1 requires 2, allotted 2, so number of free tape drives = 1
Since p1 got its maximum need, it finishes its work and returns all the 4 tape drives.
NUMBER OF FREE TAPE DRIVES NOW = 1+4 = 5
p0 requires 5, allotted 5, so number of free tape drives = 0
Since p0 got its maximum need, it finishes its work and returns all the 10 tape drives.
NUMBER OF FREE TAPE DRIVES NOW = 10
p2 requires 7, allotted 7, and p2 also got its maximum need and it finishes its work and returns all the tape drives.
The system is in safe state if the sequence is <p1,p0,p2>.
UNSAFE STATE
Let us consider, that at time t1, process p2 requests 1 tape drive and is allotted 1 more. So, the maximum and current needs are depicted as below.
|
MAXIMUM NEEDS |
CURRENT NEEDS |
| p0 |
10 |
5 |
| p1 |
4 |
2 |
| p2 |
9 |
3 |
TOTAL NUMBER OF TAPE DRIVES = 12
NUMBER OF FREE TAPE DRIVES = 12 - 10=2
p1 requires 2, allotted 2, so number of free tape drives = 0
Since p1 got its maximum need, it finishes its work and returns all the 4 tape drives.
Now, neither p0 nor p2 can be allotted the rest for completion. So, the system is in unsafe state.
Let us try to solve some problems on deadlock avoidance.
JUNE 2013-PAPERIII QUESTION NO 61
An operating system using banker’s algorithm for deadlock avoidance has ten dedicated devices (of same type) and has three processes P1, P2 and P3 with maximum resource requirements of 4, 5 and 8 respectively.
There are two states of allocation of devices as follows :
State 1 Processes P1 P2 P3
Devices allocated 2 3 4
State 2 Processes P1 P2 P3
Devices allocated 0 2 4
Which of the following is correct ?
(A) State 1 is unsafe and state 2 is safe.
(B) State 1 is safe and state 2 is unsafe.
(C) Both, state 1 and state 2 are safe.
(D) Both, state 1 and state 2 are unsafe.
Ans:- A
EXPLANATION:-
|
MAXIMUM NEEDS |
CURRENT NEEDS |
| p1 |
4 |
2 |
| p2 |
5 |
3 |
| p3 |
8 |
4 |
NUMBER OF FREE DEVICE = 10
NUMBER OF FREE DEVICE = 10-9=1
Since the number of free device is just 1, it can be allocated to any of the processes p1,p2 or p3.
p1 requires 2, as it is allocated only 2.
p2 requires 2, because it is already allocated 3 and its maximum need is 5.
p3 requires 4, because it is already allocated 4 and its maximum need is 4.
Since, none of the processes requirement can be satisified, the state 1 is in unsafe state.
|
MAXIMUM NEEDS |
CURRENT NEEDS |
| p1 |
4 |
0 |
| p2 |
5 |
2 |
| p3 |
8 |
4 |
Let us see whether state 2 is in safe or unsafe state.
TOTAL NUMBER OF FREE DEVICES = 10
NUMBER OF FREE DEVICE=10-6=4
Process p1 requires a maximum of 4 devices and they can be allocated, because the number of free device right now is 4. Since p1 gets its maximum need, it completes the process and returns all of the 4 devices.
Process p2 requires a maximum of 5, which can be allocated right now. p2 completes its process and returns all the 5 devices.
Process p3 requires a maximum of 8, which also can be allocated right now. So, p3 also can finish its execution successfully.
So, state 2 is in safe state
So, the correct answer for the question is State 1 is in unsafe state and state 2 is in safe state which is option A.
