Preventing deadlocks and living that adventurous life.
Introduction
Concurrent computing[1] has become an essential form of computing that has evolved a lot over the years. Concurrent programming refers to a type of programming in which several processes (threads) are executed at the same time (concurrently) instead of sequentially. However, there are a lot of complications that come into the picture while implementing such programs.
One of these problems is known as deadlocks.
What is a deadlock
Deadlock[2][3] is a condition in the execution of a concurrent program when there occurs a permanent blocking of a set of processes that either compete for the system resources or communicate with each other.
A set of processes is deadlocked when each process is blocked awaiting an event that can only be triggered by another blocked process in the set.
The dining philosophers problem
Illustration of the dining philosophers problem
One way to understand this condition by example is by reading about the dining philosophers problem[4][5]. The problem states that K philosophers seated around a circular table with one chopstick between each pair of philosophers. There is one chopstick between each philosopher. A philosopher may eat if he can pickup the two chopsticks adjacent to him. One chopstick may be picked up by any one of its adjacent followers but not both.
Prevention
There are many algorithms that have been developed over the years to prevent deadlocks[6]. Some well-known basic techniques are:
Mutex locks:
A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by producer, the consumer needs to wait, and vice versa.
At any point of time, only one thread can work with the entire buffer. The concept can be generalized using semaphore.
Semaphores
A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time. More differences can be found here: [7].