# 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ě