Stránkování paměti

Stránkování paměti je v informatice metoda správy virtuální paměti, kdy strojové instrukce procesu pracují s logickými adresami, které jednotka MMU (typicky součást procesoru) převádí na fyzické adresy (skutečné umístění v paměti RAM). Vzniká tak virtuální adresní prostor, který pro každý proces začíná od nuly, takže odpadá potřeba relokace použitého strojového kódu. Při převodu je adresní prostor rozdělen na stránky (rámce) stejné velikosti (typicky 4 KiB, nověji též 16 nebo 64 KiB u 64bitového ARMv8). Stránkování paměti je používáno všemi současnými běžnými operačními systémy (Linux, Windows NT, FreeBSD, Solaris atd.) a je základem pro stránkování na disk.

Terminologie

Historicky se jako stránkování označoval mechanizmus přidělování paměti, který používal stránky o fixní velikosti, na rozdíl od segmentů s proměnnou délkou. Nejstarší implementace nevyužívaly techniky virtuální paměti, ani to, že by byly tyto stránky přesuvány na disk. Takové použití je však dnes vzácností.

Zároveň některé operační systémy (UNIX) používaly takzvanou techniku swapování (swapping). Tato technika prováděla přesun celého spícího procesu z operační paměti do sekundárního úložiště a obráceně, jinak též známé jako návrh roll-in/roll-out. V 60. letech 20. století po představení konceptu virtuální (logické) paměti (ve dvou variantách: segmentace nebo právě stránkování) bylo pro odkládání aktuálně nepoužívaných dat lepší použít menší granularitu než celý proces a pojem swapping byl aplikován na přesun segmentů nebo stránek mezi diskem a pamětí. Dnes je virtuální paměť založena téměř výhradně na stránkách, segmentace se používá spíše výjimečně, a stránkování na externí médium se tak stalo synonymem swapování.

Taktéž na systémech založených na bázi Windows NT je vyhrazený swapovací (odkládací) prostor označován jako stránkovací soubor.

Na druhou stranu v procesorech architektury x86 byla původně implementována segmentace a až později byla přidána podpora stránkování. Díky tomu se u nich rozlišují tři adresové prostory - virtuální (složený ze segmentového selektoru a offsetu v segmentu), ten se přeloží podle bázové adresy příslušného segmentu na takzvanou lineární adresu, která je pak pomocí algoritmu stránkování transformována na fyzickou adresu. Dnes již je segmentace na ústupu a rozdíl mezi virtuálním a lineárním prostorem se stírá, ale pro specifické operace (lokální adresový prostor vláken) se segmentace stále používá.

Popis stránkování

Stránkování

Ve víceúlohovém systému, který využívá multitasking, je nutné umístit do paměti více procesů najednou. Pokud jsou k dispozici nástroje na virtualizaci paměti, lze vytvořit každému z procesů jeho vlastní virtuální adresní prostor, který bude začínat od adresy nula. Každý proces (resp. jeho strojové instrukce) pak bude pracovat s logickými adresami, které jsou při přístupu do paměti RAM automaticky převáděny jednotkou MMU na fyzické adresy. MMU je dnes typicky umístěna v procesoru, ale může být i nezávislým obvodem.

Aby nebylo nutné pro převod logických adres na fyzické udržovat velké množství informací, je adresní prostor rozdělen na stránky stejné velikosti (typicky 4 KiB, ale i 8 KiB nebo větší) a udržují se jen data mapování pro ně. Virtuální adresní prostor je tedy složen ze stránek, které odpovídají stejně velkým oblastem ve fyzické paměti RAM. Zatímco logické stránky vytvářejí souvislý lineární adresní prostor, umístění fyzických stránek je díky převodu zcela nahodilé. Pro běžící proces se tak vytváří iluze, že jeho adresní prostor v operační paměti je souvislý, zatímco ve skutečnosti jsou fyzické stránky fragmentovány. Fragmentace je však procesu (resp. jeho strojovým instrukcím) skryta a není ji nutné nijak řešit (na rozdíl od segmentace paměti , kde je nutné fragmentaci odstraňovat přesunem segmentů).

Podrobnější popis jednotlivých stránkovacích algoritmů naleznete v článku Stránkovací algoritmy.

Překlad adresy

Překlad adres vychází z představy rozdělení virtuálního adresového prostoru na stránky o dobře definované velikosti. Velikost stránek se může lišit na základě použité architektury, na druhou stranu však některé architektury podporují stránky rozdílných velikostí a to často dokonce souběžně. Typicky je ovšem v řádu kilobytů. U 32bitových procesorů Intel x86 je logická adresa 32bitová a velikost stránky je obvykle 4kiB. Fyzický paměťový prostor je dělen na souvislé oblasti stejné velikosti, jako mají logické stránky. Tyto oblasti jsou nazývány jako stránkové rámce. Mezi logickými stránkami a rámci je vytvořeno zobrazení. Toto zobrazení obvykle není úplné, jelikož běžný proces nespotřebuje celý svůj logický prostor. Proto existují logické stránky bez přiřazeného rámce, tzv. neplatné stránky. Mohou existovat i rámce, které nejsou mapovány na žádnou logickou stránku, nebo rámce, na které je mapováno více logických stránek (například sdílená paměť mezi procesy, ať už data nebo sdílený kód).

Tabulka stránek

