Dekker’s Algorithm

Used to implement Semaphore. Not used in practice because it is slow.

This approach has the advantage of illustrating many of the common bugs encountered in developing concurrent programs.

boolean flag [2];
int turn;
 
void P0() {
  while (true) {
    flag [0] = true;
    while (flag[1]) {
      if (turn == 1) {
        flag[0] = false;
        while (turn == 1) /* do nothing */;
        flag [0] = true;
      }
    }
    /* critical section */;
    turn = 1;
    flag [0] = false;
    /* remainder */;
  }
}
void P1() {
  while (true) {
    flag[1] = true;
    while (flag[0]) {
      if (turn == 0) {
        flag [1] = false;
        while (turn == 0) /* do nothing */;
        flag [1] = true;
      }
    }
    /* critical section */;
    turn = 0;
    flag [1] = false;
    /* remainder */;
  }
}
void main () {
  flag [0] = false;
  flag [1] = false;
  turn = 1;
  parbegin (P0, P1);
}

A better algorithm is Peterson’s Algorithm.