Řízení vnější paměti

Abychom pochopili, proč vůbec vnější paměť existuje, musíme si nejprve uvědomit základní omezení operační paměti (RAM). RAM je rychlá, přímo adresovatelná paměť, ve které procesor čte a zapisuje data v řádu nanosekund. Jenže má dvě zásadní nevýhody: je volatilní (po vypnutí napájení přijde o veškerý obsah) a kapacitně omezená (a historicky extrémně drahá na gigabajt).

Vnější paměť — tedy primárně magnetické pevné disky (HDD), optická média a dnes SSD — proto plní v počítačovém systému roli trvalého úložiště. Její obsah přežije vypnutí stroje, může být řádově větší než RAM a cena za gigabajt je podstatně nižší. Z pohledu operačního systému se jedná o tzv. sekundární paměťové médium, na němž jsou uloženy soubory, databáze, stránkovací soubor (swap), spustitelné programy a veškerá data, která mají přežít restart.

Operační systém musí vnější paměť aktivně řídit, protože fyzický přístup na disk je mnoho řádů pomalejší než přístup do RAM. Zatímco RAM odpoví v řádu nanosekund, HDD potřebuje v průměru 5–15 milisekund — tedy milionkrát déle. To znamená, že způsob, jakým OS organizuje data na disku a jakým pořadím obsluhuje požadavky na čtení/zápis, má dramatický dopad na výkon celého systému. Proto OS musí mít propracované algoritmy jak pro rozmístění dat (alokace místa), tak pro pořadí obsluhy (plánování přístupu).

Pevný disk (Hard Disk Drive, HDD) je mechanické zařízení, ve kterém jsou data uložena magneticky na rotujících kotoučích zvaných plotny (anglicky platters). Pochopení jeho fyzické struktury je klíčové pro porozumění tomu, proč jsou některé operace pomalé a jak plánovací algoritmy mohou tuto pomalost minimalizovat.

Fyzická struktura HDD: Soustředné kružnice na povrchu plotny jsou stopy; každá stopa je rozdělena na sektory — nejmenší adresovatelné jednotky. Čtecí/zapisovací hlavy jsou zavěšeny na raménku aktuátoru a pohybují se radiálně nad povrchem.

Fyzická struktura

Uvnitř HDD se nachází jeden nebo více hliníkových nebo skleněných kotoučů potažených feromagnetickým materiálem. Tyto plotny se točí konstantní rychlostí — typicky 5400, 7200, nebo u serverových disků až 15 000 otáček za minutu (RPM). Data jsou zapisována a čtena pomocí čtecích/zapisovacích hlav (read/write heads), které se pohybují radiálně nad povrchem plotny, aniž by se ho dotýkaly — jsou od něj vzdáleny doslova zlomky mikrometru.

Každá plotna má dvě strany, na každé straně pracuje jedna hlava. Všechny hlavy jsou mechanicky spojeny a pohybují se současně. Povrch plotny je rozdělen do soustředných kružnic zvaných stopy (tracks). Každá stopa je dále rozdělena na sektory — nejmenší adresovatelné jednotky disku, tradičně o velikosti 512 bajtů, moderní disky používají 4096 bajtů (tzv. Advanced Format).

Stopy se stejným číslem napříč všemi plotnami (a jejich stranami) tvoří válec (cylinder). Tento koncept je důležitý pro efektivitu: pokud čteme data uložená v jednom válci, nepotřebujeme pohybovat hlavami — stačí přepínat mezi hlavami elektronicky, což je okamžité.

Čas přístupu a jeho složky

Celkový čas přístupu (access time) k datům na HDD se skládá ze tří složek, z nichž každá má jiný charakter:

1. Doba vyhledávání (seek time): Čas potřebný k přesunu ramene aktuátoru tak, aby hlavy nastavily nad správnou stopu. Toto je mechanický pohyb, typicky 3–15 ms průměrně. Je to dominantní složka celkového zpoždění a právě ji se snaží plánovací algoritmy minimalizovat.

