Hlavní navigace

Porovnání systémů Linux a FreeBSD (11)

Mikuláš Patočka

V dalším pokračování kapitoly o virtuální paměti se podíváme na jednotlivé algoritmy výměny stránek - jak teoretické, tak prakticky realizované v jádře FreeBSD a v různých jádrech Linuxu.

Základní algoritmy výměny stránek

Zde se stručně zmíním o základních algoritmech, které jsou popsány v literatuře. Tyto algoritmy samy o sobě nestačí, neboť neřeší problém sdílení stránek. Algoritmy používané ve skutečných operačních systémech jsou většinou kombinací těchto základních algoritmů.

  • LRU — Least-recently-used. Vyrobí se fronta nacachovaných stránek. Když se přistupuje na stránku, která už v cachi je, nebo natáhne-li se nová stránka z disku, umístí se na začátek fronty. Pokud dochází paměť, uvolňují se stránky na konci fronty z paměti a případně se zapisují na disk, jestliže byly modifikovány. Tento algoritmus je možno implementovat na nenamapované stránky (data čtená pomocí syscallu read), ale není ho možno implementovat na stránky namapované v adresním prostoru procesu, neboť procesor neumí při přístupu na stránku udělat operaci „přesun stránky na začátek fronty” (šlo by to implementovat na architekturách se softwarovým zpracováváním TLB missů, jako například Sparc64, nicméně by to zpracování TLB missů zpomalovalo). Při přístupu na stránku procesor umí pouze nastavit v tabulce stránek jeden bit. Algoritmus LRU je velmi dobrý, většina implementací se mu snaží přiblížit, nicméně v jednom případě naprosto selže — při sekvenčním čtení souboru delšího, než je velikost paměti. Operační systém chovající se striktně podle LRU by v takovém případě měl odswapovat všechny procesy na disk a celou paměť použít jako cache na koncový úsek souboru. Takové chování je silně nežádoucí.
  • Hodinový algoritmus — Stránky v paměti jsou v kruhovém seznamu. Existuje ukazatel na aktuální stránku (hodinová ručička). Při přístupu na stránku se nastaví bit, že na stránku bylo přistupováno. Při nedostatku paměti se podíváme na stránku, na kterou ukazuje ručička — pokud je bit přístupu smazaný, stránku uvolníme. Je-li bit přístupu nastavený, smažeme jej a postoupíme na další stránku (pokud byly bity na všech stránkách nastavené, oběhneme jednou celý kruh a pak již nalezneme stránku, jejíž bit jsme dříve smazali). Tento algoritmus je možno použít i na namapované stránky, neboť procesor bit při přístupu nastavuje. Nevýhoda algoritmu je taková, že pokud nedochází k nedostatku paměti, algoritmus nic nedělá (kromě nastavování bitů), a až pak k nedostatku paměti dojde, vůbec od sebe nerozeznáme stránky, na které bylo naposledy přistupováno před pěti sekundami, od těch naposledy použitých před deseti minutami. Hodinový algoritmus má stejně jako LRU nežádoucí chování při čtení dlouhého souboru.
  • Page aging — Počítání „věku”stránky. Stránka má kromě bitu přístupu ještě počítadlo age. Algoritmus funguje stejně jako hodinový algoritmus až na to, že navíc manipuluje s age. Při zavedení stránky je age nastaven na nějakou malou fixní hodnotu (může to být 1). Při zjištění nastaveného bitu přístupu je age zvětšen až do nějaké maximální meze, bit přístupu je smazán a postoupí se na další stránku. Při zjištění nenastaveného bitu přístupu je age snížen; pokud dosáhne 0, stránka je uvolněna. Je-li větší než 0, postoupí se na další stránku. Tento algoritmus částečně řeší problém čtení dlouhého souboru — pokud je soubor větší než paměť, budou stránky souboru při dalším průchodu mít age 1, zatímco ostatní stránky, které byly v cachi dříve a na které se déle přistupovalo, budou mít age větší. Algoritmus bude tedy přednostně uvolňovat později načtené stránky souboru a ostatní stránky nějakou dobu v paměti nechá. Řešení to stále není ideální — všem stránkám se bude age snižovat, takže pokud budeme dlouhý soubor číst dostatečně dlouho, ostatním stránkám přece jen za čas klesne age na 0 a budou uvolněny. Dojde k tomu však mnohem později než v případě předchozích algoritmů.