Tabulka stránek je jednou z reálných implementací překladu adresy. Předpokládá lineární logický adresový prostor. Logická adresa se dělí na dvě části. Vyšší bity se považují za číslo samotné logické stránky (právě díky lineárnímu adresování pořadí stránky v adres. prostoru) a nižší bity jsou offsetem paměťového místa v dané stránce. Pro samotný překlad pomocí tabulky stránek se použijí jen vyšší bity, které zde slouží jako index (obvykle složený) do struktury stránkovacích tabulek. Výsledkem vyhledávání v této tabulce jsou čísla rámců a jejich příznaky, které jsou důležité například pro ochranu paměti před neoprávněným přístupem. Získané číslo rámce fyzické stránky je převedeno na adresu počátku rámce ve fyzické paměti bitovým posunutím vlevo. Nakonec je k bázové adrese přičten (bitovým OR) offset požadovaného místa (nižší bity virtuální adresy). Tabulka stránek může být implementována přímo v hardware, ale může to být také doplňkový algoritmus implementovaný operačním systémem, pokud hardware používá mechanizmus, který není schopen udržet celý popis virtuálního prostoru. Jedná se o komplexní, ale díky nutnosti mnoha přístupů k RAM pomalé řešení.

TLB

TLB je jiným přístupem k implementaci stránkování, kdy několik (řádově desítky) mapování logická stránka <-> fyzický rámec je uloženo ve velmi rychlé asociativní paměti přímo v MMU procesoru. Logická adresa je, podobně jako u stránkovacích tabulek, rozdělena na vyšší a nižší část, kdy vyšší je indexem do TLB, kde je hledána adresa začátku rámce, a nižší je použita jako offset v rámci. Některé architektury používají toto řešení stránkování ve své čisté podobě a pokud není mapování v TLB nalezeno, dojde u nich okamžitě k výpadku stránky.

Protože však k překladu dochází velmi často a pokud je tabulka stránek uložena v paměti RAM, která je v porovnání s rychlostí procesoru relativně pomalá, tak i moderní architektury (x86) doplňují běžné stránkovací tabulky TLB jako výraznou akceleraci.

Související informace naleznete také v článku Translation Lookaside Buffer.

Inverzní stránkovací tabulka

Inverzní stránkovací tabulka je technika, která je jakýmsi kompromisem mezi předchozíma dvěma přístupy. Jedná se totiž též o asociativní paměť, která je však implementována v klasické (levnější) RAM paměti. To je zajištěno pomocí hashování. Pokud je nutno přistoupit k adrese, je opět rozdělena na číslo stránky a offset. Adresa stránky je zpracována jednoduchou hashovací funkcí, která ji zobrazí do číselného prostoru s výrazně menší velikostí, než je prostor adres. V RAM paměti existuje tabulka mapování, která počtem záznamů přesně odpovídá prostoru funkčních hodnot hashovací funkce a výsledek této funkce se použije jako index do ní. Protože takováto hashovací funkce ze své podstaty nemůže být bijekcí, je nutné v záznamu ověřit, jestli je nalezené mapování správné. Pokud ano, je ze záznamu vyzískán prefix fyzické adresy rámce, posunut a přičten k němu offset. Pokud ne, jedná se o výpadek stránky.

Samotná implementace tabulky může podporovat kolize, kdy jsou rámce se stejným výsledkem hashovací funkce vzájemně propojeny odkazy. V tomto případě však musí být všechny členy seznamu v paměti přístupné příslušné komponentě provádějící stránkování. Druhým přístupem je v případě kolize odstranit staré mapování a nahradit jej novým. Kernel si však musí v jiné struktuře držet úplný popis virtuální paměti aktuálního procesu.

Opět se jedná o mechanizmus, který může být implementován hardwarem, ale i čistě softwarově pouze pro účely kernelu.

Výpadek stránky

Výpadek nastává, když se procesor snaží přistoupit k neplatné stránce (stránce bez namapovaného fyzického rámce). Výpadek stránky je implementován jako interní přerušení od MMU (Memory management unit). Je vyvolána synchronní výjimka, která je zpracována příslušným handlerem jádra OS. Pokud OS nalezne odpovídající stránku na disku, najde volný/uvolní (jiný) fyzický rámec v paměti RAM, načte do něj potřebná data a propojí jej s logickou stránkou. Stránce opraví příznaky platnosti tak, aby při novém přístupu již nedošlo k jejímu výpadku a obnoví vykonávání vlákna, které přerušení vyvolalo, těsně před příslušnou instrukcí. Pokud odpovídající stránku nenalezne, doručí procesu signál nebo obdobnou zprávu, na kterou proces provede nejčastěji své ukončení, případně samotný OS okamžitě ukončí tento proces.

Správa tabulky stránek

Stránkování paměti se díky možnosti oddělení virtuálních adresových prostorů využívá pro usnadnění multitaskingu, kdy je spuštěno zároveň více procesů (ať již se v běhu střídají nebo běží skutečně paralelně). Protože každý proces má přidělen vlastní oddělený virtuální adresní prostor, běžně má také vlastní tabulku stránek. Údaje o umístění tabulky stránek jsou součástí vlastností každého procesu a jsou uloženy v části paměti přístupné pouze jádru systému, obvykle v takzvaném PCB (anglicky Process control block).

Víceúrovňové tabulky stránek

Protože obvykle není virtuální adresní prostor procesu celý využitý, je část pozic v tabulce stránek neplatných. Na již zmíněné architektuře IA-32 by každý proces musel vlastnit tabulku až o velikosti 4 MiB (4 GiB, stránka po 4 KiB = 1Mi záznamů, každý po 4 bytech (32 bitů) => 4MiB prostoru). Z tohoto důvodu jsou tabulky stránek uspořádány do víceúrovňové stromové struktury (obvykle 2 nebo 3 úrovně) a tím není nutné souvislá neobsazená místa adresního prostoru vůbec tabulkami stránek popisovat a není třeba alokovat tolik dat.

