Počítačové sítě a operační systémy Jaromír Plhák, 15.3.2016PB169 Počítačové sítě a operační systémy Jaromír Plhák xplhak@fi.muni.cz Synchronizace procesů Uváznutí PB169 Počítačové sítě a operační systémy Snímek 2 z 57 Paralelní běh procesů (1) • Synchronizace běhu procesů – Jeden proces čeká na událost z druhého procesu • Komunikace mezi procesy – Komunikace – způsob synchronizace, koordinace různých aktivit – Může dojít k uváznutí • Každý proces čeká na zprávu od nějakého jiného procesu – Můž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 PB169 Počítačové sítě a operační systémy Snímek 3 z 57 Paralelní běh procesů (2) • Sdílení prostředků – Procesy používají a modifikují sdílená data – Operace zápisu musí být vzájemně výlučné – Operace zápisu musí být vzájemně výlučné s operacemi čtení – Operace čtení mohou být realizovány souběžně – Pro zabezpečení integrity dat se používají kritické sekce PB169 Počítačové sítě a operační systémy Snímek 4 z 57 Soupeření souběžných aktivit • Souběžné procesy se ucházejí o zdroje - procesor, FAP, globálně dostupné periferie, soubory dat, ... • Zdroje soupeřícím procesům typicky přiděluje OS • OS efektivně isoluje soupeřící procesy, aby se chybně neovlivňovaly • Soupeřící procesy se vzájemně neznají, soupeřící proces si není vědom existence ostatních soupeřících procesů • Realizace procesů musí být deterministická, reprodukovatelná, procesy musí být rušitelné a restartovatelné bez bočních efektů PB169 Počítačové sítě a operační systémy Snímek 5 z 57 Kooperace souběžných aktivit • Kooperující procesy sdílí jistou množinu zdrojů, vzájemně se znají • Kooperace se dosahuje buďto implicitním sdílením zdrojů nebo explicitní komunikací kooperujících procesů • Proč vlákna/procesy kooperují – Aby mohly sdílet jisté zdroje – Aby se mohly nezávislé akce řešit souběžně, např. čtení příštího bloku dat během zpracovávání již přečteného bloku dat • Vlákna jednoho procesu obvykle kooperují, nesoupeří • Procesy mohou jak kooperovat, tak i soupeřit PB169 Počítačové sítě a operační systémy Snímek 6 z 57 Problém konzistence • 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 PB169 Počítačové sítě a operační systémy Snímek 7 z 57 Problém konzistence - příklad (1) • Souběžný přístup ke sdíleným údajům se musí mnohdy provádět neatomickými operacemi • Příklad neatomické operace nad sdílenými proměnnými void echo() { chin = getchar(); chout = chin; putchar( chout) ; } • Procesy P1 a P2 provádějí tutéž proceduru echo a operují se sdílenými proměnnými chin, chout • Oba procesy lze přerušit ve kterémkoliv místě • O rychlosti postupu každého z procesů nelze nic předpovědět PB169 Počítačové sítě a operační systémy Snímek 8 z 57 Problém konzistence - příklad (2) • Příklad možného průběhu procesu P1 a P2 P1 P2 . . . . . . chin = getchar(); . . . . . . chin = getchar(); chout = chin; . . . . . . chout = chin; putchar(chout); . . . . . . putchar(chout); . . . . . . • Znak načtený v P1 se ztrácí dříve než je zobrazený • Znak načtený v P2 se vypisuje v P1 i P2 PB169 Počítačové sítě a operační systémy Snímek 9 z 57 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; PB169 Počítačové sítě a operační systémy Snímek 10 z 57 Producent-konzument (2) • Producent item nextProduced; while (1) { while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; } PB169 Počítačové sítě a operační systémy Snímek 11 z 57 Producent-konzument (3) • Konzument item nextConsumed; while (1) { while (counter == 0) ; /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; } PB169 Počítačové sítě a operační systémy Snímek 12 z 57 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é – counter++; – counter--; • count++ v assembleru může vypadat – register1 = counter – register1 = register1 + 1 – counter = register1 • count-- v assembleru může vypadat – register2 = counter – register2 = register2 – 1 – counter = register2 PB169 Počítačové sítě a operační systémy Snímek 13 z 57 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: – producer: register1 = counter (register1 = 5) – producer: register1 = register1 + 1 (register1 = 6) – consumer: register2 = counter (register2 = 5) – consumer: register2 = register2 – 1 (register2 = 4) – producer: counter = register1 (counter = 6) – consumer: counter = register1 (counter = 4) • Výsledná hodnota proměnné counter bude 4 (nebo 6), zatímco správný výsledek má být 5. PB169 Počítačové sítě a operační systémy Snímek 14 z 57 Race condition • Race condition (podmínka soupeření): – Více procesů současně přistupuje ke sdíleným zdrojům a manipulují s nimi – Konečnou hodnotu zdroje určuje poslední z procesů, který zdroj po manipulaci opustí • Ochrana procesů před negativními dopady race condition – Je potřeba procesy synchronizovat PB169 Počítačové sítě a operační systémy Snímek 15 z 57 Problém kritické sekce (KS) • 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: – Je potřeba zajistit, že v kritické sekci, sdružené s jistým zdrojem, se bude nacházet nejvýše jeden proces PB169 Počítačové sítě a operační systémy Snímek 16 z 57 Modelové prostředí • Pro hledaní řesení problému kritické sekce – Předpokládá se, že každý proces beží nenulovou rychlostí – Nic se nepředpokládá o relativní rychlosti procesu – Žádný proces nezůstane v kritické sekci nekonečně dlouho PB169 Počítačové sítě a operační systémy Snímek 17 z 57 Podmínky řešení problému KS (1) • Podmínka vzájemného vyloučení (mutual exclusion), podmínka bezpečnosti, „safety“ – Jestliž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“ – Jestliž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 PB169 Počítačové sítě a operační systémy Snímek 18 z 57 Podmínky řešení problému KS (1) • Podmínka konečnosti doby čekání (bounded waiting), podmínka spravedlivosti, „fairness“ – Musí 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 – Předpokládáme, že každý proces běží nenulovou rychlostí – O relativní rychlosti procesů nic nevíme PB169 Počítačové sítě a operační systémy Snímek 19 z 57 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“ PB169 Počítačové sítě a operační systémy Snímek 20 z 57 Řešení problému KS (1) • Softwarová řešení – Algoritmy, jejichž správnost se nespoléhá na žádné další předpoklady – S aktivním čekáním „busy waiting“ • Hardwarová řešení – Vyžadují speciální instrukce procesoru – S aktivním čekáním PB169 Počítačové sítě a operační systémy Snímek 21 z 57 Řešení problému KS (2) • Řešení zprostředkované operačním systémem – Potřebné funkce a datové struktury poskytuje OS – S pasivním čekáním – Podpora v programovacím systému/jazyku • Semafory, monitory, zasílání zpráv PB169 Počítačové sítě a operační systémy Snímek 22 z 57 Petersonův algoritmus • Proces Pi do { flag [i]:= true; turn = j; while (flag [j] and turn == j) /* do nothing */; critical section flag [i] = false; remainder section } while (1); • Jsou splněny všechny první dvě podmínky správnosti řešení problému kritické sekce PB169 Počítačové sítě a operační systémy Snímek 23 z 57 Synchronizační hardware (1) • Speciální instrukce strojového jazyka – Test_and_set, exchange / swap, … • Stále zachována idea používání „busy waiting“ • Test_and_set – Testování a modifikace hodnoty proměnné – atomicky boolean TestAndSet (boolean &target) { boolean rv = target; target = true; return rv; } PB169 Počítačové sítě a operační systémy Snímek 24 z 57 Synchronizační hardware (2) • Swap – Atomická výměna dvou proměnných void Swap (boolean &ra, boolean &rb) { boolean temp = a; a = b; b = temp; } PB169 Počítačové sítě a operační systémy Snímek 25 z 57 Využití TestAndSet • Sdílená data (inicializováno na false): boolean lock: • Proces Pi do { while (TestAndSet(lock)) ; critical section lock = false; remainder section } PB169 Počítačové sítě a operační systémy Snímek 26 z 57 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 } PB169 Počítačové sítě a operační systémy Snímek 27 z 57 Situace bez podpory OS • Nedostatek softwarového řešení – Procesy, 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 – Výhody • Vhodné i pro multiprocesory (na rozdíl od prostého maskování/povolení přerušení) – Nevý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) PB169 Počítačové sítě a operační systémy Snímek 28 z 57 Semafory • Synchronizační nástroj, který lze implementovat i bez „busy waiting“ – Proces je (operačním systémem) „uspán“ a „probuzen“ – Tj. ř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--; PB169 Počítačové sítě a operační systémy Snímek 29 z 57 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); PB169 Počítačové sítě a operační systémy Snímek 30 z 57 Uváznutí a stárnutí • Uváznutí – Dva nebo více procesů neomezeně dlouho čekají na událost, kterou může generovat pouze jeden z čekajících procesů – Nechť S a Q jsou dva semafory inicializované na 1 P0 P1 wait(S); wait(Q); wait(Q); wait(S);   signal(S); signal(Q); signal(Q) signal(S); • Stárnutí – Neomezené blokování, proces nemusí být odstraněný z fonty na semafor nikdy (předbíhání vyššími prioritami, …) PB169 Počítačové sítě a operační systémy Snímek 31 z 57 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ý – Semafor 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) signal(x) ... ... ... wait(x) signal(y) signal(x) PB169 Počítačové sítě a operační systémy Snímek 32 z 57 Problém uváznutí (1) • 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 – V systému existují 2 páskové mechaniky – Procesy 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é PB169 Počítačové sítě a operační systémy Snímek 33 z 57 Problém uváznutí (2) • Příklad 2 – Semafory A a B, inicializované na 1 P1 P2 wait (A); wait(B) wait (B); wait(A) PB169 Počítačové sítě a operační systémy Snímek 34 z 57 Problém uváznutí - soupeření o zdroj (1) • Auta (procesy) soupeří o výhradní získání prostoru pro přejezd křižovatky (zdroj) PB169 Počítačové sítě a operační systémy Snímek 35 z 57 Problém uváznutí - soupeření o zdroj (2) PB169 Počítačové sítě a operační systémy Snímek 36 z 57 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í – Preempce 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í PB169 Počítačové sítě a operační systémy Snímek 37 z 57 Definice uváznutí a stárnutí • Uváznutí – Množ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í – Pož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. PB169 Počítačové sítě a operační systémy Snímek 38 z 57 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) PB169 Počítačové sítě a operační systémy Snímek 39 z 57 Charakteristika uváznutí (1) • K uváznutí dojde, když začnou současně platit 4 následující podmínky – Vzájemné vyloučení (mutual exclusion) • Sdílený zdroj může v jednom okamžiku používat pouze jeden proces – Ponechá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 PB169 Počítačové sítě a operační systémy Snímek 40 z 57 Charakteristika uváznutí (2) – Bez předbíhání (no preemption) • Zdroj lze uvolnit pouze procesem, který ho vlastní, dobrovolně poté, co daný proces zdroj dále nepotřebuje – Kruhové č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 PB169 Počítačové sítě a operační systémy Snímek 41 z 57 Graf přidělení zdrojů (1) • Resource-Allocation Graph, RAG • Množina uzlů V a množina hran E • Uzly jsou dvou typů: – P= {P1, P2, …, Pn}, množina procesů existujících v systému – R = {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 PB169 Počítačové sítě a operační systémy Snímek 42 z 57 Graf přidělení zdrojů (2) • Proces: • Zdroj se 4 instancemi: • Proces Pi požadující prostředek Rj: • Proces Pi vlastnící prostředek Rj : Pi Pi Pi PB169 Počítačové sítě a operační systémy Snímek 43 z 57 Příklad RAG (bez cyklu) PB169 Počítačové sítě a operační systémy Snímek 44 z 57 Příklad RAG (s uváznutím) PB169 Počítačové sítě a operační systémy Snímek 45 z 57 Příklad RAG (bez uváznutí) PB169 Počítačové sítě a operační systémy Snímek 46 z 57 RAG: závěry • Jestliže se v RAG nevyskytuje cyklus – k uváznutí nedošlo • Jestliže se v RAG vyskytuje cyklus – Existuje pouze jedna instance zdroje daného typu → k uváznutí došlo – Existuje více instancí zdroje daného typu → k uváznutí může (ale nemusí) dojít PB169 Počítačové sítě a operační systémy Snímek 47 z 57 Problém uváznutí • Ochrana před uváznutím prevencí – Zajistíme, že se systém nikdy nedostane do stavu uváznutí – Zrušíme platnost některé nutné podmínky • Obcházení uváznutí – Detekce potenciální možnosti vzniku uváznutí a nepřipuštění takového stavu – Zamezujeme současné platnosti všech nutných podmínek – Prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí) • Obnova po uváznutí – Uváznutí povolíme, ale jeho vznik detekujeme a řešíme • Ignorování hrozby uváznutí – Uváznutí je věc aplikace ne systému – Způsob řešení zvolený většinou OS PB169 Počítačové sítě a operační systémy Snímek 48 z 57 Ochrana prevencí • Nepřímé metody – Zneplatně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 – Nepřipuštění platnosti postačující podmínky (cyklus v grafu) – Uspořádání pořadí vyžadování prostředků PB169 Počítačové sítě a operační systémy Snímek 49 z 57 Prevence uváznutí (1) • Vzájemné vyloučení – Podmínka není nutná pro sdílené zdroje – U nesdílených zdrojů musí podmínka platit – Řeší se např. virtualizací prostředků (např. tiskárny) • Ponechání zdrojů a čekání na další – Při žádosti o zdroje proces žádné zdroje „vlastnit“ nesmí – Proces musí požádat o zdroje a obdržet je dříve než je spuštěn běh procesu – Důsledkem je nízká efektivita využití zdrojů a možnost stárnutí PB169 Počítačové sítě a operační systémy Snímek 50 z 57 Prevence uváznutí (2) • Zakázané předbíhání – Jestliž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 – „Odebrané“ zdroje se zapíší do seznamu zdrojů, na které proces čeká – Proces 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í – Zavedeme ú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 PB169 Počítačové sítě a operační systémy Snímek 51 z 57 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ů PB169 Počítačové sítě a operační systémy Snímek 52 z 57 Obcházení - příklad PB169 Počítačové sítě a operační systémy Snímek 53 z 57 Detekce uváznutí • Umožníme, aby došlo k uváznutí • Ale toto uváznutí detekujeme • Aplikujeme plán obnovy PB169 Počítačové sítě a operační systémy Snímek 54 z 57 1 instance prostředku každého typu • Udržuje se graf čekání (wait-for graph) – Uzly jsou procesy – Pi → 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 PB169 Počítačové sítě a operační systémy Snímek 55 z 57 Grafy • (a) Graf přidělení zdrojů • (b) Odpovídající graf čekání PB169 Počítačové sítě a operační systémy Snímek 56 z 57 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í? – Priorita procesu – Doba běhu procesu, doba potřebná k ukončení procesu – Prostředky, které proces použil – Prostředky, které proces potřebuje k ukončení – Počet procesů, které bude potřeba ukončit – Preference interaktivních nebo dávkových procesů PB169 Počítačové sítě a operační systémy Snímek 57 z 57 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 – Řešení: do cenové funkce zahrneme počet restartů (rollbacků)