Subsystém pro správu paměti je jednou z nejdůležitějiích částí operačního systému. Už od prvních dnů výpočetní techniky bylo vždy zapotřebí více paměti, než kolik v systému fyzicky existovalo. Byly vyvinuty různé strategie jak toto omezení obejít, jednou z nejúspěšnějších je použití virtuální paměti. Virtuální paměť způsobuje, že se systém tváří jako kdyby měl více paměti než kolik ve skutečnosti má díky tomu, že se paměť podle potřeby sdílí mezi jednotlivými procesy.
Virtuální paměť toho ovšem zajišťuje více než jenom zvětšení objemu skutečné paměti. Subsystém správy paměti zajišťuje následující funkce:
Velký adresový prostor Operační systém způsobuje, že se systém chová, jako kdyby měl více paměti, než kolik ve skutečnosti má. Velikost virtuální paměti může být mnohonásobně větší než velikost skutečné fyzické paměti v systému.
Ochrana Každý proces v systému má vlastní virtuální adresový prostor. Virtuální adresové prostory jsou vzájemně úplně odděleny a běžící proces jedné aplikace tak nemůže nijak ovlivnit jiné procesy. Navíc mohou hardwarové mechanismy virtuální paměti chránit určité oblasti paměti před zápisem. Tím se kód a data chrání před přepsáním chybnými aplikacemi.
Mapování paměti Mapování paměti slouží k mapování obrazů programu a datových souborů do adresového prostoru procesu. Při použití paměťového mapování je obsah souboru přímo svázán s virtuálním adresovým prostorem procesu.
Alokace fyzické paměti Subsystém správy paměti umožňuje každému spuštěnému procesu alokovat spravedlivý díl fyzické paměti systému.
Sdílení virtuální paměti Přestože virtuální paměť umožňuje, aby procesy měly oddělené (virtuální) adresové prostory, jsou situace, kdy je vhodné sdílet paměť mezi více procesy. V systému může být například více procesů, které provádějí příkaz bash. Není nutné mít v paměti více kopií programu bash, každý v adresovém prostoru jednoho procesu, je lepší mít ve fyzické paměti pouze jedinou kopii, kterou budou příslušné procesy sdílet. Dalším běžným příkladem sdílení kódu mezi více procesy jsou například dynamické knihovny. Sdílenou paměť je možno využít také jako mechanismus pro meziprocesovou komunikaci, kdy si dva nebo více procesů vyměňují informace prostřednictvím paměťové oblasti, kterou společně sdílejí. Linux podporuje meziprocesovou komunikaci sdílením paměti mechanismem Unix System V IPC.
Před popisem metod, které Linux používá pro podporu virtuální paměti, bude užitečné seznámit se s abstraktním modelem, který nebude zatížen poíl"nými detaily.
Když procesor provádí program, načítá z paměti instrukce a dekóduje je. Při dekódování instrukcí může potřebovat načíst nebo zapsat z nebo na určité místo paměti. Pak procesor instrukci provede a přesune se na následující instrukci programu. Procesor tedy neustále přistupuje k paměti, aš už načítáním instrukce nebo načítáním či zápisem dat.
Při použití virtuální paměti jsou všechny adresy virtuální, nejsou to adresy fyzické. Virtuální adresy překládá na fyzické adresy procesor podle informací v tabulkách, udržovaných operačním systémem.
Aby se překlad zjednodušil, je virtuální i fyzická paměť rozdělena na pohodlně manipulovatelné části, takzvané stránky. Všechny stránky jsou stejně veliké. Teoreticky by sice nemusely být, ale kdyby nebyly, celý systém by se jen velmi obtížně spravoval. Linux na systémech s procesorem Alpha AXP používá stránky o velikosti 8 KB, systémy s procesorem Intel x86 používají stránky o velikosti 4 KB. Každá stránka je označena jedinečným číslem, číslem rámce stránky (PFN).
V takovémto stránkovém modelu se virtuální adresa skládá ze dvou částí: offsetu a čísla rámce virtuální stránky. Vezmeme-li stránku o velikosti 4 KB, bity 11 až 0 virtuální adresy jsou offset a bity 12 a výše představují číslo rámce stránky. Procesor musí přeložit číslo rámce virtuální stránky na fyzickou a poté ve fyzické stránce přistoupit na místo se správným offsetem.
K této činnosti procesor používá tabulky stránek.
Na obrázku 3.1 vidíme virtuální adresový prostor dvou procesů, procesu X a procesu Y, každý má svou vlastní tabulku stránek. Tyto tabulky mapují každou virtuální stránku procesu na fyzickou stránku paměti. Vidíme, že virtuální stránka 0 procesu X je mapována na fyzickou stránku 1, virtuální stránka 1 procesu Y se mapuje na fyzickou stránku 4. Každá položka v naší pomyslné tabulce stránek musí obsahovat následující informace:
K tabulce stránek se přistupuje tak, že číslo rámce virtuální stránky slouží jako offset v tabulce stránek. Virtuální stránka 5 tedy bude šestou položkou tabulky (první položkou je stránka 0).
Při překladu virtuální adresy na fyzickou musí procesor nejprve zjistit číslo rámce virtuální stránky a poté offset v tabulce virtuálních stránek. Když je velikost stránky mocninou dvou, dají se tyto operace snadno provádět pomocí bitového maskování a posuvů. Podívejme se znovu na obrázek 3.1 a předpokládejme stránku o velikosti 0x2000 bajtů (desítkově 8192) a adresu 0x2194 ve virtuálním adresovém prostoru procesu Y, kterou procesor přeloží jako adresu na offsetu 0x194 ve virtuální stránce 1.
Číslo rámce virtuální stránky procesor použije jako index do tabulky stránek a získá tak položku tabulky pro danou stránku. Pokud je položka tabulky s daným offsetem platná, procesor z ní převezme číslo rámce fyzické paměti. Pokud položka není platná, proces se pokouší o přístup k neexistující oblasti virtuální paměti. V takovém případě procesor nemůže provést překlad adresy a musí předat řízení operačnímu systému, který problém vyřeší.
Jak ale procesor doručí operačnímu systému zprávu o tom, že se nějaký proces pokusil o přístup k oblasti virtuální paměti, kterou procesor nemohl přeložit na fyzickou adresu? Ať už je mechanismus předání zprávy jakýkoliv, této události se obecně říká výpadek stránky a operační systém je upozorněn na výpadek virtuální paměti a na okolnosti, za kterých k tomu došlo.
Pokud se proces odkazuje na platnou položku tabulky stránek, procesor vezme číslo fyzického rámce stránky a vynásobí jej velikostí stránky, takže získává bázovou adresu stránky ve fyzické paměti. K této adrese se přičte offset instrukce nebo dat, která se požadují.
Když se budeme držet našeho předchozího příkladu, mapuje se virtuální stránka 1 procesu Y na fyzickou stránku 4, která začíná na adrese 0x8000 (4 ´ 0x2000). Přičtením bajtového offsetu 0x194 se dostáváme na fyzickou adresu 0x8194.
Tento mechanismus mapování virtuálních adres na fyzické umožňuje, aby se stránky virtuální paměti mapovaly na fyzické stránky v libovolném pořadí. Například na obrázku 3.1 se virtuální stránka 0 procesu X mapuje na fyzickou stránku 1, zatímco virtuální stránka 7 se mapuje na fyzickou stránku 0, přestože se jedná o vyšťí virtuální adresu, než je adresa stránky 0.
To nám ukazuje zajímavý vedlejší efekt virtuální paměti - stránky virtuální paměti nemusejí být ve fyzické paměti přítomny v žádném pevném pořadí.
Protože fyzické paměti je v systému méně než paměti virtuální, musí být operační systém velmi opatrný na to, aby neplýtval fyzickou pamětí. Jedna možnost jak ušetřit fyzickou paměť je nahrávat pouze ty virtuální stránky, které právě spuitiný program opravdu potřebuje. Mějme například spuštěn nějaký databázový program, který něco hledá v databázi. V takovém případě není nutné, aby byla do paměti nahrána celá databáze, stačí nahrát pouze ty záznamy, které se momentálně zkoumají. Pokud databázi prohledáváme, není nutné mít v paměti zároveň nahránu tu část programu, která zajišťuje přidávání nových záznamů. Této metodě nahrávání pouze potřebných stránek se říká vynucené stránkování.
Když se proces pokusí o přístup k virtuální adrese, která momentálně není v paměti, procesoru se nepodaří pro požadovanou stránku najít platný záznam v tabulce stránek. Například podle obrázku 3.1 není v tabulce stránek procesu X platná položka pro virtuální stránku 2, takže pokud by se proces X pokusil o čtení virtuální adresy ve druhé stránce, procesoru by se nepodařilo provést překlad na fyzickou adresu. V této chvíli procesor upozorní operační systém na fakt, že došlo k výpadku stránky.
Pokud je virtuální adresa neplatná, znamená to, že aplikace se pokusila o přístup k adrese, k níž by přistupovat neměla. Aplikace třeba někam zabloudila a pokouší se nyní zapisovat na nějakou náhodnou adresu. V takovém případě ji operační systém ukončí, čímž chrání ostatní procesy v systému před chybnou aplikací.
Pokud je ale adresa platná a odkazovaná stránka momentálně není v paměti, musí operační systém přesunout tuto stránku do paměti z obrazu paměti uloženého na disku. Diskové přístupy trvají relativně dlouho, takže proces bude muset počkat, než dojde k načtení stránky. Pokud jsou v systému současně jiné procesy, které běžet mohou, nechá operační systém mezitím pracovat tyto procesy. Načtená stránka se zapíše do některé volné stránky fyzické paměti a do tabulky stránek procesu se doplní záznam ke dříve požadované virtuální stránce. Proces se pak znovu spustí na stejné instrukci, která vyvolala výpadek stránky. Tentokrát se při přístupu do virtuální paměti procesoru podaří přeložit virtuální adresu na fyzickou a proces tedy může pokračovat v práci.
Linux používá vynucené stránkování při nahrávání obrazů spustitelných souborů do virtuální paměti procesů. Když je spuštěn nějaký příkaz, otevře se soubor, který jej obsahuje, a jeho obsah se namapuje do virtuální paměti procesu. Dosáhne se toho modifikací datových struktur jádra, které popisují paměťovou mapu procesu a celý postup se označuje jako mapování paměti.
Nicméně do fyzické paměti se nahraje pouze první část obrazu programu. Zbytek zůstává na disku. Když se obraz provádí, generuje výpadky stránek a Linux pomocí paměťové mapy procesu zjišťuje, které části obrazu je potřeba nyní přenést do paměti a nechat je proběhnout.
Když proces potřebuje přenést do fyzické paměti nějakou stránku a ve fyzické paměti není žádná stránka volná, musí operační systém pro požadovanou stránku vytvořit místo tím, že ve fyzické paměti zruší nějakou jinou stránku.
Pokud rušená stránka pochází z obrazu spustitelného souboru nebo z datového souboru do nějž nebylo zapisováno, není nutné stránku ukládat. Je možno ji přímo zrušit a pokud by ji příslušný proces potřeboval znovu, načetla by se zpátky do paměti z příslušného obrazu nebo datového souboru.
Pokud ale stránka byla modifikována, musí operační systém zachovat její obsah tak, aby k ní bylo možno později opět přistupovat. Tomuto typu stránek se říká modifikované (dirty) stránky a při jejich odstraňování z paměti se ukládají do speciálního souboru, zvaného odkládací soubor. Přístupy k odkládacímu souboru jsou výrazně pomalejší než přístupy k fyzické paměti a operační systém tedy musí pečlivě balancovat mezi potřebami zapisovat stránky na disk a potřebami znovu je načítat při dalším použití.
Pokud je algoritmus používaný k rozhodnutí o tom, které stránky zrušit či odkládat (takzvaný odkládací algoritmus) neefektivní, dochází k situaci zvané thrashing - stránky se neustále zapisují na disk a čtou z disku a operační systém je vytížen natolik, že nemá čas na pořádnou práci. Pokud by například bylo často přistupováno k fyzické stránce 1 na obrázku 3.1, pak tato stránka není vhodným kandidátem pro odložení na disk. Množina stránek, které proces momentálně používá, se nazývá pracovní prostor. Efektivní odkládací mechanismus musí zajistit, aby pracovní prostor každého procesu byl přítomen ve fyzické paměti.
Linux používá k volbě stránek, které se mají z paměti odsunout, mechanismus zvaný LRU Least Recently Used, tedy česky "nejdávněji použitáiě. Podle tohoto schématu má každá stránka v systému svůj "věkim) který se mění s přístupem ke stránce. Čím častěji se ke stránce přistupuje, tím je "mladšíim) méně navýtěvovaná stránka je starší a stále stárne. Dobrým kandidátem na odložení jsou právě staré stránky.
Virtuální paměť zjednodušuje sdílení paměti mezi několika procesy. Všechny přístupy do paměti se provádějí přes tabulky stránek a každý proces má svou vlastní tabulku stránek. Pokud mají dva procesy sdílet stejný kus fyzické paměti, objeví se v tabulkách stránek obou procesů stejné číslo fyzického paměťového rámce.
Na obrázku 3.1 vidíme dva procesy, které sdílejí fyzickou stránku 4. Pro proces X je to virtuální stránka 4, zatímco pro proces Y je to virtuální stránka 6. Tím se ukazuje zajímavý rys sdílení stránek: sdílené fyzické stránky se nemusejí ve virtuálním adresovém prostoru procesů, které je sdílejí, nacházet na stejných místech.
Není příliš rozumné, aby samotný operační systém běžel ve virtuální paměti. Bylo by dost příšerné, kdyby operační systém musel udržovat tabulku stránek i sám pro sebe. Většina univerzálních procesorů podporuje jak fyzický adresovací režim, tak virtuální adresovací režim.
Fyzický adresovací režim nepotřebuje žádné tabulky stránek a v tomto režimu procesor neprovádí žádné překlady adres. Jádro Linuxu je sestaveno tak, aby pracovalo ve fyzickém adresovacím režimu.
Procesor Alpha AXP nemá žádný zvláýtní fyzický adresovací režim. Namísto toho rozděluje paměťový prostor na několik oblastí a dvě z nich určuje jako oblasti s fyzicky mapovanými adresami. Tento adresový prostor jádra se označuje jako segment KSEG a zahrnuje všechny adresy od 0xfffffc0000000000 nahoru. Aby bylo možno provádět kód v segmentu KSEG (podle definice kód jádra) a přistupovat k datům v této oblasti, musí kód běžet v režimu jádra. Jádro Linuxu pro procesory Alpha je sestaveno tak, aby se spouštělo od adresy 0xfffffc0000310000.
Záznamy v tabulkách stránek obsahují také informace o řízení přístupu. Protože procesor tyto tabulky využívá pro mapování virtuálních adres procesů na fyzické, může při té příležitosti použít i informace o řízení přístupu ke kontrole, zda proces nepřistupuje k paměti nepovoleným způsobem.
Existuje řada důvodů proč omezovat přístup do různých oblastí paměti. Některé části paměti, například ty, kde je uložen spustitelný kód, jsou přirozeně určeny pouze pro čtení, operační systém by neměl procesu dovolit přepisovat data přes svůj spustitelný kód. Naopak stránky obsahující data je možno modifikovat, neměl by se však podařit pokus o provedení obsahu těchto stránek jako programu. Většina procesorů má nejméně dva režimy běhu programů: režim jádra a uživatelský režim. Zřejmě nebudete chtít, aby byl kód jádra a jeho datové struktury přístupné, pokud proces neběží v režimu jádra.
Informace pro řízení přístupu jsou udržovány v PTE (položkách tabulek stránek) a jsou procesorově závislé. Na obrázku 3.2 vidíme strukturu PTE procesoru Alpha AXP. Jednotlivé bity mají následující význam:
Následující dva bity jsou definovány a využívány Linuxem:
Pokud byste chtěli systém implementovat podle právě popsaného teoretického modelu, systém by sice mohl fungovat, nepracoval by ale příliý efektivně. Návrháři operačních systémů i procesorů usilují o co největší zvýšení výkonu systému. Kromě zrychlení samotného procesoru, paměti a dalších prvků je nejlepší řešení použití vyrovnávacích pamětí pro užitečné informace a data, které zajistí rychlejší provádění některých operací. Při správě paměti využívá Linux řadu vyrovnávacích pamětí.
Když dojde k odkazu na virtuální adresu, procesor se pokusí najít potřebnou položku TLB.
Pokud ji najde, může virtuální adresu přímo přeložit na fyzickou adresu a provést požadovanou datovou operaci. Pokud se procesoru nepodaří najít potřebnou položku TLB, musí požádat o pomoc operační systém. Provede to tak, že signalizuje výpadek bloku TLB. Systémově závislé mechanismy zajistí doručení této výjimky operačnímu systému, který může problém napravit. Operační systém vygeneruje novou položku TLB pro požadované mapování. Po ošetření výjimky se procesor opět pokusí o překlad virtuální adresy. Tentokrát už všechno bude fungovat, protože pro požadovanou adresu existuje potřebný blok TLB.
Nevýhodou použití vyrovnávacích pamětí, aš už hardwarových nebo jiných, je, že kvůli ušetření práce musí Linux věnovat více času a prostoru údržbě vyrovnávacích pamětí a pokud by došlo k porušení obsahu vyrovnávacích pamětí, celý systém se zhroutí.
Linux předpokládá tři úrovně tabulky stránek. Každá tabulka stránek obsahuje číslo rámce stránky tabulky stránek další úrovně. Na obrázku 3.3 je vidět, jak se virtuální adresa rozpadá na řadu položek, každá z nich představuje offset v určité tabulce stránek. Při překladu virtuální adresy na fyzickou musí procesor vzít obsah položky na každé úrovni, konvertovat jej na offset ve fyzické paměti obsahující tabulku stránek a načíst číslo rámce stránky další úrovně tabulky stránek. Toto se opakuje třikrát až dojde k nalezení čísla rámce fyzické stránky, která obsahuje požadovanou virtuální adresu. V tom okamžiku se použije poslední pole virtuální adresy, bajtový offset, kterým se naleznou požadovaná data ve stránce.
Každá platforma, na níž Linux běží, musí zajistit překladová makra pro průchod tabulkou stránek procesu. Díky tomu jádro nemusí znát formát položek tabulky stránek ani jejich uspořádání.
Toto řešení je natolik úspěšné, že Linux může používat stejný kód pro manipulaci s tabulkami stránek pro procesor Alpha, který pracuje se třemi úrovněmi tabulky stránek, i pro procesor Intel x86, který používá pouze dvouúrovňovou tabulku.
V systému se vyskytuje velká řada požadavků na fyzické stránky. Když například dochází k nahrávání obrazu kódu do paměti, systém potřebuje alokovat stránky. Tyto stránky budou uvolněny až kód skončí svou práci. Další použití fyzických stránek je pro uložení datových struktur jádra, jako například samotných tabulek stránek. Mechanismy a datové struktury používané pro alokování a dealokování stránek jsou pravděpodobně nejkritičtější pro efektivnost celého subsystému virtuální paměti.
Všechny fyzické stránky jsou popsány datovou strukturou mem_map, což je seznam struktur mem_map_t, které se inicializují při zavádění systému. Každá struktura mem_map_t popisuje jednu fyzickou stránku v systému. Důležitými položkami struktury (co se týče správy paměti) jsou následující položky:
Vektor free_area slouží kódu alokace stránek k nalezení volných stránek. Tímto mechanismem je podporováno celé schéma správy bufferů a co se týče samotného kódu, velikost stránky a fyzický stránkovací mechanismus konkrétního procesoru jsou irelevantní.
Každý prvek struktury free_area obsahuje informace o bloku volných stránek. První prvek pole popisuje samostatné stránky, druhý prvek bloky o dvou stránkách, následující prvek bloky o čtyřech stránkách a tak dále s krokem po mocninách dvou. Položka list se používá jako začátek fronty a obsahuje ukazatel na datové struktury page v poli mem_map. Zde se řadí do fronty bloky stránek. map je ukazatel na bitovou mapu, která obsahuje záznamy o alokovaných skupinách stránek dané velikosti. N-tý bit této bitové mapy je nastaven, pokud je N-tý blok stránek volný.
Na obrázku 3.4 vidíme strukturu free_area. Prvek 0 má jednu volnou stránku (stránku s číslem rámce 0) a prvek 2 má dva volné bloky o čtyřech stránkách, první začíná stránkou s číslem rámce 4 a druhý stránkou s číslem rámce 56.
K efektivní alokaci a dealokaci bloků stránek používá Linux Buddyho algoritmus. Kód pro alokování stránek se pokouší alokovat blok jedné nebo více fyzických stránek. Stránky se alokují v blocích o velikosti mocniny dvou. Znamená to tedy, že můžete alokovat blok o jedné stránce, dvou stránkách, čtyřech stránkách a tak dále. Dokud je v systému dostatek volných stránek, aby mohl být požadavek splněn (nr_free_pages > min_free_pages), bude alokační kód prohledávat strukturu free_area a bude hledat blok o požadovaném počtu stránek.
Každý prvek seznamu free_area je mapa alokovaných a volných bloků stránek dané velikosti. Například prvek 2 pole je paměťová mapa, která popisuje volné a alokované bloky o velikosti 4 stránky.
Alokační algoritmus nejprve hledá bloky stránek požadované velikosti. Prochází seznamem volých stránek který je seřazen v prvku list datové struktury free_area. Pokud není nalezen žádný volný blok požadované velikosti, hledá se volný blok o větší velikosti (tedy blok dvakrát větší než požadovaný). Tento proces pokračuje do doby, než je prohledána celá struktura free_area nebo než bude nalezen vhodný blok stránek. Pokud je nalezen blok stránek o větší než požadované velikosti, musí se rozdělit na blok požadované velikosti. Protože velikosti bloků jsou vždy mocninami dvou, dělení bloků na menší části je prostě jenom jejich půlení.Volné bloky se zařadí do příslušné fronty a alokovaný blok stránek se vrátí volajícímu procesu.
Pokud si vezmeme například obrázek 3.4 a budeme požadovat blok o velikosti dvě stránky, dojde k rozdělení prvního bloku o čtyřech stránkách (který začíná stránkou s číslem rámce 4) na dva dvoustránkové bloky. První z nich, začínající na stránce s rámcem 4, bude vrácen volajícímu procesu jako požadovaný blok, druhý blok, začínající stránkou s číslem rámce 6, bude zařazen do fronty volných dvoustránkových bloků v prvku 1 pole free_area.
Alokování bloků stránek vede k fragmentaci paměti, kdy se větší bloky volných stránek rozbíjejí na menší. Dealokační kód rekombinuje stránky zpět na větší bloky vždy když je to možné.
Velikost vraceného bloku stránek je významná, protože umožňuje snadnou kombinaci bloků na větší bloky.
Vždy když dojde k uvolnění bloku stránek, kontroluje se, zda není volný sousední blok stránek o stejné velikosti. Pokud ano, pak se oba dva bloky zkombinují do nového volného bloku o dvojnásobné velikosti. Pokaždé když dojde k rekombinaci dvou bloků do většího bloku, pokusí se dealokační kód rekombinovat tento blok do ještě většího bloku. Díky tomu budou bloky volných stránek vždy tak velké, jak to jen využití paměti dovolí. Například pokud by na obrázku 3.4 došlo k uvolnění stránky s číslem rámce 1, zkombinovala by se s už volnou stránkou s číslem rámce 0 a výsledný blok by byl zařazen do prvního prvku struktury free_area jako blok o velikosti 2 stránky.
Když dochází k vykonávání obrazu programu, musí se obraz spustitelného kódu přenést do virtuálního adresového prostoru procesu. To platí i pro všechny sdílené knihovny, které jsou ke spustitelnému obrazu přilinkovány. Spustitelný soubor se fakticky nepřenáší do fyzické paměti, dojde pouze k jeho napojení na virtuální paměť procesu. Pak, když se spuštěná aplikace odkazuje na danou část programu, dojde k přenesení spustitelného obrazu do paměti. Toto napojení obrazu na virtuální adresový prostor procesu se označuje jako mapování paměti.
Virtuální paměť každého procesu je reprezentována datovou strukturou mm_struct. Ta obsahuje informace o právě prováděném obrazu (například bash) a dále ukazatele na řadu datových struktur vm_area_struct. Každá datová struktura vm_area_struct popisuje začátek a konec oblasti virtuální paměti, přístupová práva procesu do této oblasti a operace pro tuto oblast paměti. Tyto operace jsou vlastně rutiny, které Linux musí používat při manipulaci s touto oblastí virtuální paměti. Například jednou z operací nad oblastí virtuální paměti je provedení správné akce v případě, kdy se proces pokusí o přístup do této oblasti, ale zjistí (prostřednictvím výpadku stránky), že požadovaná oblast není momentálně ve fyzické paměti. Této operaci se říká operace nopage. Operace nopage se používá když Linux potřebuje vynutit přítomnost stránky spustitelného obrazu v paměti.
Když se spustitelný obraz mapuje do virtuální paměti procesu, generují se datové struktury vm_area_struct. Každá struktura vm_area_struct představuje část spustitelného obrazu: spustitelný kód, inicializovaná data (proměnné), neinicializovaná data a další. Linux podporuje řadu standardních operací nad virtuální pamětí a když dochází k vytváření struktury vm_area_struct, přiřadí se jí správná množina operací nad virtuální pamětí.
Jakmile je spustitelný obraz namapován do virtuální paměti procesu, může se začít provádět.
Protože je v paměti fyzicky přítomen pouze úplný začátek spustitelného obrazu, dojde záhy k přístupu do oblasti virtuální paměti, která ještě není umístěna ve fyzické paměti. Když se proces pokouší o přístup k virtuální adrese, která nemá platnou položku tabulky stránek, procesor ohlásí Linuxu výpadek stránky.
Výpadek stránky oznamuje virtuální adresu, na níž došlo k výpadku, i typ paměťové operace, která výpadek způsobila.
Linux musí nalézt strukturu vm_area_struct té oblasti paměti, v níž došlo k výpadku stránky. Prohledávání struktur vm_area_struct je kritické pro efektivní obsluhu výpadků stránek, proto jsou struktury propojeny do takzvaného stromu AVL (Adělson-Velski a Landis) stromu. Pokud pro vypadlou virtuální adresu neexistuje datová struktura vm_area_struct, pokusil se proces o přístup na nelegální virtuální adresu. Linux odeýle procesu signál SIGSEGV a pokud proces tento signál neobslouží, bude ukončen.
Dále Linux kontroluje typ vzniklého výpadku stránky proti typům přístupu povoleným v této oblasti virtuální paměti. Pokud se proces pokouší přistupovat k paměti nepovoleným způsobem, řekněme že chce zapisovat někam, kde je povoleno pouze čtení, bude mu rovněž signalizována paměťová chyba.
Když Linux zjistí, že výpadek stránky je legální, musí jej obsloužit.
Linux musí rozliýovat mezi stránkami uloženými v odkládacím souboru a mezi stránkami, které jsou součástí spustitelného obrazu někde na disku. Zjistí to podle položky tabulky stránek pro vypadlou stránku.
Pokud je položka tabulky stránek neplatná, ale neprázdná, znamená to, že vypadlá stránka je momentálně držena v odkládacím souboru. U položek tabulky stránek procesoru Alpha AXP jsou to ty položky, které nemají nastaven příznak platnosti, v poli PFN však obsahují nenulovou hodnotu. V tomto případě obsahuje PFN informaci o tom, kde v odkládacím souboru (a ve kterém odkládacím souboru) je stránka uložena. Jak jsou obsluhovány stránky uložené v odkládacím souboru bude popsáno dále v této kapitole.
Ne všechny datové struktury vm_area_struct mají přiděleny operace nad virtuální pamětí, a dokonce i ty, které je přiděleny mají, nemusejí mít přidělenu operaci nopage. Je to dáno tím, že implicitně Linux řeší přístup alokováním nové fyzické stránky a vytvořením platné položky tabulky stránek pro tuto stránku. Pokud není pro danou oblast paměti definována operace nopage, provede Linux implicitní obsluhu.
Obecná operace nopage se používá pro paměťově mapované spustitelné obrazy a používá vyrovnávací paměť stránek k přenesení požadovaného obrazu stránky do fyzické paměti.
Ať už dojde k přenosu stránky do fyzické paměti jakýmkoliv způsobem, provede se aktualizace tabulky stránek procesu. Při aktualizaci tabulky může být potřebné provést i nějaké hardwarově závislé operace, zejména pokud procesor používá interní překladové buffery. Nyní tedy byl výpadek stránky obsloužen, dále se o něj nestaráme a spouštíme proces znovu od instrukce, která výpadek stránky vyvolala.
Úkolem vyrovnávací paměti stránek je zrychlit přístup k souborům na disku. Paměťově mapované soubory se načítají po jednotlivých stránkách a ty se ukládají do vyrovnávací paměti stránek. Na obrázku 3.6 vidíme, že vyrovnávací paměť stránek se skládá ze struktury page_hash_table, vektoru ukazatelů na datové struktury mem_map_t.
Každý soubor v Linuxu je identifikován datovou strukturou inode subsystému VFS (popsaného v kapitole Souborový systém). Každý inode je jedinečné číslo a plně odpovídá jednomu a právě jednomu souboru. Index do tabulky stránek se odvozuje od inode souboru a offsetu v tomto souboru.
Vždy, když se z paměťově mapovaného souboru načítá stránka, například pokud vznikl požadavek na přenesení do paměti v důsledku vynuceného stránkování, načítá se stránka přes vyrovnávací paměť stránek. Pokud je stránka ve vyrovnávací paměti přítomna, vrací se kódu obsluhy výpadku stránky ukazatel na strukturu mem_map_t, která odpovídá požadované stránce. V opačném případě se musí stránka přenést do paměti ze souborového systému. Linux provede alokaci fyzické stránky a načte stránku ze souboru na disku.
Pokud je to možné, zahájí Linux rovněž načtení následující stránky ze souboru. Toto jednoduché dopředné čtení jedné stránky znamená, že pokud proces přistupuje ke stránkám v lineárním pořadí (což je pravděpodobné), bude mít v okamžiku požadavku na další stránku tuto stránku už připravenu.
Postupem času se obsah vyrovnávací paměti stránek rozrůstá, tak jak dochází k načítání a vykonávání obrazů. Stránky se z vyrovnávací paměti odstraňují v okamžiku, kdy nejsou déle potřebné, tedy pokud není daný obraz používán žádným procesem. Když Linux pracuje s pamětí, mohou mu začít chybět fyzické stránky. V takovém případě provede snížení velikosti vyrovnávací paměti stránek.
Když začne chybět fyzická paměť, musí se subsystém správy paměti pokusit o uvolnění fyzických stránek. Tento úkol plní odkládací démon jádra, kswapd.
Odkládací démon je speciální typ procesu, jde o vlákno jádra. Vlákna jádra jsou procesy, které nemají žádnou virtuální paměť a běží v režimu jádra ve fyzickém adresovém prostoru. Označení "odkládací démonid je poněkud zavádějící, protože tento démon toho dělá daleko více, než jen prosté odložení stránek do systémových odkládacích souborů. Jeho úkolem je zajistit v systému dostatek volných stránek, aby mohl systém správy paměti pracovat efektivně.
Odkládací démon jádra (kswapd) je spuštěn procesem init jádra při startu systému a sedí a čeká na periodické spouštění odkládacím časovačem jádra.
Vždy, když přijde zpráva od časovače, démon se podívá, zda v systému nezačínají chybět fyzické stránky. K rozhodování, zda uvolnit nějaké stránky, používá dvě proměnné, free_pages_high a free_pages_low. Dokud je počet volných stránek větší než hodnota free_pages_high, nedělá démon nic, spí dál, dokud jej časovač příýtě neprobudí. Pro potřeby těchto testů pracuje odkládací démon s počtem stránek, které jsou momentálně zapisovány do odkládacího souboru. Tento počet je uchováván v proměnné nr_async_pages, jejíž hodnota se inkrementuje vždy při zařazení stránky do fronty na zápis do odkládacího souboru a dekrementuje se vždy, když se dokončí zápis stránky na odkládací zařízení. Hodnoty free_pages_low a free_pages_high se nastavují při startu systému a odvozují se od celkového počtu fyzických stránek v systému. Pokud počet volných stránek klesne pod hodnotu free_pages_high nebo dokonce pod hodnotu free_pages_low, pokusí se odkládací démon třemi způsoby snížit počet obsazených fyzických stránek:
Pokud počet volných stránek klesne pod hodnotu free_pages_low, pokusí se odkládací démon uvolnit šest paměťových stránek. V opačném případě se pokouší uvolnit pouze tři stránky. Všechny tři výše uvedené metody se cyklicky opakují dokud není uvolněno dostatečné množství stránek. Odkládací démon si pamatuje, kterou metodu použil při posledním pokusu o uvolnění fyzických stránek. Při každém spuštění začíná uvolňovat stránky tou metodou, která posledně uspěla.
Jakmile uvolní dostatek stránek, odkládací démon usíná a čeká na další probuzení časovačem.
Pokud byl důvodem pro uvolňování stránek pokles počtu volných stránek pod hodnotu free_pages_low, bude démon spát pouze polovinu svého normálního spacího času. Jakmile se počet volných stránek vyhoupne nad hodnotu free_pages_low, spí už démon mezi jednotlivými kontrolami svou normální dobu.
Stránky držené ve vyrovnávacích pamětech bufferů a stránek jsou dobrými kandidáty na uvolnění ve vektoru free_area. Vyrovnávací paměť stránek, která obsahuje stránky paměťově mapovaných souborů, může obsahovat nepotřebné stránky, které zbytečně zaplňují paměť. Podobně buffery, obsahující data čtená a zapisovaná z/na fyzická zařízení, mohou obsahovat nepotřebné údaje. Když začnou docházet fyzické stránky, je poměrně jednoduché zrušit stránky ve vyrovnávacích pamětech, protože k tomu není nutné provádět zápis na fyzická zařízení (což by bylo nutné při odkládání stránek z paměti). Zrušení takovýchto stránek nemá žádný výrazný vedlejší efekt kromě toho, že se zpomalí přístup k fyzickým zařízením a paměťově mapovaným souborům. Pokud se ovšem rušení stránek z vyrovnávacích pamětí provede spravedlivě, dotkne se to stejným dílem všech procesů.
Vždy, když se odkládací démon jádra pokouší snížit velikost vyrovnávacích pamětí, prozkoumá blok stránek ve stránkovém vektoru mem_map a zjistí, zda je možno nějaké stránky uvolnit z fyzické paměti. Velikost zkoumaných bloků stránek je tím vyšťí, čím více démon odkládá, tedy čím níže poklesl počet volných fyzických stránek. Bloky stránek se zkoumají cyklicky, při každém pokusu o uvolnění stránek se prověřují jiné bloky. Tento postup se označuje jako hodinový algoritmus, protože podobně jako u pohybu minutové ručičky hodinek dojde vždy po několika voláních nakonec k prohlédnutí celého vektoru mem_map.
U každé zkoumané stránky se zjistí, zda je uložena ve vyrovnávací paměti stránek nebo v bufferu. Všimněte si, že v tomto okamžiku se neuvažuje o rušení sdílených stránek a že stránka nemůže být současně v obou vyrovnávacích pamětech. Pokud stránka není v žádné z vyrovnávacích pamětí, prozkoumá se následující stránka vektoru mem_map.
Stránky se ukládají ve vyrovnávacích bufferech (nebo přesněji, stránky v sobě obsahují buffery), čímž se zefektivňuje alokace a dealokace bufferů. Kód snížení počtu obsazených stránek se pokouší uvolnit buffery uložené ve zkoumané stránce.
Pokud se podaří uvolnit všechny buffery, je možno uvolnit i samotnou stránku. Pokud je taková stránka uložena ve vyrovnávací paměti stránek, odstraní se z ní a uvolní se.
Pokud se při tomto postupu podaří uvolnit dostatek fyzických stránek, čeká odkládací démon na další pravidelné probuzení. Protože žádná z uvolněných stránek nebyla součástí virtuálního adresového prostoru nějakého procesu (jednalo se o stránky vyrovnávacích pamětí), není nutné modifikovat tabulky stránek. Pokud se nepodaří uvolnit dostatek stránek vyrovnávacích pamětí, pokusí se odkládací démon odložit nějaké sdílené stránky.
Sdílená paměť Systemu V je meziprocesový komunikační mechanismus, kdy dva nebo více procesů sdílejí část své virtuální paměti, aby si mohly vzájemně předávat informace. Způsob, jakým se paměť mezi procesy sdílí, je podrobněji popsán v kapitole o meziprocesové komunikaci. Nám v této chvíli stačí vědět, že sdílená paměť Systemu V je popsána datovou strukturou shmid_ds. Tato struktura obsahuje ukazatel na seznam datových struktur vm_area_struct, jednu pro každý proces sdílející danou oblast virtuální paměti. Datové struktury vm_area_struct říkají, kam ve virtuálním adresovém prostoru daného procesu se má mapovat daná sdílená oblast paměti. Jednotlivé datové struktury vm_area_struct jsou navzájem provázány ukazateli vm_next_shared a vm_prev_shared. Každá datová struktura shmid_ds navíc obsahuje seznam položek tabulek stránek, které popisují fyzické stránky, na něž se virtuální sdílené stránky mapují.
Odkládací démon jádra používá při odkládání sdílených stránek Systemu V hodinový algoritmus. Vždy, když je spuštěn, pamatuje si, kterou oblast sdílené virtuální paměti naposledy odložil. K tomu používá dva údaje, první je index do množiny datových struktur schmid_ds, druhý je index do seznamu položek tabulek stránek dané oblasti sdílené paměti. Tím je zajištěno, že stránky sdílené paměti jsou "obitoványi. spravedlivě.
Protože číslo rámce fyzické stránky sdílené virtuální stránky je uloženo v tabulkách stránek všech procesů, které danou oblast virtuální paměti sdílejí, musí odkládací démon jádra modifikovat všechny tyto tabulky aby se indikovalo, že stránka už není v paměti a je držena v odkládacím souboru. Při odkládání každé sdílené stránky musí odkládací démon nalézt záznam o této stránce v každé tabulce stránek všech procesů, které stránku sdílejí (záznam se nalezne podle ukazatele v datové struktuře vm_area_struct). Pokud je záznam o této sdílené stránce v tabulce stránek platný, démon jej označí jako neplatný a odložený a sníží počitadlo použití této sdílené stránky o jedničku. Záznam v tabulce stránek o odložené sdílené stránce obsahuje index do množiny struktur shmid_ds a index do položek tabulky stránek pro tuto oblast sdílené paměti.
Pokud počitadlo použití stránky dosáhne po modifikaci tabulek všech sdílejících procesů nulu, je možno sdílenou stránku zapsat do odkládacího souboru. Položka tabulky stránek v seznamu, na nějž ukazuje datová struktura shmid_ds, se pro tuto oblast sdílené paměti nahradí položkou odložené stránky. Položka odložené stránky je neplatná položka tabulky stránek, obsahuje ale index do množiny otevřených odkládacích souborů a offset toho souboru, v němž je možno odloženou stránku nalézt. Tyto informace se použijí jakmile bude nutné vrátit stránku zpět do fyzické paměti.
Odkládací démon zkontroluje všechny procesy v systému a zjistí, zda některý je vhodným kandidátem na odložení.
Vhodným kandidátem jsou procesy, které je možno odložit (u některých to nejde) a které vlastní jednu či více stránek, jež je možno z paměti odložit nebo zrušit. Stránky se z fyzické paměti odloží do systémového odkládacího souboru pouze v tom případě, že je není možno obnovit nějakou jinou metodou.
Většina stránek spustitelného obrazu pochází ze souboru tohoto obrazu a je možno je jednoduše obnovit novým přečtením tohoto souboru. Například spustitelné instrukce se nikdy nemodifikují, takže se ani nikdy nezapisují do odkládacího souboru. Takovéto stránky je možno přímo zrušit - až se na ně proces bude příýtě odkazovat, načtou se do paměti zpátky přímo ze spustitelného obrazu.
Jakmile je nalezen proces k odložení, odkládací démon prohlédne všechny oblasti jeho virtuální paměti a hledá oblasti, které nejsou sdíleny ani uzamčeny.
Linux neodkládá všechny odložitelné stránky vybraného procesu, zruší pouze několik málo stránek.
Pokud jsou stránky v paměti uzamčeny, není možno je odložit ani zrušit.
Odkládací algoritmus Linuxu používá stárnutí stránek. Každá stránka má počitadlo (uložené v datové struktuře mem_map_t), které dává odkládacímu démonu jádra jakousi představu o tom, zda stránka stojí či nestojí za odložení. Stránky stárnou, když nejsou používány, a mládnou při každém přístupu. Odkládací démon odkládá pouze staré stránky. Implicitní operace při alokování nové stránky je, že stránka získá výchozí věk 3. Při každém přístupu se její věk inkrementuje o 3 až do maxima 20. Vždy když je odkládací démon spuštěn, nechá stránky zestárnout tím, že jejich věk dekrementuje o jednu. Toto implicitní chování je možno měnit, a proto se všechny tyto (a další odkládací informace) udržují ve struktuře swap_control.
Pokud je stránka stará (věk - 0), odkládací démon ji dále zpracuje. Modifikované stránky je nutné odložit. K popisu těchto vlastností stránek používá Linux strojově závislé příznaky ve strukturách PTE (viz obrázek 3.2). Ne všechny modifikované stránky je však nezbytně nutné uložit do odkládacího souboru. Každá oblast virtuální paměti procesu může mít svou vlastní odkládací operaci (na kterou ukazuje ukazatel vm_ops struktury vm_area_struct) a pak se použije tato operace. Pokud operace není definována, odkládací démon implicitně alokuje stránku v odkládacím souboru a zapíše rušenou stránku na odkládací zařízení.
Položka tabulky stránek pro odloženou stránku se přepíše údajem, který říká, že položka není platná, a obsahuje informace o tom, kde se stránka v odkládacím souboru nachází. Tento údaj obsahuje jednak offset odkládacího souboru, jednak určení, který odkládací soubor byl použit. Aš už byla použita jakákoliv metoda odkládání, původní fyzická stránka je uvolněna a přidá se zpět do seznamu free_area. Čisté (přesněji řečeno nemodifikované) stránky je možno zrušit a uložit zpět do struktury free_area okamžitě.
Pokud bylo odloženo a zrušeno dostatečné množství stránek, odkládací démon usíná. Při příýtím probuzení posoudí jiný proces. Tímto způsobem odkládací démon "uzobne" pár stránek každému procesu, dokud nebude mít systém opět dostatek paměti. Je to podstatně spravedlivější řešení než úplné odložení celého procesu.
Při odkládání stránek do odkládacích souborů se Linux snaží vyhnout zápisu, pokud to není nezbytné. Může nastat situace, kdy je stránka jak v odkládacím souboru, tak ve fyzické paměti. Dochází k tomu v případě, že stránka odložená z paměti byla později do paměti vrácena, když ji její proces opět potřeboval. Pokud nedošlo k zápisu do této stránky v paměti, její kopie v odkládacím souboru je stále platná.
Ke sledování těchto stránek používá Linux vyrovnávací odkládací paměť. Tato paměť představuje seznam položek tabulek stránek, jednu pro každou fyzickou stránku v systému. V položkách odložených stránek je zapsáno, ve kterém souboru jsou uloženy a jejich pozice v tomto souboru. Pokud je údaj ve vyrovnávací paměti nenulový, znamená to, že stránka uložená v odkládacím souboru nebyla modifikována. Pokud dojde k modifikaci stránky (zápisem do této stránky), údaj o ní se z odkládací vyrovnávací paměti odstraní.
Když Linux potřebuje fyzickou stránku odložil do odkládacího souboru, podívá se nejprve do odkládací vyrovnávací paměti, a pokud v ní najde platný záznam o stránce, nemusí ji zapisovat do odkládacího souboru. Platný záznam totiž indikuje, že stránka nebyla od posledního načtení z odkládacího souboru modifikována.
Položky v odkládací vyrovnávací paměti představují položky tabulky stránek pro odložené stránky. Jsou označeny jako neplatné, obsahují však informace, podle kterých Linux nalezne správný odkládací soubor a správnou stránku v tomto souboru.
Modifikované stránky uložené v odkládacím souboru mohou být později znovu zapotřebí, například v okamžiku, kdy aplikace potřebuje zapisovat do té oblasti virtuální paměti, jejíž obsah je uložen v odložené fyzické stránce. Pokus o přístup k virtuální stránce, která není přítomna ve fyzické paměti, vyvolá výpadek stránky. Výpadkem stránky signalizuje procesor operačnímu systému, že není schopen přeložit virtuální adresu na fyzickou. V našem případě je to způsobeno tím, že při odložení stránky z paměti byl její záznam v tabulce stránek označen jako neplatný. Procesor není schopen obsloužit překlad virtuální adresy na fyzickou, takže předává řízení zpět operačnímu systému a říká mu, jaká virtuální adresa vypadla a jaký byl důvod výpadku. Formát těchto informací a způsob, jakým procesor předává řízení operačnímu systému, je závislý na procesoru.
Procesorově závislý kód obsluhy výpadku stránky musí nalézt datovou strukturu vm_area_struct popisující oblast virtuální paměti, do níž spadá vypadnuvší adresa. Dosáhne toho prohledáváním všech datových struktur vm_area_struct daného procesu tak dlouho, dokud nenajde tu, která obsahuje adresu, jež způsobila výpadek. Jedná se o časově velmi kritický kód, a proto jsou datové struktury vm_area_struct procesu organizovány tak, aby vyhledávání zabralo co nejméně času.
Jakmile se obslouží všechny procesorově závislé akce a nalezne se oblast, do níž spadá vypadlá adresa, je už obsluha výpadku dále obecná a na procesoru nezávislá.
Obecný kód obsluhy výpadku se podívá na záznam v tabulce stránek pro vypadlou stránku.
Pokud položka indikuje, že stránka je odložena, musí ji Linux opětovně vložit zpět do fyzické paměti. Formát položky tabulky stránek pro odložené stránky je procesorově závislý, všechny procesory však položku označují jako neplatnou a ukládají v ní nějakou informaci o tom, kde odloženou stránku nalézt. Tyto informace Linux potřebuje, aby mohl stránku vrátit zpět do fyzické paměti.
V tomto okamžiku Linux zná adresu, která způsobila výpadek, a má položku tabulky obsahující informaci o tom, kam byla stránka odložena. Datová struktura vm_area_struct může obsahovat ukazatel na rutinu, která opětovně vloží jakoukoliv stránku dané oblasti virtuální paměti zpět do fyzické paměti. Jedná se o operaci swapin. Pokud daná oblast paměti má definovánu operaci swapin, Linux ji použije. To je mimo jiné i způsob, jakým se obsluhuje odkládání stránek sdílených mechanismem System V, protože jejich odkládání vyžaduje speciální obsluhu danou tím, že formát odložených sdílených stránek je poněkud odl"ný od normálních odložených stránek. Operace swapin nemusí být definována a v takovém případě Linux předpokládá, že se jedná o běžnou stránku, která nevyžaduje speciální obsluhu.
Nealokuje volnou fyzickou stránku a načte stránku zpět z odkládacího souboru. Informace o tom, kde se stránka v odkládacím souboru nachází (a ve kterém odkládacím souboru), se zjistí z položky tabulky stránek pro tuto stránku.
Pokud přístup, který způsobil výpadek stránky, nebyl pokusem o zápis, zůstává stránka ve vyrovnávací odkládací paměti a její položka v tabulce stránek je označena jako nezapisovatelná.
Pokud následně dojde k zápisu do stránky, generuje se nový výpadek stránky a v tom okamžiku systém označí stránku jako modifikovanou a odstraní ji z vyrovnávací odkládací paměti.
Pokud do stránky nebylo zapsáno a je zapotřebí ji znovu načíst, Linux si ušetří zápis stránky do odkládacího souboru, protože soubor už obsahuje platnou kop" stránky.
Pokud byl výpadek způsobem zápisem, stránka se odstraní z vyrovnávací paměti rovnou a označí se jako stránka modifikovaná a s povoleným zápisem.