Počítačové sítě a operační systémy C:\Users\xplhak\Desktop\filogo.png Jaromír Plhák, 5.3.2018 PB169 Počítačové sítě a operační systémy Jaromír Plhák xplhak@fi.muni.cz Synchronizace procesů Uváznutí • Uváznutí je patologický situace C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 Já to nějak naprogramuju … obtížně odladitelné … Minule jsme si ukazovali příkladek, kdy se paralelní vlákna ovlivňovala (sdílejí stejný paměťový prostor) = změnil se nekorektně obsah proměnnné … Je nám jedno, jestli se jedná o proces nebo vlákno C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • Mějme program, kde si čteme nebo zapisujeme nějaká data ze souboru. Čteme a najednou se rozhodne do souboru zapisovat písař. Je přirozený požadavek, aby při zápisu nečetl soubor nikdo jiný (nebo nedejbože do něj zapisoval). Nevadí, že je více čtenářů ale nesmí číst … C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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ů Procesy se neperou přímo. Zadávají požadavky na OS a nějaký arbitr v OS rozhodne, na základě priorit (časového pořadí apod.) komu bude ten zdroj přidělen. OS musí izolovat procesy (neměly být vůbec o sobě vědět) – je jedno, kolik jich bude (deset, tisíc, libovolně), ale jen jeden musí být jako vítěz Boční efekt – jestli si dá něco do výhradního vlastnictví a dojde k nějaké chybě … musí být zajištěno, že zdroj bude uvolněn a bude přidán do banku dostupných zdrojů C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 Druhá forma kooexistence procesů/vláken Posíláme si nějaké signály a informace, které nám budou koordinovat běh procesů C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 v kterémkoliv místě •O rychlosti postupu každého z procesů nelze nic předpovědět Manipulují s daty neatomickými informacemi = mohou být kdykoliv přerušeny. Načte znak, přepíše ho a vypíše. Kdykoliv přerušit … před provedení, po provedení. Nevíme, jak rychle běží … C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 Pro jednoduchost je to monoprocesor. Chceme, aby procedura byla řešena jako kritická sekce. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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; Jeden generuje data do sdílené paměti a druhý je odebírá … Můžeme mít dva procesy, například file server. Mezi procesy definujeme sdílenou (vyrovnávací) paměť do které jedno vlákno vkládá (produkuje) data a druhé je odebírá (konzumuje). Velikost paměti je omezená. Koordinace zajištěna přes synchronizaci sdílené paměti. Jedno vlákno (konzument) zastaví činnost v momentě, kdy bude paměť prázdná a producent, pokud bude naplněná na maximum. A zase se obnoví činnost producenta, pokud konzument něco odebere. Je to cyklický buffer (abych nezasahoval do jiného místa v paměti, než mám přiděleno). In je ukazatel producenta (kam může zapisovat) Out je ukazatel konzumenta (odkud může odebírat) C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Producent-konzument (2) •Producent • • item nextProduced; • while (1) { • while (counter == BUFFER_SIZE) • ; /* do nothing */ • buffer[in] = nextProduced; • in = (in + 1) % BUFFER_SIZE; • counter++; • } Nedělej nic znamená, že může být dán mezi připravené a čekám než budeš znovu aktivován C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Producent-konzument (3) •Konzument • • item nextConsumed; • while (1) { • while (counter == 0) • ; /* do nothing */ • nextConsumed = buffer[out]; • out = (out + 1) % BUFFER_SIZE; • counter--; • } C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 Na první pohled jednoduché programy … ale co to znamená inkrementuj count C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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. –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. • Po druhém kroku je potlačen a konzument může běžet, protože v paměti něco vygenerováno. Ani 4 ani 6 není správně. Chci, aby posloupnost instrukcí pro increment (a dekrement) nešla přerušit. Je mi jedno, v jakém pořadí proběhnou, ale chci aby proběhly postupně po jedné. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Čtenáři a písaři (1) •Operace zápisu do sdíleného zdroje musí být exklusivní, vzájemně vyloučené s jakoukoli jinou operací •Operace čtení mohou čtený zdroj sdílet •Libovolný počet procesů-čtenářů muže číst jeden a tentýž zdroj současně •V jednom okamžiku smí daný zdroj modifikovat pouze jeden proces-písař •Jestliže proces-písař modifikuje zdroj, nesmí ho současně číst žádný proces-čtenář •Čtenář není konzument, písař není producent –Jde o jinou úlohu C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Čtenáři a písaři (2) •Čtenáři a písaři s prioritou čtenářů –První čtenář přistupující ke zdroji zablokuje všechny písaře –Poslední z čtenářů končící čtení zdroje uvolní přístup ke zdroji, případně čekajícímu některému písaři –Písaři mohou stárnout •Čtenáři a písaři s prioritou písařů –První čtenář přistupující ke zdroji zablokuje všechny písaře –První písař žádající o vstup do kritické sekce dalším čtenářům zakáže přístup ke zdroji –Čtenáři mohou stárnout C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • Když spustím n procesů, tak mne může předběhnout jen n-1 procesů C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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“ • Před vstupem musíme provést nějakou operaci nebo službu tak, aby se zajistili první dvě podmínky, ideálně i ta třetí a po provedení KS za musí dát vědět, že ji dokončil a umožnil tak vstup do KS jinému procesu Neustále se na urovni instrukcniho repertoaru dotazuji, jestli muzu vstoupit do KS. Maskování přerušení si můžu dovolit jen na počítači s jedním procesorem. Po vyřešení KS by uvolnil přerušení. Ale nejsem schopen maskovat přerušení na více procesorech – není obecné řešení C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Ř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 • I když budu mít více procesorů, tak mám společnou sběrnicí … a když se více procesorů se bude snažit zapsat do stejné buňky paměti, tak na úrovni vstupu do paměti dojde k náhodné serializaci. Já nevím v jakém pořadí (bude tam jedna nebo druhá hodnota). Na tomhle principu jsou ta softwarová řešení. Když se instrukce interpretuje, tak má možnost zablokovat vstup nikoliv nejen na jeden cyklus na dva cykly. Já možnost si něco přečíst a zároveň něco změnit. Mám tedy speciální instrukci, která se chová jinak než ostatní a díky zablokování procesoru na dva cykly nám umožní implementovat vstup do KS. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Ř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 • Odpoutání od busy waitingu. Dám vědět OS, že chci do KS. Když není volno, tak jsem ve frontě čekajících a až se vstup do KS uvolní, tak OS mne zařadí mezi připravené procesy a mohu opětovně žádat o vstup do KS. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 Řešení z 80. let (trvalo cca 10 let) Sdílí společnou fyzickou paměť a pole příznaků pro každý proces a jednu pomocnou proměnnou (která říká – jeden ano, druhý ne). Oba procesy mohou pracovat se vším. Proces nejprve označí v poli na svém indexu, že chce přístup do kritické sekce (bude true). Jakmile to sdělí, tak se ověří, že v KS není druhý proces. Pokud tam bude, tak se bude neustále dotazovat, jestli může vstoupit … a až ten druhý proces bude opouštět KS, tak změní svůj příznak na false. Problém by byl, kdyby se oba nahodili na true (při paralelním zpracování) … po přerušení po nastavení příznaku. Proto je použitá proměnná turn. Která říká, že dává přednost tomu druhému procesu (ikdyž jsou oba true). Ikdyž to udělají paralelně, tak výsledek bude 0 nebo 1 (i nebo j) – náhodně, nevíme která. Nemůžeme zaručit spravedlivost (rozhoduje náhoda). Jeden proces může stárnout. Když jsou KS řídké (a KS jsou rychlé) = dlouhé intervaly, kdy nikdo nežádá o vstup = je i spravedlivý. Vlákno neuvázne, ale může stárnout. Pettersonův alg. Se používá dodnes. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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; • } • Instrukce, které umožní zablokovat pamět na dva cykly (nikdo jiný se k ní nedostane) Test and set = testuj a uzamkni zámek. Podívá se do paměti, získá z paměti z proměnné lock hodnotu a zároveň s tím získáním hodnoty nastaví, že je zamčeno. Jestliže provádím dotaz, zdali je možné vstoupit do KS, tak se dozvím, že je zamčeno a zároveň nechám nastaveno na hodnotě zamčeno (bez možnosti aby to měnil někdo jiný). Pokud bylo odemčeno, tak je po provedení nastaveno na zamčeno a já jsem jeden jediný, který se dozví, že je odemčeno. Představte si, že prográmek řeší vstup pomocí TaS C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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; • } • Exchange výměna = mám dvě paměťová místa a chci vyměnit jejich obsah. Nehraji obsah jednoho do pomocného registru a pak je přes něj prohodit. Registr a paměťová buňka v nedělitelném cyklu přečte hodnotu do registru a obsah registru nahraje zpět do paměti a do paměti se nedostane žádná jiná instrukce (než se provede výměna těch dvou paměťových míst). C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Využití TestAndSet •Sdílená data (inicializováno na false) • boolean lock = false; •Proces Pi • do { • while (TestAndSet(lock)) ; • critical section • lock = false; • remainder section • } • Když je zamčeno, stále nastavuji na lock … busy waiting C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Využití Swap •Sdílená data (inicializováno na false) • boolean lock = false; • boolean waiting[n]; •Proces Pi • • do { • key = true; • while (key == true) • swap(lock, key); • critical section • lock = false; • remainder section • } • C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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) C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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--; • Celá řada OS poskytuje na aplikačním rozhraní nástroj semafor (zvednutý nebo shozený). Jako klasický semafor = když vjedu shodím dolu, jak vyjedu ho dám nahoru. Synchronizační proměnná, která může být shozená nebo zvednutá. K čemu si ho aplikace využijí je věc dizajnu aplikací … to OS nepodporuje. Používáme semafory (takového a takového čísla) pro nějaký účel a je na kooperujících procesech (musí se domluvit) aby se domluvili, na jak )učel jej používají. Podobně jako porty u TCP/IP – je domluveno jak se daný port používá Pokud požaduji zdroj a semafor je dole, tak jsem uspán a dán do fronty procesů čekající na daný semafor. Jakmile je zvednut, tak jsem dán mezi připravené a mohu žádat o přístup ke zdroji (do KS). To se mu ale nemusí podařit, protože do připravených jsou dány všechny čekající procesy na semafor. Pote zase spadnout do fronty čekající na semafor … mohu nějak implementovat zvyšování instrukce (aby byla splněna spravedlnost) – teoreticky můžu vyhnat ven pouze jeden proces, ale většinou se to nedělá a nechá se to na plánovači OS, který proces vybrat C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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); Může být obecný (vyšší kladné číslo). Třeba pět tiskáren, S nastaven na 5 a postupně snižuji. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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); • M M • signal(S); signal(Q); • signal(Q) signal(S); •Stárnutí –Neomezené blokování, proces nemusí být odstraněný z fronty na semafor nikdy (předbíhání vyššími prioritami, …) • Acqiure a release musí být mezi sebou výlučné (KS na úrovni jádra), nemohou probíhat souběžně. Jelikož drží nějaký zdroj, může generovat uváznutí. Semafor nemusí být použit jen pro ošetřování vstupu do KS, ale může být použitý jako snychronizátor. Tato úloha je časově závislá. Musí to probíhat paralelně přesně tak jak je to napsané. Jakmile se něco předběhne, tak je to ok  (ale my to neumíme říct, jak to časově bude probíhat = tězko detekovatelná chyba. OS většinou nenabízí obecné semafory, jen binární. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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) Jsou to nástroje nízké úrovně Na vyšší úrovni jsou monitory, případně dalším synchronizačním nástrojem je mailbox a zasílání zpráv (pošli zprávu, příjmi zprávu). Synchronním způsobem čekám na zprávu a jakmile jiný proces pošle asynchronním způsobem zprávu, tak pak můžu reagovat. Monitor – jazyková konstrukce na úrovni vyšších programovacích jazyků. Je sdílený současně definovanými činnostmi. Sdílený zdroj je uložený uvnitř toho monitoru (a monitor je obálka) a má metody, které pracuji s tímto sdíleným zdrojem. Ty metody zajišťují, že v jednom čase s daným zdrojem pracuje jen jedna metoda jednoho procesu (semafor skrytý v monitoru – pokud je požadavek na další metodu, tak je frontuje na vstupu do monitoru. Po zvednutí semaforu se zas může provést nějaká jiná procedura). Splnění podmínek je schováno na úrovni monitoru. Uvnitř monitoru můžeme definovat podmínkové proměnné – proces který řeší proceduru si může otestovat, jestli bude na podmínku bude čekat (proces vnitřně opustí monitor – ale monitor si ho zapamatuje) ale kdykoliv jiný proces změní tuto podmínku, tak je proces probuzen monitorem (pomocí procedury signal … pokud nikdo nečeká, tak prázdná operace jinak dříve než monitor pustí do monitoru další proces z vnějšku, tak vezme ten uspaný proces a probudí o a pustí ke zdroji) Semafor, Monitor a zasílaní zprávu mají stejnou sílu – lze implementovat libovolným způsobem (je na nás – otázka citu – který použijeme). Semafory jsou na nízké úrovni (ovládám si je sám), takže je tam náchylnost k chybám. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 alokaci druhé • Chybně provedená synchronizace. Deadlock. Definice = existuje … C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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) • C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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) C:\Users\User1\Disk Google\Flash\!!Lektor\Vyuka\PB169\PrezentacePrednasky\img\09_uvaznuti1.jpg Prevence bude tomu bránit … nesmíš pokračovat C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Problém uváznutí – soupeření o zdroj (2) • C:\Users\User1\Disk Google\Flash\!!Lektor\Vyuka\PB169\PrezentacePrednasky\img\09_uvaznuti2.jpg Není to umělý příklad C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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í • • • • • • • • • • • Scénář ilustrující deadlock = může být zavedena politika, že pravý se vždycky vracet – ale pokud bude dlouhá řada aut zleva, tak pravý bude furt vracen (pokud třeba neřekneme, že po x cykles dostanou přednost auta zprava) Preempce (předběhnutí) a návrat C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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. • Bankéřův algoritmus – obcházení ubváznutí. Já ti ten zdroj nedám, protože kdybych ti ho dal, tak by mohlo dojít k uváznutí (ale nemuselo). Prevence – eleminace možnosti vzniku uváznutí Obcházení – vím, že tam možnost vzniku je, ale zajistím, aby se v průběhu cesty do nevstoupilo do stavu, kdy nastane deadlock Detekce – nástroje nám umožní zjistit deadlock a řešíme to – eliminace procesů a odebrání jejich zdrojů C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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) • C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • První tři podmínky jsou podmínky nutné = tj. aby došlo k uváznutí, musí tyhle podmínky platit. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • Poslední podmínka je postačující – pokud nastane, tak došlo k uváznutí. Buď eleminujeme nutné podmínky nebo zabraňujeme cyklickému čekání. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • Modelování přes grafovou strukturu. Který reprezentuje zdroje přiřazované procesům C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 Můžeme mít více instancí jednoho zdroje – 3 tiskárny, mohou je dostat do držení tři procesy. Proces ten zdroj bere jako realizaci KS. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Příklad RAG (bez cyklu) P3 v konečné čase skončí a uvolní prostředek C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Příklad RAG (s uváznutím) • Stačí aby P3 požádala o zdroj R2 a jsme v … uváznutí C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Příklad RAG (bez uváznutí) • Cyklus sám o sobě nemusí znamenat uváznutí. Stačí, aby těch zdrojů bylo více instancí. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • Žádný univerzální OS žádný RAG neřeší. Pokud chceme zajistit řešení takových patologických jevů, tak nemůžeme spoléhat na OS (může to být nějaký middleware mezi OS a aplikací). C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • -Poskytneme virtuální tiskárnu (soubor na disku) a nějaký output writer bude sériově ty zdroje tisknout -Kdybych ti ho dal,m mohlo by dojit k uvaznuti – zeptej se za chvili = nedostaneme se do stavu splneni všech tri nutnych podminek -Nějaký middleware spustí algoritmus, který vyhodnutí, jestli dochází k uváznutí a předá lidskému uživateli k řešení -Pštrosí politika je ve všech univerzálních OS (když dojde jednou za rok k uváznutí, tak se hold nedá nic dělat a řeší to uživatel) C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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ů • Přidělím všechny prostředky do poslopunosti. Nejdřív musíš přidelit tiskárnu, potom pásku, potom … takže alespoň jeden z nich dostane všechny prostředky = neefektivní využití zdrojů (1. zdroj použiju až po hodině běhu, ale znemožňuje jeho alokaci jiným prostředkům) C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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í • Ale každý prostředek nelze virtualizovat C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 • Zase snížená efektivita C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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ů Všechny podmínky jsou zachovány … ale jejich uplatnění nebude v čase najednou (jinak prevence) Musí vědět, jak se procesy budou chovat (predikce) – mohu to udělat na začátku a ten proces nespustit = špatně (ale pak nemusím řešit dynamicky) Proces deklaruje = Já budu chtít tolik a tolik paměti, tolik a tolik tiskáren, tyto a tyto soubory (nechci je teď, ale je chtít kdykoliv poději). Nemusím nechat spustit proces, pokud nemám dostatek prostředků (předpokládám, že všichni uplatní svá maxima najednou) – velmi konzervativní. Bankéřův algoritmus = půjčky do výše maxima. Bankéř má zdroje. Půjčí jen tehdy, pokud vznikne možnost přidělit požadavek a mám ještě dostatek zdrojů, ikdyby všichni chtěli svá maxima půjčit najednou. Nepůjčím znamená počkej než nějaký proces skončí a pak se uvolní nějaké zdroje (ale neřeknu, jak dlouho budu na půjčku čekat). Udržuje systém v bezpečném stavu (maximum pro každý proces – přidělené je menší než volné prostředky), tj. existuje bezpečná posloupnost procesu P1, P2, …, Pn = pozadavky kazdeho Pi lze uspokojit pra ve volnymi zdroji a zdroji drzenymi vsemi Pj , j < i. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Bankéřův algoritmus (1) •Princip –Bankéř = OS –Zákazník = proces –Peníze = prostředky –Měna = typ prostředku –Suma = počet instancí prostředků • C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Bankéřův algoritmus (2) •Nový zákazník deklaruje max. částku v každé měně, kterou si chce půjčit •Pokud zákazník dostal všechny peníze, vrátí je v konečném čase •Půjčku může zákazník čerpat postupně. Pokud bankéř zjistí, že půjčení právě požadované částky nevede k bezpečnému stavu pokladny, zákazník musí čekat, dokud jiný zákazník nevrátí dostatek peněz •Stav je bezpečný, pokud bankéř dokáže aplikací pravidel 2. a 3. uspokojit potřeby všech zákazníků v konečném čase C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Obcházení – příklad • D:\Users\Jarek\Disk Google\Flash\!!Lektor\Vyuka\PB169\PrezentacePrednasky\img\bank.jpg Nepřidělím, protože by nebyl bezpečný C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Detekce uváznutí •Umožníme, aby došlo k uváznutí •Ale toto uváznutí detekujeme •Aplikujeme plán obnovy Na úrovni middlewaru rozpoznávám. Jestli v nějakém intervalu nebo se překročil nějaký časový limit k danému procesu a spustí se algoritmus, který zjistí, jestli nedošlo k uváznutí. Udržujeme graf čekání (hledáme cyklus) C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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 Kvadratická složitost – ubírá výkon C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Grafy •(a) Graf přidělení zdrojů •(b) Odpovídající graf čekání • • C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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ů • Pokud proces má běžet 4 hodiny a již má 3:59 za sebou, tak bude až poslední na řadě apod. Přednost mají interaktivní procesy (tj. ruší se spíše dávkové). C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 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ů) • Oběť určuje návrhář aplikace Problém rušení procesů – obyvkle se neřeší návratem na iniciální stav, ale na bezpečný stav. Dělají se tzv. checkpointy (když mám dost místa na vnější paměti) a vracím se k poslednímu checkpointu. Řešení stárnutí řeší aplikace. C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Večeřící filozofové (1) •5 filozofů buď myslí nebo jí –Jí špagety jen 2 vidličkami –Co se stane, když se všech 5 filozofů najednou chopí např. levé vidličky ? •… zemřou hladem •Hledáme řešení – rituál/protokol zajišťující ochranu před uváznutím a stárnutím C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Večeřící filozofové (2) •Zrušení symetrie –Jeden filozof je levák, ostatní jsou praváci –Levák se liší pořadím získávání vidliček •Strava se podává n filozofům v jídelně s (n – 1) židlemi –Vstup do jídelny hlída obecný semafor iniciálně nastavený na kapacitu n – 1 –Řešení chránící jak před uváznutím, tak i před stárnutím C:\Users\xplhak\Desktop\filogo.png PB169 Počítačové sítě a operační systémy Snímek ‹#› z 64 Večeřící filozofové (3) •Filozof smí uchopit vidličky pouze když jsou obě (jeho levá i pravá) volné –Musí je uchopit uvnitř kritické sekce, pro řešení lze použít monitor –Definuje se vektor n podmínkových proměnných (čekání na vidličku) •N dle počtu filozofů –Definuje se vektor indikující stav vidličky (true = volná) –Definují se dvě monitorové procedury pro získaní a uvolnění 2 vidliček –Uváznutí nehrozí, v monitoru může by pouze jeden filozof