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
Správa procesorů
Správa procesů (proces – činnost řízená programem)
Správa (hlavní, vnitřní) paměti
Správa souborů
Správa I/O systémů
Správa vnější (sekundární) paměti
Networking, distribuované systémy
Systém ochran
Interpret příkazů (mnohdy nadstavba
OS – kategorie systémové programy)
Architektury
Podle architektury operačního systému se typicky rozlišuje:
Jakýmsi kompromisem je modulární jádro, které je fakticky makrojádrem (celé běží v privilegovaném režimu) ovšem jeho značná část je tvořena takzvanými moduly, které je možné přidávat a odebírat za běhu systému.
Rozhraní
Procesy
Proces
je program zavedený do operační paměti, který je prováděn procesorem. Proces obsahuje nejen kód programu, ale i dynamicky se měnící data, která proces zpracovává.
používá systémové prostředky počítače, které mu přidělil operační systém („vlastní“ tyto prostředky)
je jednoznačně rozpoznatelný (unikátní PID - Process ID)
Význam procesu v OS
OS maximalizuje využití procesoru prokládáním běhu procesů (minimalizuje tak dobu odpovědi)
OS spravuje zdroje přidělováním procesům podle zvolené politiky (priorita, vzájemná výlučnost, zabraňuje uváznutí)
OS podporuje tvorbu procesu a jejich komunikaci
OS s multiprogramováním
multiprogramování = multitasking
Data nutná pro spravování procesu
Stavové informace (registry procesoru, čítač instrukcí)
Informace nutné pro správu a řízení procesu (priorita procesu, stav procesu, inf. o používání zdroj, PID - proces identifier, inf. o používání paměti )
Stavy procesu
Nový - proces je právě vytvářen
Běžící - proces je právě vykonáván nějakým CPU v systému
Čekající - proces čeká na nějakou událost/události (například dokončení výpočtu jiného procesu)
Připravený - proces čeká na přidělení procesoru, je připraven vykonávat svou úlohu
Ukončený - proces ukončil svou činnost, ale ještě stále existuje
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:
výhradní přístup - v každém okamžiku smí být v kritické sekci nejvýše jeden proces
vývoj - rozhodování o tom, který proces vstoupí do kritické sekce, ovlivňují pouze procesy, které o vstup do kritické sekce usilují; toto rozhodnutí pro žádný proces nemůže být odkládáno do nekonečna; nedodržení této podmínky může vést například k tomu, že je umožněna pouze striktní alternace (dva procesy se při průchodu kritickou sekcí musí pravidelně střídat)
omezené čekání; pokud jeden proces usiluje o vstup do kritické sekce, nemohou ostatní procesy tomuto vstupu zabránit tím, že se v kritické sekci neustále střídají - mohou do této kritické sekce vstoupit pouze omezený počet krát (zpravidla pouze jednou)
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í
aktivní čekání – softwarově – pouze vzájemná výlučnost R/W s pamětí, bez podpory programovacího jazyka /
OS
aktivní čekání – speciální instrukce TST, EXCHANGE – bez podpory programovacího jazyka /
OS
pasivní čekání – podpora v programovacím jazyku /
OS: semafory, monitory, zasílání zpráv
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
libovolný počet čtenářů může číst ze sdílené oblasti, v jednom okamžiku smí do sdílené oblasti zapisovat pouze jeden písař, jestliže písař píše do sdílené oblasti, nesmí současně z ní číst žádný čtenář.
Příklad výskytu této úlohy v praxi může vypadat takto: sdílenou oblast reprezentuje knihovna programů, čtenáři nazveme sestavující programy a písařem může být knihovník.
Řešení úlohy o čtenářích a písařích:
priorita čtenářů (pomocí semaforů) – první čtenář zablokuje všechny písaře, poslední čtenář je uvolní, písaři mohou stárnout
priorita písařů (pomocí semaforů) – první čtenář zablokuje všechny písaře, poslední čtenář je uvolní, první písař zakáže přístup novým čtenářům
priorita písařů (zasíláním zpráv) – první čtenář zablokuje všechny písaře, poslední čtenář je uvolní, první písař zakáže přístup novým čtenářům, ke sdílené oblasti řídí přístup referenční monitor se třemi mailboxy, každý čtenář / písař má svůj mailbox
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í
Nutné podmínky uváznutí:
vzájemné vyloučení (Mutual exclusion)
inkrementálnost požadavků (též postupné uplatňování požadavků, Hold-and-Wait)
nepředbíhatelnost (No preemption)
Postačující podmínka:
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í
ignorovat je - přestože tato strategie vypadá nepřijatelně, používá ji například
OS Unix; v případě uváznutí musí zasáhnout některý z uživatelů a jeden nebo více procesů násilím ukončit; v krajním případě může být nutné znovu nastartovat celý systém
prevence uváznutí – ruší se platnost některé nutné podmínky
detekce uváznutí – detekuje se existence uváznutí a řeší se následky
vyhýbání se uváznutí – zamezuje se současné platnosti nutných podmínek
nepřímé metody (zneplatnění nutné podmínky)
virtualizace prostředků – rušení vzájemné výlučnosti (mimo spooling nepoužitelné)
požadování všech prostředků najednou – ruší se požadavek inkrementálnosti požadavků
klady: nemusí se nic odebírat, vhodné pro procesy s jednou nárazovou činností
zápory: neefektivní, možná prodleva při zahájení procesu
odebírání prostředků – ruší se vlastnost nepředbíhatelnosti procesů z hlediska používání prostředků
1. možnost: proces, jemuž byl odmítnut požadavek, uvolní vše co vlastní a o vše požádá znovu
2. možnost: jestliže proces požaduje prostředek držený jiným procesem, držitel je požádán, aby uvolnil vše co vlastní a o vše požádal znovu (procesy nesmí být stejné priority)
klady: vhodné pro prostředky s uchovatelným a obnovitelným stavem (FAP, procesor)
zápory: režijní ztráty, možnost cyklického restartu
přímé metody (nepřipuštění planosti postačující podmínky)
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í
zrušit všechny uváznuté procesy (nejčastěji používaná metoda)
návrat uváznutých procesů k poslednímu kontrolnímu bodu (možnost opakování situace)
postupně rušit uváznuté procesy (podle spotřebovaného času procesoru, počtu tiskových řádků, času do dokončení procesu, priority, množství vlastněných prostředků)
postupně předbíhat uváznuté procesy
zamezit současné platnosti nutných podmínek
bankéřův algoritmus
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
Algoritmus grafu alokace zdrojů je použitelný pouze v systému, kde každá třída zdroje obsahuje max. 1 instanci. Algoritmus, který si popíšeme nyní, tento problém eliminuje. Není ovšem tak efektivní jako algoritmus grafu alokace zdrojů.
Když vstoupí novy proces do systému, musí deklarovat maximální počet instanci všech tříd, které bude pro svůj běh potřebovat. Tato maxima nesmi přesahovat celkový počet zdrojů v systému. Když uživatel požaduje množinu zdrojů, musí systém zjistit nepřevede-li alokace těchto zdrojů systém do nebezpečného stavu. Pokud by tomu tak bylo, musí proces čekat než jiný proces neuvolní dostatek zdrojů. V případe opačném jsou zdroje procesu alokovány.
Pro zajištěni chodu bankéřova algoritmu je třeba udržovat množství datových struktur. Tyto struktury kódují stav systému alokace zdrojů. Nechť n je celkový počet procesu v systému a m je počet typu zdrojů. Potřebujeme následující datové struktury:
Volny: vektor delky m indikujici pocet volnych instanci kazdeho typu zdroje. Jestlize Volny(j) = k, potom je v systemu k volnych instanci zdroje Rj.
Max: matice typu (n,m) definujici maximalni pozadavek kazdeho procesu na kazdou tridu zdroju. Jestlize Max(i,j) = k, potom proces Pi muze pozadat maximalne o k instanci zdroje Rj.
Alokace: matice typu (n,m) definujici pocet zdroju kazde tridy aktualne alokovany kazdemu procesu. Jestlize Alokace(i,j) = k, potom proces Pi ma momentalne alokovano k instanci zdroje tridy Rj.
Potreba: matice typu (n,m) definujici zbyly pocet instanci zdroje kazde tridy nutny k dokonceni ulohy. Jestlize Potreba(i,j) = k, potom proces Pi potrebuje k dokonceni sve ulohy dalsich k instanci tridy Rj.
Uvedene datove struktury se v case meni jak co do velikosti, tak co do hodnoty. Pro zjednoduseni prezentace Bankerova algoritmu definujme nasledujici vztah: Necht X a Y jsou vektory delky n. Potom X < = Y tehdy a jen tehdy, jestlize X(i) < = Y(i) pro vsechna i = 1, .. ,n. Napriklad jestlize X = (1, 7, 3, 2) a Y = (0, 3, 2, 1), potom Y < = X. Dale X < Y tehdy, jestlize X < = Y a zaroven X < > Y.
Kazdou radku matic Alokace a Potreba muzeme zpracovavat jako vektor a oznacovat jako Alokacei a Potrebai. Vektor Alokacei specifikuje zdroje, ktere jsou aktualne alokovany procesu Pi a vektor Potrebai specifikuje dalsi zdroje, ktere proces Pi potrebuje pro sve dokonceni.
Příklad
Uvazujme system s peti procesy P0 az P4 a tri zdroje typu A, B, C.
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 | | | |
| 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.
Program se převádí do formy schopné interpretace procesorem ve více krocích, jednou musí někdo rozhodnout kde bude v operační paměti (FAP) umístěn.
Roli dlouhodobé paměti programu plní vnější paměť.
Vnitřní operační paměť uschovává data a programy právě běžících, resp. plánovatelných procesů.
Správa paměti je předmětem činnosti
OS, nelze ji nechat na aplikačním programování. Výkon jejich funkcí by byl neefektivní až škodlivý.
Správa paměti musí zajistit, aby sdílení FAP mezi procesory bylo transparentní a efektivní a přitom bezpečné.
Požadavky na správu paměti
Možnost relokace programů
programátor nemůže vědět, ze které části paměti bude jeho program interpretován
při výměnách mezi FAP a vnější paměti (odebírání a vracení paměťového prostředku procesu) může být procesu dynamicky přidělena jiná (souvislá) oblast paměti než kterou opustil - swapping
swapping umožňuje
OS udržovat velký bank připravených procesů.
odkazy na paměť v programu (LAP) se musí dynamicky překládat na skutečné adresy ve FAP
Nutnost ochrany
procesy nesmí být schopné se bez povolení odkazovat na paměťová místa přidělená jiným procesům nebo
OS
relokace neumožňuje, aby se adresy kontrolovaly během kompilace
odkazy na paměť se musí kontrolovat při běhu procesu hardwarem
Logická organizace
Možnost sdílení
více procesů může sdílet společnou část paměti aniž by došlo k porušení její ochrany
sdílený přístup je lepší než udržování konzistence kopií, které vlastní jednotlivé procesy
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ři kompilaci
Je-li umístění ve FAP známé před překladem, kompilátor generuje absolutní program (obraz programu ve FAP)
při změně umístění ve FAP se musí překlad opakovat
při zavádění
umístění ve FAP je známé při sestavování nebo při zavádění programu
překladač generuje object module, jehož cílovým adresovým prostorem je LAP
vazby na adresy FAP provádí zavaděč
při běhu
cílovým prostorem sestavení je LAP
program se zavede do FAP ve tvaru pro LAP
vázání se odkládá na dobu běhu – při interpretaci instrukce
nutná HW podpora
proces může měnit svoji polohu ve FAP během provádění
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:
relokační – hodnota nejmenší adresy sekce ve FAP
mezní – rozpětí logických adres 0..*, přičemž logická adresa použitá v procesu musí být menší než mezní registr
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í:
First-fit – první dostatečně velký úsek paměti
Best-fit – nejmenší dostatečně dlouhý úsek paměti
Worst-fit – největší volný úsek paměti
Rychlostně i kvalitativně jsou First-fit a Best-fit lepší, než Worst-fit. Nejčastěji používaný je First-fit.
Fragmentace
Vnější – souhrn volné paměti je dostatečný, nikoliv však v dostatečně velkém souvislém bloku
Vnitřní – přidělená oblast paměti je větší, než požadovaná velikost, přebytek je nevyužitelná část paměti
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í
LAP procesu není zobrazován do jediné souvislé sekce FAP, zobrazuje se po částech do volných sekcí FAP
FAP se dělí na rámce – pevná délka (např. 512 B)
LAP se dělí na stránky – pevná délka shodná s délkou rámců
OS si udržuje seznam volných rámců
Pořadí přidělených rámců ve FAP nesouvisí s pořadím stránek v LAP
Překlad LAP → FAP je realizován
tabulkou stránek (Page Table), jejíž obsah nastavuje
OS
PT je uložena v operační paměti.
Zpřístupnění údaje v vyžaduje dva přístupy do paměti (do PT a pro operand)
Problém snížení efektivnosti dvojím přístupem lze řešit speciální rychlou HW cache (asociativní paměť, TLB – Translation Look-aside Buffer)
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
FI:PB152 Operační systémy (Jaro 2008), doc. Ing. Jan Staudek, CSc.
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)