Petersons algoritme

Den Peterson algoritme (også kjent som de kanadiske prosesser) er en løsning av problemet med gjensidig utelukkelse ( mutex ) i desentralisert styring av prosesser ( prosess synkronisering ). Den ble formulert i 1981 av Gary L. Peterson og sørger for at bare en prosess noen gang kan nå en kritisk del ( sekvensialisering ). I skjemaet som er beskrevet her, kan det bare utelukke to prosesser gjensidig.

Flytskjema

I C- kode kan Petersons algoritme vises som følger:

#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
}

funksjonalitet

Før du går inn i en kritisk region, ringer hver prosess enter_region(int process)med sitt eget prosessnummer, 0 eller 1, som parameter. Inntreden i den kritiske regionen blir dermed forsinket til den er trygg. Så snart en prosess forlater den kritiske regionen, kaller den opp leave_region(int process)med sitt eget prosessnummer som parameter. En annen prosess kan nå komme inn i den kritiske regionen hvis den ønsker det.

eksempel 1

  1. Det er ingen prosess i den kritiske regionen.
  2. Prosessen med prosessnummer 0 ringer enter_region(int process)med prosessnummer 0 som parameter.
  3. Ved å angi interested[process] = TRUEhvor process = 0, viser denne prosessen sin interesse i å komme inn i den kritiske regionen.
  4. Han turn = othergir den andre prosessen muligheten til å komme inn i den kritiske regionen hvis den er interessert.
  5. Siden prosessen med prosess nummer 1 ikke er interessert i å komme inn i den kritiske regionen, returnerer funksjonen umiddelbart enter_region(int process)uten å utføre whilesløyfen. Prosessen med prosessnummer 0 kommer dermed inn i den kritiske regionen.
  6. Hvis prosessen med prosess nummer 1 nå uttrykker interesse for å komme inn i den kritiske regionen, må den vente til prosessen med prosessnummer 0 leave_region(int process)ringer med sitt eget prosessnummer som parameter for å forlate den kritiske regionen.

Eksempel 2

  1. To prosesser kaller nesten samtidig enter_region(int process)med prosessnumrene som parametere. Begge komponentene i interestedmatrisen er dermed satt til SANT.
  2. En av de to prosessene (la oss si prosessen med prosess nummer 1) lagrer verdien av variabelen turnsist og setter den dermed til 0 ( turn = other).
  3. Prosessen med prosessnummer 0 whileutfører derfor ikke sløyfen og returnerer umiddelbart.
  4. Prosessen med prosessnummer 0 kommer inn i den kritiske regionen.
  5. Prosessen med prosess nummer 1 må nå vente fordi begge er satt interested[other]til SANT og turn = other. Den venter til prosessen med prosessnummer 0 har leave_region(int process)ringt, interestedsetter komponenten tilbake til FALSE, og har dermed forlatt den kritiske regionen igjen.

betydning

Peterson-algoritmen er enklere enn Dekker-algoritmen , som også løser det gjensidige ekskluderingsproblemet. Likevel arver den den vesentlige ulempen med den desentraliserte kontrollen: Venteprosesser gir ikke opp prosessoren , men krever heller gjennom aktiv venting .

En algoritme som Peterson-algoritmen brukes faktisk bare til å implementere gjensidig ekskludering på et datasystem med to prosessorer som ikke har noen instruksjoner som test-og-sett eller sammenlign-og-bytt . Dagens prosessorer har vanligvis dette. På et høyt nivå språk brukes bare eksisterende språkelementer som semaforer eller metoder og instruksjonssekvenser som er erklært som "synkronisert". Dette har fordelen at en ventende tråd blokkerer, dvs. H. frigjør prosessoren for andre oppgaver.

Det er mulig å generalisere Petersons algoritme slik at problemet med gjensidig utelukkelse av n parallelle prosesser kan løses.

Se også

Individuelle bevis

  1. ^ GL Peterson: "Myter om det gjensidige utelukkelsesproblemet", Informasjonsbehandling Letters 12 (3) 1981, 115-116
  2. ↑ Andrew S. Tanenbaum : Modern Operating Systems . 3. oppdaterte utgave. Pearson Studies, ISBN 978-3-8273-7342-7