Správa procesu

• Procesy patří mezi základní prostředky všech OS
• 3 základní pohledy procesů:
  1. Genetický pohled
     • Proces je instancí programu.
     • Program je nejčastěji reprezentován spustitelným souborem.
  2. Dynamický pohled
     • Proces je postupným vykonáváním instrukcí.
     • Proces ovlivňuje a může být ovlivňován prostředky.
     • Předpokládá změnu stavu, po provedení každé instrukce.
  3. Systémový pohled
     • Udržuje informace o užívaných prostředcích a jejich stavech.
     • Důležitou vlastností procesu je identifikace mezi ostatními procesy.
     • Systémové hledisko se promítá do dynamického.
• Závislost budoucích stavů na stavu aktuálním je velmi vysoká

Kontext procesu

• Sjednocení stavů všech prostředků OS, jež proces v daném okamžiku používá.
• Jak se budou chovat v krátké budoucnosti.

Determinismus

• Do kontextu procesu patří stavy všech prostředků u nichž je možnost, že by jejich změna mimo proces vedla ke změně chování programu
• Většina OS vyžaduje, aby dali najevo, jaké prostředky chtějí v budoucnu využívat
• Například do kontextu běžného programu mohou patřit stavy následujících prostředků (Procesor, Kódový paměťový region, Datový paměťový region, Zásobník, Paměť grafické karty, Paměť disku, buffery a registry zabudované do periferních zařízení, napůl vytištěná stránka v tiskárně, vypálené stopy na právě vypalovaném DVD).
• Velikost takto široce pojatého prostoru je v řádech MB -> GB.
• Kontext se musí ukládat i obnovovat v rámci přepínání procesů při multitáskingu a to by trvalo až vteřiny (nemožné).

Jak to vyřešit.

• Východiskem je skutečnost, že pokud je prostředek využíván výhradně jedním procesem (vyhrazený prostředek) není nutné jeho stav obnovovat a tím ani ukládat
• Důvodem je neměnnost stavu prostředku
• Úplného vyhražení dosáhneme pouze virtualizací prostředků
• Jsou 2 základní strategie při virtualizaci:
  • Rozdělení sdílených prostředků
    • Je užívána u většiny prostředků, neboť téměř vždy je možno prostředek virtuálně rozdělit na menší části, které mohou být přiděleny procesům do výhradního užívání
    • Příklady: paměťového zařízení na soubory, monitor rozdělen na okna
  • Strategie vyhrazených serverů
    • Užívána u prostředků, které lze obtížně rozdělit
    • V tomto případě se jeden z procesů stává výhradním vlastníkem prostředku
    • Jeho funkčnost nabízí nejčastěji ve formě fronty požadavků
    • Příklad: správa tiskárny tiskovým serverem (pouze proces server má přístup k tiskárně, další procesy musí využívat nepřímý prostředek - tiskovou frontu), DVD vypalovačka

Multitasking

• Správa procesů, která umožňuje existenci více nezávislých procesů v jednom okamžiku
• Efekt skutečného multitáskingu je při dostatečně rychlé výměně procesů (milisekundy) iluze souběžného běhu více procesů i na jednoprocesorových strojích

multitasking diagram

Vzájemné volání procesů

• Zastaralé, dobrý úvod do multitaskingu
• Na začátku existuje jeden proces (shell)
• Nový proces může vzniknout pouze v rámci volání služby jádra tímto procesem
• Volání pozastaví aktuální proces, uloží jeho kontext a vytvoří počáteční kontext nového procesu, kterému následně předá řízení
• Nyní běží jen tento nový proces, který po jisté době zavolá službu jádra exit, aby byl ukončen

S = sleeping, R = running, W = waiting, Z = Mátoha
stavový diagram procesů

Kooperativní multitasking

• K výměně procesů dochází když aktuální proces nemůže pokračovat v běhu -> čeká na splnění podmínky (nemůže ovlivnit, například stisk klávesy, nebo pohyb myši).
• Proces se vzdá procesoru pokud ho v danou chvíli nepotřebuje (dobrovolně-kooperativně).
• Systém musí zajistit, že běh procesu bude obnoven poté, co se podmínka stane pravdivou (nastane událost na niž proces čekal).
• Požadavky na OS:
  1. K výměně procesů může docházet pouze ve službách jádra (protože pouze jádro řídí přístup k prostředkům a zajišťuje komunikaci procesů).
  2. Rutina dispečer musí rozhodnout, který proces bude obnoven (protože může existovat více pozastavených procesů schopných běhu).
  3. Systém musí vyřešit i situaci, kdy neexistuje žádný proces schopný běhu (všechny čekají na událost), systém v takovém případě spouští idle proces, jenž v nekonečném cyklu volá dispečera, bez toho, že by cokoliv jiného provedl.