Algoritmus výměny stránek na FreeBSD

Natahování stránek je zřejmé (systém prostě natáhne stránku, na které došlo k výpadku, případně ještě udělá read-ahead na několik dalších stránek). Nejsložitější částí systému virtuální paměti je algoritmus, který rozhoduje, jaká stránka se má uvolnit v případě nedostatku paměti. FreeBSD používá čtyři fronty stránek: ACTIVE, INACTIVE, CACHE a FREE (množství stránek na těchto frontách je možno vidět ve výpisu příkazu  top).

Fronta ACTIVE obsahuje stránky, na které se často a hodně přistupuje. Fronta INACTIVE obsahuje stránky, na které se málo přistupuje. Fronta CACHE obsahuje čisté nenamapované stránky, které je možno kdykoli uvolnit. (Název fronty „CACHE” nemá nic společného s pojmem „cache” používaným pro paměť obsahující data souborů z disku — do CACHE fronty se ukládají jak stránky obsahující cachované soubory, tak stránky alokované a swapované — stejně tak stránky obsahující cachované soubory se vyskytují nejen na frontě CACHE, ale i na ACTIVE a INACTIVE). Fronta FREE obsahuje volné stránky. Algoritmus se snaží držet určitý pomět mezi frontami ACTIVE a INACTIVE (kdysi to bývalo ACTIVE < 2/3 celkové paměti, na aktuálních verzích může fronta ACTIVE zabrat téměř celou paměť). Dále se snaží, aby ve frontách CACHE+FREE bylo alespoň kolem 10MB paměti a aby ve frontě FREE bylo alespoň 500kB (přesné hodnoty se mohou lišit, počítají se při startu podle celkové velikosti paměti). Běžný kód v jádře může alokovat stránky z front CACHE a FREE (pokud je ve FREE více než 500kB, alokuje se z FREE, jinak se alokuje z CACHE); interrupty mohou alokovat pouze z fronty FREE. Oněch 500kB je paměť rezervovaná pro alokaci z interruptů (typicky se zde alokují buffery pro síťové packety).

Algoritmus má dvě nezávislé části: první část zajišťuje, aby ACTIVE fronta příliš nerostla — pokud je její velikost větší než nastavený limit, začnou se stránky z ACTIVE fronty přesouvat do INACTIVE fronty. K výběru stránky se používá algoritmus „Page aging”. Systém je možno přepnout, aby k výběru používal hodinový algoritmus (pokud sysctl vm.pageout_algorithm != 0). Druhá část algoritmu začne pracovat, pokud klesne množství paměti ve frontách CACHE a FREE. Tato část přesouvá stránky z fronty INACTIVE do fronty CACHE. Stránka je případně ještě zapsána do souboru nebo do swapu, pokud byla modifikovaná (t.j. má nastaven příznak PG_DIRTY). Algoritmus výběru stránky z INACTIVE fronty je následující: vezme se stránka z konce fronty, pokud má nastaven příznak PG_REFERENCED(ne­bo pokud některé její mapování má nastaven příznak přístupu), tak se tento příznak zruší a stránka se umístí do ACTIVE fronty. Pokud stránka příznak PG_REFERENCED nemá (tzn. od doby jejího umístění do INACTIVE fronty ji žádný proces nečetl), je buď zapsána (má-li PG_DIRTY), nebo rovnou přesunuta do CACHE fronty. Experimentálně se zjistilo, že poněvadž zápis stránek je pomalý, je lepší uvolňovat čisté stránky než zapisovat špinavé — algoritmus byl modifikován tak, že špinavá stránka musí celou INACTIVE frontou projít dvakrát, než bude zapsána. Když je špinavá stránka nalezena poprvé, umístí se na začátek fronty a nastaví se jí příznak PG_WINATCFLS, který znamená, že stránka je v druhém průchodu. Pokud je na konci fronty nalezena stránka s  PG_WINATCFLS, je zapsána a opět umístěna (už jako čistá stránka) na začátek INACTIVE fronty. Až po třetím průchodu INACTIVE fronty je stránka přesunuta do CACHE.

Pokud jsou nové stránky čteny nebo zapisovány pomocí read nebo write, jsou umístěny do fronty INACTIVE. Pokud jsou stránky čteny jako důsledek page-faultu, jsou umístěny do fronty ACTIVE.

Tento algoritmus splňuje většinu požadavků — pokud uživatel pouze čte nebo zapisuje soubor větší než paměť, budou stránky tohoto souboru umisťovány do INACTIVE fronty, ACTIVE fronty se to ani netkne, a proto tato operace nezpůsobí odswapovávání použitých stránek nebo uvolňování často používaných cachovaných stránek. Pokud budeme číst veliký soubor, smaže nám to jen celou INACTIVE frontu, což je asi 1/3 paměti — na rozdíl například od algoritmu LRU, který by v takovém případě přemazal celou paměť. Page aging na ACTIVE frontě je také dobrá strategie, neboť to částečně zabraňuje přemazání celé ACTIVE fronty, pokud nějaký proces namapuje velké množství paměti (větší množství, než kolik je fyzické paměti) a pak na ni cyklicky přistupuje.

Ve starších verzích FreeBSD platilo, že stránky byly před přesunutím do INACTIVE fronty odmapovány. Byla snaha udělat jakousi napodobeninu LRU (jak víme, LRU nelze používat pro namapované stránky) — v ACTIVE frontě se stránky odmapovávaly a odstraňovaly pomocí page agingu a na INACTIVE frontě fungovalo LRU. Později se zjistilo, že odmapovávání a nové namapovávání stránek je náročné, proto se od odmapovávání upustilo a na INACTIVE frontě se nacházejí i namapované stránky.

FreeBSD má kromě klasických limitů na velikost dat a velikost celkové virtuální paměti procesu i limit na množství aktuálně namapovaných stránek. Pokud proces limit překročí, jsou mu stránky odmapovávány a přesouvány do INACTIVE fronty. Tento mechanismus umožňuje základní obranu proti vytrashování systému velkým procesem; nicméně není to ochrana absolutní — proces stále může vytrashovat ACTIVE frontu, ale nejde to jednoduchým mapováním velkého množství stránek.

FreeBSD má pokus o swapování celých procesů (je třeba povolit pomocí sysctl). Pokud proces dlouho neběžel nebo pokud se nepodařilo uvolnit dost stránek procházením front, dojde k tzv. swapoutu procesu. Při swapoutu jsou všechny stránky procesu přemístěny do INACTIVE fronty a tři stránky obsahující zásobník jádra jsou změněny na swapovatelné a také přesunuty do INACTIVE fronty. Při opětovném naswapování a rozběhnutí procesu je zásobník jádra natažen do paměti a vyjmut ze swapovacího systému, aby nebyl znovu odswapován. V dnešní době velikých pamětí již nemá žádnou cenu snažit se uvolnit tři stránky na proces (nehledě na to, že proces může zabírat mnohem více neswapovatelné paměti v handlech, strukturách file, mapování paměti a podobně) — tento kód na swapování zásobníku jádra zjevně pochází z velmi dávných dob, kdy bylo třeba stránkami dost šetřit. Swapování celých procesů na FreeBSD nefunguje zdaleka tak čistě jako swapování procesů na VMS, neboť po naswapování procesu do paměti nejsou zavedeny stránky, které byly namapovány při odswapování procesu.

Algoritmus výměny stránek na Linuxu 2.2

V jádrech 2.2 a nižších se nacházel ne příliš kvalitní algoritmus. Algoritmus byl napsán spontánně, bez většího rozmýšlení, a byl laděn tak dlouho, dokud nefungoval rozumně. Měl dvě části. První, nejdříve puštěná část procházela ve stylu „hodinového algoritmu” všechny stránky v systému. Pokud měla stránka nastaven bit přístupu PG_referenced (nejedná se o příznak přístupu nastavovaný hardwarem — procházíme fyzické stránky a ne mapování), byl tento příznak smazán a stránka přeskočena. Pokud byl příznak přístupu vynulován a stránka byla namapovaná, byla stránka přeskočena. Pokud byl příznak přístupu vynulován a stránka nebyla namapovaná, byla stránka uvolněna (nebylo třeba ji zapisovat, neboť v tomto stavu se mohly nacházet pouze čisté stránky).