2. Rotační latence (rotational latency): Jakmile je hlava nad správnou stopou, musíme počkat, až se plotna otočí tak, aby pod hlavou prošel požadovaný sektor. Průměrně se čeká na půl otáčky. Při 7200 RPM trvá jedna otáčka 8,33 ms, takže průměrná rotační latence je ≈ 4,17 ms.

3. Doba přenosu (transfer time): Samotné přečtení nebo zapsání dat, když hlava sedí nad správným sektorem. Moderní HDD přenáší data rychlostí 100–200 MB/s sekvenčně.

Adresování: CHS a LBA

Historicky se data na disku adresovala pomocí tří čísel: Cylinder–Head–Sector (CHS). OS musel říct: „Chci data z válce číslo C, hlavy číslo H, sektoru číslo S." Tento systém byl přirozený pro fyzickou geometrii disku, ale měl vážná omezení — BIOS zvládl adresovat jen 1024 válců × 256 hlav × 63 sektorů = přibližně 8 GB.

Moderní disky proto používají Logical Block Addressing (LBA): celý disk je prezentován jako lineární pole sektorů číslovaných od 0 do N-1. OS neví nic o fyzické geometrii — číslo bloku přeloží firmware disku na skutečné fyzické umístění. LBA je elegantnější, škálovatelné a umožňuje diskům interně optimalizovat rozložení dat.

SMART – Self-Monitoring, Analysis and Reporting Technology

HDD obsahuje vestavěný systém sebediagnostiky zvaný S.M.A.R.T. Disk průběžně monitoruje desítky parametrů svého zdraví: počet přesměrovaných sektorů (vadné sektory, které disk automaticky nahradil záložními), teplotu, počet startů motoru, celkový počet hodin provozu, chybovost čtení a mnoho dalšího. OS nebo specializovaný software může tyto hodnoty číst a předpovídat blížící se selhání disku ještě předtím, než dojde ke ztrátě dat.

Operační systém musí řešit fundamentální problém: jak rozložit soubory po disku. Disk je z pohledu OS lineární posloupnost bloků (sektorů nebo jejich násobků). Soubory mají různé velikosti, vznikají, rostou, zmenšují se a mažou. Jak efektivně spravovat tento prostor? Existují tři základní přístupy, z nichž každý dělá jiný kompromis mezi výkonem, efektivitou a složitostí.

Spojité přidělování (Contiguous Allocation)

Nejjednodušší a nejintuitivnější metoda: každý soubor obsazuje nepřerušenou sérii bloků na disku. Pokud soubor potřebuje N bloků a první volný blok je na pozici B, soubor zabírá bloky B, B+1, B+2, …, B+N-1. Adresář si pamatuje pouze počáteční blok a délku souboru.

Spojité přidělování: Každý soubor (mail, list, tr) zabírá nepřerušený úsek bloků. Adresář uchovává jen počáteční blok a délku. Všimněte si, jak mezery vzniklé po smazaných souborech (šedé bloky) mohou být příliš malé pro nový soubor — to je vnější fragmentace.

Výhody: Sekvenční čtení je maximálně rychlé — hlavy se pohybují lineárně, přechody mezi bloky jsou minimální. Pro náhodný přístup (chci k-tý blok souboru) stačí jednoduchý výpočet: pozice = B + k, tedy O(1) bez procházení jakýchkoliv metadat.

Nevýhody: Metoda trpí dvěma závažnými problémy. Za prvé vnější fragmentace: po opakovaném vytváření a mazání souborů vznikají volné "mezery", které jsou příliš malé pro nové soubory, přestože celkový volný prostor může být dostatečný. Za druhé je zde problém dopředného přidělení: při vytváření souboru musíme vědět, jak velký bude, a pokud soubor chce růst, musíme ho celý přesunout.

Spojitý seznam (Linked Allocation)

Tato metoda řeší problém fragmentace tak, že propojuje bloky souboru pomocí ukazatelů. Každý blok obsahuje kromě dat také ukazatel na následující blok daného souboru. Adresář si pamatuje jen adresu prvního bloku. Chceme-li přečíst soubor, jdeme od prvního bloku k druhému (adresu najdeme v prvním bloku), od druhého ke třetímu atd. — jako spojový seznam v programování.

