Semafoor (computer)

Een semafoor (ook: seinpaal) is een onderdeel van een synchronisatiemechanisme voor parallelle of gedistribueerde programma's ontworpen door Edsger Dijkstra.

Bij het ontwerp van gedistribueerde programma's is het normaal dat de verschillende subprogramma's binnen het hoofdprogramma op de een of andere manier rekening met elkaar moeten houden. Dat "rekening houden" kan betrekking hebben op het delen van geheugen of toegang tot andere hardware, of gewoon dat een programma moet wachten tot een ander programma een bepaald punt heeft bereikt in zijn code.

Beschouwen we het probleem van wederzijdse uitsluiting ("mutual exclusion"). Het probleem komt er in het kort op neer dat er een aantal programma's zijn in een gedistribueerd programma met de volgende vorm:

programma p:
|[
   KRITIEKE_SECTIE.p
  ;
   NIET_KRITIEKE_SECTIE.p
]|

Van al die programma's mag er ten hoogste één op ieder moment bezig zijn aan zijn kritieke sectie. Wat we dus willen dat die programma's doen, is dit:

Gedeeld: 
  variabele s : integer; {s houdt bij hoeveel programma's bezig zijn
                          aan hun kritieke sectie}
programma p:
|[
   if s = 0 then
      s := s + 1
     ;KRITIEKE_SECTIE.p
     s := s - 1
   else blokkeer_en_probeer_nogmaals
  ;
   NIET_KRITIEKE_SECTIE.p
]|

Natuurlijk moeten de controle van de waarde van s en de toekenningen aan s (de verhoging en verlaging van s) atomaire instructies zijn.

Als we nu het programma – om historische redenen – wat aanpassen, krijgen we het volgende:

Gedeeld: 
  variabele s : integer; {s houdt bij hoeveel programma's bezig zijn
                          aan hun kritieke sectie}
            r : integer; {r = 1 - s}

programma p:
|[
   if r > 0 {dan is s dus 0} then
      r, s := r - 1, s + 1
     ;KRITIEKE_SECTIE.p
      r, s := r + 1, s - 1
   else blokkeer_en_probeer_nogmaals
  ;
   NIET_KRITIEKE_SECTIE.p
]|

Nu heeft r de functie van s overgenomen in het bovenstaande programma: r bewaakt nu de uitsluitende toegang tot de kritieke secties van de verschillende programma's. We kunnen nu s uit het programma verwijderen. In het volgende programma geven we met gebroken haken stukken aan die atomair moeten zijn:

Gedeeld: 
            r : integer;

programma p:
|[
 < if r > 0 then
     r := r - 1 >
     ;KRITIEKE_SECTIE.p
     < r := r + 1 >
   else blokkeer_en_probeer_nogmaals
  ;
   NIET_KRITIEKE_SECTIE.p
]|

Nu vatten we een aantal dingen samen in een tweetal functies:

Functie P (Probeer of "Prolaag"), met argument x: if x > 0 then x := x - 1 else blokkeer_en_probeer_nogmaals
Functie V (Verhoog), met argument x: x := x + 1

"Prolaag" is een woord dat Dijkstra heeft bedacht en het betekent "probeer te verlagen".

We komen nu aan de laatste versie van het programma:

Gedeeld: 
            r : seinpaal;

programma p:
|[
      P(r)
     ;
      KRITIEKE_SECTIE.p
     ;
      V(r)
     ;
      NIET_KRITIEKE_SECTIE.p
]|

En zo komen we aan Dijkstra's seinpalen: natuurlijke getallen met atomaire operaties die de waarden van een seinpaal met één verhogen of verlagen, maar blokkeren als gepoogd wordt de seinpaal een waarde te geven lager dan 0.

Semaforen worden niet alleen gebruikt voor de wederzijdse uitsluiting van kritieke secties, maar ook voor andere synchronisatieproblemen zoals het producer-consumer-probleem. Hierbij geeft het ene programma gegevens door aan een ander programma, via een gedeelde buffer die niet onder of over mag lopen. Bij zulke toepassingen kunnen de semaforen ook een waarde hoger dan 1 hebben.

Geschiedenis

Dijkstra ontwikkelde zijn seinpalen in 1963, toen parallelle programma's een "hot item" begonnen te worden. Het was in die dagen een groot probleem om uitsluitende toegang tot onderdelen van programma's en computers te regelen, maar met de introductie van seinpalen verdween het probleem als sneeuw voor de zon.

Tegenwoordig zijn seinpalen een dergelijk gemeengoed binnen het gedistribueerd programmeren dat vrijwel iedere processor instructies bevat om seinpalen mee te implementeren. Seinpalen behoren ook tot de standaardfaciliteiten van besturingssystemen en zijn de basis voor vrijwel ieder synchronisatie-mechanisme dat binnen computers wordt toegepast (inclusief monitors).

Bronnen

EWD74 - PDF-bestand, HTML-bestand, waarin Dijkstra seinpalen introduceerde
On a Method of Multiprogramming (uit de serie Monographs in Computer Science) -- W.H.J. Feijen en A.J.M. van Gasteren, ISBN 038798870X, uitgeverij Springer-Verlag