Počítačové systémy

CPU

• ABI
• MIPS registry – jejich účely (jak by se měly používat) jsou popsány v MIPSovém ABI
  • 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ů
• základní instrukce
  • 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
• MIPS instrukce
  • 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
• příznaky na x86
  • 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 – shrnutí
  • 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
• hardwarová architektura
  • 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í)
• pipeline
  • 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
• superskalární procesor
  • 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
• out-of-order execution
  • mikroinstrukce se umístí do poolu a čekají, až budou mít výkonné jednotky volno
  • jednotlivé jednotky umí různé věci

Paměť

• podle rychlosti: registry, cache, RAM, perzistentní RAM, SSD + flash disky, HDD, magnetické pásky
  • 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)
• paměť – definice
  • 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)
• fyzický pohled na paměť
  • 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
• datová reprezentace
  • 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
• endianita – vícebytová čísla se v paměti ukládají tak, že je MSB na začátku (big endian), nebo LSB na začátku (little endian)
• zarovnání dat
  • 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
• správa paměti
  • 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
• alokace paměti
  • ú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)
• fragmentace
  • 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
• dynamická alokace paměti – mám spojový seznam volných bloků nebo bitmapu (kde každý bit reprezentuje jeden blok)
• alokační algoritmy
  • 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
• cvičení na alokaci – alokuju do 64B bloků
  • 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
• buddy memory allocation
  • 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
• cache
  • 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ě
• víceprocesorový systém
  • 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

Programovací jazyky

• překladač, gramatika
• překlad
  • preprocesor
  • kompilátor (překladač)
  • assembler
  • linker
• knihovna – statická nebo dynamická sada binárek
• linking – spojení binárek do jedné
• loader – načte program do paměti
• program vs. proces (proces je spuštěný program, entita operačního systému)
• knihovna se linkuje do souboru .lib (statická knihovna)
  • 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
• organizace paměti
  • 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
• linking
  • 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
• volací konvence
  • 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é
  • 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
• halda
  • ú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
• přenositelnost kódu
  • 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)

Operační systém

• role OS
  • 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íť)
• režimy procesoru (bývá jich několik, ale nejdůležitější jsou dva)
  • 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
• architektura
  • 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)
• zařízení
  • 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í
• program = pasivní soubor na disku
• loader – vezme program a načte ho do paměti
• někde v hlavičce programu je informace o tom, kde program (výkon instrukcí) začíná
• proces
  • 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
• vlákno (thread)
  • 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
• fiber
  • lightweight vlákno
  • nemá celý kontext
  • scheduling se dělá kooperativně (jednotlivé fibery se vzájemně vyměňují v běhu)
• scheduler – část operačního systému, používá schedulingové algoritmy k přidělení zdrojů (jader) jednotkám
• když se přeruší vykonávání vlákna, provede se context switch – kontext procesoru se uloží
• real-time scheduling: real-time proces má čas, kdy se má spustit, a čas, do kdy má skončit (hard deadline – nemá smysl pokračovat, soft deadline – má smysl pokračovat ve výpočtu)
• stavy vlákna
  • created
  • ready
  • running
  • blocked
  • terminated (zombie)
• multitasking
  • 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í
• scheduling
  • 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
• komunikace mezi procesy (inter-process communication = IPC)
  • 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
• soubor
  • 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
• adresář
  • 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
• ukládání souborů
  • 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
• file links
  • 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
• file system
  • ř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 :)
• File Allocation Table (FAT)
  • 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
• Second extended file system (ext2)
  • 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
• rotační pevný disk
  • 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
• solid-state disk (SSD)
  • 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
• HDD partitioning (diskové oddíly)
  • dělení disku do několika logických disků – každý může mít vlastní file systém
• RAID (Redundant Array of Inexpensive Disks)
  • 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
• virtuální paměť
  • 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
• virtualizace
  • VM – hypervisor zajišťuje virtualizaci hardwaru
  • virtualizace na úrovni OS

Paralelní počítání

• chci zrychlit výpočet
• race condition
  • 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

Zkouška

• nezávislá na zápočtu
• test u počítače v laborce – musíme se zapsat v SISu
• nepotřebujeme vůbec nic – ale máme si vzít prázdné papíry a tužku + můžeme si vzít kalkulačku (nebo si pustíme na počítači)
• stačí nám znalosti z přednášky
• 10 otázek
• některé čistě teoretické
  • jedna správná odpověď (zaškrtnout)
  • několik správných odpovědí
• další otázky počítací (je jich 5)
  • 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
• je na to zhruba hodina (ale klidně dvě hodiny)
• odpovědi musí být správné, na postupu nezáleží
• v češtině i angličtině