Obsah

IN-POS 1. Architektury operačních systémů

Zadání

Vypracování

Struktury OS

Generické funkční komponenty OS:

Služby OS

Architektury OS

Mikrokernel / Mikrojádro

Makrokernel / Monolitické jádro

Modulární jádro

Procesy a vlákna

Proces

Význam procesu v OS

Stavy procesu

Informace OS o procesu

Process Control Block – tabulka obsahující informace potřebné pro definici a správu procesu

Vlákno

Objekt, který vzniká v rámci procesu, je viditelný pouze uvnitř procesu a je charakterizován svým stavem (CPU se přidělují vláknům).

Každé vlákno si udržuje svůj vlastní

Vlákno může přistupovat k paměti a ostatním zdrojům svého procesu

Tři klíčové stavy vláken:

Vlákna se (samostatně) neodkládají.

Ukončení procesu ukončuje všechna vlákna existující v rámci procesu

Výhody:
Konzistence

Vlákna jedné aplikace se proto musí mezi sebou synchronizovat, aby se zachovala konzistentnost dat (musíme zabránit současné modifikaci stejných dat dvěma vlákny apod.)

Mapování
Podpora
User-Level Threads (ULT)
Kernel-Level Threads (KLT)

Plánování procesů a vláken

Přepnutí kontextu

Vyžádá se služba, akceptuje se některé asynchronní přerušení, obslouží se a nově se vybere jako běžící proces.

Když OS přepojuje CPU z procesu X na proces Y, musí:

Přepnutí kontextu představuje režijní ztrátu (zátěž)

Při přerušení musí procesor:

Fronty plánování procesů

Strategický (dlouhodobý) plánovač

Krátkodobý plánovač

Střednědobý (taktický) plánovač

Algoritmy

FCFS

Algoritmus „Kdo dřív přijde, ten dřív mele“ (First Come, First Served).

Př.:

  • P1 (vyžaduje 24 dávek CPU)
  • P2 (vyžaduje 3 dávky CPU)
  • P3 (vyžaduje 3 dávky CPU)
  • P1, P2, P3
    • Doby čekání: P1 = 0, P2 = 24, P3 = 27
    • Průměrná doba čekání: (0+24+27)/3 = 17

  • P2, P3, P1
    • Doby čekání: P2 = 0, P3 = 3, P1 = 6
    • Průměrná doba čekání: (6+0+3)/3 = 3

SJF

Algoritmus Shortest-Job-First

  • Musíme znát délku příštího požadavku na dávku CPU pro každý proces.
  • Vybírá se proces s nejkratším požadavkem na CPU.
  • Dvě varianty:
    • nepreemptivní, bez předbíhání
      • jakmile se CPU předá vybranému procesu, tento nemůže být předběhnut žádným jiným procesem, dokud přidělenou dávku CPU nedokončí.
    • preemptivní, s předbíháním
      • jakmile se ve frontě připravených procesů objeví proces s délkou dávky CPU kratší než je doba zbývající k dokončení dávky právě běžícího procesu, je právě běžící proces ve využívání CPU předběhnut novým procesem.
      • Tato varianta se rovněž nazývá Shortest-Remaining-Time-First (SRTF)
  • SJF je optimální algoritmus (pro danou množinu procesů dává minimální průměrnou dobu čekání)

Př.:

Proces Doba příchodu Délka dávky CPU
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
  • Nepreemtivní
    • Průměrná doba čekání: (0+6+3+7)/4 = 4

  • Preemptivní
    • Průměrná délka čekání: (9+1+0+2)/4 = 3

