Editing Dekker's algorithm

{{Short description|Mutual exclusion algorithm}}
'''Dekker's algorithm''' is the first known correct solution to the [[mutual exclusion]] problem in [[concurrent programming]] where processes only communicate via shared memory. The solution is attributed to [[Dutch people|Dutch]] [[mathematician]] [[Theodorus Dekker|Th. J. Dekker]] by [[Edsger W. Dijkstra]] in an unpublished paper on sequential process descriptions<ref>{{Cite EWD|35|Over de sequentialiteit van procesbeschrijvingen}} (undated, 1962 or 1963);  English translation [http://www.cs.utexas.edu/users/EWD/translations/EWD35-English.html About the sequentiality of process descriptions]</ref> and his manuscript on [[cooperating sequential processes]].<ref>{{Cite EWD|123|Cooperating sequential processes}} (September 1965)</ref> It allows two threads to share a single-use resource without conflict, using only [[Shared memory (interprocess communication)|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.

== Overview ==

If two processes attempt to enter a [[critical section]] at the same time, the algorithm will allow only one process in, based on whose {{mono|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, {{mono|wants_to_enter[0]}} and {{mono|wants_to_enter[1]}}, which indicate an intention to enter the critical section on the part of processes 0 and 1, respectively, and a variable {{mono|turn}} that indicates who has priority between the two processes.

[[File:Dekker's Algorithm.svg|thumb|Dekker's algorithm]]

Dekker's algorithm can be expressed in [[pseudocode]], as follows.<ref>{{cite journal |title=Some Myths About Famous Mutual Exclusion Algorithms |first=K. |last=Alagarsamy |journal=ACM SIGACT News |pages=94–103 |year=2003 |volume=34 |issue=3|doi=10.1145/945526.945527 |s2cid=7545330 }}</ref>

{| style="margin:1em auto; width:75%"
| colspan="2" align="left"|
<syntaxhighlight lang="text">
    variables
        wants_to_enter : array of 2 booleans
        turn : integer

    wants_to_enter[0] ← false
    wants_to_enter[1] ← false
    turn ← 0   // or 1
</syntaxhighlight>
|-
| align="left" |
<syntaxhighlight lang="text">
p0:
   wants_to_enter[0] ← true
   while wants_to_enter[1] {
      if turn ≠ 0 {
         wants_to_enter[0] ← false
         while turn ≠ 0 {
           // busy wait
         }
         wants_to_enter[0] ← true
      }
   }

   // critical section
   ...
   turn ← 1
   wants_to_enter[0] ← false
   // remainder section
</syntaxhighlight>
|align="left" |
<syntaxhighlight lang="text">
p1:
   wants_to_enter[1] ← true
   while wants_to_enter[0] {
      if turn ≠ 1 {
         wants_to_enter[1] ← false
         while turn ≠ 1 {
           // busy wait
         }
         wants_to_enter[1] ← true
      }
   }

   // critical section
   ...
   turn ← 0
   wants_to_enter[1] ← false
   // remainder section
</syntaxhighlight>
|}

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 (computer science)|deadlock]], and freedom from [[Resource starvation|starvation]]. Let us see why the last property holds. Suppose p0 is stuck inside the {{mono|while wants_to_enter[1]}} loop forever. There is freedom from deadlock, so eventually p1 will proceed to its critical section and set {{mono|1=turn = 0}} (and the value of turn will remain unchanged as long as p0 doesn't progress). Eventually p0 will break out of the inner {{mono|while turn ≠ 0}} loop (if it was ever stuck on it). After that it will set {{mono|wants_to_enter[0]}} to true and settle down to waiting for {{mono|wants_to_enter[1]}} to become false (since {{mono|1=turn = 0}}, it will never do the actions in the while loop). The next time p1 tries to enter its critical section, it will be forced to execute the actions in its {{mono|while wants_to_enter[0]}} loop. In particular, it will eventually set {{mono|wants_to_enter[1]}} to false and get stuck in the {{mono|while turn ≠ 1}} loop (since turn remains 0). The next time control passes to p0, it will exit the {{mono|while wants_to_enter[1]}} loop and enter its critical section.

If the algorithm were modified by performing the actions in the {{mono|while wants_to_enter[1]}} loop without checking if {{mono|1=turn = 0}}, then there is a possibility of starvation. Thus all the steps in the algorithm are necessary.

== Notes ==
{{unreferenced section|date=May 2015}}
One advantage of this algorithm is that it doesn't require special [[test-and-set]] (atomic read/modify/write) instructions and is therefore highly portable between languages and machine architectures.  One disadvantage is that it is limited to two processes and makes use of [[busy waiting]] instead of process suspension.  (The use of busy waiting suggests that processes should spend a minimum amount of time inside the critical section.)

Modern operating systems provide mutual exclusion primitives that are more general and flexible than Dekker's algorithm.  However, in the absence of actual contention between the two processes, the entry and exit from critical section is extremely efficient when Dekker's algorithm is used.

Many modern [[CPU]]s execute their instructions in an out-of-order fashion; even memory accesses can be reordered (see [[memory ordering]]). This algorithm won't work on [[Symmetric multiprocessing|SMP]] machines equipped with these CPUs without the use of [[memory barrier]]s.

Additionally, many optimizing compilers can perform transformations that will cause this algorithm to fail regardless of the platform.  In many languages, it is legal for a compiler to detect that the flag variables {{mono|wants_to_enter[0]}} and {{mono|wants_to_enter[1]}} are never accessed in the loop.  It can then remove the writes to those variables from the loop, using a process called [[loop-invariant code motion]].  It would also be possible for many compilers to detect that the ''turn'' variable is never modified by the inner loop, and perform a similar transformation, resulting in a potential [[infinite loop]].  If either of these transformations is performed, the algorithm will fail, regardless of architecture.

To alleviate this problem, [[Volatile variable|volatile]] variables should be marked as modifiable outside the scope of the currently executing context. For example, in C, C++, C# or Java, one would annotate these variables as 'volatile'.  Note however that the C/C++ "volatile" attribute only guarantees that the compiler generates code with the proper ordering; it does not include the necessary [[Memory barrier#Out-of-order execution versus compiler reordering optimizations|memory barriers]] to guarantee in-order ''execution'' of that code. [[C++11]] atomic variables can be used to guarantee the appropriate ordering requirements — by default, operations on atomic variables are sequentially consistent so if the wants_to_enter and turn variables are atomic a naive implementation will "just work". Alternatively, ordering can be guaranteed by the explicit use of separate fences, with the load and store operations using a relaxed ordering.

== See also ==
* [[Eisenberg & McGuire algorithm]]
* [[Peterson's algorithm]]
* [[Lamport's bakery algorithm]]
* [[Szymański's algorithm]]
* [[Semaphore (programming)|Semaphores]]

== References ==
{{reflist|30em}}

{{Edsger Dijkstra}}
[[Category:Concurrency control algorithms]]
[[Category:Edsger W. Dijkstra]]
[[Category:Articles with example pseudocode]]