Semaforji

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Vsebina

1. Uvod

Semaforji so sinhronizacijsko orodje in klasična metoda za zaklepanje in pravilno deljenje virov med različnimi procesi v večprocesnem okolju. Uporabljajo se predvsem za reševanje problema kritične sekcije pri bolj kompleksnih sistemih oz. problemih. Semafor je celoštevilčna spremenljivka, katero lahko spreminjano samo preko dveh atomarnih operacij: wait(S) in signal(S).

Definicija wait(S)


Definicija signal(S) 


wait(S) {
  while (S<=0)
  ; //no- operation
  S--;
}

signal(S) {
  S++;
}

Ko nek proces spremeni vrednost semaforja, ne sme noben drug proces spreminjati te vrednosti. Enako velja za operacije wait(S) in signal(S), ki morajo biti atomarne – nedeljive, še posebej ko se izvaja operacija S-- ali S++.

Semaforje je leta 1965 izumil Nizozemec Edsger Dijkstra, zato so bile operacije nad semaforji v osnovi poimenovane s črkama P za operacijo wait(S) oz. down(S) (v nizozemščini »proberen« - testirati) in V za operacijo signal(S) oz. up(s) (v nizozemščini »verhogen« - inkrementirati).

2. Uporaba semaforjev

  • Semaforje lahko uporabimo pri reševanju problema kritičnih sekcij z več – n procesi. Ideja je v temu, da si procesi delijo semafor mutex (mutual exclusions), ki ima začetno vrednost 1. Njegov namen je ščiti del kode, ki ga hkrati ne moreta izvajati dva procesa. Vsak proces Pi je organiziran kot kaže spodnja koda: 
do {
   wait(mutex);'
           kritična sekcija
   signal(mutex);
           preostala sekcija
} while (1);
  • Semaforje uporabljamo tudi za sinhronizacijo poteka dveh procesov, kjer zahtevamo, da se en proces konča preden začne drugi izvajati svoje operacije (npr. generiranje povzetka). Procesi si delijo semafor synch (synchronization), kot je prikazano spodaj: 
 ...
S1;  //operacija procesa P1
signal(synch);
 ...
wait(synch);
S2;  //operacija procesa P2
 ...
V zgornjem primeru smo zahtevali, da se je operacija S1 iz procesa P1 končala preden se je začela izvajati operacija S2 procesa P2.

3. Implementacija semaforjev

Glavna pomanjkljivost v primeru reševanja kritičnih sekcij z algoritmi in prikazanem primeru s semaforjem mutex je to, da zahtevajo nekoristno čakanje (busy waiting). Ko se nek proces nahaja v svoji kritični sekciji in ostali procesi čakajo na vstop v svojo kritično sekcijo, morajo čakajoči procesi izvajati zanko čakanja (loop) v svoji vstopni sekciji. Neprestano čakanje v svoji vstopni sekciji je velik problem pri ealnem večopravilnem sistemu, kjer si en procesor deli več procesov.

Nekoristno čakanje zapravlja cikle (čas) procesorja, medtem, ko bi lahko ta čas s pridom izkoristili čakajoči procesi. Taka uporaba semaforja se imenuje tudi krožni semafor (spinlock).

Da odpravimo nekoristno čakanje spremenimo definicijo wait(S) in signal(S) operacije semaforja. Ko proces izvaja wait(S) operacijo in ugotovi, da vrednost semaforja ni pozitivna mora čakati. Raje kot nekoristno čakanje (obremenjevanje procesorja z loop operacijo), proces blokira samega sebe.

Blok operacija (block operation) prestavi proces iz pripravljene vrste v čakalno vrsto – (status procesa se spremeni v čakajoč!). Nato se kontrola prenese na razvrščevalnik procesorja, ki izbere naslednji proces v pripravljeni vrsti in ga dodeli procesorju – ni nekoristnega čakanja!! Proces, ki je blokiran v čakalni vrsti in čaka na semafor S mora biti ponovno zagnan, ko drug proces izvede signal(S) operacijo. Proces se ponovno zažene in se prestavi iz čakalne vrste v pripravljeno vrsto z operacijo zbudi (wakeup operation).

Block.jpg

Po tej definiciji lahko definiramo semafor kot semafor, ki vsebuje celoštevilčno vrednost in seznam procesov. 

typedef struct {
   int vrednost;
   struct process *L;
 } semaphore;

Ko proces čaka na semafor, je proces zapisan na seznamu procesov. Operacija signal(S) prenese en proces iz čakalne vrste in ta proces zbudi.