Pokud se v první části algoritmu nepodařilo uvolnit určité množství stránek po určitém počtu kroků, spustila se druhá část. Tato část procházela cyklicky tabulky stránek všech procesů a podle principu „hodinového algoritmu” odmapovávala stránky. Pokud byl nastaven hardwarový příznak přístupu, byl snulován a stránka byla přeskočena. Pokud byl hardwarový příznak snulován, systém se podíval na hardwarový příznak modifikace. Jestliže byl nastaven, stránka byla zapsána do swap oblasti (a umístěna do swap cache) nebo do filesystému. Pokud byl hardwarový příznak modifikace vynulován, stránka byla odmapována a zmenšilo se její počítadlo použití. Až byla takto nalezena a zrušena všechna mapování, stránka mohla již být uvolněna první částí algoritmu.

Algoritmus byl vyvinut postupným vývojem, není moc čistý, ale ve většině druhů zátěže funguje rozumně. Balancuje mezi použitím paměti pro alokované stránky a pro cache. Stránky filesystémové cache jsou uvolňovány dříve (k jejich uvolnění stačí jen první část algoritmu), zatímco stránky namapované ze souboru nebo alokované potřebují k uvolnění obě části algoritmu. Nemůže tedy dojít k velikému vyswapovávání procesů při používání cache. Samotnou cache však je možno vytrashovat při čtení velkého souboru. Další nevýhodou algoritmu je, že při určitém vzoru přístupu do cache nejsou stránky procesů nikdy odmapovávány ani odswapovávány — i kdyby tyto stránky zůstaly v paměti netknuty libovolně dlouho.

Algoritmus výměny stránek na Linuxu 2.4

Do Linuxu 2.4 byl napsán lepší algoritmus výměny stránek, který částečně vychází z FreeBSD. Algoritmus má fronty podobně jako u FreeBSD: ACTIVE a INACTIVE (kdysi měl i frontu CACHE, ale byla odstraněna — nejspíš kvůli jednoduchosti). Každá stránka má příznak přístupu PG_referenced. Jedna část algoritmu (funkce refill_inactive) přesouvá stránky z ACTIVE fronty do INACTIVE. Počet přesunutých stránek roste, pokud je ACTIVE fronta větší. Stránky jsou přesouvány podle hodinového algoritmu (kdysi se používal page aging, ale nemělo to dobrý výsledek). Druhá část algoritmu (funkce shrink_caches) odstraňuje stránky z konce INACTIVE fronty a v případě nutnosti je zapisuje na disk. Tato část nebere ohled na příznak PG_referenced  — prostě odstraňuje stránky z konce fronty. Pokud má stránka mapování nebo nemůže být uvolněna z jiných důvodů, je přesunuta na začátek INACTIVE fronty. Je-li při průchodu nalezeno větší množství namapovaných stránek, pustí se třetí část algoritmu (funkce swap_out), která prochází tabulky stránek procesů a podle hodinového algoritmu stránky odmapovává. Tato část je podobná jako v jádrech 2.2 (až na to, že neprovádí zápis stránky do swapu) a dokonce obsahuje kód pocházející ze starých jader.

Algoritmus trochu komplikuje fakt, že je dělený na jednotlivé zóny (připomínám, že na IA32 máme tři zóny: ISA DMA (velikost 16M), přímo mapovaná zóna (velikost 1G) a ostatní stránky nad 1G. Na 64bitových architekturách je možno namapovat celou paměť a stačí tam jedna zóna). Pro každou zónu existuje zvlášť počítadlo volných stránek, pokud u některé zóny množství volných stránek dosáhne kritické hranice, spustí se algoritmus jen pro tu danou zónu. Jednotlivé funkce algoritmu jako parametr dostávají zónu a přeskakují stránky, které v dané zóně neleží. Fronty ACTIVE a INACTIVE existují jen jednou; na zóny děleny nejsou.

Pokud je stránka čtena pomocí funkce read, pokud je (v třetí části algoritmu) nalezeno mapování s příznakem přístupu nebo pokud je stránka namapována nějakému procesu, je zavolána funkce mark_page_acces­sed. Má-li stránka vynulován příznak PG_referenced, je tento příznak nastaven. Pokud stránka má nastaven příznak PG_referenced a je v INACTIVE frontě, je příznak vynulován a stránka je umístěna do ACTIVE fronty.

