Operační paměť (RAM — Random Access Memory) je srdcem každého počítače. Bez ní by procesor neměl kde uchovávat instrukce ani data, se kterými právě pracuje.

Představte si počítač jako pracovní stůl a operační paměť jako jeho plochu. Pevný disk (nebo SSD) je jako velká skříň v kanceláři — pojme obrovské množství věcí, ale než s čímkoliv začnete pracovat, musíte to nejprve položit na stůl. Operační paměť je právě ten stůl: omezená plochou, ale zato bleskurychlá a přímo dostupná.

Technicky vzato slouží operační paměť jako dočasné úložiště pro vše, co procesor aktivně potřebuje. Nacházejí se v ní:

Kód spuštěných programů — instrukce, které procesor čte a vykonává jeden za druhým. Program nelze spustit z disku přímo; musí být nejprve nahrán do RAM. Data programů — proměnné, zásobník (stack), halda (heap), otevřené soubory. Každý program potřebuje prostor pro vlastní data. Kód a data operačního systému — jádro OS (kernel) musí být vždy přítomno v paměti, protože spravuje veškeré prostředky počítače a obsluhuje požadavky programů. Mezipaměti a vyrovnávací buffery — OS si v RAM ukládá nedávno načtené bloky z disku, aby je nemusel znovu číst.

Protože RAM je omezená a programů bývá mnohem víc, než by se do ní všechny najednou vešly, musí operační systém velmi pečlivě řídit, kdo dostane kolik paměti, kde přesně v adresním prostoru, a co se stane, když paměti začíná ubývat. Celá tato disciplína se nazývá správa paměti (memory management).

Základní problém, který musí správa paměti řešit, je izolace: každý proces musí mít pocit, že má paměť pro sebe, a nesmí číst ani zapisovat do paměti jiného procesu. Zároveň je třeba efektivita: paměť nesmí být zbytečně fragmentovaná ani plýtvaná. A konečně virtualizace: procesy by ideálně neměly vůbec vědět, kde fyzicky v RAM jejich data leží.

Jak přidělit paměť procesům? Existuje několik zásadně odlišných přístupů, z nichž každý má svá specifická silná místa i slabiny. Projdeme je od nejjednoduššího k nejsofistikovanějšímu.

Přidělování souvislé oblasti

Nejpřímočařejší přístup: každý proces dostane jeden nepřerušený kus fyzické paměti. Jako byste na pracovním stole přidělili každému kolegovi vlastní ohraničenou část plochy — nikdo nesmí překračovat svou hranici.

V tomto modelu je fyzická paměť rozdělena na dvě části: oblast pro operační systém (typicky na nízkých adresách) a oblast pro uživatelské procesy. Každý proces dostane při spuštění jeden blok paměti. Procesor obsahuje dva speciální registry: base register (bázový registr), který uchovává počáteční fyzickou adresu přiděleného bloku, a limit register (mezní registr), který říká, jak je blok velký. Při každém přístupu do paměti hardware automaticky kontroluje, zda logická adresa procesu nepřekračuje mezní hodnotu — pokud ano, vyvolá výjimku (tzv. segmentation fault).

Výhodou je absolutní jednoduchost — překlad adresy je jedna operace sčítání. Nevýhody jsou však závažné. Za prvé: jak zjistit, kam nový proces umístit? Paměť obsahuje volné díry různých velikostí a my musíme najít vhodnou. Existují tři klasické strategie výběru díry:

First Fit (první vhodná) — projdeme seznam volných bloků a vybereme první, který je dostatečně velký. Je to rychlé, ale tenduje k tomu, že velké bloky na začátku paměti se roztříštějí na malé kousky.

Best Fit (nejlepší vhodná) — vybereme nejmenší blok, který je stále dostatečně velký. Zdánlivě šetří paměť, ale ve skutečnosti vytváří spoustu malých zbytků, které nejsou použitelné pro nikoho.

Worst Fit (nejhorší vhodná) — naopak vybereme největší dostupný blok. Logika je taková, že zbývající kus bude stále dost velký pro další proces. V praxi ale funguje nejhůř.

Druhý zásadní problém je fragmentace. Jak procesy přicházejí a odcházejí, v paměti vznikají díry. I kdyby celkového volného místa bylo dost, jednotlivé díry mohou být příliš malé pro nový velký proces — tato situace se nazývá externí fragmentace. Řešením je kompaktace (defragmentace) — přesun procesů v paměti tak, aby se volné bloky sloučily. To je ale extrémně časově náročné a vyžaduje zastavení procesů.

