Deadlock β Easy Exam Guide Unit u09. Every exam has one deadlock question β usually the Banker's algorithm OR a resource-graph cycle (~3 pts). Both are mechanical. π΄ = comes a lot.
Written in simple (B1) English. Read it from top to bottom before the exam.
0How "deadlock" comes in the exam
There is one deadlock question in almost every exam. It is one of these, all mechanical:
| The question you will see | How often | Section |
|---|---|---|
| π΄ Banker's algorithm: given the matrices and a request, "can it be granted? give the safe sequence" | about half the exams | Β§3 |
| π΄ Resource graph: "is there a deadlock? which edge to remove?" (true/false) | about half the exams | Β§2 |
| π΄ True/false on the four conditions / prevention / avoidance | often | Β§1 |
1What deadlock is + the four conditions π΄
A deadlock is a set of processes where each one waits for a resource held by another in the same set β so they all wait forever. (Compare: starvation = one process waits forever while others go on. Deadlock implies starvation, but not the other way round.)
- Mutual exclusion β a resource can be used by only one process at a time.
- Hold and wait β a process holds some resources and waits for more.
- No preemption β a resource is only released voluntarily (cannot be taken away).
- Circular wait β a chain P1βP2ββ¦βPnβP1 each waiting for the next.
- "If all four conditions hold, there is certainly a deadlock." FALSE β they are necessary, not sufficient (deadlock is only possible).
- "If even one condition is missing, there is certainly NO deadlock." TRUE β all four are required.
- The conditions are "ME, hold-and-wait, no-preemption, circular wait" β watch wordings that drop the "no" or the "circular".
- "Starvation is a necessary condition." FALSE.
2Resource-allocation graph & the cycle rule π΄
Draw processes and resources as a graph. A request edge goes process β resource; an assignment edge goes resource β process. A resource type can have several instances (dots in the box). The key rule for the exam:
| Graph | Conclusion |
|---|---|
| No cycle | No deadlock (always) |
| A cycle, all resources single-instance | Deadlock for sure |
| A cycle, some resources multi-instance | Deadlock is only possible (not sure) |
3The Banker's algorithm π΄ the ~3-point task
This is deadlock avoidance: before granting a request, check that the system stays in a safe state (a state where all processes can still finish in some order = a safe sequence).
The four tables
| Table | Meaning |
|---|---|
| Allocation | what each process holds now |
| Max | the most each process may ever need |
| Need | = Max β Allocation (what it still might ask for) |
| Available | free resources right now |
- If Request > Need β error (asking more than declared).
- If Request > Available β must wait (not enough free now).
- Otherwise pretend to grant it: Available β= Request; Allocation += Request; Need β= Request. Then run the safety check on the new state.
- Find any unfinished process whose Need β€ Available.
- "Finish" it: add its Allocation back to Available (it returns its resources). Mark it done.
- Repeat. If all processes finish β safe (the order = a safe sequence). If you get stuck β unsafe.
Need = Max β Allocation: P1=(1,5,3) P2=(4,4,1) P3=(3,3,2) P4=(3,1,2) P5=(4,3,5) Grant P1's request: P1 Allocβ(2,1,2), Availableβ(3,2,2), Need(P1)β(0,4,2) Safety check with Available=(3,2,2): P4 Need(3,1,2) β€ (3,2,2) β finish β Available=(3,3,2) P3 Need(3,3,2) β€ (3,3,2) β finish β Available=(3,4,2) P1 Need(0,4,2) β€ (3,4,2) β finish β Available=(5,5,4) P2 Need(4,4,1) β€ (5,5,4) β finish β Available=(5,5,5) P5 Need(4,3,5) β€ (5,5,5) β finish All finish β SAFE β answer: YES, safe sequence P4 P3 P1 P2 P5
4Prevention, avoidance, detection π‘
| Strategy | Idea |
|---|---|
| Prevention | make one of the four conditions impossible. E.g. break circular wait by giving resources a fixed order and always requesting in increasing order; break hold-and-wait by requesting all resources up front. |
| Avoidance | use advance knowledge (Max) to stay in a safe state β the Banker's algorithm. |
| Detection + recovery | let deadlock happen, find the cycle, then recover (kill a process or preempt a resource). |
| Ignore (ostrich) | assume it is rare β what Windows/Unix usually do. |
5One-page trap sheet
- Four conditions: mutual exclusion, hold-and-wait, NO-preemption, circular wait. Necessary, not sufficient.
- All four hold β deadlock POSSIBLE (not sure). One missing β surely NO deadlock.
- Graph: no cycle β no deadlock. Cycle + single instances β deadlock sure. Cycle + multi instances β only possible.
- To "surely remove" a deadlock, an edge removal must break every cycle.
- Banker's: Need = Max β Allocation. Grant only if Request β€ Need, Request β€ Available, AND the new state is safe.
- Safety check: repeatedly find a process with Need β€ Available, finish it (add its Allocation back), until all finish (safe) or stuck (unsafe).
- Two deny reasons: not enough Available now vs resulting state unsafe.
- Prevention breaks a condition (e.g. ordered requests); avoidance = Banker's; detection+recovery; ignore = ostrich.