Peterson's algorithm

from Wikipedia, the free encyclopedia

The Peterson's algorithm (also known as the Canadian processes) is a solution of the problem of mutual exclusion ( mutex ) in the decentralized control of processes ( process synchronization ). It was formulated in 1981 by Gary L. Peterson and ensures that only one process can ever get into a critical section ( sequentialization ). In the form described here, it can only mutually exclude 2 processes.

Flowchart

In C code, Peterson's algorithm can be represented as follows: 

#define FALSE 0
#define TRUE 1
#define N 2 // Anzahl der Prozesse

volatile int turn; // Gibt an, wer gerade an der Reihe ist
volatile int interested[N]; // Alle Werte mit 0 (FALSE) initialisieren

void enter_region(int process)
{
  int other; // Prozessnummer des anderen Prozesses
  other = 1 - process; // Der andere Prozess
  interested[process] = TRUE; // Interesse zeigen
  turn = other; // Flag setzen

  while (interested[other] == TRUE && turn == other) ; // Leeranweisung (Aktives Warten)
}

void leave_region(int process) // Prozess, der die kritische Region verlässt
{
  interested[process] = FALSE; // Zeigt den Ausstieg aus dem kritischen Bereich an
}

functionality

Before entering a critical region, each process calls enter_region(int process)with its own process number, 0 or 1, as a parameter. Entry into the critical region is delayed until it is safe. As soon as a process leaves the critical region, it calls up leave_region(int process)with its own process number as a parameter. Another process can now enter the critical region if it so wishes.

example 1

  1. There is no process in the critical region.
  2. The process with process number 0 calls enter_region(int process)with its process number 0 as a parameter.
  3. By setting interested[process] = TRUE, where process = 0, this process shows its interest in entering the critical region.
  4. He turn = othergives the other process the opportunity to enter the critical region if interested.
  5. Since the process with process number 1 is not interested in entering the critical region, the function returns immediately enter_region(int process)without executing the whileloop. The process with process number 0 thus enters the critical region.
  6. If the process with process number 1 now expresses interest in entering the critical region, it must wait until the process with process number 0 leave_region(int process)calls with its own process number as a parameter in order to leave the critical region.

Example 2

  1. Two processes call almost simultaneously enter_region(int process)with their process numbers as parameters. Both components of the interestedarray are thus set to TRUE.
  2. One of the two processes (let's say the process with process number 1) saves the value of the variable turnlast and thus sets it to 0 ( turn = other).
  3. The process with process number 0 therefore whiledoes not execute the loop and returns immediately.
  4. The process with process number 0 enters the critical region.
  5. The process with process number 1 now has to wait because both are set interested[other]to TRUE and turn = other. It waits until the process with process number 0 has leave_region(int process)called, interestedsets its component back to FALSE, and has thus left the critical region again.

meaning

The Peterson algorithm is simpler than the Dekker algorithm , which also solves the mutual exclusion problem. Nevertheless, it inherits the significant disadvantage of the decentralized control: Waiting processes do not give up the processor , but rather demand it through active waiting .

An algorithm such as the Peterson algorithm is actually only used to implement mutual exclusion on a computer system with two processors that have no instructions such as test-and-set or compare-and-swap . Today's processors usually have this. In a high-level language, only existing language elements such as semaphores or methods and instruction sequences that are declared as "synchronized" are used. This has the advantage that a waiting thread blocks, i.e. H. releases the processor for other tasks.

It is possible to generalize Peterson's algorithm so that the problem of the mutual exclusion of n parallel processes can be solved.

See also

Individual evidence

  1. ^ GL Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12 (3) 1981, 115-116
  2. ↑ Andrew S. Tanenbaum : Modern Operating Systems . 3rd, updated edition. Pearson Studies, ISBN 978-3-8273-7342-7