Počítačové systémy

• je lepší používat přímo jména registrů v ABI – aby případné přečíslování registrů nedělalo problém
• různé funkce registrů

• součet dvou registrů, uložení do (třetího) registru
  • na rozdíl od x86 umí MIPS uložit výsledek do třetího registru
• přičtení 16bit. konstanty k registru, uložení do registru
• podobně rozdíl, odečtení konstanty
• logické operace – and, or, xor, nor (or + negace)
• negace se dělá pomocí nor $t1,$t2,$t2
• bitové posuny
• přístup do paměti

• nepodmíněné skoky
  • na adresu (j)
  • skok přes obsah registru (jr)
  • jump and link (jal; pro uložení návratové adresy do registru 31 a skok do podprogramu – návrat pomocí jr 31; kdybychom chtěli skákat do vnořených funkcí, tak bychom potřebovali zásobník)
• podmíněné skoky – equal, not equal (beq, bne)
• porovnávání – slt (menší než), sltu (unsigned), slti (immediate), sltiu
  • na x86 pomocí odčítání a příznaků
• lw $t0, 4($gp) načte hodnotu z místa, kde jsou v paměti globální proměnné, offset 4
• násobení (malými čísly) se převádí na sčítání pomocí binárního rozkladu

• rezervované, systémové, aritmetické
• typicky se používá zero flag (1 když u poslední operace vyšla nula), sign flag (kopie MSb znaménkového čísla), carry flag (přetečení a podtečení v bezznaménkové aritmetice)

• ISA je abstraktní model, často může být odtržený od implementace
• u x86 architekturu vlastní společně Intel a AMD
• tradiční klasifikace
  • CISC – Complex Instruction Set Computer
    • lidi píšou programy v asembleru
  • RISC – Reduced…
    • překládám program překladačem z vyššího programovacího jazyka
    • např. x86 (původně)
  • VLIW – Very Long Instruction Word
    • není potřeba dekódovat instrukci, rovnou je z ní jasné, co mají které části procesoru dělat
  • EPIC – Explicitly Parallel Instruction Computer
    • v jedné instrukci je jich několik (?)
• ortogonalita – mám obecné registry a instrukce, které můžu používat s libovolnými registry (x86 není ortogonální; obecně akumulátorové instrukční sady nejsou ortogonální)
• architektura typu Load-Execute-Store – máme zvlášť instrukce na load a store, s pamětí nejde dělat nic jiného

• procesor
  • řadič paměti
  • cache
  • jádra – logické procesory + registry
• hyper-threading – na jedné výpočetní jednotce (uvnitř jádra) běží dvě instrukce najednou
  • uvnitř jednoho jádra jsou dvě vlákna (logické procesory) – může jich být i víc
  • zvyšuje to výkon, schovává to latenci přístupu do paměti
  • každé vlákno má své registry
• hierarchie keší
  • privátní (na každém jádru)
    • L1I a L1D – malé keše
    • L2 – větší, pro kód (instrukce) i data
  • sdílená
    • L3/LLC – velká; dneska má obvykle každé jádro vlastní L3$ slice
• 95 % přístupů do paměti jde z nějaké úrovně cache (což je fajn, protože paměť je pomalá)
• out-of-order execution – instrukce si procesor popřehází, aby to bylo rychlejší (ale výsledek odpovídá tomu, jako by je vykonával ve správném pořadí)

• jednotlivé kroky (stage) jedné instrukce: načtení instrukce z paměti, její dekódování, vykonání, paměťová operace, zápis výsledku do registru
• najednou se můžou vykonávat všechny kroky instrukce (takže vlákno v jednu chvíli zpracovává pět instrukcí – u každé z nich je v jiné stagi)
• je potřeba řešit správné pořadí zápisů a načtení dat
• problém s podmíněnými skoky – ve chvíli, kdy zjistím, že mám skákat, už bych vykonával stage u dalších instrukcí
  • používá se branch predictor, zkouší odhadnout, kam se skočí
  • když to odhadne špatně, tak se pipeline restartuje
  • hledá ve skákání nějaké vzory, zkouší hádat
  • pokud instrukci na dané adrese nikdy neviděl, tak zpětný skok předpokládá, naopak dopředný skok nikoliv

• jsme schopni souběžně zpracovávat více instrukcí
• dnešní procesory jsou pěticestné – najednou zpracovávají pět instrukcí
• dnes se používá asymetrická superskalarita – jedna pipeline je silnější a zvládá všechno, čtyři zbývající jsou slabší a zvládají jenom jednoduché instrukce

• mikroinstrukce se umístí do poolu a čekají, až budou mít výkonné jednotky volno
• jednotlivé jednotky umí různé věci

• od perzistentní RAM (včetně) ta média drží data po vypnutí
• po perzistentní RAM (včetně) jsou uložená data přístupná CPU, zbytek je obsluhován vždy nějakým řadičem (jako externí I/O)

• každá paměť se skládá z paměťových buněk – bitů
• bity jsou seskupeny do slov fixní délky
• každé slovo je přístupné binární adresou (podle délky adresy rozlišujeme např. 32 nebo 64bitovou architekturu)
  • můžeme uložit $2^N$ slov, kde $N$ je délka adresy
• dnes se používá 8bitové slovo (bajt)

• paměť je vlastně dvojrozměrná
• adresa se dekóduje tak, aby paměťový řadič našel správnou řádku a sloupec v ní
• když bajty jsou za sebou, jsou v jedné řádce
• časování
  • CAS – Column Access Strobe, kolik taktů trvá, než jsem schopný adresovat další sloupec uvnitř jedné řádky (tento parametr ovlivňuje cenu paměti)
  • další 3 parametry

• celá čísla
  • bezznaménková
    • jednoduchá binární reprezentace čísla
    • obvykle 1, 2, 4, 8 bytů
    • reprezentovaný rozsah $[0;2^N-1]$
  • znaménková
    • dvojkový doplněk
    • bitová negace + 1
    • pouze jedna 0
    • kompatibilní s bezznaménkovou aritmetikou
    • asymetrický rozsah $[-2^{N-1};2^{N-1}-1]$
    • MSb určuje znaménko čísla
• desetinná čísla – float
  • $\text{value}=(-1)^{\text{sign}}\cdot\text{significand}\cdot 2^{\text{exponent}-\text{bias}}$
  • tohle je reprezentace v paměti, procesory si to ukládají po svém

• moderní procesory vyžadují, aby byla data v paměti zarovnaná podle jejich velikosti
• např. 4bajtový int musí mít adresu zarovnanou na 4 (dělitelnou čtyřmi)
• celá struktura (struct) je zarovnaná na největší datový typ dostupný na CPU (např. 16B)
• některé jazyky přehazují položky ve struktuře, aby se eliminovalo volné místo
• sizeof vrátí velikost včetně těch mezer

• globální proměnné – přiřazena na začátku, celou dobu drží svoji hodnotu, je na jednom místě v paměti
• lokální proměnné, argumenty funkcí – uloženy na zásobníku
• dynamicky alokované proměnné – programátor je explicitně alokuje (pomocí malloc(), new, unique_ptr, …), existuje vyhrazený blok paměti pro tyto alokace

• úkol – najdi blok nepoužité paměti dostatečné velikosti, alokuj část velkého poolu paměti (používá se pojem heap)
• životní cyklus – alokuj blok, použij blok, uvolni blok
• vždy existuje určitý počet bytů, který lze minimálně alokovat – takže na jednobytovou proměnnou se alokuje zbytečně moc paměti (proto není dobré příliš používat new)

• interní – v bloku je alokováno více paměti, než je potřeba
• externí – volná paměť je rozdělena do malých bloků a mezi nimi jsou bloky alokované paměti

• first fit – začíná na začátku, najde první dostatečně velké volné místo
• next fit – stejné jako first fit, akorát začíná na pozici, kde bylo alokováno naposledy
• best fit – začíná na začátku, najde nejmenší dost velké volné místo
  • vytváří malinké díry
• worst fit – začíná na začátku, najde největší místo

• alokuju A, což je 42 B, nejbližší násobek je 64 B
• 2 KiB je násobek 64 B, alokuju za A
• 100 B – alokuju 128 B
• atd.
• pak dealokuju nějaké bloky
• alokuju dál pomocí nějaké metody – podle toho se bloky alokují na nějaké místo

• bloky velikosti $2^N$, adresy zarovnány na násobek své velikosti
• hledám nejmenší volný blok, který odpovídá požadované velikosti
• když je blok moc velký, tak ho rozpůlím

• hardwarová nebo softwarová struktura, v níž jsou uložena data, aby se zrychlily operace s nimi
• velikost cache je omezená
• CPU používá cache, aby zrychlil přístup do paměti (když má data uložená v cachi, nechodí pro ně do paměti)
• cache je tvořena jednotlivými řádky (obvykle mají 64 bajtů, jsou zarovnány)
• cache hit – požadavek je odbaven z cache
• cache miss
  • data nebyla nalezena v hierarchii cache
  • provádí se přístup do paměti
  • načtená data se ukládají do cache
  • pokud není volná cache line, uloží se na místo jiné cache
    • tato původní cache se propisuje do hlavní paměti (při zapisování dat totiž procesor zapisuje do cache)
• stav cache line se udržuje pomocí MESI protokolu
• technická realizace cache = asociativní paměť
  • je to v podstatě tabulka – vlevo klíč (odpovídající adresa v paměti), vpravo hodnota (cache line)
  • konstantně rychle se v ní hledá klíč
  • rychlost se zajišťuje hardwarově

• SMP – symetrický multiprocessing
  • všechny procesory přistupují do paměti přes systémovou sběrnici
  • přístupy jsou stejně rychlé
• NUMA – non-uniform memory access
  • každý procesor má „svůj“ blok paměti
  • jeden společný adresový prostor vzniklý sloučením bloků jednotlivých pamětí
  • každý procesor může adresovat libovolnou paměť
  • přístupy jsou různě rychlé – přístupy do „cizích“ pamětí trvají déle

• preprocesor
• kompilátor (překladač)
• assembler
• linker

• lidi už pak používají přímo hlavičkový soubor a statickou zkompilovanou knihovnu
• pokud je knihovna statická, použije ji linker, pokud je dynamická, použije ji až loader

• u toho procesu musí OS nějak řešit paměť
• překladač jednotlivé části programu dává do správných segmentů
  • příklady segmentů – globální proměnné, konstanty, instrukce…
• v paměti je kód, statická data, zásobník (vzájemné volání funkcí, lokální proměnné) a halda (na dynamickou alokaci proměnných)
• realističtěji – kód, konstanty, inicializovaná statická data (např. int x = 5;, konkrétní hodnoty jsou umístěny ve spustitelném souboru), neinicializovaná statická data (např. objekty – konstruktor se volá až při běhu programu), jeden zásobník pro každé vlákno (při rekurzi může dojít), halda

• linker vezme segmenty z každého souboru a slije je dohromady
• z knihovny do výsledného souboru skládá jenom ty funkce, které jsou opravdu použity
• linker přepočítává adresy na základě toho, jak za sebe skládá segmenty (začátek segmentu je na adrese 0)
• loader pak ty adresy po spuštění přepočítává znova podle toho, kde jsou segmenty uloženy v paměti

• každá funkce má na zásobníku aktivační záznam
• na zásobník uložím (z registrů) návratovou adresu a adresu aktivačního záznamu funkce, která mě volala
• některé další registry (které mají vlastnost Preserve) uložím do zásobníku, aby nebyly poškozeny
• volací konvence jasně deklaruje, jak se hodnoty předávají z volané funkce do volající
• volající funkce připraví na zásobníku prostor (strukturu) pro vrácenou hodnotu, překladač adresu této struktury předá volané funkci jako parametr
• relativní adresace lokálních dat a dočasných proměnných – adresy se počítají relativně vůči frame pointeru
• technologie linkeru a loaderu je stará a nepočítala s přetížením funkcí – proto se dělá public name mangling (do jmen funkcí se vkládá otisk typů a jmen parametrů)
• musí být jasně definované, co každá funkce uklízí
• parametry fungují v podstatě stejně jako lokální proměnné
• předávání parametrů
  • předání hodnotou – na zásobník dám kopii vypočítané hodnoty parametru
  • předání referencí – na zásobník dám ukazatel (adresu) na parametr
    • v C se všechny parametry předávají hodnotou, takže se vlastně pointery kopírují

• proměnná = pojmenovaný kus paměti, v němž je uložena hodnota; má typ
• způsob uložení
  • statická data – globální proměnné v C
  • zásobník – lokální proměnné v C
  • halda – dynamická paměť v C/C#
• slovník (Python, PHP, JavaScript)
  • dynamická struktura

• úložiště pro dynamickou paměť
• alokace – vedeme si evidenci volných bloků, používá se nějaký ze zmíněných algoritmů
  • alternativní přístup – inkrementální alokace, vycházíme z předpokladu, že paměť nedojde
• dealokace – někde explicitní (C, C++), jinde automatická pomocí garbage collectoru
  • když přijdu o pointer na objekt v paměti (takže ho nemůžu smazat) = memory leak
  • u explicitní dealokace se používá funkce free – může být problém, pokud ji na jeden objekt voláme víckrát
  • GC se spustí, jakmile dojde paměť
  • při běhu garbage collectoru se může běh programu úplně zaseknout
  • přístupy k GC
    • tracing – procházíme všechny živé objekty a hledáme, co je z nich dosažitelné
    • reference counting

