Deadlock and its 4 necessary conditions with Code example

Anyone who has read Operating Systems, comes across the concept of Deadlock. We come across several articles giving the definition and listing the 4 necessary conditions for deadlock. I felt there’s a dearth of articles, using a simple code example to demonstrate the deadlock and the 4 conditions. In this article, I would like to present a code demonstrating the 4 conditions that result in deadlock and give a walkthrough of the code.

To start off, I would like to first give the definition of ‘Deadlock’ and the 4 conditions, which result in a deadlock happening in a system. After that I will present the code sample and explain how it results in deadlock.

A Deadlock is a state in which each member of a group waits for another member, including itself, to take action, such as sending a message or more commonly releasing a lock.

A deadlock can occur if all of the below necessary conditions are met (reproducing from wiki)

1. Mutual exclusion: At least one resource must be held in a non-shareable mode. Otherwise, the processes would not be prevented from using the resource when necessary. Only one process can use the resource at any given instant of time.
2. Hold and wait or resource holding: a process is currently holding at least one resource and requesting additional resources which are being held by other processes.
3. No preemption: a resource can be released only voluntarily by the process holding it.
4. Circular wait: each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P1, P2, …, PN}, such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3 and so on until PN is waiting for a resource held by P1.

Following is a code example that demonstrates deadlock by satisfying all the 4 conditions

Now, I would now like to give an explanation of the code.

In the above code, in line no. 2, a lock is being put on the file ‘test.txt’. Since, the lock is being put before a call to the fork() system call, the lock on the file is being held by the parent process. In line no. 4, a call is made to fork() system call which will result in creation of new process which is the child process, duplicating all the code statements after the fork() system call. In line 7, the child process tries to put lock on the same file, which has been placed under lock by the parent process in line 2. Since, the file is already under lock, the child process has to wait for the parent process to release lock to acquire the lock. In line 12, the parent process is waiting for the child process to be over using the wait() system call.

Now, let us see how the above code meets the 4 necessary conditions of the deadlock.

Since, the file can be held by only one process at any time, the lock on it satisfies the condition of ‘mutual exclusion’. In line 2, the parent process acquires lock on the file and is waiting on the child process in line 12 to be over. This results in ‘hold and wait’ condition. In line 7, the child process cannot make the parent process release the lock on the file, this meets the condition of ‘no preemption’. Also, since the child process is waiting for the parent process to release the lock, which in turn is waiting for the child process, this meets the condition of ‘circular wait’.

I always used to forget the deadlock condition, but by using the above code, my understanding of the deadlock has not only improved, but I derive the conditions necessary for the deadlock, instead of remembering them. I hope everyone reading this article will find it useful and will now be able to derive the conditions necessary for deadlock using the above simple code. I hope you liked the article and if there are any changes / clarification, please drop a message and will be happy to update / clarify. Thanks for reading.

For further reading: The ‘C’ Odyssey by Vijay Mukhi