Synchronizace procesů
a kritická sekce

Moderní operační systémy provozují desítky až stovky procesů zdánlivě současně. Na jednojádrovém procesoru se velmi rychle střídají (přepnutí kontextu), na vícejádrových systémech mohou běžet skutečně paralelně. Dokud každý proces pracuje výhradně se svými privátními daty, vše je v pořádku. Problémy vznikají, jakmile dva nebo více procesů sdílejí společný prostředek — sdílenou paměť, soubor na disku, síťový socket nebo databázový záznam — a přistupují k němu bez koordinace.

Taková situace se nazývá race condition (závodní podmínka, souběh). Výsledek programu pak závisí na přesném časování přepínání procesů, což je nedeterministické a velmi těžko odladitelné — chyba se může projevit jen jednou za tisíc spuštění.

Konkrétní příklad: sdílené počítadlo

Mějme sdílenou proměnnou count (počet položek v bufferu, výchozí hodnota 3). Producent provede count++, konzument count--. Ve vyšším jazyce vypadá obojí jako jeden příkaz, ale na úrovni assembleru jde vždy o tři instrukce: načti do registru → uprav → ulož zpět. Přepnutí kontextu mezi těmito třemi kroky může způsobit:

Správná výsledná hodnota je 3 (přidali jsme 1 a odebrali 1). Místo toho jsme skončili na 2, protože konzument přepsal výsledek producenta starými daty ze svého registru. Tato situace je klasickým příkladem race condition.

Charakteristika a čtyři podmínky ošetření KS

Část kódu, ve které dochází k přístupu ke sdílenému prostředku, se nazývá kritická sekce (Critical Section, KS). Je to místo, kde existuje riziko race condition — kde musí platit, že v daný okamžik se nachází nejvýše jeden proces. Aby bylo řešení korektní, musí splňovat čtyři podmínky:

Tyto čtyři podmínky jsou měřítkem každého synchronizačního mechanismu. Uvidíme, že starší přístupy nesplňují všechny — právě v tom spočívá smysl jejich vývoje od jednoduchých, ale chybných, k sofistikovaným a korektním řešením.

Aktivní vs. pasivní čekání

Při ochraně kritické sekce musí procesy, které nemohou vstoupit, nějak čekat. Existují dva zásadně odlišné způsoby:

Problém producenta a konzumenta (Bounded Buffer Problem) je jeden z nejklasičtějších synchronizačních problémů v informatice. Modeluje situaci, která nastává v praxi neustále: jeden nebo více producentů generuje data a vkládá je do sdíleného bufferu (vyrovnávací paměti), zatímco jeden nebo více konzumentů data z bufferu odebírá a zpracovává.

Reálné příklady jsou všudypřítomné. Webový server: síťový subsystém (producent) přijímá HTTP požadavky a vkládá je do fronty; pracovní vlákna (konzumenti) je obsluhují. Zvukový player: dekodér (producent) dekóduje audio rámce do bufferu; zvuková karta (konzument) je přehrává. Kompilátor: lexer (producent) generuje tokeny; parser (konzument) je zpracovává.

Buffer má fixní velikost N. Platí dvě základní omezení: producent nesmí vložit data do plného bufferu (nemá kde), konzument nesmí odebírat z prázdného bufferu (není co). Proměnná count sleduje aktuální počet prvků.

4.1 Zákaz přerušení

Nejpřímočařejší přístup: proces před vstupem do KS zakáže veškerá přerušení a po opuštění KS je opět povolí. Přepnutí kontextu je vždy vyvoláno přerušením (od časovače nebo I/O zařízení). Pokud přerušení zakážeme, ke kontextovému přepnutí nemůže dojít — v KS bude vždy nejvýše jeden proces.

Analogie ze života: jako když vstoupíš do kanceláře, zamknul dveře a vypneš telefon. Nikdo tě nemůže vyrušit, dokud sám neodemkneš a nevyjdeš.

Proč toto řešení není vhodné pro uživatelský prostor?

