Úkolem tohoto cvičení je:

• seznámit se se semafory a jejich užitím pro vzájemné vyloučení
• seznámit se s mechanismy implementace semaforů
• do modulu podpory "procesů" implementovat čítající semafory.

Pojmy kritická sekce a vzájemné vyloučení

V minulém cvičení jsme se setkali s pojmem časový souběh - chybné chování, které může nastat, pokud více paralelně běžících procesů komunikuje prostřednictvím společné datové oblasti. Ta oblast programu, ve které může k časovému souběhu dojít, se nazývá kritická sekce. V našem příkladu byl kritickou sekcí příkaz ``x:=x+1''.

K časovému souběhu by nemohlo dojít, pokud bychom dokázali zajistit, aby žádné dva procesy neprováděly své kritické sekce současně. Pro správný běh procesů tedy potřebujeme zajistit vzájemné vyloučení procesů, tj. aby proces, který vstoupil do kritické sekce mohl zabránit jinému učinit totéž.

Aby bylo možné dané řešení používat prakticky, musí splňovat následující 4 podmínky:

1. nelze přepokládat nic o počtu a relativních rychlostech procesů
2. proces pracující mimo kritickou sekci nesmí bránit jinému procesu vstoupit do kritické sekce
3. nesmí nastat situace, kdy by jeden proces opakovaně vstupoval do kritické sekce, zatímco jiný by neměl šanci ("hladověl" by)
4. nesmí nastat situace, kdy by procesy neustále odkládaly rozhodnutí, který z nich do kritické sekce vstoupí (nekonečná smyčka způsobená komunikací typu "až po vás - až po vás").

Řešení vzájemného vyloučení

V případě pseudoparalelního běhu je nejjednodušším řešením zakázat přerušení při vstupu do kritické sekce a povolit je při výstupu. Pokud jsou přerušení zakázána, nemůže dojít k přerušení od časovače a tím ani k přepnutí procesu.

Takové řešení se skutečně užívá, například pro časově kritické procesy uvnitř jádra operačního systému. Dát uživatelským procesům právo zakázat přerušení však není vhodné, protože uživatelské programy mohou být (úmyslně či neúmyslně) chybné - domyslete, co by se stalo, pokud by proces přerušení "zapoměl" povolit.

Existuje několik softwarových řešení problému vzájemného vyloučení, ale tato jsou poměrně složitá a vyžadují aktivní čekání (tj. proces čekající na vstup do kritické sekce konzumuje drahocenný čas CPU opakovaným testováním hodnoty některé proměnné).

Semafory

V roce 1965 navrhl E. W. Dijkstra dvě primitivní operace, které podstatně zjednodušily synchronizaci procesů. Tyto operace, nazývané P a V, pracují nad tzv. semafory.

Nechť semafor s je nezáporné celé číslo. Pak můžeme operace P a V definovat takto:

• P(s): je-li s>0, pak s:=s-1. Jinak (pokud bylo s=0) bude aktuální proces pozastaven. Test hodnoty, její změna nebo případně pozastavení procesu jsou prováděny jako jedna nedělitelná operace (atomicky).
• V(s): není-li žádný proces blokován v operaci P nad semaforem s, provede s:=s+1. Jinak vybere některý z procesů blokovaných v operaci P a dovolí mu operaci P dokončit. Operace zvětšení semaforu nebo vzbuzení procesu je také nedělitelná.

Jak lze snadno ověřit, semafory splňují výše uvedené "pomínky praktické použitelnosti."

Pomocí semaforů je řešení problému kritické sekce již poměrně snadné. Vytvoříme semafor s počáteční hodnotou 1, který bude mít funkci jednoduchého zámku - pouze jeden proces bude moci provést operaci P a vstoupit do své kritické sekce.

Následující pseudokód ukazuje správné řešení úlohy, na které byl ilustrován problém časového souběhu:

     var 
         mutex: semaphore; { semafor mutex s počáteční hodnotou 1 }
         x:     integer;

     proces1:
         begin
             { nějaké instrukce }
             P(mutex);
             x:=x+1; { kritická sekce, může obsahovat libovolně instrukcí }
             V(mutex);
             { nějaké instrukce }
         end;         

     proces2:
         begin
             { nějaké instrukce }
             P(mutex);
             x:=x+1; { kritická sekce }
             V(mutex);
             { nějaké instrukce }
         end;         

Existuje i jednodušší forma semaforů, nazývaných binární semafory, které mohou nabývat pouze hodnot 0 a 1.

Později uvidíme, že výše popsané obecné (čítající) semafory lze užít i pro řešení některých problémů meziprocesové komunikace, například pro řešení problému producent/konzument (The Bounded Buffer Problem, Dijkstra 1968).

Implementace semaforů

Protože většina současných počítačů nemá podporu operací P a V na úrovni strojového jazyka, bývají funkce P a V implementovány operačním systémem. Na jednoprocesorových systémech může jejich atomičnost zajistit zakázáním přerušení po dobu operace, ve víceprocesorových systémech se užívá primitivních operací s uzamčením sběrnice.

Nyní si popíšeme jeden z možných způsobů implementace na jednoprocesorovém stroji.

S každým semaforem s je sdružena celočíselná proměnná s.c a seznam blokovaných procesů s.L. Semaforům dovolíme nabývat i záporných hodnot proměnné s.c, pak absolutní hodnota s.c vyjadřuje počet blokovaných procesů.

Proces, který nemůže dokončit operaci P bude zablokován a uložen do seznamu procesů blokovaných na semaforu s. Pokud při operaci V není seznam prázdný, vybere se ze seznamu jeden proces a odblokuje se.

Výše popsanou implementaci můžeme vyjádřit následujícím pseudokódem:

     P(s):
           zakaž přerušení;
           s.c := s.c -1;
           if s.c<0 then
           begin
               zařaď volající proces do seznamu s.L;
               zablokuj volající proces;
               naplánuj další připravený proces;
               s povolením přerušení přepni kontext na naplánovaný proces
           end;
           povol přerušení;

     V(s):
           zakaž přerušení;
           s.c:=s.c+1;
           if s.c<=0 then
           begin
               vyber proces ze seznamu s.L;
               odblokuj vybraný proces
           end;
           povol přerušení;

Výše uvedený pseudokód se nezabývá implementačními detaily, například organizací datových struktur a kontrolou chyb (např. je-li při operaci V záporné s.c a přitom s.L je prázdné).

Úloha: Implementace semaforů

Do vámi vytvořeného modulu podpory procesů implementujte čítající semafory jako procedury s jedním argumentem.