36 - Semafory, vlastnosti a typické použití (binární, obecné)

Question 1

Semafor Obecně

Answer 1

Synchronizační nástroj poskytovaný operačním systémem

• Nepotřebuje aktivní čekání
• Nejjednodušší implementace je struktura:

type semaphore = record
count: integer;
queue: list of process
end;

var S: semaphore;

Question 2

Binární semafor

Answer 2

= zámek střežící kritickou sekci. Pouze dvě hodnoty zamčeno/odemčeno

• Operace init(), lock() a unlock().
• Nelze číst jeho hodnotu (nemá smysl, mohla by se změnit potom).
• Pasivní čekání ve funkci lock().
• Operace lock() a unlock() jsou atomické.
• > Odemykat může i jiný proces než ten, co zamknul (předávání zámku).
• > Mutex = speciální binární semafor pro vzájemné vyloučení, který nelze předávat (pouze vlastník ho může odemknout)
• Silný/slabý semafor - nemá/má stárnutí
• !!! Majitel zámku !!!

Použití:

pro vzájemné vyloučení:

init(sem, 0);  /* volný */ 
while (1) { 
 lock(sem);       ENTRY
 kritická sekce 
 unlock(sem);      EXIT
 výpočet 
}

pro signalizaci událostí (nevhodné) - co když se provede unlock vícekrát? - ztratí se signalizace:

init(sem, 1); /* zamčený /
P1: P2:
… unlock(sem);
lock(sem); / čeká až P2 provede unlock() */

Question 3

Obecný semafor

Answer 3

• Počáteční hodnota určuje „kapacitu“ semaforu – kolik jednotek zdroje chráněného semaforem je k dispozici
• Jakmile se operací down() zdroj vyčerpá (hodnota je 0), jsou další operace down() blokující, dokud se operací up() nějaká jednotka zdroje neuvolní
• Operace init(v) - inicializace semaforu sem na hodnotu v>=0
• Operace down() - zamčení, atomická operace čekání na hodnotu > 0 a pak zmenšení o 1, potom může pokračovat.
• Operace up() - odemčení, zvýší hodnotu o 1 a tím případně odblokuje další proces.

Používá pasivní čekání ve funkci down().

Variantní definice (povoluje zápornou hodnotu):

• down() - zmenšení hodnoty o 1, pokud je hodnota < 0, čekání
• up() - zvětšení hodnoty o 1, pokud je hodnota <= 0, odblokování čekajícího procesu
• Binární semafor lze simulovat dvěma číselnými se sdílenými proměnnými; obecný lze simulovat třemi binárními a sdílenou hodnotou

Implementace:
down(S):
   S.count--;
   if (S.count<0) {
     block this process
     place this process in S.queue
   }

 up(S):
   S.count++;
   if (S.count<=0) {
     remove a process P from S.queue
     place this process P on ready list
   }

Použití:
- hlídání zdroje s definovanou kapacitou N

init(sem, N);
Pi:
down(sem); /* pokud je volno, pokračujeme dále /
… / nejedná se o kritickou sekci,
je zde až N procesů současně! /
up(sem); / uvolníme místo */

• pro signalizaci událostí (udrží i počet neobsloužených, oproti binárnímu semaforu bezpečné, žádná událost se nemůže ztratit)

init(sem, 0);
P1: P2:
… up(sem);
down(sem); /* čeká až P2 provede up() */

pro vzájemné vyloučení - nepoužívat, důvody (vychází z toho že nevíme kdo zamyká + INVERZE PRIORITY):

• inverze priority při zamykání (nelze řešit).
• rekurzivní deadlock – co když zamkne zámek ten samý proces, který už ho má zamčený? U binárního zámku lze detekovat (je majitel zámku), u obecného nelze detekovat (z definice může kdokoli dělat libovolně krát operaci down())
• deadlock při ukončení procesu – co když proces, který má zámek zamčen, skončí bez uvolnění zámku? U binárního lze detekovat a řešit, u obecného nelze (není řečeno, kdo v případě zablokovaného semaforu provede operaci up(), může to být kterýkoli jiný proces).
• náhodné uvolnění – co když se operace down() ztratí? Obecný semafor pak pustí příště dva procesy do kritické sekce, u binárního semaforu se nic nestane.

Question 4

Problémy implementace semaforů

Answer 4

v UNIXových systémech semafor není, používá se monitor. Obecně je implementován pomocí spinlocku a testování hodnoty čítače. Pozastavené procesy se přidávají na konec fronty.

Rekurzivní binární semafor - přidá se k binárnímu semaforu čítač, který se inkrementuje v případě zamykání stejným procesem

• řeší problém pokud se v rámci funkce volá jiná funkce a obě zamykají semafor -> implementováno jako čítač rekurze
• pokud zámek zamkl stejný proces tak se pouze mění tento čítač a ne zámek
• semafor může být odemknut pouze pokud je hodnota čítače rovna nule

Implementace na úrovní už. režimu

• jako služba jádra je pomalé
• nelze použít aktivní čekání
• Řešení: jednoduchý zámek na uživatelské úrovni plus pasivní čekání na změnu hodnoty v jádře

Inverze priority - proces s nižší prioritou blokuje proces s vyšší prioritou
- formálně: Proces s vyšší prioritou (h) nemůže vstoupit do kritické sekce, protože je v kritické sekci proces s nižší prioritou (l) a neběží, protože jsou v systému procesy s prioritou p > l (pokud p < h, jedná se o inverzi priority těchto procesů proti h)

řešení (není možné u obecného semaforu, protože nevíme kdo vlastní)
!!! dědění priority (priority inheritance) - po dobu provádění KS je priorita prováděného procesu zvýšena na max. prioritu všech čekajících procesů
- - pozitivum: pokud žádný proces nečeká, zůstává priorita procesu v kritické sekci nezměněná (neovlivňuje chování systému)
- - negativum: musí se dynamicky upravovat při každém blokujícím zamčení

!!! horní mez priority (priority ceiling) - po dobu provádění KS je prováděnému procesu nastavena statická priorita

• • pozitivum: pevně deklarovaná priorita je jednoduchá na implementaci,
• • negativum: procesu se musí zvyšovat priorita vždy (i když to není nutné)

Question 5

Použití semaforů

Answer 5

Použití semaforů řeší výlučný přístup do kritické sekce:
 Process Pi:
 repeat
   down(S);
     CriticalSection
   up(S);
     RemainderSection
 forever

Bariéra = místo, na kterém čekají procesy, dokud se nesejdou všechny.

• typické u paralelních algoritmů
• čítač s počátečním stavem N (počet procesů), proces v bariéře dekrementuje čítač a čeká, až se čítač posune na 0 proces pokračují dále