Bezpečnostní riziko: Uživatelský proces by získal absolutní moc nad chodem systému. Pokud by záměrně nebo chybou přerušení znovu nepovolil, celý systém by zamrzl — žádný jiný proces, ani jádro OS, by nemohl převzít řízení. Operační systém nemůže důvěřovat uživatelskému kódu v takové míře.

Nefunkčnost na vícejádrových systémech (SMP): Zákaz přerušení postihuje pouze jádro CPU, na němž daný proces běží. Ostatní jádra mohou libovolně pokračovat a jejich procesy mohou vstoupit do téže kritické sekce na jiném jádře. Na moderním hardware tedy zákaz přerušení vůbec nezaručuje vzájemné vyloučení.

Zpoždění systémových reakcí: Během zákazu přerušení systém nereaguje na vstupy z klávesnice, síťové pakety, přerušení časovače ani I/O události. To může způsobit ztrátu dat nebo degradaci výkonu celého systému.

4.2 Zamykací proměnná (Lock Variable)

Druhý přístup je čistě softwarový a velmi intuitivní: zavedeme sdílenou proměnnou lock fungující jako „tabulka na dveřích". Hodnota 0 znamená, že KS je volná; hodnota 1, že je obsazena. Před vstupem do KS proces zkontroluje lock. Pokud je 0, nastaví ho na 1 a vstoupí. Pokud je 1, čeká v aktivní smyčce. Po opuštění KS nastaví lock zpět na 0.

Zamykací proměnná: enterCS() čeká aktivně dokud lock ≠ 1, pak zamkne. leaveCS() odemkne nastavením lock = 0.

int lock = 0;  // 0 = volno, 1 = obsazeno

void enterCS() {
    while(lock == 1);  // aktivní čekání
    lock = 1;           // zamkni
}

void leaveCS() {
    lock = 0;           // odemkni
}

Fatální slabina: race condition na samotném zámku

Zamykací proměnná přesouvá race condition z KS na proměnnou lock. Čtení lock a jeho následné nastavení jsou dvě oddělené operace. Mezi nimi může dojít k přepnutí kontextu:

Proces P1 přečte lock == 0 → OS přepne → P2 přečte lock == 0, nastaví lock = 1, vstoupí do KS → OS přepne zpět → P1 pokračuje: nastaví lock = 1, vstoupí do KS. Oba jsou v KS zároveň. Porušena podmínka č. 1.

4.3 Přesné střídání (Strict Alternation)

Přesné střídání řeší problém race condition na zámku zavedením sdílené proměnné turn, která explicitně určuje, který konkrétní proces smí vstoupit do KS. Je to jako přiřadit klíč: kdo ho drží, smí vstoupit. Po opuštění KS předá klíč druhému.

Přesné střídání: proměnná turn určuje, který proces smí vstoupit. P0 čeká dokud turn != 0, P1 dokud turn != 1.

int turn = 0;  // 0 = řada P0, 1 = řada P1

// Kód procesu P0:
while(TRUE) {
    while(turn != 0);   // čekej na svou řadu
    critical_section();
    turn = 1;            // předej řadu P1
    noncritical_section();
}

// Kód procesu P1:
while(TRUE) {
    while(turn != 1);   // čekej na svou řadu
    critical_section();
    turn = 0;            // předej řadu P0
    noncritical_section();
}

Přesné střídání skutečně zaručuje vzájemné vyloučení — dva procesy nemohou mít turn nastavený na sebe zároveň. Naráží ale na vážný problém.

Porušení podmínky trvalosti postupu

Uvažuj situaci: turn = 0. P0 vstoupí do KS, dokončí ji, nastaví turn = 1 a odejde do nekritické sekce — kde pracuje dlouho nebo je dokonce pozastaven. P1 mezitím vstoupí do KS, dokončí ji rychle, nastaví turn = 0 a odejde do nekritické sekce — kde také pracuje rychle a chce ihned znovu do KS. Nemůže! Musí čekat na P0, i když P0 je ve své nekritické sekci a KS je prázdná.