Prioritní plánování

  • S každým procesem je spojeno prioritní číslo.
    • prioritní číslo – preference procesu pro výběr příště běžícího procesu
    • CPU se přiděluje procesu s největší prioritou
    • nejvyšší prioritě obvykle odpovídá nejnižší prioritní číslo
  • Opět dvě varianty:
    • nepreemptivní, bez předbíhání
      • Jakmile proces získá přístup k CPU nemůže být předběhnut jiným procesem dokud dávku neukončí.
    • preemptivní, s předbíháním
      • Jakmile se ve frontě připravených procesů objeví proces s vyšší prioritou než je priorita běžícího procesu, je běžící proces předběhnut SJF je prioritní plánování, prioritou je předpokládaná délka příští CPU dávky.
  • stárnutí
    • Procesy s nižší prioritou se nemusí nikdy provést.
    • Řešení: zrání – priorita se s postupem času zvyšuje.

Round Robin (RR)

  • Každý proces dostává CPU na malou jednotku času – časové kvantum.
    • Desítky až stovky ms
  • Po uplynutí této doby je běžící proces předběhnut nejstarším procesem ve frontě připravených procesů a zařazuje se na konec této fronty. Je-li ve frontě připravených procesů n procesů a časové kvantum je q, pak každý proces získává 1/n doby CPU, najednou nejvýše q časových jednotek.
  • Žádný proces nečeká na přidělení CPU déle než (n-1)q časových jednotek
  • Výkonnostní hodnocení
    • q velké → ekvivalent FIFO
    • q malé → velká režie; v praxi musí být q musí být dostatečně velké s ohledem na režii přepínání kontextu
  • Typicky se dosahuje delší průměrné doby obrátky než při plánování SJF, avšak doba odpovědi je výrazně nižší.

Př.:

Proces Délka dávky CPU
P1 53
P2 17
P3 68
P4 24
  • časové kvantum: 20

Komunikace a synchronizace procesů

Synchronizace běhu procesů = „Jeden proces čeká na událost z druhého procesu.“

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.

Umožňuje:

Komunikace – způsob synchronizace, koordinace různých aktivit

Race condition

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

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

Semafor
Monitor

Synchronizační nástroj vysoké úrovně.

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

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

Stárnutí = požadavky 1 nebo více procesů z P nebudou splněny v konečném čase

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

Metody ochrany proti uváznutí

Ochrana před uváznutím prevencí
Obcházení uváznutí

Bankéřův algoritmus

  • Algoritmus používaný u zdrojů, kterých se přiděluje určité množství.
  • 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.

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.
Detekce a obnova po uváznutí

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

Resource-Allocation Graph, RAG

  • množina uzlů (procesy ⚫, zdroje ⬛)
  • hrany
    • požadavků (proces → zdroj)
    • přidělení (zdroj → proces)
  • zdroje mohou mít více instancí

Jestliže se v RAG nevyskytuje cyklus:

  • ⇒ k uváznutí nedošlo

Jestliže se v RAG vyskytuje cyklus:

  • existuje pouze jedna instance daného typu ⇒ k uváznutí došlo
  • existuje více instancí daného typu ⇒ k uváznutí může dojít

Wait-for-Graph, WFG

  • vztahy pouze mezi procesy
  • hrana = proces čeká na uvolnění zdroje druhým procesem
  • Systém uvázl, pokud je v grafu cyklus.
Ignorování hrozby uváznutí

Správa paměti a virtualizace paměti

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

Fyzický a logický adresový prostor

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í

Segmentace

Virtuální pamět

Stránkování na žádost (Demand paging)

  • stránka se zobrazuje do FAP při odkazu na ni, pokud ve FAP není již zobrazena
  • počáteční shluky výpadků stránek

Předstránkování (Prepaging)

  • umístění na vnější paměti sousedních stránek v LAP bývá blízké („sousedi“)
  • princip lokality
  • zavádí se více stránek než se žádá
  • vhodné při inicializaci procesu
Výpadek stránky

Pokud se stránka nenachází ve FAP je aktivován OS pomocí přerušení „page fault“ (výpadek stránky)

Algoritmy určující oběť

Ovládání vstupů a výstupů

Základní způsoby ovládání I/O

Polling, programované I/O operace

Přerušení

DMA

Aplikační rozhraní I/O

Síťová zařízení

Blokující a neblokující I/O

I/O subsystém v jádře

Zdroje