Přidělování paměti po blocích (segmentech/sekcích)

Místo jednoho velkého bloku lze paměť přidělovat po menších, ale stále fyzicky souvislých blocích. Myšlenka je prostá: rozdělíme fyzickou RAM na bloky pevné nebo proměnné velikosti a procesy dostávají tolik bloků, kolik potřebují — nemusí být všechny pohromadě.

Přidělování po blocích je přechodem k virtualizaci paměti: proces vidí svůj logický adresní prostor jako souvislý, ale ve skutečnosti je rozložen po více fyzicky oddělených oblastech. OS si udržuje datovou strukturu (tabulku bloků), která říká: „logický blok č. 0 tohoto procesu leží na fyzické adrese XYZ".

Tento přístup výrazně snižuje externí fragmentaci — místo jedné velké díry stačí mít několik menších. Stále však existuje interní fragmentace: pokud jsou bloky pevné velikosti a proces potřebuje méně než jeden blok, zbytek se plýtvá.

Stránkování (Paging)

Stránkování je pravděpodobně nejdůležitější technika správy paměti v moderních operačních systémech. Základní idea elegantně řeší problém fragmentace: rozdělíme jak logický adresní prostor procesu, tak fyzickou paměť na bloky pevné velikosti. Bloky logického prostoru se nazývají stránky (pages), bloky fyzické paměti se nazývají rámce (frames nebo page frames). Velikost stránky a rámce je vždy stejná — typicky 4 KB, ale existují i větší (2 MB, 1 GB — tzv. huge pages).

Klíčová myšlenka: stránky nemusejí být v rámcích umístěny ve stejném pořadí, v jakém jsou v logickém prostoru. Logická stránka 0 může být ve fyzickém rámci č. 17, logická stránka 1 v rámci č. 3, atd. A rámce různých procesů mohou být libovolně promíseny v paměti — každý proces má svou vlastní tabulku stránek a vůbec neví, kde fyzicky jeho data jsou.

Překlad logické adresy na fyzickou

Logická adresa je vnitřně rozdělena na dvě části: číslo stránky (page number, značíme p) a offset (přesun v rámci stránky, značíme d). Pokud je velikost stránky 2ⁿ bajtů, pak spodních n bitů logické adresy tvoří offset a zbývající vyšší bity tvoří číslo stránky.

Kde rámec[p] je číslo fyzického rámce, které zjistíme z tabulky stránek pro daný proces. Offset d zůstává beze změny — v rámci je struktura dat stejná jako ve stránce. Překlad provádí hardware nazývaný MMU (Memory Management Unit) transparentně při každém přístupu do paměti.

Translation Lookaside Buffer (TLB)

Tabulka stránek je uložena v RAM, ale každý přístup do paměti by pak vyžadoval dva přístupy do RAM (nejprve tabulka stránek, pak vlastní data) — to by bylo katastrofálně pomalé. Proto procesory obsahují speciální rychlou asociativní cache nazývanou TLB (Translation Lookaside Buffer). TLB si pamatuje posledně použité překlady (číslo stránky → číslo rámce). Pokud v ní hledaná stránka je (TLB hit), překlad proběhne v jednom cyklu bez přístupu do RAM. Teprve při TLB miss se musí sáhnout do tabulky stránek v RAM.

Hierarchická tabulka stránek a inverzní tabulka

64bitový adresní prostor je enormní — naivní jednoduchá tabulka stránek by pro každý proces zabrala gigabajty. Proto se používají víceúrovňové tabulky stránek (dvou- nebo třístupňové). Logická adresa je rozdělena na více polí — každé pole indexuje do jedné úrovně tabulky. Části tabulky, které odpovídají nepouživaným oblastem adresního prostoru, vůbec neexistují — ušetří se tak obrovské množství paměti.

Alternativou je inverzní tabulka stránek (inverted page table): místo tabulky pro každý proces existuje jediná globální tabulka, která má jeden záznam pro každý fyzický rámec. Záznam říká, které procesu a které jeho stránce rámec patří. Je paměťově úsporná, ale vyhledávání v ní je pomalejší (musíme hashovat).

Segmentace

Zatímco stránkování rozděluje paměť na bloky pevné velikosti bez ohledu na logickou strukturu programu, segmentace vychází z toho, jak programátor přirozeně přemýšlí o programu. Program se skládá ze segmentů: kód (text), datová sekce, zásobník, halda, sdílené knihovny atd. Segmentace tyto logické celky přímo mapuje na bloky fyzické paměti.

