PB153.md

Operační systém

• správce prostředků počítače, koordinátor, řídící složka
• cíle: uživatelská přívětivost, efektivní využití zdrojů, bezchybnost, spolehlivost

Paralelní systémy (Úzce vázané systémy)

• více procesorů, společná paměť a hodinový signál
• výcejádrové systémy

SMP (Symetrický multiprocesorový systém)

• všechny procesory jsou si rovny

AMP (Asymetrický multiprocesorový systém)

• některé procesory mají specifické funkce

Distribuované systémy (Volně vázané systémy)

• nemají společnou paměť a hodinový signál
• využívají komunikační kanály

Real-Time Systémy

• záleží na rychlosti odezvy
• pracují v reálném čase
• řízení strojů, monitoring

Hard RT Systémy

• přísné
• speciální OS, rozhoduje, jestli se proces stihne a podle toho jej zamítne nebo akceptuje

Soft RT Systémy

• tolerantní
• snažíme se dodržet limit, ale když se to nepovede, zas tak moc se nestane
• procesy s vyšší prioritou mají přednost před procesy s nižší prioritou

Mobilní systémy

• mnohá omezení (velikost, cena, výdrž, výkon...)

Hardware

Dávkové systémy

• JCL (Job Control Language)
• job = program + data + řídící informace
• využití procesoru dřív nebylo efektivní

Multiprogramování

• zajištění stálého vytížení procesoru
• pokud se procesor uvolní, přepne se na zpracovávání jiné úlohy

Multitasking (Time-sharing)

• proces procesoru odebereme i v případě, pokud jej zpracovává moc dlouho
• rychle přepínáme mezi procesy, což vzbuzuje dojem paralelního běhu
• nutná ochrana procesů (jeden nesmí zasahovat do paměti druhého)
• I/O zařízení mají vlastní vyrovnávací paměť (buffer) -> CPU a I/O zařízení mohou pracovat paralelně, ale musí se synchronizovat
• snižuje dobu odezvy

Přerušení

• aktivní čekání -- vyplatí se pouze na velmi krátkou dobu
• loop > získej další instrukci > proveď instrukci > (je-li nastaven flag přerušení a je-li povoleno, proveď přerušení) > end loop
• přerušení -- uložení adresy aktuálně prováděného kódu a provedení kódu obslužné rutiny
• tabulka přerušení -- definice chování jednotlivých přerušení

I/O přístupy

• synchronní přístup -- nejdřív načteme a pak až použijeme, proces přichází ze stavu běžící do stavu čekající
• asynchronní přístup -- zahájíme načítání a pak můžeme dělat něco jiného, následně se ptáme, jestli už je to hotovo, pokud ne, nesmíme k datům přistupovat

DMA (Direct Memory Access)

• způsob rychlého přenosu dat mezi I/O a pamětí
• CPU požádá o přenos dat a po dokončení je o tom informován přerušením

Paměť

RES -- rezidentní paměť, která nebyla odswapovaná (neodswapovaná fyzická paměť)

Primární paměť (operační paměť, hlavní paměť)

• přímá adresace
• volatilní (energeticky závislá)
• kapacita: stovky MB až desítky GB
• rychlost: nanosekundy

Sekundární paměť

• rozšiřuje paměťovou kapacitu (velká kapacita)
• energeticky nezávislá
• pomalá

Mezipaměť (kešování, cache)

• rychlá & drahá

Bezpečnost

• ochrana paměti -- Memory management unit (jednotka správy paměti), báze a limit nastavené v registrech
• spravedlivé přidělení CPU -- podle časovače
• koordinace přístupu k I/O prostředkům

Režimy procesoru

• běžný režim -- má jistá omezení (nemůže přistupovat k HW...)
• privilegovaný režim -- dostaneme se do něj přerušením

Struktura a rozhraní OS

Struktura OS

• jádro (nejdůležitější část, která běží v privilegovaném režimu)
• systémová volání -- spojovník mezi jádrem a uživatelskými procesy
• uživatelský proces (shell,... )

Správa procesů

• vytváření, ukončování, potlačování, obnovování, synchronizace, komunikace procesů, deadlock
• program -- pasivní entita
• proces -- aktivní entita, spuštěný program, potřebuje procesor, paměť a soubory
• vlákno -- jeden proces se může skládat z více vláken (v Linuxu "task")
• jednotka plánování procesoru -- dříve proces, dnes vlákno

Správa operační paměti

• alokace a dealokace paměti pro procesy

Správa souborů

• OS nezajímá struktura souboru
• souborový systém -- má za úkol zajistit přístupová práva
• otevírání, vytváření a rušení souborů a adresářů, zálohování (metadata)

