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

Virtuální paměť

Každý proces má svůj vlastní adresní prostor, který určuje jeho tabulka stránek. Pokud je nějaká stránka v tabulce stránek procesu, může na ni tento procese okamžitě přistupovat. Při přístupu je virtuální adresa převedena na fyzickou adresu podle tabulky stránek. Pokud má systém nedostatek fyzické paměti, začne stránky zapisovat na disk do swapovací oblasti. Když je stránka zapsána na disk, do tabulky stránek procesu je poznamenáno, že stránka není přístupná. Pokud proces na tuto stránku přistoupí, vyvolá se exception, který je zpracován operačním systémem. Při přijmutí exceptionu operační systém natáhne stránku z disku zpět do paměti (případně odswapuje jinou stránku na disk), nastaví v tabulce stránek procesu, že je stránka platná a pustí dál proces, který výpadek stránky vyvolal. — tohle je asi základní myšlenka, která se za principem virtuální paměti skrývá a která se učí na kurzech operačních systémů. Skutečnost je však mnohem komplikovanější. Na systém virtuální paměti je kladeno větší množství požadavků:

• Sdílení kódu programů — pokud více uživatelů pustí tentýž program, je žádoucí, aby kód programu byl v paměti zaveden jen jednou.
• Load-on-demand — určitá data (například kód programů) je možno načíst z filesystému v případě potřeby. Program proto není třeba číst celý v době jeho spuštění, ale je načítán až v době běhu. Načteny jsou jen ty části programu, které jsou skutečně použity. Pokud dochází paměť, není třeba program ukládat do swap oblasti, stránky obsahující kód programu jsou prostě uvolněny, neboť je možno je kdykoli znovu načíst ze souboru.
• Mapování souborů — souvisí s load-on-demand a jeho implementace je stejná. V tomto případě se však nenačítá kód programu, ale libovolný datový soubor. Každý proces může požádat o namapování nějakého souboru do svého adresního prostoru. Pokud na příslušnou adresu přistupuje, přistupuje do souboru. Mapování se provádí pomocí syscallu mmap. Máme tři druhy mapování: pro čtení (do namapované oblasti nelze zapisovat, příznak PROT_READ), pro privátní zápis (do namapované oblasti lze zapisovat, tyto zápisy platí pouze pro daný proces, nezapisují se zpět do souboru, zapomenou se při zrušení mapování, příznaky PROT_WRITE a MAP_PRIVATE), pro sdílený zápis (do namapované oblasti lze zapisovat, zápisy jsou viditelné všemi ostatními procesy a jsou zapsány zpět do namapovaného souboru (podle standardu POSIX zápisy nemusí být vidět v souboru a v mapování jiných procesů, dokud se oblast neodmapuje nebo dokud se nezavolá syscall msync. Na většině systémů jsou zápisy vidět okamžitě, nicméně program, který na to spoléhá, je chybný a na starších systémech nemusí fungovat), příznaky PROT_WRITE a  MAP_SHARED).
• Copy-on-write — technika copy-on-write se používá k efektivní implementaci syscallu fork. Já osobně považuji fork za nejhorší chybu návrhářů Unixu. Syscall fork spustí podproces daného procesu. Podproces i rodičovský proces pokračují v běhu od stejného místa. Jednoduchá implementace fork funguje tak, že celou datovou oblast procesu zkopíruje do nového procesu. To je velmi pomalé. Proto se k implementaci

  fork používá virtuální paměť. Při fork se starému procesu nastaví všechna mapování stránek read-only. Pak se tabulka stránek nakopíruje do nového procesu. Když některý proces do svých dat zapíše, dojde k exceptionu a systém v obslužné rutině tohoto exceptionu udělá kopii stránky a k této kopii nastaví přístup read-write. Procesy tak mají dojem, že běží každý ve svém vlastním adresním prostoru, ale ve skutečnosti jsou jejich data stále sdílená, dokud do nich nezapíší. Copy-on-write je rychlejší než kopírování celých procesů, ale stále je dost pomalé, neboť se musí kopírovat tabulka stránek. Nejhorší však je, že kopírování tabulky stránek je při pouštění jiného programu jako podprocesu zcela zbytečné. Všechny ne-unixové systémy (např. OS/2, Windows, VMS i MS-DOS) mají syscall spawn nebo jeho ekvivalent, který jako parametr dostane jméno programu a argumenty a pustí tento podproces. Pokud chceme pustit podproces na Unixu, musíme nejdříve rodičovský proces rozdvojit pomocí fork a poté zavolat v dětském podprocesu

  exec, což procesu smaže data a pustí místo něj specifikovaný program. Tabulka stránek se tak pracně zkopíruje jen na to, aby se okamžitě smazala pomocí exec. Původní Unix běžel na PDP-7, které nemělo virtuální paměť, segmentaci ani ochranu paměti. V paměti mohl být zaveden vždy jen jeden proces, který běžel. Multitasking se dělal swapováním celých procesů na disk. V tomto prostředí je implementace syscallů fork a exec velmi jednoduchá — fork pouze odswapuje aktuální proces na disk, ale nechá ho běžet s novým PID; exec načte do paměti přes existující proces nový program. Proto ani není divu, že autoři původního Unixu

  fork a exec implementovali tak, jak jsou. Bohužel v systémech se segmentací nebo virtuální pamětí je tato implementace zoufale neefektivní. Na některých Unixech (Linux i FreeBSD mezi ně patří) byl zaveden syscall vfork, který provede totéž co fork vyjma nastavování stránek read-only a kopírování tabulky. vfork také zablokuje rodičovský proces, dokud dětský podproces nezavolá exec. Předpokládá se, že dětský podproces provede ihned po vfork exec, čímž zavede nový program. Mezi vfork a exec nesmí dětský podproces modifikovat žádné proměnné vyjma proměnných aktuální funkce, neboť tahle modifikace se může a nemusí přenést do rodičovského procesu. Kompilátor ovšem občas spontánně do zásobníkového rámu píše nějaké dočasné hodnoty, proto v rodičovském procesu po vfork přestávají platit hodnoty všech lokálních proměnných v aktuální funkci. Použití

  vfork je tedy poměrně komplikované.
