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

1
Q

Semafor Obecně

A

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;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Binární semafor

A

= 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() */

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Obecný semafor

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Problémy implementace semaforů

A

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é)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Použití semaforů

A
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly