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

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

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

• mikrokernel (mikrojádro, jádro je velice jednoduché a obsahuje pouze zcela základní funkce, zbytek operačního systému je mimo toto jádro v aplikacích)

• makrokernel (monolitické jádro, jádro je rozsáhlé, obsahuje velké množství funkcí pro všechny aspekty činnosti operačního systému včetně například souborového systému).

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

• uživatelské rozhraní – interpret příkazů (command.com, shell, …),
• rozhraní služeb OS – zpřístupnění služeb OS procesům (má každý OS)

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

• 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

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

• 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

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

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

• 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

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.

• 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

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é podmínky uváznutí:
  1. vzájemné vyloučení (Mutual exclusion)
     • se sdíleným zdrojem může v jednom okamžiku pracovat právě jeden proces
  2. inkrementálnost požadavků (též postupné uplatňování požadavků, Hold-and-Wait)
     • proces vlastnící nějaký zdroj potřebuje ke své činnosti zdroj další, který je však držen jiným procesem
  3. nepředbíhatelnost (No preemption)
     • zdroje lze uvolnit pouze procesem, který tyto vlastní a to pouze dobrovolně, až je nebude potřebovat
• Postačující podmínka:
  • cyklické čekání (též zacyklení pořadí, Circular Wait)
    • důsledek prvních tří nutných podmínek
    • existuje množina n procesů (P₀…P_n), kde proces P₀ čeká na uvolnění zdroje drženého procesem P₁, P₁ čeká na uvolnění zdroje drženého P₂ atd. až P_n čeká na uvolnění zdroje drženého P₀

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

• 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)
  • uspořádání prostředků – ruší se možnost vzniku zacyklení při čekání: procesy smí požadovat prostředky pouze ve stanoveném pořadí
    • klady: lze kontrolovat při kompilaci, nic se neřeší za běhu
    • zápory: neefektivní

„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

• 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

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.

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

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

• 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

• 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

• Uživatelé tvoří programy jako moduly se vzájemně odlišnými vlastnostmi
  • execute-only – moduly s instrukcemi
  • read-only nebo read-write – datové moduly
  • private nebo public – moduly s omezením přístupu

• 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

• 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í

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

• sekce pro rezidentní část OS, obvykle bývá umístěna od počátku
• sekce pro uživatelské procesy

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.

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

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

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.

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

• Tato otázka souvisí s otázkou Plánování v operačních systémech, proto by vás nemělo překvapit, že se otázky od komise mohou lehce stočit i k této otázce.

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

• FI:PB152 Operační systémy (Jaro 2008), doc. Ing. Jan Staudek, CSc.

• FIT VUTBR, slidy přednášek

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