Dekker algorithm

from Wikipedia, the free encyclopedia

The Dekker algorithm is the oldest known complete solution to the problem of ensuring mutual exclusion ( mutex ) in the decentralized control of processes ( process synchronization ). It avoids mutual blocking ( deadlock ) and ensures that exactly one process can always get into a critical section ( sequentialization ). The algorithm was formulated in 1965 by the Dutch mathematician Theodorus Dekker . In the form described here, however, it can only mutually exclude two processes.

Scheme

The algorithm can be described schematically with the following C code: 

  // globale Variablendeklaration
  boolean flag0 = false;
  boolean flag1 = false;
  int turn = 0;   // alternativ: turn = 1

  // Prozess 0
  p0: flag0 = true;
      while (flag1) {
          if (turn != 0) {
              flag0 = false;
              while (turn != 0) {
              }
              flag0 = true;
           }
      }

      // kritischer Abschnitt
      turn = 1;
      flag0 = false;

// Prozess 1
p1: flag1 = true;
    while (flag0) {
        if (turn != 1) {
            flag1 = false;
            while (turn != 1) {
            }
            flag1 = true;
        }
    }

    // kritischer Abschnitt
    turn = 0;
    flag1 = false;

functionality

The Dekker two-process algorithm works with three variables: two flags and one variable turn. There is exactly one flag for each process. A set flag (flag = true) signals that the associated process could be in the critical section, the variable turnacts as a kind of token.

The entry condition for the loop is the flag of the other process: If this is set, the other process is either in the critical area or also in the loop. If the latter is the case, the state of decides turnon the further course. If it contains turnthe number of the other process, its own flag is reset and it waits until it has turnthe number of its own process. This gives the other process the opportunity to leave the loop (if it was in it) and get into the critical section.

After the critical section of the other process, turnthe number of its own process is set and the flag of the other process is reset. This allows your own process to leave both queues and reach its critical section.

example 

-> '''turn''' wird mit 0 initialisiert.
-> Prozess #0 bekommt den Prozessor: flag0 = true;
-> Prozess #1 bekommt den Prozessor: flag1 = true;
-> Prozess #0 bekommt den Prozessor: Eintritt in die Schleife
-> Prozess #1 bekommt den Prozessor: Eintritt in die Schleife
-> Prozess #0 bekommt den Prozessor: Die Bedingung turn != 0 wird nicht erfüllt
-> Prozess #1 bekommt den Prozessor: Die Bedingung turn != 1 wird erfüllt
-> Prozess #0 bekommt den Prozessor: Erneuter Eintritt in die Schleife, da flag1 gesetzt
-> Prozess #1 bekommt den Prozessor: flag1 = false;
-> Prozess #0 bekommt den Prozessor: Die Bedingung turn != 0 wird nicht erfüllt
-> Prozess #1 bekommt den Prozessor: Die Bedingung turn != 1 wird erfüllt
-> Prozess #0 bekommt den Prozessor: Eintritt in den kritischen Abschnitt, da flag1 nicht gesetzt
-> Prozess #0 bekommt den Prozessor: turn = 1;
-> Prozess #1 bekommt den Prozessor: flag1 = true;
-> Prozess #0 bekommt den Prozessor: flag0 = false;
-> Prozess #1 bekommt den Prozessor: Die Bedingung turn != 1 wird nicht erfüllt
-> Prozess #0 bekommt den Prozessor: Rücksprung zu Marke P0, flag0 = true
-> Prozess #1 bekommt den Prozessor: Eintritt in den kritischen Abschnitt, da flag0 nicht gesetzt
-> Prozess #0 bekommt den Prozessor: Eintritt in die Schleife
-> Prozess #1 bekommt den Prozessor: turn = 0;
-> Prozess #0 bekommt den Prozessor: Die Bedingung turn != 0 wird nicht erfüllt
-> Prozess #1 bekommt den Prozessor: flag1 = false;
-> Prozess #0 bekommt den Prozessor: Eintritt in den kritischen Abschnitt, da flag1 nicht gesetzt, turn = 1;
-> Prozess #1 bekommt den Prozessor: Rücksprung zu Marke P1, flag1 = true

meaning

In contrast to previously found solutions for decentralized control, the Dekker algorithm works turncorrectly because of the variable even when the scheduling jumps back and forth between the two processes. A generalized solution for the synchronization of N processes was also found in 1965 by Edsger W. Dijkstra . A simplification can be found in the Peterson algorithm , which also works correctly, but which was only developed 16 years later. The disadvantage of the decentralized control remains: Waiting processes do not give up the processor , but rather use it with busy waiting .

Individual evidence

  1. ^ EW Dijkstra: "Cooperating sequential processes", Technological University, Eindhoven, The Netherlands, September 1965
  2. ^ Joe Duffy, "Concurrent Programming on Windows," Addison-Wesley Professional, 2008
  3. ↑ Sibsankar Haldar: "Operating Systems", self-published 2015, p. 218
  4. ^ EW Dijkstra: "Solution of a Problem in Concurrent Programming Control", Communications of the ACM, Volume 8 Issue 9, 1965, p. 569