OS Concepts — Chapter 7 Deadlocks

CHAPTER 7

DEADLOCKS
Detailed Study Notes
Operating System Concepts — Silberschatz, Galvin, Gagne

What this chapter covers

A complete walkthrough of deadlocks in operating systems: how they arise, the conditions required
for them, how to model them graphically, and the three families of strategies used to deal with
them — prevention, avoidance, and detection/recovery.
Includes the System Model, Deadlock Characterization, Resource-Allocation Graphs, Deadlock
Prevention (all 4 conditions), Deadlock Avoidance (Safe State, RAG algorithm, Banker's Algorithm
with full worked example), Deadlock Detection (single instance and multiple instance algorithms),
Recovery (termination and preemption), plus all solved practice exercise concepts and a quick-
revision summary at the end.

Page 1 of 29
OS Concepts — Chapter 7 Deadlocks

Table of Contents
TOC \h \o "1-3"

Page 2 of 29
OS Concepts — Chapter 7 Deadlocks

1. Introduction to Deadlocks
In a multiprogramming environment, many processes run together and compete for a limited number of
resources (CPU, memory, files, printers, locks, etc.). A process that needs a resource must request it; if
the resource is unavailable, the process is forced to wait. Sometimes a process is left waiting forever
because the very resources it needs are being held by other processes that are themselves stuck waiting.
This permanent stuck condition is called a deadlock.

Classic analogy — the Kansas traffic law

An early-20th-century Kansas law stated: “When two trains approach each other at a crossing, both
shall come to a full stop and neither shall start up again until the other has gone.” If both trains
obey this rule literally and neither moves first, neither train ever proceeds — a perfect illustration of
deadlock.

Key facts to remember about how operating systems treat deadlocks:

• Most real operating systems (Linux, Windows) do not provide built-in deadlock prevention. It is
the application/programmer's job to write deadlock-free code.
• Deadlock problems are becoming more common because of: larger numbers of processes,
multithreaded programs, more system resources, and a shift from batch systems toward long-
lived file/database servers.
• This chapter has two core objectives: (1) describe what deadlocks are and how they prevent
processes from completing, and (2) present methods to prevent, avoid, detect, and recover from
deadlocks.

2. System Model (Section 7.1)

A system has a finite set of resources distributed among competing processes. Resources are grouped
into resource types (or classes), and each type may have one or more identical instances.

• Resource type: a category of resource, e.g., CPU, printer, file, semaphore, mutex lock.
• Resource instance: one physical/logical unit of that type. Example: if a system has 2 CPUs, the
resource type “CPU” has 2 instances; 5 printers means resource type “printer” has 5 instances.
If a process requests an instance of a resource type, any instance of that type must be able to satisfy the
request — otherwise the resource type classes are not defined properly. Example: two printers on
different floors (9th floor vs basement) may need to be treated as separate resource classes if users care
which one they get, even though both are “printers.”

Locks as resources
Mutex locks and semaphores (Chapter 5 synchronization tools) are also system resources and a very
common source of deadlock. Since each lock typically protects one specific data structure (a queue,
a linked list, etc.), each lock is usually given its own resource class — so resource-type definition is
not an issue for locks.

Page 3 of 29
OS Concepts — Chapter 7 Deadlocks

2.1 The Request – Use – Release Cycle

Under normal operation, every process uses a resource in exactly this three-step sequence:

1. Request: the process asks for the resource. If it cannot be granted immediately (already in use),
the requesting process must wait.
2. Use: the process operates on the resource (e.g., prints on the printer).
3. Release: the process gives the resource back.
These steps map to actual system calls / library calls:

Resource Type Request Call Release Call

Generic device request() release()

File open() close()

Memory allocate() free()

Semaphore wait() signal()

Mutex lock acquire() release()

The operating system maintains a system table that records, for every resource, whether it is free or
allocated, and to which process. If a process requests a resource already allocated elsewhere, it is added
to a queue of processes waiting for that resource.

Definition — Deadlocked State

A set of processes is in a deadlocked state when every process in the set is waiting for an event
that can be caused only by another process in the same set.
The relevant events here are almost always resource acquisition and release. Resources can be
physical (printers, tape drives, memory, CPU cycles) or logical (semaphores, mutex locks, files).
Other event types — e.g., IPC (inter-process communication) — can also lead to deadlock.

2.2 Two Illustrative Examples

Example A — Same resource type
System has three CD-RW drives. Three processes each hold one drive. If each process now requests
another drive (which doesn't exist free), all three processes wait forever for “CD RW released,” an event
only one of the other waiting processes could cause. This shows deadlock can occur even with a single
resource type, as long as there are multiple instances and multiple competing holders.

Example B — Different resource types

System has one printer and one DVD drive. Process Pi holds the DVD drive and requests the printer;
process Pj holds the printer and requests the DVD drive. Neither can proceed — deadlock involving two
different resource types.

Page 4 of 29
OS Concepts — Chapter 7 Deadlocks

Developers of multithreaded code must be careful: locking tools (mutexes, semaphores from Chapter 5)
prevent race conditions but, if locks are acquired/released carelessly, they can themselves cause
deadlock — as in the dining-philosophers problem.

3. Deadlock Characterization (Section 7.2)

In a deadlock, processes never finish, and the resources they hold remain tied up forever, blocking other
jobs that need those same resources. Before discussing how to handle deadlocks, we study the precise
features that characterize them.

3.1 Worked Example — Deadlock with Pthread Mutex Locks

This worked example from the textbook shows deadlock arising purely from lock-acquisition order in a
multithreaded program.

pthread_mutex_init() initializes an unlocked mutex. pthread_mutex_lock() and pthread_mutex_unlock()

acquire and release a mutex respectively. If a thread calls pthread_mutex_lock() on an already-locked
mutex, that call blocks until the lock's current owner calls pthread_mutex_unlock().

/* Create and initialize the mutex locks */

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

Two threads are created: thread_one runs do_work_one(), thread_two runs do_work_two().

/* thread_one runs in this function */

void *do_work_one(void *param)
{
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/* Do some work */
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
pthread_exit(0);
}

/* thread_two runs in this function */

void *do_work_two(void *param)
{
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);
/* Do some work */

Page 5 of 29
OS Concepts — Chapter 7 Deadlocks

pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);
pthread_exit(0);
}

thread_one acquires locks in order (first_mutex, second_mutex); thread_two acquires them in the
reverse order (second_mutex, first_mutex). If thread_one grabs first_mutex while, at almost the same
moment, thread_two grabs second_mutex — both threads now wait forever for the lock the other is
holding. Deadlock.

Important nuance: deadlock here is only POSSIBLE, not certain

If thread_one manages to acquire and release both locks before thread_two even starts trying,
there is no deadlock at all. Whether deadlock actually happens depends entirely on the order in
which the CPU scheduler runs the two threads.
This illustrates a core difficulty of deadlocks in practice: they may occur only under rare, specific
scheduling timings, making them very hard to reliably reproduce, identify, and test for.

3.2 The Four Necessary Conditions (Section 7.2.1)

A deadlock can arise only if all four of the following conditions hold simultaneously. This is one of the
most important facts in the entire chapter — memorize it precisely.

4. Mutual exclusion. At least one resource must be held in a non-sharable mode — only one process
can use it at a time. If another process requests it, that requester must wait until it is released.
5. Hold and wait. A process must be holding at least one resource while simultaneously waiting to
acquire additional resources that are currently held by other processes.
6. No preemption. Resources cannot be forcibly taken away. A resource can only be released
voluntarily by the process holding it, after that process has finished using it.
7. Circular wait. There must exist a set of waiting processes {P0, P1, ..., Pn} such that P0 is waiting for
a resource held by P1, P1 is waiting for a resource held by P2, …, P(n−1) is waiting for a resource
held by Pn, and Pn is waiting for a resource held by P0 — a cycle of waiting.

Subtlety: the conditions are not fully independent

All four conditions must hold together for deadlock to occur. However, the circular-wait condition
actually implies the hold-and-wait condition (if there's a circular wait, each process in the cycle is,
by definition, holding a resource and waiting for another). So the four conditions are not completely
independent of one another — but it is still useful, and standard, to treat each condition separately
when designing prevention strategies (Section 7.4 attacks each condition individually).

4. Resource-Allocation Graph (Section 7.2.2)

Deadlocks can be described precisely using a directed graph called the system resource-allocation graph
(RAG).

Page 6 of 29
OS Concepts — Chapter 7 Deadlocks

4.1 Definitions and Notation

• Vertices V are split into two sets:
– P = {P1, P2, ..., Pn} — all active processes in the system (drawn as circles).
– R = {R1, R2, ..., Rm} — all resource types in the system (drawn as rectangles; each
instance of a multi-instance resource is a dot inside the rectangle).
• Request edge Pi → Rj: process Pi has requested an instance of resource type Rj and is currently
waiting for it.
• Assignment edge Rj → Pi: an instance of Rj has been allocated to Pi. An assignment edge must
point from a specific dot (instance) inside the rectangle to the process circle, whereas a request
edge points only at the rectangle as a whole.
• When Pi requests an instance of Rj, a request edge is added. When that request is granted, the
request edge instantaneously becomes an assignment edge. When the process is done and
releases the resource, the assignment edge is deleted.

4.2 Worked Example — Figure 7.1

Sets and edges:

• P = {P1, P2, P3} R = {R1, R2, R3, R4}

• E = {P1→R1, P2→R3, R1→P2, R2→P2, R2→P1, R3→P3}
Resource instance counts: R1 has 1 instance, R2 has 2 instances, R3 has 1 instance, R4 has 3 instances
(R4 is unused in this snapshot).

Resulting process states described by the graph:

• P1 holds one instance of R2 and is waiting for an instance of R1.

• P2 holds one instance of R1 and one instance of R2, and is waiting for an instance of R3.
• P3 holds one instance of R3.
This particular graph contains no cycle, so the system is NOT deadlocked.

4.3 Cycles and What They Mean

THE CENTRAL RULE OF RESOURCE-ALLOCATION GRAPHS

If the graph has NO cycle → the system is definitely NOT deadlocked.
If the graph HAS a cycle → a deadlock MAY exist (not guaranteed).
Two special cases sharpen this rule:
• If every resource type involved has exactly ONE instance — a cycle is BOTH a necessary AND
sufficient condition for deadlock (cycle ⇒ deadlock, guaranteed).
• If some resource types have SEVERAL instances — a cycle is a necessary but NOT sufficient
condition (cycle does not guarantee deadlock).

Page 7 of 29
OS Concepts — Chapter 7 Deadlocks

Continuing the example — Figure 7.2 (cycle WITH deadlock)

Suppose P3 now also requests an instance of R2. Since none is free, a request edge P3→R2 is added.
Now two minimal cycles exist:

• P1 → R1 → P2 → R3 → P3 → R2 → P1
• P2 → R3 → P3 → R2 → P2
Here, P1, P2, and P3 are genuinely deadlocked: P2 waits on R3 (held by P3); P3 waits on R2 (held by P1
or P2); P1 waits on R1 (held by P2). Nobody can proceed.

Figure 7.3 — cycle WITHOUT deadlock

Cycle present: P1 → R1 → P3 → R2 → P1. But there is no deadlock here, because process P4 (also
holding an instance of R2, a multi-instance resource) can voluntarily release its instance of R2. That
freed instance can then be given to P3, which breaks the cycle and lets everyone proceed. This
demonstrates exactly why a cycle is not sufficient for deadlock when resources have multiple instances.

Summary takeaway
No cycle in the RAG ⇒ system is not in a deadlocked state, guaranteed. A cycle merely signals that
deadlock is possible — you must check whether other available instances of the involved resources
can break the cycle.

5. Methods for Handling Deadlocks (Section 7.3)

There are exactly three general strategies for dealing with the deadlock problem:

8. Prevention or avoidance: use a protocol that guarantees the system will NEVER enter a
deadlocked state in the first place.
9. Detection and recovery: allow deadlocks to happen, but detect them when they occur, then
recover.
10. Ignore the problem entirely: pretend deadlocks never occur (the “ostrich algorithm” approach).

Real-world fact you must know

Option 3 — ignoring the problem — is what most real operating systems actually use, including
Linux and Windows. It then becomes the responsibility of the application developer to write
deadlock-free programs.

Some researchers argue that no single approach is suitable for the entire range of resource-allocation
problems an OS faces. In practice, the basic approaches can be combined, choosing the best technique
for each class of resource in the system.

5.1 Why Prevention/Avoidance Are Grouped Together

• Deadlock prevention: provides methods to guarantee that at least one of the four necessary
conditions (Section 7.2.1) can never hold. These work by constraining HOW resource requests can
be made.

Page 8 of 29
OS Concepts — Chapter 7 Deadlocks

• Deadlock avoidance: requires the OS to have extra advance information about which resources
each process will need and use over its lifetime. With this knowledge, the OS decides, for each
individual request, whether granting it would be safe — considering currently available resources,
resources already allocated to each process, and each process's future requests/releases.

5.2 Detection and Recovery

If the system uses neither prevention nor avoidance, a deadlock may genuinely occur. In that case the
system needs: (a) an algorithm that examines system state to determine whether a deadlock has
actually happened, and (b) an algorithm to recover from it once detected.

5.3 Ignoring the Problem — Why It's Actually Common

Without detection/recovery algorithms, an undetected deadlock will silently degrade system
performance: resources stay locked up by stuck processes, and more and more new processes get stuck
too as they request those same tied-up resources. Eventually the entire system stops functioning and
must be restarted manually.

Despite sounding reckless, this approach is used by most operating systems for practical economic
reasons:

• Expense: ignoring deadlocks is cheaper than implementing prevention, avoidance, or detection

mechanisms.
• Deadlocks are often rare in practice (e.g., roughly once per year in some systems), so the overhead
of the other techniques may not be worth paying.
• Recovery methods built for other kinds of system failures can often double as deadlock recovery
methods. For example, a real-time process running at highest priority on a non-preemptive
scheduler that never returns control can freeze the system without being a true deadlock — the
same manual-recovery technique used for that situation can be reused for actual deadlocks.

6. Deadlock Prevention (Section 7.4)

Since all four necessary conditions must hold simultaneously for deadlock to occur, we can PREVENT
deadlock entirely by ensuring at least one condition can never hold. The chapter examines each of the
four conditions in turn.

6.1 Attacking Mutual Exclusion (7.4.1)

Sharable resources never require mutually exclusive access, and therefore can never be part of a
deadlock. A read-only file is the standard example — many processes can open and read it
simultaneously without ever needing to wait.

Why this approach generally fails

We generally CANNOT prevent deadlocks by denying mutual exclusion, because some resources are
intrinsically non-sharable by nature. A mutex lock, for instance, cannot simultaneously be shared by
several processes — that would defeat its entire purpose.

Page 9 of 29
OS Concepts — Chapter 7 Deadlocks

6.2 Attacking Hold and Wait (7.4.2)

To guarantee the hold-and-wait condition never occurs, we must ensure that whenever a process
requests a resource, it is not already holding any other resource. Two protocols achieve this:

• Protocol 1 — Request everything up front: each process must request and be allocated ALL the
resources it will ever need before it begins executing. This can be implemented by requiring all
resource-request system calls to precede every other system call.
• Protocol 2 — Request only when holding nothing: a process may request resources only when it
currently holds none. It can request some resources, use them, but before requesting ANY
additional resource it must first release everything it currently holds.

Illustrative example — DVD, disk, printer

Consider a process that copies data from a DVD drive to a disk file, sorts the file, then prints the result
on a printer.

• Under Protocol 1: the process must request the DVD drive, the disk file, AND the printer all at
once at the start. It will then hold the printer for its entire run, even though it is only actually
needed right at the end — wasteful.
• Under Protocol 2: the process first requests only the DVD drive and disk file, copies the data, then
releases both. It then requests the disk file and printer, copies to the printer, and releases both
before terminating.

Two main disadvantages of both hold-and-wait protocols

1. Low resource utilization. Resources may sit allocated-but-unused for long stretches. In the
example, we can only safely release the DVD drive and disk file (and re-request the disk file + printer
afterward) if we are certain our intermediate data will safely persist on disk — otherwise we are
forced back to requesting everything up front.
2. Starvation is possible. A process that needs several popular/heavily-contended resources may
end up waiting indefinitely, because at least one of its needed resources is perpetually allocated to
some other process.

6.3 Attacking No Preemption (7.4.3)

To remove the no-preemption condition, one of these protocols can be used:

11. Implicit-release protocol: if a process holding some resources requests another resource that
cannot be granted immediately, then ALL resources currently held by that process are preempted
(implicitly released). These preempted resources get added to the list of resources the process is
now waiting for. The process restarts only once it can regain both its old resources and the newly
requested ones.
12. Steal-from-a-waiter protocol: when a process requests resources, first check availability. If
available, allocate them. If not, check whether the desired resources are held by some OTHER
process that is itself currently waiting for additional resources. If so, preempt the desired
resources from that waiting process and give them to the requester. If the resources are neither
free nor held by a waiting process, the requester must wait — and while waiting, some of ITS
resources may, in turn, get preempted if another process requests them. A process resumes only

Page 10 of 29
OS Concepts — Chapter 7 Deadlocks

once it regains the new resources requested plus any of its own resources that were preempted
while it waited.

Limitation — what this protocol can and cannot be applied to

This preemption-based approach works well for resources whose state can be easily saved and later
restored, such as CPU registers and memory space (you can checkpoint and restore these). It
generally CANNOT be applied to resources like mutex locks and semaphores, since their internal
“state” (a critical section in progress) typically cannot be meaningfully saved and resumed
elsewhere.

6.4 Attacking Circular Wait (7.4.4) — The Most Practical Technique

This is the most widely-used and practically important deadlock-prevention method. The idea: impose a
total ordering on all resource types, and require every process to request resources only in strictly
increasing order of this enumeration.

Formally: let R = {R1, R2, ..., Rm} be the set of resource types. Define a one-to-one function F: R → N (the
natural numbers) that assigns each resource type a unique number, letting us compare any two
resources and determine an order between them. Example assignment:

Resource Type F( )

Tape drive 1

Disk drive 5

Printer 12

Protocol rule: a process can initially request any number of instances of some resource type Ri. After
that, it may request instances of resource type Rj if and only if F(Rj) > F(Ri). So, using the table above, a
process wanting both the tape drive and printer must request the tape drive first, then the printer (since
F(tape drive)=1 < F(printer)=12).

Alternative equivalent formulation: a process requesting an instance of Rj must first have released any
resource Ri such that F(Ri) ≥ F(Rj). Also note: if several instances of the SAME resource type are needed,
they must all be requested in a single combined request.

Proof that this scheme eliminates circular wait

Proof by contradiction. Suppose a circular wait exists among processes {P0, P1, ..., Pn}, where Pi is
waiting for a resource Ri held by process P(i+1) (indices taken modulo n, so Pn waits for Rn held by P0).
Since P(i+1) is holding Ri while requesting R(i+1), the protocol requires F(Ri) < F(R(i+1)) for every i.
Chaining this around the whole cycle gives:

F(R0) < F(R1) < F(R2) < ... < F(Rn) < F(R0)

By transitivity this implies F(R0) < F(R0), which is impossible. Therefore no circular wait can exist under
this protocol. ∎

Page 11 of 29
OS Concepts — Chapter 7 Deadlocks

Applying this to the Pthread mutex example

If we define F(first_mutex) = 1 and F(second_mutex) = 5 for the earlier Pthread example, then
thread_two would be FORBIDDEN from requesting the locks out of order (second_mutex before
first_mutex) — eliminating the deadlock possibility entirely, provided the ordering is actually followed
by every thread.

Important caveat — ordering alone doesn't enforce itself

Developing a resource ordering/hierarchy does NOT, by itself, prevent deadlock. It is entirely up to
application developers to actually write programs that follow that ordering faithfully. The function F
should be defined according to the natural/typical order resources are actually used in the system
— e.g., because a tape drive is usually needed before a printer in real workflows, it is sensible to
define F(tape drive) < F(printer).

The witness lock-order verifier

Certain tools can verify, at runtime, that locks are actually being acquired in proper order and warn
when they are not. One such tool is witness, which works on BSD UNIX variants such as FreeBSD.

• witness dynamically tracks the relationship between lock-acquisition orders observed across the
system.
• Example: if thread_one is first to acquire locks, doing so in order (1) first_mutex, (2)
second_mutex — witness records that first_mutex must always precede second_mutex.
• If thread_two later attempts to acquire the same locks in the opposite order, witness generates a
warning message on the system console, flagging the potential deadlock.

Caveat — lock ordering can still fail with dynamically acquired locks
Imposing a lock ordering does NOT guarantee deadlock prevention if locks are acquired dynamically (i.e.,
which lock object you need is only known at runtime). Classic example — a bank-transfer function
between two arbitrary accounts:

void transaction(Account from, Account to, double amount)

{
mutex lock1, lock2;
lock1 = get_lock(from);
lock2 = get_lock(to);

acquire(lock1);
acquire(lock2);
withdraw(from, amount);
deposit(to, amount);
release(lock2);
release(lock1);
}

