Zatím všechno povídání snad s výjimkou overlaying počítalo s tím, že se do fyzické paměti vejde několik programů najednou. Situace je ale občas opačná, program se vůbec nemusí vejít. Takže se vymyslela virtuální paměť, překvapivě už někdy kolem 1961.
Princip stránkování je v pohodě. Paměť se rozdělí na bloky stejné délky a udělá se tabulka, která mapuje virtuální adresy na fyzické. Problém je samozřejmě v té tabulce ...
Tabulka musí být schopna pokrýt celý adresový prostor procesu, případně jich může být i víc pro víc procesů. To vede na problém s velikostí tabulky, pro adresové prostory 32 bitů a stránky o velikosti 4KB zbývá 20 bitů adresy na číslo stránky, při 4 bajtech na položku vychází tabulka kolem 4MB. To je moc, proto se dělají ...
Víceúrovňové tabulky, kde není potřeba rezervovat prostor pro tabulku stránek celé virtuální paměti, ale jen pro použitou část, navíc mohou být části tabulky také stránkovány.
Různé velikosti stránek, kde je potřeba menší počet položek na namapování stejného objemu paměti.
Inverted page tables, které mají položku pro každou fyzickou stránku, a jsou tedy vlastně asociativní pamětí, která vyhledává podle virtuální adresy. Mají tu výhodu, že jejich velikost závisí na velikosti fyzické paměti, nikoliv virtuální, ovšem špatně se prohledávají. Protože inverted page tables se prohledávají zpravidla hashováním a řešit kolize v hardware by bylo nákladné, jsou vedle samotné inverted page v paměti ještě další hashovací struktury, které používá operační systém.
Protože prohledávání tabulek při každém přístupu do paměti by bylo pomalé, vymyslel se Translation Lookaside Buffer, který je ovšem (jako každá asociativní paměť) nákladný. S TLB souvisí ještě dvě důležité věci, jedna je vyprazdňování TLB při přepnutí adresového prostoru, druhá je idea nechat správu a prohledávání stránkovacích tabulek výhradně na operačním systému a v hardware mít pouze TLB.
Nahrazování stránek je pochopitelně věda, jde o to vyhodit vždycky tu správnou stránku. Zjevným kritériem je minimalizace počtu výpadků stránek za běhu aplikace, tedy optimální algoritmus by vyhodil vždycky tu stránku, která bude potřeba za nejdelší dobu. To se sice nedá předem zjistit, ale jde udělat jeden průchod programu pro změření výpadků stránek a další už s optimálním stránkováním (pokud program běží deterministicky). Tento algoritmus slouží spolu s algoritmem vybírajícím náhodnou stránku jako měřítko pro hodnocení bežných algoritmů, které se vesměs snaží vyrobit nějakou smysluplnou predikci chování programu podle locality of reference (náhodný a optimální výběr stránky představují limitní situace pro nulovou a dokonalou predikci aplikace).
[Tady vypadají moc pěkně ty grafy, co vyšly v ACM OS Review 10/97, je na nich vidět chování různých druhů aplikací při přístupu k paměti. Tedy, možná ne moc pěkně, ale na začátku by asi nebylo špatné je zmínit.]
First In First Out replaces the page that has been replaced longest time ago.
Not Recently Used presumes that a read access to a page sets the accessed bit associated with the page and that a write access to a page sets the dirty bit associated with the page. The operating system periodically resets the accessed bit. When a page is to be replaced, pages that are neither accessed nor dirty are replaced first, pages that are dirty but not accessed are replaced second, pages that are accessed but not dirty are replaced third, and pages that are accessed and dirty are replaced last.
One Hand Clock is a variant of Not Recently Used that arranges pages in a circular list walked by a clock hand. The clock hand advances whenever page replacement is needed, a page that the hand points to is replaced if it is not accessed and marked as not accessed otherwise.
Two Hand Clock is a variant of Not Recently Used that arranges pages in a circular list walked by two clock hands. Both clock hands advance whenever page replacement is needed, a page that the first hand points to is replaced if it is not accessed, the page that the second hand points to is marged as not accessed. The angle between the two hands determines the aggressivnes of the algorithm.
Least Recently Used replaces the page that has been accessed longest time ago. Since the information on when a page has been accessed last is rarely available, approximations are used. The algorithm exhibits very inappropriate behavior when large structures are traversed.
Least Frequently Used replaces the page that has been accessed least frequently lately. Since the information on how frequently a page has been accessed lately is rarely available, approximations are used. The algorithm exhibits very inappropriate behavior when usage frequency changes.
U algoritmů, které nezohledňují používání paměti procesem, může dojít k Beladyho anomálii, totiž v určitých situacích se přidáním frames zvýší počet výpadků stránek. Příkladem může být třeba algoritmus FIFO 012301401234 ve třech a čtyřech stránkách (je potřeba počítat už načítání prvních stránek jako výpadky).
V systému s více procesy to pak vypadá tak, že jsou namapovány nějaké množiny stránek pro každý proces. Algoritmy se dají aplikovat různým způsobem, klasické je rozdělení na lokální aplikování algoritmu v rámci jednoho procesu a globální aplikování algoritmu v rámci celého počítače. Množině stránek, které proces právě používá, se říká working set, její obsah se mění tak, jak proces běží. Ve chvíli, kdy běží příliš mnoho aplikací, se jejich working sets do paměti nevejdou. Pak se vždy spustí proces, který potřebuje naswapovat nějakou stránku, tedy se najde oběť a začne se swapovat, mezitím se spustí jiný proces, který potřebuje naswapovat nějakou stránku, a tak pořád dokola, takže se nic neudělá. Říká se tomu thrashing.
U lokálních algoritmů se dají lépe poskytovat záruky například realtime aplikacím (protože se nestatne, že jedna aplikace sebere druhé paměť), ale obecně vyhrávají spíš globální algoritmy, spolu s nějakým minimem stránek pro každý proces. Do vyhazovaných stránek se pak počítají také kernel caches. I globální algoritmy většinou fungují tak, že iterují postupně přes jednotlivé procesy, protože tím budou spíš vyhazovat nejdřív stránky z jednoho procesu a pak z dalšího, čímž zvyšují pravděpodobnost, že některé procesy budou mít v paměti celý working set.
Zmínit memory mapped files a copy on write.
References.
Al-Zoubi et al.: Performance Evaluation of Cache Replacement Policies for the SPEC CPU2000 Benchmark Suite.
Sleator et al.: Amortized Efficiency of List Update and Paging Rules
Procesor má dvě vrstvy adresace, jedna převádí logické adresy na lineární a druhá převádí lineární adresy na fyzické. První vrstvu zatím necháme, pro stránkování je zajímavá jen ta druhá. Základní verze, logická adresa 32 bitů, fyzická adresa 32 bitů. Překlad simple, CR3 je base of page directory, prvních 10 bitů adresy offset, odtamtud base of page table, druhých 10 bitů adresy offset, odtamtud base of page, zbylých 12 bitů adresy offset.
Directory entry má krom 20 bitů base ještě 3 bity user data, jeden bit size, jeden bit accessed, jeden bit cache disabled, jeden bit write through, jeden bit user/supervisor, jeden bit read/write, jeden bit present.
Page entry má krom 20 bitů base ještě 3 bity user data, jeden bit global, jeden bit dirty, jeden bit accessed, jeden bit cache disabled, jeden bit write through, jeden bit user/supervisor, jeden bit read/write, jeden bit present.
Pokud je nastaven bit global, mapování dané stránky se považuje za přítomné ve všech adresových prostorech a nevyhazuje se z TLB při změně CR3.
Pokud je nastaven bit page size, directory entry neukazuje na page table, ale rovnou na stránku, která je pak velká 4 MB.
Bity accessed a dirty nastavuje příslušným způsobem procesor, používají se pro page replacement algoritmy.
Bity s právy a podobné jsou jasné, víc se stejně proberou na nějakém jiném předmětu.
Když je položka not present, všechny ostatní bity jsou user defined.
No a aby se to pletlo, od Pentia Pro je ještě Physical Address Extension bit v CR4, když se nahodí tak jsou directory entry a page entry dlouhé 64 bitů, v CR3 se objeví pointer na page directory pointer table a překládá se trojúrovňově, 2 bity z adresy do pointer table, 9 bitů do directory table, 9 bitů do page table, 12 bitů do page, nebo 2 bity do pointer table, 9 bitů do directory table, 21 bitů do page. Fyzická adresa je pak 36 bitů.
Velikosti stránek 4, 8, 16, 64 a 256 KB a 1, 4, 16 a 256 MB. Virtuální adresa 54 bitů (51 bitů adresa, 3 bity region index), fyzická adresa 44 bitů (ale aplikace vidí virtuální adresu 64 bitů, 61 bitů adresa, 3 bity region index). Region index ukazuje na jeden z osmi region registrů šířky 24 bitů, region je v podstatě address space a region index je ve virtuální adrese proto, aby procesy mohly koukat do address space jiným procesům.
Překládá se pomocí TLB, položka obsahuje krom adresy a regionu obvyklé bity present, cacheable, accessed, dirty, access rights, nic zvláštního. Pokud TLB neobsahuje překlad, hardware může prohledat ještě Virtual Hash Page Table, což je jednoduchá hash table pevného formátu. Pokud ani VHPT neobsahuje překlad, hodí se fault a operační systém naplní TLB.
Zajímavý je systém ochran. Každá položka TLB obsahuje klíč, při jejím použití se tento klíč hledá v Protection Key Registers, které obsahují klíče přidělené aktuálnímu procesu. Pokud se klíč nenajde, hodí se Key Miss Fault (pro virtualizaci PKR), pokud se najde, zkontroluje se, zda klíč nezakazuje read, write nebo execution access.
Také zajímavý je systém registrů. General purpose registers mají jména GR0 až GR31. Ty jsou jako všude jinde. Krom nich jsou ještě k dispozici registry GR32 až GR127, které fungují jako register stack. Z register stacku je část vyhrazena jako input area, část jako local area, část jako output area. Při volání procedury se z output area volajícího stane input area volaného, velikost local area a output area volaného je 0, pomocí instrukce alloc se pak dá nastavit local a output area, simple. Pokud dojde těch 96 registrů procesoru, které se interně používají jako cyklický buffer, existuje extra stack BSP, na který se ukládá, co se nevejde.
Ze 32 bitů adresy je 7 bitů pointer do root table (registry URP a SRP obsahují user a supervisor root table pointer), 7 pointer do pointer table, 5 nebo 6 pointer do page table, zbyte pointer do stránky (8 nebo 4 KB, podle bitu P registru TCR). Také je k dispozici možnost vymezit čtyřmi TTR registry čtyři bloky virtuálních adres, které se nepřekládají. Jinak umí v podstatě všechno co Intel, s jednou věcí navíc, totiž directory table může krom normálního page descriptoru obsahovat ještě indirect page descriptor, který ukazuje na skutečný descriptor uložený někde jinde v paměti. To se hodí pokud se jedna stránka sdílí na více virtuálních adresách, pak totiž může stále mít jen jeden dirty bit.
[Obrázek překladu je v MC68060 User's Manual, Section 4 Memory Management Unit. Málo zajímavý je obrázek 4-1, který jen ukazuje, že se odděluje adresová a datová cache, TLB se říká ATC a mají 64 položek stupně asociace 4 každá. Obrázek 4-4 ukazuje formát translation control registru. Obrázek 4-5 ukazuje formát transparent translation registrů. Obrázek 4-7 ukazuje rozdělení virtuální adresy. Obrázky 4-10 a 4-11 ukazují formát stránkovacích tabulek, G je global, U je accessed, M je dirty, W je read only, CM je cache, PDT a UDT jsou typy položky s hlavní funkcí rozlišení present. Obrázek 4-12 ukazuje příklad překladu adresy. Obrázek 4-13 ukazuje příklad překladu adresy sdílené stránky. Obrázek 4-14 ukazuje příklad překladu adresy copy on write stránky. Obrázek 4-19 vysvětluje strukturu částečně asociativní TLB.]
[Obrázek cache je v MC68060 User's Manual, Section 5 Caches. Obrázek 5-4 vysvětluje strukturu částečně asociativní cache. Cache dovoluje čtyři režimy práce, write through cachuje čtení a zapisuje data rovnou, copy back cachuje čtení i zápis, inhibited čte i zapisuje data rovnou, ve verzi precise zaručuje pořadí přístupu shodné s pořadím instrukcí, ve verzi imprecise dovoluje některým čtením předběhnout zápisy.]
Tohle se zná z Nachosu. Na čipu je pouze TLB se 48 položkami, každá položka mapuje dvě stránky o velikosti od 4 KB do 16 MB po čtyřnásobcích. V položce je jeden address space ID (porovnává se s ASID v CP0) a jedna virtuální adresa, dvě fyzické adresy pro sudou a lichou stránku (smart protože se porovnává podle virtuální adresy), pro virtuální adresu maska (určuje velikost) a flag global (ignoruje se ASID), pro každou stránku dirty a valid flag a detaily pro řízení cache coherency, nezajímavé.
Pro naplnění položky TLB je k dispozici extra instrukce, může buď naplnit náhodnou položku nebo vybranou. Náhoda se odvozuje od počítání instrukčních cyklů, také je k dispozici wired TLB entry index registr, který říká, do kolika prvních položek TLB se náhoda nemá strefovat.
Mimochodem je to všechno dost zjednodušené, ale nevadí, podstatný je address translation mechanism a ten je popsaný přesně. Jinak existují varianty tohoto procesoru, které mají zjednodušenou MMU.
[Hezký obrázek je v MIPS32 4K Processor Core Family Software User's Manual (MIPS32-4K-Manual.pdf), Memory Management 3.3 Translation Lookaside Buffer]
Procesor od Compaqu, z návodu pro Alpha 21264. Virtuální adresa 48 nebo 43 bitů (podle bitu v registru I_CTL), fyzická adresa 44 bitů (nejvyšší bit je 0 pro paměť a 1 pro zařízení). TLB pro instrukce a pro data s round robin alokací, každá 128 bitů, mapují 8 KB stránky buď po jedné, nebo po skupině 8, 64 nebo 512, s 8 bity ID procesu. S TLB pracuje takzvaný PAL (Privileged Architecture Library) code, což je v podstatě privilegovaný kód blízký mikrokódu, který je uložený v normální paměti.
Zajímavě je řešené vyhazování položek z TLB. Procesor má registry ITB_IA, ITB_IS, DTB_IAP, DTB_IA a DTB_IS. Zápis do ?TB_IA vyhodí z datové nebo instrukční TLB všechny položky, DTB_IAP vyhodí všechny položky daného procesu, ?TB_IS vyhodí všechny položky týkající se zapisované adresy.
Tenhle hrůzný procesor má dokonce i virtuální registry. Běžné registry se jmenují R0 až R31, ale když je programátor používá, přemapují se na interní registry procesoru tak, aby se minimalizoval počet falešných write-after-read a writer-after-read závislostí mezi instrukcemi v pipeline.
[Zdá se, že žádné pěkné obrázky nejsou.]
Je velmi podobná MIPS procesorům, s délkami stránek 8, 64, 512 a 4096 KB, virtuální adresa 44 bitů (ale rozdělená na dvě poloviny na začátku a konci prostoru 64 bitů), fyzická adresa 41 bitů. Opět je k dispozici kontext určující kterému procesu patří položka TLB, bit na jeho ignorování u globálních mapování, page size ve dvou bitech, z dalších je třeba bit indikující endianness dat uložených na dané stránce (jmenuje se IE od Invert Endianness, další údaj o endianness je v address space ID, další v instrukci).
Aby měl TLB miss handler jednodušší život, nabízí hardware ještě další podporu. Při TLB miss se z registrů MMU dá vyčíst adresa do translation table v paměti, kde by podle jednoduchých hash rules měla být potřebná položka TLB. Pokud tam je, MMU ji umí na pokyn od handleru načíst do TLB.
[Obrázky UltraSparc 2 User's Manual, Chapter 15 MMU Internal Architecture. Obrázek 15-1 ukazuje formát položky TLB, CONTEXT je address space ID, V je valid, NFO je cosi, IE je invert endianness, L je lock entry, P je privileged, W je read only, G je global. Obrázek 15-2 ukazuje formát translation table v paměti, split říká jestli se budou 8k a 64k stránky hashovat společně nebo ne.]
Řada procesorů od ARM, z návodu pro ARM10E. Instrukční a datová TLB, každá 64 položek, tabulka stránek podporovaná hardware MMU. Umí stránky o velikosti 1, 4, 16, 64 a 1024 kB, pro zmatení nepřítele jim říká tiny pages, small pages, large pages a sections, některé umí dělit do čtyř subpages. Tabulka stránek je dvouúrovňová až na velikosti stránek 1024 kB. Ochrany jsou řešeny zavedením 16 domén, v 16 registrech jsou popsána práva supervisor a user procesů k doméně, každá stránka patří do nějaké domény. Je také možné používat pouze TLB.
[Obrázky ARM 1022E Technical Reference Manual, Chapter 4 Memory Management Units. Obrázek 4-1 ukazuje překlad adresy. Obrázek 4-3 ukazuje formát položky stránkovací tabulky úrovně 1. Obrázek 4-5 ukazuje formát položky stránkovací tabulky úrovně 2. C je cacheable, B je write back bufferable, AP je cosi co rozlišuje subpages, SBZ should be zero :). Nejsou bity accessed a dirty, nepředpokládá se paging.]
Další zajímavé vlastnosti procesoru. V kódu všech instrukcí je možné uvést podmínku, kdy se má provést, což odstraňuje nutnost branch prediction a nebezpečí prediction misses pro malé větve kódu.
To be done.
Krom obvyklých problémů s přístupem ke sdíleným strukturám mají víceprocesorové systémy problémy ještě v situacích, kdy jednotlivé procesory cachují informace související s memory managementem. Dvě situace:
Mapování v TLB. Pokud se změní address space mapppings, na uniprocesoru se flushuje TLB. Na multiprocesorech je potřeba flushnout TLB na všech procesorech, z toho vyplývá nutnost synchronizace při změně mapování, a to je pomalé. Trikem se to dá řešit třeba u R4000, kde se procesu prostě posune ASID, čímž se invalidují všechny jeho položky v TLB.
Virtual address caches. Většina caches sice používá fyzické adresy, ale protože hardware s caches na virtuální adresy může běžet rychleji, občas se také objeví. Tam je pak stejný problém jako u TLB.
HAL jako rozhraní, které zpřístupňuje memory manager dané platformy, zbytek kernelu předpokládá trojúrovňové stránkování. [Linux 2.4.20 například /include/asm-i386/pgtable-2level.h a /include/asm-i386/pgtable-3level.h] [Linux 2.6.9 například pgtable-2level.h a pgtable-2level-defs.h a pgtable-3level.h a pgtable-3level-defs.h a pgtable.h v /include/asm-i386] Neznamená to, že by se nějak simulovaly 3 úrovně kernelu pro 2 úrovně procesoru, prostě se v makrech řekne, že ve druhé úrovni je jen 1 položka.
Fyzické stránky se evidují strukturami struct page {} mem_map_t v seznamu mem_map, jako algoritmus pro výběr oběti se zřejmě používá LRU, bez bližších detailů, protože kernel vypadá všelijak. [Linux 2.4.20 /include/linux/mm.h]
Fyzické stránky jsou přiřazeny do zón, které odrážejí omezení pro některé rozsahy fyzické paměti, například ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM. Zóny mají seznamy volných stránek per CPU, aby nedocházelo ke kolizím na multiprocesorech. V každé zóně jede něco, čemu autoři říkají LRU, kód pro zájemce hlavně v [Linux 2.6.9 /mm/vmscan.c]. [Linux 2.6.9 /include/linux/mmzone.h]
Pro každý proces se pamatuje mapa jeho adresového prostoru ve struktuře mm_struct [Linux 2.4.22 /include/linux/sched.h], které je seznamem struktur vm_area_struct [Linux 2.4.22 /include/linux/mm.h]. Každá area má začátek, délku, flagy (code, data, shared, locked, growing ...) a případně associated file. Potřebné areas se vytvoří při startu procesu, uživatel pak může volat už jen pár syscalls jako mmap pro memory mapped files (dnes již v podstatě běžná záležitost) a shared memory (rovněž nic nového pod sluncem) nebo brk pro nastavení konce heapu. Nic moc. [Linux 2.4.20] [Linux 2.6.9]
[Mel Gorman: Understanding The Linux Virtual Memory Manager]
Klasické rozdělení na HAL, protože je potřeba nezávislost na platformě, pak správce segmetů a správce adresových prostorů. Mapa paměti klasicky kód, heap, stack. Stack roste on demand.
Každý segment má svého správce, v podstatě virtuální metody pro typy segmentů, hlavní je seg_vn driver pro vnodes souborů, seg_kmem pro nestránkovatelnou paměť kernelu, seg_map pro vnodes cache. Každý správce umí advise (jak se bude přistupovat k segmentu), checkprot (zkontrolování ochrany), fault (handle page fault na dané adrese), lockop (zamknutí a odemknutí stránek), swapout (žádost o uvolnění co nejvíce stránek), sync (žádost o uložení dirty stránek) a samozřejmě balík dalších.
Správce seg_vn umí mapovat soubory jako shared nebo private. Při private mapování se používá copy on write, který při zápisu přemapuje stránku do anonymní paměti. Jako drobné rozhodnutí, když je dost paměti, vyhradí se nové stránka a nakopírují se data, když ne, použije se sdílená stránka, která tím pádem přestane být sdílená.
Anonymní paměť je zajímavá, při prvním použití je automaticky zero filled, což je důležité. Spravuje jí swapfs layer, který ale nefunguje přímočaře tak, že by si pro každou stránku pamatoval pozici ve swap partition. Kdyby to tak totiž bylo, spotřebovával by se swap ještě než by se vůbec začalo stránkovat, takže místo toho je ke každé anonymní stránce struktura anon_map, která si v případě vyswapování zapamatuje pozici na disku. Prostor swapu je rezervován, ale nikoliv alokován, už v okamžiku alokace stránky, což dovoluje synchronní hlášení out of memory (do dostupného swapu se počítá i nezamčená fyzické paměť). Prý například AIX tohle nemá a out of memory se hlásí signálem.
Velmi zajímavá je také integrace správce souborů se správcem paměti. Jednak kvůli paměťově mapovaným souborů, ale hlavně kvůli cache. Aby se zabránilo sémantickým chybám při přístupu k souborům současně pomocí read a write a pomocí mmap, implementuje se read a write interně jako mmap do kernel bufferu. Když se takový buffer uvolní, stránka se sice eviduje jako volná, ale zůstane informace o tom, který vnode a offset obsahovala, takže až do té doby, než ji někdo použije, je součástí cache a dá se znovu použít. Kvůli tomu se udržuje hash stránek podle vnode a offsetu.
Page reclaim algoritmus je hodinový se dvěmi ručičkami, spouští se tím víc, čím víc dochází paměť, vzdálenost a rychlost obíhání se nastavuje v konfiguraci kernelu při bootu. Zajímavý efekt nastal, když se integroval správce souborů a správce paměti a začaly být rychlé disky, totiž když se zaplní cache a hledá se oběť pro vyhození, ručičky začnou obíhat příliš rychle (při dnešních discích desítky, v případě diskových polí stovky MB za vteřinu, což znamená, že se i bity o přístupu nulují v řádech vteřin) a tedy začnou příliš agresivně vyhazovat stránky programů, protože ty je prostě za tak krátkou dobu nestihnou použít. Solaris 7 tak upřednostňuje cache před stránkami programů, dokud mu nezačne docházet paměť, Solaris 8 už dělá něco úplně jiného, o čem nemám informace.
Jako jiná zajímavá funkce existují watchpoints, možnost dostat signál při přístupu na konkrétní adresu, ovládá se přes /proc file systém, tady jen pro zajímavost.
Detaily. Na thrashing se reaguje vyswapováním celého procesu. Dělá se page coloring kvůli caches. Shared pages se nevyhazují dokud to není nutné. Kernel allocator dělá slaby, což jsou bloky dané délky, umí reuse už inicializovaných objektů, další info skipped.
[Mauro, McDougall: Solaris Internals, ISBN 0-13-022496-0]
O lepší memory manager se pokusil například Mach, do relativně dokonalé podoby byl celý mechanismus dotažen ve Springu. Dá se dobře odpřednášet podle technical reportu z Evry.
Interně má velmi podobnou strukturu jako Spring také Unix SVR4, ale tam není přístupná uživateli. Memory objektům se říká segments, pagery jsou reprezentované pomocí vnodes pokud přistupují k objektům file systému, krom nich existuje ještě anonymous pager pro memory objekty, které přímo neodpovídají žádnému objektu file systému.
It can be observed that reading a page from a disk is not necessarily faster than reading a page from a network. It can also be observed that physical memory of a system is rarely used in its entirety except for caches. These two observations give rise to the idea of using spare physical memory of a cluster of systems instead of a disk for paging.
A prototype of a cluster memory management has been implemented for OSF/1 running on DEC Alphas connected by ATM. The prototype classifies pages on a system node as local or global depending on whether they are accessed by this node or cached for another node. The page fault algorithm of the prototype distinguishes two major situations:
The faulted page for node X is cached as global on another node Y. (The page can be fetched from network, a space for it has to be made on X.) The faulted page from Y is exchanged for any global page on X. If X has no global page, a LRU local page is used instead.
The faulted page for node X is not cached as global on any node. (The page must be fetched from disk, a space for it has to be made in cluster and on X.) A cluster wide LRU page on another node Y is written to disk. Any global page on X is written to Y. If X has no global page, a LRU local page is used instead. The faulted page is read from disk, where all pages are stored as a backup in case a node with global pages becomes unreachable.
To locate a page in the cluster, the prototype uses a distributed hash table. For each page in the cluster, the table contains the location of the page. Each node in the cluster manages part of the table.
To locate a cluster wide LRU page, the prototype uses a probabilistic LRU algorithm. The lifetime of the cluster is divided into epochs with a maximum epoch duration and a maximum eviction count. Each epoch, a coordinator is chosen as the node with most idle pages from the last epoch. The coordinator collects summary of page ages from each node in the cluster and determines the percentage of oldest pages within the maximum eviction count on each node in the cluster. The coordinator distributes this percentage to each node in the cluster and appoints a coordinator for the next epoch. Each eviction, a node is chosen randomly with the density function using the distributed percentages, the node then evicts LRU local page.
[ Michael J. Feeley, William E. Morgan, Frederic H. Pighin, Anna R. Karlin, Henry M. Levy, Chandramohan A. Thekkath: Implementing Global Memory Management in a Workstation Cluster ]