• může se lišit velikost typů na různých architekturách (u některých jazyků)
• někdy může hrát roli i endianita
• některé překladače mají specifické funkce (nebo syntaxi) navíc – ty není dobrý nápad používat
• volání funkcí OS přímo pomocí příkazů (někdy to není problém, pokud OS používají stejnou knihovnu)
• přenositelnost se někdy řeší pomocí virtuálního stoje (VM)
  • C#, Java
  • program se přeloží do bytecodu (Java) nebo CIL (C#)
  • jsou to „instrukce procesoru, který neexistuje“
  • pak je tam běhová podpora, která zpracovává instrukce abstraktního procesoru a vykonává instrukce toho konkrétního procesoru, na kterém běží – tenhle přístup je extrémně pomalý
  • výhoda: lze to zavřít do sandboxu
  • řešení problémů s rychlostí
    • JIT (just in time) kompilace – překládá mezikód do nativního kódu na vyžádání, pokud daný překlad ještě neexistuje
    • AOT (ahead of time) kompilace – při instalaci program přeložím do nativního kódu (používá se třeba u Androidu)

• abstraktní stroj
  • je reprezentován rozhraním jádra
  • schovává komplexitu hardwaru
• správa zdrojů
  • management hardwaru zajišťuje OS
  • sdílení HW mezi aplikacemi
    • alokace paměti
    • procesorový čas
    • abstrakce (disk, síť)

• uživatelský režim
  • přístupný všem aplikacím
  • omezený přístup ke zdrojům
• kernel mode
  • je používán operačním systémem nebo jeho částí
  • má plný přístup ke zdrojům
• přechod mezi režimy je jasně definovaný – je pouze omezené množství způsobů, jak přepnout z uživatelského do kernel režimu (aby bylo možné vyhodnotit, zda je to záměr, nebo chyba)
  • syscall = volání systémového API
  • tenká vrstva nad OS zajišťuje syscally

• monolitická
  • obslužná vrstva, jejím prostřednictvím se volají interní funkce
  • takhle funguje linuxový kernel
  • zranitelnost – programy v jádře mohou dělat cokoliv
  • původně byly součásti jádra pevně nastavené od instalaci
    • problém – při připojení klávesnice chceme nainstalovat driver zařízení -> dnes lze obsah jádra měnit
• vrstvená
  • každá vrstva má svoje rozhraní
  • každá vrstva může používat jenom vrstvu přímo pod ní (její rozhraní)
• mikrokernel
  • většina služeb se z kernel space vystrčí do user space, jsou tam jako jednotlivé moduly, ty komunikují bez sebou a s jádrem
  • je to rozšiřitelné, spolehlivé (jednotlivé služby lze v případě chyby restartovat) a bezpečné, ale poměrně pomalé
  • takhle fungují Windows
    • mají ještě hardwarovou abstrakční vrstvu, takže mikrokernel je přenositelný
    • služby běží v kernel režimu (což je v rozporu s filozofií mikrokernel)

• pojmy
  • řadič zařízení (controller) – HW součástka, komunikuje se zařízením nějakým protokolem
  • ovladač zařízení (driver) – SW komoponenta, součást operačního systému, realizuje komunikaci s řadičem, poskytuje operačnímu systému jednotné komunikační zařízení
  • BIOS/UEFI – inicializuje zařízení při bootu
• topologie zařízení
  • sběrnice
    • řadič, z něj vychází jeden drát, na něj jsou všechna zařízení připojena
    • na jedné sběrnici je přetlak
    • při paralelním vedení drátů je problém s přeslechy (vzájemné rušení signálů)
  • hvězda
    • každé zařízení je připojeno k řadiči samostatně
    • takhle funguje SATA
    • nevýhoda – na řadiči musí být víc konektorů
    • výhoda – na drátu není nikdo jiný, takže není potřeba řešit adresaci
    • používají se sériové protokoly – jsou rychlejší než paralelní
  • ring
    • signál se po kruhu pohybuje jedním směrem – každé zařízení (i řadič) jedním portem vysílá a druhým přijímá
  • strom
    • k řadiči můžu připojit rozbočovač (hub)
    • takhle funguje USB
• jak CPU provádí I/O operace
  • buď má speciální instrukce, nebo používá memory-mapping
• uživatel chce nějaké množství dat – jejich získání zajišťuje kernel/řadič (může být potřeba několik dotazů)
• komunikace se zařízeními
  • polling – CPU se aktivně ptá na změnu stavu zařízení (pomalé, dnes už se nepoužívá)
  • přerušení – řadič vyšle signál, že je operace hotová, a přeruší chod procesoru (ale pořád musím kopírovat data, což je pomalé)
  • DMA (Direct Memory Access) – přenos dat ze zařízení do paměti probíhá hardwarově bez účasti procesoru, až pak se provede přerušení; funkce scatter/gather umožňuje využívat nesouvislé části paměti
• typy přerušení
  • externí – hardwarové pomocí IRQ pinu, lze ho zamaskovat (deaktivovat – pomocí registru)
  • (hardwarová) výjimka – nastal problém s instrukcemi -> procesor vyvolá přerušení a nechá na OS, aby situaci vyřešil
    • výjimka typu trap se volá po instrukci, např. dělení nulou
    • u výjimek typu fault se procesor vrátí na stav před instrukcí, nechám OS, aby problém opravil, a potom instrukci pustím znova
  • softwarové – speciální instrukce
• jak funguje přerušení
  • CPU zjistí zdroj přerušení
  • získá adresu handleru
  • proud instrukcí je přerušen
  • handler uloží stav CPU
  • handler udělá něco užitečného
  • handler obnoví stav CPU
  • CPU pokračuje v proudu instrukcí

• instance programu vytvořená operačním systémem
• je to datová struktura uvnitř operačního systému, v níž jsou uložené různá data, která daný program potřebuje
• vlastní: kód, prostor v paměti, další prostředky

• místo uvnitř procesu, kde se vykonávají instrukce
• kontext procesoru – datová struktura, ve které jsou uložené registry procesoru, pokud dané vlákno zrovna neběží
• vlastní: pozici v kódu (program counter), svůj zásobník, stav procesoru

• lightweight vlákno
• nemá celý kontext
• scheduling se dělá kooperativně (jednotlivé fibery se vzájemně vyměňují v běhu)

• created
• ready
• running
• blocked
• terminated (zombie)

• cooperative – všechny procesy kooperují, předávají si řízení
• preemptive – každé vlákno dostane od scheduleru svůj time slice; jakmile čas vyprší, dojde k přerušení

• priorita – vázaná na proces
  • je dvousložková – při spuštění se přiděluje statická priorita (podle uživatele), dynamická priorita se v časových intervalech pravidelně zvyšuje všem ready vláknům (po spuštění se dynamická priorita sníží na nula); celková priorita je daná součtem
• kooperativní algoritmy
  • first come, first serve (FCFS)
    • FIFO řada, procesy se vykonávají v pořadí, ve kterém přišly
  • shortest job first
    • musí být známý očekávaný čas běhu
  • longest job first
• preemptivní algoritmy
  • round robin
    • jako FCFS
    • když vlákno trvá moc dlouho, tak se zařadí na konec fronty
  • multilevel feedback-queue
    • každá fronta má jinak dlouhý time slice
    • první (horní) ho má kratší, ty pod ní ho mají delší
    • když vlákno trvá moc dlouho, tak se zařadí na konec nižší fronty
    • když se vlákno brzo zablokuje, tak se zařadí na konec vyšší fronty
  • completely fair scheduler (CFS)
    • používá červeno-černý strom

• kooperující procesy – jejich zdroje jsou izolovány operačním systémem, ke komunikaci používají OS-specifické IPC API
• typické IPC metody
  • pipes (nebo jiný typ socketů)
  • sdílená paměť
  • signály

• jednotka organizace dat
• kolekce souvisejících informací
• jádro OS nerozumí formátům souborů
• soubory se typicky neukládají v paměti, ale na perzistentním úložišti
• soubor je chápán jako unikátní číslo – kvůli lidem mají soubory jméno a cestu (aby v souborech nebyl chaos)
• některé části názvu souboru (počáteční tečka, přípona) mají speciální význam (ale přípona souboru nemusí souviset s reálným formátem souboru)
• operace se soubory – vyčištění cache, změna atributů, vytvoření, smazání
• file handle – číslo specifické pro proces, odkazuje na konkrétní soubor (stdin, stdout, stderr mají handles 0, 1, 2)
• buffering
  • cachování sektorů disku (když disk čtu po bajtech, první se načítá z cache, všechny ostatní v daném sektoru už se pak načítají z cache)
  • existuje několik úrovní cache (systémová, language runtime)
  • sekvenční vs. náhodný přístup
• alternativy – memory mapping, asynchronní přístup souborům

• kolekce souborů
• význam – rychlejší hledání souboru, lepší navigace pro uživatele, logické seskupení souborů
• obvykle reprezentován jako soubor
• někdy v něm můžou být uloženy některé atributy jeho souborů
• obvykle existuje kořenový adresář
• operace – vytvořit, smazat, přejmenovat, najít název, vypsat soubory

• tradiční úložiště
  • na sekundárním nebo externím úložišti
  • file system in RAM (pro dočasné soubory)
• síťové úložiště – soubory se tváří, jako by byly na disku, ale přitom jsou uloženy někde jinde na síti
• virtuální soubory – např. /dev/null

• links (hard links)
  • více adresářových záznamů odkazuje na stejný fyzický soubor
  • většina operací je transparentních
  • šetří místo, ale může dělat problémy (smazání hardlinku nesmí smazat fyzický soubor – takže OS musí počítat odkazy na daný soubor)
• symlinks (soft links)
  • symlinky jsou speciální soubory, v nichž je uložená cesta jiného souboru

• řeší překlad jmen, správu datových bloků, správu dat souborů
• pro file system je jednotkou jeden blok, blok je určitý počet sektorů
• řeší abstrakci práce se soubory a adresáři
• může být lokální (FAT, NTFS) nebo síťový (NFS, CIFS/SMB)
• práce s FAT bude u zkoušky :)