Stránkování na disk

Výše popsaný algoritmus umožňuje poměrně levné "rozšíření" paměti RAM. A to díky faktu, že programy v jednom okamžiku zpracovávají data pouze z velmi omezeného počtu míst. To znamená, že je potřeba držet namapovaných jen několik stránek pro jeden proces. Ostatní se mohou odložit do vnější paměti (obvykle na pevný disk). Tím je možné uvolnit operační paměť RAM a umožnit tak její zdánlivé zvětšení pouze za cenu kapacity pevného disku, která je výrazně nižší.

Pokud je stránka odložena na externí médium, je nutné tuto skutečnost sdělit hardwaru. To se obvykle provede nastavením bitu signalizujícího její nepřítomnost ve stránkovacích strukturách a musí být samozřejmě případně odstraněn příslušný záznam z TLB. Pokud se jedná o víceprocesorový systém je nezbytné o nutnosti vyčištění TLB říci i ostatním procesorům. To se provádí vyvoláním příslušné výjimky na každém z nich (obvykle broadcastem specifické zprávy) a čekáním na odpověď od každého z nich. To může na rozsáhlých systémech v konečném efektu způsobit více či méně výraznou výkonovou degradaci. Nakonec také jádro operačního systému musí do svých interních struktur poznamenat, kam byl obsah odložené stránky uložen.

Proces se nechá dále běžet a pokud pak systém při provádění vlastního stránkovacího algoritmu narazí na nenamapovaný záznam, je zavolána rutina, která podle vnitřních struktur OS rozhodne, o jaký typ výpadku se jedná. Najde požadovaná data ve vnější paměti a volný rámec, tato data do něj načte a příslušné vlákno je restartováno od instrukce, která výpadek stránky způsobila, takže přerušený proces nic nepozná (až na větší prodlevu při zpracování této strojové instrukce) a normálně pokračuje dále.

Pro vybrání oběti, která má být odložena na disk se používají různé algoritmy, které však jsou prakticky vždy suboptimální a mnohdy jsou omezeny hardwarovou implementací.

Související informace naleznete také v článku Virtuální paměť.

Pomocné algoritmy používané při stránkování

Existují různé algoritmy používané při stránkování, některé z nich se věnují správě volných rámců fyzické paměti, například kradení stránek nebo předčišťování paměti. Protože kromě předem dobře známých oblastí paměti, využívají procesy také dynamicky alokované paměťové struktury (heap, zásobníky), je nutné řešit vztah mezi jejich logickou alokací (například voláním mmap, brk, vytvořením vlákna,...) a skutečným přístupem k dané paměti. To je možné řešit buď stránkováním na žádost anebo pesimistickým algoritmem prealokace.

Kradení stránek

Některé operační systémy periodicky hledají stránky, které nebyly nedávno použity, pokud takováto stránka byla od posledního načtení modifikována, uloží její kopii na swapovací médium, odmapuje ji z virtuálního adresového prostoru příslušného procesu, z bezpečnostních důvodů ji vynuluje a prohlásí za volnou.

Předčištění paměti

Unixové operační systémy periodicky využívají sync k synchronizování použitých stránek se swapem, tzn. systém průběžně ukládá modifikované stránky na pevný disk. Operační systém Windows používá stejnou operaci běžící ve vláknech systémového procesu zvaného zapisovač modifikovaných stránek. Pro tuto vlastnost je však nutná hardwarová podpora, jejíž pomocí je možné ověřit, zda stránka byla/nebyla od poslední synchronizace (načtení) modifikována.

Předčišťování urychluje start nového programu nebo otevření datového souboru. To díky tomu, že si operační systém drží seznam stránek, které byly nedávno uloženy a je tedy vysoká pravděpodobnost, že jsou synchronní se svým obrazem na médiu. Po ověření jejich nemodifikovanosti je možné odpovídající rámec bez nutnosti jeho opětovného zápisu odstranit z mapování virtuálního adresového prostoru příslušného procesu, vynulovat a použít jako volný. Tím odpadá nutnost provádět jeho synchronizaci v potenciálně kritickém okamžiku, kdy bude pravděpodobně vyžadováno mnoho podobných oprací a zápis na swapovací médium by musel synchronně předcházet načtení dat do příslušné stránky.

Stránkování na žádost

Při použití stránkování na žádost je stránka paměti nahrána až v případě požadavku, nikoliv předtím. Program obvykle začíná svoji činnost jako nezávislá entita nebo v případě forku sdílí všechny fyzické rámce se svým otcovským procesem. V prvním případě začíná proces běžet jen s minimální sadou stránek podložených fyzickými rámci v paměti a postupně, jak přistupuje k dalším a dalším platným virtuálním adresám, dochází k výpadkům stránek a operační systém pro ně v rámci obsluhy výjimek vytváří mapování a nahrává do nich požadovaný obsah, ať už jde o kód programu, jeho data nebo paměťově mapované soubory.

Obdobně v případě žádosti o další prostor ve virtuální paměti operační systém toto místo přidělí, vytvoří příslušné záznamy ve stránkovacích strukturách, ale označí je jako neplatné a fyzickou paměť jim přidělí až při fyzickém přístupu k nim.

