Dekker's algorithm

Dekker's algorithm

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.[1] 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.

Contents

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 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, 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.

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[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.

Footnotes

  1. ^ E.W. Dijkstra, Cooperating Sequential Processes, manuscript, 1965. Retrieved 13. May, 2009.

See also


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Theodorus Dekker — Dr. Theodorus Jozef Dekker (born March 1 1927) is a Dutch mathematician.Dekker completed his Ph.D degree from the University of Amsterdam in 1958, with his paper Paradoxical decompositions of sets and spaces.Dekker invented an algorithm that… …   Wikipedia

  • Lamport's bakery algorithm — is a computer algorithm devised by computer scientist Dr. Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion. Nature of the problem In computer science, it… …   Wikipedia

  • Peterson'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 Peterson in 1981 at the University of… …   Wikipedia

  • Jenkins-Traub algorithm — The Jenkins Traub algorithm for polynomial zeros is a fast globally convergent iterative method. It has been described as practically a standard in black box polynomial root finders .Given a polynomial P ,:P(z)=sum {i=0}^na iz^{n i}, quad a… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Mutual exclusion — For the concept, see Mutually exclusive events. mutex redirects here. For the computer program object that negotiates mutual exclusion among threads, see lock (computer science). Mutual exclusion (often abbreviated to mutex) algorithms are used… …   Wikipedia

  • Communications protocol — For other senses of this word, see Protocol. A communications protocol is a system of digital message formats and rules for exchanging those messages in or between computing systems and in telecommunications. A protocol may have a formal… …   Wikipedia

  • Lock-free and wait-free algorithms — In contrast to algorithms that protect access to shared data with locks, lock free and wait free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. Lock free refers to the …   Wikipedia

  • Brent's method — In numerical analysis, Brent s method is a complicated but popular root finding algorithm combining the bisection method, the secant method and inverse quadratic interpolation. It has the reliability of bisection but it can be as quick as some of …   Wikipedia

  • Mixture model — See also: Mixture distribution In statistics, a mixture model is a probabilistic model for representing the presence of sub populations within an overall population, without requiring that an observed data set should identify the sub population… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”