ÿþ<html> <head> <meta http-equiv="Content-Type" content="text/html; charset=unicode" /> <meta http-equiv="Content-Language" content="en-us" /> <style> <!-- p.MsoNormal, li.MsoNormal {margin-top:0mm; margin-right:0mm; margin-bottom:10.0pt; margin-left:0mm; line-height:115%; font-size:12.0pt; font-family:"Times New Roman","serif";} a:link {color:blue; text-decoration:underline;} a:visited {color:purple; text-decoration:underline;} p {margin-right:0mm; margin-left:0mm; font-size:12.0pt; font-family:"Times New Roman","serif";} ol {margin-bottom:0mm;} --> </style> <title>The Windows thread synchronization programming: concurrency, deadlocks, livelocks, liveness and deadlock example - The Dining Philosophers</title> <meta name="keywords" content="deadlock, concurrency, livelocks, problems, errors, programming, system, technology, efficiency, performance, hardware, processors, microprocessors" /> <meta name="description" content="The Win32 programming tutorial on the concurrency, deadlocks, livelocks, liveness and deadlock example - The Dining Philosophers" /> </head> <body lang="EN-US" link="#0000FF" vlink="#800080" topmargin="20" leftmargin="20" rightmargin="20" bottommargin="20"> <div class="Section1"> <h3 align="center" style="margin-bottom:0mm;margin-bottom:0; text-align:center; margin-top:0"><font size="5" face="Byington"> <span style="line-height:115%;font-weight:400">Windows Thread Synchronization 11</span></font></h3> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:0; margin-top:0">&nbsp;</p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt">&nbsp;</p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt" align="center"> <script type="text/javascript"><!-- google_ad_client = "pub-8089415323104206"; google_ad_slot = "0761177910"; google_ad_width = 728; google_ad_height = 90; //--> </script> &nbsp;<script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt">&nbsp;</p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt">&nbsp;</p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"><b> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height:115%; font-weight:bold">Concurrency, Deadlocks and Livelocks</span></font></b></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"><b> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height:115%; font-weight:bold">Liveness</span></font></b></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%"> A concurrent application&#39;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.</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%"> 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.</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt">&nbsp;</p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt" align="center"> <font face="Arial"> <img width="414" height="265" src="threadprocesssynchronizationapis11_files/winthreadprocesssynchronizationcode035.png" /></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%"> 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:</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <ol style="margin-top:0mm" start="1" type="1"> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">Threads that are already holding locks request new locks.</span></font></li> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">The requests for new locks are made concurrently.</span></font></li> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">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.</span></font></li> </ol> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%"> Here is another simple example of a deadlock condition:</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <ol style="margin-top:0mm" start="1" type="1"> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">Thread 1 holds lock A and requests lock B.</span></font></li> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">Thread 2 holds lock B and requests lock A.</span></font></li> </ol> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%"> A deadlock can be just a potential deadlock or an actual deadlock and they are distinguished as follows:</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <ol style="margin-top:0mm" start="1" type="1"> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">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.</span></font></li> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">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.</span></font></li> </ol> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"><b> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height:115%; font-weight:bold">Deadlock Example - The Dining Philosophers</span></font></b></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%"> The following Figure shows the arrangement of the Philosophers around the table with bowls and chopsticks.</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt">&nbsp;</p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:0; margin-top:0" align="center"> <font face="Arial"> <img width="337" height="309" src="threadprocesssynchronizationapis11_files/winthreadprocesssynchronizationcode036.png" alt="Concurrency, Deadlocks and Livelocks: " /></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:0; margin-top:0">&nbsp;</p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:0; margin-top:0"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%"> 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:</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <ol style="margin-top:0mm" start="1" type="1"> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">Philosopher zero is holding chopstick zero, but is waiting for chopstick one.</span></font></li> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">Philosopher one is holding chopstick one, but is waiting for chopstick two.</span></font></li> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">Philosopher two is holding chopstick two, but is waiting for chopstick three.</span></font></li> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">Philosopher three is holding chopstick three, but is waiting for chopstick four.</span></font></li> <li class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"> <span style="font-size:12.0pt;line-height: 115%">Philosopher four is holding chopstick four, but is waiting for chopstick zero.</span></font></li> </ol> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%">&nbsp;</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt"> <font size="3" face="Arial"><span style="font-size:12.0pt;line-height:115%"> In this situation, nobody can eat and the philosophers are in a deadlock.</span></font></p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt">&nbsp;</p> <p class="MsoNormal" style="margin-bottom:0mm;margin-bottom:.0001pt">&nbsp;</p> <h3 align="center" style="margin-top: 0; margin-bottom: 0"> <script type="text/javascript"><!-- google_ad_client = "pub-8089415323104206"; google_ad_slot = "2156170134"; google_ad_width = 728; google_ad_height = 15; //--> </script> &nbsp;<script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script></h3> <p align="center" style="margin-top: 0; margin-bottom: 0">&nbsp;</p> <h3 align="center" style="margin-top: 0; margin-bottom: 0"> <font face="Byington"><span style="font-weight: 400">&lt; <a title="The Windows Win32 thread synchronization tutorial: Concurrency and race conditions with program example" style="color: blue; text-decoration: underline" href="threadprocesssynchronizationapis11_9.html"> Thread Synchronization 10</a> | <a title="The Windows Win32 thread synchronization techniques programming tutorials with program examples and code samples" style="color: blue; text-decoration: underline" href="threadprocesssynchronizationapis11index.html"> Thread Synchronization Programming</a> | <a title="The Win32 programming tutorial using Visual Studio, C and C++ languages" style="color: blue; text-decoration: underline" href="index.html"> Win32 Programming</a> | <a title="The deadlock and critical section Win32 program example" style="color: blue; text-decoration: underline" href="threadprocesssynchronizationapis11_11.html"> Thread Synchronization 12</a> &gt;</span></font></h3> <p align="left" style="margin-top: 0; margin-bottom: 0">&nbsp;</p> <div align="center"> <script src="http://tag.contextweb.com/TagPublish/getjs.aspx?action=VIEWAD&cwrun=200&cwadformat=728X90&cwpid=527221&cwwidth=728&cwheight=90&cwpnet=1&cwtagid=82740"></script> </div> </div> </body> </html>