Správa I/O zařízení

• cílem je jednotnost a jednoduchost
• speciální soubory (bloková nebo znaková zařízení) v UNIXu
• rychlost, buffery, kešování, spooling

Správa síťových služeb

• implementace protokolů zajišťujících zpřístupnění vzdálených souborů v podobném rozhraní, jakou jsou lokální soubory
• sockety

Ochranný systém

• izolace procesů
• proces může přistupovat jen do svého adresového prostoru v paměti
• proces nesmí získat plný přístup k CPU
• uživatelský proces nesmí spouštět privilegované instrukce

Interní služby OS

• plánovací algoritmy pro procesor, pro plánování paměti...
• účtování -- přehled o tom, kteří uživatelé zabrali jaké zdroje

Systémová volání

• tvoří rozhraní mezi uživatelem a rozhraním jádra
• Linux: open, write, close, exit
• lze je implementovat pomocí přerušení
• MS-DOS: int 0x21, Linux: 0x80, sysenter, syscall
• sysenter -- slouží k rychlému systémovému volání
• číslo systémového volání a výsledek je v registru eax
• psána v assambleru, většina programovacích jazyků má funkce, která zprostředkovávají systémová volání
• předávání parametrů je realizováno:
  • zásobníkem
  • registry
  • pointrem na strukturu s daty uloženými v paměti patřičného procesu
• snaha o sjednocení rozhraní: POSIX (Portable Operating System Interface), WIN32 (Windows API)
• strace -- monitoruje systémová volání a signály pomocí speciálního syscallu ptrace, který slouží pro trasování běžícího kódu programu

POSIX

• od roku 1988
• standardizace
• pthread_create() -- vytvoření vlákna

Windows API

• programátorské volání není definováno na úrovni systémových volání jádra
• nižší vrstva ntdll.dll
• CreateThread() -- vytvoření vlákna

Principy výstavby OS

• monolitické jádro
• modulární, hierarchický přístup
• malé jádro + procesy
• programování pro MS-DOS: spuštěné rezidentní programy, OS, BIOS, HW
• cíl: maximální možná funkcionalita v co nejmenším prostoru
• UNIX: jádro & systémové programy

XENIX -- 1979 Microsoft koupil licenci na UNIX a tento OS se stal velmi rozšířeným

Hierarchická vrstvová architektura

• OS dělíme na úrovně
• každá vrstva se buduje na funkcionalitě nižších vrstev a používá funkce pouze předchozí vrstvy
• nejnižší vrstva je HW
• nejvyšší vrstva je UI (User Interface)
• dekompozice > jednoduchost
• princip modularity -- vrstvu lze uvnitř modifikovat, bez ovlivnění ostatních vrstev
• výhoda: modularita
• nevýhoda: efektivita (pomalé vykonávání systémových volání)

Služby v klasickém OS

• neprocesově orientované
• OS v privilegovaném režimu
• proces = uživatelský program
• služba se provádí jako součást jádra, samostatný zásobník
• přerušení se vyvolá pouze při přepnutí režimu procesoru (uživatelský > privilegovaný)
• přepínání kontextu procesů dochází jen když je to nutné kvůli plánování
• program a data OS jsou sdílena všemi uživatelskými procesy

Služby v procesově konstruovaném OS

• část funkčnosti jádra přesunu na jiné procesy
• OS je souhrnem systémových procesů
• co nejméně kódu se provádí v privilegovaném režimu
• mikrojádro, nanojádro
• jádro: komunikace mezi procesy, správa paměti
• výhody: přenositelnost OS, spolehlivost, bezpečnost, flexibilita, stabilita
• nevýhody: zvýšená režie (pomalost)

MACH -- OS s mikrojádrem z 80. let

Monolitické jádro

UNIX

• funkčnost je v jádře v privilegovaném režimu
• /dev/kmem -- soubor, ve kterém mohu jako root modifikovat jádro
• LKM (Loadable Kernel Module) -- přidávání funkčnosti do jádra za běhu, běží v privilegovaném režimu
• modularita kódu
• výhody: nízké paměťové nároky jádra
• integrita -- moduly se nepodepisují (ale můžou -- RH, Win7), ale obsahují licenci
• Secure Boot -- (bezpečný boot), samostatné zavádění komponent, prevence rootkitů (bootkitů), vytvoří se hash a podle něj se kontroluje po vrstvách to, co se zavádí
• rootkit -- maskuje přítomnost určitého sw v počítači
• snaha omezit modifikace LKM tabulky systémových volání

Windows

