🖥️ BI-OSY – Operační systémy

📦 Program, Proces, Vlákno – základní pojmy

Program je spustitelný binární soubor uložený na disku. Formát závisí na OS: ELF (Linux/Unix), PE/PE32+ (Windows). Obsahuje sekce .text (kód) a .data (data).

Co si OS udržuje pro každý proces (PCB – Process Control Block):

• Identifikace: PID (Process ID), PPID (Parent PID), SID (Session ID)
• Bezpečnost: identita vlastníka (EUID, RUID), skupiny (GID), přístupová práva
• Správa paměti: informace pro překlad virtuálních adres (page table – struct mm_struct)
• Správa souborů: tabulka deskriptorů souborů
• IPC prostředky: semafory, roury, signály

Co si OS udržuje pro každé vlákno (TCB – Thread Control Block):

• TID (Thread ID)
• Hodnoty registrů CPU, čítač instrukcí (PC) – nutné pro přepínání kontextu
• Zásobník (stack) – lokální proměnné a history volání
• Priorita, stav vlákna, čas strávený na CPU

🔄 Vytvoření a ukončení procesu

Nový proces vznikne, když existující proces zavolá příslušné systémové volání:

• Unix/Linux: fork(2), execve(2)
• Windows: CreateProcessA()

fork() – vytvoří kopii (klon) aktuálního procesu:

• Vrací číslo potomka v rodiči, v potomkovi vrací 0, při chybě -1
• Jádro alokuje nové datové struktury; adresový prostor se „zkopíruje" od rodiče (v praxi pomocí Copy-on-Write)
• Čítač instrukcí ukazuje na instrukci za fork() – rodič i potomek pokračují dál na sobě nezávisle

execve(filename, argv, envp) – nahradí adresový prostor novým programem:

• Adresový prostor se přepíše obsahem spustitelného souboru
• Nový PC ukazuje na první instrukci nového programu

wait(int *status) – rodič zablokuje, dokud potomek neskončí; potomkova exit hodnota se uloží do status.

⚙️ Plánování vláken a přepínání kontextu

Jádro OS a vlákna sdílejí omezený počet jader CPU. Jedno vlákno může být v jednom okamžiku zpracováváno jedním logickým jádrem. Vlákna se na jádrech střídají pomocí preemptivního plánování.

Preemptivní plánování:

• Vláknu je přiděleno jádro CPU na základě plánovacích kritérií (priorita, ...)
• Přidělí se časové kvantum
• CPU je vláknu odebráno, pokud: uplyne časové kvantum (přerušení od časovače), vlákno provede systémové volání (např. V/V), nastane přerušení

Postup přepnutí kontextu:

1. Uloží se kontext původního vlákna (registry, PC, zásobníkový ukazatel)
2. Jádro OS naplánuje další vlákno
3. Nastaví se kontext nového vlákna

Stavy vlákna:

⚠️ Časově závislé chyby (Race Conditions) a kritické sekce

Klasický příklad: Dvě vlákna inkrementují sdílený čítač.

// Vlákno 1:          // Vlákno 2:
LOAD  R, [A]         LOAD  R, [A]
INC   R              INC   R
STORE [A], R         STORE [A], R
// Pokud se proloží → výsledek je 1 místo 2!

Pravidla korektního paralelního programu:

1. Žádné předpoklady nesmí být kladeny na rychlost vláken a počet jader
2. Zajistit výlučný přístup ke sdíleným prostředkům (žádné vlákno nesmí čekat nekonečně dlouho)
3. Mimo kritickou sekci nesmí být vlákno blokováno ostatními vlákny

🔒 Synchronizační nástroje

Základní přístupy k synchronizaci kritické sekce:

1. Aktivní čekání (Busy Waiting / Spinning)

Sdílená proměnná indikuje obsazenost sekce. Vlákno čekající na vstup opakovaně testuje stav proměnné ve smyčce. Implementace vyžaduje atomickou instrukci:

• ✅ Výhoda: minimální režie při krátkém čekání
• ❌ Nevýhoda: čekání zatíží CPU na 100%; může způsobit inverzní prioritní problém

2. Blokující volání (Mutex / Zámek)

POSIX: pthread_mutex_t, funkce pthread_mutex_lock(), pthread_mutex_unlock(). C++: std::mutex, std::lock_guard.

• ✅ Výhoda: čekání nezatěžuje CPU
• ❌ Nevýhoda: větší režie (změna stavu vlákna v jádře OS) → vyplatí se při delším čekání

3. Podmíněné proměnné (Condition Variables)

4. Semafor

POSIX: sem_t, sem_init(), sem_wait(), sem_post().

5. Bariéra

POSIX: pthread_barrier_t, pthread_barrier_wait(). Použití: maticové výpočty, paralelní simulace.

🏭 Klasické synchronizační úlohy

Producent–Konzument (Bounded Buffer Problem)

Producent vkládá data do sdílené fronty s omezenou velikostí N. Konzument data vybírá. Musíme řešit:

1. Výlučný přístup při vkládání/vybírání
2. Fronta prázdná → zablokuj konzumenta
3. Fronta plná → zablokuj producenta

Řešení pomocí semaforů:

sem_t empty;  // sem_init(&empty, N);  // počítá prázdná místa
sem_t full;   // sem_init(&full, 0);   // počítá plná místa
mutex_t mtx;  // mutex pro ochranu fronty

// Producent:          // Konzument:
sem_wait(&empty);      sem_wait(&full);
mutex_lock(&mtx);      mutex_lock(&mtx);
vlo_item();            vyber_item();
mutex_unlock(&mtx);    mutex_unlock(&mtx);
sem_post(&full);       sem_post(&empty);

Řešení pomocí podmíněných proměnných:

// Producent:
mutex_lock(&mtx);
while(count == N) cond_wait(&cv_full, &mtx);
insert_item();
count++;
cond_signal(&cv_empty);
mutex_unlock(&mtx);

💀 Uváznutí (Deadlock) – definice a příčiny

Výpočetní prostředky mohou být:

• Fyzické: fyzická paměť, tiskárna, ...
• Logické: proměnná, soubor, mutex, semafor, ...
• Odnímatelné (preemptable): lze odebrat bez rizika (např. CPU)
• Neodnímatelné (nonpreemptable): nelze bezpečně odebrat (většina prostředků)

Alokační graf znázorňuje alokaci prostředků vlákny (orientovaný graf). Hrana od prostředku k vláknu = alokovaný prostředek. Hrana od vlákna k prostředku = vlákno čeká. Každá smyčka v grafu = uváznutí.

📋 Coffmanovy podmínky

Uváznutí nastane pouze pokud jsou splněny všechny čtyři podmínky současně:

🛡️ Strategie pro řešení uváznutí

1. Pštrosí strategie (ignorování problému)

• Problém se neřeší – pokud uváznutí nastane, vyžaduje se zásah uživatele/administrátora
• Vhodná, pokud: systém obsahuje velký počet různě se chovajících vláken, pravděpodobnost uváznutí je malá, řešení by bylo příliš drahé
• Praktické řešení většiny univerzálních OS (Linux, Windows) – jádro je navrženo jako „deadlock free", na úrovni procesů se řeší částečně (limity ulimit)

2. Prevence uváznutí (porušení jedné z Coffmanových podmínek)

• Porušení vzájemného vyloučení: v praxi téměř nerealizovatelné bez race conditions
• Porušení neodnímatelnosti: vhodné, kde lze uložit stav (např. přepínání kontextu CPU)
• Porušení „drž a čekej": alokovat všechny prostředky najednou před použitím (worse utilization)
• Porušení kruhového čekání: číslování prostředků + alokace jen ve vzestupném pořadí → smyčka nemůže vzniknout. Příklad: večeřící filozofové – filosof musí brát vidličky ve vzrůstajícím pořadí čísel

