Dekker's algorithm

The Dekker algorithm (after Theodorus Dekker ) is like the Peterson algorithm a complete solution of the problem, the mutual exclusion ( mutex ) in the decentralized control of processes to ensure ( process synchronization). He avoids mutual blocking ( deadlock ) and ensures that there is always exactly can get a process in a critical section ( sequencing ).

Scheme

The algorithm can be described by the following C- code schematically:

/ / Global variable declaration    FLAG0 boolean = false;    boolean flag1 = false;    int turn = 0; / / Alternatively: turn = 1    / / Process 0    p0: FLAG0 = true;        while ( flag1 ) {            if ( turn! = 0) {                FLAG0 = false;                while ( turn! = 0) {                }                FLAG0 = true;             }        }          / / Critical section        turn = 1;        FLAG0 = false; / / Process 1 p1: flag1 = true;      while ( FLAG0 ) {          if ( turn! = 1) {              flag1 = false;              while ( turn! = 1) {              }              flag1 = true;          }      }        / / Critical section      turn = 0;      flag1 = false; operation

The Dekker algorithm for two processes uses three variables: two flags and a variable turn. For each process, there is exactly one flag. A set flag ( flag = true ) indicates that the associated process could be located in the critical section, the variable turn acts 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 located in the critical area or also in the loop. Should the latter be the case, decided by the state of turn about the further course. Contains the turn number of the other process, the own flag is reset and waits until the number of the turn has its own process. So that the other process has the opportunity to leave the loop (if it was located in it) and to enter the critical section.

After the critical section of the other process turn is set to the number of own process and the flag of the other process is reset. This allows the own process of trust for both queues and enter its critical section.

Example

- >'' 'Turn ''' is initialized to 0. - > Process # 0 gets the processor: FLAG0 = true; - > Process # 1 gets the processor: flag1 = true; - > Process # 0 gets the processor: entering the loop - > Process # 1 gets the processor: entering the loop! - > Process # 0 gets the processor: The condition turn = 0 is not satisfied - > Process # 1 gets the processor: The condition turn = 1 is fulfilled! - > Process # 0 gets the processor: Another entry into the loop, as set flag1 - > Process # 1 gets the processor: flag1 = false;! - > Process # 0 gets the processor: The condition turn = 0 is not satisfied - > Process # 1 gets the processor: The condition turn = 1 is fulfilled! -> Process gets the processor # 0: entry into the critical section, as flag1 not set -> Process gets the processor # 0: turn = 1; - > Process # 1 gets the processor: flag1 = true; - > Process # 0 gets the processor: FLAG0 = false;! - > Process # 1 gets the processor: The condition turn = 1 is not satisfied -> Process gets the processor # 0: Return to brand P0, FLAG0 = true - > Process # 1 gets the processor: entry into the critical section, since FLAG0 not set - > Process # 0 gets the processor: entering the loop - > Process # 1 gets the processor: turn = 0;! - > Process # 0 gets the processor: The condition turn = 0 is not satisfied - > Process # 1 gets the processor: flag1 = false; -> Process gets the processor # 0: entry into the critical section, as flag1 not set, turn = 1; - > Process # 1 gets the processor: Return to brand P1, flag1 = true importance

Unlike other solutions for decentralized control of the Dekker algorithm works because of the variable and then turn correctly when scheduling alternately jumps between the two processes back and forth. A simplification can be found in Peterson also correctly working algorithm. The disadvantage of the decentralized control remains: Waiting processes do not give up the processor, but claim it through busy waiting.

  • Algorithm
  • Operating system theory
Synchronization (computer science)
225873
de