Tento algoritmus splňuje většinu požadavků kladených na systém virtuální paměti. Namapované stránky jsou odmapovávány jen tehdy, když se jich moc nalézá v INACTIVE frontě. Nehrozí tedy, že by čtení dlouhého souboru způsobovalo odswapovávání většího množství stránek. Pokud uživatel sekvenčně čte soubor, který je delší než paměť, zasáhne tento soubor pouze INACTIVE frontu. Protože každá stránka souboru je čtena pouze jednou, funkce mark_page_acces­sed jí nastaví příznak PG_referenced, ale nepřesune ji do ACTIVE fronty. Algoritmus stránku z konce INACTIVE fronty odstraní, aniž by se jakkoli dotkl stránek v ACTIVE frontě. Pokud byla stránka přečtena více než jednou, dostane se do ACTIVE fronty a odtud již nebude tak snadno odstraněna. Namapované stránky se vždy dostávají do ACTIVE fronty — začnou sice v INACTIVE s nastaveným PG_referenced, ale při prvním pokusu o odstranění mapování je zjištěn příznak přístupu na mapování a stránka je přesunuta do ACTIVE fronty.

Algoritmus výměny stránek na Linuxu 2.6

Na Linuxu 2.6 bylo přidáno reversní mapování, čímž se algoritmus výměny stránek se zjednodušil. Není již třeba procházet všechna mapování v systému, stačí procházet stránky a ke každé stránce je možno nalézt seznam mapování. Funkce refill_inactive_zone přesouvá stránky z ACTIVE fronty do INACTIVE. Byl zaveden nový parametr swappiness nastavitelný v proc, který určuje, jak moc bude systém swapovat nebo uvolňovat namapované stránky. Aby nedocházelo k přílišnému swapování procesů při práci s cachí, bude tato funkce přesouvat namapované stránky do INACTIVE fronty pouze pokud (poměr namapovaných stránek v procentech / 2 + swappiness + (100 >> log2(celkový počet stránek / počet projitých stránek v předchozím průchodu) > 100)). Možnost swapovat procesy roste, pokud systém prochází příliš mnoho stránek při uvolňování, pokud roste poměr namapovaných stránek nebo pokud správce nastaví vysoký swappiness. Moc šťastný mi tenhle algoritmus nepřipadá, neboť nejsou-li splněny tyto podmínky, algoritmus nebude swapovat vůbec žádné stránky, i když leží v paměti netknuté libovolně dlouho. Druhá část algoritmu ve funkci shrink_cache odebírá stránky z konce INACTIVE fronty a uvolňuje je. Přesouvání stránek do ACTIVE fronty při přístupu na ně je stejné jako na Linuxu 2.4.

Našli jste v článku chybu?

29. 11. 2009 23:13

Kusta (neregistrovaný)

No to LRU je popsane dosti vagne, nepresne a implementacne spatne. Davam palec dolu

9. 2. 2004 16:26

peto2 (neregistrovaný)

No, prelink je sice pekna vec, ale na KDE a pod. velke aplikacie to aj tak nefunguje (linkuju do libGL alebo co) a pri inych to nema moc velky efekt.

120na80.cz: Rovnátka, která nejsou vidět

Rovnátka, která nejsou vidět

DigiZone.cz: SES zajistí HD pro M7 Group

SES zajistí HD pro M7 Group

120na80.cz: Boreliózu nelze žádným testem prokázat

Boreliózu nelze žádným testem prokázat

Root.cz: Nová třída SD karet A1 s vysokým výkonem

Nová třída SD karet A1 s vysokým výkonem

DigiZone.cz: R2B2 a Hybrid uzavřely partnerství

R2B2 a Hybrid uzavřely partnerství

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

DigiZone.cz: V Plzni odstartovalo Radio 1

V Plzni odstartovalo Radio 1

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Vitalia.cz: Test na HIV je zdarma i za pět set

Test na HIV je zdarma i za pět set

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Vitalia.cz: To nejhorší při horečce u dětí: Febrilní křeče

To nejhorší při horečce u dětí: Febrilní křeče

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Vitalia.cz: Nejlepší obranou při nachlazení je útok

Nejlepší obranou při nachlazení je útok

DigiZone.cz: Sat novinky: slovenská TV8 HD i ruský NTV Mir

Sat novinky: slovenská TV8 HD i ruský NTV Mir

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Lupa.cz: Levný tarif pro Brno nebude, je to kartel

Levný tarif pro Brno nebude, je to kartel

Lupa.cz: Obchod budoucnosti je bez front, košíků i pokladen

Obchod budoucnosti je bez front, košíků i pokladen

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky