The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b35osy [2025/06/02 15:45] – [Jak se deadlocku vyhnout] mistrjirkastatnice:bakalar:b4b35osy [2025/06/09 20:32] (current) – [5. Souborové systémy] zapleka3
Line 11: Line 11:
   * **Virtualizace** – softwarová virtualizace, metoda trap-and-emulate, virtualizace systémového volání, virtualizace stránkovacích tabulek, hardwarově asistovaná virtualizace.   * **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í =====+===== 1. 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. ** ** 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. 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í ==== ==== 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.  +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  +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.   
-režimu.  +Pokud potřebujeme předat větší množství dat, jako jsou struktury nebo pole, používá se ukazatel na paměť, který se předává jako parametr. Jádro pak může přistupovat k těmto datům přímo. 
-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.+ 
 +==== Předávání parametrů a návratových hodnot ==== 
 +Parametry systémového volání se předávají různými způsoby podle architektury a konkrétního API: 
 + 
 +  * **Jednoduché hodnoty** (čísla, příznaky, velikosti atd.) se ukládají do registrů – např. v Linuxu na x86-64 se používají registry **rdi, rsi, rdx, r10, r8, r9**. 
 +  * **Složitější struktury nebo pole** se předávají pomocí **ukazatelů**, které jádro validuje a dereferencuje. 
 +  * **Výsledky systémových volání** se obvykle vrací do jednoho registru (např. **rax**) – typicky návratový kód nebo počet zpracovaných bajtů. V případě chyby se vrací záporný návratový kód (např. `-EINVAL`, `-EPERM`, ...). 
 + 
 +**Předávání přes paměť** je bezpečnější, protože jádro ověří přístupová práva (např. zda proces může číst/zapisovat do dané oblasti).
  
 ==== Ochrana paměti jádra ==== ==== 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á svůj 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. +Hlavním způsobem ochrany paměti jádra je použití **virtuální paměti**. Každý proces má svůj 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 moderních architekturách procesory implementují tzv. **privilegované režimy** (*rings of privilege*). Jádro OS běží v nejvyšším privilegovaném režimu (**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 (**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í.
  
-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í).+  * **Důsledek:** Uživatelský kód nemůže přímo přistupovat k jádrové paměti – případný pokus vede k výjimce (segfault).
  
 +**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 vs. monolitické jádro ====
Line 56: Line 69:
     * 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).     * 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 =====+===== 2. 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é)** **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é)**
  
Line 69: Line 82:
   * Tradiční „monolitický“ proces = proces s jediným vláknem.   * Tradiční „monolitický“ proces = proces s jediným vláknem.
   * **Stavy vlákna:** Running (běží), Ready (připravené), Blocked/Waiting (čeká), Terminated (ukončené).   * **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.+  * Přepnutí (context switch) uloží registry + 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).   * OS plánuje vlákna podobně jako procesy; implementace může být kernel-level, user-level nebo hybridní (např. NPTL v Linuxu).
  
Line 84: Line 97:
  
 | Kategorie                         | Sdílí všechna vlákna | Jedinečné pro vlákno | | Kategorie                         | Sdílí všechna vlákna | Jedinečné pro vlákno |
-| Kód (text) & globální data        | ✔                    | ✖ | +|----------------------------------|-----------------------|-----------------------| 
-| Heap (dynamicky alokovaná paměť)  | ✔                    | ✖ | +| Kód (text) & globální data       | ✔                     | ✖ | 
-| Otevřené popisovače souborů       | ✔                    | ✖ | +| Heap (dynamicky alokovaná paměť) | ✔                     | ✖ | 
-| Programový čítač & registry       | ✖                    | ✔ | +| Otevřené popisovače souborů      | ✔                     | ✖ | 
-| Zásobník (stack)                  | ✖                    | ✔ | +| Programový čítač & registry      | ✖                     | ✔ | 
-| Thread-local storage (TLS)        | ✖                    | ✔ |+| Zásobník (stack)                 | ✖                     | ✔ | 
 +| Thread-local storage (TLS)       | ✖                     | ✔ |
  
 +**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.
  
-<markdown> +**Realizace:** 
-**Přednosti**:  +  * knihovna **PThread** 
-- Vlákno se vytvoří i ukončí rychleji než proces  +  * v jazyce Java pomocí třídy **Thread**
-- 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 ==== ==== Procesy ====
-<markdown> +  * **Program** – soubor (např. na disku) definovaného formátu obsahující instrukce, data a údaje potřebné k inicializaci procesu. 
-**Program**: +  * **Proces** – spuštěný program, spravovaný operačním systémem: 
--  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  +    * má vlastní virtuální adresní prostor, otevřené soubory, systémové prostředky, ..., 
- +    * může obsahovat více vláken (multithreadovaný proces), 
-**Proces**:  +    * je identifikovatelný **PID** (Process IDentifier), 
-- je spuštěný program – objekt jádra operačního systému provádějící výpočet podle programu +    * paměť procesu: `.text` (kód), `.data` (globální), `.stack`, heap.
-- 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:  +  * Proces je objekt s vlastním kontextem: 
-- návratovou hodnotu systémového volání  +    * registry procesoru (čítač instrukcí, ukazatel zásobníku, příznaky FLAGS, uživatelské registry, FPU registry) 
-- hodnotu PID, PPID – číslo rodičovského procesu +    * přidělený paměťový prostor 
 +    * seznam otevřených souborů 
 +    * komunikační kanály (pipes, sockets...) 
 +    * použitá paměť: Zásobník – .stack, Data – .data, Program – .text
  
-návratová hodnota určuje, kdo je potomek a kdo rodič (0 – jsem potomek, PID – jsem rodič a získávám PID potomka) +==== Vytváření procesů a předávání dat ==== 
-potomek může použít volání služby **exec** pro náhradu programu ve svém adresním prostoru jiným programem +  * Proces vytváří nový proces voláním systémového volání **fork()**. 
-</markdown> +    * vznikne téměř identická kopie rodičovského procesu. 
-**Stavy**+    * rozdíly: návratová hodnota (0 pro dítě, PID pro rodiče), nový PID. 
 +  * Dítě může použít **exec()** k přepsání svého kódu jiným programem. 
 +  * Předání dat mezi procesy: 
 +    * pomocí **sdílené paměti** (např. `shm_open`, `mmap`) 
 +    * **potrubí (pipes)** – unidirekcionální datový tok 
 +    * **sockets** – obousměrná komunikace, i mezi různými stroji 
 +    * **signály** – pro jednoduchou asynchronní notifikaci 
 +    * **souborový systém** – zápis do souboru čitelný jiným procesem
  
 +==== Stavy procesů ====
 {{:statnice:bakalar:pasted:20250524-114645.png}} {{: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). +  * Přepnutí mezi procesy nastává po přerušení, výjimce nebo explicitním uvolnění CPU. 
- +  * Proces může čekat v různých frontách: na CPU, na I/O, na synchronizaci, na alokaci paměti atd.
-**Meziprocesní komunikace**+
  
 +==== Meziprocesní komunikace ====
 {{:statnice:s_cbd745353e168c5cf1a67e4fa2573e59a956a598a03b4e79ea21df1273428276_1559044521854_image.png}} {{:statnice:s_cbd745353e168c5cf1a67e4fa2573e59a956a598a03b4e79ea21df1273428276_1559044521854_image.png}}
  
 +  * IPC je klíčová pro spolupráci procesů.
 +  * Výběr prostředku závisí na požadavcích (rychlost, bezpečnost, rozsah).
  
-===== Synchronizace vláken =====+ 
 +===== 3. 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.** **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.**
  
Line 146: Line 163:
   * 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.   * 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)   * 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)
 +
 +==== Problémy při paralelním přístupu ====
 +  * **Deadlock** – situace, kdy dva nebo více procesů čeká na uvolnění zdrojů, které jsou drženy jinými, a žádný nemůže pokračovat.
 +  * **Data race** – výsledek výpočtu závisí na pořadí přístupu k proměnným → nekonzistentní chování.
 +  * **False sharing** – více vláken přistupuje k různým částem stejného cache-řádku → výkonnostní problém (neporušuje správnost, ale zpomaluje).
  
 ==== Deadlock ==== ==== Deadlock ====
-<markdown> +Deadlock (uváznutí) nastává, když skupina vláken čeká na zdroje způsobem, který vytvoří cyklus a nikdo nemůže pokračovat.
-**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.   +**Coffmanovy podmínky pro vznik deadlocku:** 
-2. **Hold-and-Wait** – proces drží už přidělený zdroj a současně čeká na další.   +  - **Vzájemné vyloučení** – zdroj může držet jen jedno vlákno. 
-3. **Neodnímatelnost (No Preemption)** – zdroje nelze aktivně odebrat; uvolní je jen proces, který je drží.   +  - **Hold and wait** – vlákno drží jeden zdroj a čeká na další. 
-4. **Cyklické čekání (Circular Wait)** – existuje kruhové pořadí proces → zdroj → proces …, kde každý drží zdroj, na který ten další čeká.+  - **Neodnímatelnost** – zdroje nelze násilně odebrat. 
 +  - **Cyklické čekání** – vznikne kruh, kde každé vlákno čeká na zdroj jiného.
  
 Pokud všechny čtyři podmínky platí zároveň, vznikne deadlock. Pokud všechny čtyři podmínky platí zároveň, vznikne deadlock.
  
- +**Jak se deadlocku vyhnout:** 
- +  * **Prevence** – např. nepovolíme Hold-and-Wait nebo nastavíme globální pořadí zámků. 
-### Jak se deadlocku vyhnout +  * **Vyhýbání (Avoidance)** – algoritmus bankéře: systém ověřuje, zda přidělením zdroje nevznikne nebezpečný stav. 
-* **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ů**.   +  * **Detekce + obnova** – detekce cyklů v grafu čekání; obnova ukončením nebo restartem procesu.
-* **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> <tikzjax>
Line 198: Line 215:
 \end{document} \end{document}
 </tikzjax> </tikzjax>
 +
 ==== Synchronizační prostředky ==== ==== 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:   +  * **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í.
-  * **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“. +  * **Semafor** – celočíselná proměnná s operacemi: 
-  * **Princip:** vlákno držící *mutex* otestuje predikát (např. „fronta není prázdná“).   +    * **wait** – pokud je hodnota ≤ 0, vlákno čeká; jinak se hodnota sníží. 
-    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.   +    * **signal** – zvýší hodnotu a probudí čekající vlákno, pokud existuje. 
-    Jakmile jiné vlákno predikát splní, **probudí čekající** pomocí `signal` (jedno) nebo `broadcast` (všechna). +    * Na rozdíl od mutexu může semafor zaručit, že se vlákno *vždy* časem dostane do kritické sekce; u mutexu může dojít ke *hladovění*.
-  * **Hlavní operace** (`pthread` API):+
  
-    | Operace | Efekt | +  * **Podmínkové proměnné (condition variables)** – slouží k čekání na konkrétní stav: 
-    |---------|-------| +    * Vlákno držící mutex otestuje predikát (např. "fronta není prázdná"). 
-    | `pthread_cond_wait(&cond, &mutex)` | *Atomicky* odemkne `mutex`, uspí vlákno, po probuzení `mutex` znovu zamkne (posun do fronty plánovače). | +    * Pokud predikát neplatí, vlákno se přesune do čekací fronty a *atomicky* uvolní mutex. 
-    | `pthread_cond_signal(&cond)` | Probudí **jedno** čekající vlákno (pokud nějaké). | +    * Po splnění predikátu může jiné vlákno zavolat `signal` (probudí jedno) nebo `broadcast` (všechna). 
-    | `pthread_cond_broadcast(&cond)` | Probudí **všechna** čekající vlákna. |+ 
 +    * **Hlavní operace (`pthread` API):** 
 +      * `pthread_cond_wait(&cond, &mutex)` – atomicky odemkne mutex, uspí vlákno, po probuzení mutex znovu zamkne. 
 +      * `pthread_cond_signal(&cond)` – probudí jedno čekající vlákno. 
 +      * `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`.   * **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 +<code c> 
-    pthread_mutex_lock(&m); +pthread_mutex_lock(&m); 
-    while (queue_empty)         // test v *while*! +while (queue_empty)         // test v *while*! 
-        pthread_cond_wait(&cond, &m); // uvolní m, uspí, znovu zamkne m +  pthread_cond_wait(&cond, &m); // uvolní m, uspí, znovu zamkne m 
-    dequeue_item(); +dequeue_item(); 
-    pthread_mutex_unlock(&m); +pthread_mutex_unlock(&m); 
-    ```+</code>
  
   * **Rozdíl vůči semaforu:**     * **Rozdíl vůči semaforu:**  
Line 241: Line 257:
   * **Nevýhody:** vyžaduje disciplínu (predikát v `while` + mutex), signály se mohou ztrácet, pokud nejsou korektně použity.   * **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.+  * **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)**   
 +      * **Sdílená proměnná `lock`** je inicializována na `0` = neobsazeno.   
 +      *  Vlákno provede ***atomickou*** instrukci `test-and-set` (TAS) nebo `compare-and-swap` (CAS) 
 +    * **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).   
 +    * **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. 
 +   
 +**TAS**: „ulož do `lock` hodnotu 1 **a vrať mi předchozí obsah**“.   
 +<code c> 
 +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 
 +</code>
  
-  * **Princip (krok za krokem)**   +**CAS**: „pokud je `lock == 0`, zapiš 1; jinak nedělej nic a dej mi současnou hodnotu“.   
-    1. **Sdílená proměnná `lock`** je inicializována na `0` = neobsazeno.   +<code c> 
-    2. Vlákno provede ***atomickou*** instrukci `test-and-set` (TAS) nebo `compare-and-swap` (CAS):   +bool acquired = __sync_bool_compare_and_swap(&lock, 0, 1); 
-       - *TAS*: „ulož do `lock` hodnotu 1 **a vrať mi předchozí obsah**“.   +</code> 
-         ```asm +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.  
-         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í“?**     * **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**.   +    * 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í.+    * Atomická instrukce provede **čtení, test i zápis jako jedinou nepreemptovatelnou transakci**; hardware garantuje, že jen jeden zvítězí.
  
   * **Kdy se vyplatí**     * **Kdy se vyplatí**  
-    - Kritická sekce ≤ ~100 CPU cyklů: inkrement globálního čítače, push/pop z velmi krátkého freelistu.   +    * 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é.   +    * 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čí.+    * 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**     * **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).   +    * 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í.   +    * 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*). +    * 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>+
  
-===== Správa virtuální a fyzické paměti =====+  * **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“. 
 + 
 +===== 4. Správa virtuá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.   * 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í ==== ==== 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. +  * **FAP** – Fyzický adresní prostor, skutečná paměť počítače; její velikost je dána technickým limitem základní desky a kapacitou osazených RAM modulů. 
-** 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): +  * **LAP** – Logický (virtuální) adresní prostor, který vidí každý běžící proces.   
-  * 32-bit: 4 GiB (2^32) +    * Adresy v LAP jsou překládány OS na odpovídající místa ve FAP pomocí tabulek stránek a dalších struktur. 
-  * 64-bit: 16 EiB (2^64) – v praxi omezeno na 256 TiB (2^48) kvůli TLB a stránkovacím tabulkám+    * Velikost LAP závisí na architektuře CPU a OS: 
 +      * 32-bit: 4 GiB (2³²) – většinou celý prostor nelze využít kvůli dělení jádra a uživatelského prostoru. 
 +      * 64-bit: teoreticky 16 EiB (2⁶⁴), ale prakticky bývá omezeno (např. na 48 bitů = 256 TiB), hlavně kvůli velikosti TLB a implementaci stránkování. 
 + 
 +==== Segmentace ==== 
 +  * Segmentace je jedna z metod správy paměti, kde se paměť dělí na logické bloky – **segmenty** (např. pro kód, data, zásobník). 
 +  * Adresy v programu jsou tzv. **selektory**, které odkazují na konkrétní záznam v segmentové tabulce. 
 +  * Segmentový záznam obsahuje: základní adresu, délku segmentu, přístupová práva. 
 +  * Procesor pak fyzickou adresu vypočítá jako: `fyzická adresa = základna segmentu + offset`.
  
-==== Segmentace ====  
-V programu používáme adresy zvané "selektory", existuje tabulka, která mapuje selektory na fyzické adresy. 
 {{statnice:bakalar:segmentace.png}} {{statnice:bakalar:segmentace.png}}
  
-<markdown>+**Výhody segmentace** 
 +  * Délka segmentu odpovídá skutečné potřebě – **úspora paměti** (menší vnitřní fragmentace). 
 +  * Při přístupu mimo segment dojde k **výjimce** – typicky **segmentation fault**. 
 +  * Přesuny v paměti jsou **transparentní** – změna základny segmentu neovlivní kód procesu. 
 +  * Každý segment může mít samostatná **přístupová práva** – lepší ochrana paměti (např. nelze spustit data).
  
-Výhody segmentace  +**Nevýhody segmentace** 
-- Segment má délku uzpůsobenou skutečné potřebě  +  * Alokace paměti je složitá – segmenty mají různou délku, takže jejich správné rozmístění není triviální. 
-    - minimum vnitřní fragmentace  +  * Při častém vytváření a rušení segmentů dochází k **externí fragmentaci** – malé mezery mezi segmenty nelze využít. 
-    - Lze detekovat přístup mimo segment, který způsobí chybu segmentace – výjimku typu „segmentation fault“  +  * Větší **režie při přístupu do paměti** – nutnost kontroly segmentového záznamu a výpočtu fyzické adresy.
-- 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>+
  
 +**Fragmentace**
 +  * *Externí (vnější)* – V paměti je dost místa, ale rozděleného na malé části – **nelze přidělit větší blok**.
 +  * *Interní (vnitřní)* – Segment je větší, než proces reálně potřebuje → vzniká **nevyužitý zbytek** uvnitř segmentu.
  
 ==== Stránkování ==== ==== 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. +**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).   
-</markdown>+  * Překlad stránka → rámec zajišťují **stránkovací tabulky**, které spravuje jádro; hardwarová jednotka MMU je využívá k překladu adres.
  
 === Základní pojmy === === Základní pojmy ===
-<markdown> 
  
-- **Velikost stránky** – 4 KiB na x86 / ARM (často i větší: 2 MiB „huge-pages“, 1 GiB „gigapages“).   +  * **Velikost stránky** – obvykle 4 KiB (x86/ARM), ale lze použít i větší: 2 MiB „huge-pages“, 1 GiB „gigapages“. 
-- **Page Frame Number (PFN)** – index rámce ve fyzické paměti.   +  * **Page Frame Number (PFN)** – index rámce ve fyzické paměti. 
-- **Virtuální adresa** = ⟨index stránky, offset ve stránce⟩.   +  * **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. +  * **Page fault** – přerušení při přístupu na stránku, která není (zatím) namapována do RAM. 
-</markdown>+ 
 +=== Stránkovací tabulka === 
 + 
 +  * Každý proces má svou **stránkovací tabulku** – strukturu mapující virtuální adresy na fyzické rámce. 
 +  * Záznam o stránce obsahuje např.: 
 +    * PFN cílového rámce (pokud je stránka přítomná), 
 +    * přístupová práva (RWX), 
 +    * příznaky (valid/dirty/accessed), 
 +    * info pro cache / TLB. 
 +  * V moderních architekturách (např. x86_64) je tabulka **víceúrovňová** (typicky 4 nebo 5 úrovní) – pro každou část adresy existuje jedna tabulka.
  
 === Eliminace externí fragmentace === === Eliminace externí fragmentace ===
-<markdown> 
  
-- Fyzická paměť je rozdělena na **stejně velké rámce** – OS udržuje jen bitmapu nebo volný seznam rámců.   +  * Fyzická paměť je rozdělena na **stejně velké rámce** – OS udržuje bitmapu nebo volný seznam. 
-- 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**.   +  * Každá stránka může být umístěna do libovolného rámce ⇒ **nevznikají nespojité díry** jako u segmentace. 
-- 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.   +  * Vzniká pouze **vnitřní fragmentace** (max. 1 stránka na segment). 
-- Oproti **segmentaci** tak kernel nemusí provádět drahou kompakci/relokaci velkých bloků a nedochází k postupnému „rozkouskování“ RAM.   +  * Výběr volného rámce je efektivní (bitmapa – O(1)); není nutné relokovat paměť.
-- 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 === === 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).   +  - **TLB lookup** – MMU nejprve hledá překlad (Virt → Fyz) v *Translation Lookaside Bufferu* (L1/L2 cache). 
-2. **Miss v TLB** ⇒ hardware čte položku ze stránkovací tabulky v paměti (víceúrovňově).   +  - **Miss v TLB** ⇒ hardware načte záznam ze stránkovací tabulky v paměti (víceúrovňový průchod podle částí adresy). 
-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. +  - Pokud záznam říká, že stránka není v RAM ⇒ **page fault**: 
-</markdown>+    * jádro zvolí volný rámec (nebo oběť, kterou swapne na disk), 
 +    * načte požadovanou stránku (např. z binárky, souboru nebo swappu), 
 +    * aktualizuje tabulku a TLB, zopakuje instrukci.
  
