Tabulka stránek - Page table

Vztah mezi stránkami adresovanými virtuálními adresami a stránkami ve fyzické paměti v rámci jednoduchého schématu adresního prostoru. Fyzická paměť může obsahovat stránky patřící k mnoha procesům. Stránky mohou být uchovávány na disku, pokud jsou zřídka používány nebo pokud je fyzická paměť plná. Ve výše uvedeném diagramu některé stránky nejsou ve fyzické paměti.

Tabulka stránek je datová struktura používaná systémem virtuální paměti v operačním systému počítače k ukládání mapování mezi virtuálními adresami a fyzickými adresami . Virtuální adresy používá program prováděný přístupovým procesem , zatímco fyzické adresy používá hardware nebo konkrétněji subsystém RAM . Tabulka stránek je klíčovou součástí překladu virtuálních adres, která je nezbytná pro přístup k datům v paměti.

Role tabulky stránek

V operačních systémech, které používají virtuální paměť, má každý proces dojem, že pracuje s velkými souvislými částmi paměti. Fyzicky může být paměť každého procesu rozptýlena v různých oblastech fyzické paměti nebo může být přesunuta ( stránkována ) do jiného úložiště, obvykle na jednotku pevného disku nebo jednotku SSD .

Když proces požaduje přístup k datům ve své paměti, je odpovědností operačního systému namapovat virtuální adresu poskytnutou procesem na fyzickou adresu skutečné paměti, kde jsou tato data uložena. Tabulka stránek je místo, kde operační systém ukládá svá mapování virtuálních adres na fyzické adresy, přičemž každé mapování se označuje také jako položka tabulky stránek (PTE).

Proces překladu

Akce podniknuté při překladu adresy z virtuální na fyzickou. Každý překlad se restartuje, pokud dojde k chybě TLB, takže k vyhledávání může dojít správně pomocí hardwaru.

Jednotka pro správu paměti CPU (MMU) ukládá mezipaměť naposledy použitých mapování z tabulky stránek operačního systému. Toto se nazývá překladová vyrovnávací paměť překladu (TLB), což je asociativní mezipaměť.

Když je třeba virtuální adresu přeložit na fyzickou adresu, prohledá se nejprve TLB. Pokud je nalezena shoda (přístup TLB ), je vrácena fyzická adresa a přístup do paměti může pokračovat. Pokud však neexistuje shoda (nazývá se chyba TLB ), jednotka správy paměti nebo obslužná rutina chyby TLB operačního systému obvykle vyhledá mapování adres v tabulce stránek, aby zjistila, zda existuje mapování ( procházení stránky ). Pokud existuje, zapíše se zpět do TLB (toto je nutné provést, protože hardware přistupuje k paměti prostřednictvím TLB ve virtuálním paměťovém systému) a instrukce k poruše se restartuje (může se to stát také paralelně). Následující překlad najde TLB přístup a přístup do paměti bude pokračovat.

Selhání překladu

Vyhledání tabulky stránky může selhat a spustit chybu stránky ze dvou důvodů:

  • Vyhledání může selhat, pokud pro virtuální adresu není k dispozici žádný překlad, což znamená, že virtuální adresa je neplatná. K tomu obvykle dojde kvůli programovací chybě a operační systém musí podniknout nějaké kroky, aby problém vyřešil. V moderních operačních systémech to způsobí odeslání signálu poruchy segmentace do problematického programu.
  • Hledání může také selhat, pokud stránka aktuálně není rezidentem ve fyzické paměti. K tomu dojde, pokud byla požadovaná stránka přesunuta z fyzické paměti, aby se vytvořil prostor pro další stránku. V tomto případě je stránka stránkována do sekundárního úložiště umístěného na médiu, jako je jednotka pevného disku (toto sekundární úložiště nebo „záložní úložiště“ se často nazývá „odkládací oddíl“, pokud se jedná o diskový oddíl, nebo swapový soubor , "swapfile" nebo "stránkovací soubor", pokud se jedná o soubor). Když k tomu dojde, je třeba stránku odebrat z disku a vrátit zpět do fyzické paměti. Podobný mechanismus se používá pro soubory mapované paměti , které jsou mapovány do virtuální paměti a na vyžádání načteny do fyzické paměti.

Pokud fyzická paměť není plná, jedná se o jednoduchou operaci; stránka je zapsána zpět do fyzické paměti, tabulka stránek a TLB jsou aktualizovány a instrukce je restartována. Když je však fyzická paměť plná, bude třeba vytočit jednu nebo více stránek ve fyzické paměti, aby se vytvořil prostor pro požadovanou stránku. Tabulku stránek je třeba aktualizovat, aby bylo možné označit, že stránky, které byly dříve ve fyzické paměti, již neexistují, a označit, že stránka, která byla na disku, je nyní ve fyzické paměti. Je také třeba aktualizovat TLB, včetně odstranění stránky s stránkováním, a restartování instrukce. Která stránka má být vyřazena, je předmětem algoritmů nahrazování stránek .

Některé MMU spouští poruchu stránky z jiných důvodů, ať už je stránka aktuálně rezidentní ve fyzické paměti a mapována do prostoru virtuálních adres procesu:

  • Pokus o zápis, když má tabulka stránek nastaven bit jen pro čtení, způsobí chybu stránky. Toto je běžná součást implementace copy-on-write mnoha operačních systémů ; může se také vyskytnout, když je zápis proveden do místa, ze kterého je proces povolen číst, ale do kterého není povolen zápis, v takovém případě je do procesu doručen signál.
  • Pokus o spuštění kódu, když má tabulka stránek v tabulce nastaven bit NX ( bit bez provedení), způsobí chybu stránky. To může operační systém v kombinaci s bitem jen pro čtení použít k zajištění funkce Write XOR Execute , která zastaví některé druhy zneužití.

Data tabulky rámců

Nejjednodušší systémy tabulkových stránek často udržují tabulku rámců a tabulku stránek. Tabulka rámců obsahuje informace o tom, které rámce jsou mapovány. V pokročilejších systémech může tabulka rámců obsahovat také informace o tom, do kterého adresního prostoru stránka patří, statistické informace nebo jiné základní informace.

Data tabulky stránek

Tabulka stránek je pole položek tabulky stránek.

Záznam stránky stránky

Každá položka tabulky stránek (PTE) obsahuje mapování mezi virtuální adresou stránky a adresou fyzického rámce. K dispozici jsou také pomocné informace o stránce, například aktuální bit, špinavý nebo upravený bit, adresní prostor nebo informace o ID procesu.

Sekundární úložiště, například pevný disk, lze použít k rozšíření fyzické paměti. Stránky lze stránkovat dovnitř a ven z fyzické paměti a disku. Přítomný bit může označovat, jaké stránky jsou aktuálně přítomny ve fyzické paměti nebo jsou na disku, a mohou označovat, jak zacházet s těmito různými stránkami, tj. Zda načíst stránku z disku a stránku jinou stránku ve fyzické paměti ven.

Špinavý bit umožňuje optimalizaci výkonu. Stránka na disku, která je stránkována do fyzické paměti, poté čtena z a následně znovu stránkována, nemusí být zapsána zpět na disk, protože stránka se nezměnila. Pokud však byla stránka zapsána po jejím stránkování, bude nastaven její špinavý bit, což znamená, že stránka musí být zapsána zpět do záložního úložiště. Tato strategie vyžaduje, aby záložní úložiště zachovalo kopii stránky po jejím stránkování do paměti. Pokud se nepoužije špinavý bit, záložní úložiště musí být v každém okamžiku pouze tak velké, jako je okamžitá celková velikost všech stránkovaných stránek. Když se použije špinavý bit, některé stránky budou vždy existovat jak ve fyzické paměti, tak v záložním úložišti.

V operačních systémech, které nejsou operačními systémy s jedním adresovým prostorem , jsou informace o adresním prostoru nebo ID procesu nezbytné, aby systém správy virtuální paměti věděl, jaké stránky se k jakému procesu přiřadit. Dva procesy mohou používat dvě stejné virtuální adresy pro různé účely. Tabulka stránek musí dodávat různá mapování virtuální paměti pro tyto dva procesy. To lze provést přiřazením dvou odlišných identifikátorů map adres, nebo pomocí ID procesu. Přiřazení ID procesů k stránkám virtuální paměti může také pomoci při výběru stránek, které se mají vypnout, protože stránky spojené s neaktivními procesy, zejména procesy, jejichž kódové stránky byly stránkovány, jsou méně pravděpodobně okamžitě potřebné než stránky patřící k aktivním procesům.

Jako alternativu k označování položek tabulky stránek identifikátory jedinečnými pro proces může samotná tabulka stránek pro každý proces zabírat jinou stránku virtuální paměti, takže se tabulka stránek stává součástí kontextu procesu. V takové implementaci je možné stránkovat tabulku stránek procesu, kdykoli proces již není rezidentem v paměti.

Typy stránek

Existuje několik typů tabulek stránek, které jsou optimalizovány pro různé požadavky. Tabulka stránek s holými kostmi musí v zásadě uchovávat virtuální adresu, fyzickou adresu, která je „pod“ touto virtuální adresou, a případně některé informace o adresním prostoru.

Obrácené tabulky stránek

Tabulka obrácených stránek (IPT) je nejlépe považována za rozšíření čipu TLB mimo čip, které používá normální systémovou RAM. Na rozdíl od skutečné tabulky stránek není nutně schopen pojmout všechna aktuální mapování. Operační systém musí být připraven na zvládnutí chyb, stejně jako u softwarově plněného TLB ve stylu MIPS.

IPT kombinuje tabulku stránek a tabulku rámců do jedné datové struktury. V jádru je tabulka pevné velikosti s počtem řádků rovným počtu rámců v paměti. Pokud existuje 4 000 rámců, převrácená tabulka stránek má 4 000 řádků. U každého řádku je položka pro číslo virtuální stránky (VPN), číslo fyzické stránky (ne fyzická adresa), některá další data a prostředky pro vytvoření řetězce kolizí , jak uvidíme později.

Prohledávat všechny položky základní struktury IPT je neúčinné a lze použít hashovací tabulku k mapování virtuálních adres (a případně adresního prostoru / informací PID) na index v IPT - zde se používá kolizní řetězec . Tato hash tabulka je známá jako hash kotevní tabulka . Funkce hash není obecně optimalizována pro pokrytí - surová rychlost je více žádoucí. Samozřejmě hašovací tabulky zažívají kolize. Kvůli této vybrané hashovací funkci se může při používání setkat s mnoha kolizemi, takže pro každou položku v tabulce je poskytována VPN, aby se zkontrolovalo, zda se jedná o hledanou položku nebo kolizi.

Při hledání mapování se používá hash kotevní tabulka. Pokud neexistuje žádný záznam, dojde k chybě stránky. Jinak bude položka nalezena. V závislosti na architektuře může být položka znovu umístěna do TLB a reference paměti je restartována, nebo může být sledován kolizní řetězec, dokud není vyčerpán a dojde k chybě stránky.

Virtuální adresa v tomto schématu může být rozdělena na dvě, přičemž první polovina je číslo virtuální stránky a druhá polovina je offset na této stránce.

Hlavním problémem tohoto návrhu je špatná lokalita mezipaměti způsobená funkcí hash . Stromové návrhy se tomu vyhnou tím, že umístí položky tabulky stránek pro sousední stránky do sousedních umístění, ale obrácená tabulka stránek zničí prostorovou referenční lokalitu rozptýlením položek po celém textu. Operační systém může minimalizovat velikost hashovací tabulky, aby tento problém zmenšil, přičemž kompromisem je zvýšená míra chyb.

Obvykle existuje jedna hash tabulka, sousedící s fyzickou pamětí, sdílená všemi procesy. Identifikátor podle jednotlivých procesů se používá k vzájemné nejednoznačnosti stránek různých procesů. Odstranit položky tabulky stránek daného procesu je poněkud pomalé; operační systém se může vyhnout opětovnému použití hodnot identifikátorů jednotlivých procesů, aby se s tím setkal. Alternativně lze použít hašovací tabulky pro jednotlivé procesy, ale jsou nepraktické z důvodu fragmentace paměti , která vyžaduje předběžné přidělení tabulek.

Obrácené tabulky stránek se používají například na architektuře PowerPC , UltraSPARC a IA-64 .

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

Dvouúrovňová struktura tabulky stránek v architektuře x86 (bez PAE nebo PSE ).
Tříúrovňová struktura tabulky stránek v architektuře x86 (s PAE , bez PSE ).

Tabulka převrácené stránky udržuje seznam mapování nainstalovaných pro všechny rámce ve fyzické paměti. To by však mohlo být docela zbytečné. Místo toho bychom mohli vytvořit strukturu tabulky stránek, která obsahuje mapování pro virtuální stránky. Děje se to udržováním několika tabulek stránek, které pokrývají určitý blok virtuální paměti. Můžeme například vytvořit menší 1024 vstupní stránky 4K, které pokrývají 4M virtuální paměti.

To je užitečné, protože při spouštění procesu se často používají nejhornější části a nejspodnější části virtuální paměti - horní část se často používá pro textové a datové segmenty, dolní část pro zásobník a mezi nimi je volná paměť. Víceúrovňová tabulka stránek může ponechat několik menších tabulek stránek tak, aby pokrývaly pouze horní a dolní část paměti a vytvářely nové pouze v nezbytně nutných případech.

Nyní je každá z těchto menších tabulek stránek propojena hlavní stránkovou tabulkou, čímž se efektivně vytváří stromová datová struktura. Nemusí existovat pouze dvě úrovně, ale možná i více. Například virtuální adresu v tomto schématu lze rozdělit na tři části: index v tabulce kořenových stránek, index v tabulce podstránek a posun na této stránce.

Víceúrovňové tabulky stránek se také označují jako „hierarchické tabulky stránek“.

Virtualizované tabulky stránek

Bylo zmíněno, že vytvoření struktury tabulky stránek, která obsahovala mapování pro každou virtuální stránku ve virtuálním adresovém prostoru, by mohlo být zbytečné. Nadměrné obavy o prostor však můžeme obejít tak, že umístíme tabulku stránek do virtuální paměti a necháme systém virtuální paměti spravovat paměť pro tabulku stránek.

Část této lineární struktury tabulky stránek však musí vždy zůstat rezidentní ve fyzické paměti, aby se zabránilo chybám kruhových stránek a hledala klíčová část tabulky stránek, která se v tabulce stránek nenachází.

Vnořené tabulky stránek

Viz také: Překlad adres druhé úrovně

Je možné implementovat vnořené tabulky stránek, aby se zvýšil výkon virtualizace hardwaru . Poskytnutím hardwarové podpory pro virtualizaci tabulkových stránek se výrazně sníží potřeba emulace. Pro x86 virtualizace aktuální volby jsou Intel 's Extended Page Table funkce a AMD je Rapid Virtualization Indexing funkce.

Viz také

Reference

Další čtení

externí odkazy