Semaforji

Za reševanje problemov sinhronizacije sočasnih procesov je Dijkstra uvedel koncept semaforjev in takoimenovanih operacij P in V. Oznake teh operacij izhajajo iz holandskih besedic vhod in izhod. Semafor je ščitena spremenljivka (pravzaprav podatkovna struktura), ki jo lahko inicializiramo ter doseľemo le z operacijami P in V. Binarni semaforji lahko zavzamejo le vrednosti 0 in 1, Števni semaforji pa poljubne nenegativne vrednosti.

Operacijo P na semaforju S zapiąemo kot P(S) in deluje tako:

if S>0
    then S:= S-1
    else (* pocakaj na S v ustrezni vrsti *);

Operacijo V na semaforju S pa zapiąemo kot V(S) in deluje tako

if (* eden ali vec procesov caka v vrsti  na S *)
    then (* naj vstopi en proces *)
else S:=S+1;

Procesi naj čakajo na zaključek P(S) v čakalni vrsti tipa FIFO (first in - first out). Zato je vsak semafor podatkovna struktura, ki vsebuje en integer in eno vrsto.

V literaturi označujejo operaciji P(S) in V(S) tudi z imeni wait(semaphore) in signal(semaphore), ki imata v bistvu enak pomen.

Operaciji P in V morata biti nedeljivi. Same konkretne implementacije semaforjev so lahko različne. Če imamo na voljo instrukcije tipa test-and-set, jih uporabimo, sicer pa ne dovolimo prekinitev (disable interrupts) med samim izvajanjem operacij wait in signal.

Demonstracija semaforjev Java in semaforji

Sinhronizacija procesov s semaforji

Naslednji zgled uporabe semaforjev je sinhronizacija procesov. Vzemimo za primer vhodno-izhodne računalniške operacije. Proces, ki sproži vhodno-izhodno operacijo, se običajno sam blokira , da bi tako počakal na njen zaključek. Blokirani proces kasneje obudi nek dogodek v nekem drugem procesu. Pri taki interakciji imamo torej protokol blokiranje- bujenje. Ta je uporaben, kadarkoli želimo nek proces sinhronizirati z danim dogodkom v drugem procesu:

program sinhronizacija;
var dogodek:semaphore;
procedure process_A;
begin
  (*..predhodne operacije...*)
  wait(dogodek); (* proces_A caka na dogodek v procesu B *)
  (*...nadaljevanje procesa...*)
end;

procedure process_B;
begin
  (*...predhodne operacije ..*)
  signal(dogodek);
  (*..nadaljevanje procesa..*)
end;


begin
  initSemaphore(dogodek,0);
  parbegin
    process_A;
    process_B;
  parend;
end.

Primer: Speči brivec

Semaforji in problem proizvajalec - porabnik

Oglejmo si še uporabnost semaforjev za reševanje problema proizvajalec - porabnik. Proces A tvori podatke, ki jih proces B uporablja. Hitrost izvajanja posameznih procesov A in B se v splošnem ne ujema. Zagotoviti moramo, da ne prihaja niti do izgube podatkov niti do večkratnega branja in izpisa istega podatka. Oba procesa moramo torej sinhronizirati, kot to kaže naslednji zgled:

program proizvajalec_porabnik;
var zasedeno:semaphore;
    vpisano:semaphore;
    buffer: integer;

procedure proizvajalec;
var rezultat: integer;
begin
  repeat
    racunaj(rezultat);
    wait(zasedeno);  (* vstop v kriticno sekcijo *)
    buffer:=rezultat;
    signal(vpisano);  (* sinhronizacija *)
    signal(zasedeno); (* sprostitev kriticne sekcije *)
  until FALSE;
end;

procedure porabnik;
var podatek:integer;
begin
  repeat
     wait(vpisano); (* blokiran proces, ce podatka se ni *)
     wait(zasedeno);  (* vstop v kriticno sekcijo *)
    podatek:=buffer;
    signal(zasedeno);  (* sprostitev kriticne sekcije *)
    izpis(podatek);
  until FALSE;
end;

begin
  initSemaphore(zasedeno,1);
  initSemaphore(vpisano,0);
  parbegin
    proizvajalec;
    porabnik;
  parend;
end.

Števni semaforji

Števne semaforje s pridom uporabimo, če želimo alokacijo enega sredstva (resource) iz zaloge enakih sredstev. Semafor inicializiramo na število sredstev v zalogi. vsaka operacija P (oziroma wait) zmanjša semafor za 1 in tako pokaže, da se je zaloga zmanjšala. Vsaka operacija V (oziroma signal) poveča semafor za 1 in tako nakaže povečanje zaloge za 1. Če uporabimo operacijo wait potem, ko je semafor dosegel 0, mora tak proces počakati, da se vsaj eno sredstvo sprosti z ustrezno operacijo signal.

Semaforji so zelo primitivni in z njimi težko izrazimo zelo kompleksne konkurenčne probleme. Tako si težko zapomnimo, kateri ščiteni strukturi smo priredili dani semafor. Mimogrede pozabimo uporabiti kakšno instrukcijo wait in prezgodaj vstopimo v kritično sekcijo. Procesi lahko tudi ostanejo neomejeno blokirani, ker (morda zaman) čakajo na odrešilno operacijo signal, ki bi jo moral uporabiti nek drug proces.

Ali Java pozna semaforje
Primeri s semaforji v Javi
Primer števnega semaforja