Q: Describe your own example which may encounter deadlocks.
a. Show that the four necessary conditions for deadlock indeed holds in this example.
b. State a simple way for avoiding deadlocks in this case.

A: A deadlock occurs when two or more threads are each waiting on events (e.g. semaphores, resources, etc.) that only the other thread can release.

Deadlock can arise if four conditions hold simultaneously:

• Mutual exclusion: only one process at a time can use a resource.


• Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.


• No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task.


• Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1is waiting for a resource that is held by P2, …, Pn–1is waiting for a resource that is held by Pn, and P0is waiting for a resource that is held by P0.

1. Example descr iption

Here's a simple example. There are two threads and two resources we'll try to get locks for.

The first thread tries to lock resource1 first and we will pause for a bit, simulating some file I/O or something else. Basically, we just want to give the other thread a chance to run. After the pause, thread 1 will wait until we can get a lock on resource 2.

The second thread tries to lock resource 2 right away and just like thread 1, it will pause for a bit. After the pause, it will tries to lock resource 1. However, thread 1 locked resource 1 , and won't release it till it gets a lock on resource 2. To make things worse, thread 2 holds the lock on resource2, and won't release it till it gets resource1, which cause the deadlock situation. Neither thread can run, and the program freezes up and it will never exit.



As you can see from the below picture, the program never stop and never print "Thread 2: locked resource 1" and "Thread 1: locked resource 2".



2.  Deadlock analysis

• Mutual exclusion: The lock on a resource is exclusive. Only one thread can own the resource during the lock.


• Hold and wait: Because Thread1 and Thread2 are created and Thread1 owns resources 1 and it wants another resources (resource 2) taken by Thread2, it must wait for Thread2 to release.


• No preemption: Resource 1 can be released only voluntarily by thread 1 holding it, after thread 1 has completed its task.


• Circular wait: Thread 1 owns resource 1 and wants resource 2 and Thread 2 owns resource 2 and wants resource 1.

3. Solution to deadlock

Once a deadlock occurs, we can't solve it. We can only avoid deadlock. Since deadlocks need to satisfy four conditions, We can break the deadlock by breaking any rule.

We can bread the deadlock by breaking the second rule: hold and wait. We can make all threads acquire their locks in the same order.



And we can see from the result. The problem has been solved.