Deadlock Detection
Chapter Sixty-Four
Syllabus topic Module 2, "Deadlocks - Deadlock Detection"
Pages 249 to 253 of 452
In one line
Let deadlocks happen, and run an algorithm every so often that looks at the current state and reports which processes, if any, are stuck.
Why a system would choose this
Prevention and avoidance both cost utilisation all the time, whether or not anything ever goes wrong. Detection costs nothing until it is run, and what it costs then is one algorithm and, if it finds something, somebody's work.
That trade is why database engines detect rather than prevent: transactions deadlock often enough to matter and cheaply enough to abort, and no transaction can declare its maximum needs in advance.
Two cases, two algorithms
Which algorithm applies depends on whether every resource type has one instance. A question that gives you instance counts is telling you which method it wants.
| Every type has | Use | Cost |
|---|---|---|
| one instance | the wait for graph: look for a cycle | of the order of n squared |
| several instances | the detection algorithm: like the banker's, with Request instead of Need | of the order of m times n squared |
Case one: the wait for graph
The textbooks hyphenate it, as the wait-for graph, and it is worth recognising in that spelling because that is how a question will print it. Take the resource allocation graph of Chapter fifty eight and collapse the resource vertices out of it. What is left is processes only, with an edge from P to Q meaning P is waiting for a resource that Q holds.
To build it: for every pair of edges P to R and R to Q in the resource allocation graph, draw an edge P to Q, and then remove the resource vertices.
Example. The resource allocation graph has P1 waiting for R1 which P2 holds, P2 waiting for R2 which P3 holds, and P3 waiting for R3 which P1 holds. Collapsed, the wait for graph is:
| From | To | Means |
|---|---|---|
| P1 | P2 | P1 waits for something P2 holds |
| P2 | P3 | P2 waits for something P3 holds |
| P3 | P1 | P3 waits for something P1 holds |
The cycle is P1, P2, P3, P1, found by sim/deadlock.py rather than by eye, and with one instance of every type a cycle in the wait for graph is a deadlock.
A cycle in the WAIT FOR graph is sufficient for deadlock; a cycle in the RESOURCE ALLOCATION graph is not. That is because the wait for graph can only be built at all when every type has one instance, so the ambiguity Chapter fifty eight described cannot arise. Getting those two sentences the right way round is worth marks.
To use this, the system must maintain the wait for graph and search it for a cycle periodically. The search is of the order of n squared in the number of processes.
Deadlock Detection
Case two: the detection algorithm
For several instances, the same shape as Chapter sixty two's safety algorithm with one difference that is the whole point of this chapter.
| Matrix | The banker uses | Detection uses |
|---|---|---|
| Allocation | Allocation | Allocation |
| The demand | Need: what the process might ask for in total | Request: what it is asking for right now |
| Available | Available | Available |
Need is the future and Request is the present, and swapping them is the commonest error in this row. The banker asks whether the processes could all finish if they each asked for everything they are entitled to. Detection asks whether they can finish given only what they are actually waiting for. Detection is therefore optimistic where the banker is pessimistic, which is right: the banker is preventing something, and detection is reporting something that has already happened or has not.
The algorithm:
- Let Work be a copy of Available. For each i, set
Finish[i] = false if Allocation[i] is not all zero, and true otherwise.
- Find an i with Finish[i] false and Request[i] less than or equal to Work. If there is
none, go to 4.
- Work = Work + Allocation[i], Finish[i] = true, and go back to 2.
- If Finish[i] is false for some i, the system is deadlocked, and those processes are
the deadlocked ones.
Step 1's second half is worth understanding rather than memorising: a process holding nothing cannot be part of a deadlock, because nobody can be waiting for anything it has. So it is marked finished at the start and takes no further part.
Worked: no deadlock
Five processes, three types A B C with 7 2 6 instances, Available 0 0 0.
| Process | Allocation | Request |
|---|---|---|
| P0 | 0 1 0 | 0 0 0 |
| P1 | 2 0 0 | 2 0 2 |
| P2 | 3 0 3 | 0 0 0 |
| P3 | 2 1 1 | 1 0 0 |
| P4 | 0 0 2 | 0 0 2 |
Work starts at 0 0 0. Every process holds something, so no Finish starts true.
| Step | Process | Request | Work before | Work after |
|---|---|---|---|---|
| 1 | P0 | 0 0 0 | 0 0 0 | 0 1 0 |
| 2 | P2 | 0 0 0 | 0 1 0 | 3 1 3 |
| 3 | P1 | 2 0 2 | 3 1 3 | 5 1 3 |
| 4 | P3 | 1 0 0 | 5 1 3 | 7 2 4 |
| 5 | P4 | 0 0 2 | 7 2 4 | 7 2 6 |
Every process finishes, so there is no deadlock, and the sequence found is P0, P2, P1, P3, P4.
Notice how it starts. Nothing at all is available, and yet the algorithm gets going, because P0 and P2 are requesting nothing. A process that is not waiting for anything will finish, and what it releases is what frees everybody else. That is the engine of the whole algorithm.
Deadlock Detection
Worked: a deadlock, after one more request
Change one number: P2 now requests one instance of C.
| Process | Allocation | Request |
|---|---|---|
| P0 | 0 1 0 | 0 0 0 |
| P1 | 2 0 0 | 2 0 2 |
| P2 | 3 0 3 | 0 0 1 |
| P3 | 2 1 1 | 1 0 0 |
| P4 | 0 0 2 | 0 0 2 |
| Step | Process | Request | Work before | Work after |
|---|---|---|---|---|
| 1 | P0 | 0 0 0 | 0 0 0 | 0 1 0 |
And it stops. Work is 0 1 0, and every remaining request needs A or C, of which there are none.
Finish is false for P1, P2, P3 and P4, so those four processes are deadlocked. P0 is not: it was requesting nothing and finished.
One instance of one resource type turned a healthy system into a four process deadlock, and nothing else changed. That is worth a sentence in any answer about why deadlock is hard to test for: the state one request before a deadlock looks entirely healthy.
When to run it, which is a real decision
Detection is only half the method. How often to run it is the other half, and a question asks for the trade.
| Run it | Cost | What you get |
|---|---|---|
| On every request that must wait | very high: it is the most expensive thing the kernel does | you know exactly which request closed the cycle, so the victim is obvious |
| Periodically, say once an hour | low | several processes may be in the cycle by then, so choosing a victim is harder |
| When processor utilisation drops below some level, say 40 per cent | low, and self triggering | deadlocked processes do not compute, so a deadlock shows up as an idle machine |
The third is the clever one and it is worth naming: a deadlock makes the machine idle, because the stuck processes are waiting rather than computing. So low utilisation with a long ready queue is itself the signal.
The cost of running it rarely is not only a harder choice of victim. A cycle can grow: once two processes are stuck holding resources, a third that wants one of those resources joins the deadlock, then a fourth. Running detection an hour later may find twenty processes where there were two.
Distinctions that carry marks
| The banker's safety algorithm | The detection algorithm | |
|---|---|---|
| Uses | Need | Request |
| Asks | could they all finish if each asked for its maximum | can they all finish given what they are asking now |
| Run | before granting a request | after the fact, periodically |
| Answer | safe or unsafe | deadlocked or not, and who |
| Processes holding nothing | take part normally | marked finished at the start |
Deadlock Detection
| Resource allocation graph cycle | Wait for graph cycle | |
|---|---|---|
| Vertices | processes and resources | processes only |
| A cycle means | deadlock only if one instance per type | deadlock, and the graph exists only in that case |
| Cost to search | larger graph | of the order of n squared |
What it does not mean
Detection does not prevent anything. The deadlock has already happened when the algorithm finds it.
Request is not Need. Request is what a process is waiting for at this instant; Need is what it might ask for in total. Using Need here would report deadlocks that do not exist.
A process holding nothing is not idle. It may be computing happily. It is excluded because nobody can be waiting for it.
Finding a deadlock is not fixing it. The next chapter is the fixing, and it always costs somebody their work.
Quick revision
- Detection lets deadlocks happen and looks for them. It costs nothing until it runs.
- One instance per type: build the wait for graph by collapsing the resources out, and
look for a cycle. A cycle there is a deadlock. Cost of the order of n squared.
- Several instances: the detection algorithm, which is the safety algorithm with
Request in place of Need. Cost of the order of m times n squared.
- Need is the future, Request is the present. Swapping them is the error this row is full of.
- A process holding nothing is marked finished at the start: nobody can be waiting for it.
- Worked here: a five process state with nothing available is not deadlocked, by P0, P2, P1,
P3, P4; add one request for one instance of C and four of the five are deadlocked.
- When to run it: on every waiting request, which is too expensive; periodically; or when
processor utilisation drops, because deadlocked processes do not compute.
- Running it rarely makes the cycle bigger and the victim harder to choose.
Test yourself
- What are the two detection methods and when is each used? The wait for graph with a cycle
search, when every resource type has one instance; and the detection algorithm, when types have several instances.
- How is a wait for graph built? By removing the resource vertices from the resource
allocation graph: for every P to R and R to Q, draw P to Q.
- Is a cycle in a wait for graph sufficient for deadlock? Yes. The graph can only be built
when every type has one instance, so the ambiguity of the resource allocation graph does not arise. 4. What is the one difference between the detection algorithm and the banker's safety algorithm? It uses Request, what each process is waiting for now, instead of Need, what it might eventually ask for.
Deadlock Detection
- Why is a process holding no resources marked finished at the start? Because no other
process can be waiting for anything it holds, so it cannot be part of a deadlock.
- Give three policies for when to run detection, with a cost of each. On every request that
must wait, which is very expensive; periodically, which lets the cycle grow before it is found; or when processor utilisation falls below a threshold, which is cheap and self triggering because deadlocked processes do not compute.
- Why does running detection rarely make recovery harder? A cycle grows: processes that want
the resources held by the stuck ones join the deadlock, so an hour later there may be twenty processes in it rather than two, and choosing a victim is harder.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.