• můžeme vkládat ovladače
• podepisování: spolehlivost systému, bezpečnost, DRM (Digital Rights Management)
• User Mode Drivers -- snaha omezit množství kódu bežícího v jádře

System generation (sysgen)

• OS se přizpůsobí při instalaci danému HW
• program Sysgen získá informace o konfiguraci HW

Bootování

• inicializace HW
• z kterého zařízení zavést OS
• MBR (Master Boot Record) -- limitován velikostí disku 2TB
• spuštění zavaděče
• výběr OS a parametrů (GRUB, LILO)
• spuštění jádra -- načtení obrazu, dekomprimace, inicializace, spuštění
• jádro -- nastavení systému, spuštění plánovače, spuštění procesu Init, jehož úkolem je spustit všechno ostatní

Procesy

• spuštěný program (proces)
  • dávkové systémy: úloha, dávka, job
  • multiprogramové systémy: proces, vlákno
• vlákno = dílčí proces v rámci procesu
• proces obsahuje: čítač instrukcí, zásobník, datová sekce, instrukční sekce (program)
• hierarchie procesů: rodič, potomek, sourozenci
• multiprogramování -- prokládání procesů, slouží k maximalizaci využití procesoru
• stavy procesu: nový, běžící, čekající (čeká na událost), připravený (čeká na přidělení času procesoru), ukončený
• Process Control Block -- tabulka obsahující všechno, co OS o procesoru ukládá (stav, čítač instrukcí, registry procesoru, informace pro správu paměti a I/O zařízení, účtovací informace)
• IPC (Inter Proces Communication) -- semafory, sdílená paměť, roury, signály (asynchronní události), zprávy

Přepnutí procesu

• plánovač rozhoduje, který proces dostane čas procesoru
• mezi přepnutím probíhá záznam do Process Control Blocku

Přepnutí kontextu

• do PCB se zaznamená stav původně běžícího procesu
• z PCB se zavede stav nového procesu
• během přepnutí kontextu se neděje nic efektivního -- režijní ztára (zátěž)
• doba závisí na HW
• při přerušení procesor uchovává čítač instrukcí a zavést do něj informace o přerušení
• fronty plánování procesů

Plánovače

Krátkodobý plánovač

• z připravených procesů vybrat další proces
• musí být velmi rychlý (protože plánuje na velmi malé časové úseky)

Strategický plánovač

• rozhoduje, kdy bude který proces spuštěn
• zařazuje procesy mezi připravené
• určuje stupeň multiprogramování
• nemusí být rychlý

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

• když je úloh moc
• vyplatí se nějaký proces odložit (na disk, pryč z operační paměti)
• dva nové stavy procesu: odložený čekající, odložený připravený

Vytvoření procesu

• strom procesů
• proces vytvoří jiný proces
• dědění -- potomek sdělí veškeré zdroje od rodiče nebo jen podmnožinu
• běh -- rodič a potomek běží současně nebo rodič čeká na dokončení potomka
• UNIX: fork(), LINUX: vfork, WIN32: CreateProcess()

Ukončení procesu

• proces sám požádá o ukončení
• požádá-li jedno vlákno, skončí všechna
• proces může být ukončen OS
• pokud skončí rodič mohou skončit i potomci
• UNIX: exit, WIN32: ExitProcess

Vlákna

program -- soubor na disku, obsahující data, instrukce a další informace

proces -- spuštěný program

vlákno (sled) -- "podproces", na který se dělí proces

• proces má zdroje, vlákno je jednotka plánovací činnosti
• každé vlákno má: zásobník, PC (program counter), registry, TCB (Thred Context Block)
• vlákna sdílejí: stejný adresový prostor (paměť), číslo procesu, číslo vlákna
• vlákno může přistupovat ke zdrojům svého procesu
• výhody: jednodušší programování, využití multiprocesorových strojů, vlákna jsou rychlejší (vytvoření, ukončení, přepínání) než procesy
• modely: 1:1 (1 proces = 1 vlákno, MS-DOS), 1:M (1 proces = M vláken, Windows XP)
• přepnutí mezi vlákny je rychlejší, protože vlákna jednoho procesu využívají stejné zdroje
• problém konzistence -- vlákna se musí synchronizovat
• vlákno ve WIN: fiber, vytvoření vlákna v Linuxe: clone()

Stavy vláken

• běží
• připravený
• čekající
• vlákna se neodkládají
• ukončení ukončí všechna vlákna jednoho procesu

Vlákna na uživatelské úrovni (ULT - User-Level Threads)

