statnice:bakalar:b4b35osy

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Operační systémy a jejich architektury. Systémová volání, vlákna, procesy. Správa virtuální a fyzické paměti, souborové systémy. Bezpečnost, virtualizace. ======

[[https://fel.cvut.cz/cz/education/bk/predmety/46/83/p4683606.html|B4B35OSY]] [[https://osy.pages.fel.cvut.cz/docs/prednasky/|Webové stránky předmětu]]

  * **Systémová volání** – jak je implementována ochrana paměti jádra, jak se předávají parametry a data ze systémových volání, rozdíl mezi mikro jádrem a monolitickým jádrem.
  * **Vlákna, procesy** – jak se vytvoří proces, jak lze předat data mezi procesy. Jaký je rozdíl mezi vlákny a procesy, která data sdílejí různá vlákna jednoho procesu (registry, zásobník, lokální proměnné, globální proměnné, dynamicky alokované proměnné).
  * **Synchronizace vláken** – jaké jsou problémy při paralelním přístupu ke sdíleným datům, jaké existují synchronizační prostředky, co je to deadlock, kdy může nastat a jak se lze deadlocku vyhnout.
  * **Správa virtuální a fyzické paměti** – co je a jak vypadá stránkovací tabulka, jaké jsou zásadní nevýhody stránkování, TLB (translation-lookaside-buffer), víceúrovňové stránkování v 32-bitovém a 64-bitovém systému, odkládání stránek na disk, algoritmy výběru oběti, metoda copy-on-write.
  * **Souborové systémy** – jaké typy souborových systémů znáte, který je vhodný pro sekvenční čtení a který pro náhodné čtení souborů. Vysvětlete základní souborové systémy: FAT, systémy založené na inodech a systémy založené na extendech. Žurnálování – základní princip, kdy mohou vzniknout v souborovém systému chyby, jaké jsou úrovně žurnálování a jeho nevýhody.
  * **Bezpečnost** – co je Trusted Computing Base, základní metody řízení přístupu, jak se provádí útok na přetečení zásobníku, jak se lze takovému útoku bránit.
  * **Virtualizace** – softwarová virtualizace, metoda trap-and-emulate, virtualizace systémového volání, virtualizace stránkovacích tabulek, hardwarově asistovaná virtualizace.

===== Systémová volání =====
** jak je implementována ochrana paměti jádra, jak se předávají parametry a data ze systémových volání, rozdíl mezi mikro jádrem a monolitickým jádrem. **

Systémová volání jsou rozhraní mezi uživatelským a jádrovým režimem. Umožňují uživatelským aplikacím komunikovat s jádrem operačního systému a využívat jeho služby. Systémová volání se obvykle implementují pomocí přerušení nebo speciálních instrukcí (SYSCALL či SYSENTER), které přepínají procesor do jádrového režimu.
==== Jak se volají systémová volání ====
Jádro implementuje tzv ABI (Application Binary Interface), což je rozhraní, které definuje, jakým způsobem se volají systémová volání a jak se předávají parametry. 
Systémová volání mají čísla, která se uloží do registru (např. EAX v x86 architektuře) a parametry se předávají pomocí dalších registrů nebo na zásobník. Po provedení systémového volání jádro vrátí výsledek do registru a přepne procesor zpět do uživatelského 
režimu. 
Pokud potřebujeme předat velké množství dat, jako jsou struktury nebo pole, obvykle se používá ukazatel na paměť, který se předává jako parametr. Jádro pak může přistupovat k těmto datům přímo.

==== Ochrana paměti jádra ====

Hlavním způsobem ochrany paměti jádra je použití virtuální paměti. Každý proces má svou vlastní virtuální adresní prostor, což znamená, že každý proces vidí svou vlastní paměť a nemůže přistupovat k paměti jiných procesů nebo jádra. To se provádí pomocí stránkování, které mapuje virtuální adresy na fyzické adresy v paměti. 

V moderních architekturách procesory implementují tzv. **privilegované režimy** (rings of privilege). Jádro OS běží v nejvyšším privilegovaném režimu (např. ring 0 v x86), s plným přístupem k hardwaru a paměti. Uživatelské aplikace běží v méně privilegovaném režimu (např. ring 3 v x86) s omezeným přístupem. Přechod z uživatelského do jádrového režimu je řízen (např. přes systémová volání). (Pozn.: Intel v r. 2024 oznámil útlum podpory pro ring 1 a 2 v x86, jelikož je moderní OS nevyužívají).


==== Mikro jádro vs. monolitické jádro ====
Mikro jádro a monolitické jádro jsou dva základní přístupy k návrhu operačního systému:

  * **Mikro jádro:**
    * **Princip:** Minimalizuje kód běžící v jádrovém režimu. Většina OS služeb (např. ovladače zařízení, souborové systémy) běží jako oddělené procesy v uživatelském prostoru.
    * **Výhody:** 
      * Vyšší modularita a flexibilita.
      * Lepší bezpečnost a stabilita (izolace chyb – pád jedné služby neohrozí celé jádro).
      * Snazší vývoj, testování a přenositelnost jednotlivých komponent.
      * Menší velikost samotného jádra.
    * **Nevýhody:** 
      * Potenciálně nižší výkon kvůli režii meziprocesové komunikace (IPC) mezi službami a jádrem.
      * Složitější návrh mechanismů komunikace mezi procesy.
  * **Monolitické jádro:**
    * **Princip:** Většina OS služeb (včetně ovladačů, správy paměti, plánovače procesů) běží v jednom velkém programu v jádrovém režimu.
    * **Výhody:** 
      * Vyšší výkon, protože komunikace mezi komponentami probíhá pomocí přímých volání funkcí bez režie IPC.
      * Jednodušší návrh (alespoň zpočátku, pro základní funkce).
    * **Nevýhody:** 
      * Nižší modularita.
      * Větší komplexita kódu s rostoucí velikostí, což ztěžuje údržbu a ladění.
      * Chyba v jedné části může vést k pádu celého systému.
      * Obtížnější přenositelnost.
      * Větší bezpečnostní riziko, pokud je kompromitována část jádra.
  * **Hybridní jádro:**
    * Kombinuje prvky mikro jádra a monolitického jádra.
    * Některé části jádra jsou implementovány jako samostatné procesy (jako v mikro jádře), zatímco jiné části běží přímo v jádrovém režimu (jako v monolitickém jádře).

===== Vlákna a procesy =====
**jak se vytvoří proces, jak lze předat data mezi procesy. Jaký je rozdíl mezi vlákny a procesy, která data sdílejí různá vlákna jednoho procesu (registry, zásobník, lokální proměnné, globální proměnné, dynamicky alokované proměnné)**

==== Vlákna ====
  * **Vlákno** je lehká plánovací jednotka – sekvence instrukcí běžících na CPU.
  * Vlákna jednoho procesu **sdílejí** jeho adresní prostor, heap, globální a statické proměnné, otevřené soubory a další kernel-objekty.
  * Každé vlákno má **vlastní**:
    * kontext CPU (registry včetně PC, SP, …),
    * zásobník pro lokální proměnné a návratové adresy,
    * thread-local storage (TLS),
    * **TCB (Thread Control Block)** – kam se při přepnutí ukládá kontext vlákna.
  * Tradiční „monolitický“ proces = proces s jediným vláknem.
  * **Stavy vlákna:** Running (běží), Ready (připravené), Blocked/Waiting (čeká), Terminated (ukončené).
  * Přepnutí (context switch) uloží registr + stack pointer do TCB a načte kontext jiného vlákna.
  * OS plánuje vlákna podobně jako procesy; implementace může být kernel-level, user-level nebo hybridní (např. NPTL v Linuxu).

  * **PCB vs. TCB**
    * **PCB (Process Control Block)** – jádrová struktura **procesu**:
      * PID, stav procesu, ukazatel na tabulky stránek (adresní prostor), otevřené soubory, bezpečnostní údaje (UID, GID, capabilities), signálová maska, limity zdrojů, statistiky CPU času atd.
    * **TCB (Thread Control Block)** – lehčí záznam **vlákna**:
      * uložené registry (PC, SP …), ukazatel na vlastní zásobník, TLS pointer, stav vlákna, priorita, CPU afinity, statistiky.
    * **Vztah:** PCB udržuje seznam všech TCB patřících procesu.
      * Přepnutí mezi vlákny téhož procesu mění jen TCB (rychlejší); přepnutí na vlákno jiného procesu ukládá navíc PCB (pomalejší).

{{:statnice:bakalar:pasted:20250524-103550.png}}
**Sdílená vs. privátní data ve vícevazebném procesu**

| Kategorie                         | Sdílí všechna vlákna | Jedinečné pro vlákno |
| Kód (text) & globální data        | ✔                    | ✖ |
| Heap (dynamicky alokovaná paměť)  | ✔                    | ✖ |
| Otevřené popisovače souborů       | ✔                    | ✖ |
| Programový čítač & registry       | ✖                    | ✔ |
| Zásobník (stack)                  | ✖                    | ✔ |
| Thread-local storage (TLS)        | ✖                    | ✔ |


<markdown>
**Přednosti**: 
- Vlákno se vytvoří i ukončí rychleji než proces 
- Přepínání mezi vlákny je rychlejší než mezi procesy 
- Dosáhne se lepší strukturalizace programu

Realizace: - knihovna PThread, Java - třída Thread

</markdown>
==== Procesy ====
<markdown>
**Program**:
-  je soubor (např. na disku) přesně definovaného formátu obsahující instrukce, data, údaje potřebné k zavedení do paměti a inicializaci procesu 

**Proces**: 
- je spuštěný program – objekt jádra operačního systému provádějící výpočet podle programu
- je charakterizovaný svým paměťovým prostorem a kontextem (prostor v RAM se přiděluje procesům – nikoli programům!) 
- může vlastnit (kontext obsahuje položky pro) otevřené soubory, I/O zařízení a komunikační kanály, které vedou k jiným procesům, ... 
- obsahuje jedno či více vláken 
 
Proces je identifikovatelný jednoznačným číslem v každém okamžiku své existence  - PID (Process IDentifier)
 
 **Co tvoří proces:** 
-  Obsahy registrů procesoru (čítač instrukcí, ukazatel zásobníku, příznaky FLAGS, uživatelské registry, FPU registry)
-  Otevřené soubory
-  Použitá paměť: Zásobník – .stack, Data – .data, Program – .text

Rodič vytváří nový proces (potomka) voláním služby **fork** - vznikne identická kopie rodičovského procesu až na: 
- návratovou hodnotu systémového volání 
- hodnotu PID, PPID – číslo rodičovského procesu 

návratová hodnota určuje, kdo je potomek a kdo rodič (0 – jsem potomek, PID – jsem rodič a získávám PID potomka)
potomek může použít volání služby **exec** pro náhradu programu ve svém adresním prostoru jiným programem
</markdown>
**Stavy**

{{:statnice:bakalar:pasted:20250524-114645.png}}

Přepnutí od jednoho procesu k jinému nastává výhradně v důsledku nějakého přerušení (či výjimky) Procesy mohou čekat v různých frontách na vykonání (na přidělení procesoru, na dokončení I/O, na přidělení místa v hlavní paměti, na synchronizační událost, na zvětšení adresního prostoru).
**Meziprocesní komunikace**
{{:statnice:s_cbd745353e168c5cf1a67e4fa2573e59a956a598a03b4e79ea21df1273428276_1559044521854_image.png}}


===== Synchronizace vláken =====
**jaké jsou problémy při paralelním přístupu ke sdíleným datům, jaké existují synchronizační prostředky, co je to deadlock, kdy může nastat a jak se lze deadlocku vyhnout.**

  * cílem je zabránit současný přístup více vláken do kritické sekce programu

==== Problémy při paralelním přístupu ====
  * Deadlock – situace, kdy dva nebo více procesů čekají na uvolnění zdrojů, které jsou drženy jinými procesy, a žádný z nich nemůže
  * Data race – situace, kdy výsledek operace závisí na pořadí provedení vláken, což může vést k nečekaným výsledkům.
  * False sharing – situace, kdy více vláken přistupuje k různým částem stejného cache řádku, což může vést k neefektivnímu využití cache a snížení výkonu. (není kritické, ale může hodně zpomalit)

==== Deadlock ====
<markdown>
**Deadlock** (uváznutí) nastává, když skupina procesů (nebo vláken) čeká na zdroje takovým způsobem, že žádný ze zúčastněných nemůže pokračovat.  
Formálně se musí současně vyskytnout **čtyři Coffmanovy podmínky**:

1. **Vzájemné vyloučení (Mutual Exclusion)** – alespoň jeden zdroj lze v každém okamžiku držet jen jedním procesem.  
2. **Hold-and-Wait** – proces drží už přidělený zdroj a současně čeká na další.  
3. **Neodnímatelnost (No Preemption)** – zdroje nelze aktivně odebrat; uvolní je jen proces, který je drží.  
4. **Cyklické čekání (Circular Wait)** – existuje kruhové pořadí proces → zdroj → proces …, kde každý drží zdroj, na který ten další čeká.

Pokud všechny čtyři podmínky platí zároveň, vznikne deadlock.



### Jak se deadlocku vyhnout
* **Prevence:** zrušit některou z Coffmanových podmínek – např. zakázat Hold-and-Wait (nejdřív si musím vyžádat vše) nebo definovat **globální pořadí zámků**.  
* **Vyhýbání (Avoidance):** algoritmus Bankéře – systém dynamicky ověřuje, zda existuje **bezpečný stav** před přidělením zdroje.  
* **Detekce + Obnova:** periodicky procházet graf přidělení/čekání, najít cyklus a některý proces ukončit nebo odblokovat.

</markdown>

<tikzjax>
\usepackage{tikz}
\usetikzlibrary{arrows.meta, positioning}

\begin{document}
\begin{tikzpicture}[>=stealth, node distance=35mm, every node/.style={font=\small}]
  % Procesy
  \node[draw, rectangle, rounded corners, fill=blue!15] (A) {Proces A};
  \node[draw, rectangle, rounded corners, fill=blue!15, right of=A] (B) {Proces B};

  % Zdroje
  \node[draw, circle, fill=orange!20, below left of=A, yshift=-2mm] (R1) {$\,\text{Zámek }1\,$};
  \node[draw, circle, fill=orange!20, below right of=B, yshift=-2mm] (R2) {$\,\text{Zámek }2\,$};

  % Hrany „žádá“
  \draw[->, thick] (A) -- node[left, xshift=-2pt] {žádá} (R2);
  \draw[->, thick] (B) -- node[right, xshift=2pt] {žádá} (R1);

  % Hrany „drží“
  \draw[->, thick] (R1) -- node[left] {drží} (A);
  \draw[->, thick] (R2) -- node[right] {drží} (B);
\end{tikzpicture}
\end{document}
</tikzjax>
==== Synchronizační prostředky ====
<markdown>
* **Mutex (mutual exclusion)** – zámek, který umožňuje pouze jednomu vláknu přístup do kritické sekce. Pokud jedno vlákno zámek získá, ostatní musí čekat, dokud ho neuvolní.

* **Semafor** – základní vlastností je celočíselná proměnná. Dvě základní operace:  
  * **wait** – čeká, pokud je hodnota ≤ 0, poté snižuje hodnotu semaforu (pro vstup do kritické sekce).  
  * **signal** – zvyšuje hodnotu semaforu a probouzí čekající vlákno, pokud existuje.  
  * Na rozdíl od mutexu může semafor zařídit, že se vlákno *vždy* časem dostane do kritické sekce; u mutexu platí „kdo dřív přijde, ten dřív bere“, což může vést ke kompletnímu zablokování některých vláken.

* **Podmínkové proměnné (condition variables)** – synchronizační objekt určený k „čekání na stav“.
  * **Princip:** vlákno držící *mutex* otestuje predikát (např. „fronta není prázdná“).  
    Pokud predikát není splněn, **uloží se do čekací fronty cond-proměnné a *atomicky* uvolní mutex** → ostatní vlákna mohou predikát změnit.  
    Jakmile jiné vlákno predikát splní, **probudí čekající** pomocí `signal` (jedno) nebo `broadcast` (všechna).
  * **Hlavní operace** (`pthread` API):

    | Operace | Efekt |
    |---------|-------|
    | `pthread_cond_wait(&cond, &mutex)` | *Atomicky* odemkne `mutex`, uspí vlákno, po probuzení `mutex` znovu zamkne (posun do fronty plánovače). |
    | `pthread_cond_signal(&cond)` | Probudí **jedno** čekající vlákno (pokud nějaké). |
    | `pthread_cond_broadcast(&cond)` | Probudí **všechna** čekající vlákna. |

  * **Spurious wake-ups:** vlákno se může probudit i bez `signal` → **vždy testuj predikát v `while` smyčce**, ne v `if`.

    ```c
    pthread_mutex_lock(&m);
    while (queue_empty)         // test v *while*!
        pthread_cond_wait(&cond, &m); // uvolní m, uspí, znovu zamkne m
    dequeue_item();
    pthread_mutex_unlock(&m);
    ```

  * **Rozdíl vůči semaforu:**  
    * Semafor nese vlastní čítač; `wait` ho dekrementuje a když je > 0, hned pokračuje → nestrácí signály.  
    * Cond-proměnná **nepamatuje historii**: pokud proces zavolá `signal`, když nikdo nečeká, signál se **ztratí**. Predikát musí být ve sdílené proměnné chráněné mutexem.

  * **Typické vzory použití:**  
    * **Rendez-vous / producent–konzument** (fronta úloh)  
    * **Barrier** (vlákna čekají, než všechna dosáhnou určitého bodu)  
    * **Event flag** (čekání na vznik/neexistenci souboru, dokončení I/O atd.)

  * **Výhody:** umožňuje spaní bez aktivního čekání, přesné buzení jen když je co dělat.  
  * **Nevýhody:** vyžaduje disciplínu (predikát v `while` + mutex), signály se mohou ztrácet, pokud nejsou korektně použity.

* **Spin-lock** – zámek, který místo uspání **aktivně točí procesor** (busy-wait), dokud se neuvolní. Hodí se jen pro opravdu krátké kritické sekce.

  * **Princip (krok za krokem)**  
    1. **Sdílená proměnná `lock`** je inicializována na `0` = neobsazeno.  
    2. Vlákno provede ***atomickou*** instrukci `test-and-set` (TAS) nebo `compare-and-swap` (CAS):  
       - *TAS*: „ulož do `lock` hodnotu 1 **a vrať mi předchozí obsah**“.  
         ```asm
         tas:     mov  $1, %eax       ; pokusím se zapsat 1
                   xchg %eax, lock    ; ATOMICKY vyměním registr ↔ paměť
                   ; pokud %eax == 0 → zámek byl volný a mám ho
         ```  
       - *CAS*: „pokud je `lock == 0`, zapiš 1; jinak nedělej nic a dej mi současnou hodnotu“.  
         ```c
         bool acquired = __sync_bool_compare_and_swap(&lock, 0, 1);
         ```
       Tyto instrukce jsou **atomické**, protože CPU uzamkne cache-line / sběrnici a zaručí, že během operace *nikdo jiný nemůže mezitím měnit* tutéž buňku paměti.  
    3. **Výsledek atomické operace**  
       - návratová 0 → zámek byl volný, vlákno ho právě získalo ⇒ vstup do kritické sekce;  
       - návratová 1 → zámek je držen někým jiným ⇒ vlákno **spinuje**: opakuje krok 2 (obvykle s `pause` či exponenciálním back-off, aby nezahltilo sběrnici).  
    4. **Uvolnění**: vlákno po dokončení kritické sekce prostým zápisem nastaví `lock = 0`. (Operace zápisu je pro uvolnění bezpečná, protože z 1 → 0 není podmíněná.)  
       - U vícejádrových CPU se přidá *release memory fence* (`mfence`, `std::atomic_thread_fence(std::memory_order_release)`), aby se změny v kritické sekci *nejprve* propagovaly do paměti.

  * **Proč „atomické nastavení“?**  
    - Kdybychom dělali `if(lock==0) lock=1;`, dva thready mohou *současně* přečíst `0` a oba vstoupit – **race condition**.  
    - Atomická instrukce provede **čtení, test i zápis jako jedinou nepreemptovatelnou transakci**; hardware garantuje, že jen jeden zvítězí.

  * **Kdy se vyplatí**  
    - Kritická sekce ≤ ~100 CPU cyklů: inkrement globálního čítače, push/pop z velmi krátkého freelistu.  
    - OS kernel & interrupt context, kde uspání není možné.  
    - Vícejádrové systémy, kde je šance, že držitel zámku běží paralelně a brzy skončí.

  * **Nevýhody / na co si dát pozor**  
    - Na jednojádru může spin-lock místo zrychlení vyvolat *hladovění* (drží CPU a nepustí vlákno, které má zámek uvolnit).  
    - Dlouhé držení zámku = plýtvání CPU → raději mutex, který vlákno uspí.  
    - Bez férového algoritmu (ticket, MCS) může některé vláknou točit výrazně déle (*starvation*).
* **Monitor** – „třída + vestavěný zámek + čekací fronta“, která **zapouzdřuje sdílená data a pravidla používání**:
  * Voláš-li *veřejnou metodu* monitoru, **vstupuješ do monitoru** – systém ti **automaticky zamkne vnitřní mutex**.  
    Žádné jiné vlákno se dovnitř nedostane, dokud z metody nevrátíš – tím se zámek zase uvolní.  
    → Všechny změny dat uvnitř monitoru jsou atomické vůči ostatním vláknům.
  * Potřebuje-li metoda čekat na nějaký **stav** (např. „fronta není prázdná“), zavolá `wait(cond)`  
    - vlákno se přesune do **čekací fronty** dané podmínky a **současně opustí monitor** (uvolní vnitřní zámek),  
    - jiná vlákna mohou stav změnit.  
    Když někdo zavolá `signal(cond)`, jedno čekající vlákno se probudí, znovu vstoupí do monitoru a pokračuje – zámek už drží.
  * Důsledek: **uživatel monitoru nikdy ručně nemanipuluje se zámkem ani s podmínkovými proměnnými** – ty jsou schované „pod kapotou“.  
    Programátor píše jen logiku metod a test predikátů.
  * **Rozdíl proti „mutex + podmínková proměnná“ samostatně:**  
    - s monitorem nemůžeš omylem zapomenout zámek odemknout nebo přistoupit k datům bez ochrany;  
    - data jsou *soukromá*, dostupná výhradně skrze metody monitoru → jasně vymezená kritická oblast a platnost invariantů.  
    V podstatě jde o **bezpečnější a samo-dokumentující obal** nad dvojicí „mutex + cond-var“.
</markdown>

===== Správa virtuální a fyzické paměti =====
  * co je a jak vypadá stránkovací tabulka, jaké jsou zásadní nevýhody stránkování, TLB (translation-lookaside-buffer), víceúrovňové stránkování v 32-bitovém a 64-bitovém systému, odkládání stránek na disk, algoritmy výběru oběti, metoda copy-on-write.

==== Názvosloví ====
** FAP ** – Fyzický adresní prostor, skutečná paměť počítače, velikost závisí na možnosti základní desky a osazených modulech RAM.
** LAP ** - Logický adresní prostor, virtuální paměť, kterou vidí procesy, velikost závisí na architektuře procesoru a operačním systému (32-bit, 64-bit):
  * 32-bit: 4 GiB (2^32)
  * 64-bit: 16 EiB (2^64) – v praxi omezeno na 256 TiB (2^48) kvůli TLB a stránkovacím tabulkám

==== Segmentace ==== 
V programu používáme adresy zvané "selektory", existuje tabulka, která mapuje selektory na fyzické adresy.
{{statnice:bakalar:segmentace.png}}

<markdown>

Výhody segmentace 
- Segment má délku uzpůsobenou skutečné potřebě 
    - minimum vnitřní fragmentace 
    - Lze detekovat přístup mimo segment, který způsobí chybu segmentace – výjimku typu „segmentation fault“ 
- Lze nastavovat práva k přístupu do segmentu 
- Lze pohybovat s daty i programem v fyzické paměti – posun počátku segmentu je pro aplikační proces neviditelný a nedetekovatelný 

Nevýhody segmentace 
- Alokace segmentů v paměti je netriviální úloha 
    - Segmenty mají různé délky. 
    - Při běhu více procesů se segmenty ruší a vznikají nové → problém **externí fragmentace**. 
- Režie při přístupu do paměti

**Fragmentace**  
  *Externí (vnější) fragmentace* – Celkové množství volné paměti je sice dostatečné, aby uspokojilo požadavek procesu, avšak prostor není souvislý, takže ho nelze přidělit.  
  *Interní (vnitřní) fragmentace* – Přidělená díra v paměti je o málo větší než potřebná, avšak zbytek je tak malý, že ho nelze využít.
</markdown>


==== Stránkování ====
<markdown>

**Stránkování** (paging) rozděluje logický adresní prostor procesu na pevně velké bloky – **stránky** – a fyzickou paměť na stejně velké **rámce** (frames). Překlad stránka → rámec zajišťují **stránkovací tabulky** uložené v paměti; jádro je udržuje, hardware (MMU) je čte.
</markdown>

=== Základní pojmy ===
<markdown>

- **Velikost stránky** – 4 KiB na x86 / ARM (často i větší: 2 MiB „huge-pages“, 1 GiB „gigapages“).  
- **Page Frame Number (PFN)** – index rámce ve fyzické paměti.  
- **Virtuální adresa** = ⟨index stránky, offset ve stránce⟩.  
- **Page fault** – přerušení při přístupu na stránku, která není (zatím) namapována do RAM.
</markdown>

=== Eliminace externí fragmentace ===
<markdown>

- Fyzická paměť je rozdělena na **stejně velké rámce** – OS udržuje jen bitmapu nebo volný seznam rámců.  
- Jakákoli stránka může být umístěna do libovolného volného rámce ⇒ **žádné děravé „díry“ různé velikosti**.  
- Zbytková nevyužitá paměť se omezuje jen na *vnitřní* fragmentaci (max. 1 stránka na segment) – velikost je tedy **pevně ohraničená** volbou page size.  
- Oproti **segmentaci** tak kernel nemusí provádět drahou kompakci/relokaci velkých bloků a nedochází k postupnému „rozkouskování“ RAM.  
- Díky jednotné velikosti rámců i stránek je výběr volného místa jednoduchý (O(1) bitmapa) a predikovatelný.
</markdown>

=== Překlad adresy – krok za krokem ===
<markdown>

1. **TLB lookup** – MMU hledá záznam prospektivní (Virt → Fyz) ve *Translation Lookaside Bufferu* (malá L1 + L2 cache uvnitř CPU).  
2. **Miss v TLB** ⇒ hardware čte položku ze stránkovací tabulky v paměti (víceúrovňově).  
3. Pokud tabulky říkají „stránka není v RAM“, vyvolá se **page fault** → kernel vybere rámec (oběť), případně zapíše jeho obsah na disk (**swap**), načte požadovanou stránku, aktualizuje tabulku, zopakuje instrukci.
</markdown>

=== Víceúrovňové tabulky ===
<markdown>

| Architektura | Úrovně | Dekompozice virtuální adresy (příklady) |
|--------------|-------|-----------------------------------------|
| **x86 32-bit** | 2 (PDE, PTE) | 10 bit index PDE • 10 bit index PTE • 12 bit offset |
| **x86-64 (48 bit LAP)** | 4 (PML4, PDPTE, PDE, PTE) | 9 + 9 + 9 + 9 + 12 |
| **x86-64 (57 bit LAP, „5-level“)** | 5 (PML5…) | 9 × 5 + 12 |

> Více úrovní = tabulky jsou samy stránkované ⇒ menší rezidentní režie, protože se alokují jen podstromy skutečně používané procesem.
</markdown>

=== Nevýhody stránkování ===
<markdown>

- **Vícenásobný přístup** na jednu virtuální adresu: TLB miss → až 4–5 čtení z paměti, pak teprve data.  
- **Vnitřní fragmentace**: poslední stránka segmentu bývá ne plně využita.  
- **TLB thrashing** u pracovních setů větších než TLB.  
- **Režie správy swapu** (I/O latence) ⇒ thrashing celé RAM.
</markdown>

=== TLB (Translation Lookaside Buffer) ===
<markdown>

- Malá, plně asociativní cache překladů (desítky až stovky záznamů na jádro).  
- **Shoot-down**: když kernel změní mapování, musí invalidovat TLB všech CPU (IPI).  
- **ASID/PCID**: značka procesu v TLB zmenšuje nutnost flush při přepnutí procesu.
</markdown>

=== Odkládání stránek na disk (swapping) ===
<markdown>

- **Swap area** na HDD/SSD; stránky se zapisují při tlaku na RAM.  
- **Lazy** a **demand paging**: kód i data se načítají až při prvním přístupu (page fault).  
- **Thrashing**: když se pracovní set nevejde do RAM a proces tráví víc času swapováním než výpočtem.
</markdown>

=== Algoritmy výběru oběti (page replacement) ===
<markdown>
*„Oběť“ (victim) = stránka/rámec ve fyzické RAM, který jádro vyhodí (popř. odsune do swapu), když je nutné uvolnit místo pro jinou stránku po page faultu. Neplést s TLB – tam probíhá samostatný HW replacement – ani s celými stránkovacími tabulkami; ty se pouze upraví podle výsledku algoritmu výběru oběti.*

| Algoritmus | Idea | Poznámky |
|------------|------|----------|
| **FIFO** | vyhoď nejstarší stránku | jednoduchý, trpí Beladyho anomálií |
| **Second-Chance (Clock)** | FIFO + 1 bit „referenced“ | linuxový základ (`CLOCK-Pro`) |
| **LRU / Aproximované LRU** | vyhoď nejméně nedávno použitou | přesné LRU drahé; používají se bitmapy / časová okna |
| **Working-Set** | drž stránky aktivní v posledním intervalu ∆ | dobré, ale těžké měřit |
| **Adaptive (e.g., ARC)** | kombinuje LRU a LFU | v moderních OS/DB |
</markdown>

=== Copy-On-Write (COW) ===
<markdown>

1. Při `fork()` dostanou parent i child stránky **jen pro čtení** a ukazují na *stejný rámec*.  
2. První zápis vyvolá **page fault**. Kernel:  
   - alokuje nový rámec,  
   - zkopíruje obsah původní stránky,  
   - přemapuje zapisující proces na nový rámec (RW).  
3. Šetří kopírování při `fork+exec`, sdílí read-only data (např. `.text`, sdílené knihovny).
</markdown>

=== Shrnutí výhod stránkování ===
<markdown>

- **Eliminace externí fragmentace** – všechny rámce mají stejnou velikost, takže OS vždy najde volný rámec bez „děr“; na rozdíl od segmentace není nutná kompakce.  
- Snadný růst haldy/stacku – nové stránky se prostě namapují do dalších rámců.  
- Izolace procesů – ochranné bity (R/W/X, User/Supervisor).  
- Sdílení kódu a knihoven mezi procesy (stejný rámec mapovaný do více LAP).  
- Podpora virtuální paměti větší než fyzická (swap, demand paging).  
- Mechanismus pro COW, mmap souborů, lazy allocation.

Nevýhody (víceúrovňové přístupy, TLB miss, swap latence) se řeší větší TLB, huge-pages, lepším algoritmem náhrady a dostatkem RAM.
</markdown>

===== Souborové systémy =====
  * jaké typy souborových systémů znáte, který je vhodný pro sekvenční čtení a který pro náhodné čtení souborů. Vysvětlete základní souborové systémy: FAT, systémy založené na inodech a systémy založené na extendech. Žurnálování – základní princip, kdy mohou vzniknout v souborovém systému chyby, jaké jsou úrovně žurnálování a jeho nevýhody.

FAT, FAT32, exFAT, NTFS, ext2/3/4, btrfs, ZFS

možnosti uložení obsahu:
  * uložení souboru jako souvislý úsek bloků
    * posobné alokace paměti, rychlý přístup k datům
    * způsobuje fragmentaci a nutnost přesunů souborů
  * spojové seznamy
    * každý blok obsahuje i ukazatel na další blok (adresář obsahuje odkaz na 1. blok)
    * výhodné pro sekvenční přístup k souborům, ne pro vše ostatní
    * není možné data mapovat přímo z disku
    * jeden špatný sektor na disku může způsobit ztrátu celého souboru
  * indexové struktury
    * indexový blok obsahuje ukazatele na mnoho jiných bloků
    * vhodnější pro náhodný přístup, stále poměrně dobré pro sekvenční
    * může být potřeba použít více indexových bloků


=== FAT (File Allocation Table) ===
  * starý souborový systém s mnoha omezeními
  * něco mezi spojovými seznamy a indexovou strukturou
  * základní jednotka je cluset (4-32 KiB), max počet clusterů pro FAT16: $2^16$, pro FAT32: $2^{28}$, exFAT: $2^{32} - 10$
  * disk je rozložen na MBR (master boot record, informace o file systému - velikost, jméno, počet kopií FAT tabulek, etc.), FAT1, FAT2, root directory, data (má dvě FAT tabulky pro zajištění redundance)
  * v tabulce FAT jsou uloženy položky, kdy každá odpovídá jednomu clusteru na disku (hodnota položky udává číslo následujícího, nebo $-1$ pro konec souboru)
  * nevýhodou je fragmentace, omezená velikost a nutnost procházet FAT položky sekvenčně

=== Inodový souborový systém ===
  * metadata o jednotlivých souborech jsou uložena v inodech (Index Node), položka adresáře obsahuje kromě jména souboru i číslo inode
  * inode obsahuje pevný počet odkazů na datové bloky (z offsetu (pozice v souboru) lze jednoduše vypočítat, který odkaz použít pro přístup k datům), několik inode se vejde do jednoho bloku
  * když je soubor větší než počet odkazů na datové bloky v inode, odkat na další bloky je nepřímo přes blok odkazů

{{statnice:bakalar:osy_inode.png?500}}

rozložení na disku:
  * pevný počet inodů, samotný inode lze nalézt pomocí jeho indexu v tabulce
  * v superbloku je uložena informace o souborovém systému(celková délka, počet inode, počet volných bloků, odkaz na záložní superblok)
  * kořenový adresář

hledání volného místa
  * sekvenčním procházením (neefektivní)
  * poznání volného místa je obtížné (blok nul může být validní obsah souboru)
  * řešení jsou bitové mapy, kde každý bit udává obsazenost inodu nebo datového bloku
  * místo prohledávání inodů se prohledává tato bitová mapa

{{statnice:bakalar:osy_inode_bit.png?750}}

ext2-4
  * při práci se souborem je potřeba pracovat s bitmapou, inodem a datovými bloky
  * disky (hlavně rotační) přistupují rychleji k blokům blízko sebe, pokud budou datové bloky až na konci disku, hlavičky disků budou stále jezdit mezi inody a datovými bloky (pomalé)
  * proto jsou data organizována do skupin, kde se FS snaží alokovt datové bloky ve stejné skupině jako inody

{{statnice:bakalar:osy_inode_skupiny.png?750}}

=== Extents ===
  * tabulky bloků nejsou efektivní pro obrovské soubory, je potřeba velká režie
  * moderní FS mohou odkazovat místo na jednotlivé bloky na celé souvislé skupiny bloků
  * odkazovaná skupina s více než jedním blokem se nazývá extent
  * implementováno v ext4, NTFS, btrfs
  
{{statnice:bakalar:osy_extents.png?500}}


=== Žurnálování ===
  * před tím než se začne souborový systém modifikovat, uloží se seznam potřebných změn na vyhrazené místo (žurnál)
  * pokud dojde k pádu systému, zkontroluje se žurnál, změny disku se provedou dostatečně
  * implementováno v NTFS, ext3/4

{{statnice:bakalar:osy_journal.png?500}}

bezpečný způsob změny FS
  - Commit
  - Checkpoint
    - aktualizace bloků v souborovém systému (inode, bitmapy, data)
    - odstranění transakce z žurnálu

Možné scénáře při pádu:
  - do žurnálu se zapíše pouze část transakce
    * souborový systém je konzistentní, ale obsahuje původní data
    * při startu O se zjistí, že transakce v žurnálu není kompletní a ignoruje se
  - do žurnálu se zaíše celá transakce, ale neaktualizují se bloky
    * při startu OS se bloky aktualizují podle informací v žurnálu
  - zapíše se celá transakce, aktualizují se bloky ale transakce ze žurnálu není odstraněna
    * při startu OS se bloky přepíší ze žurnálu
  - do žurnálu se zapíše pouze část transakce (např. $TxB$, $I_\text{v2}$ a $TxE$, bez $B_\text{v2}$ a $D_\text{v2}$)
    * problém - HW disků se snaží provádět optimalizace, může změnit pořadí vykonávání příkazů zalaných OS
    * OS musí poslat speciální příkaz (bariéry), aby se data skutečně zapsala ve skutečném pořadí (garance vykonání všech příkazů před bariérou před pokračováním)
    * sekvence je tedy: $TxB$, $I_\text{v2}$, $B_\text{v2}$, $D_\text{v2}$, bariéra, $TxE$

nevýhodou je overhead, komplexnost, zpomalení zápisu

Flash paměti
  * zapisovat lze pouze do vymazaného bloku
  * zapsat lze pouze jednou, pak se musí vymazat
  * mazací blok bývá větší (např 4 MiB)
  * každý blok garantuje pouze určitý početpřepsání (např. 100 000)
  * často se měnící data (např. bitmapy, či FAT tabulka) drasticky snižují životnost paměti
  * změna jednoho bytu v souboru znamená smazání a znovu zapsání 4 MiB

řešením je nepoužívat Flash čipy samostatně, ale v kombinaci s řadičem - Flash Translation Layer
  * použití speciálních souborových systémů (UBIFS, JFFS2, NILFS)




===== Bezpečnost =====
  * co je Trusted Computing Base, základní metody řízení přístupu, jak se provádí útok na přetečení zásobníku, jak se lze takovému útoku bránit.

=== Trusted Computing Base ===
je množina všech entit kterým systém **věří** => pokud selžou, systém už nemusí být bezbečný.
Příklady: hardware, Jádro OS (nezbytně), administrátor serveru, …

=== Základní metody řízení přístupu ===
Základní princip  je **Matice řízení přístupu** - definuje stav ochrany v daném čase.

{{statnice:bakalar:osymatrix.png?200}}

  * Objekty jsou např. soubory
  * Subjekt je např. uživatel
  * Subjekty mohou být zároveň objekty

**Ukládání stavu ochrany** není typicky jako matice (moc „řídké“, neefektivní, dynamické).
V praxi 2 zřejmé volby:
  * Ukládání jednotlivých sloupců dohromady s objektem 
    - Každý sloupec je nazýván „seznam pro řízení přístupu“ (**access control list**, ACL) daného
      objektu
  * Ukládání jednotlivých řádků dohromady se subjektem
    - Definuje objekty, ke kterým má daný subjekt přístup – doména ochrany (**protection domain**)
      daného subjektu
    - Každý takový řádek je nazýván „seznam schopností“ (**capability list**)

== Seznamy pro řízení přístupu (ACL) ==
Implementováno skoro ve všech běžných OS
Subjekty jsou obvykle sloučeny do tříd
  * např. v UNIXu: majitel, skupina, ostatní
<code bash>
$ ls -ld /var/spool/cups
drwx--x--- 1 root lp 6754 Nov 22 00:00 /var/spool/cups
</code>
  * obecnější seznamy ve Windows či v současném Linuxu
    (příkazy get/setfacl)
  * mohou obsahovat „negativní“ oprávnění – např. pro
    vyloučení přístupu několika uživatelů ze skupiny
Meta-oprávnění:
  * řízení členství ve třídách
  * dovolují modifikaci ACL

{{statnice:bakalar:osyacl.png?150}}
== seznamy Schopností (capability lists) == 
**Schopnost** je prvek seznamu schopností (duh)
{{statnice:bakalar:osycap.png?250}}
**Pojemnovává objekt**, aby s ním program mohl zacházet (Obj2) a **uděluje** k objektu práva (RW)
Všichni kdo vlastní „schopnost“ mají právo s objektem pracovat
Méně časté použití v běžných systémech (ale pomalu se to mění)

== ACL vs capability list ==

| Seznamy řízení přístupu (ACL) | Schopnosti |
|-----------------------------------|----------------|
| - Tradiční, všeobecně známé, ale... | Lepší vlastnosti z pohledu bezpečnosti. |
| - Proces musí být schopen **zjistit jaké objekty existují** (pojmenování) a pak teprve je může používat (a nebo mu je k nim přístup odepřen) | - Neexistuje ambientní autorita, každému procesu jsou **delegovány** jen ty **schopnosti**, které potřebuje (zásada nejmenší pravomoci). |
| - Typicky to řeší tzv. **ambientní autorita** – tj. každý proces má všechna práva uživatele, který ho spustil (např. „vidí“ celý souborový systém a může zjistit, kteří další uživatelé jsou v systému). | - Např. proces nevidí všechny soubory, ale jen soubory (či celé adresářové stromy), které mu rodič nebo nějaká služba „delegoval(a)“. |
|    - Pokud program spouští jiný program, potomkovi nelze jednoduše práva omezit. | - Nikdo nemůže delegovat schopnosti, které sám nemá. |
|    - V Linuxu se dnes tento problém řeší pomocí „jmenných prostorů“ (**namespaces**), ale není to elegantní a trpí to některými nedostatky |  |

=== Stack Overflow - how to attack ===
Přetečení zásobníku nastane, když program zapíše více dat do bufferu (pole, proměnné) na zásobníku, než je jeho velikost.

=> Tím se přepíší další položky na zásobníku, jako jsou sousední proměnné, uložený rámec (frame pointer) nebo návratová adresa funkce.

Útočník může do bufferu vložit tzv. shellcode – malý strojový kód, který po vykonání může např. spustit shell a umožnit vzdálenou kontrolu systému.

Pokud útočník přepíše návratovou adresu funkce, může přesměrovat běh programu na vlastní kód (shellcode) nebo jiné instrukce v programu.

Útoky jsou často cílené na programy v jazyce C/C++, kde chybí automatická kontrola hranic polí.

Omezení shellcode: nesmí obsahovat binární nulové bajty (řetězce jsou ukončeny nulou). Proto se využívají speciální techniky kódování.

Moderní útočníci používají i Return-Oriented Programming (ROP) – místo vkládání nového kódu využívají již existující kód (gadgety) a poskládají z něj škodlivý program.
=== Stack Overflow - how to defend ===
Nespustitelný zásobník (Non-executable stack) – moderní procesory (Intel XD bit, ARM UXN) umožňují označit zásobník jako neexekuovatelný, takže nelze spustit kód přímo z dat na zásobníku.

Address Space Layout Randomization (ASLR) – náhodné rozmístění paměťových oblastí (zásobník, knihovny, program) při každém spuštění, což komplikuje útočníkovi nalezení přesných adres pro přesměrování.

Stack Canary / Stack Protector – do zásobníku se před návratovou adresu vloží speciální kontrolní hodnota (canary). Při návratu se zkontroluje, zda nebyla přepsána, a pokud ano, program se ukončí.

Retguard – kódování návratové adresy při vstupu do funkce a její dekódování při návratu; pokud je adresa změněná útočníkem, dojde k chybě a program skončí.

Bezpečné programování – vždy kontrolovat velikost vstupních dat před jejich uložením do bufferů, používat bezpečné funkce místo nebezpečných (např. strncpy místo strcpy).

Použití moderních jazyků a knihoven, které mají zabudovanou ochranu proti přetečení bufferu.

Oddělení práv a omezení přístupu – minimalizovat oprávnění běžících procesů, aby případné zneužití mělo co nejmenší dopad.






===== Virtualizace =====
  * softwarová virtualizace, metoda trap-and-emulate, virtualizace systémového volání, virtualizace stránkovacích tabulek, hardwarově asistovaná virtualizace.

Virtualizace je abstrakce hardwaru a jeho částečná emulace v softwaru.

Jmenujeme tři základní pojmy:
  * **Hostitel** - systém, na kterém běží hypervizor, na nejnižší úrovni fyzický hardware, v případě zapouzdřené virtualizace to neni fyzický hardware  
  * **Hypervizor** - software běžízí na hostiteli implementující virtuální hardware
  * **Host** - systém (většinou OS) běžící na virtuálním hardware poskytovaným hypervizorem

====Výhody VM==== 
  * **Izolace** - izolace zlepšuje zabezpečení systému
  * **Mnooho OS najednou** - jeden velmi mi výkonný server je možno kompletně nezávisle používat více lidmi mnoho účelů společnostmi/lidmi
  * **Praktické** - můžeme přesunout běžící instanci VM na jiného hostitele
  * **Dobré pro vývoj** - při vývojí věcí jako kernel (nepadá celý počítač)

====Problémy virtualizace====
Běžné **CPU** vykonává instrukce ve dvou režimech:
  * **uživatelský** - běžné uživatelské aplikace, není možné vykonávat určité akce jako např. zápis na disk
  * **privilegovaný** - režim jádra, má neomezený přístup k celému systému
  
Virtualizovaný stroj tedy nemůže běžet v privilegovaném režimu, běží v uživatelském - pro hostitele se tváří jako běžný program.
Je nutné tedy implementovat virtuální uživatelský a virtuální privilegovaný režim.

====Trap and emulate====
  * VM vykonává instrukce, jako by se jednalo o normální nativní OS.
  * Uživatelské instrukce běží normálně, nenastává problém.
  * Při privilegované instrukci nastane vyjímka (exception) - VM neví že běží celý ve uživatelském režimu.
  * Hypervizor tuto vyjímku odchytí a vyřeší - běh VM pokračuje a VM ani neví že nějaká vyjímka nastala

====Virtualizace Syscalls====
Využívá systému **trap and emulate** - privilegované instrukce vykonává jako by byl normální OS, hypervizor se postará o vyjímky

====Virtualizace Page Tables====


====Hard
Trace: • b4b39hry • b0b36pjv • b4b39iur • b0b39pgr • b4b01jag • be4b39vgo
Search

Navigation

Print/export

Tools

QR Code
