0 / 4
Deadlock
A deadlock is a state in which two or more processes each wait for a resource held by another, so none of them can proceed. It arises only when all four conditions hold: mutual exclusion, hold and wait, no preemption, and circular wait.
Example: P1 gets R1 and P2 gets R2 first. Arrows show who holds and who requests what. A drawing like this is called a resource-allocation graph.
1 / 4
Mutual Exclusion
R1 is allocated to P1, and R2 to P2. The printer and the scanner can be used by only one process at a time. Any other process that wants one must wait until it is released.
2 / 4
Hold and Wait
P1 holds R1 while it requests R2 and waits. P2 likewise holds R2 while it waits for R1. Neither gives back the resource it already holds.
3 / 4
No Preemption
Preemption means the operating system forcibly takes a resource away from the process using it. No preemption means it does not do that. A resource is released only when the process holding it finishes its work and gives it back on its own.
4 / 4
Circular Wait
P1 waits for R2, which P2 holds, and P2 waits for R1, which P1 holds. The waiting forms a cycle, so neither can finish first. With only one of each resource, a cycle of waiting means a deadlock, so both processes stay stuck.
1 / 4
Rule 1: Break mutual exclusion
Resources that can naturally be shared, such as read-only files, do not need mutual exclusion. A printer, however, must be used by one process at a time, or two print jobs would get mixed. So mutual exclusion is usually hard to break. This rule cannot stop the deadlock in the picture.
2 / 4
Rule 2: Break hold and wait
Each process must request all the resources it needs at once, before it starts. Another way is to let it request new resources only after giving back everything it holds. P2 holds nothing and waits until P1 gets both R1 and R2 and finishes. The cost is waste, since resources are held even while unused. A process may also wait forever for all its resources to be free at the same time, which is called starvation.
3 / 4
Rule 3: Break no preemption
If a process asks for another resource and cannot get it right away, it must give back everything it holds. Suppose P2 asks for R1 first. P2 cannot get R1 right away, so it gives back R2. After that, it waits again until it can get both R1 and R2. This rule suits resources whose state can be saved and restored, such as CPU registers and memory. It is hard to apply to a printer or a scanner, so the picture only shows how the rule works.
4 / 4
Rule 4: Break circular wait
Every resource type gets a number, and resources must be requested in increasing order of number. The printer R1 is number 1 and the scanner R2 is number 2, so P2 also has to request R1 first. While P2 waits for R1, R2 stays free and P1 will get it soon. So the waiting never forms a cycle.
1 / 5
Declaring needs in advance
When P1 and P2 start, they tell the operating system that they will need both R1 and R2. This declared amount is called the maximum demand. The operating system uses it to look ahead on every request.
2 / 5
P1 requests R1: safe, so granted
P1 requests R1. Even after granting it, there is an order in which P1 later gets R2 and finishes, and then P2 finishes. The state is safe, so R1 is allocated.
3 / 5
P2 requests R2: unsafe, so it waits
P2 requests R2. R2 is free, but if it were granted, P1 could end up waiting for R2 and P2 for R1. That is an unsafe state with no order in which both can finish. So R2 is not allocated, and P2 is made to wait. An unsafe state is not itself a deadlock. It is a state that risks leading to one.
4 / 5
P1 requests R2: safe, so granted
P1 requests R2. With it, P1 holds everything it needs and can finish right away. Then P2 can finish with the resources P1 gives back. The state is safe, so R2 is allocated.
5 / 5
P1 finishes, and P2 goes next
P1 finishes its work and gives back R1 and R2. When the R2 request P2 has been waiting on is checked again, it is safe this time, so R2 is allocated. R1, which P2 requests next, is allocated too. P2 also gets everything it needs and can finish without a deadlock.
1 / 4
Granting without checks
Unlike avoidance, a free resource is allocated right away, without any check. P1 gets R1, and P2 gets R2.
2 / 4
A deadlock forms
P1 requests R2, P2 requests R1, and they wait for each other. All four conditions hold and a deadlock has formed, but the operating system does not know it yet.
3 / 4
Running the detection algorithm
The detection algorithm follows the arrows, checking which process waits for which resource and who holds that resource. Running it every time a request cannot be granted right away is costly. So it usually runs at set intervals or when CPU utilization drops sharply.
4 / 4
A cycle is found
Starting from P1 and passing R2, P2, and R1, the path returns to P1, so a cycle is found. With one instance of each resource type, a cycle means a deadlock. With several instances of a resource type, a cycle does not always mean a deadlock, so a different detection algorithm is used.
1 / 5
Choosing a victim
The system picks a process to cut the cycle (the victim). It weighs things like priority, how long each process has run, and how many resources it holds, and chooses the one that costs least to stop. Here, say P2 is chosen because it has run for less time.
2 / 5
Freeing R2 from P2
There are two ways. Process termination forcibly ends P2. Resource preemption takes only R2 away from P2. Either way, R2 is freed and the cycle of waiting is cut.
3 / 5
P1 continues
P1, which had been waiting, gets R2 and runs.
4 / 5
P1 finishes and gives back
P1 finishes its work and gives back R1 and R2. Both resources are now free.
5 / 5
P2 runs again
If P2 was terminated, it runs again from the beginning. If its resource was taken away, it is returned to its state before it got R2 (rollback) and runs again. If the same process keeps being picked as the victim, it may never finish, which is called starvation. So the number of times a process has been a victim is also weighed when choosing.