Tím je porušena podmínka č. 2: „Proces mimo KS nesmí blokovat jiný proces, který chce vstoupit." P0 blokuje P1, přestože sám není v KS. Procesy musí vstupovat do KS přesně střídavě, bez ohledu na svůj skutečný zájem. Rychlý proces je zbytečně brzděn pomalým.

4.4 Petersonovo řešení

Petersonovo řešení (Gary L. Peterson, 1981) je elegantní čistě softwarová metoda, která kombinuje myšlenky přesného střídání a zamykací proměnné. Splňuje všechny čtyři podmínky korektního řešení KS pro dva procesy. Je jedním z nejdůležitějších algoritmů v historii teorie operačních systémů — elegantně vyřešilo problém, který se zdál velmi obtížný.

Algoritmus používá dvě sdílené datové struktury. Pole interested[2] (výchozí hodnota 0) říká, zda proces má zájem vstoupit do KS. Proměnná turn určuje, kdo má „přednost" v případě, že oba procesy chtějí vstoupit současně.

Petersonovo řešení: kombinace interested[] a turn zajišťuje vzájemné vyloučení bez hardwarové podpory.

#define N 2
int turn;
int interested[N];  // výchozí 0 (nemám zájem)

void enterCS(int process) {
    int other = 1 - process;   // druhý proces (0→1 nebo 1→0)
    interested[process] = 1;   // oznámím zájem o vstup do KS
    turn = process;            // ustoupím druhému (nabídnu mu přednost)
    // Čekej pokud: druhý chce KS A druhý má přednost
    while(turn == process && interested[other] == 1);
}

void leaveCS(int process) {
    interested[process] = 0;   // vzdávám zájem — KS je volná
}

Proč to funguje? Rozbor logiky krok za krokem

Krok 1 — Oznámení zájmu: interested[process] = 1. Proces říká ostatním: „Chci vstoupit do KS."

Krok 2 — Ustoupení: turn = process. Toto je klíčový trik. Nastavením turn na sebe sama proces říká: „Jestli jsme oba chtěli vstoupit zároveň, nechám toho druhého jít napřed." Kdo zavolá enterCS() jako poslední, ten prohraje a bude čekat. Je to jako zdvořilostní gesto: „Po tobě."

Krok 3 — Podmínka čekání: while(turn == process && interested[other] == 1). Čekám právě tehdy, když jsou splněny obě podmínky: jsem ten, kdo ustoupil (turn == process) A druhý skutečně chce vstoupit (interested[other] == 1). Pokud druhý nechce KS, smyčka okamžitě skončí. Pokud oba vstupují zároveň, ten, kdo jako poslední napsal turn = process, čeká — druhý prošel.

Nevýhodou je stále aktivní čekání (busy waiting). Také je toto řešení navrženo pro právě dva procesy; rozšíření na N procesů existuje (Lamportův algoritmus pekárny), ale je výrazně složitější.

4.5 Atomická instrukce (Hardware podpora)

Zatímco předchozí řešení jsou čistě softwarová (a výsledně složitá), moderní procesory nabízejí přímou hardwarovou podporu: atomické instrukce. Atomická instrukce je taková, která se z pohledu ostatních procesorů jeví jako nedělitelná — provede se buď celá, nebo vůbec. Mezi jejím začátkem a koncem nemůže zasáhnout jiný procesor ani dojít k přepnutí kontextu.

Hardware to zajistí uzamčením paměťové sběrnice (memory bus): po dobu provádění atomické instrukce žádný jiný procesor nesmí přistoupit k paměti. Tím je zaručena atomicita i na vícejádrových SMP systémech.

Atomické instrukce TAS (Motorola 68000) a XCHG (Intel IA-32): obě realizují operaci „přečti a nastav" jako jednu nedělitelnou instrukci.

Test-And-Set (TAS)

TAS atomicky: přečte hodnotu paměťového místa do registru CPU, nastaví paměťové místo na 1. Čtení a zápis probíhají jako jediná nedělitelná operace. Pokud byl lock před voláním TAS nulový, nyní je nastaven na 1 a registr obsahuje 0 — to signalizuje, že jsme získali zámek. Pokud byl nenulový, registr obsahuje 1 — čekáme.

