Obsah

AP5, IN5 Operační systémy

Architektury operačních systémů, rozhraní operačních systémů. Procesy, synchronizace procesů, uváznutí a metody ochrany proti uváznutí. Práce s pamětí, logický a fyzický adresový prostor, správa paměti a způsoby jejího provádění.

Architektury operačních systémů, rozhraní operačních systémů

Generické komponenty OS

Architektury

Podle architektury operačního systému se typicky rozlišuje:

Rozhraní

Procesy

Proces

Význam procesu v OS

Data nutná pro spravování procesu

Stavy procesu

Synchronizace procesů

Se souběžně běžícími procesy se můžeme setkat buď v přímo paralelním prostředí, kde je jedna paměť sdílena více procesy, nebo v prostředí distribuovaném, kde má každý proces vlastní lokální paměť. Hlavním problémem výskytu souběžných procesů je sdílení prostředků (paměť, zařízení, soubory, atd.) Tento problém se vyskytuje dokonce i v mnohouživatelských OS, kdy se např. řeší sdílení paměti mezi hlavní linií výpočtu v jádře a obslužnou rutinou přerušení při I/O operaci. Především při sdíleném přístupu do paměti nebo do souboru mohou vznikat neočekávané problémy – časové závislé chyby.

Vzájemné vyloučení

Vzájemné vyloučení je prostředek, jak zamezit dvěma procesům, aby zároveň přistupovaly k určitým datům nebo prováděly současně určité operace. Jedná se obvykle o funkce, po nichž požadujeme, aby je jeden proces provedl celé sám bez přerušování jinými procesy. Obecně se těmto funkcím říká kritické sekce. Kritické sekci obvykle předchází tzv. preludium (vstup do KS) – místo soupeření procesů o vstup – a je ukončena tzv. postludiem (výstup z KS) – kritická sekce je opět uvolněna pro jiný proces.

Kritická sekce

Problémem kritické sekce je umožnit přístup ke kritické oblasti procesům, které o to usilují, při dodržení následujících podmínek:

Pokud o přístup do kritické sekce usiluje některý proces v době, kdy je v ní jiný proces, případně o přístup usiluje v jednom okamžiku více procesů, je nutné některé z nich pozdržet. Toto pozdržení je možné realizovat smyčkou. Toto tzv. aktivní čekání (busy waiting) však zbytečně spotřebovává čas CPU - je možné čekající proces zablokovat a obnovit jeho běh až v okamžiku, kdy proces, který je v kritické sekci, tuto sekci opustí.

Nástroje a algoritmy pro vzájemné vyloučení

Sdílené vzájemné vyloučení

Jedná se o exkluzivní vzájemné vyloučení operací zápisu s jakoukoli jinou operací a sdílené čtení. U tohoto typu vzájemného vyloučení se objevuje také další typ úloh – tzv. úloha o čtenářích a písařích.

Úloha o čtenářích a písařích

Uváznutí

Množina procesů P uvázla, jestliže každý proces Pi z P čeká na událost (uvolnění prostředků, zaslání zprávy), kterou vyvolá pouze některý z procesů P.

Nutná a postačující podmínka uváznutí

Bezpečný stav

Stav je bezpečný, jestliže systém může alokovat zdroje každému procesu (v mezích maximálního počtu) v nějakém pořadí a zároveň nenastane deadlock (uváznutí). Formálně, systém je v bezpečném stavu, jestliže existuje bezpečná sekvence. Sekvence procesů <P1, P2, …, Pn> je bezpečná pro aktuální stav alokace, jestliže každému procesu Pi mohou být přiděleny požadované zdroje ze zdrojů volných + zdrojů držených procesy Pj, kde j < i. Za této situace, pokud zdroje požadované procesem Pi nejsou momentálně volné, potom Pi čeká, dokud nejsou ukončeny všechny procesy Pj. V momentě, kdy dokončeny jsou, Pi může dostat všechny požadované zdroje, splnit svou úlohu, zdroje uvolnit a skončit. Je-li proces Pi ukončen, může dostat všechny požadované zdroje proces Pi+1 atd. Pokud v systému neexistuje bezpečná sekvence, říkáme o něm, že není bezpečný.

Metody ochrany proti uváznutí

Detekce uváznutí

