36 - Semafory, vlastnosti a typické použití (binární, obecné) Flashcards
Semafor Obecně
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;
Binární semafor
= 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() */
Obecný semafor
- 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.
Problémy implementace semaforů
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é)
Použití semaforů
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