Paginering en virtueel geheugen

Een programma gebruikt virtuele adressen. Het fysieke geheugen bevat de bytes in paginaframes. Paginering verdeelt de virtuele adresruimte in even grote pagina's en het fysieke geheugen in paginaframes van dezelfde grootte. Het besturingssysteem kan elke pagina in elk vrij paginaframe plaatsen. Pagina 0 kan in paginaframe 12 staan en pagina 1 in paginaframe 3; het programma ziet nog steeds aaneengesloten virtuele adressen.

Dit neemt externe fragmentatie bij afzonderlijke paginatoewijzingen weg. Bij segmenten van variabele grootte kan een aanvraag mislukken doordat de vrije ruimte is verdeeld in gaten die te klein zijn. Bij paginering past een vrij paginaframe altijd bij één pagina. Een dunbezette adresruimte kan een groot gat tussen heap en stack laten zonder daarvoor fysieke paginaframes te reserveren.

Meet ongebruikte ruimte binnen pagina's

Paginering kent nog steeds interne fragmentatie. Een gebied moet hele pagina's innemen, ook als de laatste pagina gedeeltelijk leeg is. Een gebied van 9.000 bytes heeft drie pagina's van 4 KiB nodig: twee pagina's bevatten 8.192 bytes, zodat 808 bytes voor de derde overblijven. De toewijzing beslaat 12.288 bytes, waarvan 3.288 bytes ongebruikt zijn. KiB betekent 1.024 bytes; MiB betekent 1.048.576 bytes. Sommige boeken gebruiken KB en MB voor deze binaire hoeveelheden.

Splits het adres in velden

Een adres duidt zowel een pagina als een byte daarbinnen aan. Bij een paginagrootte van $2^k$ bytes vormen de lage $k$ bits de offset. De overige hoge bits vormen het virtuele paginanummer, of VPN. Een adres van 32 bits heeft bij pagina's van 4 KiB 12 offsetbits en 20 VPN-bits. In die adresruimte zijn $2^{20}$ virtuele pagina's mogelijk.

Bij 0x00403A7C geven de laatste drie hexadecimale cijfers offset 0xA7C, omdat elk hexadecimaal cijfer vier bits vertegenwoordigt. De eerste vijf cijfers geven VPN 0x00403. Deze verkorte werkwijze werkt hier omdat de veldgrens tussen hexadecimale cijfers valt. Tel bij een andere paginagrootte eerst de bits voordat je de geschreven hexadecimale waarde splitst.

Decimaal rekenen geeft hetzelfde resultaat:

Hier is $P$ de paginagrootte in bytes. Bij pagina's van 1.024 bytes heeft virtueel adres 5.000 VPN 4 en offset 904. Vier volledige pagina's zijn samen goed voor 4.096 bytes; de resterende 904 bytes bepalen de plaats van het adres binnen pagina 4. Offsets beginnen bij nul, dus lopen de offsets van deze pagina van 0 tot en met 1.023.

De vertaling vervangt het VPN door een fysiek paginaframenummer. De offset wordt ongewijzigd overgenomen: byte 904 van een virtuele pagina is byte 904 van het bijbehorende paginaframe. Het paginanummer alleen is geen byteadres. Vermenigvuldig een paginaframenummer met de paginagrootte om het beginadres van het paginaframe te vinden en tel vervolgens de offset erbij op.

Kies een paginagrootte

Grotere pagina's verminderen het aantal geheugenkoppelingen en laten elke gecachete vertaling meer bytes bestrijken. Ze verspillen ook meer ruimte in gedeeltelijk gebruikte pagina's en verplaatsen meer gegevens wanneer een pagina wordt geladen. Een veelgebruikte basispaginagrootte is 4 KiB; andere systemen gebruiken 16 KiB of 64 KiB. x86-64 ondersteunt ook grote geheugenkoppelingen, zoals pagina's van 2 MiB.

Een paginatabel legt de geheugenkoppelingen van een proces vast. In een lineaire paginatabel is het VPN de index van een array: vermelding 4 beschrijft virtuele pagina 4. Elk proces heeft een eigen tabel, zodat hetzelfde virtuele adres in verschillende processen naar verschillende fysieke bytes kan verwijzen. Bij een contextwisseling selecteert het besturingssysteem de tabel van het nieuwe proces via een paginatabelbasisregister.

Lees de toestand en rechten van een vermelding

Een paginatabelvermelding, of PTE, bevat een fysiek paginaframenummer (PFN) en besturingsinformatie. In het onderwijsmodel geeft een geldigheidsbit aan dat de pagina tot de adresruimte behoort; een aanwezigheidsbit geeft aan dat de inhoud in het fysieke geheugen aanwezig is. Beschermingsbits regelen lezen, schrijven, uitvoeren en gebruikerstoegang. Een wijzigingsbit legt schrijfbewerkingen vast sinds het voor het laatst is gewist. Een gebruiksbit legt gebruik vast sinds het voor het laatst is gewist; het heet ook een referentiebit.

Dit zijn begripsmatige rollen, geen garantie dat hardware overal hetzelfde is ingedeeld. x86 heeft geen afzonderlijk geldigheidsbit in een PTE. Als het aanwezigheidsbit is gewist, raadpleegt het besturingssysteem zijn eigen administratie om een ongebruikt adres te onderscheiden van een geldige pagina die elders is opgeslagen. Op x86 stelt de hardware het gebruiks- en wijzigingsbit in; het besturingssysteem beheert en wist ze.

Zoek de vermelding en de byte

Om een adres met een lineaire tabel te vertalen:

1. Splits het virtuele adres in VPN en offset.
2. Zoek de vermelding op $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}+\mathrm{V}\mathrm{P}\mathrm{N}\times \mathrm{P}\mathrm{T}\mathrm{E}\text{-}\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}\mathrm{t}\mathrm{e}$.
3. Controleer of de geheugenkoppeling bestaat, aanwezig is en deze toegang toestaat.
4. Vorm het fysieke adres met $\mathrm{P}\mathrm{F}\mathrm{N}\times \mathrm{p}\mathrm{a}\mathrm{g}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}\mathrm{t}\mathrm{e}+\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{s}\mathrm{e}\mathrm{t}$.
5. Lees of schrijf de byte op dat fysieke adres.

Bij pagina's van 1.024 bytes geeft virtueel adres 5.000 VPN 4 en offset 904. Stel dat PTE 4 aanwezig is en de gevraagde leesbewerking toestaat, met PFN 9. Paginaframe 9 begint op 9.216, dus is het fysieke byteadres 10.120. Het adres van de tabel zelf vereist een afzonderlijke berekening: als vermeldingen 4 bytes innemen, ligt PTE 4 16 bytes na de tabelbasis.

Een hexadecimaal voorbeeld: pagina's van 4 KiB splitsen 0x00403A7C in VPN 0x403 en offset 0xA7C. Als de toegestane geheugenkoppeling PFN 0x1F2B5 bevat, is het fysieke adres 0x1F2B5A7C. De PTE staat op basis + 0x403 × 4 = basis + 0x100C. De offset toevoegen vormt een gegevensadres; het VPN met de vermeldingsgrootte vermenigvuldigen bepaalt de locatie van de PTE. Deze twee adressen hebben verschillende doelen.

Een mislukte controle veroorzaakt een exceptie. Het besturingssysteem kan een geldige, niet aanwezige pagina binnenhalen, met nullen gevuld geheugen leveren of een andere geldige geheugenkoppeling herstellen. Een ongeldig adres of verboden toegang veroorzaakt meestal een segmentatiefout. Een aanwezige pagina kan een schrijfbewerking nog steeds afwijzen als de bescherming schrijven verbiedt.

Tel tabelruimte en leesbewerkingen uit het geheugen

Lineaire tabellen zijn zelfs voor kleine processen kostbaar. Bij virtuele adressen van 32 bits en pagina's van 4 KiB heeft elke tabel 1.048.576 vermeldingen nodig. Bij 4 bytes per vermelding is dat 4 MiB per proces, inclusief vermeldingen voor ongebruikte virtuele pagina's. Honderd processen hebben alleen al voor deze tabellen 400 MiB nodig.

Ze voegen ook een opzoeking toe aan elke geheugenverwijzing. In een eenvoudig model zonder vertaalcache leest de processor één PTE en vervolgens de gevraagde gegevens: twee geheugentoegangen. Delen blijft mogelijk: twee processen kunnen hun afzonderlijke virtuele pagina's bewust aan hetzelfde PFN koppelen, zoals bij alleen-lezen-programmacode.

Een adresvertaalbuffer, of TLB, is een kleine hardwarecache voor adresvertalingen in de geheugenbeheereenheid (MMU). De buffer bevat recente koppelingen van VPN naar PFN en toegangsinformatie. De buffer cachet vertalingen, terwijl een gegevenscache programmabytes bevat. Een programma kan in de ene cache een misser en in de andere een treffer hebben.

Volg treffers en missers

Bij een TLB-treffer haalt de MMU het PFN uit de gecachete vermelding, controleert de toegangsrechten en combineert het PFN met de ongewijzigde offset. De MMU hoeft de paginatabel niet te lezen. Ook bij een treffer moet de bescherming altijd worden afgedwongen. Het geldigheidsbit van de TLB geeft aan dat een gecachete vermelding bruikbaar is; het zegt niet of een virtuele pagina tot de adresruimte van het proces behoort.

Bij een TLB-misser moet het systeem de vertaling opzoeken in de paginatabel. Als de pagina aanwezig is en de toegang is toegestaan, plaatst het systeem de vertaling in de TLB en voltooit of herhaalt het de verwijzing. Er hoeft niets van de opslag te worden gelezen. Als de tabel daarentegen een ontbrekende geheugenkoppeling of verboden toegang aangeeft, moet het besturingssysteem een paginafout afhandelen. Een TLB-misser op zichzelf is geen paginafout.

Voorspel hergebruik met lokaliteit

TLB's kunnen veel minder vermeldingen bevatten dan er virtuele pagina's zijn, maar werken toch goed doordat programma's lokaliteit vertonen. Ruimtelijke lokaliteit betekent dat nabije adressen kort na elkaar worden gebruikt. Zodra één vertaling is gecachet, kunnen veel adressen binnen die pagina die gebruiken. Temporele lokaliteit betekent dat onlangs gebruikte adressen waarschijnlijk opnieuw worden gebruikt, zoals de instructies in een lus.

Neem 16.384 gehele getallen van elk vier bytes die achtereenvolgens in een array staan die op een paginagrens begint. Bij pagina's van 4 KiB bevat elke pagina 1.024 gehele getallen, zodat de array 16 pagina's beslaat. Als de TLB aanvankelijk leeg is en er geen storende vertalingen zijn, veroorzaakt het eerste gehele getal op elke pagina een misser. De volgende 1.023 op die pagina zijn treffers. In totaal zijn er 16 missers en 16.368 treffers, met een trefferpercentage van ongeveer 99,9%.

De toegangsvolgorde verandert dat resultaat. In C slaat int a[1024][1024] rijen achtereenvolgens op. Ga uit van gehele getallen van vier bytes, uitlijning op een paginagrens, pagina's van 4 KiB en een LRU-TLB met 64 vermeldingen. Elke rij neemt één pagina in. Doorlopen per rij levert één misser per rij op, oftewel 1.024 missers. Doorlopen per kolom bezoekt 1.024 verschillende pagina's voordat de eerste opnieuw aan bod komt. De vertaling daarvan is al verwijderd, dus zijn alle 1.048.576 arrayverwijzingen missers. De grootte van de array is onveranderd; de hergebruiksafstand verandert.

Bereken de gemiddelde kosten van treffers en missers

Het tijdmodel moet aangeven wat een treffer en een misser kosten. Stel dat een geheugentoegang 100 ns duurt, de TLB-opzoeking geen tijd toevoegt en een misser in een lineaire tabel één leesbewerking uit het geheugen toevoegt. Een treffer kost 100 ns en een met succes afgehandelde misser kost 200 ns. Bij een trefferpercentage van 98%:

Dit gemiddelde omvat in beide gevallen de uiteindelijke gegevenstoegang. Als je alleen de extra PTE-leesbewerking als de volledige kosten van een misser telt, onderschat je het totaal. Bij tabellen met meerdere niveaus kan een misser meerdere leesbewerkingen uit tabellen vereisen, zodat lokaliteit nog belangrijker is.

Bij een TLB-misser moet een vertaling worden opgezocht, maar architecturen verdelen dat werk verschillend. Bij een door hardware beheerde TLB, zoals op x86 en ARM, doorloopt de MMU de paginatabel vanaf de geselecteerde tabelbasis. De hardware bepaalt welke tabelvorm ze kan doorlopen. Als de geheugenkoppeling bruikbaar is, vult de hardware de vertaalcache zonder voor de gewone misser een afhandelaar van het besturingssysteem aan te roepen.

Een door software beheerde TLB, gebruikt in klassieke MIPS- en SPARC-ontwerpen, veroorzaakt bij een misser een exceptie. Een afhandelaar van het besturingssysteem vindt de geheugenkoppeling en voegt die met geprivilegieerde instructies toe. Dit geeft het besturingssysteem meer vrijheid in de tabelstructuur. Bij terugkeer uit deze exceptie wordt de instructie die de misser veroorzaakte opnieuw geprobeerd; bij terugkeer uit een systeemaanroep gaat de uitvoering normaal gesproken verder na de aanroep.

Houd de aanvulafhandelaar bereikbaar

De misserafhandelaar heeft betrouwbare toegang nodig tot zijn eigen instructies en gegevens. Als de afhandeling van een misser direct hetzelfde onopgeloste type misser binnen de afhandelaar veroorzaakt, kan de voortgang vastlopen. Ontwerpen voorkomen dit met geheugen zonder adresvertaling of permanent vastgezette vertalingen voor de noodzakelijke code en gegevens van de afhandelaar.

Selecteer de juiste adresruimte

Contextwisselingen brengen een ander probleem mee. Proces A kan VPN 7 aan paginaframe 20 koppelen, terwijl proces B VPN 7 aan paginaframe 90 koppelt. Als na de wisseling naar B de niet-gemarkeerde vermelding van A blijft staan, zou B naar het verkeerde paginaframe worden gestuurd. Het laden van de paginatabelbasis van B maakt een gecachete koppeling zonder identificatie op zichzelf niet veilig.

Eén oplossing is om bij een wisseling de relevante TLB-vermeldingen ongeldig te maken. Hun geldigheidsbits worden gewist, zodat het nieuwe proces de vermeldingen opnieuw moet vullen. Een andere oplossing voorziet vermeldingen van een adresruimte-identificatie (ASID). Bij het zoeken worden dan zowel de virtuele pagina als de bijbehorende adresruimte-identificatie vergeleken. x86 noemt die identificatie een procescontextidentificatie, of PCID. Vermeldingen voor meerdere adresruimten kunnen gecachet blijven, terwijl de hardware alleen die van de huidige context selecteert. Hergebruik van identificaties moet nog steeds worden beheerd, zodat een oude vermelding niet voor een nieuwe adresruimte wordt aangezien.