-=== Víceúrovňové tabulky === +=== Nevýhody stránkování ===
-<markdown>+
  
-| Architektura | Úrovně | Dekompozice virtuální adresy (příklady) | +  * **Vícenásobný přístup** při TLB miss – může být třeba 4–5 čtení z paměti (1–4 úrovně tabulek + samotná data). 
-|--------------|-------|-----------------------------------------| +  * **Vnitřní fragmentace** – poslední stránka segmentu často není plně využita. 
-| **x86 32-bit** | 2 (PDE, PTE) | 10 bit index PDE • 10 bit index PTE • 12 bit offset | +  * **TLB thrashing** – pokud pracovní set přesahuje kapacitu TLB, dochází ke zpomalujícím TLB missům. 
-| **x86-64 (48 bit LAP)** | 4 (PML4, PDPTE, PDE, PTE) | 9 + 9 + 9 + 9 + 12 | +  * **Správa swappu** přináší I/O režii a může vést ke *thrashingu* celé RAM.
-| **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. +=== TLB (Translation Lookaside Buffer) ===
-</markdown>+
  
-=== Nevýhody stránkování === +  * Malá, **plně asociativní cache** překladů Virt → Fyz (desítky až stovky záznamů na CPU jádro). 
-<markdown>+  * Výrazně zrychluje přístup – při TLB hit není třeba sahat na stránkovací tabulky. 
 +  * **TLB shootdown**: při změně mapování (např. `mmap()`, `fork()`) musí OS invalidovat TLB záznamy všech CPU, které daný proces používají – pomocí IPI. 
 +  * **ASID (Address Space ID)** nebo **PCID (Process Context ID)**: 
 +    * značka v TLB, která umožňuje udržovat překlady i po přepnutí procesu, 
 +    * zabraňuje nutnosti flush TLB při každém context switchi.
  
-- **Vícenásobný přístup** na jednu virtuální adresu: TLB miss → až 4–5 čtení z paměti, pak teprve data.   +=== Víceúrovňové tabulky ===
-- **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) === +| Architektura               | Úrovně překladu                 | Dekompozice virtuální adresy (bitové pole)     | 
-<markdown>+|----------------------------|----------------------------------|------------------------------------------------| 
 +| **x86 (32-bit)**           | 2 (PDE, PTE)                     | 10 bit index PDE • 10 bit index PTE • 12 bit offset | 
 +| **x86-64 (48bit LAP)**     | 4 (PML4, PDPTE, PDE, PTE)        | 9 + 9 + 9 + 9 + 12                             | 
 +| **x86-64 (57bit LAP)**     | 5 (PML5, PML4, PDPTE, PDE, PTE)  | 9 × 5 + 12                                     |
  
-- Malá, plně asociativní cache překladů (desítky až stovky záznamů na jádro).   +  * Každá úroveň odpovídá stránkovací tabulce (page table), která se používá pro překlad části virtuální adresy. 
-- **Shoot-down**: když kernel změní mapování, musí invalidovat TLB všech CPU (IPI).   +  * Jednotlivé části virtuální adresy slouží jako indexy do těchto tabulek – z každé se vybere záznam ukazující na tabulku další úrovně. 
-- **ASID/PCID**: značka procesu v TLB zmenšuje nutnost flush při přepnutí procesu. +  * Poslední úroveň obsahuje **Page Table Entry (PTE)** s fyzickým rámcem, ve kterém stránka začíná. 
-</markdown>+  * Díky stránkování stránkovacích tabulek (samy jsou rozděleny na stránky) systém **alokuje jen části stromu**, které proces skutečně používá ⇒ **úspora paměti**. 
 +  * Nejčastější hloubka tabulek dnes je 4 (x86-64), pátá úroveň se používá při větších LAP (např. 57bit v Linuxu).
  
 === Odkládání stránek na disk (swapping) === === Odkládání stránek na disk (swapping) ===
-<markdown> 
  
-- **Swap area** na HDD/SSD; stránky se zapisují při tlaku na RAM.   +  * **Swap area** – vyhrazená část disku (HDD/SSD), kam se ukládají stránky, které nejsou často používané, aby se uvolnila RAM. 
-- **Lazy** a **demand paging**: kód i data se načítají až při prvním přístupu (page fault).   +  * **Demand paging** – stránky se načítají do paměti **až při pokusu o přístup** → efektivnější využití RAM. 
-- **Thrashing**: když se pracovní set nevejde do RAM a proces tráví víc času swapováním než výpočtem. +  * **Thrashing** – situace, kdy proces spotřebuje tolik stránek, že dochází k **častému swapování** a výkon dramaticky klesá (systém více swapuje než počítá).
-</markdown>+
  
 === Algoritmy výběru oběti (page replacement) === === 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 | +  * „Oběť“ = stránka ve fyzické paměti, kterou kernel vyhodí (nebo uloží do swapu), aby mohl přinést novou stránku (např. po page faultu). 
-|------------|------|----------| +  * Cílem je vybrat stránku, která **nebude brzy znovu potřebná**, což je těžké odhadnout → používají se heuristiky. 
-| **FIFO** | vyhoď nejstarší stránku | jednoduchý, trpí Beladyho anomálií | + 
-| **Second-Chance (Clock)** | FIFO + 1 bit „referenced“ | linuxový základ (`CLOCK-Pro`) | +| Algoritmus                 | Idea                                 | Poznámky                                      | 
-| **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 | +| **FIFO**                   | Vyhoď nejstarší stránku              | jednoduchý; trpí **Beladyho anomálií** (větší paměť ⇒ horší výkon) | 
-| **Adaptive (e.g., ARC)** | kombinuje LRU a LFU | v moderních OS/DB | +| **Second-Chance (Clock)** | FIFO s dodatečným bitem „referenced“ | základní Linuxová varianta (`CLOCK-Pro`), stránka dostane „druhou šanci“ | 
-</markdown>+| **LRU / Approx. LRU**      | Vyhoď nejméně nedávno použitou       | přesný LRU je drahý na implementaci; OS často používají approximace (bitmapy, počitadla) | 
 +| **Working-Set**            | Drž stránky aktivní v posledním čase ∆ | přesnější, ale dražší na výpočet | 
 +| **Adaptive (např. ARC)**   | Kombinace LRU a LFU                  | používá se v moderních OS (Windows, ZFS) i databázích |
  
 === Copy-On-Write (COW) === === Copy-On-Write (COW) ===
-<markdown> 
  
-1. Při `fork()` dostanou parent i child stránky **jen pro čtení** a ukazují na *stejný rámec*.   +  * Mechanismus pro **efektivní sdílení paměti** mezi procesy. 
-2. První zápis vyvolá **page fault**. Kernel:   +  * Při volání `fork()` nedochází hned ke kopírování všech stránek – místo toho: 
-   - alokuje nový rámec,   +    * Proces **rodič i potomek sdílejí stejné rámce**, označené jako **read-only**. 
-   - zkopíruje obsah původní stránky,   +    * Jakmile jeden z nich provede **zápis**, vyvolá se **page fault**. 
-   - přemapuje zapisující proces na nový rámec (RW).   +    * Kernel: 
-3. Šetří kopírování při `fork+exec`, sdílí read-only data (např. `.text`, sdílené knihovny). +       * alokuje nový rámec, 
-</markdown>+       * zkopíruje obsah původní stránky, 
 +       * přemapuje novou stránku jako RW. 
 +  * Výhody: 
 +    * výrazné **zrychlení `fork()`**, když následně proces provede `exec()`, 
 +    * efektivní **sdílení statických dat** – např. kód (`.text`), knihovny apod.
  
 === Shrnutí výhod stránkování === === 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.   +  * **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ů.   +  * **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).   +  * **Izolace procesů** – ochranné bity (R/W/X, User/Supervisor) zajišťují oddělení paměti mezi procesy. 
-- Sdílení kódu a knihoven mezi procesy (stejný rámec mapovaný do více LAP).   +  * **Sdílení kódu a knihoven** – více procesů může mapovat stejný fyzický rámec (např. `.text` segment) do svého LAP. 
-- Podpora virtuální paměti větší než fyzická (swap, demand paging).   +  * **Virtuální paměť > fyzická** – systém může využít swap a demand paging pro rozšíření dostupné paměti. 
-- Mechanismus pro COW, mmap souborů, lazy allocation.+  * **Podpora moderních technik** – Copy-On-Write, `mmap()` pro soubory, 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. +  *Nevýhody* (víceúrovňový překlad, TLB missy, latence při swapu) se zmírňují pomocí: 
-</markdown>+    * větších TLB (ASID/PCID), 
 +    * použití **huge-pages**, 
 +    * lepších algoritmů výběru oběti, 
 +    * dostatku fyzické paměti (RAM).
  
-===== Souborové systémy ===== +===== 5. 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.+** 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+Způsob organizace dat na disku – data jsou uložena v souborech, soubory jsou strukturované v adresářích (hierarchická struktura). 
 +  * Souborový systém určuje, jak jsou data fyzicky a logicky organizována, jak se přistupuje ke souborům, jaká metadata jsou vedena apod.
  
-možnosti uložení obsahu: +==== Příklady souborových systémů ====
-  * 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, FAT32** – jednoduché, široce kompatibilní (např. USB disky), bez žurnálování, náchylné na poškození při výpadku.
 +  * **exFAT** – nástupce FAT32, podporuje větší soubory a disky, stále bez žurnálu.
 +  * **NTFS** – moderní FS pro Windows, podporuje práva, šifrování, kompresi, žurnálování.
 +  * **ext2/3/4** – nejpoužívanější na Linuxu; ext3/4 podporují žurnál, ext4 má rychlejší přístup a větší limity.
 +  * **Btrfs** – pokročilý FS s podporou snapshotů, kontrolních součtů, RAIDu, dynamické alokace.
 +  * **ZFS** – kombinace FS a správy disků, silné kontroly integrity dat, snapshoty, samoopravné mechanismy.
 +
 +==== Možnosti uložení obsahu souboru ====
 +
 +  * **Souvislý úsek bloků**
 +    * Podobné jako alokace paměti – rychlý sekvenční přístup.
 +    * Nevýhoda: fragmentace a nutnost přesunů při zvětšení souboru.
 +    * Typicky vhodné pro **sekvenční čtení** (např. média, logy).
 +
 +  * **Spojové seznamy**
 +    * Každý blok obsahuje i ukazatel na další blok; adresář obsahuje odkaz na první blok.
 +    * Jednoduchá implementace, vhodné pro **sekvenční přístup**, ale:
 +      * Nevhodné pro náhodný přístup – nutné projít celý seznam.
 +      * Nemožnost přímého mapování souboru do paměti.
 +      * Jediný poškozený sektor může znepřístupnit celý soubor.
 +
 +  * **Indexové struktury**
 +    * Používá se samostatný **indexový blok**, který obsahuje ukazatele na datové bloky.
 +    * Umožňuje rychlý **náhodný přístup** (random access), stále dobrý i pro sekvenční čtení.
 +    * Při velkých souborech může být potřeba víceúrovňový index.
 +    * Používají např. ext a NTFS.
 +
 +==== Základní souborové systémy ====
  
 === FAT (File Allocation Table) === === FAT (File Allocation Table) ===
-  * starý souborový systém s mnoha omezeními +  * Starý, jednoduchý souborový systém s mnoha omezeními. 
-  * něco mezi spojovými seznamy a indexovou strukturou +  * Konstrukčně 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$ +  * Základní jednotka alokace je **cluster** (4–32 KiB). 
-  * 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) +  * Maximální počet clusterů: 
-  * 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) +    * FAT16: 2¹⁶ 
-  * nevýhodou je fragmentace, omezená velikost a nutnost procházet FAT položky sekvenčně+    * FAT32: 2²⁸ 
 +    * exFAT: 2³² − 10 
 +  * Disková struktura: 
 +    * **MBR** (Master Boot Record) – informace o FS (velikost, jméno, počet FAT tabulek, apod.) 
 +    * **FAT1, FAT2** – dvě redundantní tabulky 
 +    * **Root directory** 
 +    * **Data** 
 +  * V každé položce FAT je číslo následujícího clusteru nebo hodnota `-1` pro konec souboru. 
 +  * Nevýhody: 
 +    * silná **fragmentace** 
 +    * **sekvenční přístup** k FAT tabulce při čtení souboru 
 +    * **omezená velikost souboru i disku** 
 +    * chybí žurnálování
  
 === Inodový souborový systém === === 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 +  * Metadata o souborech jsou uložena ve **struktuře inode** (Index Node). 
-  * 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 +  * Adresářová položka obsahuje jméno a číslo inode. 
-  * 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ů+  * Každý inode obsahuje: 
 +    * několik přímých odkazů na datové bloky 
 +    * nepřímé odkazy – jednoduchý, dvojitý, trojitý (pro větší soubory) 
 +  * Výpočet pozice bloku je snadný – dle offsetu v souboru.
  
 {{statnice:bakalar:osy_inode.png?500}} {{statnice:bakalar:osy_inode.png?500}}
  
-rozložení na disku: +Rozložení na disku: 
-  * pevný počet inodů, samotný inode lze nalézt pomocí jeho indexu v tabulce +  * **Pevný počet inode** – jsou uloženy v inode 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) +  * **Superblok** – obsahuje informace o FS (velikost, počet inode, volné bloky, záložní superblok). 
-  * kořenový adresář+  * **Kořenový adresář** – výchozí místo připojení FS.
  
-hledání volného místa +Hledání volného místa: 
-  * sekvenčním procházením (neefektivní) +  * Sekvenční procházení – neefektivní. 
-  * poznání volného místa je obtížné (blok nul může být validní obsah souboru) +  * Blok s nulou může být validní obsah souboru ⇒ obtížné určit volný blok. 
-  * řešení jsou bitové mapy, kde každý bit udává obsazenost inodu nebo datového bloku +  * Řešení: 
-  * místo prohledávání inodů se prohledává tato bitová mapa+    * **bitové mapy** (bitmapy) pro inode i datové bloky. 
 +    * Vyhledávání je pak rychlé a efektivní.
  
 {{statnice:bakalar:osy_inode_bit.png?750}} {{statnice:bakalar:osy_inode_bit.png?750}}
  
-ext2-4 +ext2/3/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é) +  * Při práci se souborem je potřeba přístup k bitmapě, inodu a datovým blokům. 
-  * proto jsou data organizována do skupin, kde se FS snaží alokovt datové bloky ve stejné skupině jako inody+  * U rotačních disků je výhodné, když jsou bloky blízko sebe. 
 +  * FS dělí disk na **skupiny bloků**, které obsahují inody i data ⇒ snížení latence přístupu.
  
 {{statnice:bakalar:osy_inode_skupiny.png?750}} {{statnice:bakalar:osy_inode_skupiny.png?750}}
  
 === Extents === === 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}} 
  
 +  * U velkých souborů je indexace po jednotlivých blocích neefektivní.
 +  * Moderní FS používají **extenty** – odkazy na **souvislé skupiny bloků** (namísto jednotlivých).
 +  * Každý extent: ⟨začátek, délka⟩
 +  * Výhody:
 +    * Méně režie než při uložení všech odkazů zvlášť.
 +    * Lepší výkon u sekvenčního i náhodného přístupu.
 +  * Používá se např. v **ext4**, **NTFS**, **btrfs**.
 +
 +{{statnice:bakalar:osy_extents.png?500}}
  
 === Žurnálování === === Ž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ě +  * Před tím, než se začne měnit obsah souborového systému, uloží se plánované změny do zvláštní oblasti disku – **žurnálu**. 
-  * implementováno v NTFS, ext3/4+  * Pokud dojde k pádu systému, při startu OS se kontroluje žurnál a změny se podle něj **dokončí nebo zahodí** tak, aby byl FS v konzistentním stavu. 
 +  * Běžné v moderních FS: **NTFS**, **ext3**, **ext4**, **btrfs**, **ZFS** (ten má místo žurnálu transakční model se snapshoty).
  
 {{statnice:bakalar:osy_journal.png?500}} {{statnice:bakalar:osy_journal.png?500}}
  
-bezpečný způsob změny FS +Bezpečný postup změny FS (tzv. transakční protokol):
-  - 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: +  * **Commit** – ukončení transakce zápisem speciálního záznamu (`TxE`). 
-  - do žurnálu se zapíše pouze část transakce +  * **Checkpoint** – změny v inodech, datech, bitových mapách se zapíšou na správná místa na disku. 
-    * souborový systém je konzistentní, ale obsahuje původní data +  * Po úspěšném dokončení se transakce **odstraní** ze žurnálu.
-    * 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+==== Scénáře při pádu systému ====
  
-Flash paměti +  * **Pouze část transakce** zapsaná do žurnálu: 
-  * zapisovat lze pouze do vymazaného bloku +    * FS zůstává konzistentní, ale obsahuje původní (nezměněná) data. 
-  * zapsat lze pouze jednou, pak se musí vymazat +    * OS při startu zjistí neúplnou transakci a ignoruje ji. 
-  * mazací blok bývá větší (např 4 MiB) +  * **Celá transakce** je v žurnálu, ale **blogy na disku se nezmění**: 
-  * každý blok garantuje pouze určitý početpřepsání (např. 100 000) +    * OS je použije k dokončení změn (tzv. *roll-forward*). 
-  * často se měnící data (např. bitmapy, či FAT tabulka) drasticky snižují životnost paměti +  * **Transakce i bloky jsou zapsány**, ale transakce není odstraněna: 
-  * změna jednoho bytu v souboru znamená smazání a znovu zapsání 4 MiB+    * OS je znovu aplikuje (*idempotentní* operace – nezmění výsledek, když se provedou víckrát). 
 +  * **Pouze část transakce** – např. `TxB`, `I_v2`, `TxE`, ale **chybí `B_v2` a `D_v2`**: 
 +    * Riziko způsobeno optimalizacemi disku – **změna pořadí zápisů**. 
 +    * OS musí použít tzv. **write barriers** (paměťové/IO bariéry), aby donutil disk dodržet pořadí: 
 +      * Správná sekvence: `TxB`, `I_v2`, `B_v2`, `D_v2`, *bariéra*, `TxE`. 
 +  
 + * **Nevýhody žurnálování**: 
 +    * Režie navíc (dvojnásobné zápisy: nejprve do žurnálu, pak do FS). 
 +    * Složitost implementace. 
 +    * Zpomalení zápisových operací.
  
-řešením je nepoužívat Flash čipy samostatně, ale v kombinaci s řadičem - Flash Translation Layer +=== Flash paměti === 
-  * použití speciálních souborových systémů (UBIFS, JFFS2, NILFS)+  * **Flash bloky** lze pouze přepsat, pokud jsou nejprve **vymazány**. 
 +  * **Zápis je jednorázový** – změna jednoho bajtu znamená smazání celého bloku (např. 4 MiB). 
 +  * **Omezený počet přepisů** – typicky 100 000 až 1 000 000 cyklů na blok. 
 +  * Často měněná data (bitmapy, FAT tabulky) mohou výrazně zkrátit životnost paměti. 
 +  * Důsledkem je **write amplification** – malá změna vyžaduje velkou operaci.
  
 +==== Řešení pro flash paměti ====
 +  * Nepoužívají se přímo, ale s řadičem, který implementuje **Flash Translation Layer (FTL)**:
 +    * Skryje omezení zápisu, přemapovává fyzické bloky, spravuje wear-leveling.
 +    * Typické u SSD, eMMC, SD karet.
 +  * **Speciální souborové systémy pro flash**:
 +    * **UBIFS** – pro NAND flash, umí journal, garbage collection.
 +    * **JFFS2** – log-strukturovaný, pro malé embedded systémy.
 +    * **NILFS** – log-based, kontinuální snapshoty, optimalizovaný pro SSD.
  
  
- +===== 6. Bezpečnost =====
-===== 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.   * 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 === +=== Trusted Computing Base (TCB) === 
-je množina všech entit kterým systém **věří** => pokud selžou, systém už nemusí být bezbečný. +  * Množina všech komponent, kterým systém **musí důvěřovat**, aby zaručil bezpečnost. 
-Příklady: hardware, Jádro OS (nezbytně), administrátor serveru, …+  * Pokud selže některá část TCB, **celý systém může být kompromitován**. 
 +  * Příklady: hardware, jádro OS, správce systému (root), hypervisor, firmware, kryptografické klíče.
  
 === Základní metody řízení přístupu === === Základní metody řízení přístupu ===