• vláknová knihovna -- provádí správu vláken
• jádro o vláknech neví, o vše se stará knihovna
• knihovna obsahuje funkce: vytváření, rušení, předávání zpráv, plánování, uchovávání a obnova kontextu vláken
• jádro manipuluje s celými procesy
• stavy vláken jsou na stavu nezávislé
• pokud vlákno volá službu jádra, je blokován celý proces

Vlákna na úrovni jádra (KLT - Kernel-Level Threads)

• správu jader podporuje jádro
• pomalejší
• umožňuje paralelní běh dvou vláken na dvou procesorech
• k blokování dochází na úrovni vlákna (neblokuje se celý proces)
• OS/2, Windows 95<, Solaris, Tru64 UNIX, BeOS, Linux

Kombinace ULT/KLT

• vlákna se vytvářejí v uživatelském prostoru
• většina plánování a synchronizace probíhá v uživatelském prostoru
• programátor může nastavit počet vláken na úrovni jádra
• kombinuje přínosy obou přístupů
• např. OS Solaris <= 8

• n : 1 (více ULT se zobrazuje do 1 KLT)
• 1 : 1 (1 ULT odpovídá 1 KLT)
• n : m

Plánování CPU

Multiprogramování

• zvyšuje využití CPU
• pokud jeden proces čeká, je spuštěn jiný
• nejvhodnější je kombinovat procesy orientované na I/O zařízení a na využití CPU

Krátkodobý plánovač (Dispečer)

• vybírá proces (z připravených a zavedených do operační paměti), kterému bude přidělen CPU
• rozhodnutí vydá v případě, že proces
  • nepreemptivní (bez předbíhání):
    • přechází ze stavu běžící do čekající
    • končí
  • preemptivní (s předbíháním):
    • přechází ze stavu běžící do připravený
    • přechází ze stavu čekající do připravený
• dispečer -- modul předávající procesor novému procesoru
• předání zahrnuje: přepnutí kontextu, přepnutí procesoru na uživatelský režim, skok na odpovídající místo v programu pro pokračování běhu programu
• Dispath latency (dispečerské zpoždění) -- doba, kterou potřebuje dispečer k pozastavení jednoho procesu a startu druhého

Kritéria plánování (a optimalizace)

• využití CPU -- snaha o neustálý provoz procesoru (max)
• propustnost -- počet procesů, které dokončí svůj běh za jednotku času (max)
• doba obrátky -- doba potřebná k provedení konkrétního procesu (min)
• doba čekání -- doba, po kterou proces čeká ve frontě "připravených" procesů (min)
• doba odpovědi -- doba od zadání požadavku do okamžiku první reakce (min)

Algoritmus FCFS

• First Come, First Served.
• konvojový efekt -- krátké procesy po jednom dlouhém zhoršují průměrnou dobu čekání

Algoritmus SJF

• Shortest Job First
• vybírá procesy s nejkratším požadavkem na CPU
  • nepreemptivní (bez předbíhání) -- žádný proces nemůže předběhnout ten, jež je právě zpracováván
  • preemptivní (s předbíháním) -- pokud se ve frontě objeví proces s nižšími požadavky na CPU, než zbývá aktuálně probíhajícímu procesu, je aktuální proces předběhnut tímto kratším procesem
• je to optimální algoritmus (dává minimální průměrnou dobu čekání pro danou množinu procesů)

Určení délky příští dávky CPU procesu

• délku neznáme, můžeme ji odhadnout na základě historie

Prioritní plánování

• každý proces má prioritní číslo, čím nižší, tím vyšší priorita
• CPU se přiděluje podle priority procesu
  • nepreemptivní
  • preemptivní
• problém stárnutí -- procesy s nízkou prioritou nepřijdou nikdy na řadu > řešení: zrání -- priorita se postupem času zvyšuje

Round Robin

• každý proces dostane pevně přidělenou dobu procesoru, která se odvíjí od počtu procesů ve frontě
• n procesů ve frontě, každý proces získá 1/n doby CPU
• provádí se přerušení, při kterém proces přechází ze stavu běžící do stavu připravený

Synchronizace procesů

Paralelní běh procesů

• synchronizace běhu procesů
  • jeden proces čeká na druhý
• komunikace mezi procesy -- způsob synchronizace a koordinace různých aktivit
  • uváznutí -- každý proces čeká na zprávu od jiného procesu
  • stárnutí -- dva procesy posílají zprávy a třetí čeká nekonečně dlouho
• sílení prostředků -- procesy používají a modifikují sdílená data
  • operace zápisu se nesmí vzájemně překrýt
  • operace zápisu se nesmí překrýt s operací čtení
  • kritická sekce
• nekonzistence -- je způsobena paralelním přístupen k datům

