EECE-4029 Operating Systems Fall 2016
Deadlock

processes, mutex, semaphores, memory management, producer-consumer, files, deadlock, more..

Sample code and documentation

Archive:
   
deadlock.tar     All code and Makefile in a tar file
   
Makefile:
   
Makefile     A simple device - just an array of 100 bytes
   
C/C++ Code:
   
00-deadlock.c     Why is this deadlocked?
01-deadlock.c     A cond variables does not help but looks like java solution
00-deadlockfix.c     One way to fix the deadlock
01-deadlockfix.c     Alternatively, add another lock
   
Applets:
   

Source

    Tool for experimenting with deadlock. Each process needs both resources to complete. Each resource can be held by one process at a time. Cause deadlock by giving the second resource to the second process, first resource to the first process, then attempt to give the first resource to the second process and attempt to give the second resource to the first process. Start both processes. Release processes where you can. The processes never finish.
 

Source

    Attempt at a simple handshake that is intended to work like this: Girl pings Boy, gets confirmation; then Boy pings girl, get confirmation. But the Girl thread invokes ping, asks Boy to confirm and simultaneously the Boy invokes ping and asks Girl to confirm. Neither Boy nor Girl can give time to their confirm call because they are stuck in ping. Hence the handshake cannot be completed.
 

Source

    The handshake is reliable now. The Girl and Boy invoke their ping. One of the two reaches other.release() first but since the other thread has not even entered its ping, no thread is released. The first thread continues to the try-catch and waits before invoking p.confirm(). This allows the other thread to enter its ping. That thread wakes up the first thread by invoking other.release(). It then continues to the try-catch block and waits. Since the first thread is now awake, it gets run time and invokes p.confirm(). Since the other thread is waiting, the first thread enters the other thread's monitor and invokes the confirm. The confirm returns and the first thread continues to other.release(). The other thread awakens and continues to p.confirm(). Since there is no thread that owns the first thread's monitor, confirm completes and the other thread continues to other.release() where nothing happens and the handshake ends.
 

Source

    One way to deal with deadlocks is to detect deadlocked threads, stop them, rollback to a safe state, then restart them. This applet illustrates detection and recovery in Java (although the state recovered to is not anything to brag about, at least the deadlocked threads are stopped). The function test1 creates two threads grabbing locks lock1 and lock2 in different order - hence promoting deadlock. Click on "Do not recover" to run test1 and a deadlock detector. The result of detection is displayed along with the thread ids of any deadlocked threads. Click "Do not recover" several times to deadlock lots of threads. Click "Kill all" to kill all deadlocked threads. Click "Recover" to kill the deadlocked threads in the most recent run of test1.
 
Documentation:
Lecture notes