wait semafor definiramo z: 

void wait(semaphore S){
   S.value--;
   if (S.value<0) {
       dodaj ta proces v S.L (seznam procesov);
       block();
   }
}

signal semafor definiramo z: 

void signal(semaphore S){
    S.value++;
    if (S.value<=0) {
       odstrani proces P iz S.L (seznama procesov);
       wakeup(P);
   }
}

Operacija block() začasno ustavi proces, ki je zaprosil za izvajanje kritične sekcije in ga postavi v čakajočo vrsto. Operacija wakeup(P) nadaljuje prekinjeno izvajanje začasno ustaljenega procesa in ga postavi v pripravljeno vrsto. Ti dve operaciji izvede operacijski sistem preko sistemskega klica.  

Pri tej implementaciji semaforja je vrednost semaforja lahko negativna, kar pri prejšnjem primeru ne mora biti. Velikost negativne številke predstavlja število čakajočih procesov na semafor. Seznam čakajočih procesov na semafor lahko enostavno izvedemo s povezanim poljem v PCB. Vsak semafor vsebuje celoštevilsko vrednost in kazalec na seznam procesov v čakalni vrsti. Procesi se praznijo iz čakalne vrste po načelu FIFO (First In First Out).

 

Kritični pogled na semaforje je ta, da izvaja operaciji wait(S) in signal(S) atomarno - nedeljivo. Zagotoviti moramo, da ne pride do tega, da bi dva procesa izvedla wait(S) in signal(S) operacijo na istem semaforju istočasno. Ta problem je problem kritičnih sekcij in ga lahko rešimo na dva načina:

  • v enoprocesorskem sistemu lahko preko prekinitve zagotovimo, da se izvaja samo wait(S) ali samo signal(S) operacija. Tak pristop deluje samo v enoprocesorskem sistemu, ker ko enkrat pride do prekinitve, se instrukcije drugih procesov ne morejo izvajati. Izvaja se lahko samo trenutni proces, dokler prekinitve niso ponovno vzpostavljene in razvrščevalnik zopet pridobi kontrolo.
  • v večprocesorskem sistemu zadrževanje z prekinitvami ne deluje. Ukazi drugih procesov, ki tečejo na drugih procesorjih lahko vskočijo v nekem zaporedju. Če strojna oprema ne dopušča kakšne posebne instrukcije si moramo pomagati z programskimi rešitvami - algoritmi, ki smo jih prej omenili.

4. Smrtni objemi

Implementacija semaforjev in čakalne vrste lahko pripelje do situacije, kjer dva ali več procesov nedoločeno čakajo na dogodek, ki ga lahko sproži eden od čakajočih procesov. Dogodek bi tule bil operacija signal(), ki da signal naslednjemu procesu, da lahko vstopi v svojo kritično sekcijo. Ko pridemo do te situacije pravimo da so procesi v smrtnem objemu (deadlock). Primer smrtnega objema kaže naslednji zgled:

 

P0

P1

 
wait(S);
wait(Q);
...
signal(S);
signal(Q);
 

wait(Q);
wait(S);
...
signal(Q);
signal(S);

 

Proces P0 izvaja wait(S) in nato P1 izvede wait(Q). Ko P0 izvede wait(Q) mora čakati dokler P1 ne izvede signal(Q). Enako velja obratno, ko P1 izvaja wait(S), mora počakati P0 da izvede signal(S). Ker eden čaka na drugega sta procesa P1 in P0 v smrtnem objemu.

5. Binarni semaforji

Prej omenjen semafor je števni semafor, ker se njegova celoštevilčna spremenljivka giba v neomejenih mejah. Pri binarnem semaforju pa lahko zavzame samo dve vrednosti (0,1). Uporablja se za kontrolo dostopa do enega samega vira.

Kako lahko števni semafor predstavimo z binarnim semaforjem?

Naj bo S števni semafor. Potrebujemo naslednje podatkovne strukture:   

binarni-semafor S1, S2;
int C;
S1=1, S2=0, C=1;  //začetne vrednosti

  wait operacijo definiramo z: 

wait(S1);
C--;
if (C<0){
    signal(S1);
    wait(S2);
}
signal(S1);
 

signal operacijo definiramo z : 

wait(S1);
C++;
if (C<=0){
    signal(S2);
    wait(S2);
}
else
    signal(S1);


6. Grafični primer semaforja na primeru vlaka

SemaphoreExample.png


7. Povezave

dostopno 10. 01. 2006

Vzpostavljeno iz »http://www.e-studij.si/Semaforji«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja