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 správy paměti (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 mechanismus 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í náhled|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á mechanismus, 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í v jeho č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.
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 mechanismus, 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 (jednotka správy paměti). 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 ().
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.