Note
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 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 barriers.
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 and flag 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++11 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.
Read more about this topic: Dekker's Algorithm
Famous quotes containing the word note:
“In his very rejection of art Walt Whitman is an artist. He tried to produce a certain effect by certain means and he succeeded.... He stands apart, and the chief value of his work is in its prophecy, not in its performance. He has begun a prelude to larger themes. He is the herald to a new era. As a man he is the precursor of a fresh type. He is a factor in the heroic and spiritual evolution of the human being. If Poetry has passed him by, Philosophy will take note of him.”
—Oscar Wilde (1854–1900)
“Is whispering nothing?
Is leaning cheek to cheek? Is meeting noses?
Kissing with inside lip? Stopping the career
Of laughter with a sigh?—a note infallible
Of breaking honesty.”
—William Shakespeare (1564–1616)
“What is line? It is life. A line must live at each point along its course in such a way that the artist’s presence makes itself felt above that of the model.... With the writer, line takes precedence over form and content. It runs through the words he assembles. It strikes a continuous note unperceived by ear or eye. It is, in a way, the soul’s style, and if the line ceases to have a life of its own, if it only describes an arabesque, the soul is missing and the writing dies.”
—Jean Cocteau (1889–1963)