Maak gewijzigde geheugenkoppelingen ongeldig

Een wijziging van een PTE maakt ook een gecachete vertaling verouderd. Stel dat het besturingssysteem het schrijfrecht in het geheugen verwijdert, maar een beschrijfbare TLB-vermelding laat staan. De processor zou via die oude vermelding schrijfbewerkingen kunnen blijven toestaan. Het besturingssysteem moet de betrokken vertalingen ongeldig maken. Op een machine met meerdere processorkernen moet elke kern die de koppeling kan cachen meedoen. Deze coördinatie heet een TLB-shootdown.

Bereken het vertaalbereik

Naast correctheid is ook capaciteit van belang. Het TLB-bereik is de hoeveelheid geheugen die door de gecachete vertalingen wordt vertegenwoordigd:

Een TLB met 64 vermeldingen bereikt 256 KiB bij pagina's van 4 KiB en 128 MiB bij pagina's van 2 MiB. Het bereik beschrijft hoeveel geheugen kan worden gekoppeld, niet de capaciteit van het fysieke geheugen. Bestaande processors kunnen afzonderlijke TLB-capaciteiten voor verschillende paginagroottes hebben; deze berekening vergelijkt daarom een vast aantal vermeldingen.

Wanneer een TLB vol is, vervangt die een vertaling. LRU geeft de voorkeur aan onlangs gebruikte vermeldingen; willekeurige vervanging kiest zonder recent gebruik bij te houden. Een ronde langs één pagina meer dan past, is ongunstig voor LRU omdat elke vertaling wordt verwijderd vlak voordat die opnieuw nodig is.

Een lineaire paginatabel reserveert één vermelding voor elke mogelijke virtuele pagina. De meeste processen gebruiken maar een klein deel van hun adresruimte: code en heap liggen dicht bij het ene uiteinde, de stack bij het andere en een groot gat scheidt ze. Een tabel met miljoenen ongeldige vermeldingen neemt nog steeds geheugen in. Om deze kosten te verlagen, verander je de paginagrootte, de tabelorganisatie of beide.

Verminder het aantal pagina's

Grotere pagina's verminderen het aantal VPN's. Bij een adresruimte van 32 bits en pagina's van 16 KiB vormen 14 bits de offset en 18 bits het VPN. Een lineaire tabel heeft dan 262.144 vermeldingen nodig. Bij 4 bytes per vermelding neemt die 1 MiB in, tegenover 4 MiB bij pagina's van 4 KiB. Dit bespaart tabelruimte, hoewel het proces nog steeds 4 GiB aan virtuele bytes kan adresseren.

De kosten verschuiven naar elders. Een kleine toewijzing kan meer ruimte in de laatste pagina verspillen en bij het binnenhalen van een pagina worden meer bytes overgedragen. Een grotere paginagrootte maakt geen onderscheid tussen een dichtgebruikt deel van de adresruimte en een ongebruikt gat; beide krijgen alleen minder vermeldingen.

Laat gaten weg met afzonderlijke segmenttabellen

Een combinatie van segmentatie en paginering geeft code, heap en stack elk een eigen paginatabel. Elk segment heeft een tabelbasis en een grens voor zijn paginanummers. Het gat tussen segmenten heeft geen vermeldingen nodig. De vertaling selecteert eerst het segment, controleert de grens en zoekt dan de pagina binnen dat segment op.

Deze aanpak hangt af van een bruikbare indeling in segmenten. De tabellen kunnen verschillende lengtes hebben en aaneengesloten fysieke ruimte nodig hebben, waardoor voor de tabellen zelf opnieuw externe fragmentatie ontstaat. De gegevenspagina's van het proces blijven van vaste grootte; de gefragmenteerde objecten zijn nu de paginatabellen van variabele grootte.

Indexeer in plaats daarvan fysieke paginaframes

Een omgekeerde paginatabel verandert wat een vermelding beschrijft. De tabel heeft voor de hele machine één vermelding per fysiek paginaframe en legt het gebruikende proces en VPN vast. Bij 16 GiB fysiek geheugen en paginaframes van 4 KiB zijn 4.194.304 vermeldingen nodig, ongeacht hoeveel processen grote virtuele adresruimten hebben. Om dat aantal om te zetten in een totaal aantal bytes is nog de vermeldingsgrootte nodig.

Een gewone tabel gebruikt het VPN als directe array-index. Een omgekeerde tabel zoekt daarentegen naar het paar dat bestaat uit adresruimte-identiteit en VPN. Een hashstructuur kan dit efficiënt maken, maar bij botsingen kunnen extra zoekstappen nodig zijn. Gedeelde paginaframes vereisen ook extra afhandeling, omdat één paginaframe meerdere virtuele namen kan hebben. Gehashte paginatabellen, zoals in PowerPC-systemen, gebruiken verwante zoekideeën; een gehashte tabel is niet noodzakelijk een strikte omgekeerde tabel met één vermelding per paginaframe.

Wijs tabellen toe per gebruikt gebied

Paginatabellen met meerdere niveaus behouden opzoeken met een index en wijzen alleen tabelpagina's op lagere niveaus toe waar geheugenkoppelingen nodig zijn. Een vermelding op een hoger niveau kan een heel ongebruikt bereik markeren zonder de tabel op het lagere niveau toe te wijzen. Dit is de gebruikelijke oplossing op moderne systemen. De besparing is het grootst bij dunbezette adresruimten, terwijl een TLB-misser meer zoekstappen vereist.

Vergelijk de mogelijkheden door te vragen wat de grootte bepaalt. Een lineaire tabel schaalt met het aantal virtuele pagina's per proces. Een omgekeerde tabel schaalt met het aantal fysieke paginaframes voor het systeem. Een hiërarchie schaalt met de tabeltakken die nodig zijn voor de geheugenkoppelingen. Geen van deze aantallen is het aantal bytes aan programmagegevens dat momenteel aanwezig is.

Een paginatabel met twee niveaus verdeelt een grote lineaire tabel in stukken ter grootte van een pagina. Een paginadirectory verwijst naar die stukken. De directory wordt toegewezen, maar een paginatabelpagina op het lagere niveau wordt alleen toegewezen als voor het gebied ervan geheugenkoppelingen nodig zijn. Een ontbrekende directoryvermelding kan een heel ongebruikt bereik vertegenwoordigen.

Leid de 10/10/12-splitsing af

Neem een virtueel adres van 32 bits, pagina's van 4 KiB en vermeldingen van 4 bytes. Elke paginatabelpagina bevat 1.024 vermeldingen, dus selecteert een index van 10 bits een vermelding. Het adres wordt gesplitst in 10 directorybits, 10 tabelbits en 12 offsetbits. Elke tabel op het lagere niveau koppelt 1.024 pagina's en bestrijkt daarmee 4 MiB aan virtuele adressen. De directory heeft ook 1.024 vermeldingen en neemt één pagina van 4 KiB in.

Volg directory- en tabelvermeldingen

De doorgang volgt fysieke pointers:

1. Tel $\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}\text{-}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ op bij de fysieke basis van de directory. Lees die paginadirectoryvermelding (PDE).
2. Als die naar een tabelpagina verwijst, vermenigvuldig je het PFN met 4.096 om de fysieke basis van die tabel te krijgen.
3. Tel $\mathrm{t}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\times 4$ erbij op en lees de PTE.
4. Controleer de uiteindelijke geheugenkoppeling en combineer het PFN met de offset.

De PDE verwijst naar een tabel, terwijl de PTE naar de gevraagde gegevenspagina verwijst. Als je deze rollen verwart, gaat een verwijzing naar paginatabelgeheugen in plaats van naar de gegevens van het programma.

Voor virtueel adres 0x00803ABC is de directory-index 2, de tabelindex 3 en de offset 0xABC. Stel dat directoryvermelding 2 naar paginaframe 0xA1 verwijst. De tabel begint op 0xA1000. Vermelding 3 staat 12 bytes verder in die tabel, op 0xA100C. Als de toegestane, aanwezige PTE PFN 0x2F3C4 bevat, is het gegevensadres 0x2F3C4ABC.

Let op de twee verschillende vermenigvuldigingsfactoren. Een tabelindex telt vermeldingen, dus vermenigvuldig je die met de vermeldingsgrootte. Een PFN telt paginaframes, dus vermenigvuldig je dat met de paginagrootte. De offset telt bytes binnen de uiteindelijke pagina en heeft geen van beide factoren nodig. De directorybasis en de pointers die tijdens de doorgang worden gebruikt, zijn fysieke adressen; virtuele pointers gebruiken zou een andere vertaling vereisen om deze vertaling uit te voeren.

Tel tabellen en leesbewerkingen voor het opzoeken

Het ruimtegebruik hangt af van de verdeling van de geheugenkoppelingen. Stel dat een proces de onderste 8 MiB van zijn ruimte van 4 GiB gebruikt en de bovenste 4 MiB, met beide gebieden uitgelijnd op directorygrenzen. Het lage gebied heeft twee tabelpagina's nodig en het hoge gebied één. Met de directory erbij zijn dat vier pagina's, oftewel 16 KiB, in plaats van een lineaire tabel van 4 MiB. Als hetzelfde aantal gegevenspagina's dun verspreid over veel directorygebieden wordt gekoppeld, kunnen meer tabelpagina's nodig zijn.

In het basisonderwijsmodel betekent een ongeldige PDE dat geen van de pagina's in het bijbehorende gebied van 4 MiB tot de adresruimte behoort. De doorgang stopt zonder een PTE te lezen. Volledige besturingssystemen kunnen ontbrekende vermeldingen ook gebruiken voor uitgestelde toewijzing, zodat hun softwareadministratie bepaalt wat een volgens de hardware niet aanwezige vermelding betekent.

De hiërarchie bespaart ruimte door extra werk bij een TLB-misser. Een niet-gecachete doorgang door twee niveaus leest een PDE en een PTE voordat de gegevens worden benaderd: in totaal drie leesbewerkingen uit het geheugen, tegenover twee voor een lineaire tabel. Een TLB-treffer slaat die tabellezingen over. Daardoor is een hoog trefferpercentage vooral waardevol naarmate de hiërarchie dieper wordt.

Het aantal tabelniveaus volgt uit drie grootheden: de geïmplementeerde breedte van het virtuele adres, de paginagrootte en de vermeldingsgrootte. Bereken eerst de breedte van de offset. Bereken daarna hoeveel vermeldingen in één tabelpagina passen en hoeveel bits een vermelding selecteren. Verdeel ten slotte de resterende VPN-bits in indexvelden en rond het aantal niveaus zo nodig naar boven af.

Leid de vier niveaus af

Voor x86-64-paginering met vier niveaus is de geïmplementeerde breedte van het virtuele adres 48 bits. Een pagina van 4 KiB levert 12 offsetbits. Een vermelding van 8 bytes geeft 512 vermeldingen per tabelpagina, geselecteerd met 9 bits. Het VPN heeft 36 bits, dus zijn vier indexen van 9 bits nodig. Een succesvolle niet-gecachete doorgang volgt vier vermeldingen en benadert daarna de gegevens.

De niveaus zijn PML4, paginadirectorypointertabel, paginadirectory en paginatabel. Hun indexen beslaan respectievelijk bits 47–39, 38–30, 29–21 en 20–12. CR3 duidt de fysieke basis aan. Linux noemt de overeenkomstige niveaus PGD, PUD, PMD en PTE; de algemene hiërarchie bevat een P4D-niveau, dat wordt samengevouwen wanneer de architectuur slechts vier niveaus gebruikt.

Onderscheid adresbreedte van RAM

Een geïmplementeerde adresruimte van 48 bits bevat 256 TiB aan adresseerbare bytes. Adressen worden nog steeds in waarden van 64 bits opgeslagen: in de gewone canonieke vorm herhalen de bits boven bit 47 dat bit. De geldige lage en hoge bereiken worden gescheiden door een niet-canoniek gat. Dat dit een adresruimte van 48 bits heet, betekent niet dat elk 64-bitspatroon bruikbaar is of dat een proces 256 TiB RAM krijgt.

Een lineaire tabel zou enorm zijn. Er zijn $2^{36}$ virtuele pagina's; vermenigvuldiging met vermeldingen van 8 bytes geeft $2^{39}$ bytes, oftewel 512 GiB per proces. Een hiërarchie geeft ongebruikte bereiken weer met ontbrekende takken in plaats van al die vermeldingen te reserveren.

Processors die paginering met vijf niveaus ondersteunen, kunnen 57 geïmplementeerde virtuele adresbits gebruiken wanneer die modus is ingeschakeld. Boven de PML4 wordt nog één index van 9 bits toegevoegd, wat 128 PiB aan adresseerbare bytes en één mogelijke extra tabellezing oplevert. De bovenste bits van een canoniek adres herhalen dan bit 56. De processorondersteuning en de ingeschakelde pagineringsmodus bepalen welke breedte geldt.

Stop de doorgang bij een grote pagina

Grote pagina's stoppen de doorgang vroegtijdig. Op x86-64 kan een vermelding op paginadirectoryniveau rechtstreeks een pagina van 2 MiB koppelen, met 21 offsetbits over. Een paginadirectorypointervermelding kan een pagina van 1 GiB koppelen, met 30 offsetbits over. Lagere bits die anders vermeldingen op een lager niveau zouden selecteren, selecteren nu bytes binnen die grote pagina.

Dit vermindert zowel de lengte van de doorgang als het aantal vertalingen dat voor een bepaald gebied nodig is. Het vergroot het TLB-bereik, wat databases en andere grote werklasten kan helpen. De fysieke koppeling vereist een passend uitgelijnde aaneengesloten reeks paginaframes en een gedeeltelijk gebruikte grote pagina kan veel meer geheugen verspillen. Linux ondersteunt expliciete toewijzing van grote pagina's en transparante grote pagina's; de ondersteunde groottes hangen af van de architectuur.

De eenvoudige kostentelling gaat ervan uit dat geen tabelvermeldingen zijn gecachet. Bestaande processors cachen paginatabelstructuren en tabellezingen kunnen treffers in gewone caches opleveren. Vier niveaus betekenen daarom niet dat elke TLB-misser vier vertragingen door toegang tot het hoofdgeheugen oplevert. Ze beschrijven de afhankelijkheidsketen en de kosten zonder caching.

Virtuele adresruimten kunnen samen groter zijn dan het fysieke geheugen, omdat niet elke pagina aanwezig hoeft te blijven. Wisselruimte bewaart de inhoud van verdrongen pagina's op een schijf of SSD. Linux kan een wisselpartitie of wisselbestand gebruiken; Windows gebruikt een wisselbestand. Het fysieke geheugen bevat de verzameling pagina's die op dat moment aanwezig is.