• z doby MS DOSu
• jedna struktura (FAT) spravuje volné bloky a uložení dat souborů
• adresář je sekvence záznamů s pevnou délkou a atributy (počáteční blok, název + přípona, velikost, časy, …)
• root je na fixní pozici
• formát struktury
  • boot record
  • FAT1
  • FAT2
  • root directory
  • data
• smazané soubory se označují speciálním bajtem (takže při mazání nepřepisuju data)
• FAT je pole intů
  • velikost
    • FAT = FAT16 → inty jsou 16bitové
    • FAT32 → inty jsou 32bitové
  • pole je indexované od dvojky
    • nula má speciální význam
    • jednička je kořenový adresář
  • index v poli určuje offset bloku dat, kde je uložený obsah souboru
  • hodnoty položek v poli
    • nula = odpovídající blok je volný
    • ostatní hodnoty tvoří spoják (ten začíná záznamem v adresáři, hodnota na daném indexu odkazuje na další index…)
    • minus jedna označuje poslední blok souboru
  • nepoužívá se alokační strategie – hledám první volný blok
  • FAT se dnes obvykle vejde do paměti
  • spoják je jednosměrný – takže při náhodném přístupu k souboru musím spoják projít od začátku

• starý linuxový file system
• s random access má podobný problém jako FAT
• inode reprezentuje jeden soubor/adresář
• inode je poměrně složitě zanořený, je tam daný pevný limit na velikost souboru

