Otázka č. 14 - Synchronizace

Zadání: vysvětlení pojmu · kritický kód · synchronizační prostředky · uváznutí

Vysvětlení pojmu

• Synchronizace = řízení přístupu ke sdíleným prostředkům (paměť, soubory, periferie) tak, aby nedocházelo ke kolizím.
• Týká se hlavně jádrových procesů, vláken a sdílených dat.
• Cíle:
  • zabránit konfliktům a ztrátě dat
  • zajistit správné pořadí operací (např. handshake - jeden proces čeká, až druhý potvrdí)
  • pozastavit běh procesu, dokud nenastane určitá podmínka

Proč je to vůbec potřeba

• Procesy jsou preemptivní - jádro může proces přerušit kdykoliv, i uprostřed zdánlivě jednoduché operace.
• Například x = x + 1 se do strojového kódu přeloží jako tři instrukce: načti x do registru, přičti 1, ulož zpět. Když se mezi ně vejde přepnutí kontextu, obě vlákna načtou stejnou hodnotu a jedno zvýšení se ztratí.
• Souběh (race condition) - situace, kdy výsledek závisí na časování, tj. na tom, v jakém pořadí se operace prostřídají. Je to jedna z nejhůř odladitelných chyb, protože se projevuje náhodně a při ladění často zmizí.
• Řešením je zajistit, aby se kritické části kódu prováděly atomicky, tedy nedělitelně - jako by šlo o jedinou instrukci.

Kritický kód

• Kritický kód (kritická sekce) je část programu, která přistupuje ke sdílenému prostředku.
• Pokud by ho najednou vykonávaly dva procesy, může dojít k chybě.
• Řešení: synchronizační mechanismy, které do kritického kódu pustí vždy jen jeden proces / vlákno.

Korektní řešení kritického kódu musí splnit tři podmínky:

1. Vzájemné vyloučení (mutual exclusion) - v kritickém kódu smí být nejvýš jeden proces.
2. Postup (progress) - je-li kritický kód volný a někdo do něj chce, nesmí mu v tom bránit proces, který o něj nemá zájem.
3. Konečné čekání (bounded waiting) - existuje horní mez, kolikrát můžou ostatní vstoupit dřív, než se dostane na řadu čekající proces. Zabraňuje stárnutí.

Příklad: producent a konzument

• Producent generuje data (např. audio, video) a ukládá je do vyrovnávací paměti (bufferu).
• Konzument data z bufferu odebírá a zpracovává.

Problémy bez synchronizace:

• konzument čte dřív, než jsou data připravena
• konzument čte stará nebo duplicitní data
• producent přepíše data dřív, než je konzument přečte
• při plném bufferu musí producent počkat, při prázdném musí počkat konzument

Klasické řešení používá tři semafory: mutex (ochrana samotného bufferu), volno (kolik je volných míst) a obsazeno (kolik je připravených položek).

Typy synchronizace

• Čekání na událost - jeden proces čeká, až druhý splní svůj úkol (určení pořadí operací).
• Vzájemné vyloučení - zabránění tomu, aby dva procesy současně vstoupily do téhož kritického kódu.

Synchronizační prostředky

Binární semafor

• Zavedl ho Edsger Dijkstra. Má dva stavy: „červená“ (obsazeno) a „zelená“ (volno).
• Dvě atomické operace:
  • wait (P, down) - čekání; je-li obsazeno, proces se zablokuje a zařadí do fronty semaforu
  • signal (V, up) - povolení; uvolní semafor a probudí čekajícího
• Výhody: jednoduchost, umí i určení pořadí (ne jen vzájemné vyloučení).
• Nevýhody: je to nízkoúrovňový a méně bezpečný nástroj - semafor nemá vlastníka, takže ho může „odemknout“ i proces, který ho nezamkl. Zapomenuté nebo prohozené wait/signal vede k uváznutí a hledá se velmi špatně.
• Používá se např. v modelu producent / konzument.

Obecný (čítající) semafor není jen 0/1, ale drží číslo - hlídá prostředek o n jednotkách (např. pět volných slotů v bufferu). Umožňuje tedy současný přístup až n procesům.

MUTEX (Mutual Exclusion)

• Silnější a bezpečnější než semafor, protože má vlastníka.
• Přístup má pouze proces, který MUTEX zamkl.
• Operace:
  • Lock - získání MUTEXu (když je obsazený, proces se zablokuje)
  • Unlock - uvolnění MUTEXu
• Vlastnosti:
  • Jen proces, který MUTEX získal, ho může odemknout. To je hlavní rozdíl proti semaforu a důvod, proč je bezpečnější.
  • Rekurzivní (reentrantní) MUTEX může tentýž vlastník zamknout opakovaně - vede si počet zámků a odemknout ho musí stejněkrát.

Pozor: MUTEX nikdy nemůže držet víc procesů současně - to by popřelo vzájemné vyloučení, ke kterému slouží. Počítání zámků se týká opakovaného zamčení jedním vlastníkem (rekurzivní mutex). Prostředek, který smí držet víc procesů naráz, je čítající semafor.

Další prostředky

• Monitor - vysokoúrovňová konstrukce zabudovaná do jazyka. Data a metody jsou zapouzdřené tak, že uvnitř monitoru může být vždy jen jeden proces - vzájemné vyloučení zajišťuje překladač, ne programátor. V Javě synchronized, v C# lock.
• Spinlock (aktivní čekání) - proces v cyklu testuje proměnnou, dokud se neuvolní. Plýtvá procesorovým časem, ale uvnitř jádra na víceprocesorových systémech se vyplatí, protože se čeká extrémně krátce a přepnutí kontextu by bylo dražší.
• Zákaz přerušení - proces si před kritickým kódem zakáže přerušení. Funguje jen na jednoprocesorovém systému a jen v jádře.
• Bariéra - všechna vlákna na ní počkají, dokud nedorazí poslední.
• Atomické instrukce procesoru - TSL / test-and-set a CAS (compare-and-swap) v jednom nedělitelném kroku přečtou a zapíší paměť. Na nich stojí implementace všech výše uvedených prostředků.

Klasické synchronizační problémy

• Producent - konzument (viz výše)
• Čtenáři a písaři - číst může současně víc procesů, zapisovat smí jen jeden a to sám.
• Večeřící filozofové - pět filozofů, pět vidliček, každý potřebuje obě sousední. Naivní řešení (každý vezme nejdřív levou) vede k uváznutí, když všichni zvednou levou naráz.

Uváznutí (deadlock)

• Dva (nebo více) procesy čekají na uvolnění prostředku, který drží ten druhý. Nikdy se tak nedočkají a stojí navždy.
• Příklad:
  • Proces A drží prostředek X a čeká na Y
  • Proces B drží prostředek Y a čeká na X

Coffmanovy podmínky

Uváznutí může nastat jen tehdy, platí-li všechny čtyři současně:

1. Vzájemné vyloučení - prostředek může používat jen jeden proces.
2. Držení a čekání - proces drží prostředek a zároveň čeká na další.
3. Nepreemptivnost prostředku - prostředek nelze procesu násilím odebrat.
4. Kruhové čekání - existuje cyklus procesů, kde každý čeká na prostředek držený následujícím.

Řešení uváznutí

• Prevence - zabránění vzniku jedné z podmínek uváznutí. Např. vynutit pevné pořadí zamykání prostředků (zabije kruhové čekání) nebo požadovat všechny prostředky naráz (zabije držení a čekání). Nevýhodou je horší využití prostředků.
• Vyhýbání (avoidance) - systém dopředu zná maximální požadavky procesů a povolí jen takové přidělení, po kterém zůstane v bezpečném stavu. Klasikou je bankéřův algoritmus (Dijkstra). V praxi se skoro nepoužívá, protože se maximální požadavky dopředu neznají.
• Detekce - uváznutí se nechá nastat, systém ale hlídá graf čekání a při nalezení cyklu ho rozbije. Je to pomalé a náročné, používají to hlavně databáze.
• Ignorance (pštrosí algoritmus) - OS uváznutí neřeší (např. UNIX, Windows), protože je vzácné a hlídání by bylo dražší než občasný restart. Uživatel musí proces přerušit ručně.

Pozor: bankéřův algoritmus patří k vyhýbání, ne k detekci. Uváznutí předem nedopustí tím, že rizikové přidělení odmítne. Detekce naopak nechá uváznutí vzniknout a pak hledá cyklus v grafu čekání.

Zrušení uváznutí

• Aplikace - uživatel ukončí zaseknutý proces (správce úloh, kill).
• Jádro - odebere prostředek a vrátí proces na dřívější kontrolní bod (rollback), v krajním případě restart systému.

Související problémy

• Stárnutí (starvation) - proces se nikdy nedostane k prostředku, i když systém jako celek běží. Na rozdíl od uváznutí není nic zablokované, jen je někdo trvale přeskakován.
• Livelock - procesy nejsou zablokované, pořád na sebe reagují, ale nedělají žádný pokrok.
• Inverze priorit - proces s nízkou prioritou drží zámek, který potřebuje proces s vysokou prioritou. Řeší se dědičností priority.