• Sdílená paměť — procesy mohou sdílet paměť pomocí syscallů SYSV SHM. Toto rozhraní je značně těžkopádné, pro každý sdílený segment se musí vyrábět speciální klíč a ten se pak musí distribuovat mezi procesy (pokud nebude vyroben unikátní klíč, ale bude použita pevná hodnota, nebude program sestávající z více procesů sdílejících paměť moci používat více uživatelů současně). Proto nová norma POSIX umožňuje sdílet paměť pomocí mapování souborů (funkce shm_open). Segment sdílené paměti se identifikuje pomocí řetězce a ne pomocí číselného klíče, což zabraňuje kolizi klíčů mezi jednotlivými programy nebo mezi více instancemi téhož programu.
• Cachování — je žádoucí, aby zbylá volná paměť byla použita jako disková cache. Dnešní počítače mají velké množství paměti, málokterý program celou paměť využije a cachování souborů v nepoužité paměti je zcela zásadní nutnost správy virtuální paměti. Kvalita cache výrazně určuje rychlost systému. Dnes již u virtuální paměti nejde ani tak o swapování (ke swapování dochází zřídka), ale právě o cachování souborů. Je třeba, aby nedošlo k tzv. vytrashování cache čtením nebo zápisem velkého souboru. Pokud budeme sekvenčně číst soubor větší než velikost paměti, není žádoucí, aby se tento soubor ukládal do cache. To by vedlo k úplnému„pře­mazání” všech údajů v cachi naposled načtenými stránkami souboru. Až bude soubor čten znovu od začátku, nebude cache užitečná; pravděpodobnost, že soubor bude čten znovu od konce (kde jsou nacachovaná data), je velmi malá.
• Balancování cachování a swapování — v určitých situacích je v systému zaveden veliký program, který neběží. Pak je žádoucí program odswapovat na disk a uvolněnou paměť používat jako cache. V jiných případech se zase stává, že běží jeden veliký program, který cache téměř nepotřebuje. Pak je žádoucí velikost cache stáhnout na minimum a veškerou paměť dát onomu programu.
• Spravedlivost vůči uživatelům — jeden uživatel by neměl mít možnost nekontrolovatelně vyswapovávat stránky ostatních uživatelů a zpomalovat jim tak běh jejich procesů. Současné systémy tenhle požadavek příliš nesplňují (mají jakousi podporu pomocí příkazu ulimit, FreeBSD je na tom lépe než Linux, ale k dokonalosti má tohle řešení hodně daleko). Jediný systém, na kterém je tento problém rozumně vyřešen, je VMS.

Historie virtuální paměti

První pokusy s něčím, co trochu připomínalo virtuální paměť, začaly v interpretech jazyka LISP. LISPové struktury CONS byly ukládány na disk. Při procházení pointerů bylo interpretem zjišťováno, zda pointer ukazuje na strukturu v paměti, nebo na disku, a struktura byla případně z disku nahrána. Procesory v té době neměly žádnou virtuální paměť, virtualizace se dělala pouze v rámci interpretu.

Prvním systémem, který měl komplexní podporu virtuální paměti, byl Multics. Multics splňoval téměř všechny požadavky na virtuální paměť: sdílení kódu programu, používání paměti jako souborové cache, mapování souborů do paměti, jednotný pohled na cachované stránky a na stránky alokované procesy. V Multicsu se pro práci se soubory používalo výhradně mapování — klasické unixové syscally read  a