; Motorola 68000 — instrukce TAS
enter_cs:
    tas   lock         ; atomicky: zkopíruj lock→CPU, nastav lock=1
    bnz   enter_cs     ; lock byl nenulový → opakuj (aktivní čekání)
    ret               ; lock byl 0 → vstup do KS

leave_cs:
    mov   lock, #0     ; odemkni KS
    ret

Exchange (XCHG)

XCHG atomicky vymění obsah registru a paměťového místa. Na architektuře IA-32 (Intel x86) je instrukce XCHG automaticky atomická, i bez prefixu LOCK. Do registru EAX vložíme 1 a provedeme výměnu s lock. Původní hodnota lock přijde do EAX. Pokud byla 0 (volno), vstoupíme. Pokud byla 1 (obsazeno), opakujeme.

; Intel IA-32 — instrukce XCHG
enter_cs:
    mov  EAX, #1      ; chystám hodnotu 1 do registru
    xchg lock, EAX    ; atomická výměna: lock↔EAX
    jnz  enter_cs     ; původní lock byl nenulový → čekej
    ret               ; lock byl 0 → vstup do KS

leave_cs:
    mov  lock, #0     ; odemkni
    ret

Compare-And-Swap (CAS) — moderní varianta

Na moderních x86-64 a ARM procesorech se hojně používá instrukce CAS (x86: CMPXCHG). Atomicky porovná hodnotu v paměti s očekávanou hodnotou (expected) a pouze pokud se shodují, uloží novou hodnotu (desired). Vrátí informaci o úspěchu. CAS je základem moderních lock-free a wait-free datových struktur a atomických operací v jazycích (C++ std::atomic, Java AtomicInteger).

4.6 Sleep() a Wakeup() — přechod na pasivní čekání

Mechanismus sleep/wakeup je přechodem od aktivního k pasivnímu čekání. Místo nekonečné testovací smyčky se proces, který nemůže vstoupit do KS, dobrovolně vzdá procesoru voláním sleep() — OS ho uspí a zařadí do fronty čekajících. Jiný proces, který KS uvolní, zavolá wakeup() a proboudí čekajícího.

Přehled problémů, které mohou nastat při pasivním čekání: deadlock, stárnutí, livelock, inverze priorit.

Deadlock (uváznutí)

Deadlock nastane, když dva nebo více procesů na sebe navzájem čekají způsobem, ze kterého není úniku. Každý drží zdroj, který potřebuje ten druhý, a čeká na zdroj, který drží ten druhý. Systém je zablokován — procesy nemohou udělat žádný pokrok a situaci nelze vyřešit bez vnějšího zásahu (typicky ukončení jednoho z procesů nebo odebrání zdroje).

Klasický příklad: Proces A drží soubor X a čeká na soubor Y. Proces B drží soubor Y a čeká na soubor X. Žádný z nich nemůže pokračovat. Čtyři podmínky pro vznik deadlocku (Coffmanovy podmínky): vzájemné vyloučení zdrojů, držení a čekání, nepřerušitelnost (zdroj nelze procesu násilně odebrat), kruhové čekání.

Stárnutí (Starvation)