Bij paginering worden afzonderlijke pagina's verplaatst. Bij uitwisselen wordt een pagina naar de achterliggende opslag geschreven voordat het paginaframe opnieuw wordt gebruikt; bij inwisselen wordt de pagina teruggelezen. Historisch betekende wisselen ook het verplaatsen van een heel proces. In moderne gesprekken verwijst het woord vaak naar het verplaatsen van pagina's, dus bepaal wat er wordt verplaatst.

Interpreteer de ontbrekende geheugenkoppeling

Het aanwezigheidsbit van een PTE vertelt de hardware of een aanwezige geheugenkoppeling beschikbaar is. Als een geldige pagina is uitgewisseld, legt het besturingssysteem vast waar de inhoud te vinden is, in door software bepaalde bits van de vermelding of in afzonderlijke metadata. Een aanwezigheidsbit van nul duidt op zichzelf niet op wisselruimte: het kan ook niet-toegewezen of uitgesteld toegewezen geheugen beschrijven.

Een paginafout is een exceptie die ontstaat door een toegang die met de huidige geheugenkoppeling niet kan worden voltooid. De fout kan wijzen op afwezigheid of een schending van de bescherming. De afhandelaar beslist of de toegang geldig is en hoe de fout kan worden opgelost. Bij een succesvolle afhandeling kunnen opgeslagen bytes worden geladen, met nullen gevuld geheugen worden geleverd, een bestaand aanwezig paginaframe worden gekoppeld of een privékopie worden gemaakt. Een werkelijk ongeldige toegang leidt meestal tot een segmentatiefout.

Herstel een opgeslagen pagina

Volg het lezen van een uitgewisselde pagina bij pagina's van 1.024 bytes:

1. Virtueel adres 5.000 geeft VPN 4 en offset 904.
2. De TLB heeft geen bruikbare vertaling. Bij het doorlopen van de paginatabel blijkt de geldige pagina niet aanwezig; de softwareadministratie wijst wisselblok 37 aan.
3. De afhandelaar verkrijgt paginaframe 9. Als geen paginaframe vrij is, moet eerst geheugen worden vrijgemaakt.
4. Het besturingssysteem leest blok 37 in paginaframe 9. Het proces dat de paginafout veroorzaakte wacht; een ander uitvoerbaar proces kan de CPU gebruiken.
5. Na voltooiing legt het besturingssysteem PFN 9 vast, markeert de geheugenkoppeling als aanwezig en maakt het proces uitvoerbaar.
6. De instructie wordt opnieuw geprobeerd. De vertaling bereikt nu fysiek adres 10.120.

De instructie hervat de bedoelde bewerking nadat de bytes beschikbaar zijn. Als de uitvoering de mislukte instructie zou overslaan, zou een lees- of schrijfbewerking verloren gaan. Het proces kan een vertraging merken, maar het virtuele adres is niet veranderd.

Deel de paginafout in en voorspel de vraag

Een paginafout met opslagtoegang vereist een leesbewerking van de opslag. Een paginafout zonder opslagtoegang wordt zonder die I/O opgelost, bijvoorbeeld door een met nullen gevuld paginaframe te leveren of een al aanwezig paginaframe te koppelen. Een groot aantal paginafouten zonder opslagtoegang betekent dus niet evenveel apparaatverkeer als hetzelfde aantal paginafouten met opslagtoegang. Op Linux rapporteert /usr/bin/time -v de twee aantallen voor een commando.

Paginering op aanvraag wacht met het leveren van een pagina totdat die wordt aangesproken. Daardoor kan een programma beginnen zonder alle inhoud te laden. Vooraf ophalen haalt pagina's binnen die naar verwachting binnenkort nodig zijn. Goede voorspellingen voorkomen later wachten; slechte voorspellingen gebruiken bandbreedte en geheugen voor pagina's die nooit worden gebruikt.

Houd de gebeurtenissen uit elkaar. Bij een TLB-misser moet een vertaling worden opgezocht. Bij een paginafout moet het besturingssysteem een probleem met een geheugenkoppeling afhandelen. Een segmentatiefout is een gebruikelijk resultaat van verboden toegang. Een aanwezige pagina waarvoor toegang is toegestaan, kan een TLB-misser veroorzaken zonder een van de andere gebeurtenissen.

Een zeldzame leesbewerking van de opslag kan de gemiddelde geheugentoegangstijd bepalen. Laat $p$ de kans zijn dat een verwijzing een paginafout met opslagtoegang veroorzaakt, $M$ de gewone toegangstijd en $F$ de totale afhandelingstijd voor een verwijzing die een paginafout veroorzaakt. Een eenvoudig model met twee gevallen geeft:

Hier omvat $F$ de leesbewerking van de opslag, het werk van het besturingssysteem en eventueel vereist terugschrijven van een gewijzigde te vervangen pagina. Het gaat om de totale tijd in het geval van een paginafout, niet alleen om een kleine extra tijd voor het opzoeken van een PTE.

Bereken het effect van zeldzame paginafouten

Stel dat een gewone toegang 100 ns duurt en een paginafout met opslagtoegang in totaal 8 ms. Reken 8 ms om naar 8.000.000 ns voordat je het gemiddelde berekent. Bij één paginafout per 1.000 verwijzingen:

Dit is ongeveer 81 keer de gewone toegangstijd. Een paginafoutfrequentie van 0,1% klinkt klein, maar een paginafout kost evenveel als vele duizenden geheugenverwijzingen.

Voor een vertraging van minder dan 10% moet het gemiddelde onder 110 ns blijven. Herschikken geeft:

Dat is minder dan ongeveer één paginafout met opslagtoegang per 800.000 verwijzingen. De toegestane kans hangt af van de aangenomen afhandelingstijd. Bij een voorbeeldtijd van 0,1 ms voor een SSD is de wachttijd korter, maar nog steeds 100.000 ns: duizend toegangen van 100 ns.

Houd paginaframes gereed

Het besturingssysteem probeert paginaframes gereed te hebben voordat een paginafout er één nodig heeft. Een paginadaemon op de achtergrond, zoals kswapd van Linux, maakt geheugen vrij wanneer het aantal vrije paginaframes onder een lage geheugendrempel daalt. In het basisdrempelmodel gaat de daemon door tot een hoge geheugendrempel is bereikt. Zo hoeft niet bij elke paginafout te worden gewacht tot een te vervangen pagina is geselecteerd en voorbereid.

Bewaar wijzigingen vóór hergebruik

Een gewijzigde pagina bevat wijzigingen sinds de wijzigingstoestand voor het laatst is gewist. Voordat het paginaframe opnieuw wordt gebruikt, moeten die wijzigingen worden bewaard als de pagina deel blijft uitmaken van het geheugen van een proces. Terugschrijven kan op de achtergrond gebeuren. Na succesvol terugschrijven kan de aanwezige pagina als ongewijzigd worden gemarkeerd; een latere schrijfbewerking maakt die weer gewijzigd.

Een ongewijzigde pagina kan alleen zonder nieuwe schrijfbewerking worden verwijderd als de inhoud kan worden teruggehaald of opnieuw kan worden aangemaakt. Ongewijzigde programmacode kan opnieuw uit het uitvoerbare bestand worden gelezen. Een pagina met een actuele kopie in de wisselruimte kan daaruit worden gelezen. Een ongewijzigde anonieme pagina zonder terug te halen kopie kan niet zomaar worden vergeten. Het wijzigingsbit alleen bewijst niet dat achterliggende opslag bestaat.

