Stránkovací algoritmy

V počítačových operačních systémech, které používají stránkování, algoritmus nahrazování stránek rozhoduje o tom, které stránky (části paměti) swapovat („odkládat“ na disk) v případě potřeby alokace stránek nových. Ke stránkování dochází v případě stránkovací chyby (výpadku stránky), tj. není možné použít volnou stránku, buď z toho důvodu, že už žádná není k dispozici, nebo jich není k dispozici dostatečné množství.

Jakmile je zvolena nahrazovaná stránka, je potřeba ji načíst z disku, což zahrnuje čekání na dokončení I/O operace tohoto čtení. Délka této prodlevy přímo určuje kvalitu zvoleného algoritmu nahrazování stránek.

Algoritmus musí pracovat s omezenými informacemi o přístupu ke stránkách, které jsou mu poskytovány hardwarem a poté se snaží vybrat stránky určené k nahrazení takovým způsobem, aby minimalizoval množství chybně vybraných stránek a zároveň, aby samotný algoritmus nebyl příliš náročný na procesorový čas a přístup k datovému úložišti.

Lokální vs. globální nahrazování

Při vyčerpání počtu volných stránek daným procesem lokální algoritmus nahrazování stránek vybírá jen ze stránek, které patří ke stejnému procesu, případně skupině procesů, které sdílejí stejnou část paměti (memory partition). Zatímco globální algoritmus může vybrat libovolnou stránku z celé paměti.

Výhodou globálního nahrazování je velká škálovatelnost – každý proces řídí své stránkování nezávisle a není vyžadována žádná sdílená globální datová struktura, je nicméně vyžadována nějaká forma dělení (partitioningu) paměti, které přiděluje části paměti jednotlivým procesům.

Preemptivní čištění stránek a předběžné stránkování

Jednouché nahrazovací algoritmy jako výsledek vrací jen cílovou stránku (určenou pro nahrazení), pokud je tato stránka „špinavá“ (obsahuje data, které musí být zapsány na disk, před uvolněním stránky). Toto dříve nebýval velký problém, protože první systémy využívající virtuální paměť byly implementovány na plně duplexních systémech, takže stránkovaní a čištění mohlo probíhat zároveň.

U hardwaru, který ale plně duplexní komunikaci nepodporuje dochází k velkému zpomalení, proto se implementují různé „předčišťovací“ algoritmy, které se snaží předpovídat, které stránky budou vybrány nahrazení a čistí je předem. Pokud jsou předčišťovací algoritmy moc agresivní mohou zahltit I/O pásmo a způsobit opětovné „znečištění“ (zaplnění) předčištěných stránek.

S předčišťovacími algoritmy se také často kombinuje takzvané předběžné stránkování, které (na rozdíl od stránkování na požádání) předběžně načítá do operační paměti stránky u kterých se předpokládá, že budou brzy potřeba. V případě chyby stránkování je navíc díky předběžnému stránkování možné přistupovat i k následujícím stránkám ve frontě.

Stránkovací úloha (h,k)

Jde o model určený k měření výkonnosti daného stránkovacího algoritmu. V tomto případě jsou h a k kladná celá čísla, u kterých platí h<=k, kde k je velikost cache a h je velikost cache Optimálního nahrazovacího algoritmu. Výkon se měří srovnáním s optimálním nahrazovacím algoritmem.

Značkovací (marking) algoritmy

Značkovací algoritmy jsou třída stránkovacích algoritmů fungující následujícím způsobem:

Každá stránka je propojena s jedním bitem (hodnoty 1/0), který funguje jako značka. Při spuštění algoritmu je nejdříve všem bitům přiřazena hodnota 0 (neoznačeno).

Při prvním načtení dané stránky je označena 1, značkovací algoritmus pak zajišťuje, že označené stránky nejsou swapovány na disk.

Účinnost značkovacích algoritmů je hodnocena podle následujícího vztahu: ''hm, chybí''.

Kde h je velikost cache našeho algoritmu a k je velikost cache optimálního algoritmu.

Konzervativní algoritmus

Konzervativní algoritmus je takový algoritmus, který pro každou sekvenci stránkovacích žádostí, která obsahuje k nebo méně referencí na určité stránky vyhodí k, nebo méně stránkovacích chyb.

Účinnost se hodnotí shodně, jako u značkovacího algoritmu.

Používané algoritmy nahrazování stránek

Teoreticky optimální nahrazování stránek

Teoreticky optimální algoritmus nahrazování stránek, funguje následovně: Pokud je nutné swapnout stránku na disk, systém vybere takovou, která bude využita nejpozději.

Tento algoritmus je pouze teoretický, protože v klasickém operačním systému ho není možné spolehlivě implementovat. Existují algoritmy, které analyzují běh programu a mohou se teoreticky optimálnímu algoritmu velmi přiblížit po několika „učících“ cyklech, za předpokladu že se program chová při každém cyklu podobným (předvídatelným) způsobem.

Pomocí tohoto teoretického „best case“ algoritmu se hodnotí účinnost algoritmů ostatních.

NRU - Not recently used

Not recently used (dále NRU), neboli „v poslední době nepoužité“ je algoritmus, který ponechává v paměti prioritně nedávno použité stránky.

Tento algoritmus funguje na principu přiřazování vlastností jednotlivým stránkám a to reference bitu (na stránku bylo odkázáno) a modified bitu (stránka byla změněna).

Pro každou stránku běží časovač, který po určitém čase vynuluje její vlastnosti. Tím je zajištěno, že v paměti budou přednostně uloženy naposledy použité stránky a nedávno nepoužité budou swapovány na disk.

Jde o značkovací algoritmus, používá se tedy příslušné hodnocení účinnosti.

FIFO - First-in, first-out

Jde o nejjednodušší stránkovací algoritmus používající (jak už je jasné z názvu) frontovou strukturu stránek, ve které platí, že když je velikost fronty (paměť) vyčerpána, swapuje se stránka, která je ve frontě nejdelší dobu.

Jde o velmi „levný“ algoritmus, co se systémových prostředků týče, nicméně jeho efektivita je velmi špatná, proto se v podstatě nepoužívá (jen jeho modifikované verze – viz níže).

Jde o konzervativní algoritmus.

Second chance (algoritmus druhé šance)

Jde o modifikaci FIFO algoritmu (viz výše). Jde o výrazně účinnější algoritmus s poměrně malým zvýšením požadavků na systémové prostředky. Používá kombinaci FIFO a NRU algoritmu, kdy stejně jako FIFO kontroluje začátek fronty, ale místo toho aby okamžitě swapnul první stránku na disk, zkontroluje, zda k ní není přiřazen referenced bit, pokud ano, přistoupí k další stránce v pořadí a proces se opakuje.

V případě, že mají všechny stránky nastaven referenced bit, tak v druhém cyklu je swapnuta první stránka ve frontě.

Clock (hodinový algoritmus)

Jde o účinnější variantu FIFO algoritmu (i ve vztahu k algoritmu druhé šance). Stránkovací prostor je uspořádán do kruhu (hodiny), ve kterém se pohybuje ukazatel (ručička), který ukazuje na poslední zkontrolovanou stránku (nebo prázdný stránkovací rámec).

V případě, že dojde paměť, tak se na stránce, kde se nachází ukazatel zkontroluje přítomnost referenced bitu. Pokud je R bit 0, stará stránka se swapne na disk a nová je zapsána na její místo. V případě, že hodnota R bitu je 1, změní se na 0 a ukazatel se posune o jedno místo. Tento proces se opakuje, dokud není nová stránka zapsána.

LRU - Least recently used (nejdéle nepoužívané)

Tento algoritmus je podobný NRU algoritmu, s tím rozdílem, že zatímco NRU pracuje pouze s jednotlivými tiky časovače LRU pracuje se stránkami, které byly použity za několik posledních instrukcí.

Idea za algoritmem je tedy taková, že stránky, které byly nejvíce používané v bezprostřední minulosti budou s nejvyšší pravděpodobností použity znovu v bezprostřední budoucnosti.

Hlavní problém LRU algoritmu leží ve velmi nákladné implementaci v kontextu systémových prostředků.

Základní (a nejdražší) LRU implementace spočívá v použití spojového seznamu, kde vzadu jsou nedávno nejméně používané stránky a vepředu nejvíce. Náročnost této implementace je dána faktem, že se při každém přístupu do paměti musí tento list posunout.

Další způsob implementace je možný s použitím hardwarového počítadla. V tomto případě se vždy „zavolané“ stránce přiřadí aktuální hodnota počítadla. Nahrazovány jsou pak stránky s hodnotou nejnižší. Tato implementace je ovšem také velmi náročná a u dnešního hardware stále nevhodná.

Velkou nevýhodou LRU jsou tedy výkonnostní nároky. Existuje velké množství jeho modifikací, které používají LRU jen částečně, nebo jen v některých případech.

Jde o značkovací algoritmus.

Random (náhodný)

Tento algoritmus jednoduše nahradí náhodnou stránku v paměti, je výkonnostně nenáročný a ve většině případů funguje lépe, než FIFO. Nicméně je většinou méně optimální než LRU.

NFU - Not frequently used (nejméně používané)

Tento algoritmus funguje na principu počitadel, které jsou přiřazené každé stránce a na začátku nastavená na nulovou hodnotu. V každém intervalu časovače se pak všem zavolaným stránkám přičte k jejich počítadlu 1. Při swapováni je tedy upřednostněna stránka s nejnižší hodnotou počítadla.

Největší nevýhoda NFU leží v tom, že algoritmus nebere ohled na frekvenci používání stránek, jen na jejich počet. Toto je samozřejmě problematické, když se například v první části procesu používá hojně jedna skupina stránek, zatímco v druhé je daleko důležitější skupina, která byla doposud využívána jen sporadicky.

Aging (stárnutí)

Jde o derivát NFU algoritmu, funguje obdobně s tím rozdílem, že počítadlo je v každém tiku děleno 2 a pak až se eventuálně inkrementuje. Tím je zajištěna větší relevance nedávných referencí.

V podstatě jediná nevýhoda aging algoritmu spočívá ve faktu, že může sledovat jen reference 16-, nebo 32bitových intervalech (podle procesoru). V praxi ale nejde o velký problém, protože pro většinu úloh je tento rozsah dostatečný.

Jde tedy o algoritmus, který je středně náročný, ale velmi se přibližuje algoritmu optimálnímu.

Reference

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

Windows MSDN library - About memory management