P4-L5: Deadlocks

deadlock

a situation where a group of threads are all waiting on each other, and none can proceed

four necessary conditions for deadlock

• Mutual Exclusion – Only one thread can access a resource at a time.

• Hold and Wait – Threads hold resources while waiting for more.

• No Preemption – Resources can’t be forcibly taken away.

• Circular Wait – A cycle of threads, each waiting for a resource held by the next.

resource allocation graph (RAG)

A directed graph showing which resources are held or requested.

• Cycle = potential deadlock

• Cycle + 1 instance per resource = deadlock guaranteed

deadlock prevention

Prevents at least one of the 4 conditions from happening.
Examples:

• Don’t allow Hold and Wait

• Use preemption

• Lock ordering to prevent Circular Wait

deadlock avoidance

Requires the OS to know future resource requests. Uses:

• Banker’s Algorithm (safe/unsafe state model)

deadlock detection

Let deadlocks happen, then detect and recover.

• Detect cycles in RAG

• Recover by:

  • Killing processes

    • Rolling back to a checkpoint

deadlock recovery

Once a deadlock is detected:

• Kill one or more threads

• Preempt resources

• Rollback to a previous safe state

safe state

a system state where no deadlock can occur, even if it all processes request max resources

unsafe state

not currently in deadlock, but a bad sequence of requests could lead to one

banker’s algorithm

deadlock avoidance strategy. only grant resource requests if they leave the system in a safe state

livelock

Processes continuously change state in response to each other but never make progress (e.g., “After you!” “No, after you!” forever)

starvation

A thread waits indefinitely for a resource while others continue to acquire it.

wait for graph

a simplified RAG where only processes are nodes. an edge from P1 → P2 means P1 is waiting for a resource held by P2. A cycle = deadlock

hold and wait policy violation

one way to prevent deadlocks - don’t let threads hold resources while requesting more. must request all resources at once

preemption strategy

recovery method: forcibly take a resource away from a thread and give it to another to break the deadlock

lock ordering

prevent circular wait by always acquiring locks in a specific global order (e.g., always lock A before B) It’s very common in real systems