Stárnutí nastane, když je jeden nebo více procesů systematicky odsouvano a nikdy se nedostanou k prostředku, i když prostředek je periodicky volný. Příkladem je systém s neomezenou předností čtenářů: pokud neustále přicházejí noví čtenáři, písař může čekat libovolně dlouho — stárne. Stárnutí je méně fatální než deadlock (procesy technicky „běží"), ale v praxi může způsobit selhání systému (time-out, odmítnutí požadavku).

Aktivní zablokování (Livelock)

Livelock je situace, kdy procesy nejsou zablokované (stále se vykonávají), ale nedělají žádný užitečný pokrok — neustále reagují na akce toho druhého způsobem, který jim oba brání postupovat. Klasická analogie: dva zdvořilí lidé jdou proti sobě úzkou chodbou. Oba se snaží uhnout — ale vždy uhnou na stejnou stranu, takže se opět blokují. Nikdo není agresivní, oba jsou ochotni ustoupit, ale výsledkem je pat.

Inverze priorit (Priority Inversion)

Inverze priorit je záludný problém při kombinaci prioritního plánování a sdílených prostředků. Uvažuj tři procesy: H (vysoká priorita), M (střední priorita), L (nízká priorita). Proces L získá zámek na sdíleném prostředku. Přijde H, chce ten prostředek — zablokuje se a čeká. Přijde M, nepotřebuje prostředek, ale má vyšší prioritu než L — plánovač mu dá CPU. L nemůže dokončit práci a uvolnit zámek, protože M ho blokuje. H čeká na L, L čeká na M. Efektivně tak středněprioritní proces M blokuje vysokoprioritní proces H. Slavný příklad: Mars Pathfinder v roce 1997 se kvůli inverzi priorit periodicky resetoval.

4.7 Semafory a transakce

Semafor je zobecněný synchronizační primitiv navržený Edsgerem Dijkstrou v roce 1965. Je to programový prostředek (datová struktura) spravovaný operačním systémem, který umožňuje procesům koordinovat přístup ke sdíleným prostředkům bez aktivního čekání a bez problému ztracených probuzení.

Analogie: semafor na železnici signalizuje vlakům, zda je trať volná. Pokud je červený (hodnota 0), vlak stojí a čeká. Jakmile předchozí vlak odjede (signal), semafor se přepne na zelenou a čekající vlak může pokračovat.

Obecný semafor (Counting Semaphore)

Obecný semafor je datová struktura obsahující celočíselný čítač a frontu čekajících procesů. Jsou definovány tři operace. init(S, n) inicializuje semafor na hodnotu n ≥ 0 — udává, kolik procesů může vstoupit do KS bez blokování (kolik „povolení" je dostupných). wait(S) sníží čítač o 1; pokud je výsledná hodnota záporná, proces je zablokován a zařazen do fronty. Záporná hodnota čítače říká (absolutní hodnotou), kolik procesů právě čeká. signal(S) zvýší čítač o 1; pokud jsou v frontě čekající procesy, jeden je probuzen.

Obecný semafor: wait() snižuje čítač a blokuje při záporné hodnotě, signal() zvyšuje čítač a probouzí čekající proces.

// Pseudokód: obecný semafor
struct Semaphore {
    int   count;    // čítač povolení
    Queue queue;    // fronta blokovaných procesů
};

void wait(Semaphore &S) {   // ATOMICKÁ operace!
    S.count--;
    if(S.count < 0) {
        enqueue(S.queue, current_process);
        sleep();          // usni → pasivní čekání
    }
}

void signal(Semaphore &S) {  // ATOMICKÁ operace!
    S.count++;
    if(S.count <= 0) {
        P = dequeue(S.queue);
        wakeup(P);        // probuď čekající proces
    }
}

Binární semafor — Mutex

Binární semafor je speciální případ, kde čítač nabývá pouze hodnot 0 a 1 (nebo booleovské false/true). Operace wait() se chová jako lock() — zamkni; signal() jako unlock() — odemkni. Název „mutex" (z mutual exclusion) přesně vystihuje jeho účel: zajistit, aby v chráněné sekci bylo nejvýše jeden proces.

Binární semafor (mutex): místo čítače používá booleovskou proměnnou. První proces zamkne (lock), po opuštění KS odemkne (unlock) — případně probudí čekající.

// Ochrana KS pomocí mutexu
Semaphore mutex;
init(mutex, 1);       // 1 = KS volná

// Kód každého procesu:
wait(mutex);          // zamkni (čekej pokud obsazeno)
critical_section();
signal(mutex);        // odemkni (probuď čekající)
noncritical_section();

Producent–konzument se semafory — správné řešení

Semafory elegantně a správně řeší problém producenta a konzumenta. Používáme tři semafory: mutex inicializovaný na 1 (ochrana bufferu), empty inicializovaný na N (počet volných míst v bufferu), full inicializovaný na 0 (počet obsazených míst).

// Producent:
while(TRUE) {
    item = produce_item();
    wait(empty);      // čekej na volné místo v bufferu
    wait(mutex);      // zamkni přístup k bufferu
    insert_item(item);
    signal(mutex);    // odemkni buffer
    signal(full);     // oznám: přibylo obsazené místo
}

// Konzument:
while(TRUE) {
    wait(full);       // čekej na data v bufferu
    wait(mutex);      // zamkni přístup k bufferu
    item = remove_item();
    signal(mutex);    // odemkni buffer
    signal(empty);    // oznám: přibylo volné místo
    consume_item(item);
}

Teorie synchronizace se ověřuje na sadě modelových problémů, které vystihují různé reálné situace a demonstrují různé aspekty synchronizačních výzev. Znalost těchto problémů je důležitá, protože slouží jako referenční vzory při návrhu synchronizace v reálných systémech.

1. Producent a konzument (Bounded Buffer)

Viz kapitola 3 a sekce 4.7. Koordinace generátoru a spotřebitele dat přes sdílený buffer omezené velikosti. Klíčové body: nesmí dojít k přepsání dat (producer do plného bufferu), ani ke čtení neexistujících dat (consumer z prázdného bufferu), a ani k souběžnému přístupu obou. Řeší se třemi semafory: mutex, empty, full. Správné pořadí wait() je kritické pro zabránění deadlocku.

2. Čtenáři a písaři (Readers-Writers Problem)

Databáze nebo sdílený datový zdroj může být čten více čtenáři zároveň bez problémů (čtení nemodifikuje data). Písař, který data mění, ale potřebuje výhradní přístup — nesmí číst ani psát nikdo jiný. Existují dvě varianty s odlišnými prioritami.

Ve variantě s předností čtenářů může kdokoliv z čtenářů vstoupit, pokud je alespoň jeden čtenář přítomen. Písaři mohou být odloženi donekonečna — stárnutí písařů. Ve variantě s předností písařů jakmile chce písař přistoupit, noví čtenáři musí čekat. Tím hrozí stárnutí čtenářů. Praktické řešení volí kompromis — například fair-scheduling, kde se střídají skupiny čtenářů a skupiny písařů.

3. Večeřící filozofové (Dining Philosophers)

Pět filozofů sedí u kulatého stolu. Mezi každými dvěma sousedy leží jedna hůlka (celkem 5 hůlek). Každý filozof střídá přemýšlení (žádné prostředky) a jídlo (potřebuje obě sousední hůlky). Hůlky jsou sdíleným prostředkem — sousední filozofové o ně soupeří.

Problém nastane, pokud všichni filozofové zároveň vezmou levou hůlku a čekají na pravou — žádná pravá hůlka není k dispozici, nastane deadlock. Řešení zahrnují: dovolení maximálně N-1 filozofům sedět u stolu zároveň (zabrání kruhového čekání), asymetrické pravidlo (sudí berou nejprve levou hůlku, lichí pravou), nebo atomické uchopení obou hůlek najednou (pomocí semaforu, který dovoluje „vzít obě nebo nic").

Tento problém modeluje situaci, kdy procesy potřebují více sdílených prostředků zároveň — typické v databázových systémech, kde transakce zamykají více tabulek.

4. Spící holič (Sleeping Barber Problem)

Holičství má jedno křeslo a čekárnu s N místy k sezení. Pokud není zákazník, holič spí v křesle. Příchozí zákazník: probudí spícího holiče, nebo si sedne (pokud je místo v čekárně), nebo odejde (čekárna plná). Holič po dokončení střihu zkontroluje čekárnu — pokud je prázdná, jde spát.

Synchronizační výzva: koordinace holiče a zákazníků tak, aby holič nespal, když zákazníci čekají, a zákazník neodešel zbytečně. Řeší se typicky třemi semafory: customers (počet čekajících zákazníků), barbers (počet volných holičů), mutex (ochrana počítadla sedadel). Tento problém modeluje servery s omezenou frontou požadavků — webové servery, thread pools.

Postupný vývoj synchronizačních mechanismů odráží historii boje s race conditions. Každé řešení odstraňuje slabiny toho předchozího, ale přináší nové kompromisy. Následující tabulka shrnuje hodnocení každé metody: