Windows Thread Synchronization 11

 

 

 

Concurrency, Deadlocks and Livelocks

 

Liveness

 

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:

 

1. Threads that are already holding locks request new locks.
2. The requests for new locks are made concurrently.
3. Two or more threads form a circular chain in which each thread waits for a lock which is held by the next thread in the chain.

 

Here is another simple example of a deadlock condition:

 

1. Thread 1 holds lock A and requests lock B.
2. Thread 2 holds lock B and requests lock A.

 

A deadlock can be just a potential deadlock or an actual deadlock and they are distinguished as follows:

 

1. A potential deadlock does not necessarily occur in a given run, but can occur in any execution of the program depending on the scheduling of threads and the timing of lock requests by the threads.
2. An actual deadlock is one that occurs during the execution of a program. An actual deadlock causes the threads involved to hang, but may or may not cause the whole process to hang.

 

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:

 

1. Philosopher zero is holding chopstick zero, but is waiting for chopstick one.
2. Philosopher one is holding chopstick one, but is waiting for chopstick two.
3. Philosopher two is holding chopstick two, but is waiting for chopstick three.
4. Philosopher three is holding chopstick three, but is waiting for chopstick four.
5. Philosopher four is holding chopstick four, but is waiting for chopstick zero.

 

In this situation, nobody can eat and the philosophers are in a deadlock.

 

 

 

< Thread Synchronization 10 | Thread Synchronization Programming | Win32 Programming | Thread Synchronization 12 >