Race condition (podmínka soupeření, souběh)

• více procesů současně pracuje se zdroji
• podstatné je, kdo zdroje modifikoval naposled
• ochrana před negativními dopady -- synchronizace

Problém kritické sekce

• n procesů soupeří o právo používat jistá sdílená data
• kritická sekce je kus kódu, ve kterém prosec přistupuje ke sdíleným zdrojům
• je třeba zajistit, aby se v konkrétní kritické sekci nacházel nanejvýš jeden proces
  • podmínka vzájemného vyloučení (mutual exclusion), podmínka bezpečnosti, „safety“ -- pokud se nějaký proces nachází v kritické sekci spojené s určitými daty, nemůže do ní vejít jiný proces
  • podmínka trvalosti postupu (progress) podmínka živosti, „liveliness“ -- procesy, které čekají na přístup do kritické sekce, by se do ní měly dostat, pokud není další proces, který by toto blokoval (viz výše)
  • podmínka konečnosti doby čekání, (bounded waiting), podmínka spravedlnosti, „fairness“ -- pokud je přístup do kritické sekce umožněn procesům s vyšší prioritou, také ostatní procesy by se do ní měly v konečném čase dostat

Řešení problému kritické sekce

• softwarové řešení -- algoritmy s aktivním čekáním (busy waiting), Petersonův algoritmus
• hardwarové řešení -- vyžaduje speciální instrukce procesoru, aktivní čekání, instrukce test_and_set
• OS řešení -- potřebné funkce poskytuje OS, pasivní čekání, např. semafory, monitory, zasílání zpráv, vyšší režie

Semafor

• synchronizační nástroj, který lze implementovat i bez "busy waiting"
• OS proces "uspí" nebo "probudí"
• dvě atomické operace: wait & signal
  • Obecný semafor -- celočíselná hodnota z neomezovaného intervalu, lze implementovat binárním semaforem
  • Binární semafor -- celočíselná hodnota z intervalu <0,1>, lze snadněji implementovat

Monitor

• synchronizační nástroj vysoké úrovně
• umožňuje bezpečné sdílení abstraktního datového typu souběžnými procesy

Uváznutí

• skupina blokovaných procesů, ve které každý čeká na zdroj držený jiným procesem z této skupiny
• stárnutí -- požadavky jednoho nebo více procesů nebudou splněny v konečném čase
  • z důvodu vyšších priorit jiného procesu
  • z důvodu prevence uváznutí
• pokud chce proces použít zdroj: požádá, použije a uvolní

Charakteristika uváznutí

• vzájemné vyloučení (mutual exclusion) -- zdroj může naráz používat jen jeden proces
• ponechání si zdroje a čekání na další (hold and wait) -- získám zdroj a pak až chci něco dalšího
• bez předbíhání (no preemption) -- nemůžeme předbíhat, uvolňovat zdroje nuceně
• kruhové čekání (circular wait) -- P1 čeká na P2 a P2 čeká na P1

Graf přidělení zdrojů

• RAG (Resource-Allocation Graph)
• pokud graf neobsahuje cyklu, k uváznutí nedošlo
• pokud graf obsahuje cyklus, záleží na počtu instancí zdroje

Řešení uváznutí

• ignorace -- je to problém aplikace, OS to nebude řešit

Prevence

• přímé metody -- zneplatnění některé z podmínek:
  • vzájemné vyloučení -- u nesdílených zdrojů podmínka platí (př. virtualizace prostředků)
  • požadování všech prostředků naráz -- neefektivní, možnost stárnutí
  • odebírání požadovaných prostředků ostatním procesům
• nepřímé metody -- nepřipuštění cyklu v grafu:
  • uspořádání pořadí vyžadovaných prostředků

Obcházení uváznutí

• prostředek se nepřidělí, pokud by hrozilo uváznutí
• algoritmus, který se dynamicky dívá, jestli nemůže dojít k uváznutí

Obnova po uváznutí

• uváznutí povolíme, ale jeho vznik detekujeme a aplikujeme plán obnovy
• hledáme cykly v grafu
• ukončujeme proces po procesu (podle priority), dokud neodstraníme cyklus

Správa paměti

• pro běh procesu je nutné, aby program, který jej vykonává byl umístěn v operační paměti
• program je složen z různých částí: execute-only, read/write, private, public
• více procesů může sdílet společnou část paměti

Vázání adres

• při kompilaci -- umístění v paměti je známé předem, lze vygenerovat absolutní kód, při změně umístění se musí program znovu přeložit
• při zavádění -- umístění v paměti není v době kompilace známé, generuje se přemístitelný kód
• za běhu -- adresy budou vytvářeny dynamicky, v určitém limitu