„každý dostává co chce kdy chce“, OS periodicky testuje existenci uváznutí (detekce cyklu v grafu), klady: žádný prostoj při zahájení, zápory: nutnost řešit uváznutí a posteriori

Způsoby řešení uváznutí

Algoritmus prevence uváznutí

Základní myšlenkou je zajistit, aby systém byl neustale v bezpečném stavu. Na počátku systém v bezpečném stavu pochopitelně je. V okamžiku, kdy proces žádá zdroj, který je aktuálně volný, musí systém rozhodnout, zda procesu zdroj přidělí, nebo ho nechá čekat. Zdroj může byt procesu přidělen pouze v případě, ze systém i po přiděleni zůstane v bezpečném stavu.

Bankéřův algoritmus

Příklad

Uvazujme system s peti procesy P0 az P4 a tri zdroje typu A, B, C.
  • Zdroj typu A ma 10 instanci
  • zdroj typu B ma 5 instanci
  • zdroj typu C 7 instanci

Necht v case t0 je system v nasledujicim stavu:

Alokace Max Volny
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
  • Obsah matice Potreba je definovan rozdilem Max - Alokace a je tedy:
Potreba
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
  • V teto situaci je system v bezpecnem stavu. Sekvence < P1, P3, P4, P2, P0,> je bezpecna sekvence.

Práce s pamětí, logický a fyzický adresový prostor, správa paměti a způsoby jejího provádění

Obecné poznatky správy paměti

Pro běh procesu je nutné, aby program, který ho řídí, byl umístěn v operační paměti.

Požadavky na správu paměti

Možnost relokace programů
Nutnost ochrany
Logická organizace
Možnost sdílení

LAP a FAP

Správa paměti, základní pojmy

Vstupní fronta (input queue): Fronta procesů čekajících na zavedení do paměti.

Logický adresový prostor (LAP): virtuální adresový prostor, se kterým pracuje procesor při provádění kódu (každý proces i jádro mají svůj). Dán šířkou a formou adresy. Kapacita je dána šířkou adresy v instrukci.

Fyzický adresový prostor (FAP): adresový prostor fyzických adres paměti (společný pro všechny procesy i jádro). Adresa akceptovaná operační pamětí. Kapacita je dána šířkou adresové sběrnice operační paměti

Vázání adres LAP na adresy FAP

Přidělování souvislých oblastí

Operační paměť (FAP) je typicky rozdělena na dvě části:

Pro ochranu procesů uživatelů mezi sebou a OS při přidělování sekce procesům lze použít schéma s relokačním a mezním registrem:

Problém při přidělování více souvislých sekcí. Dynamicky vznikají a zanikají úseky dostupné paměti, které jsou roztroušené po FAP. Procesu se přiděluje takový úsek ve FAP, který uspokojí jeho požadavky. Evidenci úseků (volných i obsazených) udržuje právě OS.

Způsoby rozhodování přidělování:

Rychlostně i kvalitativně jsou First-fit a Best-fit lepší, než Worst-fit. Nejčastěji používaný je First-fit.

Fragmentace

Fragmentace je snižována setřásáním – přesun sekcí s cílem vytvořit velký úsek paměti. Použitelné jen pokud je možná dynamická relokace (řeší MMU – Memory Management Unit). Provádí se v době běhu.

Výměny (Swapping)

Sekce FAP přidělená procesu je vyměňována mezi vnitřní a vnější pamětí oběma směry (roll out, roll in). Velmi časově náročné (srovnej přístupové doby do RAM a na HDD). Princip používaný mnoha OS ve verzích nepodporujících virtualizaci paměti – UNIX, Linux, Windows

Překryvy (Overlays)

Historická, klasická technika. V operační paměti se uchovávají pouze ty instrukce a data, která je potřeba zde uchovat „v nejbližší budoucnosti“. Vyvolávání překryvů je implementované uživatelem, není potřeba speciální podpory ze strany OS.

Stránkování

Co ještě byste měli znát?

* Měli byste chápat rozdíly mezi způsoby rozhodování přidělování souvislých oblastí (Best-fit, First-fit a Worst-fit) a především jejich výhody a nevýhody.

Předměty

Použitá literatura

* FI:PB152 Slidy k přednáškám (Verze Jaro 2007 od Marečka), na webu je aktuální verze (nevím, nakolik se shoduje)