• na ose je několik ploten
• stopy (soustředné kružnice) se dělí na sektory
• blok – stejný sektor na všech plotnách
• cluster – stejná stopa na všech plotnách
• flying height – vzdálenost mezi hlavou a plotnou
• rotační rychlost – 5 až 15 tisíc otáček za minutu
• přístup na sektor je docela dlouhý (v jednotkách milisekund)
• rotační zpoždění – hlava na správný sektor čeká třeba 4 ms (pokud celá rotace trvá 8 ms)
• disk access time = seek time + rotational latency + transfer time
  • transfer time je zanedbatelný (ve srovnání se zbylými dvěma hodnotami)
• disk nestíhá odbavovat všechny požadavky operačního systému, takže je řadí do fronty, v disku je procesor, který se rozhoduje sám, jak je obslouží (dřív to rozhodoval OS)
• trojice čísel – CHS (cluster, head = číslo plotny, sector)
• disk scheduling algorithms
  • FCFS (First Come First Served)
  • SSTF (Shortest Seek Time First)
  • SCAN (aka Elevator algorithm) – zachovává směr (dokud je kam)
  • CSCAN (Circular SCAN) – jede jenom jedním směrem, na konci udělá seek zpátky na počáteční mez; časy seeků jsou rovnoměrnější
  • LOOK/CLOOK – jako scany, ale nenavštěvují kraje disku (dívají se, jestli tam jsou ještě požadavky)
  • FSCAN – má dvě fronty

• disk bez pohyblivých částí – jenom elektrické obvody
• NAND flash – sestává z tranzistorů
• má omezenou životnost na počet zápisů
• mřížková struktura organizovaná po blocích stránek (pages)
• vymazat se dá pouze celý blok najednou
• „smazané“ stránky se nedají přepsat, dokud není celý blok vymazán
• někdy se dělá to, že se plné stránky překopírují jinam, aby se blok mohl vymazat

dělení disku do několika logických disků – každý může mít vlastní file systém

• způsob propojení více pevných disků do jednoho
• typicky na úrovní hardwaru, ale může být implementováno pomocí OS
• hlavní cíl je zvýšení spolehlivosti a zrychlení přístupu

• instrukce procesoru pracují s virtuálními adresami
• operační paměť má fyzické adresy
• hardwarově je implementován převodní mechanismus
  • musí vyhodnotit, jestli existuje převod
  • zajistí přepočet, pokud existuje
  • tyto kroky musí být extrémně rychlé
