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).

Je to pěkne vysvětleno v 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ů.

Jde o krátkodobý plánovač (short-time scheduler), který vybírá proces na určitou dobu podle zvoleného algoritmu (viz dále).

O nepreemptivním plánování mluvíme, pokud k přepnutí procesů probíhá pouze za těchto okolností:

1. proces, který běží, se přepne ze stavu běžící do stavu čeká (např. I/O operace)
2. proces, který běží, se přepne ze stavu běžící do stavu připravený (např. při přerušení)
3. proces se přepne ze stavu čekající do stavu připravený (dokončení I/O operace)
4. 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.

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.

Způsob výběru dalšího procesu se liší podle přístupu:

1. Maximální využití procesoru – plánovač se snaží zařídit co největší využití procesoru
2. Propustnost – směrodatnou hodnotou je zde počet ukončených procesů za sekundu
3. 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í
4. 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
5. 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 %.

Jednoduché kdo dřív přijde, ten dřív mele. Nepreemptivní, nevhodný.

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.

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.

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.

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.

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.

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

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.

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ě.

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á:

1. 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
2. Blokování (blocking) – proces čeká na podmínku, která nemůže nastat
3. 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

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.

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.

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.

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.

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.

• 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