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 seeHow oftenSection
πŸ”΄ 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 / avoidanceoftenΒ§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.)

Four necessary conditions β€” all must hold at the same time:
  1. Mutual exclusion β€” a resource can be used by only one process at a time.
  2. Hold and wait β€” a process holds some resources and waits for more.
  3. No preemption β€” a resource is only released voluntarily (cannot be taken away).
  4. Circular wait β€” a chain P1β†’P2→…→Pnβ†’P1 each waiting for the next.
βœ— Traps (the exam loves these)
  • "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:

GraphConclusion
No cycleNo deadlock (always)
A cycle, all resources single-instanceDeadlock for sure
A cycle, some resources multi-instanceDeadlock is only possible (not sure)
🎯 In the exam β€” "which edge removal guarantees no deadlock?" (2024-02-07 Ex11, 2024-09-18 Ex12)
With multi-instance resources, a cycle means deadlock is POSSIBLE (so "surely NOT deadlock" and "surely IN deadlock" are both false). An edge removal "surely removes the deadlock" only if it breaks every cycle. So: find all cycles, then test each edge β€” removing a process's only request edge usually breaks all cycles; removing one of two parallel assignment edges usually does not.

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

TableMeaning
Allocationwhat each process holds now
Maxthe most each process may ever need
Need= Max βˆ’ Allocation (what it still might ask for)
Availablefree resources right now
Step 1 β€” handle the request (resource-request algorithm):
  1. If Request > Need β†’ error (asking more than declared).
  2. If Request > Available β†’ must wait (not enough free now).
  3. Otherwise pretend to grant it: Available βˆ’= Request; Allocation += Request; Need βˆ’= Request. Then run the safety check on the new state.
Step 2 β€” safety check (is the state safe?):
  1. Find any unfinished process whose Need ≀ Available.
  2. "Finish" it: add its Allocation back to Available (it returns its resources). Mark it done.
  3. Repeat. If all processes finish β†’ safe (the order = a safe sequence). If you get stuck β†’ unsafe.
If the resulting state is safe β†’ grant the request. If not β†’ deny and restore.
β–Ά Example (like 2025-06-12 Ex12) β€” Available = (4,3,3), request P1 = (1,1,1)
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
βœ— Two different "no" reasons
"Not enough free now" (Request > Available β†’ wait) is different from "resulting state is unsafe" (free resources exist but granting leads to possible deadlock β†’ deny). Say which one applies. And always compute Need = Max βˆ’ Allocation first.

4Prevention, avoidance, detection 🟑

StrategyIdea
Preventionmake 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.
Avoidanceuse advance knowledge (Max) to stay in a safe state β†’ the Banker's algorithm.
Detection + recoverylet 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.