• existují dva mechanismy – segmentace (už se nepoužívá) a stránkování
• MMU = Memory Management Unit, provádí převod
• převod paměti je transparentní
• výhody konceptu
  • větší adresový prostor – abych mohl spustit proces s většími požadavky na paměť
  • bezpečnost – aby si procesy navzájem nemohly koukat do paměti, každý má vlastní mapování; to je dnes ten hlavní důvod
• segmentace
  • virtuální adresový prostor se dělí do logických segmentů
  • segmenty mají svoje unikátní číslo, velikost, začátek (kde ve virtuální paměti daný segment začíná) a vlastnosti (např. zda se od nich smí zapisovat)
  • adresa v paměti je dvojice – číslo segmentu a offset uvnitř segmentu
  • tabulka segmentů je v paměti – je to jednoduché pole indexované číslem segmentu, pro každý segment je v poli uložená datová struktura se všemi potřebnými informacemi o segmentu
  • data o aktivních segmentech se cachují
  • když se proces snaží přistoupit k segmentu, který neexistuje, tak najdu nějaký jiný segment, data v něm uložená schovám na disk (pokud je read-only, tak to nemusím dělat, protože jsou data uložená v původním exe souboru) a segment můžu použít
  • v případě chyby – segmentation fault
• stránkování (paging) – používá se
  • virtuální adresový prostor (VAS) je rozdělen na stejné části (stránky, jejich velikost odpovídá mocninám dvojky)
  • fyzický adresový prostor (PAS) je rozdělen na stejné části (rámce, framy, mají stejnou velikost jako stránky)
  • VAS je jednorozměrný, instrukce pracují s jedním číslem
  • page table (stránkovací tabulka)
    • zajišťuje překlad adres
    • je to pole stránek (indexované číslem stránky)
    • každý záznam obsahuje číslo framu a atributy
    • je tam jednička/nula – aby se dalo určit, jestli stránka fyzicky existuje
    • v případě chyby – page fault
  • virtuální adresa se navenek jeví jako jedno číslo, ale protože velikost stránky je mocnina dvojky, tak část binárního čísla odpovídá číslu stránky a část offsetu
  • když mi dojde fyzická paměť, tak nějakou stránku uložím na disk – je to obvykle méně dat, než by to bylo při výpadku segmentu (segmenty měly různé velikosti, stránky jsou všechny stejně velké)
  • problémy s page table
    • velikost
      • 32-bit VA/PA, 4k paes/frames (12 bits)
        • jedna stránka = 4 bajty
        • počet stránek = $2^{20}$
        • takže 4 MB pro každý proces
      • nápad – víceúrovňové stránkovací tabulky
        • obvykle nepotřebuju celou tabulku
        • první úroveň tabulky je vždycky v paměti, další úrovně tam být nemusí
        • je to vlastně strom
        • může být výpadek stránkovací tabulky
    • rychlost
      • každý přístup do paměti znamená alespoň jeden další přístup do paměti
      • TLB (Translation Lookaside Buffer)
        • asociativní paměť (mapa)
        • cachuju převody mezi adresou stránky a framu
        • některé procesory nemají stránkovací tabulku, mají jenom TLB – tuhle logiku řeší OS
  • reálný příklad
    • 32-bit adresa
    • posledních 12 bitů určuje offset
    • číslo stránky rozdělím na dvakrát 10 bitů
    • každá část odpovídá jedné úrovni stránkování
    • prvních deset bitů použiju k indexaci do první tabulky
    • dozvím se číslo rámce tabulky druhé úrovně
    • použiju druhých deset bitů k indexaci do druhé tabulky
    • dozvím se číslo rámce dat, použiju offset a mám data
  • příklad (může být ve zkoušce)
    • 32bitové adresy
    • dvouúrovňové stránkování, 4KiB stránky
    • inty mají 4 bajty
    • sčítám dva tisíce intů do jednoho long longu
    • kolik page faultů maximálně může nastat?
    • čtu 8 000 bajtů, stránky mají 4 000
    • v nejhorším případě bude těch 8 000 sahat do tří stránek
    • můžou nastat tři výpadky stránek + nemusí existovat stránkovací tabulky druhé úrovně
    • stránkovací tabulka druhé úrovně pokrývá 4 MB
      • tudíž mi stačí jedna
      • ale v nejhorším případě se to nevejde do jedné, ale do dvou, takže můžou nastat dva výpadky
    • takže celkem pět výpadků
  • proces převodu adresy
    • vezmu adresu a rozdělím ji na číslo stránky a offset
    • vezmu číslo stránky a podívám se do TLB (pokud ho má → mám číslo rámce → slepím s offsetem → hotovo)
    • pokud ho TLB nemá, pokračuju dál – projdu stránkovací tabulky
    • v tabulce/TLB jsou dva příznaky
      • A (accessed) – přistoupil jsem tam
      • D (dirty) – něco jsem tam zapsal
    • aktualizuju ty příznaky podle reality
    • adresu slepím s offsetem, přistoupím k datům
    • když v tabulce není present bit, tak vrátím page fault
    • převod uložím do TLB
  • adresy přepočítává hardware (softwarově by to bylo pomalé)
  • v TLB jsou vždycky 3 bity – Accessed, Dirty, Present
  • připomenutí: fault vypadne před instrukcí × trap za instrukcí
  • page fault handling
    • zajišťuje OS
    • provádí se kontrola, jestli program sahá na adresu, kam má přístup
    • vytváří se mapování – hledá se volný rámec
      • pokud je paměť plná, tak se najde oběť (pomocí page replacement algoritmu) – pokud je dirty, tak se uloží; odstraní se mapping z TLB
    • opakuje instrukci
  • page replacement algoritmy (používají se u rámců, TLB, cachí…)
    • optimální algoritmus – pouze teoretický, nahradí stránku, ke které budeme přistupovat za nejdelší dobu
    • clock
      • rámce jsou organizovány kruhově
      • ručička ukazuje na rámec, který bude nahrazen
      • pokud má rámec nenulový Accessed bit, nastavím ho na nulu a posunu se dál
      • pokud ho má rámec nulový, tak ho nahradím
    • NRU (not recently used)
      • Accessed bit pravidelně nuluju
      • klasifikuju rámce podle jejich A, D bitů do čtyři tříd
        • A0, D0 … třída 0
        • A0, D1 … třída 1
        • A1, D0 … třída 2
        • A1, D1 … třída 3
      • použiju náhodný rámec z neprázdné třídy s nejnižším číslem
    • LRU (least recently used)
      • používá minulost k předpovědi budoucnosti
      • nahrazuje stránku, která nebyla použita nejdéle
      • HW implementace cachí nebo bitovou maticí
    • NFU (not frequently used)
      • bokem mám počítadlo pro rámec
      • jednou za čas vezmu A a přičtu ho k počítadlu a vynuluju A
      • vyberu frame s nejnižším počítadlem
      • problémy – nově přidané rámce jsou vyhozeny dříve, než nasbírají dostatek bodů v počítadle; rámce, které byly hodně používány nebudou nikdy vyhozeny
      • stárnutí – periodicky dělím počítadla (shiftuju)
      • když stránku namapuju, tak jí dám nějakou počáteční hodnotu do počítadla, aby nebyla hned eliminována
  • sdílená paměť
    • část virtuálního adresového prostoru je sdílená mezi procesy
    • ty používají sdílenou paměť ke komunikaci
  • paměťově mapované soubory
    • virtuální adresový prostor ukazuje do souboru

• VM – hypervisor zajišťuje virtualizaci hardwaru
• virtualizace na úrovni OS

• více vláken přistupuje ke sdílenému prostředku
• to vede k tomu, že výsledek výpočtu závisí na plánování operačního systému nebo na chování procesoru
• takový výsledek je k ničemu
• řešila by to atomizace read-modify-write operace
• definuju kritickou sekci
• pomocí synchronizačního primitiva zajistím, že v kritické sekci je jenom jedno vlákno
• aktivní a pasivní/blokující synchronizační primitiva
  • aktivní vykonávají instrukce a pořád koukají do kritické sekce, jestli tam můžou
  • pasivní/blokující jsou zablokovány, dokud není přístup povolen
• hardwarová podpora – atomické instrukce test-and-set (TSL), compare-and-swap (CAS)
• spin-lock
• semafor

• jedna správná odpověď (zaškrtnout)
• několik správných odpovědí

• page faults
  • pozor na rozdíl mezi čtením a kopírováním
  • při kopírování jich vypadne 8 (úloha viz prezentace)
• struktura (struct) – vnější a vnitřní zarovnání, počítání offsetu
• FAT (odpověď: 10, 15)
• vybrat kód
• Jedná se o alokaci souvislých bloků paměti. Máte zadaný typ algoritmu pro alokaci (např. first fit) a sekvenci alokací a dealokací bloků různé velikosti. A otázka pak zní: Na jaké adrese leží nějaký blok na heapu, pokud byl použitý daný algoritmus?
• ale můžou tam být i jiné otázky