Deadlocks

1. Deadlocks

A set of processes is deadlocked if each process is waiting for an event that only another process can cause. The four necessary conditions for resource deadlock are:

• Mutual Exclusion - each resource is either available or assigned to exactly one process.
• Hold & Wait - each process can request resources while holding others.
• No Preemption - resources given to a process cannot be forcibly revoked.
• Circular Wait - a set of processes in a circular chain, each waiting for a resource held by the next.

A directed graph can model resource allocation:

• Directed edge from resource to process if the resource is held by the process.
• Directed edge from process to resource if the process is waiting for the resource.

A cycle in the graph indicates a deadlock.

2. Dealing with Deadlocks

1. Ignore It (The Ostrich Algorithm) - contention for resources is low, so deadlocks are rare.
2. Detection & recovery - periodically check for deadlocks and recover.
3. Dynamic Avoidance - dynamically consider every request and decide whether it is safe to grant it, needs some information regarding potential resource use.
4. Prevention - prevent deadlocks by ensuring that at least one of the four deadlock conditions never holds.

2.1 Detection and Recovery

• Detects deadlock and recovers after the fact.
• Dynamically builds resource ownership graph and looks for cycle.
• When an edge has been inspected, it is marked and not visited again.

1. For each node:
2. Initialize to the empty list.
3. Add the current node to and check if it apprears in two times.
4. If it does, a cycle has been detected.
5. If no cycle is detected, from current node check if any unmarked outgoing edge.
6. If yes, goto 7. If no, goto 8.
7. Pick unmarked outgoing edge, mark it, follow it to the new current node, goto 3.
8. If this is initial node, no cycle exists.

Recovery can be done with the following strategies:

• Pre-emption: temporarily take resource from owner and give to another.
• Rollback: processes are periodically checkpoint (memory image, state). On a deadlock, rollback.
• Killing processes: select random process in cycle and kill it.

2.2 Prevention

1. Remove mutual exclusion - share the resource.
2. Remove hold and wait - require all processoes to request resources before start (need to know what you need in advance).
3. Remove no preemption - allow processes to be preempted.
4. Remove circular wait - resources must be acquired in a total order.

1void no_hold_and_wait(void) {
2  pthread_mutex_lock(&lock_acquisition);
3  pthread_mutex_lock(&m1);
4  pthread_mutex_lock(&m2);
5
6  critical_section();
7
8  pthread_mutex_unlock(&m2);
9}
10
11void no_preemption(void) {
12  top:
13  pthread_mutex_lock(&m1);
14  if (pthread_mutex_trylock(&m2) != 0) {
15    pthread_mutex_unlock(&m1);
16    goto top;
17  }
18
19  critical_section();
20
21  pthread_mutex_unlock(&m2);
22  pthread_mutex_unlock(&m1);
23}
24
25void no_circular_wait(void) {
26  if (m1 > m2) {
27    pthread_mutex_lock(&m1);
28    pthread_mutex_lock(&m2);
29  } else {
30    pthread_mutex_lock(&m2);
31    pthread_mutex_lock(&m1);
32  }
33
34  critical_section();
35
36  pthread_mutex_unlock(&m2);
37  pthread_mutex_unlock(&m1);
38}

3. Communication Deadlocks

• Process A sends message to B and blocks waiting on B's reply.
• B didn't get A's message, then A is blocked and B is blocked waiting for A's message.
• Deadlock.

This is solved by timeout and retransmission.

4. Livelocks

Processes / threads are not blocked, but the system is not making progress.

For example, a system receiving and processing incoming messages. Processing thread has lower priority and never runs under high load (receive livelock).

4.1 Starvation

A process is ready to run but never gets the CPU. This is a form of livelock, solved by the scheduler.