• Vhodný pro: procesy čekající v pravidelných intervalech na událost (stisk klávesy, příchod paketu, zpráva, odpověď).
• Nevhodný pro: procesy které si vystačí pouze s výpočty nad OP (vědecko technické výpočty).
• Největší nevýhoda: možnost časově neohraničeného držení procesoru jedním procesem (pokud proces omylem vstoupí do nekonečné smyčky, bez volání systémových služeb, pokud tato situace nastane, není postižen jenom daný proces, ale i všechny ostatní, včetně procesů systémových, neboť i ty již nikdy nezískají procesor).
• Z těchto důvodů se tyto systémy prosadily pouze z hlediska snadnější implementace a menších nároků na hardware

Preemtivní multitasking

• U KM může dojít k výměně procesů dojít pouze tehdy, čeká-li proces na externí událost a nepotřebuje tudíž procesor
• Existují však i další místa, v nich může potenciálně dojít k výměně procesů:
  1. Okamžik bezprostředně před návratem z libovolné služby jádra (jádro vždy uvolní nevyhrazené prostředky před skončením služby)
  2. Při návratu z obsluhy přerušení do uživatelského režimu (jen u přerušení, která byla vyvolána za procesu v uživatelském režimu)
• Důsledky této relativně malé změny strategie jsou obrovské

Klady

• Proces může být zbaven procesoru i nedobrovolně.
• Časovač: vyvolává přerušení (milisekundy), výměna procesů v pravidelných a krátkých intervalech.
• Povinná systémová správa všech hardwarových prostředků a jejich úplná virtualizace (proces může být v uživatelském režimu přerušen v libovolném okamžiku).
• Minimalizace časových závislostí mezi procesy -> nutnost virtualizace paměti.
• Dynamický systém priorit: Proces musí poskytovat informaci o nároku na využití procesoru
• Vynucené odebírání je spíše výjimkou.
• Převažuje kooperace, preempce jen tehdy, drží-li proces procesor příliš dlouho.
• Systém silněji zatížen procesy, které příliš navzájem nekomunikují (vědecko technické výpočty, multimediální aplikace)

Průběh:

• Každý proces získává procesor na určitý pevný časový interval (dán jeho statickou prioritou).
• Intervaly jsou krátké (desítky milisekund).
• time-slicing: sdílení času, které vytváří iluzi souběžného běhu procesů.
• Proces začíná ve stavu Nový a končí ve stavu Zombie
• Většinu života však proces stráví však ve dvou základních cyklech:
  • Wait
  • Running
    1. 2 podstavy
    2. RU (running user) nebo RK (running kernel)
    3. Delší cyklus navíc obsahuje stav Sleep[S] (proces čeká na externí událost)

Běžící proces stav running

• V jednoprocesorovém systému existuje právě jeden běžící proces.
• RU (running user) nebo RK (running kernel).
• Proces může opustit tento stav:
  • Dobrovolně (uspí se) => pokud čeká na systémovou událost.
  • Nedobrovolně (čeká) => pokud mu je odebrán procesor při přeplánování, řadí se do prioritní fronty.

Zablokovaný proces stav sleeping

• Dobrovolné vzdání procesoru, čeká na systémovou událost (stisk klávesy, příchod paketů).
• Při přechodu do stavu sleeping, by měl proces využívat minimum dalších prostředků.
• Ve stavu sleeping se může nachzet více procesů čekajících na stejný vyhrazený prostředek.
• Pro jejich uvolňování existují 2 mechanisny
  1. Fronta čekajících procesů => procesy čekající na prostředek jsou řazeny do fronty a po uvolonění prostředku je pouze první z nich (nejdéle čekající) odblokován.
  2. Probuďte se a předbíhejte => probuzeny jsou všechny procesy a o tom který proces prostředek získá rozhoduje absolutní priorita.

Proces mátoha stav zombie

• Procesy končí svůj život ve stavu zombie.
• Proces se do stavu zombie může dostat:
  1. Vražda
     • Proces je ukončen aktuálně běžícím procesem a do stavu Mátoha přechází ze stavu waiting nebo sleeping.
     • Vzájemné zabíjení procesů je omezené běžný uživatel smí zabíjet pouze své procesy.
  2. Sebevražda
     • Běžící proces zavolá systémovou službu pro své ukončení.
  3. Smrtelný úraz
     • Pokud program poruší ochranu paměti, použije v uživatelském režimu prvilegovanou instrukci, či se jinak snaží narušit stabilitu OS respektive jiných aktuálních procesů, může být nedobrovolně ukončen.
     • Aplikace je přerušena vyvoláním přerušení od procesoru (výjimkou), např. výpadkem stránky.
• Při přechodu do zombie jsou programu odebrány všechny prostředky.

Vlákna (threads)

• Preemptivní systémy -> paralelnost na úrovni všech procesů (ale ne stejných programů) -> nepohodlné a náročné na výpočetní prostředky.
• Řešením jsou vlákna
• Obdobná procesům, sdílejí datový region -> usnadňuje jejich vzájemné působení, komunikovace prostřednictvím globálních statických proměnných.
• Vlákna mají svou aktuální instrukci a zásobník a souběžně běží nad společnou pamětí.
• Hlavní nevýhoda je globální zablokování => jestliže dojde v jenom z vláken k zablokování procesu, jsou pozastavena i ostatní vlákna procesu.
• Vlákna procházejí stejnými stavy jako klasické procesy.
• Proces lze popsat jako množinu vláken sdílejících společný datový region.
• Každý proces má hlavní vlákno, které je vytvořeno během vzniku procesu a po přidělení prostředků prochází běžným stavovým cyklem.
• OS může na požádání (volání služby jádra) vytvořit pro proces nové vlákno, které začne vykonávat část programu v souběhu s ostatními vlákny procesu.
• Hlavní výhodou vláken je snadnější a efektivnější kooperace paralelních toků řízení -> umožňuje užití většího počtu souběžně běžících vláken bez výrazného zpomalení systému.

Synchronizace

Kritický kód a vzájemné vyloučení

• Pro preemptivní multitásking je typická téměř úplná vzájemná nezávislost procesů.
• Jedním z prostředků dosažením tohoto stavu je striktní oddělení tohoto prostředku užívaných jednotlivými procesy, což zcela brání kolizi procesů při jejich užívání.
• Tento ideální stav panuje pouze na uživatelské úrovni a to výhradně u procesů, které s okolními procesy nikdy nekomunikují. Zcela jiná situace je u rutin jádra, které přistupují ke sdíleným prostředkům -> vznikají chyby.
• 2 procesy:
  • Producent (P) -> zapisuje, generuje šifrovací klíče
  • Konzument (K) -> čte, používá klíče
• Spolupráce mezi těmito procesy nemusí fungovat (vznikají chyby)

Chyby

1. Čte dříve -> Konzument využívá prostředek, který ještě není k dispozici
2. Čte moc rychle -> Konzument přečte 2x či dokonce vícekrát tentýž klíč
3. Nestíhá číst -> Nepřečtení klíče z důvodů jeho bezprostředního přepsání producentem (konzument nestačí klíče dostatečně rychle číst)
4. Nejsložitější případ -> překryv zpráv (situace daná náhodných souběhem je komplikovaná, konzument přečte sdílenou paměť, která obsahuje fragmenty dvou klíčů, novějšího a staršího)

• Synchrozizace předchází kolizím daným
• Pokus o nesynchrozivanou komunikaci je potencionálně nebezpečný => kritický kód

2 základní typy synchronizace:

1. Čekání na událost
   • Proces čeká na událost, jež je výsledkem činnosti jiného procesu, synchronizace zajistí časovou následnost a zabrání propásnutí události čekajícím procesem
   • Tento typ řeší problémy dané rozdílnou rychlostí
   • Producenta a konzumenta
   • První 3 příklady s klíčem
2. Vzájemné vyloučení
   • Synchronizace musí zabránit současnému vykonávání dvou kritických kódů nad stejným prostředkem tj. pokud jeden proces vykonává kritický kód zahájil, nebo dokončil vykonávání první instrukce a ještě neprovedl instrukci poslední nesmí jiný proces vstoupit do kritického kódu nad týmž prostředkem

info

oba typy synchronizace lze kombinovat

Synchronizační prostředky

Binární samafór

• Sdílený logický prostředek, dva stavy (červená, zelená)
  • WAIT: pokud je semafor ve stavu zelená, je bezprostředně přepnut do stavu červená, jinak proces vyčká změny stavu na zelenou (Ta je provedena voláním operace signál jiným procesem a až poté změní sám stav semaforu na červenou, stav semaforu je změněn na zelenou)
  • SIGNAL: stav samafóru je nastaven na zelenou.
• Aby byl semafor funkční, musí se testování hodnoty semaforu a jeho nastavení v operaci dít atomicky tj. nesmí být přerušeno přepnutím kontextu.
• Kromě požadavku na atomičnost si zpracování v jádře vynucuje i požadavek na zablokování a odblokování procesu, které musí být provedeno rutinou jádra.

MUTEX

Mutual exclusion

• Může být uvolněn pouze procesem, který daný MUTEX drží (vstoupil přes něj do kritického kódu).
• Je určen dvěma hodnotami:
  1. Identifikátor procesu, jenž MUTEX drží ( pokud takový proces existuje, jinak není tato hodnota definována )
  2. Počet uzamčení MUTEXU nad nímž jsou definovány 2 atomické operace.
• LOCK
  • uzamčení/získání MUTEXU
  • Je-li MUTEX volný proces se stává držitelem MUTEXU a počet uzamknutí nabývá hodnoty 1
  • Je-li vlastněn aktuálním procesem, je pouze zvýšen počet uzamknutí
  • Je-li MUTEX vlastněn jiným než aktuálním procesem, je proces zablokován a čeká na uvolnění MUTEXU
• UNLOCK
  • odemčení/uvolnění MUTEXU
  • Je-li MUTEX volný, je chování nedefinováno
  • Je-li vlastněn aktuálním procesem, zmenšuje se počet uzamknutí o 1 a jel-li poté nulový je MUTEX uvolněn a jeden z čekajících procesů je odblokován
  • Je-li MUTEX vlastněn jiným než aktuálním procesem, je chování nedefinováno, ale MUTEX není v žádném případě uvolněn
• Základním pravidlem je absolutní zamezení držení MUTEXU více procesy najednou.
• I Mutex musí být implementován jako semafor na úrovni jádra a musí být zaručena atomičnost operací.
• Použití Mutexu: je používán pro zajištění vzájemného vyloučení nad kritickým kódem.
• Hlavní výhodou ve srovnání s BS je snažší použíti, především v rozsáhlejších projektech dané požností vícnásobného zamykání.
• Základním rozdílem mezi Mutexem a Událostí je bezestavový charakter události (událost si nepamatuje svůj stav a je dostupná na uživatelské úrovni).
• Jak tedy zajistit, aby ty procesy navazovali a nepřekrývali se?
  • Řešením je použití sdílené stavové proměné, která ukazuje dosažený stav (nastavována je prvním procesem a testována druhým)
  • Protože nastavování ani testování není atomickou čiností, musí být obě činosti chráněni Mutexem

Uváznutí (deadlock)

• Je trvalé zablokování procesů, při chybném použití synchronizačních prostředků
• Proces, který získal samafór, opětovně zavolá operaci WAIT
• Dělíme na skupiny podle závažnosti
  1. Chybná synchronizace navždy zablokuje proces, (bez ukončení nemohou ukončit stav SLEEP) označujeme jako uváznutí (DEADLOCK).
     • Výše zmíněný příklad patří do skupiny méně nebezpečných, uváznutí tohoto typu vznikají důsledkem hrubých chyb v použití synchronizačních prostředků, označují se jako triviální.
  2. Druhou a nebezpečnější skupinu uváznutí, tvoří uváznutí vzniklá nepříznivým souběhem dvou procesů -> když 2 procesy používají 2 společné prostředky, může nastávat po dnech (Obtížně se detekují)

Odstranění uváznutí

1. Nejjednušší metoda -> vyloučení překrytí kritických kódů, lze splnit pouze pokud není vyžadováná přímá spolupráce několika prostředků.
2. Pořadí procesů -> správné pořadí jejich alokace
   warning

   Větší časová závislost kvůli povinnému pořadí -> výrazné zpomalení

3. Vše nebo nic -> proces se pokusí získat všechny prostředky, které potřebuje a když se mu to nepovede, všechny prozatím uvolní (musí mít podporu v jádře).
4. Detekce potencionálního uváznutí (Predikce)
   • Bohužel příliž defenzivní a náročný na čas (nepoužívá se)
   • Nejznámější algoritmus je Bankéřův algoritmus