-Základní princip  je **Matice řízení přístupu** - definuje stav ochrany v daném čase.+  * Základním teoretickým modelem je **matice řízení přístupu** – popisuje, kdo má jaká oprávnění k čemu v daném čase.
  
 {{statnice:bakalar:osymatrix.png?200}} {{statnice:bakalar:osymatrix.png?200}}
  
-  * Objekty jsou např. soubory +  * **Subjekty** – např. uživatelé, procesy. 
-  * Subjekt je např. uživatel +  * **Objekty** – např. soubory, zařízení, síťové sockety. 
-  * Subjekty mohou být zároveň objekty+  * Subjekty mohou být zároveň i objekty (např. pokud lze nastavit práva k procesu).
  
 **Ukládání stavu ochrany** není typicky jako matice (moc „řídké“, neefektivní, dynamické). **Ukládání stavu ochrany** není typicky jako matice (moc „řídké“, neefektivní, dynamické).
Line 565: Line 637:
     - Každý takový řádek je nazýván „seznam schopností“ (**capability list**)     - Každý takový řádek je nazýván „seznam schopností“ (**capability list**)
  
-== Seznamy pro řízení přístupu (ACL) == +=== Seznamy pro řízení přístupu (ACL) === 
-Implementováno skoro ve všech běžných OS + 
-Subjekty jsou obvykle sloučeny do tříd +  * Nejrozšířenější model, implementován v UNIX, Linux, Windows... 
-  * např. v UNIXu: majitel, skupina, ostatní+  * Subjekty bývají seskupeny do tříd (např. majitel, skupina, ostatní). 
 +  
 <code bash> <code bash>
 $ ls -ld /var/spool/cups $ ls -ld /var/spool/cups
 drwx--x--- 1 root lp 6754 Nov 22 00:00 /var/spool/cups drwx--x--- 1 root lp 6754 Nov 22 00:00 /var/spool/cups
 </code> </code>
-  * obecnější seznamy ve Windows či v současném Linuxu + 
-    (příkazy get/setfacl) +  * Moderní systémy (Linux, Windows) podporují **rozšířené ACL** – více individuálních pravidel. 
-  * mohou obsahovat „negativní“ oprávnění – např. pro +  * Podpora **negativních oprávnění** – např. zakázat přístup členům určité skupiny. 
-    vyloučení přístupu několika uživatelů ze skupiny +  * **Metaoprávnění** – např. oprávnění měnit ACL nebo členství ve skupinách.
-Meta-oprávnění: +
-  * řízení členství ve třídách +
-  * dovolují modifikaci ACL+
  
 {{statnice:bakalar:osyacl.png?150}} {{statnice:bakalar:osyacl.png?150}}
-== seznamy Schopností (capability lists) ==  + 
-**Schopnost** je prvek seznamu schopností (duh)+=== Seznamy schopností (Capability Lists) === 
 + 
 +  * **Schopnost (capability)** = token, který **pojmenovává objekt a uděluje oprávnění**. 
 +  * Držitel schopnosti může s objektem manipulovat podle udělených práv. 
 +  * Nevyžaduje centrální seznam přístupů – **decentralizovaný model přístupu**.
  
 {{statnice:bakalar:osycap.png?250}} {{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)+  * Typicky se používá v systémech, kde se upřednostňuje bezpečnostní izolace a modularita (např. mikrojádrá, sandboxy, některé OS pro embedded zařízení). 
 +  * Objekty jsou **neviditelné** bez příslušné schopnosti ⇒ důležitý princip *least privilege*.
  
-Všichni kdo vlastní „schopnost“ mají právo s objektem pracovat+=== ACL vs Capability List ===
  
-Méně časté použití v běžných systémech (ale pomalu se to mění)+| Seznamy řízení přístupu (ACL) | Schopnosti (Capabilities) | 
 +|-------------------------------|-----------------------------| 
 +| Tradiční model; proces musí vědět, **jaký objekt chce**, a systém mu řekne, jestli má přístup. | Objekty jsou přístupné **pouze skrze předané schopnosti** – uživatel je *nemůže najít sám*. | 
 +| Oprávnění určena podle identity subjektu (UID, skupina, …). | Proces **dostane pouze schopnosti**, které mu byly explicitně předány (např. přes socket, fork, init). | 
 +| Problém **ambientní autority** – proces má automaticky všechna práva uživatele. | **Neexistuje ambientní autorita** – práva se předávají cíleně a omezeně. | 
 +| Nelze snadno omezit práva potomků (děděná práva). | Nikdo nemůže předat právo, které **sám nemá**. | 
 +| Linux částečně řeší pomocí **namespaces**, ale není to univerzální ani bezpečnostně dokonalé. | Princip *objektově orientované bezpečnosti*, čistší a škálovatelnější řešení. |
  
-== ACL vs capability list ==+=== 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. 
 +    * ⇒ přepíší se další položky na zásobníku – např. 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ý může např. spustit shell a umožnit vzdálenou kontrolu systému. 
 +  * Pokud útočník přepíše **návratovou adresu**, může přesměrovat běh programu na vlastní kód (shellcode) nebo jinou část programu. 
 +  * Útoky se zaměřují na programy v C/C++, kde chybí **automatická kontrola hranic polí**. 
 +  * **Omezení shellcodu** – nesmí obsahovat binární nuly (`\0`), protože řetězce jsou jimi ukončovány. ⇒ používají se techniky kódování. 
 +  * Moderní techniky: **Return-Oriented Programming (ROP)** – nevpichují nový kód, ale skládají útočný řetězec z již existujících instrukcí v programu (**gadgety**).
  
-| Seznamy řízení přístupu (ACL) | Schopnosti | +=== Stack Overflow – how to defend === 
-|-----------------------------------|----------------| +  * **Nespustitelný zásobník (NX, XD bit, ARM UXN)** – zakáže spuštění kódu z datové části zásobníku. 
-| - Tradiční, všeobecně známé, ale... | Lepší vlastnosti z pohledu bezpečnosti. | +  * **ASLR (Address Space Layout Randomization)** – náhodné rozmístění paměťových oblastí (zásobník, knihovny, binárky) při každém spuštění programu. 
-| - 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). | +  * **Stack Canary / Stack Protector** – před návratovou adresu se vloží kontrolní hodnota (canary). Pokud je přepsaná, program detekuje útok a ukončí se. 
-| - 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)“. | +  * **Retguard** – návratová adresa je zakódována při vstupu do funkce a dekódována při návratu. Změna adresy útočníkem způsobí pád. 
-|    - Pokud program spouští jiný program, potomkovi nelze jednoduše práva omezit. | - Nikdo nemůže delegovat schopnosti, které sám nemá. | +  * **Bezpečné programování** – validace velikosti vstupních dat, používání bezpečných funkcí (`strncpy` místo `strcpy`, `snprintf` místo `sprintf`). 
-|    - V Linuxu se dnes tento problém řeší pomocí „jmenných prostorů“ (**namespaces**), ale není to elegantní a trpí to některými nedostatky |  |+  * **Používání moderních jazyků a knihoven**, které mají ochranu proti přetečení zabudovanou (Rust, některé safe C knihovny). 
 +  * **Oddělení práv a minimalizace oprávnění** – běžící procesy by měly mít minimální potřebná oprávnění, aby případný útok měl omezený dopad.
  
-=== 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.+===== 7. Virtualizace ===== 
 +  * softwarová virtualizace, metoda trap-and-emulate, virtualizace systémového volání, virtualizace stránkovacích tabulek, hardwarově asistovaná virtualizace.
  
-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.+Virtualizace je **abstrakce hardwaru** a jeho částečná emulace v softwaru. Hostujícímu systému je vytvořena iluze, že běží na vlastním fyzickém stroji.
  
-Útoky jsou často cílené na programy v jazyce C/C++, kde chybí automatická kontrola hranic polí.+Základní pojmy: 
 +  * **Hostitel (host)** – fyzický hardware nebo virtualizované prostředí, na kterém běží hypervizor. 
 +  * **Hypervizor** – software, který emuluje virtuální hardware a řídí běh VM. 
 +  * **Host (guest)** – OS běžící na virtuálním hardware poskytovaným hypervizorem.
  
-Omezení shellcode: nesmí obsahovat binární nulové bajty (řetězce jsou ukončeny nulou). Proto se využívají speciální techniky kódování.+Typy virtualizace: 
 +  * **Plná virtualizace** – host neví, že běží na virtualizovaném systému (typicky trap-and-emulate). 
 +  * **Paravirtualizace** – host si je vědom virtualizace a aktivně spolupracuje s hypervizorem. 
 +  * **Emulace** – celé prostředí je softwarově emulované, včetně instrukcí CPU (např. QEMU bez KVM). 
 +  * **Cloud virtualizace** – vzdálené řízení a spouštění VM v rámci cloud infrastruktury.
  
-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. +=== Výhody VM ===
-=== 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í.+  * **Izolace** – VM jsou navzájem i od hosta oddělené, vyšší bezpečnost. 
 +  * **Současný běh více OS** – např. Linux + Windows současně na jednom stroji. 
 +  * **Přenositelnost a snapshoty** – běžící VM lze přesunout nebo pozastavit. 
 +  * **Vývoj a testování** – chyby v kernelu nezhodí celý systém.
  
-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čí.+=== Problémy virtualizace ===
  
-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čí.+Moderní CPU má dva režimy: 
 +  * **Uživatelský režim (user mode)** – omezený, aplikace, nelze přistupovat k HW. 
 +  * **Privilegovaný režim (kernel mode)** – OS, přístup ke všemu v systému.
  
-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).+VM nesmí běžet přímo v privilegovaném režimu – vnímáno by to jako bezpečnostní riziko.   
 +VM tedy běží v uživatelském režimu hostitele ⇒ je nutné emulovat vlastní **uživatelský** a **privilegovaný režim** uvnitř VM.
  
-Použití moderních jazyků a knihoven, které mají zabudovanou ochranu proti přetečení bufferu.+=== Trap and Emulate ===
  
-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.+  * Instrukce v **uživatelském režimu** hosta se vykonávají nativně. 
 +  * Pokus o vykonání **privilegované instrukce** (např. přístup k HW) vyvolá **výjimku** (trap). 
 +  * Výjimku zachytí hypervizor, provede požadovanou akci a vrátí řízení zpět do VM. 
 +  * Hostující OS si myslí, že vše proběhlo nativně – **transparentní virtualizace**.
  
 +  * Nutné rozlišovat:
 +    * **Privilegované instrukce** – způsobí trap, když jsou volány z uživatelského režimu.
 +    * **Citlivé instrukce** – mění globální stav nebo závisí na systému ⇒ musí být zachytitelné (v ideálním případě vždy privilegované).
  
 +=== Virtualizace systémových volání ===
  
 +  * Systémová volání (např. `open`, `read`, `write`) přecházejí z uživatelského do privilegovaného režimu.
 +  * Ve VM se volání spustí pomocí **trap**, který hypervizor zachytí a provede požadovanou činnost.
 +  * ⇒ **lehce pomalejší** než nativní syscalls, ale zachována kompatibilita a izolace.
  
 +=== Virtualizace stránkovacích tabulek ===
  
 +  * Každý OS spravuje své **virtuální paměťové mapování** pomocí vlastních stránkovacích tabulek.
 +  * Hypervizor ale musí zajistit, že host nemůže měnit skutečné fyzické mapování:
 +    * Host dostane **virtuální stránkovací tabulky pouze pro čtení**.
 +    * Pokus o změnu vyvolá **trap** – hypervizor provede potřebnou aktualizaci.
 +  * Efektivnější varianta: **shadow page tables** – hypervizor vede vlastní mapu překladů, kterou host nevidí.
 +  * Modernější způsob: **EPT (Intel)** / **NPT (AMD)** – viz níže.
  
-===== Virtualizace ===== +=== Hardwarově asistovaná 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.+Moderní procesory (Intel VT-x, AMD-V) přidávají nový režim: 
 +  * **Non-root execution mode** – speciální režim pro běh VM. 
 +  * Privilegované instrukce v tomto režimu mohou běžet přímo bez nutnosti trap-emulace. 
 +  * Významně zvyšuje výkon, protože: 
 +    * většina běžných činností běží nativně, 
 +    * trapy nastávají jen při I/O nebo specifických výjimkách.
  
-Jmenujeme tři základní pojmy: +Navíc podporují: 
-  * **Hostitel** - systém, na kterém běží hypervizor, na nejnižší úrovni fyzický hardware, v případě zapouzdřené virtualizace to neni fyzický hardware   +  * **EPT (Extended Page Tables)** – hardwarová správa překladů virtuální → fyzická (host) → skutečná fyzická (hostitel) adresa. 
-  * **Hypervizor** - software běžízí na hostiteli implementující virtuální hardware +  * **Nested virtualization** – virtualizace uvnitř virtualizace (VM v jiné VM).
-  * **Host** - systém (většinou OS) běžící na virtuálním hardware poskytovaným hypervizorem+
  
-====Výhody VM====  +=== Shrnutí === 
-  * **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 +| Oblast                   | Princip                                                                 | 
-  * **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č)+| Trap and Emulate         | Hypervizor zachytává výjimky při pokusu o privilegovanou instrukci.     | 
 +| Virtualizace syscalls    | Přes trap do hypervizoru, který syscall provede za VM.                 | 
 +| Virtualizace page tables | Host spravuje své PT, ale nesmí je měnit ⇒ trapy a ochrana zápisu.     | 
 +| HW asistence             | Non-root režim + EPT/NPT – mnoho operací běží přímo na CPU.            |
  
-====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: • b4b33alg

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b35osy (generated for current page)