PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 1 Synchronizace procesů Uváznutí PB 169 Počítačové sítě a operační systémy PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 2 Paralelní běh procesů ¢Synchronizace běhu procesů ljeden proces čeká na událost z druhého procesu ¢Komunikace mezi procesy lkomunikace – způsob synchronizace, koordinace různých aktivit lmůže dojít k uváznutí •každý proces čeká na zprávu od nějakého jiného procesu lmůže dojít ke stárnutí •dva procesy si opakovaně posílají zprávy zatímco třetí proces čeká na zprávu nekonečně dlouho ¢Sdílení prostředků lprocesy používají a modifikují sdílená data loperace zápisu musí být vzájemně výlučné loperace zápisu musí být vzájemně výlučné s operacemi čtení •operace čtení mohou být realizovány souběžně lpro zabezpečení integrity dat se používají kritické sekce PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 3 Nekonzistence ¢Paralelní přístup ke sdíleným údajům může být příčinou nekonzistence dat ¢Udržování konzistence dat vyžaduje používání mechanismů, které zajistí patřičné provádění spolupracujících procesů ¢Problém komunikace procesů v úloze typu Producent-Konzument přes vyrovnávací paměť s omezenou kapacitou PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 4 Producent-konzument (1) ¢Sdílená data •#define BUFFER_SIZE 10 •typedef struct { • . . . •} item; •item buffer[BUFFER_SIZE]; •int in = 0; •int out = 0; •int counter = 0; • ¢ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 5 Producent-konzument (2) ¢Producent ¢ ¢ item nextProduced; ¢ while (1) { ¢ while (counter == BUFFER_SIZE) ¢ ; /* do nothing */ ¢ buffer[in] = nextProduced; ¢ in = (in + 1) % BUFFER_SIZE; ¢ counter++; ¢ } ¢ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 6 Producent-konzument (3) ¢Konzument ¢ ¢ item nextConsumed; ¢ while (1) { ¢ while (counter == 0) ¢ ; /* do nothing */ ¢ nextConsumed = buffer[out]; ¢ out = (out + 1) % BUFFER_SIZE; ¢ counter--; ¢ } PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 7 Producent-konzument (4) ¢Atomická operace je taková operace, která vždy proběhne bez přerušení ¢Následující příkazy musí být atomické lcounter++; lcounter--; ¢count++ v assembleru může vypadat lregister1 = counter lregister1 = register1 + 1 lcounter = register1 ¢count-- v assembleru může vypadat lregister2 = counter lregister2 = register2 – 1 lcounter = register2 PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 8 Producent-konzument (5) ¢Protože takto implementované operace count++ a count-- nejsou atomické, můžeme se dostat do problémů s konzistencí ¢Nechť je hodnota counter nastavena na 5. Může nastat: lproducer: register1 = counter (register1 = 5) lproducer: register1 = register1 + 1 (register1 = 6) lconsumer: register2 = counter (register2 = 5) lconsumer: register2 = register2 – 1 (register2 = 4) lproducer: counter = register1 (counter = 6) lconsumer: counter = register2 (counter = 4) ¢Výsledná hodnota proměnné counter bude buďto 4 nebo 6, zatímco správný výsledek má být 5. ¢ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 9 Race condition ¢Race condition (podmínka soupeření): lvíce procesů současně přistupuje ke sdíleným zdrojům a manipulují s nimi lkonečnou hodnotu zdroje určuje poslední z procesů, který zdroj po manipulaci opustí ¢Ochrana procesů před negativními dopady race condition lje potřeba procesy synchronizovat PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 10 Problém kritické sekce ¢N procesů soupeří o právo používat jistá sdílená data ¢V každém procesu se nachází segment kódu programu nazývaný kritická sekce, ve kterém proces přistupuje ke sdíleným zdrojům ¢Problém: lje potřeba zajistit, že v kritické sekci, sdružené s jistým zdrojem, se bude nacházet nejvýše jeden proces PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 11 Podmínky řešení problému kritické sekce ¢Podmínka vzájemného vyloučení (mutual exclusion), podmínka bezpečnosti, „safety“ ljestliže proces P1 provádí svoji kritickou sekci, žádný jiný proces nemůže provádět svoji kritickou sekci sdruženou se stejným zdrojem ¢Podmínka trvalosti postupu (progress), podmínka živosti, „liveliness“ ljestliže žádný proces neprovádí svoji sekci sdruženou s jistým zdrojem a existuje alespoň jeden proces, který si přeje vstoupit do kritické sekce sdružené s tímto zdroje, pak výběr procesu, který do takové kritické sekce vstoupí, se nesmí odkládat nekonečně dlouho ¢Podmínka konečnosti doby čekání (bounded waiting), podmínka spravedlivosti, „fairness“ lmusí existovat horní mez počtu, kolikrát může být povolen vstup do kritické sekce sdružené s jistým zdrojem jiným procesům než procesu, který vydal žádost o vstup do kritické sekce sdružené s tímto zdrojem, po vydání takové žádosti a před tím, než je takový požadavek uspokojen lpředpokládáme, že každý proces běží nenulovou rychlostí lo relativní rychlosti procesů nic nevíme l PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 12 Počáteční návrhy řešení ¢Máme pouze 2 procesy, P0 a P1 ¢Generická struktura procesu Pi ¢ do { ¢ entry section ¢ critical section ¢ exit section ¢ reminder section ¢ } while (1); ¢Procesy mohou za účelem dosažení synchronizace svých akcí sdílet společné proměnné ¢Činné čekání na splnění podmínky v „entry section“ – „busy waiting“ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 13 Řešení problému KS ¢Softwarová řešení lalgoritmy, jejichž správnost se nespoléhá na žádné další předpoklady ls aktivním čekáním „busy waiting“ ¢Hardwarová řešení lvyžadují speciální instrukce procesoru ls aktivním čekáním ¢Řešení zprostředkované operačním systémem lpotřebné funkce a datové struktury poskytuje OS ls pasivním čekáním lpodpora v programovacím systému/jazyku •semafory, monitory, zasílání zpráv PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 14 Algoritmus 1 ¢Sdílené proměnné lint turn; počátečně turn = 0 lturn = i Þ Pi může vstoupit do KS ¢Proces Pi ¢ do { ¢ while (turn != i) ; ¢ critical section ¢ turn = j; ¢ reminder section ¢ } while (1); ¢Splňuje vzájemné vyloučení, ale ne trvalost postupu ¢ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 15 Algoritmus 2 ¢Sdílené proměnné lboolean flag[2]; počátečně flag [0] = flag [1] = false. lflag [i] = true Þ Pi může vstoupit do své KS ¢Process Pi ¢ do { ¢ flag[i] := true; while (flag[j]) ; critical section ¢ flag [i] = false; ¢ remainder section ¢ } while (1); ¢Splňuje vzájemné vyloučení, ale ne trvalost postupu ¢ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 16 Algoritmus 3 (Petersonův) ¢Kombinuje sdílené proměnné algoritmů 1 a 2 ¢Proces Pi ¢ do { ¢ flag [i]:= true; turn = j; while (flag [j] and turn == j) ; ¢ critical section ¢ flag [i] = false; ¢ remainder section ¢ } while (1); ¢Jsou splněny všechny tři podmínky správnosti řešení problému kritické sekce PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 17 Synchronizační hardware ¢Speciální instrukce strojového jazyka ltest_and_set, exchange / swap, … ¢Stále zachována idea používání „busy waiting“ ¢Test_and_set ltestování a modifikace hodnoty proměnné – atomicky ¢ boolean TestAndSet (boolean &target) { ¢ boolean rv = target; ¢ target = true; ¢ return rv; ¢ } ¢Swap lAtomická výměna dvou proměnných lVoid Swap (boolean &ra, boolean &rb] { l boolean temp = a; l a = b; l b = temp; l } l PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 18 Využití TestAndSet ¢Sdílená data (inicializováno na false): ¢ boolean lock: ¢Proces Pi ¢ do { ¢ while (TestAndSet(lock)) ; ¢ critical section ¢ lock = false; ¢ remainder section ¢ } PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 19 Využití Swap ¢Sdílená data (inicializováno na false): ¢ boolean lock; ¢ boolean waiting[n]; ¢Proces Pi ¢ do { ¢ key = true; ¢ while (key == true) ¢ Swap(lock,key); ¢ critical section ¢ lock = false; ¢ remainder section ¢ } PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 20 Situace bez podpory OS ¢Nedostatek softwarového řešení lprocesy, které žádají o vstup do svých KS to dělají metodou „busy waiting“ •po nezanedbatelnou dobu spotřebovávají čas procesoru ¢Speciální instrukce lvýhody •vhodné i pro multiprocesory (na rozdíl od prostého maskování/povolení přerušení) lnevýhody •opět „busy waiting“ •možnost stárnutí – náhodnost řešení konfliktu •možnost uváznutí v prioritním prostředí (proces v KS nedostává čas CPU) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 21 Semafory ¢Synchronizační nástroj, který lze implementovat i bez „busy waiting“ lproces je (operačním systémem) „uspán“ a „probuzen“ ltj. řešení na úrovni OS ¢Definice ¢ Semaphore S : integer ¢Lze ho zpřístupnit pouze pomocí dvou atomických operací ¢ wait (S): signal(S): ¢ while S ≤ 0 do no-op; S ++; ¢ S --; PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 22 Kritická sekce ¢Sdílená data: ¢ semaphore mutex; // počátečně mutex = 1 ¢Proces Pi: ¢ do { ¢ wait(mutex); ¢ critical section ¢ signal(mutex); ¢ remainder section ¢ } while (1); PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 23 Uváznutí a stárnutí ¢Uváznutí ldva nebo více procesů neomezeně dlouho čekají na událost, kterou může generovat pouze jeden z čekajících procesů lNechť S a Q jsou dva semafory inicializované na 1 ¢ P0 P1 ¢ wait(S); wait(Q); ¢ wait(Q); wait(S); ¢ M M ¢ signal(S); signal(Q); ¢ signal(Q) signal(S); ¢Stárnutí lneomezené blokování, proces nemusí být odstraněný z fonty na semafor nikdy (předbíhání vyššími prioritami, …) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 24 Problémy se semafory ¢Semafory jsou mocný nástroj pro dosažení vzájemného vyloučení a koordinaci procesů ¢Operace wait(S) a signal (S) jsou prováděny více procesy a jejich účinek nemusí být vždy explicitně zřejmý lsemafor s explicitním ovládáním wait/signal je nástroj nízké úrovně ¢Chybné použití semaforu v jednom procesu hroutí souhru všech spolupracujících procesů ¢Patologické případy použití semaforů: ¢ wait(x) wait(x) ¢ KS KS ¢ wait(x) signal(y) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 25 Příklad: Linux (1) ¢IPC (InterProcess Communication) lsignály (asynchronní události) lroury ( ls|pr|lpr ) lzprávy (messages) lsemafory (semaphores) lsdílená paměť (shared memory) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 26 sem Příklad: Linux (2) ¢Semafory, volání jádra lsemget lsemctl lsemop PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 27 Problém uváznutí ¢Existuje množina blokovaných procesů, každý proces vlastní nějaký prostředek (zdroj) a čeká na zdroj držený jiným procesem z této množiny ¢Příklad 1 lv systému existují 2 páskové mechaniky lprocesy P1 a P2 chtějí kopírovat data z pásky na pásku, každý z procesů „vlastní“ jednu mechaniku a požaduje alokací druhé ¢Příklad 2 lSemafory A a B, inicializované na 1 • P0 P1 •wait (A); wait(B) •wait (B); wait(A) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 28 Příklad: úzký most ¢Most s jednosměrným provozem ¢Každý vjezd mostu lze chápat jako zdroj ¢Dojde-li k uváznutí, lze ho řešit tím, že se jedno auto vrátí lPreempce zdroje (přivlastnění si zdroje, který vlastnil někdo jiný) a vrácení soupeře do situace před žádostí o přidělení zdroje (preemption a rollback) ¢Při řešení uváznutí se může vracet i více vozů ¢Může docházet ke stárnutí PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 29 Definice uváznutí a stárnutí ¢Uváznutí lmnožina procesů P uvázla, jestliže každý proces Pi z P čeká na událost (uvolnění prostředku, zaslání zprávy), kterou vyvolá pouze některý z procesů P ¢Stárnutí lpožadavky 1 nebo více procesů z P nebudou splněny v konečném čase •z důvodů vyšších priorit jiného procesu •z důvodů prevence uváznutí apod. PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 30 Model ¢Typy zdrojů R1, R2, …, Rm •tiskárna, paměť, I/O zařízení, … ¢Každý zdroj Ri má Wi instancí ¢Každý proces používá zdroj následujícím způsobem 1.žádost 2.použití 3.uvolnění (v konečném čase) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 31 Charakteristika uváznutí ¢K uváznutí dojde, když začnou současně platit 4 následující podmínky lvzájemné vyloučení (mutual exclusion) •sdílený zdroj může v jednom okamžiku používat pouze jeden proces lponechání si zdroje a čekání na další (hold and wait) •proces vlastnící alespoň zdroj čeká na získání dalšího zdroje, dosud vlastněného jiným procesem lbez předbíhání (no preemption) •zdroj lze uvolnit pouze procesem, který ho vlastní, dobrovolně po té, co daný proces zdroj dále nepotřebuje lkruhové čekání (circular wait) •existuje takový seznam čekajících procesů (P0, P1, …, Pn), že P0 čeká na uvolnění zdroje drženého P1, P1 čeká na uvolnění zdroje drženého P2, …, Pn-1čeká na uvolnění zdroje drženého Pn, a Pn čeká na uvolnění zdroje drženého P0 PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 32 Graf přidělení zdrojů ¢Resource-Allocation Graph, RAG ¢Množina uzlů V a množina hran E ¢uzly jsou dvou typů: lP= {P1, P2, …, Pn}, množina procesů existujících v systému lR = {R1, R2, …, Rm}, množina zdrojů existujících v systému ¢Hrana požadavku – orientovaná hrana Pi → Rj ¢Hrana přidělení – orientovaná hrana Rj → Pi ¢Proces: ¢ ¢Zdroj se 4 instancemi: ¢ ¢Proces Pi požadující prostředek Rj: ¢ ¢Proces Pi vlastnící prostředek Rj : ¢ Pi Pi Pi PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 33 Příklad RAG (bez cyklu) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 34 Příklad RAG (s uváznutím) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 35 Příklad RAG (bez uváznutí) PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 36 RAG: závěry ¢Jestliže se v RAG nevyskytuje cyklus – k uváznutí nedošlo ¢Jestliže se v RAG vyskytuje cyklus lexistuje pouze jedna instance zdroje daného typu → k uváznutí došlo lexistuje více instancí zdroje daného typu → k uváznutí může (ale nemusí) dojít PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 37 Problém uváznutí ¢Ochrana před uváznutím prevencí lzajistíme, že se systém nikdy nedostane do stavu uváznutí lzrušíme platnost některé nutné podmínky ¢Obcházení uváznutí ldetekce potenciální možnosti vzniku uváznutí a nepřipuštění takového stavu lzamezujeme současné platnosti všech nutných podmínek lprostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí) ¢Obnova po uváznutí luváznutí povolíme, ale jeho vznik detekujeme a řešíme ¢Ignorování hrozby uváznutí luváznutí je věc aplikace ne systému lzpůsob řešení zvolený většinou OS PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 38 Ochrana prevencí ¢Nepřímé metody lzneplatnění některé nutné podmínky •Virtualizací prostředků, ruším nutnost vzájemné výlučnosti při přístupu •požadováním všech prostředků najednou •odebíráním prostředků ¢Přímé metody lnepřipuštění platnosti postačující podmínky (cyklus v grafu) •uspořádání pořadí vyžadování prostředků PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 39 Prevence uváznutí (1) ¢Vzájemné vyloučení lpodmínka není nutná pro sdílené zdroje lu nesdílených zdrojů musí podmínka platit lřeší se např. virtualizací prostředků (např. tiskárny) ¢Ponechání zdrojů a čekání na další lpři žádosti o zdroje proces žádné zdroje „vlastnit“ nesmí lproces musí požádat o zdroje a obdržet je dříve než je spuštěn běh procesu ldůsledkem je nízká efektivita využití zdrojů a možnost stárnutí PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 40 Prevence uváznutí (2) ¢Zakázané předbíhání ljestliže proces držící nějaké zdroje a požadující přidělení dalšího zdroje, nemůže zdroje získat okamžitě, pak se uvolní všechny tímto procesem držené zdroje l„odebrané“ zdroje se zapíší do seznamu zdrojů, na které proces čeká lproces bude obnoven, pouze jakmile může získat jak jím původně držené zdroje, tak jím nově požadované zdroje ¢Zabránění kruhovému pořadí lzavedeme úplné uspořádání typů zdrojů a každý proces bude žádat o prostředky v pořadí daném vzrůstajícím pořadí výčtu PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 41 Obcházení uváznutí ¢Systém musí mít nějaké dodatečné apriorní informace ¢Nejjednodušší a nejužitečnější model požaduje, aby každý proces udal maxima počtu prostředků každého typu, které může požadovat ¢Algoritmus řešící obcházení uváznutí dynamicky zkouší, zda stav systému přidělování zdrojů zaručuje, že se procesy v žádném případě nedostanou do cyklické fronty čekání ¢Stav systému přidělování zdrojů se definuje počtem dostupných a přidělených zdrojů a maximem žádostí procesů PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 42 Detekce uváznutí ¢Umožníme, aby došlo k uváznutí ¢Ale toto uváznutí detekujeme ¢Aplikujeme plán obnovy ¢ PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 43 1 instance prostředku každého typu ¢Udržuje se graf čekání (wait-for graph) luzly jsou procesy lPi → Pj jestliže Pi čeká na Pj ¢Periodicky se provádí algoritmus, který v grafu hledá cykly ¢Algoritmus pro detekci cyklu v grafu požaduje provedení n2 operací, kde n je počet uzlů v grafu PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 44 Grafy ¢Graf přidělení zdrojů ¢Odpovídající graf čekání PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 45 Obnova: ukončení procesu ¢Násilné ukončení uváznutých procesů ¢Násilně se ukončuje jednotlivě proces po procesu, dokud se neodstraní cyklus ¢Čím je dáno pořadí násilného ukončení? lpriorita procesu ldoba běhu procesu, doba potřebná k ukončení procesu lprostředky, které proces použil lprostředky, které proces potřebuje k ukončení lpočet procesů, které bude potřeba ukončit lpreference interaktivních nebo dávkových procesů PB 169 Počítačové sítě a operační systémy ‹#› PB 169 Počítačové sítě a operační systémy 46 Obnova: nové rozdělení prostředků ¢Výběr oběti: minimalizace ceny ¢Návrat zpět (rollback) – návrat do některého bezpečného stavu, proces restartujeme z tohoto stavu ¢Stárnutí – některý proces může být vybírán jako oběť trvale lřešení: do cenové funkce zahrneme počet restartů (rollbacků)