Page 12 of 29
OS Concepts — Chapter 7 Deadlocks

Even though this function always acquires “from’s lock” before “to’s lock” in source-code order,
deadlock is still possible if two threads invoke transaction() with the SAME two accounts in transposed
(reversed) order, e.g.:

• transaction(checking_account, savings_account, 25);

• transaction(savings_account, checking_account, 50);
Here, the first call's lock1 is the second call's lock2 and vice versa — a classic circular-wait setup, because
the “order” is determined by argument order, not by any fixed global resource ordering. (The textbook
leaves the actual fix as an exercise — typically solved by always acquiring locks in a consistent order
based on, e.g., the accounts' fixed IDs or memory addresses, regardless of argument order.)

7. Deadlock Avoidance (Section 7.5)

Deadlock-prevention algorithms (Section 7.4) work by limiting HOW requests are made, guaranteeing at
least one necessary condition can never occur. A side effect is often low device utilization and reduced
throughput, since requests get restricted even when granting them would actually have been safe.

Deadlock avoidance takes a different approach: it requires additional advance information about how
each process will request resources. Example: in a system with one tape drive and one printer, the
system might know in advance that process P will request the tape drive first, then the printer, before
releasing both; while process Q will request the printer first, then the tape drive. With full knowledge of
each process's complete future sequence of requests and releases, the system can decide, for every
individual request, whether the requesting process should be made to wait in order to avoid a possible
FUTURE deadlock.

Algorithms in this family differ in how much and what type of advance information they require. The
simplest and most practically useful model requires only that each process declare the maximum
number of resource instances of each type it might ever need.

7.1 Safe State (Section 7.5.1)

Definition
A state is safe if the system can allocate resources to every process (up to each one's declared
maximum) in SOME order, and still avoid deadlock for all of them.
More formally: a system is in a safe state only if a safe sequence exists.

A sequence of processes <P1, P2, ..., Pn> is a safe sequence for the current allocation state if, for every
Pi, the resource requests Pi could still possibly make can be satisfied using the currently available
resources PLUS the resources currently held by all Pj where j < i. If Pi's needs aren't immediately
available, Pi can simply wait until all those earlier Pj processes finish and release their resources; once
they finish, Pi can obtain everything it needs, complete, and release its own resources — letting P(i+1)
proceed the same way, and so on down the line.

If no such sequence exists at all, the state is called unsafe.

Page 13 of 29
OS Concepts — Chapter 7 Deadlocks

Concept Relationship

Safe state Never a deadlocked state.

Deadlocked state Always an unsafe state (the converse direction).

Unsafe state NOT always a deadlock — may or may not lead to one, depending on
what the processes actually do next.

Key insight about unsafe states

As long as the system stays in a safe state, the OS can always avoid both unsafe states AND
deadlocked states. But once the system enters an unsafe state, the OS CANNOT prevent processes
from making requests in a way that eventually causes an actual deadlock — from that point on, it is
entirely the BEHAVIOR of the processes themselves that determines whether deadlock actually
occurs.

Worked example — 12 tape drives, 3 processes

System has 12 magnetic tape drives and three processes P0, P1, P2 with these maximum needs: P0
needs up to 10, P1 needs up to 4, P2 needs up to 9. At time t0, current allocations are P0 holds 5, P1
holds 2, P2 holds 2 (so 12 − 5 − 2 − 2 = 3 tape drives are currently free).

Process Maximum Needs Current Needs (allocated)

P0 10 5

P1 4 2

P2 9 2

At t0 this is a SAFE state, because the sequence <P1, P0, P2> works:

• P1 needs at most 2 more (4 max − 2 held); 3 are free — grant them. P1 finishes and returns all 4,
leaving 5 free.
• P0 needs at most 5 more (10 max − 5 held); 5 are free — grant them. P0 finishes and returns all
10, leaving 10 free.
• P2 needs at most 7 more (9 max − 2 held); 10 are free — grant them. P2 finishes and returns all 9,
leaving all 12 free again.

How a safe state can slide into an unsafe state

Suppose at time t1, process P2 requests and IS GRANTED one more tape drive (now holding 3, free pool
drops from 3 to 2). The system is now UNSAFE. Reasoning: only P1 can still be fully satisfied (it needs 2
more, and 2 are free). After P1 finishes and returns its 4, the system has only 4 available. P0 (holding 5,
max 10) might next request up to 5 more — unavailable, so P0 waits. P2 (holding 3, max 9) might
request up to 6 more — also unavailable, so P2 waits too. Now we have an actual deadlock: P0 waits on
P2's resources (indirectly via availability) and P2 waits on P0's, with nobody able to finish.

Page 14 of 29
OS Concepts — Chapter 7 Deadlocks

The lesson
The mistake was granting P2's request for that ONE additional tape drive without first checking
whether doing so would still leave the system in a safe state. If the system had instead made P2
WAIT until either P0 or P1 finished and released its resources, the deadlock would have been
completely avoided. This is exactly the discipline a deadlock-avoidance algorithm enforces
automatically: it grants a request only if doing so leaves the system in a safe state; otherwise the
requester waits, even if the resource is technically available right now.

Consequence: in this scheme, even if a process requests a resource that IS currently available, it may still
be forced to wait (because granting it now would create an unsafe state). This means resource
utilization can be lower than it otherwise would be — the same fundamental trade-off seen with
deadlock prevention, just applied more surgically.

7.2 Resource-Allocation-Graph Algorithm (Section 7.5.2)

This avoidance algorithm applies ONLY when every resource type has exactly ONE instance. It extends
the resource-allocation graph from Section 7.2.2 with a new edge type.

Claim edge — new edge type

A claim edge Pi → Rj indicates that process Pi MAY request resource Rj at some point in the future.
It points the same direction as a request edge, but is drawn as a dashed line to distinguish it.
When Pi actually requests Rj, the claim edge Pi→Rj is converted into a real request edge. When Pi
later releases Rj, the assignment edge Rj→Pi is converted BACK into a claim edge Pi→Rj (since Pi
might request it again later).

All of a process's claim edges must, in principle, be added to the graph before that process even starts
executing (resources must be “claimed a priori”). This requirement can be relaxed somewhat: a claim
edge Pi→Rj may be added to the graph at any time, as long as ALL of the edges currently associated with
Pi are themselves still claim edges (i.e., Pi hasn't actually started making real requests yet).

The granting rule

When process Pi requests resource Rj, the request can be granted ONLY IF converting the request edge
Pi→Rj into an assignment edge Rj→Pi would NOT create a cycle anywhere in the resource-allocation
graph. This is checked using a cycle-detection algorithm, which takes on the order of n² operations,
where n is the number of processes.

• No cycle would result → granting the resource leaves the system in a safe state → grant it.
• A cycle WOULD result → granting would put the system in an unsafe state → Pi must wait.

Worked example — Figures 7.7 and 7.8

Suppose P2 requests R2. Even though R2 happens to be currently free, the request CANNOT be granted,
because doing so would create a cycle in the graph (shown in Figure 7.8) — putting the system into an
unsafe state. The textbook notes: if P1 then requests R2, AND P2 requests R1, an actual deadlock would
occur — exactly the scenario this algorithm is designed to prevent by refusing the earlier request.

Page 15 of 29
OS Concepts — Chapter 7 Deadlocks

7.3 Banker's Algorithm (Section 7.5.3)

The resource-allocation-graph algorithm only works for systems where every resource type has a single
instance. The banker's algorithm generalizes deadlock avoidance to systems with MULTIPLE instances of
each resource type — though it is less efficient than the graph-based approach. It earns its name from
analogy to a bank that must never commit its available cash in a way that leaves it unable to satisfy the
needs of all its customers.

Operating rule: when a NEW process enters the system, it must declare the maximum number of
instances of each resource type it could ever need (this number cannot exceed the system total). When
any process requests a set of resources, the system must determine whether granting that allocation
would leave the system in a safe state. If yes — grant immediately. If no — the process must wait until
enough other resources are released.

Required data structures

Let n = number of processes in the system, and m = number of resource types.

Structure Type Meaning

Available Vector, length m Available[j] = k means k instances of resource type Rj are

currently available.

Max n × m matrix Max[i][j] = k means process Pi may request at most k

instances of resource type Rj over its lifetime.

Allocation n × m matrix Allocation[i][j] = k means process Pi currently holds k

instances of resource type Rj.

Need n × m matrix Need[i][j] = k means process Pi may still need k more

instances of Rj to finish. Need[i][j] = Max[i][j] − Allocation[i][j].

Notation used throughout: for vectors X and Y of length n, X ≤ Y means X[i] ≤ Y[i] for every i. (Example: if
X = (1,7,3,2) and Y = (0,3,2,1), then Y ≤ X.) And Y < X means Y ≤ X and Y ≠ X. We also treat each row of
Allocation and Need as a vector, written Allocationi and Needi: Allocationi is the resources currently
allocated to Pi, and Needi is the additional resources Pi may still request.

7.3.1 The Safety Algorithm

This algorithm determines whether the CURRENT state of the system is safe.

13. Initialize: Let Work (length m) and Finish (length n) be working vectors. Set Work = Available, and
Finish[i] = false for every i = 0, 1, …, n−1.
14. Find a candidate process: find an index i such that BOTH (a) Finish[i] == false AND (b) Needi ≤
Work. If no such i exists, go to step 4.
15. Simulate completion: Work = Work + Allocationi; Finish[i] = true; then go back to step 2.
16. Check result: if Finish[i] == true for ALL i, the system is in a safe state.
Computational cost: this safety algorithm requires on the order of m × n² operations to determine
whether a given state is safe (Practice Exercise 7.5 asks you to prove this bound).

Page 16 of 29
OS Concepts — Chapter 7 Deadlocks

7.3.2 The Resource-Request Algorithm

This algorithm determines whether a NEW request from process Pi can be safely granted right now. Let
Requesti be Pi's request vector, where Requesti[j] = k means Pi wants k more instances of resource type
Rj.

17. Validate against declared maximum: if Requesti ≤ Needi, proceed to step 2. Otherwise, raise an
error — the process has exceeded its own declared maximum claim.
18. Check availability: if Requesti ≤ Available, proceed to step 3. Otherwise, Pi must wait, since the
resources simply aren't there yet.
19. Tentatively grant and test safety: pretend the resources have been allocated by updating the
state:

Available = Available - Request_i;

Allocation_i = Allocation_i + Request_i;
Need_i = Need_i - Request_i;

If the RESULTING state (after this tentative update) is safe according to the Safety Algorithm, the
transaction is finalized and Pi really is allocated those resources. But if the new state turns out to be
unsafe, then Pi must wait for its Requesti, and the system rolls the state back to exactly what it was
before (undoing the tentative update).

7.3.3 Full Illustrative Example (the canonical banker's algorithm example)

Five processes P0–P4, three resource types A, B, C with totals: A = 10 instances, B = 5 instances, C = 7
instances. Snapshot at time T0:

Process Allocation (A B C) Max (A B C) Available (A B C)

P0 010 753 332

P1 200 322

P2 302 902

P3 211 222

P4 002 433

Need = Max − Allocation, computed row by row:

Process Need (A B C)

P0 743

P1 122

P2 600

P3 011

Page 17 of 29
OS Concepts — Chapter 7 Deadlocks

Process Need (A B C)

P4 431

Claim: this state IS safe. The sequence <P1, P3, P4, P2, P0> satisfies the safety criteria (each process's
Need can be met by Available plus what's freed by the processes before it in the sequence).

Now a new request arrives

Suppose P1 requests one more instance of A and two more of C: Request1 = (1, 0, 2). We must decide
whether to grant it immediately.

20. Step 1 check: is Request1 ≤ Available? (1,0,2) ≤ (3,3,2)? Yes — true.

21. Step 2 — tentatively grant and recompute state:

Process Allocation (A B C) Need (A B C) Available (A B C)

P0 010 743 230

P1 302 020

P2 302 600

P3 211 011

P4 002 431

Running the safety algorithm on this NEW tentative state finds that the sequence <P1, P3, P4, P0, P2>
satisfies safety. Therefore the new state IS safe, and P1's request can be granted immediately.

Two more requests that CANNOT be granted from this new state
A request for (3,3,0) by P4 cannot be granted, simply because the resources are not available (fails
the Available check at step 2 of the Resource-Request Algorithm).
A request for (0,2,0) by P0 CANNOT be granted either, even though the resources ARE technically
available right now — because granting it would push the system into an unsafe state. This is the
entire point of the algorithm: availability alone is not sufficient justification to grant a request.

8. Deadlock Detection (Section 7.6)

If a system uses NEITHER prevention NOR avoidance, deadlocks may genuinely occur. In that case the
system needs: (1) an algorithm to examine system state and determine if a deadlock has actually
happened, and (2) a recovery algorithm (covered in Section 7.7). There is real overhead to this entire
approach — not just the runtime cost of maintaining state and running the detection algorithm, but also
the potential losses involved in actually recovering from a detected deadlock.

Page 18 of 29
OS Concepts — Chapter 7 Deadlocks

8.1 Single Instance of Each Resource Type (Section 7.6.1)

When every resource type has only ONE instance, we use a variant of the resource-allocation graph
called a wait-for graph. It is derived from the RAG by removing all the resource nodes and collapsing the
edges that pass through them.

Constructing the wait-for graph

An edge Pi → Pj in the wait-for graph means process Pi is waiting for process Pj to release some
resource that Pi needs. Formally, edge Pi→Pj exists in the wait-for graph if and only if the
corresponding resource-allocation graph contains BOTH edges Pi→Rq and Rq→Pj for some resource
Rq (i.e., Pi is waiting on a resource that Pj currently holds).

As before, a deadlock exists in the system if and only if the wait-for graph contains a cycle. The system
periodically maintains this graph and invokes a cycle-search algorithm on it. Detecting a cycle in a graph
with n vertices requires on the order of n² operations.

8.2 Several Instances of a Resource Type (Section 7.6.2)

The wait-for graph technique does NOT work when resource types have multiple instances. For that
case, we use a detection algorithm using data structures very similar to the banker's algorithm:

Structure Meaning

Available Vector of length m — number of available instances of each resource type.

Allocation n × m matrix — number of instances of each resource type currently allocated

to each process.

Request n × m matrix — Request[i][j] = k means process Pi is currently requesting k

MORE instances of resource type Rj.

The ≤ relation between vectors is defined exactly as in the banker's algorithm. We again treat matrix
rows as vectors: Allocationi and Requesti. This detection algorithm investigates every possible allocation
sequence for the processes that still remain to be completed — compare it directly with the banker's
safety algorithm.

22. Initialize: Work = Available. For each i = 0, …, n−1: if Allocationi ≠ 0, set Finish[i] = false; otherwise
set Finish[i] = true (processes holding nothing are trivially treated as already ‘finished’ for this
algorithm, since they can't be part of a deadlock from holding nothing).
23. Find a candidate: find index i such that BOTH (a) Finish[i] == false AND (b) Requesti ≤ Work. If no
such i exists, go to step 4.
24. Simulate completion: Work = Work + Allocationi; Finish[i] = true; go back to step 2.
25. Conclude: if Finish[i] == false for SOME i (0 ≤ i < n), the system IS in a deadlocked state. Moreover,
every process Pi with Finish[i] == false is specifically one of the deadlocked processes.
Cost: this detection algorithm requires on the order of m × n² operations to determine whether the
system is currently deadlocked.

Page 19 of 29
OS Concepts — Chapter 7 Deadlocks

Why we reclaim resources optimistically in step 3

You might wonder why, in step 3, we reclaim Pi's resources (treat them as if returned) as soon as
we find Requesti ≤ Work in step 2(b). The reasoning: we know Pi is NOT currently involved in a
deadlock (since its request CAN be satisfied with what's available). So we optimistically assume Pi
will need no further resources, will finish, and will soon return everything it holds to the system. If
this optimistic assumption turns out to be wrong later, a deadlock might form afterward — but that
future deadlock will simply be caught the NEXT time the detection algorithm runs.

Worked Example — Not Deadlocked

Five processes P0–P4, resource types A (7 instances), B (2 instances), C (6 instances). State at T0:

Process Allocation (A B C) Request (A B C) Available (A B C)

P0 010 000 000

P1 200 202

P2 303 000

P3 211 100

P4 002 002

Running the detection algorithm finds the sequence <P0, P2, P3, P1, P4> achieves Finish[i] == true for
every i — so the system is NOT deadlocked.

Worked Example — Now Deadlocked

Suppose P2 now makes ONE additional request, for one more instance of resource type C. The Request
matrix updates to:

Process Request (A B C)

P0 000

P1 202

P2 001

P3 100

P4 002

Now the system IS deadlocked. We can still reclaim the resources held by P0 (since Request0 = 0 ≤ Work
trivially), but after doing so, the available pool is still not sufficient to satisfy ANY of the remaining
processes' requests. The deadlock consists of processes P1, P2, P3, and P4.

Page 20 of 29
OS Concepts — Chapter 7 Deadlocks

8.3 Detection-Algorithm Usage (Section 7.6.3)

A crucial practical question: when should the detection algorithm actually be invoked? The answer
depends on two factors:

26. How OFTEN is a deadlock likely to occur?

27. How MANY processes will be affected by a deadlock once it happens?
If deadlocks happen frequently, the detection algorithm should run frequently too. This matters because
resources allocated to deadlocked processes sit idle until the deadlock is broken, and the number of
processes caught in the deadlock cycle can keep growing the longer it goes undetected.

Key structural insight: deadlocks only occur when SOME process makes a request that cannot be
granted immediately — and that exact request may be the final link that completes a chain of waiting
processes into a cycle.

Two practical invocation strategies

Strategy A — maximally responsive: invoke the detection algorithm EVERY time a resource request
cannot be granted immediately. Benefit: this lets you identify not just the full deadlocked set of
processes, but specifically the ONE process whose request “caused” the deadlock (technically, every
process in the cycle jointly caused it, but this one request was the final trigger). With many different
resource types, a single request might even create several cycles at once, each completed by that
same most-recent request. Downside: invoking detection on every blocked request incurs
considerable computational overhead.
Strategy B — periodic checking: invoke the algorithm only at defined intervals — e.g., once per
hour, or whenever CPU utilization drops below some threshold like 40% (since a growing deadlock
eventually cripples throughput and causes utilization to fall). Downside: if invoked at arbitrary
points in time rather than right when a request fails, the wait-for/resource graph may already
contain MULTIPLE cycles by the time you check, making it generally impossible to identify which
specific deadlocked process actually “caused” the situation.

9. Recovery from Deadlock (Section 7.7)

Once a detection algorithm confirms a deadlock exists, the system has several options. The simplest is to
notify a human operator and let them handle it manually. Alternatively, the system can recover
automatically using one of two fundamental techniques: (1) abort one or more processes to break the
circular wait, or (2) preempt some resources from one or more deadlocked processes.

9.1 Process Termination (Section 7.7.1)

Two methods exist for eliminating deadlock by aborting processes. In both, the system reclaims every
resource allocated to whichever process(es) get terminated.

• Abort ALL deadlocked processes: this definitely breaks the deadlock cycle, but at great expense —
these processes may have been computing for a long time, and all that partial work is discarded
and will likely need to be recomputed from scratch later.

Page 21 of 29
OS Concepts — Chapter 7 Deadlocks

• Abort ONE process at a time, repeatedly, until the cycle breaks: this incurs considerable
overhead too, since the deadlock-detection algorithm must be re-invoked after EACH single
termination, just to check whether any processes remain deadlocked.

Practical difficulty — aborting a process isn't always clean

If a process was in the middle of updating a file when terminated, that file is left in an
incorrect/inconsistent state. Similarly, if a process was mid-way through printing, the system must
reset the printer to a correct state before the next print job can safely begin.

How do you choose WHICH process to abort? (the partial-termination case)

This is fundamentally a policy decision, much like CPU-scheduling decisions — essentially an economic
question of minimizing cost, though “minimum cost” itself isn't a precisely defined quantity. Factors that
commonly influence the choice:

28. What is the priority of the process?

29. How long has the process already computed, and how much longer will it need to finish?
30. How many resources, and what TYPES of resources, has the process used (e.g., are they
simple/cheap to preempt)?
31. How many MORE resources does the process still need to complete?
32. How many processes will need to be terminated in total?
33. Is the process interactive, or a batch process?

9.2 Resource Preemption (Section 7.7.2)

Instead of killing processes outright, we can break the deadlock cycle by successively preempting (taking
away) some resources from certain processes and reassigning those resources to other processes, until
the cycle is broken. If preemption is used this way, three distinct issues must be addressed:

34. Selecting a victim: which resources, and which processes, should be preempted? As with
termination, we want to minimize cost — common cost factors include how many resources a
deadlocked process is currently holding and how much CPU time it has already consumed.
35. Rollback: once a resource is preempted from a process, that process clearly cannot continue
normal execution — it's now missing something it needs. We must roll it back to some earlier
SAFE state and restart it from there. Because determining exactly what a safe rollback state
actually is can be difficult in general, the simplest practical solution is total rollback: just abort the
process entirely and restart it from scratch. A more surgical (partial) rollback — only as far back as
strictly necessary to break the deadlock — is more efficient but requires the system to track much
more detailed state information about every running process.
36. Starvation: how do we guarantee starvation does not occur — i.e., that resources are not always
preempted from the very same unlucky process every time? If victim selection is based purely on
cost factors, the same process might repeatedly get picked as the cheapest victim, and as a result
it NEVER actually completes its task. Any practical system must guard against this. The standard
fix: explicitly factor the NUMBER OF PRIOR ROLLBACKS into the cost calculation, so a process that
has already been a victim many times becomes progressively less likely to be chosen again.

Page 22 of 29
OS Concepts — Chapter 7 Deadlocks

10. Chapter Summary (Section 7.8) — Quick Revision

Core definition
A deadlocked state occurs when two or more processes are waiting indefinitely for an event that
can be caused only by one of those very same waiting processes.

Three principal ways to handle deadlocks:

37. Use a protocol to PREVENT or AVOID deadlocks — guaranteeing the system never enters a
deadlocked state at all.
38. Allow deadlocks to occur, DETECT them, then RECOVER from them.
39. IGNORE the problem entirely — pretend deadlocks never happen. This is the approach actually
used by most real operating systems, including Linux and Windows.
A deadlock can occur only if all FOUR necessary conditions hold at once: mutual exclusion, hold and
wait, no preemption, and circular wait. Prevention works by guaranteeing at least one of these can
never hold.

Deadlock AVOIDANCE (rather than prevention) requires the OS to have a priori information about how
each process will use resources. The banker's algorithm is the canonical example, requiring advance
knowledge of the maximum number of instances of each resource class every process might request.

If no prevention/avoidance protocol is used, a detection-and-recovery scheme can be employed: a

detection algorithm determines whether a deadlock has actually occurred; if so, the system recovers
either by terminating some deadlocked processes or by preempting resources from them.

Where preemption is the chosen recovery method, three issues must always be addressed: selecting a
victim, rollback, and starvation. Systems that select victims purely by cost factors risk starving the same
unlucky process repeatedly, so it never completes.

Final important note from the chapter

Researchers have argued that no single one of these basic approaches (prevention, avoidance,
detection/recovery, ignoring) is appropriate for the ENTIRE spectrum of resource-allocation
problems an operating system faces. In practice, these approaches are combined, letting the system
choose the most suitable technique for each individual class of resources.

11. Quick-Reference Comparison Tables

11.1 Prevention Strategy per Necessary Condition

Condition Attacked How It's Prevented Practical Drawback

Mutual exclusion Make resource sharable (e.g., read-only Many resources (mutex locks) are
files). intrinsically non-sharable — mostly
not a usable strategy.

Page 23 of 29
OS Concepts — Chapter 7 Deadlocks

Condition Attacked How It's Prevented Practical Drawback

Hold and wait Request all resources up front, OR Low resource utilization; possible
release everything before requesting starvation.
more.

No preemption Preempt (implicitly release) a waiting Only works for easily save/restorable
process's resources; restart it once it resources (CPU registers, memory) —
regains old + new resources. not locks/semaphores.

Circular wait Impose a total ordering F on resource Requires discipline from developers;
types; request only in increasing order. dynamic lock acquisition can still
cause deadlock (e.g., bank transfer
example).

11.2 Avoidance vs Detection vs Prevention

Aspect Prevention Avoidance Detection & Recovery

Advance info No — just constrains Yes — max future need No advance info needed.
needed? request style. per process.

When deadlock can Never (guaranteed). Never (guaranteed, via Can actually happen;
occur Safe State checks). caught afterward.

Resource utilization Often low. Can be low (rejects safe- Generally higher — no
looking requests too). restriction until problem
found.

Key algorithm(s) Resource ordering (F Safe State check; RAG Wait-for graph (1
function). algorithm (1 instance); instance); m×n² detection
Banker's Algorithm algorithm (multi-
(multi-instance). instance).

11.3 Algorithm Complexity Cheat-Sheet

Algorithm Applies To Time Complexity

Cycle detection in wait-for graph Single-instance resource O(n²), n = number of

detection processes/vertices

RAG cycle check (avoidance) Single-instance resource O(n²)

avoidance

Banker's Safety Algorithm Multi-instance avoidance O(m × n²)

Banker's Resource-Request Algorithm Multi-instance avoidance Runs Safety Algorithm once →

O(m × n²)

Multi-instance Detection Algorithm Multi-instance detection O(m × n²)

Page 24 of 29
OS Concepts — Chapter 7 Deadlocks

11.4 Key Formulas to Remember

• Need[i][j] = Max[i][j] − Allocation[i][j] (Banker's Algorithm)
• X ≤ Y iff X[k] ≤ Y[k] for every index k (vector comparison used throughout
avoidance/detection)
• F: R → N one-to-one function assigning each resource type a unique natural number, for the
circular-wait prevention ordering
• Resource-Request Algorithm 3-step check: Request ≤ Need, then Request ≤ Available, then
tentatively allocate + run Safety Algorithm

11.5 Definitions At a Glance

Term One-line definition

Deadlock A set of processes each waiting for an event only another process in that
same set can cause.

Request edge (Pi→Rj) Pi has asked for an instance of Rj and is currently waiting.

Assignment edge (Rj→Pi) An instance of Rj has been given to Pi.

Claim edge (dashed, Pi→Rj) Pi might request Rj at some future point (used only in avoidance, single-
instance case).

Safe state A state from which a safe sequence exists, guaranteeing every process can
eventually finish without deadlock.

Safe sequence An ordering of processes such that each one's remaining needs can be met
by available + already-held (by earlier processes) resources.

Wait-for graph RAG with resource nodes removed/collapsed; cycle = deadlock (single-
instance case only).

Witness A FreeBSD lock-order verifier tool that warns when locks are acquired out of
an established order.

Page 25 of 29
OS Concepts — Chapter 7 Deadlocks

12. Notes on the Chapter's Practice Exercises & Exercises

The chapter ends with Practice Exercises (7.1–7.10), general Exercises (7.11–7.26), and Programming
Problems/Projects. These notes summarize the CONCEPTS each one is testing, since working through full
numeric solutions is a separate exercise — use this as a guide to know what each question is really
asking.

12.1 Practice Exercises (7.1–7.10) — Concept Map

# What it's really testing

7.1 Real-world (non-computer) analogies of deadlock — tests whether you grasp the abstract pattern
(e.g., traffic, bureaucratic paperwork loops, social etiquette deadlocks) beyond just OS resources.

7.2 Tests the key distinction: unsafe ≠ deadlocked. Asks you to show a process sequence from an
unsafe state that still completes successfully without deadlock — proving unsafe states are merely
risky, not doomed.

7.3 Direct application of the Banker's Algorithm: compute Need = Max − Allocation, run the Safety
Algorithm to test if the state is safe, then run the Resource-Request Algorithm for a hypothetical
request from P1.

7.4 Compares a 'single master lock F containing everything' (containment) scheme against the circular-
wait total-ordering scheme of 7.4.4 — tests understanding that containment is really a
DEGENERATE case of total ordering (F is simply ordered before everything else).

7.5 Asks for a formal complexity proof of the Safety Algorithm — reinforces WHY it's O(m×n²): the
outer loop runs up to n times (once per process found-and-finished), and each pass scans up to n
processes checking an m-length Need vector.

7.6 A cost-benefit analysis exercise: weighs the overhead of installing a deadlock-avoidance scheme
(10% slower execution, 20% worse turnaround) against the current cost of deadlocks (lost CPU-time
worth of aborted jobs twice a month) — tests applied economic reasoning around deadlock
handling, echoing Section 7.3's 'ignore the problem' discussion.

7.7 Asks whether a system can DETECT starvation, and what to do about it if so — distinguishes
deadlock detection from the separate (related but different) problem of starvation detection.

7.8 Walks through a 'steal resources from a blocked process' policy (the no-preemption-removal
protocol from 7.4.3) with concrete numbers, then asks whether deadlock or indefinite blocking
(starvation) can still occur under that exact policy.

7.9 Tests whether you understand the DEEP similarity (and key difference) between the Banker's safety
algorithm and the deadlock-DETECTION algorithm — by asking if simply redefining Max as Waiting
+ Allocation lets you reuse the safety-algorithm code as a detector. (Hint: detection algorithm uses
CURRENT requests, not a declared future maximum — the semantics genuinely differ even though
the code shape is similar.)

7.1 Tests the boundary case: can a SINGLE single-threaded process ever deadlock by itself? (Generally
0 no for the classic definition, since circular wait requires ≥ 2 entities waiting on each other — though
self-deadlock on a non-reentrant lock a thread already holds is a related but distinct phenomenon
worth discussing.)

Page 26 of 29
OS Concepts — Chapter 7 Deadlocks

12.2 Selected General Exercises — Concept Map

# What it's really testing

7.1 Traffic-deadlock diagram (Figure 7.10): identify all FOUR necessary conditions in a real traffic
1 gridlock, then propose a simple traffic rule that breaks one of them (commonly: don't enter an
intersection unless your exit is clear — a no-hold-and-wait-style rule).

7.1 Reader–writer locks and the four conditions: tests whether shared (reader) access changes the
2 mutual-exclusion analysis, and whether deadlock is still possible purely from writer-vs-writer or
writer-vs-reader ordering conflicts across MULTIPLE such locks.

7.1 Revisits the Pthread mutex example (Figure 7.4): asks you to explain the CPU scheduler's role —
3 since deadlock there depends entirely on the interleaving/timing the scheduler happens to
produce, not on the code alone.

7.1 Asks you to actually FIX the transaction() function from Figure 7.5 so transposed-argument calls
4 can't deadlock — the standard fix is to always acquire locks in a FIXED canonical order (e.g., by
comparing account IDs/addresses) regardless of the 'from'/'to' argument order.

7.1 Compares circular-wait-ordering (a prevention technique) against avoidance schemes like the
5 banker's algorithm, specifically on (a) runtime overhead and (b) system throughput — ordering
schemes are typically cheaper to check but more restrictive; avoidance is more flexible but costs
more per request.

7.1 Six sub-questions about safely modifying Banker's-Algorithm inputs (Available, Max per process,
6 number of processes) WITHOUT reintroducing deadlock risk — tests which changes are always safe
(e.g., increasing Available) vs. which require re-running the safety check (e.g., increasing one
process's Max, since that process might now claim more than the system can ever supply).

7.1 Classic 'deadlock-free by resource-count arithmetic' proofs — show that if total resources, number
7& of processes, and per-process maximum needs satisfy certain inequalities (e.g., sum of max needs <
7.1 m + n), deadlock is mathematically impossible regardless of timing.
8

7.1 Dining-philosophers variants with chopsticks pooled centrally rather than fixed per-philosopher —
9& tests designing a simple ADMISSION RULE for grants (how many of the shared pool can be handed
7.2 out before a request must be refused) that provably avoids deadlock, first for 2 chopsticks per
0 philosopher, then for 3.

7.2 Tests the (false) intuition that 'multi-resource banker's algorithm = single-resource banker's
1 algorithm applied to each type separately' — asks for a counter-example showing that satisfying
safety for EACH resource type individually does NOT guarantee a combined safe state. (The
resource types interact through shared process Need vectors.)

7.2 More worked banker's-algorithm numeric problems: build Need from Allocation/Max, test multiple
2& candidate Available vectors for safety (showing a valid completion order or proving none exists),
7.2 and evaluate specific incoming requests.
3

7.2 Asks for the specific optimistic assumption embedded in the Detection Algorithm (Section 7.6.2,
4 step 3) — that any process whose current request CAN be satisfied will need NO further resources
and will finish; and how this assumption can be violated (the process makes ANOTHER request later

Page 27 of 29
OS Concepts — Chapter 7 Deadlocks

# What it's really testing

before finishing, which a future detection-algorithm run will catch).

7.2 Classic 'one-lane bridge' mutual-exclusion design problem: design a semaphore/mutex-based

5& algorithm preventing two opposite-direction farmers from being on the bridge simultaneously
7.2 (7.25), then extend it to also guarantee starvation-freedom so neither direction can be locked out
6 indefinitely (7.26).

12.3 Programming Problems & Projects

• 7.27 (Programming Problem): Implement the bridge solution from 7.25 using real POSIX threads
— northbound/southbound farmers as separate threads, each sleeping a random time once “on
the bridge” to simulate crossing.
• Programming Project — Banker's Algorithm: Build a full multithreaded program implementing
the banker's algorithm with NUMBER_OF_CUSTOMERS threads and NUMBER_OF_RESOURCES
resource types, using the exact data structures (available, maximum, allocation, need) from
Section 7.5.3. You must implement request_resources() and release_resources() functions
(returning 0 on success, −1 on failure/denial) that are safely callable concurrently from multiple
customer threads, using mutex locks to prevent race conditions on the shared arrays. This project
deliberately combines THREE separate skills at once: multithreading, race-condition prevention,
and deadlock avoidance — exactly mirroring the chapter's overall structure.

12.4 Bibliographical Notes — Key Names to Remember

Researcher(s) Contribution

Dijkstra (1965) One of the earliest and most influential deadlock researchers;
originated the banker's algorithm for a SINGLE resource type.

Holt (1972) First to formalize deadlocks using an allocation-graph model (the

basis of the resource-allocation graph used throughout this chapter);
also covered starvation.

Hyman (1985) Source of the famous Kansas-legislature train-crossing deadlock

anecdote.

Havender (1968) Devised the resource-ordering (circular-wait) prevention scheme,

originally for the IBM OS/360 system.

Habermann (1969) Extended the banker's algorithm from a single resource type to
MULTIPLE resource types.

Coffman, Elphick & Shoshani Presented the deadlock-detection algorithm for multiple instances of
(1971) a resource type (Section 7.6.2).

Baldwin (2002) Presented the witness lock-order verifier (used on FreeBSD).

Page 28 of 29
OS Concepts — Chapter 7 Deadlocks

End of Notes — Chapter 7: Deadlocks

Page 29 of 29