Virtual-Memory Management - Page Replacement

• Het proces dat het tekort veroorzaakt afbreken.
• Een ander proces uit het geheugen swappen.
• Page replacement: een pagina uit het geheugen swappen.

Door middel van de modify-bit wordt aangegeven of een pagina sinds deze in het geheugen is geplaatst gewijzigd is. Als de pagina niet gewijzigd is, kan deze uit het geheugen worden verwijderd zonder dat het nodig om de pagina terug te schrijven naar disk. Op deze manier kan page replacement versneld worden.

• FIFO page replacement: de pagina die het langst in het geheugen staat wordt vervangen.
• Optimal page replacement: de pagina die het langst niet gebruikt zal worden wordt vervangen.
• LRU (least-recently-used) page replacement: de pagina die het langst niet gebruikt is wordt vervangen.
• LRU-approximation page replacement: de te vervangen pagina wordt bepaald aan de hand van een of meer reference-bits, die voor elke pagina het patroon van referenties naar de pagina aangeven.
• Counting-based page replacement: de te vervangen pagina wordt bepaald aan de hand van het aantal referenties naar de pagina.

Belady's anomaly duidt op de situatie dat een toename van het aantal frames leidt tot een toename van het aantal page faults.

• Met behulp van counters. In de pagetable wordt bij elke pagina aangegeven op welk tijdstip of op welke kloktik de pagina voor het laatst is opgevraagd. Via de tijdstempels in de pagetable kan achterhaald worden welke pagina het langst niet gebruikt is.
• Met behulp van een stack. Elke keer dat een pagina wordt opgevraagd wordt deze bovenop de stack gezet. De onderste pagina van de stack is het langst niet gebruikt.

Eerst wordt de gewenste pagina in een vrij frame uit de free frame pool geplaatst en pas daarna wordt een ander frame vrijgemaakt. Op die manier hoeft het proces niet te wachten op het wegschrijven van de victim pagina.

• Zoek de locatie van de gewenste pagina op schijf
• Zoek een vrij frame. Indien geen vrij frame:
• Selecteer een victim frame
• Schrijf het victim frame naar disk
• Wijzig de page en frame tables
• Lees de gewenste pagina in het frame
• Wijzig de page en frame tables
• Herstart het user process

Een page replacement algoritme kan worden geëvalueerd met een reference string. Deze string bestaat uit een opeenvolging van paginanummers. De string wordt verkregen met behulp van een random number generator of door middel van waarneming in een bestaand systeem.

De score wordt uitgedrukt in het aantal page faults bij een gegeven aantal frames.

Voordeel:

• Laagste page fault rate
• Niet gevoelig voor Belady's anomaly

Nadeel:

• Lastig te implementeren omdat men niet weet wanneer welke pagina nodig zal zijn

Een stack algoritme is een algoritme waarvoor aangetoond kan worden dat de verzameling pagina's in n frames altijd een subset is van de verzameling pagina's in n+ 1 frames. Dit betekent dat het algoritme niet gevoelig is voor Belady's anomaly.

Voorbeelden van stack algoritmen zijn optimal page replacement en LRU page replacement.

Met de reference bit wordt aangegeven of de pagina is opgevraagd. Bij gebruik van meerdere reference bits per pagina kan aan de positie van de referentie bits worden gezien op welke momenten de pagina is opgevraagd.

• Additional reference bits algoritme: voor elke pagina wordt een serie reference bits bijgehouden die periodiek wordt bijgewerkt;
• Second chance algoritme: een variant van FIFO page replacement waarbij pagina's met een positieve reference bit worden overgeslagen.
• Enhanced second chance algoritme: een variant van het second chance algoritme waarbij onderscheid wordt gemaakt tussen gewijzigde en ongewijzigde pagina's.

• Basisimplementatie: eerst wordt de gewenste pagina in een frame uit de frame pool geplaatst en vervolgens wordt een victim frame leeggemaakt en aan de pool toegevoegd.
• Er wordt een lijst met gewijzigde pagina's bijgehouden. Bij gelegenheid worden deze pagina's naar disk geschreven.
• De frames in de free frame pool worden niet leeggemaakt, zodat de betreffende pagina's indien nodig snel opgevraagd kunnen worden.

Dergelijke applicaties verzorgen hun eigen memory management en doen dit efficiënter dan wanneer het besturingssysteem dit doet.

Om die reden kunnen deze applicaties beschikken over raw disk en file system services zoals demand paging omzeilen.