How to use the Deadlock Detection Simulator
- 1. Enter the matricesType the Allocation and Request matrices, one process per line, in the same order.
- 2. Add AvailableEnter the Available vector, or switch to Total instances and the tool works out Available.
- 3. Read the stepsSee each Request ≤ Work check, the Work vector after it, and the final list of deadlocked processes.
How the deadlock detection algorithm works
Deadlock detection is used when a system lets processes ask for resources freely and checks for deadlock from time to time. With several instances of each resource type, it uses three inputs: Allocation (what each process holds now), Request (what each process is waiting for now) and Available (free instances).
- Set Work = Available. Mark Finish[i] = true for any process that holds nothing.
- Find an unfinished process Pi with Request[i] ≤ Work.
- Assume it finishes: Work = Work + Allocation[i], Finish[i] = true. Go back to step 2.
- When no such process is left, every Pi with Finish[i] = false is deadlocked.
The algorithm is optimistic. It assumes a process that gets what it asks for will finish and release everything. It takes about m × n² steps for n processes and m resource types.
Worked example (Silberschatz)
Five processes P0 to P4 share resources A (7 instances), B (2) and C (6). Allocation is P0 = 0 1 0, P1 = 2 0 0, P2 = 3 0 3, P3 = 2 1 1, P4 = 0 0 2. Request is P0 = 0 0 0, P1 = 2 0 2, P2 = 0 0 0, P3 = 1 0 0, P4 = 0 0 2. Available is 0 0 0.
P0 needs nothing, so Work becomes 0 1 0. P1 needs 2 0 2 and waits. P2 needs nothing, so Work becomes 3 1 3. P3 then gives 5 2 4, P4 gives 5 2 6 and P1 gives 7 2 6. Every process finishes, so there is no deadlock. These are the tool's default values.
Now change P2's request to 0 0 1. Only P0 can finish (Work = 0 1 0), and P1, P2, P3 and P4 stay blocked. They are deadlocked.
Detection vs the Banker's algorithm
The two look alike but answer different questions. The Banker's algorithm is avoidance. It uses Need = Max − Allocation and asks whether a future state is safe before granting a request. Detection uses the current Request matrix and asks whether a deadlock exists right now. For avoidance questions with a Max matrix, use the Banker's algorithm calculator. Exam tip: if the question gives a Request matrix and asks "is the system deadlocked?", it is a detection question.
Frequently asked questions
Is the Request matrix the same as Need?
No. Need (Max − Allocation) is used by the Banker's algorithm. Detection uses Request, which is only what each process is waiting for right now.
Why can the order of finishing differ from my textbook?
When more than one process can run, any of them may be picked. The order can change, but the set of deadlocked processes is always the same.
What happens to a process that holds no resources?
It is marked finished at the start, because it cannot be part of a circular wait, even if its own request cannot be met yet.
What does the system do after a deadlock is found?
It recovers by ending one or more deadlocked processes or by taking resources back from them (preemption) and rolling them back.