Semafor (synchronizace)

Semafor je v informatice široce používané synchronizační primitivum, které obsahuje celočíselný čítač. Semafor se využívá zejména jako ochrana proti souběhu tím, že chrání přístup do kritické sekce, k čemuž používá dvojici operací V (up) a P (down). Je tak zobecněním instrukce TSL, která používá proměnnou typu boolean. Semafory poprvé popsal nizozemský informatik Edsger Dijkstra v roce 1965.^[1]

Implementace[editovat | editovat zdroj]

Implementace semaforu je založena na atomických operacích V (verhogen, též označováno jako up) a P (proberen, též označováno jako down). Operace down otestuje stav čítače a v případě že je nulový, zahájí čekání. Je-li nenulový, je čítač snížen o jedničku a vstup do kritické sekce je povolen. Při výstupu z kritické sekce je vyvolána operace up, která odblokuje vstup do kritické sekce pro další (čekající) proces. Čítač je možné si představit jako omezení počtu procesů, které mohou zároveň vstoupit do kritické sekce nebo například jako počitadlo volných prostředků. Tato implementace neodstraňuje problém aktivního čekání.

Odstranění aktivního čekání[editovat | editovat zdroj]

V případě, že je při vyvolání operace down čítač nulový, je nutné volající proces zablokovat. Čekání je implementováno jako nekonečná smyčka (tzv. aktivní čekání), která může být přerušena pouze vnějším zásahem jiného procesu do počitadla pomocí volání operace up. Neustálé testování stavu proměnné je možné nahradit pomocí fronty čekajících procesů.^[1] Proces je místo aktivního čekání (tj. neustálého kontrolování stavu proměnné) zařazen do fronty, ve které je uspán. Funkce up je rozšířena o průchod touto frontou, kdy je kromě zvýšení počitadla aktivován pouze proces, který je ve frontě první. Tento proces sníží počitadlo a vstoupí do kritické sekce. Ostatní procesy dále čekají v uspaném stavu.

Příklad implementace v pseudokódu:

 P(Semaphore s)
 {
   čekej dokud není s > 0 pak s = s-1; /* musí být atomické, jakmile je zjištěno, že s > 0 */
 }
 
 V(Semaphore s)
 {
   s = s+1;   /* musí být atomické */
 }
 
 Init(Semaphore s, Integer v)
 {
   s = v;
 }