Každý segment má své vlastní jméno (nebo číslo) a délku. Logická adresa v segmentovaném systému se skládá ze dvou částí: číslo segmentu a offset v rámci segmentu. OS udržuje pro každý proces tabulku segmentů, která říká, kde fyzicky každý segment začíná (base) a jak je velký (limit).

Hardwarová podpora segmentace

Překlad segmentových adres musí být rychlý. V procesorech architektury x86 se segmentace realizovala pomocí speciálních segmentových registrů (CS, DS, SS, ES, FS, GS). Každý registr ukazuje na deskriptor segmentu v globální nebo lokální deskriptorové tabulce (GDT/LDT). Deskriptor obsahuje bázovou adresu, limit a přístupová práva segmentu.

Segmentace se stránkováním

Nejdokonalejší přístup kombinuje výhody obou předchozích metod. Logický adresní prostor je rozdělen na segmenty (jako v čisté segmentaci), ale každý segment je dále rozdělen na stránky (jako v čistém stránkování). Fyzická paměť je rozdělena na rámce jako při stránkování — segmenty tedy nemusejí být fyzicky souvislé, čímž se eliminuje jejich fragmentace.

Logická adresa má pak tři složky: číslo segmentu, číslo stránky v rámci segmentu a offset v rámci stránky. Překlad probíhá ve dvou krocích: nejprve se segment přeloží na tabulku stránek, pak se tabulka stránek použije k nalezení fyzického rámce.

Toto schéma používal například slavný procesor Intel 80386 a celá rodina IA-32. Na moderních 64bitových systémech (x86-64) je segmentace fakticky deaktivována (všechny segmenty mají bázi 0 a celý 64bitový limit) a systém pracuje prakticky jen se stránkováním — ale konceptuálně je myšlenka segmentace se stránkováním velmi elegantní a dodnes se s ní setkáváme v různých formách.

Stránkování umožňuje fascinující trik: nemusíme mít v RAM všechny stránky procesu najednou. Stránky, které se právě nepoužívají, mohou být odloženy na disk. To dává vzniknout konceptu virtuální paměti.

Výpadek stránky (Page Fault)

Každá položka v tabulce stránek obsahuje mimo jiné příznak přítomnosti (present bit nebo valid bit). Pokud je nastaven na 1, stránka je v RAM a překlad proběhne normálně. Pokud je nastaven na 0, stránka právě není v operační paměti — je buď na disku (v odkládacím prostoru, swap), nebo ještě vůbec nebyla inicializována.

Když se procesor pokusí přistoupit ke stránce s příznakem přítomnosti = 0, nastane hardwarová výjimka zvaná výpadek stránky (page fault). Řízení přebírá obslužná rutina OS:

1. OS zjistí, zda je přístup legitimní (patří daná adresa do adresního prostoru procesu?). Pokud ne, proces dostane signál SIGSEGV a pravděpodobně selže. 2. OS najde místo na disku, kde leží data chybějící stránky. 3. OS vybere oběť — fyzický rámec, který bude uvolněn (a jehož obsah bude případně uložen na disk). 4. Data chybějící stránky se načtou z disku do uvolněného rámce. 5. Tabulka stránek se aktualizuje — příznak přítomnosti se nastaví na 1 a zaznamená se číslo nového fyzického rámce. 6. Instrukce, která způsobila výpadek, se restartuje — tentokrát už proběhne normálně.

Pre-cleaning

Když nastane výpadek stránky a OS potřebuje uvolnit rámec, musí nejprve zapsat jeho obsah na disk (pokud byl modifikován). Tato operace je časově nákladná. Pre-cleaning je technika, kdy OS preventivně zapisuje modifikované stránky na disk dříve, než jsou reálně potřeba — v době, kdy je systém méně vytížený. Tím se při samotném výpadku stránky ušetří čas čekání na zápis.

OS si vede seznam stránek, které jsou "špinavé" (dirty — byly modifikovány od posledního načtení z disku). Pozadíový démon (page daemon) tyto stránky průběžně zapisuje na disk a označuje je jako "čisté" (clean). Uvolnění čisté stránky je pak okamžité — nemusí se čekat na zápis.

Thrashing

Thrashing (česky někdy "přehazování" nebo "mlácení") je vážný stav, kdy systém tráví více času obsluhou výpadků stránek než skutečnou prací procesů. Stane se to, když je v RAM příliš mnoho procesů a každý proces dostane méně rámců, než potřebuje pro svůj pracovní set (working set — stránky, ke kterým proces pravidelně přistupuje).

V takovém stavu každý proces neustále způsobuje výpadky stránek. OS neustále načítá stránky, ale hned je musí zase vyhodit pro jiný proces. Procesory stráví 99 % času čekáním na disk. Celý systém se zdánlivě "zamrzne".

Při výběru oběti (stránky k vyhnání z RAM) je zásadní, zda stránka byla od svého načtení modifikována či nikoliv. Tato informace se sleduje pomocí jednoho bitu v tabulce stránek.

Každý záznam v tabulce stránek obsahuje tzv. dirty bit (bit modifikace, bit zápisu). Pokud proces do stránky zapsal (i jen jeden bajt), hardware automaticky nastaví dirty bit na 1. Stránka se tím stane špinavou (dirty page).

Čistá stránka (clean page)

Čistá stránka je taková, jejíž obsah v RAM je identický s obsahem na disku (ve swapu nebo v souboru). Pokud takovou stránku potřebujeme uvolnit, jednoduše ji zahodíme — data máme stále na disku, odkud je lze znovu načíst. Uvolnění čisté stránky je okamžité a bezbolestné.

Špinavá stránka (dirty page)

Špinavá stránka obsahuje data, která ještě nebyla zapsána na disk. Pokud bychom ji jednoduše zahodili, přišli bychom o změny. Proto ji musíme nejprve zapsat na disk (swap-out) a teprve pak uvolnit rámec. Tato operace trvá podstatně déle než zahození čisté stránky.

Zajímavý případ jsou stránky obsahující spustitelný kód (text segment). Tyto stránky jsou zpravidla vždy čisté — kód se nemění. Navíc je lze uvolnit a znovu načíst přímo ze spustitelného souboru na disku, takže ani nepotřebují swap prostor. Proto na paměťově omezených systémech OS rád obětuje stránky kódu — jsou nejsnáze obnovitelné.

Algoritmus výměny stránek rozhoduje: když potřebujeme uvolnit rámec, která stránka bude obětována? Špatná volba znamená, že vyhozenou stránku okamžitě zase budeme potřebovat — a nastane další výpadek. Cílem je minimalizovat celkový počet výpadků stránek.

Pro porovnání algoritmů se používá standardní metrika: celkový počet výpadků stránek při zpracování referenčního řetězce přístupů a daném počtu dostupných rámců. Referenční řetězec je sekvence čísel stránek, ke kterým proces přistupuje v čase.

Optimální algoritmus (OPT / Bélády)

Optimální algoritmus je teoretickým maximem — vždy vyhodí tu stránku, která bude nejdéle nepoužita v budoucnosti. Je to jako mít křišťálovou kouli: víme dopředu, jaké stránky bude program žádat, a vždy se zbavíme té, která přijde na řadu nejpozději.

Výsledek je vždy nejmenší možný počet výpadků — jde o dolní mez, vůči které měříme ostatní algoritmy. Nevýhoda je fatální: v praxi je nerealizovatelný, protože OS nemá věštecké schopnosti — nezná budoucí přístupový vzor procesu. Používá se výhradně jako referenční bod pro porovnání.

FIFO (First In, First Out)

FIFO je nejjednodušší reálný algoritmus. Princip je přímočarý: vyhodíme tu stránku, která je v paměti nejdéle — bez ohledu na to, jak často se používá. Stránky jsou uspořádány do fronty; nejstarší stránka (hlava fronty) se vyhazuje, nová stránka se přidává na konec.

Implementace je triviální — stačí cyklická fronta. Nevýhoda: stránka může být v paměti nejdéle, ale přitom být stále velmi aktivně používána (třeba inicializační rutina nebo frekventovaně volaná funkce). V takovém případě FIFO zbytečně vyhazuje užitečnou stránku.

FIFO trpí slavným Béládyho anomálií: s více rámci může nastat více výpadků stránek. To je neintuitivní — více paměti by mělo pomoci, ale FIFO to zaručit nedokáže.

LRU (Least Recently Used)

LRU vychází z principu lokality: co bylo nedávno použito, bude pravděpodobně použito znovu brzy. Naopak co nebylo použito dlouho, pravděpodobně nebude potřeba ani v blízké budoucnosti. LRU proto vyhazuje stránku, která nebyla nejdelší dobu použita.

LRU je přibližnou implementací optimálního algoritmu s pohledem do minulosti místo do budoucnosti. V praxi funguje velmi dobře — minulé chování je dobrým prediktorem budoucnosti (princip lokality přístupů). Bohužel přesná implementace LRU je nákladná: při každém přístupu do paměti musíme zaznamenat čas přístupu a při výběru oběti projít všechny rámce a najít nejstarší. To je prakticky nereálné v hardware.

Proto se používají aproximace LRU — nejčastěji pomocí reference bitu (use bitu): hardware nastaví tento bit na 1, kdykoli se stránka použije. OS perioidicky bity nuluje a sleduje, které stránky mezi nulovacími intervaly nebyly použity (bit zůstal 0) — ty jsou kandidáty na vyhazení. Tento přístup je základem algoritmů Druhá šance a Hodiny.

Druhá šance (Clock s bitem R)

Algoritmus Druhá šance je FIFO vylepšené o referenční bit (R bit). Místo slepého vyhazování nejstarší stránky dáme každé stránce "druhou šanci": pokud má R = 1 (byla nedávno použita), nulujeme R a přesuneme ji na konec fronty — jako by právě přišla do paměti. Pokud má R = 0, vyhodíme ji.

Výsledkem je, že aktivně používané stránky (R = 1) dostávají stále nové šance a zůstávají v paměti, zatímco nepoužívané stránky (R = 0) jsou odstraněny i přesto, že jsou třeba "staré" jen o málo.

Algoritmus Hodiny (Clock)

Hodiny jsou efektivní implementací algoritmu Druhá šance. Místo fronty se používá cyklický seznam (jako ciferník hodin) a jeden ukazatel ("ručička"). Ručička postupuje po ciferníku:

Pokud stránka, na kterou ukazuje ručička, má R = 1, nastavíme R = 0 a posuneme ručičku dál. Pokud má R = 0, tuto stránku vyhodíme a na její místo dáme novou stránku, pak ručičku posuneme. V nejhorším případě ručička oběhne celý kruh a vyhodí stránku, která má R = 0 po jednom průchodu (= nepoužila se od posledního průchodu ručičky).

Algoritmus Hodiny je velmi praktický: je efektivní, jednoduchá implementace, a dobře aproximuje LRU. Používá se (nebo se používaly varianty) v mnoha reálných OS, včetně starších verzí Linuxu a BSD.

NUR / NRU (Not Recently Used / Not Used Recently)

NUR (nebo NRU — záleží na zdroji, jde o tentýž koncept) rozšiřuje sledování o dva bity: referenční bit R (byl přistoupen) a modifikační bit M (byl modifikován, dirty bit). Kombinací těchto bitů vznikají čtyři třídy stránek:

OS vybere jako oběť stránku z nejnižší neprázdné třídy. Bity R se periodicky nulují (každý časový interval), aby se zachytil aktuální vzor přístupů. Algoritmus je jednoduchý, nenákladný a dobře aproximuje LRU s bonusem rozlišení čistých a špinavých stránek.

Náhodný výběr (Random)

Algoritmus Random je přesně tak prostý, jak název napovídá: oběť se vybere náhodně z dostupných rámců. Nesleduje žádné přístupové vzory, nepoužívá žádné bity.

Výhodou je absolutní jednoduchost a nulová režie. Překvapivě není špatný ve srovnání s FIFO, protože alespoň netrpí Béládyho anomálií a v průměrném případě nevybírá systematicky špatně. Hlavní nevýhoda je nepředvídatelnost — v nejhorším případě vždy vyhazuje stránky, které budou okamžitě potřeba. Používá se v systémech s velmi omezenými prostředky nebo jako záložní mechanismus.

NFU (Not Frequently Used)

NFU sleduje celkový počet použití každé stránky od chvíle, kdy přišla do paměti. Každý časový interval OS projde všechny stránky, přičte referenční bit R k čítači dané stránky (a R vynuluje). Vyhazuje se stránka s nejmenším čítačem.

Myšlenka je, že stránka s malým čítačem se za svůj pobyt v paměti moc nepoužívala. Problém: NFU zapomínat neumí. Stránka, která se v minulosti hodně používala, ale nyní je nečinná, má stále vysoký čítač a nebude vyhazována — i když ji program nepotřebuje. Naopak nová stránka, která je nyní aktivně využívána, má čítač blízký nule a může být předčasně vyhozena.

Řešením je varianta NFU se stárnutím (aging): před přičtením R bitu se čítač posune doprava o jeden bit (dělení dvěma). Starší přístupy tak mají stále menší vliv — čítač "stárne". Tato varianta výborně aproximuje LRU a je efektivně implementovatelná.

Operace posunutí doprava (>>) dělí čítač dvěma — starší přístupy mají exponenciálně klesající vliv. Přičtení R_bitu na nejvyšší pozici zaznamenává aktuální referenci. Výsledkem je "klouzavý průměr" s exponenciálním zapomínáním.

Souhrnné srovnání algoritmů výměny stránek