Obdobně případě forku začíná synovský proces běžet ve virtuální paměti, která je celá sdílená s otcovským procesem, ale je změněno mapovaní obou virtuálních prostorů (pro jednoduchost uvažujme jen dva, avšak algoritmus je analogický pro více) pouze pro čtení. Až v okamžiku, kdy se jeden z této dvojice procesů pokusí změnit některou svoji stránku mapovanou pouze pro čtení, dojde k výjimce a příslušná obslužná rutina operačního systému najde volný fyzický rámec, do něj zkopíruje data z dané stránky, namapuje jej na příslušnou virtuální adresu. Tentokráte však již s příznaky umožňující zápis a naplánuje vlákno, které výjimku vyvolalo, na příslušné instrukci. A obdobně je možné přemapovat pro zápis stránku i v druhém procesu, pokud již není sdílena voláním forku s jiným procesem.

Tento algoritmus benefituje především z předpokladu, že procesy mnohdy požadují rozsáhlé paměťové oblasti, ale ve skutečnosti z nich použijí jen relativně malé množství stránek. Navíc všechny procesy obvykle nepřistupují k paměti okamžitě po jejím naalokování a tak existuje pravděpodobnost, že některé procesy dokončí svoji práci dříve, než systému dojde fyzická paměť. Toto schéma však selže v okamžiku, kdy systém přidělí procesům více virtuální paměti, než umožňují jeho zdroje (množství RAM + velikost swapu) a tyto procesy pak vyčerpají všechnu dostupnou paměť a některý z nich se pokusí přistoupit na stránku, pro kterou již není možné naalokovat hardwarový zdroj. Tomuto stavu se také říká memory overcommit. V tuto chvíli existují dvě možné varianty chování. Buď dotčený proces uspat a počkat, než se nějaká fyzická paměť uvolní, ale existuje zde vysoké riziko, že takto bude odplánováno více procesů, čímž dojde k nepredikovatelnému chování celého systému. Anebo najít vhodný proces, ten ukončit a jeho paměť přidělit žadateli. Což je také sporné řešení, protože zabíjený proces může být ukončen v potenciálně kritickém okamžiku aniž by udělal cokoli špatně.

Prealokace

Některé systémy předpokládají, že pokud si proces požádá o paměť, bude ji skutečně potřebovat. Proto v okamžiku, kdy jádro operačního systému zjistí, že proces žádá o zvětšení virtuálního prostoru, projde své volné zdroje a potřebné fyzické rámce nebo swapovací bloky předrezervuje. Tento algoritmus má zásadní výhodu v tom, že proces nikdy nebude násilně ukončen kvůli chybnému chování jiného. Naopak, pokud jeho alokace selže, může zvolit jiný, méně paměťově náročný, algoritmus, nebo korektně uložit svá data a ukončit se. Případně, pokud není nutnost jeho okamžitého běhu, může alokovat virtuální stránky tak, že se toto systémové volání uspí, dokud nebude dostupné potřebné množství zdrojů. Dále, pokud se proces chová korektně a skutečně využije (téměř) všechnu virtuální paměť, se celkové zpomalení nemusí lišit od předchozího případu (zdroje budou dříve a nebo později stejně naalokovány). Na druhou stranu je v tomto případě nutné, aby paměťový subsystém kernelu byl skutečně dobře implementován a byl efektivní jak pro malé alokace, tak pro skutečně rozsáhlé. Další nevýhodu mohou způsobit procesy, které si vytvoří velké virtuální prostory, ale ve skutečnosti je nevyužijí.

Výhody a nevýhody stránkování

Největší výhodou stránkování je omezení fragmentace volné paměti. Mezi nevýhody stránkování patří nutnost hardwarové podpory procesorem, zpomalení systému kvůli nutnosti režijních výpočtů a problémy s alokací většího souvislého úseku fyzické paměti kvůli zařízením, která neumí pracovat s virtuálními adresami (např. řadič DMA). Na druhou stranu klasický DMA řadič se již ve velkých moderních systémech (x86, SPARC, obecně se sběrnicí PCI a novější) nepoužívá a místo něj si přístup do paměti ovládají samotné řídící obvody periferií připojených na sběrnice. A aby mohly jednoduše a bez vyvolání výjimky přistupovat do hlavní paměti přes hranici rámců, je v posledních letech v těchto systémech implementován speciální subsystém nazývaný IOMMU, který má za úkol virtualizovat paměť pro periferie podobným způsobem jako MMU v procesoru.

Ochrana paměti

Ochrana paměti je u stránkování zajišťována různými metodami. Záleží na tom, jestli je potřeba zajistit ochranu v rámci jednoho procesu nebo navzájem mezi procesy. V rámci jednoho procesu se může jednat například o ochranu kódu programu před přepisem nebo obsahu zásobníku před vykonáním. To je zajištěno nastavením určitých bitů ve stránkovacích strukturách. V případě, že je stránkovací mechanismus sdílen mezi jednotlivými adresními prostory (typicky TLB, inverzní stránkování), je použita metoda zámků a klíčů. Každá namapovaná stránka paměti má přiřazen zámek (číslo) a v procesoru je speciální registr (klíč, na některých architekturách tzv. ASID - Address Space ID). Přístup do paměti jednotka MMU dovolí pouze v případě, že se klíč (registr procesoru) shoduje se zámkem. Někdy existuje univerzální klíč (např. s hodnotou nula), který umožňuje přístup k libovolné stránce v paměti a který používá jádro operačního systému. Změna hodnot ovlivňujících ochranu stránek vyžaduje privilegovaný režim, takže ji může provést pouze jádro operačního systému. Pokusí-li se proces běžící v neprivilegovaném režimu provést modifikaci klíče v registru, vyvolá procesor vnitřní přerušení. Tím dojde ke spuštění příslušné obsluhy. Ta je typicky uvnitř jádra operačního systému, které tak okamžitě může chybný proces ukončit.

Implementace odkládání na disk z hlediska operačního systému

Windows 3.x a Windows 9x