Als bij een paginafout synchroon een gewijzigde pagina moet worden verwijderd, kan dat een schrijfbewerking voor de te vervangen pagina vereisen, gevolgd door de gevraagde leesbewerking. De voorkeur geven aan een ongewijzigde, terug te halen pagina voor vervanging voorkomt die schrijfbewerking op het kritieke pad van de foutafhandeling. Bij bundeling worden meerdere schrijfbewerkingen gecombineerd tot grotere overdrachten, wat vooral op schijven nuttig is.

Paginafouten zijn nuttige aangrijpingspunten om werk uit te stellen. Een geheugenkoppeling kan tot een proces behoren voordat het besturingssysteem er een eigen paginaframe aan toewijst. Bij nulinitialisatie op aanvraag levert de eerste toegang met nullen gevuld geheugen op. Zo hoeft niet elke gereserveerde pagina vooraf te worden toegewezen en gewist. Nulinitialisatie voorkomt ook dat een proces achtergebleven gegevens van een ander proces ziet.

Voor de paginafout is geen leesbewerking van de schijf nodig, omdat de vereiste inhoud uit nullen bestaat en niet uit opgeslagen bytes. Het is een paginafout zonder opslagtoegang. Een systeem kan de implementatie optimaliseren, maar het zichtbare resultaat blijft dat pas geleverd geheugen de vereiste nullen bevat.

Deel alleen-lezencode

Afzonderlijke paginatabellen vereisen niet van elke pagina afzonderlijke kopieën. Twee PTE's kunnen hetzelfde PFN bevatten, ook op verschillende virtuele adressen. Processen die hetzelfde programma uitvoeren, kunnen alleen-lezencode delen. Vijftig processen die een editor gebruiken, kunnen verwijzen naar één aanwezige kopie van elke gedeelde codepagina. Alleen-lezenbescherming voorkomt dat één proces die instructies voor iedereen verandert.

Maak bij schrijven eigen inhoud

Kopiëren bij schrijven (COW) maakt het mogelijk pagina's aanvankelijk te delen terwijl later mogelijk eigen inhoud nodig is. Na fork() hebben ouder en kind afzonderlijke adresruimten, maar kunnen ze hun gewone privégegevenspaginaframes delen. Het besturingssysteem markeert hun beschrijfbare privégeheugenkoppelingen als alleen-lezen en legt vast dat het om COW-koppelingen gaat. Lezen lukt zonder te kopiëren.

Wanneer een van de processen voor het eerst naar een gedeelde COW-pagina schrijft, is die schrijfbewerking in strijd met de huidige bescherming en veroorzaakt ze een paginafout. De afhandelaar herkent het geldige COW-geval, wijst een eigen paginaframe toe, kopieert de pagina, legt een beschrijfbare geheugenkoppeling vast voor het schrijvende proces en probeert de instructie opnieuw. Het andere proces behoudt de oorspronkelijke inhoud. Het besturingssysteem moet ook zorgen dat gecachete vertalingen overeenkomen met de gewijzigde geheugenkoppelingen.

Stel dat een proces 400 MiB aan aanwezige privégegevens heeft en dat het kind naar drie verschillende pagina's van 4 KiB schrijft voordat het exec() aanroept. De gegevens die door die schrijfbewerkingen worden gekopieerd, zijn in totaal 12.288 bytes. Herhaald schrijven naar één pagina die al privé is, veroorzaakt niet telkens een nieuwe kopie van de hele pagina. Het aanmaken van paginatabellen en andere procesadministratie kosten nog steeds tijd en ruimte; COW voorkomt dat alle 400 MiB aan gegevens vooraf wordt gekopieerd.

Dit is vooral nuttig wanneer kort na fork() een aanroep van exec() volgt, die de adresruimte van het kind vervangt. Alle oude gegevens direct kopiëren zou werk opleveren dat het kind mogelijk nooit benut. Opzettelijk gedeelde beschrijfbare geheugenkoppelingen hebben een andere betekenis: COW beschrijft de privékoppelingen die bij een schrijfbewerking uiteen moeten gaan.

Een alleen-lezen-PTE alleen maakt een koppeling nog geen COW-koppeling. Schrijven naar werkelijk alleen-lezen-programmacode is een fout; schrijven naar een door COW beschermde gegevenspagina kan worden hersteld. De softwareadministratie onderscheidt de gevallen, zodat dezelfde hardwarematige beschermingsfout kan leiden tot een succesvolle nieuwe poging of een segmentatiefout.

Bescherm kernelkoppelingen

Ook kernelkoppelingen gebruiken bescherming. Een traditioneel ontwerp koppelt kernelgeheugen in de adresruimte van elk proces met toegang uitsluitend voor de kernel, zodat de kernel kan worden binnengegaan zonder een volledig andere geheugenkoppeling te selecteren. Code in gebruikersmodus kan die pagina's niet benaderen alleen omdat ze adressen hebben. Isolatie van kernelpaginatabellen, op getroffen systemen ingevoerd nadat Meltdown in 2018 bekend werd, verwijdert de meeste kernelkoppelingen terwijl gebruikerscode draait en wisselt bij het binnengaan van de kernel van geheugenkoppelingen.

Een vervangingsbeleid kiest een aanwezige pagina om te verwijderen wanneer voor een benodigde pagina geen vrij paginaframe beschikbaar is. Het fysieke geheugen werkt als een cache voor pagina-inhoud. Het beleid probeert pagina's te bewaren waarvan toekomstig gebruik kostbare paginafouten voorkomt. Een misser bij paginavervanging is een abstracte gebeurtenis waarbij een pagina niet aanwezig is; of I/O nodig is, hangt af van de herkomst van de ontbrekende inhoud.

Registreer treffers en missers

Vergelijk beleidsvormen met dezelfde paginaverwijzingsreeks, hetzelfde aantal paginaframes en dezelfde begintoestand. Een paginaverwijzingsreeks vermeldt paginanummers in toegangsvolgorde. Vraag bij elke verwijzing eerst of de pagina aanwezig is. Zo ja, noteer je een treffer. Zo niet, noteer je een misser, laad je de pagina en verwijder je alleen een pagina voor vervanging als het geheugen al vol is.

Eerste verwijzingen zijn missers, ook zolang er nog paginaframes vrij zijn. Deze onvermijdelijke missers bij eerste gebruik kunnen niet worden voorkomen door een andere pagina voor vervanging te kiezen. Latere missers door onvoldoende capaciteit zijn capaciteitsmissers. Bij paginavervanging zijn er geen plaatsingsconflicten: een pagina kan elk paginaframe bezetten. Conflictmissers horen bij caches met beperkte plaatsingsmogelijkheden, niet bij dit volledig flexibele paginaframemodel.

Kies het gebruik dat het verst in de toekomst ligt

Het optimale beleid, OPT of MIN, kiest de pagina waarvan het volgende gebruik het verst in de toekomst ligt. Een pagina die nooit meer wordt gebruikt, is een ideale kandidaat voor vervanging. Dit levert het kleinste aantal missers op voor een bekende paginaverwijzingsreeks, maar een draaiend besturingssysteem kan willekeurige toekomstige verwijzingen niet kennen. OPT biedt een maatstaf voor praktisch beleid.

Gebruik drie aanvankelijk lege paginaframes en de reeks 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. De eerste drie verwijzingen vullen het geheugen en zijn missers. De volgende 1 is een treffer. Bij verwijzing 5 komt pagina 4 binnen: aanwezige pagina's 1, 2 en 3 worden vervolgens gebruikt op posities 6, 8 en 11. Verwijder 3, waarvan het volgende gebruik het verst weg ligt.

