Deadlocks

Deadlocks: Occur when threads are waiting for resources with circular dependencies

Often involve nonpreemptable resources, which cannot be taken away from its current thread without failing the computation (e.g., storage allocated to a file)

Deadlocks that involve preemptable resources (e.g., CPU) can usually be resolved by reallocation of resources

Starvation: a thread waits indefinitely

A deadlock implies starvation

An Example of Deadlocks

Thread A Thread B

P(x); P(y);

P(y); P(x);

A deadlock won’t always happen with this code, but it might

Deadlocks, Deadlocks, Everywhere…

Can happen with any kind of resource

Among multiple resources

Cannot be resolved for each resource independently

A thread can grab all the memory

The other grabs all the disk space

Each thread may need to wait for the other to release

Round-Robin CPU scheduling cannot prevent deadlocks (or starvation) from happening

Can occur whenever there is waiting…

A Classic Example of Deadlocks

Dinning lawyers (philosophers)

Each needs two chopsticks to eat

If each first grabs the chopstick on their right before the one on their left, and all grab at the same time, we have a deadlock

A Dining Lawyer Implementation

semaphore chopstick[5] = {1, 1, 1, 1, 1};

lawyer(int j) {

while (TRUE) {

P(chopstick[j]);

P(chopstick[(j + 1) % 5];

// eat

V(chopstick[(j + 1) % 5];

V(chopstick[j]);

}

}

Deadlock Prevention Techniques

Deadlock 

All four conditions must be true

If deadlock, then all four conditions are true

All four conditions are true 

Deadlock

To prevent deadlocks

Remove one of the four conditions

Deadlock Prevention Techniques

1. Infinite resources (buy a very large disk)

2. No sharing (independent threads)

3. Allocate all resources at the beginning (if you need 2 chopsticks, grab both at the same time)

4. Make everyone use the same ordering in accessing resource (All threads must call P(x) before P(y)

More Deadlock Prevention Methods

5. No waiting (phone company)

6. Preempt resources (copying memory content to disk)

7. Banker’s algorithm

8. A combination of techniques

Banker’s Algorithm

The idea of Banker’s algorithm:

Allows the sum of requested resources > total resources

As long as, there is some way for all threads to finish without getting into any deadlocks

Banker’s algorithm:

A thread states its maximum resource needs in advance

The OS allocates resource dynamically as needed. A thread waits if granting its request would lead to deadlocks

A request can be granted if some sequential ordering of threads is deadlock free

Deadlock Detection and Recovery

Scan the resource allocation graph

Detect circular chains of requests

Recover from the deadlock

Once A Cycle is Detected…

Some possible actions

Kill a thread and force it to give up resources

Remaining system may be in an inconsistent state

Rollback actions of a deadlocked thread

Not always possible (a file maybe half-way through modifications)

Need checkpointing, or taking snapshots of system states from time to time