Virtuální paměť byla rysem Microsoft Windows od dob Windows 3.0 v roce 1990. Společnost Microsoft představila virtuální paměť v reakci na selhávání systémů Windows 1.0 a Windows 2.0. Požadavkem bylo redukovat potřebné požadavky na systém pro nový operační systém. Tento krok, odkazovat na odkládací soubor jako "virtuální paměť", způsobil zmatky. Nováčci neznalí tohoto konceptu jej přijali bez otázek a mluvili o přizpůsobení virtuální paměti systémem Windows. Ve skutečnosti má každý proces fixní, nezměnitelnou velikost virtuální paměti, obvykle 2 GB. Uživatel má pouze možnost měnit velikost diskového prostoru vyhrazeného pro stránkování.

Windows 3.x vytváří skrytý soubor pojmenován jako 386SPART.PAR nebo WIN386.SWP využívaný jako odkládací soubor. Nalézá se v kořenu disku, ale může se vyskytnout kdekoliv (typicky ve složce WINDOWS). Jeho velikost závisí na nastavení v systému (Ovládací panely → rozšířené a položka Virtuální paměť). Pokud uživatel tento soubor přesune nebo smaže, objeví se Modrá obrazovka smrti při příštím startu systému společně s chybovou hláškou "Trvalý odkládací soubor je poškozen". Uživatel bude vyzván k výběru, zda chce či nechce soubor vymazat (nehledě na to, zda existuje či ne).

Windows NT

Ve verzích Windows založených na NT (jako jsou Windows XP, Windows Vista, a Windows 7), soubor který se používá pro stránkování se nazývá pagefile.sys. Základní umístění souboru pro stránkování je v kořenovém adresáři oddílu, kde je nainstalován systém Windows. Systém Windows muže být nastaven pro použití volného místa na disku pro stránkovací soubory. Každý spouštěcí oddíl (např. jednotka obsahující adresář Windows) musí mít svůj stránkovací soubor, pokud je systém nastaven k výpisu paměti jádra nebo plného výpisu paměti po ukončení kernelu z důvodu chyby. Windows používají stránkovací soubor jako dočasné úložiště pro výpis paměti. Po restartu systém Windows zkopíruje výpis paměti ze stránkovacího souboru do odděleného souboru a tím uvolní místo použité ve stránkovacím souboru.

Fragmentace

V základním nastavení Windows je stránkovacímu souboru umožněna expanze za jeho počáteční velikost, pokud je potřeba. Pokud se toto děje opakovaně, stává se silně fragmentovaný, což může způsobit degradaci výkonu. Doporučuje se uzamknout velikost stránkovacího souboru, aby ji systém Windows nemohl zvětšovat. Nicméně stránkovací soubor expanduje pokud je zaplněn, tzn. v jeho základní konfiguraci velikost 150 % celkové fyzické paměti. Tudíž celkový požadavek pro virtuální paměť využívající zpětné čtení ze stránkovacího souboru musí překročit 250 % velikosti fyzické paměti počítače před expanzí stránkovacího souboru.

Fragmentace stránkovacího souboru po expanzi je dočasná. Jakmile dříve expandované regiony přestanou být používány (po restartovaní, nikoli dříve) je opět diskový prostor uvolněn a stránkovací soubor je vrácen zpět do své původní velikosti.

Uzamknutí velikosti stránkovacího souboru může býti problematické, pokud aplikace spuštěná pod Windows požaduje více paměti než je celková velikost fyzické paměti a stránkovacího souboru. V tomto případě požadavek na alokování paměti skončí chybou, která může způsobit pád aplikace nebo systému. Zastánci tohoto názoru mohou namítnout, že stránkovací soubor je ojediněle čten nebo je do něj zapisováno v sekvenčním pořadí, takže výhoda mít kompletně sekvenční stránkovací soubor je minimální. Ačkoli je obecně známo, že velké stránkovací soubory umožní použití aplikací s velkými nároky na použitou paměť, jediná nevýhoda je poté velikost zabraného místa na disku.

Využití více místa na disku k tomuto účelu může být zanedbatelné. Například systém s 3 GB operační paměti a 6 GB místa pro swap oddíl na disku o velikosti 750GB nebo systém se 6GB operační paměti a 2TB diskem, v obou případech využití paměti je 8/10 z 1% celkového místa na disku rozšířeným swap oddílem.

Defragmentace stránkovacího souboru je doporučena pro zvýšení výkonu pokud systém Windows používá často mnohem více paměti než je jeho fyzická paměť. Toto ovšem ignoruje fakt, že stránkovací soubor se časem nestává fragmentovaný. Obecně platí, že obavu ze snížení výkonu je možno efektivně řešit přidáním fyzické paměti.

Unixové systémy

V systémech, které jsou nazývány jako unixové (Linux, FreeBSD, Solaris...) je obvykle pro odkládání vyčleněn speciální diskový oddíl. Tento oddíl je díky tomu, že leží mimo jakékoli uživatelsky přístupné oblasti disku, dobře chráněn před případnou modifikací. Dále odpadá výše popsaná fragmentace stránkovacího souboru. Navíc je takto možné snadno vyčlenit (pořídít) velmi rychlé, ale jinak poměrně drahé zařízení. Některé systémy (například Solaris) navíc umožňují provozovat swap na více médiích, které jsou provozovány v redundantním uspořádání, což významně zvyšuje spolehlivost této technologie. Na druhou stranu je obtížnější měnit velikost odkládacího prostoru díky méně flexibilní správě velikosti. A také, protože si operační systém musí držet tabulky popisující stav swapovacího prostoru, je v některých případech velmi složité správné určení jeho velikosti, aby měl systém optimální výkon.