Nadat 1 een treffer oplevert, komt pagina 5 binnen op positie 7. Aanwezige pagina's 1, 2 en 4 worden vervolgens gebruikt op posities 9, 8 en 10, dus verwijdert OPT pagina 4. De volgende 2 en 1 zijn treffers. Pagina 4 is een misser op positie 10; 2 of 5 mag worden verwijderd omdat geen van beide opnieuw wordt gebruikt. Daarna is pagina 3 een misser en wordt een andere pagina verwijderd die niet meer wordt gebruikt. De laatste 1 is een treffer.

Vergelijk totalen en werklasten

Het verloop heeft 7 missers en 5 treffers. Als je alle 12 verwijzingen meetelt, is het trefferpercentage 5/12, oftewel ongeveer 41,7%. Er zijn vijf verschillende pagina's, dus vijf onvermijdelijke missers bij eerste gebruik. Als die missers niet worden meegerekend, wordt het gerapporteerde percentage 5/7, oftewel ongeveer 71,4%. Beide percentages kunnen hetzelfde verloop beschrijven, dus vermeld altijd de noemer.

Houd de huidige verwijzing gescheiden van het toekomstige deel van de reeks om je plaats niet kwijt te raken. OPT vergelijkt het volgende gebruik van elke aanwezige pagina na de huidige positie; het kiest niet de pagina met het grootste nummer of de pagina die als eerste is geladen. Als twee pagina's nooit meer worden gebruikt, blijft de uitkomst bij beide keuzes optimaal.

De werklast bepaalt hoeveel het beleid uitmaakt. Als verwijzingen naar alle pagina's even waarschijnlijk zijn, biedt eerder gebruik weinig houvast. Bij lokaliteit krijgt een kleine, vaak gebruikte verzameling veel verwijzingen en verbetert het bewaren daarvan het trefferpercentage. Het verschil tussen het aantal missers van een praktisch beleid en dat van OPT meet de mogelijke verbetering voor die werklast.

FIFO verwijdert de pagina die van de huidige aanwezige pagina's het eerst is geladen. Een wachtrij houdt de volgorde van binnenkomst bij. Een treffer verplaatst de pagina niet naar de achterkant van die wachtrij. Daardoor is FIFO eenvoudig bij te houden, maar kan het een pagina verwijderen die nog vaak wordt gebruikt, alleen omdat die lang geleden binnenkwam.

Houd het laatste gebruik bij in plaats van de binnenkomst

LRU houdt het recentste gebruik van elke aanwezige pagina bij. Bij een treffer wordt die pagina de meest recent gebruikte; bij een misser met vol geheugen verdwijnt de pagina waarvan het laatste gebruik het langst geleden is. Dit volgt uit temporele lokaliteit: recent gebruik voorspelt vaak gebruik in de nabije toekomst. Binnenkomsttijd en laatste gebruik vormen verschillende geschiedenissen.

Willekeurige paginavervanging kiest willekeurig een aanwezige pagina voor vervanging zonder de volgorde van recent gebruik bij te houden. Het resultaat verschilt per uitvoering. Dit beleid kan het deterministische faalpatroon van LRU bij een cyclische werklast vermijden, maar kan nog steeds ongelukkige keuzes maken. LFU houdt aantallen bij in plaats van recent gebruik. Zonder geleidelijke verlaging van die aantallen kan LFU een pagina behouden die in een eerdere programmafase populair was, maar nu ongebruikt is.

Volg beleidsvormen op dezelfde reeks

Vergelijk drie lege paginaframes met 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1. Pagina's 1, 2 en 3 vullen eerst het geheugen. De treffer op 1 laat de FIFO-volgorde ongewijzigd, dus verwijdert de binnenkomende 4 pagina 1. LRU beschouwt 1 daarentegen als recent en verwijdert 2. De volgende verwijzing naar 1 is daarom een misser bij FIFO en een treffer bij LRU.

Bij LRU verwijderen de latere missers pagina 3 voor pagina 5, 4 voor pagina 2, 5 voor pagina 4 en 2 voor pagina 3. Het eindresultaat is 8 missers en 4 treffers. FIFO heeft 10 missers en 2 treffers. OPT heeft 7 missers op dezelfde reeks. LRU presteert hier beter dan FIFO, maar bereikt niet het optimum dat kennis van de toekomst vereist.

Leg de anomalie van Belady uit

Meer paginaframes verbeteren niet elk beleid op elke reeks. De anomalie van Belady is een toename van missers wanneer FIFO meer paginaframes krijgt. Voor 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 heeft FIFO 9 missers met drie paginaframes en 10 met vier. Extra capaciteit verandert de pagina's die later uit de wachtrij worden verwijderd, zodat de verzamelingen aanwezige pagina's niet noodzakelijk in elkaar passen.

LRU en OPT zijn stackalgoritmen: bij een consistente afhandeling van gelijke keuzes is de verzameling aanwezige pagina's bij een kleiner aantal paginaframes opgenomen in die bij een groter aantal. Een grotere capaciteit kan een treffer bij minder geheugen daardoor niet in een misser bij meer geheugen veranderen. LRU geeft op de reeks voor de anomalie 10 missers met drie paginaframes en 8 met vier.

Herken werklasten waarvoor recent gebruik slecht werkt

LRU kent nog steeds ongunstige werklasten. Doorloop drie keer pagina's 1, 2, 3, 4 met drie paginaframes. Elke nieuwe pagina verwijdert de pagina die als volgende nodig is, wat 12 missers oplevert. OPT heeft er 6 nodig. Willekeurige paginavervanging kan bruikbare pagina's gedurende een ronde behouden en presteert hier gemiddeld beter. Ook een eenmalige scan kan een bruikbare, vaak gebruikte verzameling uit een LRU-cache verdringen.

Een beleidsvergelijking moet de werklast en het aantal paginaframes vermelden. Lokaliteit maakt recent gebruik nuttig in veel programma's en vormt zo een reden om LRU in bestaande systemen te benaderen. Een terugkerende lus die net groter is dan de capaciteit, vraagt om een andere keuze; een waargenomen voordeel op één kort verloop bewijst geen algemene rangorde.

Exacte LRU vereist werk bij elke geheugenverwijzing. Met tijdstempels werkt elke verwijzing een tijdstempel bij en zoekt de selectie van een te vervangen pagina naar de oudste. Met een geordende lijst staat de te vervangen pagina achteraan klaar, maar moet elke verwijzing de pagina naar voren verplaatsen. Deze structuur bij elke lees- en schrijfbewerking in software bijwerken zou te kostbaar zijn.

Lees het gebruiksbit

De hardware biedt een goedkoper signaal: het gebruiksbit, ook referentiebit genoemd. De hardware stelt het in wanneer een pagina wordt gelezen of beschreven. Het besturingssysteem wist het om een nieuw waarnemingsinterval te beginnen. Een ingesteld bit betekent minstens één gebruik sinds het laatste wissen; het telt de frequentie niet en onthult niet de exacte volgorde van laatste gebruik.

Zoek een pagina voor vervanging

Het klokalgoritme plaatst paginaframes in een cirkel en houdt een wijzer bij die naar de volgende kandidaat wijst. Bij vervanging onderzoekt het het gebruiksbit van de kandidaat. Als het bit 1 is, wist de wijzer het en schuift door. Als het bit 0 is, wordt dat paginaframe gekozen voor vervanging. De nieuwe pagina komt binnen met het gebruiksbit ingesteld en de wijzer schuift er voorbij. Een treffer stelt het bit van de aangesproken pagina in zonder de wijzer te verplaatsen.

