Deadlock

It is possible for two program to be hung up waiting for each other.

For example

Two programs may reach require two I/O devices to perform some operations (e.g., disk to tape copy). One of the programs has seized control of one of the devices and the other program to release the desired resource. Such a deadlock may depend on the chance timing of resource allocation and release.

Patrick also gave me the analogy of the Dining philosophers problem. https://howardhinnant.github.io/dining_philosophers.html

$\to$ Five philosophers dine together at the same table. Each philosopher has his own plate at the table. There is a fork between each plate. The dish served is a kind of spaghetti which has to be eaten with two forks. Each philosopher can only alternately think and eat. Moreover, a philosopher can only eat his spaghetti when he has both a left and right fork. Thus two forks will only be available when his two nearest neighbours are thinking, not eating. After an individual philosopher finishes eating, he will put down both forks. The problem is how to design a regimen (a concurrent algorithm) such that any philosopher will not starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think (an issue of incomplete information).

Deadlock avoidance: (Conditions and requirements)

• Maximum resource requirements must be stated in advance
• Processes under consideration must be independent; no synchronization requirements
• There must be a fixed number of resources to allocate
• No process may exit while holding resources

Conditions for Deadlock

1. Mutual exclusion
2. Hold and wait
3. No preemption
4. Circular Wait

From CS343

Deadlock is the state when one or more processes are waiting for an event that will not occur.

Unlike live-lock/starvation, deadlocked task is blocked so not consuming CPU.

Synchronization Deadlock

Failure in cooperation, so a blocked task is never unblocked (stuck waiting):

int main(){
	uSemaphore s(0); // closed
	s.P();           // wait for lock to open (a V to happen)
}

Mutual Exclusion Deadlock

• Failure to acquire a resource protected by mutual exclusion
• Deadlock, unless one of the cars is willing to backup
• There are 5 conditions that must occur for a set of processes to deadlock
  1. A concrete shared-resource requiring mutual exclusion, i.e., exists without a task.
     • A task “wanting to drive across the intersection” is not a resource
  2. A process holds a resource while waiting for access to a resource held by another process (hold and wait)
  3. Once a process has gained access to a resource, the runtime system cannot get it back (no preemption)
  4. There exists a circular wait of processes on resources
  5. These conditions must occur simultaneously
• Simple example using semaphores:

Deadlock Prevention

todo

Deadlock Avoidance

todo

Explain why preventing synchronization deadlocks is not practical

Briefly explain the difference between deadlock prevention and deadlock avoidance

Deadlock prevention removes one of the conditions necessary for deadlock, thus ensuring that deadlock cannot occur.

Deadlock avoidance allows a thread/task to move into a potentially unsafe state, but the system prevents deadlock from occurring by refusing requests that would (conservatively) lead to deadlock.

Name a technique for mutual exclusion deadlock avoidance.

Banker’s Algorithm or Allocation Graphs.

What is the only reasonable practical method for preventing mutual exclusion deadlock?

The ordered resource policy is the only practical method.