Operating Systems Cheatsheet

Deadlocks

Use this Operating Systems reference while you build software engineering projects, review code for technical interview prep, or polish examples for a software engineer resume.

Deadlock Definition

A set of processes is in deadlock if every process in the set is waiting for an event that can only be caused by another process in the set — creating a circular wait with no possibility of progress.

The Four Necessary Conditions (Coffman Conditions)

All four must hold simultaneously for deadlock to occur.

Condition	Meaning	Example
Mutual exclusion	Resources are non-shareable	Only one process can hold a printer
Hold and wait	Process holds ≥1 resource while waiting for more	Holds lock A, waits for lock B
No preemption	Resources cannot be forcibly taken away	OS can't revoke a held mutex
Circular wait	Chain P₁ → r₁ → P₂ → r₂ → … → Pₙ → rₙ → P₁	P1 waits for P2's lock; P2 waits for P1's lock

Preventing any one condition prevents deadlock.

Resource Allocation Graph (RAG)

Directed graph with two node types: - Process nodes (circles): P₁, P₂, … - Resource nodes (boxes, dots = instances): R₁, R₂, …

Edge	Direction	Meaning
Request edge	Pᵢ → Rⱼ	Process i is waiting for resource j
Assignment edge	Rⱼ → Pᵢ	One instance of resource j is held by process i

Deadlock detection rule: - If all resources have 1 instance: cycle in RAG ⟺ deadlock - If resources have multiple instances: cycle is necessary but not sufficient — use banker's algorithm to confirm

Deadlock Handling Strategies

Strategy	Approach	Overhead	Used in
Prevention	Eliminate ≥1 Coffman condition	Design-time constraints	Some embedded/RT systems
Avoidance	Allocate only if safe state remains	Per-request check	Rarely (overhead)
Detection + Recovery	Allow deadlock; detect and break it	Detection cost	Many OSes
Ignore (ostrich)	Assume it never happens / very rare	None	Linux, Windows

Deadlock Prevention

Attack each Coffman condition:

Condition	Prevention method	Drawback
Mutual exclusion	Make resources sharable (e.g., read-only files)	Not always possible
Hold and wait	Request all resources at once before start	Low utilization; starvation
No preemption	Preempt resources from waiting process	Only for state-saveable resources
Circular wait	Impose total ordering on resource types; always acquire in order	Ordering can be cumbersome

Deadlock Avoidance

OS tracks resource allocation state and only grants requests that keep system in a safe state.

Safe state: there exists a sequence ⟨P₁, P₂, …, Pₙ⟩ such that each Pᵢ's remaining resource needs can be satisfied by currently available resources + those held by P₁ … Pᵢ₋₁.

safe ⟹ no deadlock (but unsafe ≠ deadlock)

Banker's Algorithm

For each resource type with multiple instances.

Data structures (n processes, m resource types):

Array	Size	Meaning
`Available[j]`	m	Free instances of resource j
`Max[i][j]`	n×m	Max demand of process i for resource j
`Allocation[i][j]`	n×m	Current allocation of j to i
`Need[i][j]`	n×m	`Max[i][j] − Allocation[i][j]`

Safety algorithm:

Work = Available
Finish[i] = false for all i

repeat:
    find i such that Finish[i]=false AND Need[i] ≤ Work
    if found:
        Work += Allocation[i]
        Finish[i] = true
until no such i

if all Finish[i] = true → SAFE
else → UNSAFE

Resource-request algorithm:

Process i requests Request[i]:
1. If Request[i] > Need[i] → error
2. If Request[i] > Available → wait (not enough)
3. Tentatively allocate:
   Available -= Request[i]
   Allocation[i] += Request[i]
   Need[i] -= Request[i]
4. Run safety algorithm
5. If safe → grant; else → rollback, wait

Banker's Example

3 processes (P0, P1, P2), 3 resources (A=10, B=5, C=7 total)

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

Available = (3, 3, 2). Safe sequence: P1 → P2 → P0 ✓

Deadlock Detection

Single Instance: Cycle Detection in RAG

Use DFS; if back-edge found → cycle → deadlock.

Multiple Instances: Detection Algorithm

Same as banker's safety check but using Allocation (not Need):

Work = Available
Finish[i] = (Allocation[i] == 0) for all i

repeat:
    find i: Finish[i]=false AND Request[i] ≤ Work
    if found:
        Work += Allocation[i]; Finish[i] = true
until no such i

if some Finish[i] = false → those processes are deadlocked

When to run: periodically or whenever a resource request cannot be granted immediately. Frequent runs → fast detection but high CPU cost.

Deadlock Recovery

Method	Description	Cost
Abort all	Kill all deadlocked processes	High — all work lost
Abort one at a time	Kill cheapest; re-run detection	Iterative overhead
Resource preemption	Take resource from victim, rollback	Needs checkpointing; starvation risk

Victim selection criteria: priority, elapsed time, resources held, resources still needed, how many times already rolled back.

Lock Ordering (Prevention in Practice)

// Always acquire in a consistent global order to break circular wait:
// Rule: always lock mu1 before mu2

void transfer(Account *from, Account *to, int amount) {
    pthread_mutex_t *first  = (from->id < to->id) ? &from->lock : &to->lock;
    pthread_mutex_t *second = (from->id < to->id) ? &to->lock : &from->lock;
    pthread_mutex_lock(first);
    pthread_mutex_lock(second);
    from->balance -= amount;
    to->balance   += amount;
    pthread_mutex_unlock(second);
    pthread_mutex_unlock(first);
}

Livelock vs Starvation

Condition	Description	Example
Deadlock	Processes blocked, no progress	Each holds one lock, waits for the other
Livelock	Processes active but making no progress	Two politely step aside for each other forever
Starvation	Process indefinitely delayed	Low-priority process never scheduled