Concurrency, Deadlocks and Livelocks
A concurrent application's ability to execute in a timely manner is known as its liveness. The most common kind of liveness problems in this case are deadlock, starvation and livelock. A deadlock occurs when two threads each lock a different variable at the same time and then try to lock the variable that the other thread already locked. As a result, each thread stops executing and waits for the other thread to release the variable. Because each thread is holding the variable that the other thread wants, nothing occurs, and the threads remain deadlocked.
As an example, deadlock happens when a thread A is holding or locking shared resource and need other resource to continue while thread B is locking or holding the other shared resource needed by thread A while requesting the shared resource which hold by thread A. In simple word, a thread that holds one resource that requested by others and at the same time request resources hold by the other party and at the end two or more threads stop and wait for each other. Incorrect use of synchronization primitives such as mutex and semaphores objects can lead to deadlock. Deadlocks can be considered as a specific kind of race condition. A common symptom of deadlock is that the program or group of threads stops responding. This is also known as a hang. At least two threads are each waiting for a variable that the other thread locked. The threads do not proceed, because neither thread will release its variable until it gets the other variable. The whole program can hang if the program is waiting on one or both of those threads to complete execution.
This type of deadlock is commonly encountered in multithreaded applications. A process with two or more threads can enter deadlock when the following three conditions hold:
Here is another simple example of a deadlock condition:
A deadlock can be just a potential deadlock or an actual deadlock and they are distinguished as follows:
Deadlock Example - The Dining Philosophers
The following Figure shows the arrangement of the Philosophers around the table with bowls and chopsticks.
Five philosophers, numbered zero to four, are sitting at a round table, thinking. As time passes, different individuals become hungry and decide to eat. There is a platter of noodles on the table but each philosopher only has one chopstick to use. In order to eat, they must share chopsticks. The chopstick to the left of each philosopher (as they sit facing the table) has the same number as that philosopher. Each philosopher first reaches for his own chopstick which is the one with his number. When he has his assigned chopstick, he reaches for the chopstick assigned to his neighbor. After he has both chopsticks, he can eat. After eating, he returns the chopsticks to their original positions on the table, one on either side. The process is repeated until there are no more noodles to be eaten. An actual deadlock occurs when every philosopher is holding his own chopstick and waiting for the one from his neighbor to become available:
In this situation, nobody can eat and the philosophers are in a deadlock.