write tam neexistovaly. Mapování je efektivnější než read a write, neboť při něm nedochází ke kopírování dat. Pro výměnu stránek používal Multics prostý hodinový algoritmus (popis algoritmu bude v dalším článku). Praxe však ukázala, že to nefungovalo příliš efektivně — jednotný pohled na alokované stránky a na cache sice umožnil efektivní cachování, ale způsoboval, že pokud někdo přečetl veliký soubor, všem ostatním uživatelům byly stránky odswapovány. V dobách, kdy byl Multics používán, byly na počítače kladeny mnohem větší požadavky než dnes; počítačů bylo málo a uživatelů hodně. Na Multicsu velmi často docházelo k tzv. trashování. Tento jev nastává, když množství paměti, na kterou aktivní procesy přistupují, je výrazně větší než množství fyzické paměti — skoro každý přístup do paměti pak způsobí page-fault a načtení stránky z disku, během operace disku je naschedulován jiný proces, ten ovšem také okamžitě způsobí page-fault, zařadí požadavek na čtení stránky do fronty a čeká, je naschedulován další proces, který udělá další fault a tak dále… výsledek je takový, že fronta požadavků na disk je zaplněna a žádný proces se téměř nehne z místa. Kdyby byly procesy pouštěny sekvenčně po sobě, doběhnou o několik řádů rychleji, než když jsou puštěny paralelně. Je paradoxní, že Linux 2.2 používá rovněž hodinový algoritmus k výměně stránek podobně jako Multics, a přitom si na pomalost Linuxu nikdo tolik nestěžuje

— je to dáno tím, že dnes jsou na počítače kladeny výrazně nižší nároky. Kdyby Linux měl podporovat přístup čtyřiceti uživatelů na stroji s 4M RAM, byl by zcela nepoužitelný.

Neúspěch Multicsu a problém trashování vedl k jednoduchému řešení — nepoužívat virtuální paměť vůbec. Tak byl implementován Unix. Unix nedělal stránkování a swapoval celé procesy, původní verze Unixu mohly mít v paměti zaveden jen jeden proces, novější verze mohly mít v paměti více procesů. I když je swapování procesů výrazně primitivnější činnost než stránkování, v určitých situacích se chová lépe. Při swapování procesů nedochází k trashování; pokud je systém přetížen mnoha procesy, má sice velmi dlouhou odezvu, ale procesy běží a konají nějakou práci. Naproti tomu při trashování procesy téměř neběží. Problematikou cache se v Unixu příliš nezabývali — systém měl malou fixní část paměti předalokovanou na buffery a to bylo všechno. V té době ani cache nebyla potřeba — pokud byla v systému nějaká volná paměť, určitě se našel nějaký uživatel, který by se rád přihlásil a paměť využil, takže plýtvání pamětí na cache nemělo smysl. Spousta Unixů (OpenBSD, Irix, Solaris – nejsem si jist, zda to platí i pro nejnovější verze) bohužel má bufferovou cache fixní velikosti dodnes. V praxi to pak vypadá tak, že systém má třeba 2/3 paměti volné, ale nepoužije ji jako cache a soubory znovu a znovu pomalu čte z disku.

Poučení z pomalosti Multicsu si vzali návrháři VMS a udělali virtuální paměť tak, že k samovolnému vytrashování nemůže dojít. VMS používá kombinaci stránkování a swapování celých procesů. Na VMS má každý proces nastavenou tzv. „working set”. Je to množství paměti, které má proces namapované — t.j. množství položek tabulky stránek, které mají bit PRESENT nastaven a ukazují na stránku. Pokud chce proces přistupovat na více paměti, než je jeho working set, systém mu automaticky nějaké stránky odmapuje a umístí je do clean nebo modified listu, aby working set byla zachována. Namapovaná paměť procesu nikdy neklesne pod jeho working set. Když v systému dochází paměť, systém zapisuje stránky z modified listu na disk nebo uvolňuje stránky z clean listu. Pokud už se takto žádnou paměť nepodaří uvolnit, systém začne swapovat celé procesy. Až je proces později naswapován, jsou nataženy všechny jeho stránky, které byly namapovány před odswapováním. Tento přístup má výhody virtuální paměti bez nebezpečí trashování — protože množství stránek procesu zavedeného v paměti není nikdy menší než jeho working set, proces může aspoň chvíli po naswapování běžet, aniž by produkoval další page-faulty a způsoboval trashování. Pokud je systém pod malou zátěží, chová se jako systém s virtuální pamětí a stránkováním. Pokud je pod velkou zátěží, začne se chovat jako systém bez virtuální paměti se swapováním celých procesů, což je v takovém případě efektivnější. Tento systém je také spravedlivý vůči uživatelům. Pokud jeden uživatel začne používat enormní množství paměti, bude jeho proces odswapovávat a naswapovávat jenom svoje vlastní stránky a neovlivní to nijak paměť ostatních uživatelů. Původní VMS nemělo žádnou cache (neboť v té době nebyla cache potřeba), nové verze ji už mají, ale není do zmíněného systému virtuální paměti moc dobře integrovaná a není tam stejný pohled na stránky nacachované a namapované. Navzdory tomu, že správa virtuální paměti na VMS zabraňuje trashování a je spravedlivá vůči uživatelům, současné operační systémy tyto principy nepoužívají, neboť zátěž na ně kladená je výrazně nižší.