MMU (Memory Management Unit)

• HW modul převádějící logické adresy na fyzické
• uživatelský program pracuje pouze s logickou adresou, fyzickou nevidí
• relokační registr

Adresový prostor

• LAP (Logický Adresový Prostor) -- logická adresa, virtuální adresa, dána adresou ve strojovém jazyku, generuje CPU
• FAP (Fyzický Adresový Prostor) -- adresa akceptovaná operační pamětí
• v době kompilace a době zadávání se LAP a FAP shodují
• při vázání v době běhu se mohou lišit

Dynamické zavádění

• programový kód se zavádí, dokud není spuštěn
• lepší využití paměti
• program nevyžaduje speciální podporu od OS

Dynamické vázání

• vázání je odkládáno na dobu běhu
• funkce, které nemáme k dispozici nahrazujeme kódem "stub", který se potom nahradí kódem funkce, až bude nahrána

Překryvy

• pokud za běhu programu nejsme schopni nahrát veškerou funkčnost programu
• rozdělíme program do modulů

Souvislé oblasti

• dvě sekce:
  • rezidentní OS, FAP s tabulkou ovladačů přerušení
  • uživatelské procesy
• přidělování jedné souvislé paměti:
  • schéma s relokačním registrem
  • relokační registr -- hodnota nejmenší fyzické adresy paměti procesu
  • mezní registr -- rozpětí logických adres, logická adresa <= mezní registr
• přidělování několika částí paměti:
  • díra -- blok volné paměti
  • evidenci o volných a obsazených sekcích vede OS

Přidělování paměti

• first-fit -- přiděluje se první dostatečně velká díra
• best-fit -- přidělí se nejmenší možná padnoucí díra
• worst-fit -- přidělí se největší díra

Problém fragmentace

• vnější fragmentace -- všechny díry jsou příliš malé, ale dohromady tvoří požadované místo
• vnitřní fragmentace -- nedostanu přesnou velikost požadované paměti, protože paměť je rozdělena do bloků, po kterých se paměť alokuje
• setřásání -- snižování vnější fragmentace, přesouvají se bloky paměti, aby vznikl jeden volný, nutná dynamická relokace

Stránkování

• rozdělení adresový prostor na stránky a rámce
• MMU překládá logické adresy na fyzické
• udržujeme seznam volných rámců
• vzniká vnitřní fragmentace kvůli pevné velikosti rámce

Tabulka stránek

• uložena v operační paměti
• počátek a konec je odkazován registry (PTBR, PTLR)
• číslo stránky a ofset stránky
• dvouúrovňová tabulka stránek -- jedna vnořená do druhé
• invertovaná tabulka stránek -- jaká stránka je ve kterém rámci, je časově náročnější
• sdílení stránek -- některý rámec odkazujeme několikrát, musí se nacházet na stejné logické adrese ve všech procesech, kód je reentrantní a „read-only“

Segmentování

• segment -- souvislá část paměti, která někde začíná a má určitou velikost
• segmentovací tabulka -- kde segment začíná a jeho velikost (base, limit)
  • STBR (Segment-table base register)
  • STLR (Segment-table length register)
• relokace -- dynamická, pomocí tabulky

Virtuální paměť

• oddělení LAP a FAP
• LAP může být větší než FAP
• efektivnější vytváření procesů
• techniky implementace:
  • stránkování na žádost
  • segmentování na žádost
• nutná podpora HW
• swapovací oblast v paměti pro odkládání stránek

Běh procesů ve virtuální paměti

• rezidentní množiny -- část procesů umístěných v FAP
• překlad LA na FA dělá HW
• pokud LA nelze převést, vyvolá se přerušení (page fault), proces se označí za čekající
• stránka se natáhne do operační paměti
• výhody: ve FAP lze udržovat více procesů najednou, "máme" více paměti, než máme

Zavádění stránek

• stránkování na žádost -- nezavádím, dokud se o stránku "nepožádá" (není k ní nutné přistoupit)
  • odkazovaná stránka
  • legální reference
  • nelegální reference
• předstránkování -- predikuji, co bude potřeba a nahraji to dopředu, princip lokality (v podobném čase potřebuju podobné adresy)

Kterou stránku nahradit?

• když je FAP plný
• některé rámce mohou být "zamknuty"

Výpadek stránky

• pokud se stránka nenachází v FAP, provede se přerušení
• "page fault"
• OS zavede stránku do paměti (získání prázdného rámce, zavedení stránky do rámce, úprava tabulky)
• opakování instrukce, která způsobila page fault