Hardwarová implementace

Způsob implementace stránkování paměti je jedním ze zásadních rozdílů jednotlivých hardwarových architektur. Pro srovnání mohou být uvedeny například:

Přepínání paměťových bank

Přepínání paměťových bank bylo používáno již u starších 8bitových počítačů. Do paměťového prostoru 64 KiB byla pomocí této jednoduché techniky mapována až několikanásobně větší paměť, než je paměťový rozsah procesoru (viz Didaktik Gama a Sinclair ZX Spectrum 128+). Hlavní rozdíl mezi stránkováním a přepínáním paměťových bank je v tom, že přepínání paměťových bank je typicky realizováno mimo procesor počítače, zatímco stránkování je naopak vlastnost procesoru, resp. jeho MMU (anglicky Memory Managment Unit). U nejstarších procesorů byla však MMU realizována nezávisle na procesoru jako samostatný obvod, takže rozdíl mezi těmito technikami není až tak výrazný.

Na počítačích IBM PC kompatibilních umožňovalo přepínání paměťových bank hardwarově mapovat do paměťového prostoru více paměťových rámců (tzv. EMS – rozšířená paměť), což umožňovalo při omezeném adresním prostoru procesoru používat větší množství paměti. EMS byla realizována nejprve přídavnou paměťovou kartou, později na procesorech i386 a novějších pak emulátorem rozšířené paměti EMM386.

Stránkování na IA-32

Na procesoru architektury IA-32 (procesory i386 a novější) je stránkování volitelná část hardwarového překladu adresy. Pokud je zapnuto nastavením příslušného bitu v registru CR0 a nastavením fyzické adresy počátku stránkovacího adresáře do registru CR3, vždy se provádí až po segmentaci, tedy virtuální adresa (používaná v programu - segment:offset) se nejprve segmentací transformuje na lineární adresu, která se pak stránkováním překládá na fyzickou adresu. Taktéž již tyto procesory obsahují TLB, ale pouze jako akceleraci, takže nebude dále rozebírána. První procesory podporovaly pouze velikost stránky 4 KiB a následující rozdělení 32bitové lineární adresy na tři části:

1. index do stránkovacího adresáře – záznam ukazuje na záznam tabulky stránek (10 bitů)
2. index do tabulky stránek (10 bitů)
3. offset ve stránce (12 bitů)

Velikost stránkovacího adresáře i tabulky stránky je 4KB a každý záznam v nich má délku 32 bitů (4 byty), což znamená že vždy obsahují 1024 záznamů. Stránkování probíhá tak, že se nejprve vezme prvních deset bitů virtuální adresy (1024 hodnot), kterými se vybere příslušný záznam ve stránkovacím adresáři. Pokud je platný, přečte se z něj nejvýznamnějších 20 bitů, které určují fyzickou adresu tabulky stránek. Do té se opět zaindexuje 11.-20. bitem virtuální adresy a vybere se příslušný záznam. Jeho nejvýznamnějších 20 bitů je již počátek fyzické adresy hledaného rámce. K ní se po posunu o 12 bitů vlevo přičte 12bitový offset a tím se získá úplná fyzická adresa.

Záznam v tabulce stránek i stránkovacím adresáři obsahuje příznak platnosti (určuje zda je daná stránka skutečně namapována). Pokud strojová instrukce přistupuje na neplatnou stránku, dojde k vyvolání výjimky (resp. vnitřního přerušení procesoru), které se nazývá „výpadek stránky“ (anglicky page fault). V případě, že je daná stránka na disku, obsluha přerušení ji z disku zavede do paměti a je obnoven běh daného vlákna od instrukce, která výpadek stránky způsobila.

Od procesoru Pentium byla přidána podpora stránek velikosti 4MiB, kvůli tomu, že například jádro operačního systému ví, že pro určitá data bude výhodnější použít velké stránky. Schéma stránkování je téměř shodné s předchozím případem, až na použití sedmého nejméně významného bitu v záznamu stránkovacího adresáře. Pokud je tento bit nastaven, jednotka MMU vezme prvních 10 nejvýznamnějších bitů adresáře (pokud systém podporuje větší fyzickou paměť než 4GiB, může se množina těchto bitů lišit), použije je jako adresu počátku rámce a jako offset v něm je 22 méně významných bitů virtuální adresy.

• 
  Původní stránkování bez 4MiB extenze
• 
  Původní stránkování, 4MiB extenze

V procesoru Pentium Pro byl dále zaveden speciální režim PAE (Physical Address Extension). Ten umožňuje adresovat více než 4GiB fyzické paměti za podpory 4GiB lineálního prostoru. Tento režim podporuje současnou existenci 4KiB a 2MiB stránek. Toho je docíleno tak, že lineární adresa je rozdělena na

1. index do tabulky adresářových ukazatelů (2 bity)
2. index do stránkovacího adresáře (9 bitů)
3. index do tabulky stránek (9 bitů)
4. offset ve stránce (12 bitů)

Velikost každého záznamu v tabulce adresářových ukazatelů, stránkovacím adresáři a tabulce stránek je 64 bitů. Tabulka adresářových ukazatelů má pouze čtyři záznamy, jinak stránkovací adresář a tabulka stránek má sníženy počet záznamů na 512, a tedy je zachována velikost 4kiB. Stránkování pak probíhá takto: podle prvních dvou bitů lineární adresy se vybere záznam v tabulce adresářových ukazatelů, z něj se vyextrahuje (až) 40 bitů počátku fyzické adresy příslušného stránkovacího adresáře a do něj se zaindexuje devíti bity Indexu do stránkovacího adresáře (pozor adresář má jen 512 záznamů), opět se z příslušného záznamu přečte (až) 40 bitů počátku fyzické adresy tabulky stránek, do které se zaindexuje druhou devíticí bitů. Opět se vyextrahuje (až) 40 bitů fyzické adresy stránky, provede se bitový posun o 12 bitů vlevo a k výsledku se přičte dvanáctibitový offset.

V případě použití 2MiB stránky se překlad, podobně jako u Pentia, zastaví přečtením jedničky v sedmém bitu záznamu stránkovacího adresáře a rovnou získaných (až) 31bitů počátku fyzické adresy je posunuto o 21 bitů vlevo a zbylých 21 bitů z virtuální adresy je přičteno jako offset.

Celkově tedy tento systém umožňuje adresovat až 4PiB operační paměti, nicméně původní implementace Pentia Pro měla pouze 36 bitů fyzické adresy a tudíž používala pouze 24 bitů adres počátků rámců.

• 
  PAE stránkování 4 KiB stránky
• 
  PAE stránkování 2 MiB stránky

Stránkování na x86-64

Intel tento způsob stránkování označuje jako IA32e-Paging. Byť se jedná o metodu stránkování v 64bitovém operačním módu, reálně však používá pouze posledních 48 bitů lineární adresy. Jinak by totiž byla hloubka stránkovací tabulky příliš velká a překlad adres by způsoboval výkonovou regresi, aniž by se benefitovalo z většího virtuálního prostoru. Lineární adresa je rozdělena na čtyři oblasti o devíti bitech a jednu o dvanácti:

1. index do PML4 tabulky (9 bitů)
2. index do tabulky adresářových ukazatelů (9 bitů)
3. index do stránkovacího adresáře (9 bitů)
4. index do tabulky stránek (9 bitů)
5. offset ve stránce (12 bitů)

Každá úroveň stránkovacích tabulek (od PML4 až po tabulku stránek) má právě 512 záznamů a tedy její struktura zabírá opět 4kiB. Při plné hloubce má adresovaná stránka velikost taktéž 4kiB. Algoritmus je až na hloubku tabulky shodný s předchozími, s tím, že fyzická adresa rámce je vždy vytvořena 12bitovým posunem vlevo určitých 40 bitů obsahu záznamu jednotlivých úrovní.

• 
  64bit stránkování 4 KiB stránky

Obdobně je také možné modifikovat sedmý bit záznamu tabulky adresářových ukazatelů nebo stránkovacího adresáře, což způsobí ukončení průchodu stránkovací tabulkou na příslušné úrovni a záznam indexuje rámec o velikosti 1GiB u tabulky adresářových ukazatelů, respektive 2MiB v případě stránkovacího adresáře (tomu pak i odpovídá velikost zbylého offsetu a zároveň posunu vlevo). Zároveň je v tomto případě snížen počet obsažených bitů určujících adresu počátku rámce na 22, resp. 31.

Na konci roku 2016 byla firmou Intel uvolněna dokumentace popisující stránkování užívající 57 bitů virtuální adresy. V podstatě se jedná o stejný mechanismus jako v předchozím případě. Jen je využito navíc dalších 9 bitů virtuální adresy pro indexování páté úrovně stránkovacích tabulek.

Výkon

Médium pro odkládání stránek je obvykle o několik řádů pomalejší než RAM. A to jak z hlediska rychlosti samotného přenosu dat, tak i latencí, než je potřebný blok vůbec vyhledán. U běžných pevných disků dosahuje zpoždění (v případě nízkého zatížení) zhruba 10 milisekund. Z těchto důvodů je ve vždy žádoucí optimalizace odkládání stránek. Pro případy, kdy standardní nastavení neposkytuje uspokojivé výsledky, některé operační systémy nabízejí nastavení ovlivňující rozhodování kernelu ohledně stránkování.

1. Linux nabízí parametr /proc/sys/vm/swappiness, který mění rovnováhu mezi stránkováním běhové paměti a odstraňováním stránek ze systémové stránkovací vyrovnávací paměti.
2. Windows 2000, XP a Vista nabízejí nastavení registru DisablePagingExecutive.
3. Mainframové počítače často používají diskové jednotky head-per-track pro stránkovací prostor kvůli snížení vyhledávacího času. Dále také používají několik technologií pro obsloužení více požadavků na stejném zařízení za účelem snížení rotační latence.

Flash paměť je z některých pohledů problematickým médiem pro swappování. To proto, že má pouze konečný počet cyklů zápisu, po jejich překročení se může stát nespolehlivou. Dále je nevýhodou nejmenší množství dat, které lze na ní najednou prohlásit za volná (to umožňuje vnitřní logice paměti, aby s bloky hospodařila a předcházela nerovnoměrnému optřebení), může být poměrně velké (128 KiB pro Intel X25-M SSD) a jen zřídkakdy se shoduje s velikostí stránky.

U flashových pamětí tedy může dojít k velmi rychlému opotřebení, zvláště pokud se používá jako swapovací prostor v zařízeních s omezenou kapacitou hlavní paměti. Ovšem obrovskou výhodou flash paměti je, že ve srovnání s pevnými disky a jinými nevolatilními RAM čipy funguje s výrazně nižší latencí. Proto existují technologie jako jsou ReadyBoost a Intel Turbo Memory, které snižují výše posané nevýhody.

Mnoho unixových operačních systémů (například AIX, Linux a Solaris) umožňují použít různé konfigurace externích paměťových zařízení pro stránkovací prostor, za účelem zvýšení systémového výkonu.

Odlišné velikosti stránek

Na procesorech ARM má 64bitová platforma AArch64 (ARMv8) možnost používat stránky o velikosti 4, 16 nebo 64 KiB. Standardní velikost je 4KiB. Větší velikost stránky pmaěti je používána v serverovém a HPC prostředí a v systému Android 15, kde 16 KiB stránky poskytují zvýšení výkonu o 5 až 10 % na úkor zvýšení využití operační paměti RAM o asi 9 %.

Pro zvýšení výkonu jsou v Linuxu jsou softwarově implementovány větší stránky o velikosti 64 KiB („big“ pages) a 1 MiB („super“ pages).

Stránkování na disk

Stránkování je jedním ze způsobů jak umožnit, aby velikosti adres využívaných procesem ("virtuální adresní prostor" nebo "logický adresní prostor") mohly být rozdílné od množství skutečně instalované operační paměti na konkrétním počítači (fyzický adresní prostor).

Velikosti stránkovacího prostoru na disku

V některých starších operačních systémech s virtuální pamětí je část swapovacího prostoru rezervována pro alokaci běhových dat spuštěného programu. Vývojáři systému obvykle vydávají pokyny o tom, kolik stránkovacího prostoru by mělo být přiděleno.

Spolehlivost stránkování na disk

Swapování může částečně snížit spolehlivost systému. Pokud dojde k poškození dat na disku (nebo na kterémkoliv dalším subsystému podílejícím se na swapování), může dojít k načtení chybných dat, což může mít katastrofické následky. Daleko častěji však v tomto případě zafungují případné kontrolní mechanizmy (implementované v hardwaru, například pevném disku, a operačním systému) a zabrání načtení takto poškozených dat. To je nutno považovat za kritickou chybu a jediným rozumným řešením je ukončení běhu dotčeného procesu (i samotný kernel je v tomto ohledu jen proces). Někdy je teoreticky možné pokusit se data načíst z nepoškozené kopie, pokud je dostupná (například kód programu), ale nespolehlivost swapovacího média se může projevit při jiné příležitosti.

Fyzická paměť menší než virtuální paměť

Ve většině systémů je velikost virtuálního adresního prostoru procesu mnohem větší, než je k dispozici fyzické paměti.

Množství dostupné fyzické paměti je limitováno celkovou instalovanou a případně instalovatelnou velikostí paměťových modulů.

Existovat může méně bitů fyzické adresy, než bitů virtuální adresy. Například i386SX interně využívá 32bitové virtuální adresy, taktéž vnitřně pracuje s 32bitovými fyzickými adresami, ale má pouze 24 pinů na vnější adresové sběrnici, což omezuje adresování fyzické paměti na nejvýše 16 MB. Dokonce i na systémech, které mají stejně nebo i více fyzických adresních bitů než virtuálních adresních bitů je často skutečné množství instalované fyzické paměti mnohem menší než velikost, kterou lze potenciálně adresovat. A to z finančních důvodů (zvyšuje se složitost hardwaru, který by to umožnil, aniž by bylo myslitelné pokrýt celý fyzický adresní prostor moduly RAM) nebo proto, že hardwarová adresní mapa rezervuje velké úseky pro vstupně výstupní zařízení nebo pro jiné hardwarové funkce a tedy fyzická paměť nemůže být umístěna v těchto úsecích.

Fyzická paměť stejně velká jako virtuální paměť

Je možné setkat se s 32bitovými počítači se 4 GiB RAM, tedy maximálním množstvím adresovatelné RAM paměti. Ne vždy je však možné využít celou tuto paměť, neboť je nutné pro to mít hardwarovou i softwarovou podporu. To proto, že u některých strojů, např. IBM S/370 v režimu XA, se horní bit nepoužíval k adresování fyzické paměti a bylo možné použít pouze 2 GiB. Navíc určitá část fyzického adresního prostotu může být rezervována pro vnitřní potřeby operačního systému (například mapování paměti grafické karty), a tudíž není možné adresovat fyzickou RAM, která se takto překrývá. Z toho plyne nutnost širší vnější fyzické adresové sběrnice procesoru a zároveň její podpora ze strany operačního systému.

Stránkovací a swapovací prostor však lze využít mimo tento 4 GB limit fyzické paměti, jelikož využívá odlišný, čistě softwarový, způsob adresování kvůli svému umístění na disku, které nikdy není přímo podporováno hardwarem MMU.

Fyzická paměť větší než virtuální adresní prostor

Existují architektury, které podporují větší fyzickou paměť než virtuální adresní prostor pro proces, jako je například Magic-1, některé stroje PDP-11 a některé systémy využívající 32bitové x86 procesory s Physical Address Extension.

Na první pohled se může zdát, že tyto systémy pozbývají významnou výhodu virtuální paměti, protože jediný proces nemůže využít více paměti, než je velikost jeho virtuálního adresního prostoru, ale to není pravda, protože při zachování zpětné binární kompatibility nedochází ke zmenšení virtuálního adresního prostoru. Naopak je zde použito stránkovací techniky k získání sekundárních výhod:

• Fyzická paměť může být použita pro různé cache v kernelu, pro ukládání často používaných souborů a metadat, jako jsou například informace o adresářích v sekundárním úložišti.
• Pokud procesor a operační systém podporují více virtuálních adresních prostorů, je možné virtuální adresní prostory jednotlivých procesů rozmístit do rozsáhlé fyzické paměti, čímž se omezí anebo úplně odstraní nutnost vystránkování na disk.

Velikost kumulativního součtu virtuálních adresních prostor je stále omezena velikostí dostupného sekundárního úložiště.

Reference

V tomto článku byl použit překlad textu z článku Paging na anglické Wikipedii.

Související články

• Dirty bit
• Virtuální paměť