dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming. the solution is attributed to dutch mathematician th. j. dekker by edsger w. dijkstra in his manuscript on cooperating sequential processes.e.w. dijkstra, cooperating sequential processes, manuscript, 1965. retrieved 13. may, 2009. it allows two threads to share a single-use resource without conflict, using only shared memory for communication. it avoids the strict alternation of a naÃ¯ve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented. ==introduction== if two processes attempt to enter a critical section at the same time, the algorithm will allow only one process in, based on whose turn it is. if one process is already in the critical section, the other process will busy wait for the first process to exit. this is done by the use of two flags, flag[0] and flag[1], which indicate an intention to enter the critical section and a turn variable that indicates who has priority between the two processes. ==pseudocode== {| style="width:75%" |- | colspan="2" align="left"| //flag[] is boolean array; and turn is an integer flag[0] = false flag[1] = false turn = 0 // or 1 |- | align="left" | p0: flag[0] = true; while (flag[1]) { if (turn == 1) { flag[0] = false; while (turn == 1) { // busy wait } flag[0] = true; } } // critical section ... turn = 1; flag[0] = false; // remainder section |align="left" | p1: flag[1] = true; while (flag[0]) { if (turn == 0) { flag[1] = false; while (turn == 0) { // busy wait } flag[1] = true; } } // critical section ... turn = 0; flag[1] = false; // remainder section |} processes indicate an intention to enter the critical section which is tested by the outer while loop. if the other process has not flagged intent, the critical section can be entered safely irrespective of the current turn. mutual exclusion will still be guaranteed as neither process can become critical before setting their flag (implying at least one process will enter the while loop). this also guarantees progress as waiting will not occur on a process which has withdrawn intent to become critical. alternatively, if the other process's variable was set the while loop is entered and the turn variable will establish who is permitted to become critical. processes without priority will withdraw their intention to enter the critical section until they are given priority again (the inner while loop). processes with priority will break from the while loop and enter their critical section. dekker's algorithm guarantees mutual exclusion, freedom from deadlock, and freedom from starvation. let us see why the last property holds. suppose p0 is stuck inside the "while flag[1]" loop f
Concurrency_control_algorithms Dutch_inventions