Volný rámec

• pokud nemáme volný rámec, hledáme oběť
• princip lokality -- lze dělat rozumné odhady o částech programu/dat potřebných v nejbližší budoucnosti

Algoritmy pro určení oběti

• nejmenší pravděpodobnost výpadku stránky
• čím více rámců máme, tím méně často dojde k výpadku stránky

• LRU (Least Recently Used) -- oběť = nejdéle neodkazovaná stránka
• FIFO (First-In-First-Out) -- oběť = stránka nejdéle zobrazená ve FAP
• Algoritmus poslední šance -- FIFO + vynechávání z výběru těch stránek, na které od posledního výběru bylo odkázáno

I/O systém

Hardware

• rozmanitý
• běžně používané prvky: port, sběrnice, hub
• instrukce IN (načtení třeba do registru), OUT

I/O porty

• skládá se ze 4 registrů:
  • Data-in -- čtení vstupu zařízení
  • Data-out -- zápis výstupu do zařízení
  • Status -- v jakém stavu se zařízení nachází
  • Control -- ovládání zařízení

Techniky provádění I/O

• polling
  • aktivní čekání
  • stavy: připraven, pracuje, chyba
• přerušení
  • OS -- ovladač přerušení
  • maskování přerušení
  • prioritní přerušení
• DMA
  • přímý přístup k paměti
  • paralelně můžeme dělat jinou činnost

Aplikační rozhraní I/O

• jádro OS se snaží poskytovat jednotné rozhraní různých HW zařízení
• vlastnosti I/O zařízení:
  • znakové (get, put)/blokové (read, write, seek) -- v Linuxu reprezentována jako speciální soubor (b), reprezentována dvěma čísli
  • sekvenční/přímý přístup
  • sdílené/dedikované
  • rychlost přenosu
  • read-write, read only, write only

Síťová zařízení

• mívají samostatné rozhraní OS
• sockets -- rozhraní, separující síťové protokoly od síťových operací
• přistupuje se jako k souborům
• přístupy k síťovým službám: roury, FIFOs, streams, queues, mailboxes

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

• blokující
  • synchronní
  • proces čeká na ukončení I/O
  • jednoduché na programování
  • někdy nedostačující kvůli nízké efektivitě
• neblokující
  • synchronní
  • pokud data nejsou k dispozici, nic se nestane -- nejsem blokován
• asynchronní
  • proces běží souběžně s I/O
  • konec I/O se hlášen signály
  • složité na programování
  • více efektivní

I/O subsystém v jádru

• plánování -- některé OS se snaží o "spravedlnost"
• buffer -- paměť pro vyrovnávání bloků I/O
• caching -- rychlá paměť udržující kopie, zajištění vyššího výkonu
• spooling -- udržování fronty dat určených k výpis na zařízení (tiskárna)
• rezervace zařízení -- exkluzivita přístupu k zařízení pro proces, hrozí deadlock, rezervace / uvolnění -- volání systému

Chybové řízení

• číslo chyby -- záporná hodnota
• syslog -- záznam o chybách v systému

Výkon

• I/O je nejvýznamnější faktor výkonu celého systému
• ovladače a programy I/O části jádra, přepínání kontextu při přerušení, kopírování dat, síťový provoz

Zvyšování výkonu

• minimalizovat počet přepnutí kontextu
• omezit kopírování dat
• minimalizovat počet přerušení (přenášením delších bloků)
• využití funkcí moderních řadičů
• využití DMA
• kombinace komponent (CPU, paměť, sběrnice, I/O zařízení) vedoucí k vysoké propustnosti

Vnější paměti

Primární paměti

• nejrychlejší
• energeticky závislé
• cache, operační paměti

Magnetické disky

• hlavičky a plotny se soustřednými kružnicemi a sektory
• adresace: jednorozměrné pole
• přístup k disku je starost OS
• doba přístupu (access time) = doba vystavení (seek time, nastavíme hlavičku na konkrétní cylindr) + průchod adresového sektoru pod čtecí/zápisovou hlavou (rotační zpoždění)
• disk scheduling
  • FCFS (First Come, First Served) -- popořadě
  • SSTF (Shortest Seek Time First) -- první nejbližší, má přirozené chápání, často implementován
  • SCAN -- algoritmus typu výtah, jede z jedné strany na druhou a po cestě plní požadavky, vhodný pro velkou zátěž na disku
  • C-SCAN -- poskytuje jednotnější čekací dobu, při cestě zpátky nevykonává požadavky, vhodný pro velkou zátěž na disku
  • C-LOOK -- výtah v rozmezí minima a maxima požadavků, často implementován
