‹#›/23 PB153 Operační systémy a jejich rozhraní Uváznutí 09 ‹#›/23 lExistuje 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 lPří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é lPříklad 2 ●Semafory A a B, inicializované na 1 ● P0 P1 ●wait (A); wait(B) ●wait (B); wait(A) PROBLÉM UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lMost s jednosměrným provozem lKaždý vjezd mostu lze chápat jako zdroj lDojde-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) lPři řešení uváznutí se může vracet i více vozů lMůže docházet ke stárnutí PŘÍKLAD: ÚZKÝ MOST PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 ANIMACE ÚZKÉHO MOSTU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lUvá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 lStá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. DEFINICE UVÁZNUTÍ A STÁRNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lTypy zdrojů R1, R2, …, Rm ●tiskárna, paměť, I/O zařízení, … lKaždý zdroj Ri má Wi instancí lKaždý proces používá zdroj následujícím způsobem 1.žádost 2.použití 3.uvolnění (v konečném čase) MODEL PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lK 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 ●bez 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 ●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 CHARAKTERISTIKA UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lResource-Allocation Graph, RAG lMnožina uzlů V a množina hran E luzly 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 lHrana požadavku – orientovaná hrana Pi → Rj lHrana přidělení – orientovaná hrana Rj → Pi lProces: l lZdroj se 4 instancemi: l lProces Pi požadující prostředek Rj: l lProces Pi vlastnící prostředek Rj : l GRAF PŘIDĚLENÍ ZDROJŮ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ Pi Pi Pi ‹#›/23 PŘÍKLAD RAG (BEZ CYKLU) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 R1 R3 R2 R4 ‹#›/23 PŘÍKLAD RAG (S UVÁZNUTÍM) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 R1 R3 R2 R4 ‹#›/23 PŘÍKLAD RAG (BEZ UVÁZNUTÍ) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P1 P2 P3 P4 R1 R2 ‹#›/23 lJestliže se v RAG nevyskytuje cyklus – k uváznutí nedošlo lJestliž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 RAG: ZÁVĚRY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lOchrana 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 lObchá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í) lObnova po uváznutí ●uváznutí povolíme, ale jeho vznik detekujeme a řešíme lIgnorování hrozby uváznutí ●uváznutí je věc aplikace ne systému ●způsob řešení zvolený většinou OS PROBLÉM UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lNepří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ů lPří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ů OCHRANA PREVENCÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lVzá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) lPonechá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í PREVENCE UVÁZNUTÍ (1) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lZaká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 lZabrá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 PREVENCE UVÁZNUTÍ (2) PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lSystém musí mít nějaké dodatečné apriorní informace lNejjednodušší 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 lAlgoritmus ř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í lStav systému přidělování zdrojů se definuje počtem dostupných a přidělených zdrojů a maximem žádostí procesů OBCHÁZENÍ UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lUmožníme, aby došlo k uváznutí lAle toto uváznutí detekujeme lAplikujeme plán obnovy l DETEKCE UVÁZNUTÍ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lUdržuje se graf čekání (wait-for graph) ●uzly jsou procesy ●Pi → Pj jestliže Pi čeká na Pj lPeriodicky se provádí algoritmus, který v grafu hledá cykly lAlgoritmus pro detekci cyklu v grafu požaduje provedení n2 operací, kde n je počet uzlů v grafu 1 INSTANCE PROSTŘEDKU KAŽDÉHO TYPU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lGraf přidělení zdrojů lOdpovídající graf čekání GRAFY PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ P5 R1 R3 R4 R5 R2 P1 P2 P3 P4 P5 P1 P2 P3 P4 (a) (b) ‹#›/23 lNásilné ukončení uváznutých procesů lNásilně se ukončuje jednotlivě proces po procesu, dokud se neodstraní cyklus lČí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ů OBNOVA: UKONČENÍ PROCESU PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 lVýběr oběti: minimalizace ceny lNávrat zpět (rollback) – návrat do některého bezpečného stavu, proces restartujeme z tohoto stavu lStárnutí – některý proces může být vybírán jako oběť trvale ●řešení: do cenové funkce zahrneme počet restartů (rollbacků) OBNOVA: NOVÉ ROZDĚLENÍ PROSTŘEDKŮ PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ ‹#›/23 Windows: řetězec čekání (1) PB 153 Operační systémy a jejich rozhraní ‹#›/23 Windows: řetězec čekání (2) PB 153 Operační systémy a jejich rozhraní ‹#›/23 lDriver verifier – Deadlock detection (viz MSDN) ●When Deadlock Detection finds a violation, it will issue bug check 0xC4. The first parameter of this bug check will indicate the exact violation. Possible violations include: ●Two or more threads involved in a lock hierarchy violation ●A resource that is released out of sequence ●A thread that tries to acquire the same resource twice (a self-deadlock) ●A resource that is released without having been acquired first ●A resource that is released by a different thread than the one that acquired it ●A resource that is initialized more than once, or not initialized at all ●A thread that is deleted while still owning resources ● Windows: nástroje pro vývojáře PB 153 Operační systémy a jejich rozhraní ‹#›/23 Windows Applications: Best Practices PB 153 Operační systémy a jejich rozhraní Users like responsive applications. When they click a menu, they want the application to react instantly, even if it is currently printing their work. When they save a lengthy document in their favorite word processor, they want to continue typing while the disk is still spinning. Users get impatient rather quickly when the application does not react in a timely fashion to their input. A programmer might recognize many legitimate reasons for an application not to instantly respond to user input. The application might be busy recalculating some data, or simply waiting for its disk I/O to complete. However, from user research, we know that users get annoyed and frustrated after just a couple of seconds of unresponsiveness. After 5 seconds, they will try to terminate a hung application. Next to crashes, application hangs are the most common source of user disruption when working with Win32 applications. Zdroj: MSDN ‹#›/23 Windows Applications: Best Practices PB 153 Operační systémy a jejich rozhraní Do: •Design a lock hierarchy and obey it. Add all the necessary locks. There are many more synchronization primitives than just Mutex and CriticalSections; they all need to be included. Include the loader lock in your hierarchy if you take any locks in DllMain() •Agree on locking protocol with your dependencies. Any code your application calls or that might call your application needs to share the same lock hierarchy •Lock data structures not functions. Move lock acquisitions away from function entry points and guard only data access with locks. If less code operates under a lock, there is less of a chance for deadlocks •Analyze lock acquisitions and releases in your error handling code. Often the lock hierarchy if forgotten when trying to recover from an error condition •Replace nested locks with reference counters - they cannot deadlock. Individually locked elements in lists and tables are good candidates •Be careful when waiting on a thread handle from a DLL. Always assume that your code could be called under the loader lock. It's better to reference-count your resources and let the worker thread do its own cleanup (and then use FreeLibraryAndExitThread to terminate cleanly) •Use the Wait Chain Traversal API if you want to diagnose your own deadlocks Do not: •Do anything other than very simple initialization work in your DllMain() function. See DllMain Callback Function for more details. Especially do not call LoadLibraryEx or CoCreateInstance •Write your own locking primitives. Custom synchronization code can easily introduce subtle bugs into your code base. Use the rich selection of operating system synchronization objects instead •Do any work in the constructors and destructors for global variables, they are executed under the loader lock Zdroj: MSDN ‹#›/23 Výukovou pomůcku zpracovalo Servisní středisko pro e-learning na MU http://is.muni.cz/stech/ PB 153 Operační systémy a jejich rozhraní