OSY Flashcards
Proces
• Instance spuštěného programu.
o Program je posloupnost instrukcí definující chování procesu, která obsahuje globální data
• Slouží k alokování prostředků (adresový prostor, otevřené soubory, … ).
• Jádro udržuje informace o procesu (ID, identita, informace o rodiči a potomcích,…).
Vznik nového procesu/
Nové procesy vytváří již existující procesy systémovým voláním:
• Unix: fork(), exec()
• Windows: CreateProcess()
Vytvoření:
• OS inicializuje v jádře datové struktury spojené s novým procesem
• OS nahraje kód a data programu z disku do paměti a vytvoří
prázdný systémový zásobník pro main vlákno.
Klonování:
• OS zastaví aktuální proces a uloží jeho stav.
• OS inicializuje v jádře datové struktury spojené s novým procesem.
• OS udělá kopii aktuálního kódu, dat, zásobníku, stavu procesu, …
Spustenie procesu - fork()
• Vytvoří nový proces, který je kopií procesu, z kterého byla tato funkce zavolána.
• Kódový segment sdílí potomek s rodičem.
• Datový a zásobníkový segment vznikají kopií dat a zásobníku rodiče.
• Nový proces má jiné PID a PPID, ostatní vlastnosti dědí (např. EUID, EGID, prostředí), nebo sdílí s rodičem
soubory, …).
• V rodičovském procesu vrací funkce PID potomka (chyba -1), v potomkovi 0.
Spustenie procesu - exec()
• V procesu, ze kterého je funkce volána, spustí nový program (obsah původního procesu je přepsán novým
programem).
• Atributy procesu se nemění (PID, PPID, …).
Spustenie procesu - wait()
- Umožňuje v rodičovském procesu počkat na dokončení potomka.
- Funkce zablokuje rodičovský proces, ve kterém je zavolána, dokud se jeden potomek neukončí.
Ukončenie procesu
• Normal exit (dobrovolné) - proces dokončí svou práci a použije OS volání exit(), aby řekl OS, že končí.
• Error exit (dobrovolné) – pomocí exit() při fatální chybě (např. žádný vstupní soubor,…)
• Fatal error (nedobrovolné) – OS násilně ukončí proces díky chybě (často chyba v programu)
• Ukončení jiným procesem (nedobrov.) - proces použije OS volání - např. kill(), aby řekl OS o ukončení jiného
procesu
Implementace procesu
• OS spravuje tabulku (seznam struktur), která se nazývá tabulka procesů, s jednou položkou pro jeden proces,
nazývanou process control block (PCB).
• PCB obsahuje informace o procesu a jeho vláknech, které jsou nutné pro správu procesů a vláken.
• Velikost tabulky procesů se obvykle odvozuje od konfigurace systému (např. od velikosti fyzické paměti).
process control block (PCB)
• Informace pro identifikaci procesu (process identification)
o Jméno procesu, číslo procesu (PID), rodičovský proces
(PPID), vlastník procesu (EUID, RUID, SUID), seznam vláken
• Stavové informace procesoru pro každé vlákno
o Hodnoty viditelných registrů CPU.
o Hodnoty řídících a stavových registrů CPU (program
counter, program status word (PSW), status information
o Ukazatel na zásobník, …
• Informace pro správu vlákna/procesu
o Vlákno: stav, priorita, informace nutné pro plánování,
informace o událostech na které vlákno čeká
o Proces: informace pro mezi-procesovou komunikaci, správu paměti (ukazatel na tabulku stránek),
alokované a používané prostředky (otevřené soubory, …)
Vlákno
Nejmenší sekvence (posloupnost) instrukcí, které lze nezávisle spravovat plánovačem. Neboli vlákno je část výpočtu, které je přidělován CPU (jeho jádro)
• Jádro alokuje pro každé vlákno:
o zásobník (pro historii výpočtu a lokální proměnné)
▪ ostatní prostředky a identita jsou sdíleny
o a udržuje aktuální hodnoty registrů (pro opětovné spuštění). Tedy vlastní:
▪ hodnotu čítače instrukcí
▪ hodnoty CPU registrů (pro uchování informace o výpočtu)
Proces s více vlákny
- Jednotlivá vlákna v daném procesu nejsou nezávislá tak jako jednotlivé procesy.
- Všechny vlákna v procesu sdílí stejný adresový prostor, stejné otevřené soubory, potomky, reakce na signály
Vytvoření a ukončení vlákna
- Procesy se spouští standardně s jedním vláknem.
- Toto vlákno může vytvářet další vlákna pomocí knihovní funkce (např pthread_create()).
- Když chce vlákno skončit, může se opět ukončit pomocí knihovní fce (např pthread_exit()).
Přepínání kontextu
• V systému je omezený počet jader CPU -> Přepínání kontextu
• Vlákna se na jednotlivých jádrech střídají tak, že každé vlákno může běžet na přiděleném jádru po určitou
dobu. Po uplynutí této doby bude vlákno přerušení a nahrazeno jiným.
Stavy vlákien
- vytvoření procesu/vlákna
- spuštění vlákna na jádru CPU
- pozastavení vlákna po uplynutí časového kvanta
- pozastavení vlákna kvůli čekání na událost (IO,…)
- odblokování vlána po tom co nastala událost
- vlákno čeká až rodič převezme jeho exit code
- ukončení vlákna
Idle 1> Ready 2> Running 3> Ready (4> Blocked 5> Ready) 2> Running 6> Zombie 7> Free
Časově závislé chyby
- Dva nebo několik procesů/vláken používá (čte/zapisuje) společné sdílené prostředky
- Výsledek výpočtu je závislý na přepínání kontextu jednotlivých vláken, které používají sdílené prostředky.
- Velmi špatně se detekují.
- Př: 2 uživatelé editují stejný soubor
Kritické sekce
• Část programu, kde procesy používají sdílené prostředky (paměť, proměnné, soubor, …)
• Sdružené kritické sekce: kritické sekce dvou a více procesů týkající se stejného sdíleného prostředku
• Vzájemné vyloučení: procesům není dovoleno sdílet ve stejném čase 1 prostředek a nesmí se nacházet ve
sdružených sekcích současně
Implementace vláken
V uživatelském prostoru:
• Run-time system: množina funkcí, která spravuje vlákna.
• Vlákna jsou implementována pouze v uživatelském prostoru.
• V jádru jsou implementovány procesy (jedno-vláknové procesy).
• Jádro o dalších vláknech nemá žádné informace.
• Výhody:
o Vlákna mohou být implementována v OS, které nepodporuje vlákna.
o Rychlé plánování vláken uvnitř procesu.
o Každý proces může mít svůj vlastní plánovací algoritmus.
• Nevýhody:
o Jak budou implementována blokující systémová volání?
o Co se stane když dojde k výpadku stránky?
o Žádný clock interrupt uvnitř procesu (jedno vlákno může okupovat CPU během celého časového
kvanta procesu).
o Špatná efektivita na SMP architektuře.
V prostoru jádra:
• Procesy i vlákna jsou implementovány v jádru.
• Výhody:
o Žádný problém s blokujícími systémovými voláními.
• Nevýhody:
o Vytváření, ukončování a plánování vláken je
pomalejší.
Hybridní:
• Jádro se stará pouze o kernel-level threads a plánuje je.
• Některé kernel-level threads mohou mít user-level threads.
• User-level threads jsou vytvářená, ukončovaná a plánovaná
uvnitř procesu.
Plánování vláken
Při přidělování CPU vláknům jádro OS (scheduler) rozhoduje:
• Které vlákno poběží.
• Na kterém CPU/jádru.
• Kdy poběží a jak dlouho.
Strategie plánování:
• bez předbíhání - vlákno běží dokud nepožádá o nějakou službu jádro nebo neskončí (vlákno běží dle libosti)
• s předbíháním - běžící vlákno je zablokováno automaticky po uplynutí časového kvanta
Typy plánování dle použitého systému:
Interaktivní systémy:
• Round-robin
o strategie předbíhání
o vlákna čekají ve frontě než se dostanou na řadu
▪ po uplynutí přiděleného CPU času se zařadí na konec fronty.
• Prioritní plánování
o Každé vlákno má prioritu, „ready“ vlákna jsou seskupena do tříd dle priority
o CPU je přidělováno vláknům z aktuálně nejvyšší prioritní třídy metodou round-robin
Dávkové:
• First-Come First-Served - plánování bez předbíhání pomocí jedné FIFO fronty vláken
o Jednoduché, minimalizace času na přepínání kontextu
o Může zpomalit vlákna orientovaná na V/V
Synchronizační nástroje
Problémy při paralelních výpočtech
• Bez použití synchronizace
o Časově závislé chyby (race conditions) = situace kdy více vláken přistupuje (read/write) ke sdílenému
objektu a výsledek je závislý na přepínání kontextu
• Se synchronizací
o Uváznutí (deadlock) = situace, kdy několik vláken čeká na událost, kterou může vyvolat pouze jedeno z
čekajících vláken
o Livelock = situace, kdy několik vláken vykonává neužitečnou práci (mění svůj stav), ale nemohou
postoupit k vykonávaní užitečné práce
o Hladovění (starvation) = situace, kdy ready vlákno je předbíháno a nedostane se k prostředkům.
Různé úrovně synchronizačních nástrojů
• Hardware (zákaz přerušení - DI)
• Kernel space ( atomické operace, zámky)
• User space (pipes, signály, semafory)
Zákaz přerušení (DI):
• CPU je přidělováno postupně jednotlivým vláknům za pomoci přerušení od časovače nebo jiného přerušení.
• Vlákno zakáže všechna přerušení před vstupem do kritické sekce a opět je povolí po opuštění kritické sekce.
Nevýhody:
• DI od jednoho uživatele blokuje i ostatní uživatele
• Ve víceprocesorovém systému DI má efekt pouze na aktuálním CPU
• Zpomalí reakce na přerušení
Užitečné uvnitř jádra a na jednoprocesorovém systému (ale jen na krátký čas), nevhodné pro běžná user vlákna