3. Předcházení vzniku uváznutí (Banker's Algorithm)

Předpoklady: Předem známé požadavky vláken na prostředky. Koncept bezpečného stavu:

Používané matice/vektory: E (existence vector), F (free vector), Q (request matrix – celkové požadavky), A (allocation matrix – aktuálně alokované), M = Q - A (missing matrix).

Algoritmus detekce bezpečného stavu:

1. Existuje vlákno, které lze uspokojit volnými prostředky? → označ je, přidej jeho prostředky k volným, opakuj
2. Byla označena všechna vlákna? → ANO = bezpečný stav, NE = nebezpečný stav

4. Detekce a zotavení

Uváznutí se detekuje periodickými kontrolami (algoritmus podobný bankéřovu, ale pro aktuální požadavky Qc). Zotavení:

• Ukončení všech uvázlých vláken – typické v OS
• Postupné ukončování – dokud uváznutí přetrvává
• Rollback a restart – vyžaduje checkpoint mechanismus; pravděpodobnost opakovaného uváznutí je nízká díky nedeterminismu

🗺️ Virtuální adresní prostor (VAS) – motivace a princip

Proč VAS?

• Ochrana paměti: nelze číst/přepisovat data jiného procesu → bezpečnost (hesla, PIN), stabilita (pád procesu neovlivní ostatní)
• Jednodušší zavádění programu: lze zavést do libovolné volné fyzické paměti bez přepočítávání adres
• Větší adresní prostor než fyzická paměť: 32-bit OS → každý proces může adresovat 4 GB; fyzicky může být méně

Segmenty VAS: .text (kód), .data (globální proměnné), heap (halda, roste nahoru), libraries (sdílené knihovny), stack (zásobník, roste dolů).

📄 Stránkování – základní princip

Proč stránkování?

• Elegantně řeší fragmentaci fyzické paměti – každé stránce lze přiřadit libovolný rámec
• Celý VAS nemusí být v paměti – stačí pouze aktuálně používané stránky
• Nepoužívané stránky mohou být odloženy na disk (swap)

Struktura virtuální adresy:

🔧 MMU a jednoúrovňová stránkovací tabulka

Jednoúrovňová stránkovací tabulka obsahuje pro každou stránku VAS jeden řádek:

• Číslo rámce – kam je stránka namapována
• Řídicí bity:
  • P (Present) – stránka je v hlavní paměti
  • A (Accessed) – ke stránce se přistupovalo
  • D (Dirty) – obsah byl modifikován (před odložením nutno zapsat na disk)
  • W (Write) – lze stránku modifikovat?
  • X (Execute) – stránka obsahuje spustitelný kód?
  • U (User/Supervisor) – přístupná v uživatelském modu?
  • G (Global) – platná ve všech procesech (sdílené jádro OS)
  • C (Cache) – lze používat cache? (zakázat pro registry periferií)

Překlad adresy (jednoúrovňová ST):

1. Rozděl virtuální adresu na číslo stránky (index do ST) a offset
2. Přečti řádek ST[číslo stránky] → zkontroluj bit P
3. Bit P = 1: fyzická adresa = číslo rámce + offset → přístup do paměti
4. Bit P = 0: výpadek stránky → OS obsluha

🌲 Víceúrovňová stránkovací tabulka

Princip (n-úrovňová ST):

• V paměti je vždy pouze top-level tabulka (úroveň 1)
• Tabulky úrovní 2 ... n existují jen pro používané části VAS → úspora paměti
• Každá tabulka úrovně 1 ... n-1 obsahuje Present bit + číslo rámce s tabulkou další úrovně
• Tabulka úrovně n obsahuje Present bit + číslo rámce s daty

Příklad – dvouúrovňová ST (x86 32-bit):

Virtuální adresa: [10 bitů L1 index | 10 bitů L2 index | 12 bitů offset]

Pro 128 procesů stejné zátěže jako dříve: 128 × [1 × (1024 × 4B) + 3 × (1024 × 4B)] = 128 × 16 KB = 2 MB (oproti 512 MB u jednoúrovňové!).

Reálné architektury:

🔀 Invertovaná stránkovací tabulka

Překlad adresy:

1. Hašovací funkce z (PID, číslo stránky) → index do invertované ST
2. Porovnej záznam v tabulce s (PID, číslo stránky)
3. Shoda → číslo řádku = číslo rámce → fyzická adresa = rámec + offset
4. Neshoda → procházej zřetězení (chain) → nebo výpadek stránky

⚡ Translation Lookaside Buffer (TLB)

Obsah jedné položky TLB:

• valid bit – platná položka?
• Číslo stránky (page number)
• Číslo rámce (frame number)
• ASID – Address Space ID (identifikátor adresního prostoru – aby TLB mohl být sdílený více procesy)
• Kopie řídicích bitů ze stránkovací tabulky (W, X, U...)

Průběh překladu s TLB:

1. MMU hledá číslo stránky v TLB → TLB Hit: fyzická adresa = rámec z TLB + offset → velmi rychlé (~1 cyklus)
2. TLB Miss: MMU prohledá stránkovací tabulky v paměti, aktualizuje TLB, přeloží adresu
3. Při výpadku stránky: OS obslouží, aktualizuje ST, TLB, restartuje instrukci

🔁 Obsluha výpadku stránky (Page Fault Handler)

OS obsluha výpadku stránky (krok za krokem):

1. Ověření platnosti virtuální adresy (leží ve VAS?) a oprávněnosti přístupu (zápis do R/O stránky?) → pokud ne: Segmentation Fault
2. Nalezení volného rámce (Get Free Frame):
   • Pokud existuje volný rámec → použij jej
   • Pokud ne → vyber oběť pomocí algoritmu pro náhradu stránek (PRA)
   • Je oběť dirty (D bit)? → zapiš ji nejprve na disk (swap)
   • Zneplatni záznamy ST a TLB pro odložený rámec ve všech dotčených procesech
3. Načtení stránky do rámce:
   • Ze souboru (file-backed VMA, např. .text, .data programu, mmap)
   • Ze swapu (anonymní stránka dříve odložená)
   • Inicializace nulou (nová anonymní stránka – heap, stack)
4. Aktualizace stránkovacích tabulek (nastavení P bitu, čísla rámce)
5. Aktualizace TLB
6. Restart přerušené instrukce

🧮 Algoritmy pro náhradu stránek (Page Replacement Algorithms)

Cíl: minimalizovat počet výpadků stránek. Vychází z principu časové a prostorové lokality.

1. Optimální algoritmus (OPT)

• Nahradí stránku, ke které se bude přistupovat nejpozději v budoucnosti
• ✅ Generuje minimální počet výpadků (dolní mez)
• ❌ Nerealizovatelný (neznáme budoucnost) – slouží jako benchmark

2. NRU algoritmus (Not Recently Used)

• Třídy stránek podle R (referenced) a D (dirty) bitů: Třída 0 (R=0,D=0), 1 (R=0,D=1), 2 (R=1,D=0), 3 (R=1,D=1)
• Nahradí stránku z neprázdné třídy s nejnižším číslem
• OS periodicky resetuje R bit
• ✅ Jednoduchý, rozumný počet výpadků

3. FIFO algoritmus (First-In First-Out)

• Nahradí stránku, která je v paměti nejdéle (hlava fronty)
• ✅ Jednoduchý na implementaci
• ❌ Nezohledňuje frekvenci přístupu → velký počet výpadků; trpí Bélády anomálií (více rámců → více výpadků)

4. Clock algoritmus (modifikovaný FIFO)

• Kruhová fronta + ručička (ukazatel). Každá stránka má R bit.
• Při hledání oběti: pokud R=1 → vynuluj R, posuň ručičku. Pokud R=0 → tato stránka je oběť.
• ✅ Lepší než FIFO, rozumná implementace. Varianta se dvěma ručičkami (two-handed clock) – používá se ve SVR4 Unix a nástupcích.

5. LRU algoritmus (Least Recently Used)

• Nahradí stránku, ke které se přistupovalo nejdéle (nejstarší přístup)
• Dobrá aproximace optimálního algoritmu (využívá časovou lokalitu)
• ✅ Nízký počet výpadků
• ❌ Implementace: nutný speciální HW čítač nebo matice přístupů → v čisté podobě příliš drahé

6. Aging algoritmus (softwarová simulace LRU)

• Pro každou stránku n-bitový čítač C (inicializován na 1 při načtení)
• Periodicky: posun C doprava o 1 bit, nastavení MSB na hodnotu R bitu, reset R bitu
• Oběť = stránka s nejmenší hodnotou C
• ✅ Menší režie než LRU, rozumná aproximace
• ❌ Pamatuje jen omezenou historii (n bitů); nerozliší přesný čas přístupu v jedné periodě

🏗️ Návrh stránkovacích systémů – klíčové otázky

Kdy nahrát stránku?

• Demand paging – stránka se nahraje až při prvním přístupu (výpadek stránky)
• Pre-paging – při výpadku se nahraje stránka + několik sousedních (prostorová lokalita) → méně přenosů z disku

Kolik rámců přidělit procesu?

• Málo rámců → mnoho výpadků stránek → thrashing (zahlcení výměnou stránek)
• Od určitého počtu se počet výpadků výrazně nemění (= Working Set)
• Variable-allocation: OS přiděluje rámce podle aktuálních potřeb procesu

Sdílení paměti:

• .text segment sdílených knihoven → sdílení v paměti (MAP_SHARED), jen jeden rámec na systém
• .data sdílených knihoven → MAP_PRIVATE + Copy-on-Write: kopie se vytvoří až při zápisu

Kernel space a KPTI (Meltdown):

Jádro OS je tradičně namapováno do VAS každého procesu (chráněno U bitem = 0). Po útoku Meltdown (2018): KPTI (Kernel Page Table Isolation) – do user space se namapuje pouze nutné minimum jádra; jádro má vlastní oddělené ST. Při systémovém volání se přepíná PTBR.