Kalábovi

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== Plánování a synchronizace procesů, transakce ======
====== Proces ======
Proces je program v běhu, instance programu. O procesu OS ví, na jaké pozici proces je (instrukce, která má proběhnout), obsah registrů, zásobník na dočasná data, ... Toto je uložené ve struktuře, které se někdy říká Process Control Block (PCB).

====== Plánování procesů ======
Je to pěkne vysvětleno v [[https://www.fit.vutbr.cz/study/courses/IOS/public/IOS-opora.pdf|opoře k IOS]].

Na jednoprocesorovém stroji může najednou běžet pouze jeden program, tedy v rámci operačního systému pouze jeden proces. Jelikož často potřebujeme spouštět více procesů najednou, musí se tyto procesy o strojový čas procesoru dělit. O tom, jaký další proces bude spuštěn, rozhoduje tzv. **plánovač procesů**.

===== Plánovač procesů =====
Jde o krátkodobý plánovač (short-time scheduler), který vybírá proces na určitou dobu podle zvoleného algoritmu (viz dále).
==== Nepreemptivní plánování ====
O nepreemptivním plánování mluvíme, pokud k přepnutí procesů probíhá pouze za těchto okolností:

  - proces, který běží, se přepne ze stavu ''běžící'' do stavu ''čeká'' (např. I/O operace)
  - proces, který běží, se přepne ze stavu ''běžící'' do stavu ''připravený'' (např. při přerušení)
  - proces se přepne ze stavu ''čekající'' do stavu ''připravený'' (dokončení I/O operace)
  - proces se ukončí

Běžící proces při využití tohoto plánování drží procesor do té doby, dokud nenastane jeden z výše zmíněných případů. Jde o dnes nepoužívaný přístup, měly to tak třeba Win 3.x.

==== Preemptivní plánování ====
K přepnutí kontextu (procesu) se používá vnějšího podnětu (přerušení, typicky od časovače). Proces nemá kontrolu nad držením procesoru. K přepnutí však může stále dojít ve výše zmíněných případech. Tento přístup se běžně používá v moderních OS.

==== Plánovací kritéria ====
Způsob výběru dalšího procesu se liší podle přístupu:

  - **Maximální využití procesoru** -- plánovač se snaží zařídit co největší využití procesoru
  - **Propustnost** -- směrodatnou hodnotou je zde počet ukončených procesů za sekundu
  - **Doba běhu** -- plánovač vybírá podle součtu dobe nahrávání procesu do paměti, čekáním ve frontě připravených procesů, vykonáváním procesu a vykonáváním I/O operací
  - **Doba čekání** -- v tomto případě plánovač nepřerušuje právě běžící proces, pouze vybírá další proces na základě doby, jakou čekal ve frontě na přidělení procesoru
  - **Doba odezvy** -- důležité kritérium v aplikacích, které reagují na vnější podněty -- jde o dobu, jakou trvá odpověd na požadavek

Základním přístupem je maximalizovat využití procesoru a propustnost a minimalizovat dobu běhu, dobu čekání a dobu odezvy. Plánovač se například snaží dosáhnout průměrného využití procesoru na 70 %.

==== Plánovací algoritmy ====
=== First Come First Served (FCFS) ===
Jednoduché //kdo dřív přijde, ten dřív mele//. Nepreemptivní, nevhodný.

=== Shortest Job First ===
Proces, který se chystá obsadit procesor na nejkratší dobu, má prioritu. Při shodě se použije FCFS. Optimální algoritmus, ale blbé je, že musí odhadovat dobu dalšího běhu procesu. Obvykle se to extrapoluje z předchozích hodnot. Preemptivní nebo nepreemptivní -- podle toho, jestli při příchodu nového procesu přeruší nebo nepřeruší právě běžící proces.

=== Priority scheduling ===
Procesy mají přiřazenou prioritu, vyšší priorita má přednost (ale není jasně dané, jestli je nižší číslo vyšší prioritou, nebo zda je to naopak). Při stejné prioritě opět FCFS. SJF je vlastně prioritní, akorát prioritu počítá jako odhad doby trvání (priorita je inverzní k době trvání). Může být preemptivní i nepreemptivní. Preemptivní přístup při příchodu procesu s vyšší prioritou aktuální proces přeruší a zařadí ho do fronty. Nepreemptivní pouze vloží nově příchozí proces na začátek fronty, pokud má tedy větší prioritu.

=== Round-Robin ===
Jde o preemptivní variantu FCFS. Fronta procesu je kruhová (z konce se jde na začátek). Plánovač nastaví časovač, aby zavolal přerušení za 10--100 ms a vybere první proces z fronty. Po přerušení jde proces nakonec fronty a vybírá se další za začátku. Nově příchozí jdou také na konec fronty.

=== Víceúrovňové plánování ===
Jde o speciální algoritmus, který rozdělí procesy do několika kategorií. Každý proces je jen v jedné kategorii. Každá kategorie má jednu frontu a může mít svůj vlastní rozhodovací algoritmus, odlišný od ostatních kategorií. Kromě jednotlivých plánovačů nad těmtito kategoriemi existuje ještě jeden hlavní plánovač, který vybírá mezi frontami. Tento je obvykle implementován jako prioritní plánovač a každá kategorie (fronta) má svoji fixní prioritu. Druhý přístup je takový, že "důležitější" fronty dostanou větší podíl strojového času než méně důležité fronty.

==== Problémy spojené s prioritním plánováním ====
Proces, který má nízkou prioritu, se nemusí nikdy dostat ke slovu (//vyhladovění//). Nízkoprioritní proces také může mít alokovaný nějaký zdroj, ale nedostává se k procesoru přes vyšší priority, takže způsobí zablokování tohoto zdroje (//inverze priorit//).

Řešením v UNIXových systémech je následující přístup. U procesu je známo, jak má velké využití procesoru v poslední době. Čím větší využití, tím víc se mu postupně dynamicky snižuje priorita. Opačně to také platí. Důsledek: reakce interaktivních aplikací se zvyšuje, protože tyto žerou málo procesoru a tak jsou často spouštěny na procesoru.

FIXME mozna je to moc rozsahle, ale neni to zase moc podrobne, takze to staci snad jednou precist, hm?

===== Synchronizace procesů =====
Synchronizace paralelně prováděných procesů, vláken nebo jiných typů obsluhy (přerušení, ...) je náročnou úlohou. Setkáme se s ní při progamování aplikací, které využívají paralelní výpočty, nebo například když obsluhujeme systémové signály.
==== Časově závislá chyba ====
[[wp>Race condition]]

Anglicky **race condition**. Jde o chybu, která vzniká při souběžném přístupu více procesů ke sdíleným zdrojům (sdílená data, I/O). Jednoduchý příklad: jeden proces (A) navyšuje hodnotu nějaké proměnné o 1, druhý (B) hodnotu snižuje. Operace navýšení se do strojového kódu přeloží jako neatomická posloupnost instrukcí a může tedy dojít k následujícímu (počáteční hodnota je 5):

  A: register1 = N (5)
  A: register1 += 1
  B: register2 = N (5)
  B: register2 -= 1
  A: N = 4
  B: N = 6

Chyba je dost jasná -- výsledek je špatně.

==== Kritická sekce ====
[[wp>Critical section]]

Část programu, kde pracuje s nějakým sdíleným zdrojem (sdílená paměť), se nazývá **kritická sekce**. Takovou částí je například výše zmíněná proměnná N, ale taky například proměnná nebo I/O zdroj, který je používaný jak v samotném programu, tak v obsluze signálu -- ve chvíli přepnutí na obsluhu signálu totiž mohl program zrovna být uprostřed operace s tím zdrojem. Kritické sekce, které pracují se stejnými sdílenými zdroji, označujeme jako skupinu kritických sekcí.

U kritické sekce musíme zaručit:
  * vzájemné vyloučení -- nanejvýš jeden proces může pracovat s jednou skupinou kritických sekcí
  * dostupnost kritické sekce -- každý proces musí v konečném čase získat přístup do kritické sekce

Mohou nastat tři případy, kdy je kritická sekce nedostupná:
  - Uváznutí (deadlock) -- cyklická závislost, každý proces čeká před vstupem do krit. sekce na stav, který může nastat, jen kdyby nějaký jiný proces do sekce vstoupil
  - Blokování (blocking) -- proces čeká na podmínku, která nemůže nastat
  - Stárnutí (přesněji hladovění, starvation) -- tím rozumíme situaci, kdy nějaký proces do kritické sekce dlouhou dobu nevkročí, například v případě, že prostě jiné procesy do sekce vstupují s nějakou (klidně i náhodnou) předností. Toto je jediný případ, který se v některých případech toleruje
==== Řešení problému kritické sekce ====

=== Petersonův algoritmus ===
[[wp>Peterson's algorithm]]

Algoritmus řeší jak vzájemné vyloučení, tak dostupnost kritické sekce. Ve verzi pro dva procesy funguje tak, že každý proces před vstupem do kritické sekce nastaví jednak příznak, že má zájem o vstup do sekce a zároveň nastaví do sdílené proměnné ID druhého procesu, čímž mu dává najevo, že mu dává přednost. Pak ve smyčce aktivně čeká, dokud druhý proces má o sekci zájem nebo dokud mu druhý proces nedá přednost.

=== Bakery algoritmus ===
Jde o synchronizaci N procesů. Každý proces před vstupem do kritické sekce dostane lístek, který má číselnou hodnotu větší, než lístky všech ostatních procesů. Pokud se stejně stane, že mají dva procesy stejnou hodnotu lístku (neatomičnost přiřazování to umožňuje), rozhoduje PID procesu. Na řadu se dostane vždy proces s nejnižším štítkem.

=== Hardwarová podpora synchronizace ===
Na moderním hardware existují atomické instrukce pro nastavení nějaké proměnné, které lze použít k synchronizaci. Jde o instrukce //test and set//, která atomicky nastaví hodnotu v paměti na 1 (true) a vrátí původní hodnotu. Druhá instrukce je //swap//, která atomicky vymění hodnoty dvou proměnných.

Nevýhodou použití těchto instrukcí je to, že se při jejich použití v software využívá aktivního čekání, které zbytečně zatěžuje procesor.

=== Semafory ===
[[wp>Semaphore (programming)]]

Semafory jsou příkladem synchronizačního algoritmu, který nevyužívá aktivního čekání. Využívá sdílené proměnné, nad kterou existují atomické operace **lock** a **unlock**. Při locku se hodnota této proměnné snižuje, při unlocku se zvyšuje. Pokud je tato hodnota 0, je kritická sekce plně obsazená a žádný další proces nečeká na přístup. Pokud v takovém případě další proces zažádá o vstup do sekce, postaví se do fronty (eviduje to semafor) a záporná hodnota synch. proměnné semaforu ukazuje, jak je tato fronta dlouhá. Procesy, které jsou ve frontě semaforu, jsou obvykle pozastaveny a jsou obnoveny semaforem, když se kritická sekce uvolní. Semafor, který má kapacitu 1, se jmenuje **mutex**. Synchronizace kritické sekce v kódu jednotlivých procesů se dělá tak, že před vstupem proces zavolá lock a po výstupu unlock.

=== Monitory ===
[[wp>Monitor (synchronization)]]

Monitor je vysokoúrovňový nástroj pro synchronizaci. Jde prakticky o to, že se postaví sada funkcí, které pracují se sadou proměnných sychronně (pomocí semaforů) a my pak můžeme přes tyto operace s proměnnými pracovat, aniž bychom museli synchronizaci dál řešit. To předchází tomu, že bychom někde zapomněli synchronizaci provést a zároveň to šetří čas při vývoji. V praxi to většinou je zařízené objekty, které mají vnitřní proměnné a semafory. My pak pracujeme pouze s těmito objekty a s jejich metodami a vnitřní implementace těchto metod řeší synchro.

===== Shrnutí =====
  * proces, PCB, multitasking, přepínání kontextu
  * plánovač, plánovací kritéria, přístup k plánování
  * synchronizace procesů: petersonův algoritmus, bakery, atomické instrukce, aktivní čekání
  * semafory, monitory
Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Nástroje pro stránku