Stel dat de cirkel A met bit 1, B met bit 0 en C met bit 1 bevat en dat de wijzer op A staat. Een paginafout op D wist het bit van A en verplaatst de wijzer naar B. B heeft al bit 0, dus vervangt D pagina B met bit 1 en eindigt de wijzer bij C. Als de volgende verwijzing een paginafout op E is, wist de wijzer het bit van C, vindt vervolgens A met bit 0 en vervangt A. Als A tussen die paginafouten was aangesproken, zou het bit 1 zijn en zou A opnieuw een kans krijgen.

Als elk bit 1 is en er tussendoor geen nieuwe toegangen zijn, wist één ronde ze allemaal. De wijzer verwijdert dan bij terugkomst de pagina waar hij begon. Die specifieke keuze lijkt op de volgende kandidaat in FIFO-volgorde, maar het klokalgoritme volgt doorgaans de gebruiksgeschiedenis en de positie van de wijzer; het is niet altijd gelijk aan FIFO.

Een volledig verloop van het klokalgoritme vereist een afspraak over de begintoestand. Hier worden lege paginaframes op volgorde gevuld met bit 1; de wijzer blijft bij paginaframe 0 tot de eerste vervanging. Treffers stellen bits in. Bij elke vervanging schuift de wijzer door. Volgens die afspraak leveren drie paginaframes op 1, 2, 3, 1, 4, 1, 5, 2, 1, 4, 3, 1 10 missers op. Een korte reeks kan het voordeel van een benadering van recent gebruik verbergen; over langere uitvoeringen volgt het klokalgoritme lokaliteit vaak goed.

Houd rekening met schrijfkosten en bestaande varianten

Een gewijzigde toestand voegt de kosten toe om een te vervangen pagina te bewaren. Een voorkeur bij het verbeterde klokalgoritme rangschikt paren (gebruiksbit, wijzigingsbit) als (0, 0), (0, 1), (1, 0) en vervolgens (1, 1). Dit geeft de voorkeur aan een pagina zonder recent gebruik en zonder niet-opgeslagen wijzigingen. Implementaties verschillen in de manier waarop ze bij het doorlopen bits wissen en schrijfbewerkingen plannen. Terugschrijven op de achtergrond kan een gewijzigde kandidaat ongewijzigd maken voordat vervanging nodig is.

Bestaande systemen gebruiken uitgebreidere varianten. VAX/VMS plaatste verwijderde pagina's op lijsten met ongewijzigde of gewijzigde pagina's, zodat een proces een pagina kon terughalen voordat het paginaframe opnieuw werd gebruikt. Linux heeft actieve en inactieve lijsten gebruikt en biedt LRU met meerdere generaties, dat pagina's groepeert op waargenomen recent gebruik. Deze systemen gebruiken aanwijzingen van de hardware voor beslissingen van het besturingssysteem; het gebruiksbit van de hardware kiest zelf geen pagina voor vervanging.

Overmatig wisselen van pagina's treedt op wanneer processen het grootste deel van hun tijd besteden aan het via paginafouten binnenhalen van pagina's en het verwijderen van pagina's die snel weer nodig zijn. Het opslagapparaat blijft bezet terwijl de CPU-bezettingsgraad daalt, hoewel programma's nog werk hebben. Een lage CPU-belasting alleen toont geen overmatig wisselen aan; de combinatie van veel paginering en weinig voortgang is de aanwijzing.

De oorzaak is een geheugenvraag die groter is dan het aantal beschikbare paginaframes. Een proces heeft een bruikbare verzameling aanwezige pagina's nodig om de huidige fase te voltooien. Als de actieve verzamelingen van meerdere processen niet samen passen, verdringen hun paginafouten telkens bruikbare pagina's. Nog meer processen starten kan deze druk verergeren, ook al lijkt de CPU onderbenut.

Schat de huidige vraag naar pagina's

De werkverzameling, geschreven als $W(t,\mathrm{\Delta })$, schat de huidige behoeften van een proces. In het verwijzingsvenstermodel is dit de verzameling verschillende pagina's in de laatste $\mathrm{\Delta }$ verwijzingen die eindigen op tijdstip $t$. Tel elke pagina één keer, ook als die meerdere keren in het venster voorkomt. De grootte van de werkverzameling is een aantal pagina's, niet het aantal verwijzingen.

Bekijk met venster 5 en de reeks 1, 2, 1, 3, 2, 1, 4, 5, 4, 5, 4, 6, 5, 4 de toestand na verwijzing 6. De laatste vijf verwijzingen zijn 2, 1, 3, 2, 1, wat {1, 2, 3} geeft, met grootte 3. Na verwijzing 8 is het venster 3, 2, 1, 4, 5, met grootte 5. Na verwijzing 11 is het 4, 5, 4, 5, 4, met grootte 2. De vraag bereikt tijdelijk een piek wanneer oude en nieuwe fasen overlappen.

Beheer de actieve vraag en toewijzing

Een kort venster kan pagina's weglaten die nog nodig zijn; een te lang venster kan pagina's uit een afgeronde fase bevatten. Het werkverzamelingsmodel van Peter Denning koppelt deze veranderende behoeften aan de toewijzing. Werkverzamelingsbeleid voert processen alleen uit als hun gezamenlijke werkverzamelingen passen. Als dat niet zo is, schort het één of meer processen op en geeft het hun paginaframes vrij. Dit is toelatingsregeling.

Regeling op basis van de paginafoutfrequentie (PFF) gebruikt gemeten foutfrequenties. Boven een bovengrens heeft een proces meer paginaframes nodig. Onder een ondergrens kunnen sommige paginaframes opnieuw worden toegewezen. Als een proces paginaframes nodig heeft en er geen beschikbaar zijn, kan het nodig zijn een proces op te schorten. Twee drempels verminderen voortdurende aanpassingen rond één grens.

Bij globale paginavervanging kan een paginafout een pagina van een ander proces verwijderen. Dit past zich flexibel aan veranderende vraag aan, maar laat één proces het aantal paginafouten van een ander verhogen. Bij lokale paginavervanging komen te vervangen pagina's alleen uit de toewijzing van het proces dat de paginafout veroorzaakt. Dit beperkt onderlinge verstoring, maar kan een proces met te weinig toegewezen paginaframes niet helpen zonder de toewijzing te veranderen.

Kies oplossingen voor geheugendruk

Nuttige oplossingen verminderen de vraag of vergroten de capaciteit: voer minder programma's uit, voeg fysiek geheugen toe of verbeter de lokaliteit, bijvoorbeeld door arrays in opslagvolgorde te doorlopen. Snellere wisselruimte verlaagt de kosten van elke paginafout met opslagtoegang; ze laat een te grote actieve verzameling niet passen. Een schijf vervangen door een SSD kan de voortgang verbeteren zonder de oorzaak weg te nemen.

Bij extreme druk kan de OOM-killer van Linux een geselecteerd proces beëindigen wanneer geheugen vrijmaken en wisselen niet genoeg geheugen kunnen vrijmaken. De selectie gebruikt een score op basis van geheugengebruik en beleidsaanpassingen, niet simpelweg de identiteit van het grootste proces. Het geheugen kan worden vrijgemaakt wanneer het proces eindigt en het werk van het proces gaat verloren. Dit is het vrijmaken van bronnen als laatste redmiddel, anders dan een proces opschorten zodat het later kan worden hervat.