Lecture 8 about 60 min 32 quiz questions

Deadlock

Why processes freeze forever waiting on each other, the four conditions that make it possible, resource-allocation graphs, and the three ways out: prevent it, avoid it with the Banker's algorithm, or detect and recover.

Start reading Jump to quiz Open the Banker's algorithm lab

What you will be able to do

State the formal definition of deadlock and the four necessary conditions with an example of each.
Read a resource-allocation graph and decide whether a cycle means deadlock or only the possibility of one.
Explain how each of the four conditions can be attacked for deadlock prevention, and the cost of each attack.
Define a safe state and find a safe sequence.
Run the Banker's safety algorithm and resource-request algorithm by hand on the slide example.
Describe detection with wait-for graphs and recovery by termination, preemption, or rollback.

Resources, and a deadlock in the kitchen

Two cooks, one pan, one bottle of oil, and dinner never gets made.

A resource is something a process uses, and it is usually limited. Computer examples: printers, semaphores and locks, tables in a database. Processes need access to resources in a reasonable order. The slides split resources into two types.

Preemptable versus non-preemptable resources

Preemptable

Can be taken away from a process with no ill effects
Example: the CPU (save the registers, give it back later)
Example: a memory page that can be swapped out
Rarely involved in deadlock

Non-preemptable

Taking it away will make the process fail
Example: a printer halfway through a page
Example: a semaphore or lock
The usual ingredient of deadlock

Using a resource: the three-step protocol

1Request the resource.
2Use the resource.
3Release the resource.

If the request is denied, the process has options

Block and wait for the resource.
Continue without it, if possible, perhaps using an alternate resource.
Fail with an error code.
Some of these choices can prevent deadlock. Blocking is the one that lets deadlock happen.

Deadlocks occur when processes are granted exclusive access to devices or software constructs, and each deadlocked process needs a resource held by another deadlocked process. Process 1 holds A and requests B; Process 2 holds B and requests A. Both block, neither can proceed.

1 of 8

Definition and the four necessary conditions

All four must hold at once. Break any one and deadlock is impossible.

Four conditions for deadlock, with an example that satisfies each

Condition	Meaning	Example
Mutual exclusion	Only one process at a time can use the resource	Only one process may print on a printer at a time
Hold and wait	A process holding at least one resource is waiting for additional resources held by others	Process holds R1 and requests R2
No preemption	A resource can be released only voluntarily by the holder, after it finishes its task	A lock cannot be forcibly taken from its owner
Circular wait	A set P0, P1, ..., Pn where P0 waits for P1's resource, P1 for P2's, ..., and Pn waits for P0's	Alice waits for Adam's pan, Adam waits for Alice's oil

2 of 8

Resource-Allocation Graph (RAG)

Draw the processes, draw the resources, look for a cycle.

A resource-allocation graph has a set of vertices V and edges E. V is partitioned into P, the set of all processes, and R, the set of all resource types. A resource type is drawn as a rectangle with one dot per instance.

The two kinds of edge

Edge	Direction	Meaning
Request edge	`Pi -> Rj`, from process to resource	Pi has requested an instance of Rj and is waiting
Assignment edge	`Rj -> Pi`, from a specific instance dot to the process	Pi is holding an instance of Rj

A resource-allocation graph with the cycle P1, R1, P2, R3, P3, R2, P1 highlighted. R2 has two instances but both are held inside the cycle, so nobody can release and the cycle is a deadlock. R4 has free instances and is outside the cycle.

Reading cycles

1
No cycle
No deadlock. Every process can eventually be satisfied.
2
Cycle, single instance per resource type
Deadlock, guaranteed. Nobody in the cycle can get what it needs.
3
Cycle, multiple instances per resource type
Possibility of deadlock. A process outside the cycle holding another instance may finish and release it, breaking the cycle.

3 of 8

Three ways to handle deadlock

Never let it happen, let it happen and clean up, or pretend it never happens.

Methods for handling deadlocks

Strategy	How	Who uses it
Prevention	Ensure the system never enters deadlock by making one of the four necessary conditions impossible	Systems that can afford restrictive rules
Avoidance	Ensure the system never enters deadlock by monitoring resource use and denying requests that would lead to an unsafe state	Systems where processes declare maximum needs in advance
Detection and recovery	Allow deadlock to occur, detect it, then recover	Databases, some transaction systems
Ignore it	Pretend deadlocks never occur; reboot if they do	Most operating systems, including UNIX and Windows

Prevention versus avoidance

Deadlock prevention

Attacks one of the four necessary conditions
Needs no information about future requests
Static rules imposed on all processes
Cost: low resource utilisation, possible starvation

Deadlock avoidance

Ensures the system never enters an unsafe state
Needs a priori information: each process's maximum claim
Dynamic check on every request
Cost: runtime overhead, may deny requests that would in fact have been fine

4 of 8

Deadlock prevention

Disallow one condition. Each choice has a price.

Attacking each condition

1
Disallow mutual exclusion
Not required for sharable resources such as read-only files. But it must hold for non-sharable resources like printers, so this attack does not work in general.
2
Disallow hold and wait
Guarantee that whenever a process requests a resource it holds no others. Either request and be allocated all resources before execution begins, or request resources only when holding none. Cost: low resource utilisation because resources sit idle while reserved, and starvation is possible for a process needing many popular resources.
3
Disallow no preemption
If a process holding resources requests one that cannot be allocated immediately, all its held resources are released. They are added to the list it is waiting for. The process restarts only when it can regain its old resources and the new ones.
4
Disallow circular wait
Impose a total ordering of all resource types and require every process to request resources in increasing order of enumeration. Slide example order: 1 tape drive, 2 disk drive, 3 printer, 4 CPU. A process wanting the printer and the tape drive must ask for the tape drive first.

5 of 8

Deadlock avoidance and safe states

Know each process's maximum claim, then never grant a request that leaves you without a way out.

Avoidance requires a priori information. The simplest and most useful model: each process declares the maximum number of instances of each resource type it may ever need. The avoidance algorithm then dynamically examines the resource-allocation state, defined by available resources, allocated resources, and maximum demands, to ensure a circular wait can never form.

A system is in a safe state if there exists a safe sequence of all processes P1, P2, ..., Pn such that for each Pi, the resources Pi may still request can be satisfied by the currently available resources plus the resources held by all Pj with j < i. If Pi's needs are not immediately available, Pi waits until all earlier Pj finish, gets what it needs, runs, returns everything, and then Pi+1 can proceed.

Safe states are a subset of unsafe-free states; deadlock states sit inside the unsafe region. Avoidance keeps the system inside the safe region.

Basic facts

Safe state implies no deadlock.
Unsafe state implies the possibility of deadlock, not certainty. Processes might release early.
Avoidance means ensuring the system never enters an unsafe state.
The state is safe because the OS can definitely avoid deadlock by blocking new requests until the safe order has executed.

Worked example: 12 tape drives

1
Snapshot
P0 max 10, allocated 5, need 5. P1 max 4, allocated 2, need 2. P2 max 9, allocated 2, need 7. Allocated total 9, so 3 drives available.
2
Who can finish now?
P0 needs 5 > 3, no. P1 needs 2 <= 3, yes. Let P1 run and return its 2. Available becomes 5.
3
Next
P0 needs 5 <= 5, yes. P0 runs and returns all 10. Available becomes 10.
4
Last
P2 needs 7 <= 10, yes. P2 finishes. Available is 12.
5
Conclusion
Safe sequence is P1, P0, P2. The state is safe.

Which algorithm to use depends on the resources. With a single instance of each resource type, use the resource-allocation graph algorithm. With multiple instances, use the Banker's algorithm.

Resource-allocation graph algorithm (single instances)

1
Claim edges
A claim edge Pi -> Rj, drawn dashed, means Pi may request Rj in the future. All resources must be claimed a priori.
2
Request
When Pi actually requests Rj, the claim edge becomes a request edge.
3
Allocation
When Rj is allocated to Pi, the request edge becomes an assignment edge Rj -> Pi.
4
Release
When Pi releases Rj, the assignment edge reverts to a claim edge.
5
The rule
Grant a request only if converting the request edge to an assignment edge does not create a cycle in the graph. A cycle would mean an unsafe state.

6 of 8

The Banker's algorithm

A bank never lends so much that it could not eventually satisfy every customer's maximum. Neither does the OS.

The Banker's algorithm is a resource allocation and deadlock avoidance algorithm. It tests for safety by simulating allocation up to the predetermined maximum of every resource, and makes a safe-state check before deciding whether an allocation may proceed. Let n be the number of processes and m the number of resource types.

Data structures

Structure	Shape	Meaning
Available	Vector of length m	`Available[j] = k`: k instances of Rj are free
Max	n x m matrix	`Max[i][j] = k`: Pi may request at most k instances of Rj
Allocation	n x m matrix	`Allocation[i][j] = k`: Pi currently holds k instances of Rj
Need	n x m matrix	`Need[i][j] = Max[i][j] - Allocation[i][j]`: Pi may still need k more of Rj
Finish	Boolean vector of length n	Whether Pi has been shown able to complete. Safe if all true

Safety algorithm

1
Step 1: initialise
Work = Available. Finish[i] = false for every i.
2
Step 2: find a candidate
Find an i with Finish[i] == false and Need[i] <= Work (every component). If none exists, go to step 4.
3
Step 3: let it finish
Work = Work + Allocation[i], Finish[i] = true. Go back to step 2.
4
Step 4: verdict
If Finish[i] == true for all i, the system is in a safe state. Otherwise it is unsafe.

Resource-request algorithm for process Pi requesting Request[i]

1
Step 1: within claim?
If Request[i] <= Need[i], go to step 2. Otherwise raise an error: the process exceeded its maximum claim.
2
Step 2: available?
If Request[i] <= Available, go to step 3. Otherwise Pi must wait: resources are not available.
3
Step 3: pretend
Available = Available - Request[i], Allocation[i] = Allocation[i] + Request[i], Need[i] = Need[i] - Request[i]. Run the safety algorithm on this pretend state.
4
Decide
If safe, the resources are allocated. If unsafe, Pi must wait and the old state is restored.

Slide example: 5 processes, resources A (10), B (5), C (7). Available = (3, 3, 2). Need = Max minus Allocation.

Process	Allocation A B C	Max A B C	Need A B C
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Safety algorithm on the snapshot, scanning i = 0 to 4 in order

1
Start
Work = (3, 3, 2). All Finish false.
2
P0?
Need (7, 4, 3) > Work. Must wait.
3
P1
Need (1, 2, 2) <= (3, 3, 2). Finish P1. Work = (3, 3, 2) + (2, 0, 0) = (5, 3, 2).
4
P2?
Need (6, 0, 0): 6 > 5. Must wait.
5
P3
Need (0, 1, 1) <= (5, 3, 2). Finish P3. Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3).
6
P4
Need (4, 3, 1) <= (7, 4, 3). Finish P4. Work = (7, 4, 3) + (0, 0, 2) = (7, 4, 5).
7
Second pass, P0
Need (7, 4, 3) <= (7, 4, 5). Finish P0. Work = (7, 4, 5) + (0, 1, 0) = (7, 5, 5).
8
P2
Need (6, 0, 0) <= (7, 5, 5). Finish P2. Work = (10, 5, 7), which is every instance in the system.
9
Verdict
All Finish true. Safe, with safe sequence P1, P3, P4, P0, P2.

Request 1: P1 asks for (1, 0, 2)

1
Within claim?
(1, 0, 2) <= Need[1] = (1, 2, 2). Yes.
2
Available?
(1, 0, 2) <= Available (3, 3, 2). Yes.
3
Pretend
Available becomes (2, 3, 0). P1 Allocation becomes (3, 0, 2). P1 Need becomes (0, 2, 0).
4
Safety check
Work (2, 3, 0). P1 need (0, 2, 0) fits: Work (5, 3, 2). P3 need (0, 1, 1) fits: Work (7, 4, 3). P4 need (4, 3, 1) fits: Work (7, 4, 5). P0 need (7, 4, 3) fits: Work (7, 5, 5). P2 need (6, 0, 0) fits: Work (10, 5, 7).
5
Decision
Sequence P1, P3, P4, P0, P2 still works. Granted.

State after granting P1's request. Available = (2, 3, 0).

Process	Allocation A B C	Need A B C
P0	0 1 0	7 4 3
P1	3 0 2	0 2 0
P2	3 0 2	6 0 0
P3	2 1 1	0 1 1
P4	0 0 2	4 3 1

Request 2: P4 asks for (3, 3, 0)

1
Within claim?
(3, 3, 0) <= Need[4] = (4, 3, 1). Yes.
2
Available?
(3, 3, 0) <= Available (2, 3, 0)? A: 3 > 2. No.
3
Decision
P4 must wait. The resources simply are not there. No safety check needed; the algorithm stops at step 2.

Request 3: P0 asks for (0, 2, 0)

1
Within claim?
(0, 2, 0) <= Need[0] = (7, 4, 3). Yes.
2
Available?
(0, 2, 0) <= Available (2, 3, 0). Yes.
3
Pretend
Available becomes (2, 1, 0). P0 Allocation becomes (0, 3, 0). P0 Need becomes (7, 2, 3).
4
Safety check
Work (2, 1, 0). P0 needs (7, 2, 3): no. P1 needs (0, 2, 0): B 2 > 1, no. P2 needs (6, 0, 0): no. P3 needs (0, 1, 1): C 1 > 0, no. P4 needs (4, 3, 1): no. Nobody can finish.
5
Decision
The pretend state is unsafe. P0 must wait, and the old state is restored. The request was affordable but it would have removed the last unit of B that lets P1 and P3 start the chain.

Open the Banker's algorithm labLoad the slide snapshot or type your own matrices, step the safety algorithm, submit requests, and draw resource-allocation graphs to hunt for cycles.

7 of 8

Deadlock detection and recovery

Let it happen, notice it, then break it.

Under this strategy the system lets deadlocks occur, tries to detect them when they do, and takes action to recover. Detection depends on whether each resource type has one instance or many.

Detection algorithms

Single instance of each resource type

Maintain a wait-for graph: nodes are processes only
Edge Pi -> Pj means Pi is waiting for Pj
Built from the RAG by collapsing each resource node
Periodically search for a cycle; a cycle means deadlock
Cycle detection costs O(n^2) for n vertices

Multiple instances of each resource type

Use a Banker's-style algorithm with current requests instead of maximum needs
Processes that cannot be finished are deadlocked
Costs O(m n^2) for m resource types and n processes

Recovery options

1
Process termination: abort all
Kill every deadlocked process. Guaranteed to break the cycle, and wasteful.
2
Process termination: abort one at a time
Choose a victim in the cycle, kill it, re-run detection, repeat until no deadlock. Restart the process later. Fine for something like compiling; not fine for database record updates that were half done.
3
Resource preemption
Temporarily take a resource from its current owner and give it to another process. A laser printer can be taken away in some cases.
4
Rollback
Processes are checkpointed periodically: their state, including resource allocation, is written to a file. On deadlock, roll a victim back to a checkpoint and restart from there.

8 of 8

Before the exam

The lines worth memorising, and the mistakes that lose marks.

Remember this

1Deadlock: each process in a set waits for an event only another process in the set can cause. None can run, release, or be awakened.
2Preemptable resources (CPU, memory pages) can be taken back safely. Non-preemptable ones (printer, lock) cause failure if taken. Deadlock involves non-preemptable, exclusively held resources.
3Four necessary conditions: mutual exclusion, hold and wait, no preemption, circular wait. All must hold together.
4RAG: request edge Pi -> Rj, assignment edge Rj -> Pi. No cycle means no deadlock. Cycle with single instances means deadlock. Cycle with multiple instances means maybe.
5Handling: prevention, avoidance, detection and recovery, or ignore it (UNIX).
6Prevention breaks a condition: request all upfront or hold nothing when requesting (kills hold and wait), release everything when blocked (kills no preemption), total resource ordering (kills circular wait). Mutual exclusion cannot be dropped for non-sharable resources.
7Avoidance needs each process's maximum claim in advance and keeps the system in a safe state.
8Safe state: a sequence exists where each process's remaining need fits in available plus what earlier processes hold. Safe means no deadlock; unsafe means deadlock is possible.
912 tape drives, P0 5/10, P1 2/4, P2 2/9, available 3: safe sequence P1, P0, P2.
10Banker's: Need = Max minus Allocation. Safety: Work = Available, repeatedly finish any process with Need <= Work and add its Allocation to Work.
11Request: must be <= Need (else error), <= Available (else wait), then pretend-allocate and run safety (unsafe means wait and restore).
12Slide example: Available (3, 3, 2), safe sequence P1, P3, P4, P0, P2. P1 (1, 0, 2) granted. P4 (3, 3, 0) waits, exceeds Available. P0 (0, 2, 0) waits, would be unsafe.
13Single-instance avoidance uses claim edges in the RAG: grant only if no cycle forms.
14Detection: wait-for graph O(n^2) for single instances; Banker's-style O(m n^2) for multiple. Recovery: abort all, abort one at a time, preempt resources, roll back to a checkpoint.

Exam traps

Saying a cycle in the RAG always means deadlock. Only with single-instance resources. With multiple instances it is a possibility.
Calling an unsafe state a deadlocked state. Unsafe means deadlock could happen; processes may still release early and everything finishes.
Choosing the printer as a preemptable resource. Taking a printer mid-job ruins the output, so it is non-preemptable. The CPU is the preemptable example.
Listing priority scheduling among the deadlock conditions. The four are mutual exclusion, hold and wait, no preemption, circular wait.
Confusing a claim edge with an assignment edge. A claim edge is dashed and means 'may request in future'; assignment means 'currently holds'.
Skipping the Request <= Need check. If a process asks beyond its declared maximum, that is an error, not a wait.
Concluding P4's (3, 3, 0) request fails for safety reasons. It fails earlier: A = 3 exceeds Available A = 2.
Using Max instead of Need when comparing against Work in the safety algorithm. Always Need, which is Max minus Allocation.

Quiz yourself

One question at a time with instant feedback. Your best score is saved.

Timed version →

Q 1 / 32 · Resourceseasyscore 0

Which of the following is an example of a preemptable resource?

Not quite

The CPU can be taken from a process at any time with no ill effect: its registers are saved and restored later. A printer or semaphore taken mid-use causes failure.

Finished reading?

Mark this lecture as done

Take the quiz above first so your score is saved here.

Practise itOpen the Banker's algorithm lab