Dekker's algorithm
Encyclopedia
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. 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 naive turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented.
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 which indicates who has priority between the two processes.
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 forever. There is freedom from deadlock, so eventually p1 will proceed to its critical section and set 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 "while turn ≠ 0" loop (if it was ever stuck on it). After that it will set flag[0] := true and settle down to waiting for flag[1] to become false (since 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 "while flag[0]" loop. In particular, it will eventually set flag[1] = false and get stuck in the "while turn ≠ 1" loop (since turn remains 0). The next time control passes to p0, it will exit the "while flag[1]" loop and enter its critical section.
If the algorithm were modified by performing the actions in the "while flag[1]" loop without checking if turn = 0, then there is a possibility of starvation. Thus all the steps in the algorithm are necessary.
(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 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 CPUs execute their instructions in an out-of-order fashion, even memory accesses can be reordered (see memory ordering
). This algorithm won't work on 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 flag[0] and flag[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
variables should be marked as modifiable outside the scope of the currently executing context. For example, in 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 barriers to guarantee in-order execution of that code. C++0x
atomic variables can be used to guarantee the appropriate ordering requirements — by default, operations on atomic variables are sequentially consistent so if the flag 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.
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
problem in concurrent programming. The solution is attributed to Dutch
Dutch people
The Dutch people are an ethnic group native to the Netherlands. They share a common culture and speak the Dutch language. Dutch people and their descendants are found in migrant communities worldwide, notably in Suriname, Chile, Brazil, Canada, Australia, South Africa, New Zealand, and the United...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Th. J. Dekker
Theodorus Dekker
Theodorus Jozef Dekker is a Dutch mathematician.Dekker completed his Ph.D degree from the University of Amsterdam in 1958...
by Edsger W. Dijkstra in his manuscript on cooperating sequential processes. It allows two threads to share a single-use resource without conflict, using only shared memory
Shared memory
In computing, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors...
for communication.
It avoids the strict alternation of a naive turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented.
Introduction
If two processes attempt to enter a critical sectionCritical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
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 which indicates who has priority between the two processes.
Pseudocode
flag[0] := false flag[1] := false turn := 0 // or 1 |
|
| p0: flag[0] := true while flag[1] = true { if turn ≠ 0 { flag[0] := false while turn ≠ 0 { } flag[0] := true } } // critical section ... turn := 1 flag[0] := false // remainder section |
p1: flag[1] := true while flag[0] = true { if turn ≠ 1 { flag[1] := false while turn ≠ 1 { } 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
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
, freedom from deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
, and freedom from starvation
Resource starvation
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
. Let us see why the last property holds. Suppose p0 is stuck inside the "while flag[1]" loop forever. There is freedom from deadlock, so eventually p1 will proceed to its critical section and set 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 "while turn ≠ 0" loop (if it was ever stuck on it). After that it will set flag[0] := true and settle down to waiting for flag[1] to become false (since 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 "while flag[0]" loop. In particular, it will eventually set flag[1] = false and get stuck in the "while turn ≠ 1" loop (since turn remains 0). The next time control passes to p0, it will exit the "while flag[1]" loop and enter its critical section.
If the algorithm were modified by performing the actions in the "while flag[1]" loop without checking if turn = 0, then there is a possibility of starvation. Thus all the steps in the algorithm are necessary.
Note
One advantage of this algorithm is that it doesn't require special Test-and-setTest-and-set
In computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
(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
Busy waiting
In software engineering, busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input is available, or if a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary...
instead of process suspension. (The use of busy waiting suggests that processes should spend a minimum 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 CPUs execute their instructions in an out-of-order fashion, even memory accesses can be reordered (see memory ordering
Memory ordering
Memory ordering is a group of properties of the modern microprocessors, characterising their possibilities in memory operations reordering. It is a type of out-of-order execution. Memory reordering can be used to fully utilize different cache and memory banks.On most modern uniprocessors memory...
). This algorithm won't work on SMP
Symmetric multiprocessing
In computing, symmetric multiprocessing involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory and are controlled by a single OS instance. Most common multiprocessor systems today use an SMP architecture...
machines equipped with these CPUs without the use of memory barrier
Memory barrier
Memory barrier, also known as membar or memory fence or fence instruction, is a type of barrier and a class of instruction which causes a central processing unit or compiler to enforce an ordering constraint on memory operations issued before and after the barrier instruction.CPUs employ...
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 flag[0] and flag[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
Loop-invariant code motion
In computer programming, loop-invariant code consists of statements or expressions which can be moved outside the body of a loop without affecting the semantics of the program...
. 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
Infinite loop
An infinite loop is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, having one that can never be met, or one that causes the loop to start over...
. If either of these transformations is performed, the algorithm will fail, regardless of architecture.
To alleviate this problem, volatile
Volatile variable
In computer programming, particularly in the C, C++, C#, and Java programming languages, a variable or object declared with the volatile keyword usually has special properties related to optimization and/or threading...
variables should be marked as modifiable outside the scope of the currently executing context. For example, in 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 barriers to guarantee in-order execution of that code. C++0x
C++0x
C++11, also formerly known as C++0x, is the name of the most recent iteration of the C++ programming language, replacing C++03, approved by the ISO as of 12 August 2011...
atomic variables can be used to guarantee the appropriate ordering requirements — by default, operations on atomic variables are sequentially consistent so if the flag 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
- Peterson's algorithmPeterson's algorithmPeterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary L. Peterson in 1981...
- Eisenberg McGuire algorithm
- Lamport's bakery algorithmLamport's bakery algorithmLamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion....