Skip to main content

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
    danger

    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