• moderní HW -- nemusí být známé mapování LA na FA, pořadí adres si disk optimalizuje sám (kromě priority z původu výpadku stránek a zápisu dat a metadat souborového systému)
• Linux -- algoritmy:
  • Noop -- nemění pořadí požadavků, pokud na sebe dva požadavky navazují, jsou sloučeny
  • Anticipatory -- jako Deadline, ale chvíli vyčká, jestli nepřijde následující požadavek
  • Deadline -- známka, do kdy má být požadavek vyřídit, pokud něco expiruje, je to vyřízeno ve speciální dávce, upřednostňuje čtení před zápisem
  • CFQ (Completely Fair Queue) -- každý proces má přidělený časový díl (slice), parametrizovatelný,

Technologie RAID

• Redundant Arrays of Independent (Inexpensive) Disks
• několik nezávislých disků
• vyšší výkon, kapacita a spolehlivost
• zvýšení spolehlivosti: redundance, zrcadlení, stínování (mirroring, shadowing)
• zvýšení výkonu: část dat je na jednom disku, část na jiném (bit-level striping, blok-level striping)
  • RAID Level 0: pouze více disků
  • RAID Level 1: zrcadlení disků
  • ...
  • RAID Level 6: odolnost při více než jedné poruše

Sekundární paměti

• středně rychlé
• energeticky nezávislé
• on-line storage
• flash disky, magnetické disky

Terciální paměti

• levná, vyměnitelná média
• pomalé
• energeticky nezávislé
• off-line storage
• floppy disky, magnetické pásky, optické disky

Souborový systém

= způsob organizace dat ve formě souborů a adresářů

• snadný přístup
• virtualizaci adresového prostoru média
• řízení přístupu

Typy souborových systémů

• souborové systémy v uživatelském prostoru
  • použití jaderného modulu FUSE
  • GlusterFS, sshfs
• souborové systémy v jaderném prostoru*
  • distribuované, síťové (NFS, Samba), lokální (
  • speciální souborové systémy
  • pseudo souborové systémy -- neobsahuje data, neukládá data, pouze je exportuje z kernelu, pouze se jako souborový systém tváří

Utility v uživatelském prostoru

• nástroje pro vytvoření
  • vytvoření souborového systému s danými parametry
  • mkfs, ext4, mkfs.xfs...
• nástroje pro kontrolu
  • kontrola, oprava, optimalizace
• nástroje pro správu

Inode -- struktura reprezentující všechny typy souborů v paměti (i_mode -- typ souboru, i_ino -- číslo inodu, i_nlink -- počet odkazů na inode, i_size -- velikost inode...)

Dentry (Directory entry) -- struktura mapující jméno souboru na číslo inode v paměti (d_parent -- ukazatel na rodičovskou dentry, d_name -- jméno záznamu, d_inode -- odkaz na inode, může být i Null...)

File -- reprezentuje otevřený soubor (f_path -- cesta k souboru, f_inode -- odkaz na příslušný inode, f_mode -- mód otevřeného souboru, F_pos -- aktuální pozice v souboru...)

Superblock -- identifikuje souborový systém na médiu v paměti (s_dev -- číslo identifikující zařízení, s_blocksize, s_magic...)

Blok -- nejmenší alokovatelná jednotka souborového systému

Stránka -- nejmenší alokovatelná jednotka virtuálního systému; přesun dat mezi pamětí a záznamovým médiem

Rozhraní souborových systémů

• systémová volání -- standardní rozhraní pro komunikaci s jádrem
• input/output control -- ioctl
• procfs, sysfs

VFS -- Virtual File System Switch

Dentry cache -- spravuje hašovací tabulku adresářových záznamů

Inode cache -- spravuje hashovací tabulku inode, urychluje přístup k inode

Bloková vrstva

• zprostředkovává rozhraní mezi souborovými systémy a ovladači blokových zařízení
• fronty -- vkládání požadavků do fronty k odeslání do ovladače zařízení
• I/O plánovače -- připojují a odpojují frontu za účelem seskupování požadavků do dávek
• virtuální bloková zařízení -- mdraid, device mapper

Interní struktury

• správa volného místa -- rozsahy bloků uložené ve stromech, zastaralejší řešení: bitmapy
• alokátor -- kritická část souborového systému, alokuje bloky ze zásoby volných bloků, snaha o prostorovou optimalizace, definuje rozložení disku
• diskový formát -- definuje formát a rozložení dmetadat na disku, statické/dynamické rozložení

Adresování bloků v souboru

• přímé/nepřímé adresování stromů
• extent tree