Virtual-Memory Management - Page Replacement
14 belangrijke vragen over Virtual-Memory Management - Page Replacement
Als de logische adresruimte groter is dan de fysieke adresruimte (over-allocating memory) dan kan een tekort aan frames in het geheugen optreden. Op welke drie manieren kan dit tekort opgevangen worden?
- Het proces dat het tekort veroorzaakt afbreken.
- Een ander proces uit het geheugen swappen.
- Page replacement: een pagina uit het geheugen swappen.
Wat is de functie van de modify-bit (dirty bit) bij page replacement?
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.
Noem vijf algoritmen voor page replacement.
- 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.
- Hogere cijfers + sneller leren
- Niets twee keer studeren
- 100% zeker alles onthouden
Welk verschijnsel wordt bedoeld met Belady's anomaly?
Belady's anomaly duidt op de situatie dat een toename van het aantal frames leidt tot een toename van het aantal page faults.
Noem twee manieren om LRU-page replacement te implementeren.
- 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.
Wat is het idee achter het gebruik van een free frame pool?
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.
In welke stappen verloopt page replacement?
- 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
Hoe kan een page replacement algoritme worden geëvalueerd?
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.
Noem een voordeel en een nadeel van optimal page replacement
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
Wat wordt bedoeld met een stack algoritme?
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.
LRU-approximation page replacement maakt gebruik van een of meer reference bits bij een pagina. Wat is de functie van de reference bit?
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.
Noem drie varianten van het LRU-approximation page replacement algoritme.
- 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.
Noem drie verschillende implementaties van een free frame pool.
- 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.
Voor sommige applicaties, zoals databases, is demand paging nadelig. Hoe wordt dit verklaard?
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.
De vragen op deze pagina komen uit de samenvatting van het volgende studiemateriaal:
- Een unieke studie- en oefentool
- Nooit meer iets twee keer studeren
- Haal de cijfers waar je op hoopt
- 100% zeker alles onthouden
![Trustpilot-logo](/images/design_2020/lp/clp-trustpilot-nl.png)