Spojitý seznam (linked allocation): Bloky souboru nemusí být sousední — každý blok obsahuje ukazatel na blok následující. Adresář ukládá jen adresu prvního bloku. Pozorujte, jak jsou bloky jednoho souboru rozptýleny po celém disku: to eliminuje fragmentaci, ale znemožňuje přímý přístup k libovolnému bloku.

Výhody: Odpadá vnější fragmentace — každý volný blok lze použít, bez ohledu na jeho polohu. Soubor může růst jednoduše přidáním nového bloku kdekoliv na disku. Není potřeba předem znát velikost souboru.

Nevýhody: Klíčovým problémem je pomalý náhodný přístup. Chceme-li přeskočit na k-tý blok souboru, nemáme jinou možnost než projít celý řetěz od začátku — sekvenčně načíst k-1 bloků, abychom zjistili adresu k-tého. Pro velké soubory je to devastující výkon. Dalším problémem je spolehlivost: pokud se poškodí jeden blok v řetězu, ztrácíme přístup ke všem následujícím blokům souboru.

FAT — File Allocation Table (varianta spojového seznamu)

Praktická a velmi úspěšná varianta spojového seznamu je FAT (File Allocation Table). Namísto ukládání ukazatelů přímo do datových bloků se všechny ukazatele soustředí do jedné tabulky na začátku disku. FAT je pole, kde index odpovídá číslu bloku a hodnota na daném indexu říká, který blok je následující. Celá FAT se dá načíst do operační paměti, takže procházení řetězu je rychlé — probíhá v paměti, nikoliv fyzickými přístupy na disk.

Indexová alokace (Indexed Allocation)

Indexová alokace je kompromis, který řeší nedostatky obou předchozích metod. Pro každý soubor existuje speciální blok zvaný indexový blok (nebo index node, i-node). Tento blok obsahuje pole ukazatelů na datové bloky souboru — každý ukazatel v indexovém bloku ukazuje přímo na jeden datový blok. Adresář si pamatuje pouze adresu indexového bloku.

Indexová alokace: Každý soubor má svůj indexový blok, který obsahuje pole ukazatelů na jednotlivé datové bloky. Pro přístup k n-tému bloku souboru stačí přečíst indexový blok a skok přímo na ptr[n] — žádné procházení řetězu, O(1) přístup.

I-node struktura: Indexový blok (i-node) se záznamy pro každý datový blok souboru. Každý řádek odpovídá jednomu ukazateli — datové bloky mohou být rozmístěny libovolně po disku.

Víceúrovňová indexace: Pro velké soubory přidává Unix/Linux nepřímé ukazatele (single, double, triple indirect), čímž umožňuje soubory o velikosti gigabajtů až terabajtů, aniž by trpěl výkon malých souborů.

Výhody: Umožňuje přímý přístup k libovolnému bloku souboru v O(1) — stačí přečíst indexový blok a pak skočit přímo na požadovaný datový blok. Nedochází k vnější fragmentaci. Poškozením jednoho datového bloku nepřicházíme o zbytek souboru.

Nevýhody: Každý soubor zabírá alespoň jeden celý indexový blok, i když je soubor velmi malý. Pro obří soubory je potřeba víceúrovňová indexace — Unix/Linuxové souborové systémy (ext2/3/4) řeší toto pomocí hierarchie přímých, nepřímých (single indirect), dvojitě nepřímých (double indirect) a trojitě nepřímých (triple indirect) ukazatelů. Malé soubory jsou obsluhovány přes přímé ukazatele rychle; obří soubory využívají nepřímé úrovně automaticky.

Moderní operační systém obsluhuje současně desítky až stovky procesů, každý z nich může generovat požadavky na čtení nebo zápis různých sektorů disku. Tyto požadavky se hromadí ve frontě diskových požadavků. Klíčová otázka: v jakém pořadí tyto požadavky obsloužíme?

Protože přesun hlavy (seek) je nejdražší operací, může jiné pořadí obsluhy dramaticky zkrátit celkovou vzdálenost, kterou hlavy urazí, a tím snížit průměrnou dobu odezvy. Právě o to se starají diskové plánovací algoritmy.

FCFS — First Come, First Served

FCFS (First Come, First Served — „první přišel, první obsloužen") je nejjednodušší možný přístup: požadavky se obsluhují přesně v tom pořadí, v jakém dorazily. Žádná optimalizace, žádná inteligence. Je to dokonale férové vůči procesům, ale výkonnostně bývá suboptimální — hlava "divoce" skáče přes celý disk.

FCFS — pohyb hlavy: Šipky ukazují pořadí obsluhy přesně tak, jak požadavky přišly: 50 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67. Jsou zřetelně vidět obrovské skoky (např. 183 → 37, pak 122 → 14), které zbytečně prodlužují celkovou dobu obsluhy. Celková vzdálenost: 643 stop.

SSTF — Shortest Seek Time First

SSTF vždy obslouží ten požadavek, ke kterému má hlava v danou chvíli nejblíže. Je to hladový (greedy) algoritmus — v každém kroku volí lokálně optimální rozhodnutí. Výrazně snižuje celkovou vzdálenost, ale hrozí hladovění (starvation) vzdálených požadavků.

SSTF — pohyb hlavy: Hlava vždy skočí na nejbližší čekající stopu. Pohyb je mnohem efektivnější než u FCFS — krátké skoky v blízkém okolí. Nevýhoda je viditelná v situaci, kdy hlava "uvázne" v hustém clusteru požadavků a vzdálené stopy (jako 183 nebo 14) musí čekat. Celková vzdálenost: 239 stop.

SCAN (výtahový algoritmus)

SCAN se inspiruje výtahem: hlava se pohybuje v jednom směru, cestou obsluhuje všechny požadavky, při dosažení konce disku se obrátí a jede zpět — opět obsluhuje vše, co potká. Eliminuje hladovění, ale požadavky těsně za místem otočení čekají nejdéle.

SCAN — pohyb hlavy (výtahový algoritmus): Hlava nejprve obslouží vše ve směru nahoru (65, 67, 98, 122, 124, 183), dojede na konec disku (199), pak se obrátí a obslouží požadavky při cestě dolů (37, 14). Pohyb připomíná výtah — lineární průjezd jedním směrem, pak druhým. Celková vzdálenost: ≈ 334 stop.

C-SCAN — Circular SCAN

C-SCAN řeší nerovnoměrné čekací doby algoritmu SCAN. Hlava se pohybuje vždy jedním směrem. Při dosažení konce disku skočí bez obsluhy zpět na začátek a opět pokračuje stejným směrem — jako kruhový dopravník. Každý bod na disku čeká přibližně stejně dlouho.

C-SCAN — kruhový pohyb hlavy: Hlava jede výhradně jedním směrem (nahoru). Po obsloužení všech požadavků v tomto směru (65, 67, 98, 122, 124, 183) přeskočí bez obsluhy zpět na začátek disku (přerušovaná šipka) a pokračuje dál (14, 37). Výsledkem je rovnoměrnější rozložení čekacích dob oproti SCAN. Celková vzdálenost: ≈ 382 stop (včetně skoku zpět).

LOOK

LOOK je vylepšenou verzí SCAN: hlava se otočí hned za posledním požadavkem v daném směru — nepokračuje zbytečně na fyzický konec disku (stopu 0 nebo 199). Tím šetří čas strávený "prázdnými jízdami" na okraje disku. V praxi se pod názvem SCAN často implementuje právě LOOK.

C-LOOK

C-LOOK kombinuje myšlenky C-SCAN a LOOK: pohybuje se vždy jedním směrem, po posledním požadavku přeskočí přímo na nejmenší číslo stopy s čekajícím požadavkem (ne na fyzický začátek disku) a opakuje. Je považován za jeden z nejlepších algoritmů pro obecné použití — kombinuje rovnoměrné čekací doby C-SCAN s efektivitou LOOK.

C-LOOK — cirkulární pohyb s inteligentním skokem: Hlava obslouží požadavky jedním směrem (65, 67, 98, 122, 124, 183), pak přeskočí přímo na nejnižší čekající požadavek (14 — ne na stopu 0!) a pokračuje nahoru (14, 37). Přerušovaná šipka = skok bez obsluhy. Výsledek: rovnoměrné čekání bez zbytečných jízd na okraje disku. Celková vzdálenost: ≈ 322 stop.

Srovnání plánovacích algoritmů

* Přibližné hodnoty pro náš ukázkový příklad. Pozn.: LOOK diagram chybí v původních materiálech — chová se jako SCAN, jen se nezajíždí na fyzický konec disku.

Solid State Drive (SSD) je zásadní technologická změna v oblasti trvalého úložiště. Namísto mechanických součástí a rotujících ploten využívá SSD flash paměťové čipy — konkrétně NAND flash. Data jsou uložena jako elektrické náboje v tranzistorech s plovoucím hradlem (floating-gate transistors). Protože v SSD nejsou žádné pohybující se součásti, celý princip přístupu k datům je zásadně odlišný od HDD.

Jak SSD ukládá data

Základní paměťová buňka NAND flash může ukládat jeden nebo více bitů. Podle počtu bitů na buňku rozlišujeme SLC (1 bit), MLC (2 bity), TLC (3 bity) a QLC (4 bity). Buňky jsou organizovány do stránek (pages, typicky 4–16 KB), stránky do bloků (blocks, typicky 256–512 stránek). Stránka je nejmenší jednotka čtení a zápisu; blok je nejmenší jednotka mazání. Firmware disku (FTL — Flash Translation Layer) tuto komplexitu skrývá před OS a prezentuje disk jako lineární pole bloků, stejně jako HDD.

Opotřebení, wear leveling, TRIM a garbage collection

NAND flash buňky mají omezený počet cyklů mazání (SLC ~100 000, TLC ~1 000 cyklů). Proto SSD firmware implementuje wear leveling — rozptyluje zápisy rovnoměrně po celém disku, aby všechny bloky stárly přibližně stejně rychle.

Příkaz TRIM informuje SSD, které LBA bloky jsou volné po smazání souboru. Firmware pak může tyto bloky vymazat předem (garbage collection), takže při příštím zápisu jsou připraveny prázdné bloky. Bez TRIMu se SSD časem zpomaluje, protože musí provádět operaci read-modify-write za běhu.

Rozhraní: SATA vs. NVMe

Původní SSD disky se připojovaly přes rozhraní SATA (max. ~600 MB/s). Moderní high-end SSD používají rozhraní NVMe (Non-Volatile Memory Express) přes sběrnici PCIe. NVMe je protokol navržený přímo pro flash paměti: podporuje tisíce front požadavků, NVMe SSD dosahují propustnosti 3 000–7 000 MB/s a latencí pod 0,1 ms.

Přehledné srovnání HDD a SSD

Kdy použít HDD a kdy SSD?

HDD dominuje tam, kde jde o velké kapacity za nízkou cenu: archivní úložiště, zálohovací systémy, NAS (síťová úložiště), video archivy. Pokud přistupujete k datům sekvenčně a nepotřebujete rychlou odezvu, HDD je ekonomicky racionální volba.

SSD je naproti tomu dominantní volbou pro všechno, kde záleží na rychlosti: operační systém, aplikace, hry, databáze, vývojářské prostředí. Latence pod 0,1 ms versus 10 ms u HDD znamená dramaticky svižnější systém — zejména při bootování, spouštění aplikací a obecné responzivitě.

Hybridní strategie — SSD jako systémový disk a HDD jako datové úložiště — je dnes nejběžnějším přístupem pro domácí uživatele a malé firmy: těží z výhod obou technologií za rozumnou celkovou cenu.