Virtueel geheugen

Start Omhoog Computersystemen Besturingssystemen Processen Threads Gelijktijdigheid: Wederzijdse uitsluiting Gelijktijdigheid: deadlock en utisterving Geheugenbeheer Virtueel geheugen Uniprocessor planning Multiprocessor en real-time planning Bestandsbeheer I/O beheer en schijfplanning Bash Powershell Begrippen

In hoofdstuk 7 zijn de concepten van paginering en segmentering geïntroduceerd en zijn hun tekortkomingen bestudeerd. We kunnen nu verder met de bespreking van het virtueel geheugen. Doordat het geheugenbeheer een complexe samenwerking is tussen processor hardware en besturingssysteemsoftware, is dit onderwerp moeilijk te onderzoeken. Eerst concentreren we ons op het hardware aspect van het virtueel geheugen, kijkend naar het gebruik van paginering, segmentatie en gecombineerde paginering en segmentatie. Daarna kijken we naar kwestie met betrekking tot het ontwerp van een virtuele geheugen faciliteit in besturingssystemen.

8.1. Hardware en controlestructuren

Vergelijk eenvoudige paginering en eenvoudige segmentatie aan de ene kant met vaste- dynamische partitionering aan de andere kant dan zien we de grondslag voor een fundamentele doorbraak op het gebied van geheugenbeheer. Twee eigenschappen van paginering en segmentatie liggen aan de basis voor deze doorbraak:

  1. Alle geheugenreferenties binnen een proces zijn logische adressen die op run-time dynamisch vertaald worden naar fysieke adressen. Dit betekend dat een proces gewisseld kan worden naar of van het hoofdgeheugen zodanig dat verschillende hoofdgeheugengebieden bezet kan worden op verschillende momenten gedurende de duur van uitvoering.
  2. Een proces kan opgedeeld worden in een aantal stukken (pagina's of segmenten). Het is niet nodig dat deze stukken moeten niet opeenvolgend in het hoofdgeheugen geplaatst worden tijdens uitvoering. De combinatie van dynamische run-time adresvertaling en het gebruik van een pagina- of segmenttabel laat dit toe.

Als de twee voorgaande kenmerken aanwezig zijn dan in niet nodig dat alle pagina's of alle segmenten van een proces in het hoofdgeheugen moeten zitten tijden uitvoering. Als het stuk (segment of pagina) dat de volgende op te halen instructie bevat en het stuk dat de volgende data locatie bevat in het hoofdgeheugen zit dan kan tenminste de uitvoering worden voortgezet.

Het deel van een proces dat eigenlijk op het moment in het hoofdgeheugen zit wordt de resident set van het proces genoemd.

  1. Meer processen kunnen in het hoofdgeheugen onderhouden worden. Omdat we alleen maar enkele stukken van eender welk proces gaan laden is meer plaats voor meer processen. Dit leidt tot efficiënter gebruik van de processor omdat het waarschijnlijker is dat één van de meer talrijke processen in de Ready toestand zullen staan op eender welk moment.
  2. Een proces kan groter zijn dan heel het hoofdgeheugen. Een van de meest fundamentele beperkingen van het programmeren is weggevallen. Zonder dit schema waarover we het hebben moet een programmeur zich bewust zijn hoeveel geheugen beschikbaar is. Als het geschreven programma te groot is, moet de programmeur manieren vinden om het programma op te delen in stukken die apart geladen kunnen worden in de vorm van een soort overlay strategie. Met virtueel geheugen dat gebaseerd is op paginering en segmentatie wordt deze taak overgelaten aan het besturingssysteem en hardware. In hoeverre het de programmeur aangaat, heeft hij of zij te maken met een gigantisch geheugen, de omvang van de grootte van de disk opslag. Het besturingssysteem zal automatisch de benodigde stukken van een proces in hoofdgeheugen laden.

Omdat een proces alleen kan worden uitgevoerd in het hoofdgeheugen wordt dit geheugen verwezen met real memory. Maar een programmeur of gebruiker neemt een potentieel veel groter geheugen waar - die welk is toegewezen op disk. Deze laatste wordt naar verwezen als virtual memory. Virtueel geheugen laat toe voor zeer effectieve multiprogrammering en ontlast de gebruiker van de onnodige strakke beperkingen van het hoofdgeheugen. Tabel 8.2 geeft een samenvatting van de kenmerken van paginering en segmentatie, met en zonder het gebruik van virtueel geheugen.

8.1.1. Lokaliteit en virtueel geheugen

De voordelen van virtueel geheugen zijn aantrekkelijk, maar is het schema praktisch? Op een gegeven moment was er veel discussie omtrent dit punt. Maar de ervaring met vele besturingssystemen heeft uitgewezen dat virtueel geheugen zonder meer werkt. Het op paginering, of paginering met segmentatie gebaseerd virtueel geheugen is een essentieel component in de hedendaagse besturingssystemen geworden.

Om deze belangrijke kwestie te begrijpen en waarom virtueel geheugen een veel besproken onderwerp was, moeten we opnieuw de taak van het besturingssysteem onderzoeken met betrekking tot virtueel geheugen.

Beschouw een groot proces dat bestaat uit een lang programma plus een aantal arrays van data. Na een korte periode kan de uitvoering beperkt blijven tot een klein gedeelte van het programma (bv. subroutine) en misschien enkel twee data-arrays benaderen. Als dit zo blijkt dan zie je de duidelijke verspilling om tientallen delen voor dat proces in te laden als je maar enkele nodig hebt voordat je programma opgeschort wordt en uitgewisseld wordt (swapped-out). We kunnen het geheugen beter benutten als we maar enkele stukken inladen. Als het programma dan aftakt naar een instructie of een referentie van een data-item dat zich niet in het hoofdgeheugen bevindt dan zal dat een fout veroorzaken. Dit zal het besturingssysteem laten weten om het benodigde stuk in te laden.

Dus op eender welk tijdstip zullen er maar enkele stukken van een proces zich in het hoofdgeheugen bevinden en daarom kunnen er meer processen onderhouden worden in het hoofdgeheugen. Voorts wordt er tijd bespaard omdat er geen onnodige stukken in en uit het geheugen gewisseld moeten worden. Het besturingssysteem moet echter intelligent zijn om dit schema te beheren. In de stabiele toestand zal praktisch al het hoofdgeheugen bezet zijn door processtukken, zodat de processor en het besturingssysteem directe toegang hebben tot ze veel mogelijke processen. Als het besturingssysteem een ander stuk wil inbrengen zal het eerst een stuk moeten uithalen. Als het een stuk uithaalt net voordat het gebruikt wordt, dan zal het onmiddellijk weer naar dat stuk moeten gaan om op te halen. Dit leidt tot een conditie dat gekend is als 'trashing': Het systeem besteed meer tijd aan het verwisselen (swapping) van stukken dan aan het uitvoeren van instructies. Het voorkomen van trashing was een belangrijk onderzoeksgebied in de jaren 70 en heeft geleid tot een verscheidenheid van complexe maar effectieve algoritmes. In wezen probeert het besturingssysteem te schatten, gebaseerd op de recente geschiedenis, welke stukken op korte termijn het meest waarschijnlijk nodig zullen zijn.

Mogelijke strategie

  • Enkel het minimaal benodigde van een proces in het geheugen inladen
  • Benodigde stukken die zich niet bevinden in het hoofdgeheugen verwisselen (swapped-in) naar het hoofddgeheugen
  • Niet gebruikte stukken uit het hoofdgeheugen verwisselen (swapped-out)
  • Principe van lokaliteit

  • Clustering van programma en data binnen een proces
  • Enkele delen van een proces zijn korte tijd benodigd
  • Intelligente schatting welke stukken vervolgens nodig zullen zijn zal 'trashing' voorkomen
  • Werkt enkel indien er ondersteuning is voor virtueel geheugen
  • Hardware moet segmentering en paginering ondersteunen
  • Besturingssysteem moet de verplaatsing van pagina’s en/of segmenten kunnen beheren tussen het primaire- en secundaire geheugen
  • 8.1.2. Paginering

    De term virtueel geheugen is normaal gesproken geassocieerd met systemen die gebruik maken van paginering alhoewel een op gesegmenteerd virtueel geheugen ook gebruikt wordt. Om virtueel geheugen te bereiken was het gebruik van paginering voor het eerst gezien in de Atlas computer en werd vlug daarna commercieel gebruikt.

    In de bespreking van eenvoudige paginering gaven we aan dat ieder proces zijn eigen geheugentabel heeft en wanneer alle pagina's in het hoofdgeheugen geladen zijn wordt de paginatabel voor dat proces aangemaakt en in het hoofdgeheugen ingeladen. Iedere paginatabelingang (PTE) bevat het framenummer van de overeenkomstige pagina in het hoofdgeheugen. Een paginatabel is ook nodig voor een op paginering gebaseerd virtueel geheugenschema. Het is alweer typisch om een unieke paginatabel te associëren met ieder proces. Echter worden de paginatabelingangen in dit geval veel complexer (figuur 8.2a). Omdat alleen enkele pagina's van een proces in het hoofdgeheugen kan zitten is er in iedere paginatabelingang een bit nodig om aan te geven of de overeenkomstige pagina in het hoofdgeheugen aanwezig (P) is. Als de bit aangeeft dat de pagina in het geheugen zit dan zal de ingang ook het framenummer van die pagina bevatten.

    De paginatabelingang bevat ook een modificatiebit (M) om aan te geven of de inhoud van de bijbehorende pagina veranderd is sinds de pagina de laatste keer in het hoofdgeheugen geladen was. Als er geen wijziging is dan is het niet nodig om de pagina weg te schrijven wanneer het tijd wordt om de pagina in dat frame te veranderen dat het momenteel bezet. Er kunnen nog andere controlebits aanwezig zijn. Bijvoorbeeld, als beveiliging of deling op paginaniveau worden beheerd dan zullen er voor dat doel ook bits nodig zijn.

    Elk proces heeft zijn eigen paginatabel en iedere ingang van een paginatabel bevat:

  • Het framenummer van de overeenkomstige pagina in het hoofdgeheugen
  • Een bit die aangeeft of de pagina al dan niet in het hoofdgeheugen zit (P)
  • Een bit die aangeeft of de pagina gewijzigd is sinds de laatste keer dat het in het hoofdgeheugen was geladen (M)
  • Indien geen wijziging is, moeten we de pagina niet wegschrijven naar de schijf bij uitswappen
  • Andere besturingsbits
  • 8.1.2.1. Paginatabelstructuur

    Het basis mechanisme om een woord van het geheugen te lezen gaat gepaard met de vertaling van een paginanummer en offset bevattend virtueel of logisch adres naar een frame nummer en offset bevattende paginatabel. Omdat de paginatabel een variabele lengte heeft, bepalend door de grootte van het proces, kunnen we niet verwachten dat dit in de registers kan zitten. In de plaats daarvan moet het in het hoofdgeheugen zitten als men het wil benaderen. Als een specifiek proces in uitvoering is dan bevat een register het start adres van de paginatabel van dat proces. Het paginanummer van het virtueel adres wordt gebruikt om de tabel te indexeren en het corresponderend frame nummer op te zoeken. Dit wordt gecombineerd met het offset gedeelte van het virtueel adres om het gewenste echt (real) adres te maken.

    In de meeste systemen is er maar één paginatabel per proces. Maar ieder proces kan gigantische hoeveelheden van virtueel geheugen bevatten.

    8.1.2.2. Geïnverteerde paginatabel

    De keerzijde van het gebruik van de paginatabellen die we reeds hebben besproken is dat hun grootte proportioneel is met dat van het virtueel geheugengebied.

    Een alternatieve aanpak met betrekking tot het gebruik van één- of meerdere niveaus paginatabellen is het gebruik van een geïnverteerde paginatabel structuur.

    Met deze aanpak wordt het paginanummer van een virtueel adres toegewezen naar een hash waarde gebruikmakend van een eenvoudige hashing functie. De hash waarde is een pointer naar de geïnverteerde paginatabel, welke de paginatabelingangen bevat. Er is één ingang in de geïnverteerde paginatabel voor ieder echte (real) geheugen paginaframe in plaats van één per virtuele pagina. Dus een vaste hoeveelheid van het echt geheugen is benodigd voor de tabellen ongeacht het aantal processen of virtuele pagina's ondersteund.

    8.1.2.3. Translation lookaside buffer

    In principe kan iedere virtuele referentie veroorzaken dat het fysieke geheugen tweemaal benaderd moet worden: een om de bijbehorende paginatabel op te halen en een om de gewenste data op te halen. Dus een stringent geheugenbeheerschema zou het effect kunnen hebben dat de geheugentoegangstijd verdubbeld. Om dit probleem aan te pakken, maken de meeste virtuele geheugenschema's voor paginatabellen gebruik van een speciale hoge snelheids cache, normaal een translation lookaside buffer (TLB) genaamd.

    Translation Lookaside Buffer (TLB)

  • High-speed cache
  • Enkel voor paginatabellen
  • Bevat meest recent gebruikt paginatabelingangen
  • Werkt op zelfde manier als de geheugencache
  • Werking

  • Processor ontvangt een virtueel geheugenadres
  • Processor kijkt in de TLB
  • Bevat de TLB een paginatabelingang?
  • Ja, teruggave van framenummer en echt adres wordt gevormd
  • Nee, paginanummer gebruiken om de paginatabel van het proces te overlopen
  • 8.1.2.4. Paginagrootte

    Een belangrijke beslissing van het hardware ontwerp is de gebruikte paginagrootte. Er zijn een aantal factoren waar rekening mee gehouden moet worden. Het is duidelijke dat hoe kleiner de paginagrootte is, hoe minder interne fragmentatie er is. Om het gebruik van het hoofdgeheugen te optimaliseren zouden we graag de interne fragmentatie verminderen. Aan de andere kant, hoe kleiner de pagina, hoe groter het aantal benodigde pagina's per proces. Meer pagina's betekent grotere paginatabellen. Voor grote programma's in een zware Multi-geprogrammeerde omgeving betekent het dat een gedeelte van de paginatabellen van actieve processen niet in het hoofdgeheugen kan zitten maar in het virtueel geheugen moet zitten. Hier kan voor een enkele geheugenreferentie een dubbele paginafout optreden: eerst om het benodigd deel van de paginatabel op te halen en ten tweede om de procespagina op te halen. Een andere factor dat meespeelt heeft te maken met de fysische eigenschappen van de meeste secundaire opslagapparaten welke een omwenteling hebben (bv. hard disk) heeft de voorkeur aan grotere paginagroottes voor een meer efficiënte blokverplaatsing van data.

  • Een kleinere paginagrootte betekent:

  • Minder interne fragmentatie

  • Meer pagina's per proces, wat zorgt voor grotere paginatabellen en meer ruimte ingenomen het in virtueel geheugen

    Een grotere paginagrootte betekent:

  • Efficiënter want secundair geheugen is ontworpen om grote blokken data te verplaatsen.

  • Meerdere pagina-groottes voorzien in de flexibiliteit die nodig is om TLB effectief te gebruiken.

  • Grote pagina’s voor programma-instructies
  • Kleine pagina’s voor threads
  • Echter de meeste besturingssystemen ondersteunen nog steeds maar één paginagrootte ongeacht de mogelijkheden van de onderliggende hardware. De reden hiervoor is dat de paginagrootte veel aspecten van het besturingssysteem beïnvloed. De verandering naar meerdere paginagroottes is een complexe taak.

    8.1.3. Segmentatie

    8.1.3.1. Virtuele geheugen implicaties

    Segmentatie staat de programmeur toe om het geheugen te bezien alsof het uit meerdere adresruimten of segmenten bestaat. Segmenten kunnen ongelijk en van dynamische grootte zijn. Geheugen referenties bestaan uit (segment nummer, offset) vorm van adres.

    De manier van organiseren heeft voor de programmeur een aantal voordelen boven dat van een gesegmenteerde adresruimte:

    1. Het vereenvoudigt het werken van groter wordende datastructuren. Als de programmeur niet vroeg genoeg weet hoe groot een specifieke datastructuur gaat worden, is het nodig om dit in te schatten tenzij dynamische segmentgroottes toegestaan zijn. Met gesegmenteerd virtueel geheugen kan de datastructuur toegewezen worden aan zijn eigen segment en het besturingssysteem zal het segment uitbreiden of inkrimpen naar gelang dit nodig is. Als een benodigd segment dat uitgebreid moet worden zich bevind in het hoofdgeheugen bevind, maar er te weinig plaats is, kan het besturingssysteem, als er genoeg plaats is, het segment naar een groter gebied in het hoofdgeheugen verplaatsen of dit in- of uitwisselen. In het laatste geval; zou het vergrootte segment terug gewisseld worden (swapped-in) bij de eerstvolgende mogelijkheid.
    2. Het laat programma’s toe om onafhankelijk gewijzigd of ge-hercompileerd te worden, zonder te vereisen dat de volledige set van programma's opnieuw gelinkt en geladen moet worden. Dit wordt bereikt door het gebruiken van meerdere segmenten.
    3. Het leent zich om gedeeld te worden tussen de processen. A programmeur kan een hulpprogramma of een handige tabel met data in een segment plaatsen waarnaar verwezen kan worden door andere processen.
    4. Het leent zich tot beveiliging. Omdat een segment samengesteld kan worden om een goed gedefinieerde set van programma's of data te bevatten, kan de programmeur of systeembeheerder op een gemakkelijke manier toegangsprivileges instellen.

    8.1.3.2. Organisatie

    In de bespreking van eenvoudige segmentatie gaven we aan dat ieder proces zijn eigen segmenttabel had en wanneer al die segmenten in het hoofgeheugen zijn geladen, het segmenttabel voor een proces wordt aangemaakt en geladen in het hoofdgeheugen. Iedere segmenttabelingang bevat het startadres van het corresponderend segment in het hoofdgeheugen, alsook de lengte van dat segment. Hetzelfde adres, een segment tabel, is benodigd als we een virtueel geheugenschema op segmentatie gebaseerd overwegen. Het is typisch om een unieke segmenttabel te associëren met ieder proces. In dit geval worden de segmenttabelingangen complexer (figuur 8.2). Omdat alleen enkele segmenten van een proces in het hoofdgeheugen zou kunnen zitten is een bit benodigd om aan te geven of dat segment in het hoofdgeheugen zit.

    Een andere besturing bit in de segmentatietabelingang is een modificatie bit dat aangeeft of de inhoud van het corresponderend segment gewijzigd zijn sinds het segment in het hoofdgeheugen was geladen. Als er geen wijziging is, is het ook niet nodig om dit segment weg te schrijven zodra het tijd is om het segment in het frame te vervangen dat het momenteel bezet. Andere besturing bits kunnen eveneens aanwezig zijn. Bijvoorbeeld, als beveiliging of deling op segment niveau beheerd worden dan zijn er bits voor dat doel nodig.

  • Corresponderend segment wordt aangemaakt en in het hoofdgeheugen geladen
  • Elke segementtabelingang bevat het startadres van het corresponderend segment in het hoofdgeheugen alsook de lengte van het segment
  • Een bit om aan te geven of segmenten van een proces in het hoofdgeheugen zitten
  • En bit die weergeeft of het segment gewijzigd is sinds het segment in het hoofdgeheugen geladen is
  • 8.1.4. Gecombineerde paginering en segmentatie

    Paginering

  • Transparant voor de programmeur
  • Elimineert externe fragmentatie
  • Voorziet in efficiënt gebruik van hoofdgeheugen
  • Segmentering

  • Zichtbaar voor de programmeur
  • Laat groter wordende datastructuren toe

  • In een gecombineerd paginering/segmentatie systeem, wordt de gebruikersadresruimte opgedeeld in aan aantal segmenten naar believen van de programmeur. Ieder segment is op zijn beurt opgedeeld in een aantal pagina's van vaste grootte, welke even groot in lengte zijn als dat van een hoofdgeheugenframe. Als een segment kleiner is dan dat van een pagina zal het segment enkel één pagina bezetten. Vanuit de kant van de programmeurs zal het segment offset gezien worden als een paginanummer en paginaoffset voor een pagina binnen het gespecificeerde segment.

    8.1.5. Beveiligen en delen

    Segmentatie leent zichzelf voor de implementatie van beveiligings- en deelbeleid. Omdat iedere segmenttabelingang een lengte alsook een basisadres bevat, kan een programma niet willekeuring toegang krijgen tot het hoofdgeheugen buiten de limieten van een segment. Om te kunnen delen is het voor een segment mogelijk om meerdere malen gerefereerd te worden in de segmenttabellen van andere processen. Deze mechanismen zijn uiteraard ook van toepassing op het pagineringssysteem. Hoewel in dat geval de paginastructuur van programma's en data niet zichtbaar is voor de programmeur, maakt het de specificatie van beveiliging en deling er niet makkelijker op.

    Meer gesofisticeerde mechanismen kunnen ook worden gebruikt. Een gebruikelijk schema is het gebruik van een ring-protectie structuur, van het type dat we kennen uit hoofdstuk 3 (figuur 3.18). Basis principes van het ring systeem zijn als volgt:

    1. Een programma mag alleen toegang tot data krijgen dat zich op dezelfde ring bevind of een minder geprivilegieerde ring.
    2. Een programma mag service oproepen maken op dezelfde of een meer geprivilegieerde ring.

    8.2. Besturingssysteem software

    Het ontwerp van het geheugenbeheer-gedeelte van een besturingssysteem hangt af van drie fundamentele zaken:

  • Het al dan niet gebruiken van virtuele geheugentechnieken
  • Het gebruik van paginering, segmentering of beide
  • De gebruikte algoritmes voor de verschillende aspecten van het geheugenbeheer
  • De keuzes die gemaakt worden in de eerste 2 punten steunen op de beschikbaarheid van het hardware platform. Dus, vroegere UNIX implementaties voorzagen niet in virtueel geheugen omdat de processoren op welk het systeem draaide geen paginering of segmentatie ondersteunde.

    Twee opmerkingen die je bij de eerste twee punten kan geven zijn: eerst, met uitzondering van besturingssystemen voor oudere computers zoals MS-DOS, en gespecialiseerde systemen, voorzien alle belangrijke besturingssystemen in virtueel geheugen. Ten tweede, pure segmentatie systemen worden alsmaar zeldzamer. Wanneer segmentering gecombineerd wordt met paginering, liggen de meeste kwesties van geheugenbeheer waarmee de ontwerper van een besturingssysteem mee geconfronteerd wordt op het gebied van paginering.

    De keuzes met betrekking tot het derde punt liggen in het gebied van besturingssysteem-software en zijn het onderwerp van deze sectie. Tabel 8.4 lijst de sleutelontwerp elementen op die we zullen onderzoeken.

    8.2.1. Fetch beleid

    Het fetch-beleid bepaalt wanneer een pagina in hoofdgeheugen geladen moet worden. De twee gangbare alternatieven zijn demand paging en prepaging.

    Paginering op aanvraag (= Demand paging)

  • Pagina wordt enkel in het hoofdgeheugen geladen indien er een referentie naar een locatie op die pagina gemaakt wordt.
  • Als de andere elementen van het geheugenbeheer in orde zijn gebeurt het volgende:
  • Als het proces voor eerst wordt gestart zal er een toeloop zijn van paginafouten. Zodra er meer en meer pagina's worden geladen zal het principe van lokaliteit voorstellen dat de meeste toekomstige referenties naar de meest recent geladen pagina's. Na een tijd zal het aantal paginafouten zakken tot een heel laag peil.
  • Prepaginering (= Prepaging)

  • Niet alleen de pagina waarvoor een paginafout was wordt geladen maar ook bijhorende pagina’s.
  • Karakteristieken van de meeste secundaire geheugenapparaten worden benut, zoals disks, welke zoektijden en omwentelingslatentie heeft.
  • Als pagina’s van een proces opeenvolgend in het secundair geheugen zijn opgeslagen is het efficiënter om een aantal opeenvolgende pagina’s in te laden dan ze één voor één over een langere periode in te laden.
  • Deze strategie is niet effectief als de meeste extra pagina’s die ingeladen werden niet naar verwezen werd.
  • De prepagineringsstrategie kan gebruikt worden als een proces voor de eerste maal opstart, in het geval dat de programmeur op de een of andere manier de gewenste pagina's zou willen aanwijzen of wanneer iedere keer een paginafout optreedt.
  • Prepaginering moet men niet verwarren met verwisselen (swapping). Als een proces uitgewisseld word uit het geheugen en in Suspended toestand wordt gezet, dan zullen al zijn residente pagina's uitgeplaatst worden. Als het proces verder wordt gezet, zullen alle pagina's dit voorheen in het hoofdgeheugen zaten weer terugkomen in het hoofdgeheugen.
  • 8.2.2. Plaatsingsbeleid

    Het plaatsingsbeleid bepaalt waar in het echt geheugen een stuk van een proces moet zitten.

    In een puur segmentatiesysteem is deze plaatsingsstrategie een belangrijke ontwerpkwestie; strategieën zoals best-fit, first-fit, enzovoorts welke behandeld waren in hoofdstuk 7 zijn mogelijke alternatieven. Echter voor een systeem dat enkel een puur pagineringssysteem of gecombineerd systeem gebruikt is plaatsing over het algemeen niet belangrijk omdat de adres translation hardware en de hoofdgeheugen toegangshardware hun functie kan uitvoeren van ieder combinatie van een pagina-frame met een gelijke efficiëntie.

    8.2.3. Vervangingsbeleid

    In de meeste besturingssysteemteksten is er een sectie 'vervangingsbeleid'. Deze handelt over de selectie van een pagina in het hoofgeheugen dat vervangen moet worden als een nieuwe pagina opgehaald moet worden. Dit onderwerp is moeilijk om uit te leggen omdat er een aantal zaken zijn betrokken die met elkaar in verband staan:

  • Hoeveel pagina frames moeten worden toegewezen aan ieder actief proces
  • Echter moet de set van pagina's gelimiteerd worden dat in aanmerking komt om vervangen te worden tot diegene van het proces die de paginafout heeft veroorzaakt of alle die de pagina-frames in het hoofdgeheugen bevatten
  • Tussen de overwogen pagina's, welke specifieke pagina moet geselecteerd worden om vervangen te worden
  • We zullen in de eerste twee concepten refereren naar resident set management welke in de volgende subsectie wordt behandeld en de term replacement policy bewaren het derde concept welk nog in deze subsectie behandeld zal worden.

    Alle beleidsvormen hebben tot doel dat een pagina dat verwijderd is, de minst waarschijnlijke pagina zal worden waar in de nabije toekomst naar zal verwezen worden. Door de het principe van lokaliteit is er vaak een hoge correlatie tussen recente geschiedenisreferentie en nabije toekomst referentiepatronen. Dus meeste beleidsvormen proberen het toekomstig gedrag te voorspellen op basis van het gedrag in het verleden.

    8.2.3.1. Venstervergrendeling

  • Niet alle vensters in het intern geheugen kunnen vervangen worden

  • Vensters waar het OS in draait

  • Vensters waar essentiële besturingsstructuren zijn in opgeslagen
    => Deze vensters zijn vergrendelt

  • Locking gebeurt door een bit in het venster

  • Zorgt voor beperking op het vervangingsbeleid

  • 8.2.3.2. Basis algoritmes

    Losstaand van de residentiële set beheerstrategie (besproken in de volgende subsectie) zijn er een aantal basis algoritmes die gebruikt worden voor de selectie om een pagina te vervangen:

  • Optimaal
    Vervangt de pagina waarvan de tijdsduur tot de volgende vervanging het langst is
    Praktisch onmogelijk te voorspellen
    Kan dienen als norm
  • LRU
    Vervangt de pagina waarnaar het langste niet is verwezen
    Benadert de optimale strategie
    Zorgt voor enorm veel overhead van het systeem
  • FIFO
    Vervangt de pagina’s volgens het principe First In, First out
    Circulaire buffer
    Verwijdert pagina’s om beurten (roundrobin)
  • Klok
    Gelijkaardig aan FIFO
    Werking
    Plaatst bij elke frame een use-bit
    Bij uitvoeren frame komt use-bit op 1
    Indien pagina niet in geheugen
    De pagina vervangen met use-bit 0
    De ander pagina’s in het intern geheugen hun use-bit op 0 zetten
    De nieuwe ingeladen pagina krijgt use-bit 1
  • 8.2.4. Beheer van de residentiële set

    8.2.4.1. Grootte van residentiële set

    Met gepagineerd virtueel geheugen is het niet nodig en kan het niet om alle pagina's van een in het hoofdgeheugen voor te bereiden voor uitvoering. Het besturingssysteem moet bepalen hoeveel pagina's er worden geladen, wat betekend, hoeveel hoofdgeheugen moet toegewezen worden aan een specifiek proces. Verschillende factoren die de keuze beïnvloeden:

  • Hoe minder geheugen we toekennen aan een proces, hoe meer processen er kunnen in het hoofdgeheugen aanwezig zijn. Zorgt voor verhoging zodat OS minstens een proces vindt dat klaar is om uitgevoerd te worden
  • Als we een heel klein aantal pagina’s per proces in het hoofdgeheugen laden zal het aantal paginafouten tot hoog zijn (ondanks het localiteitsprincipe)
  • Voorbij een zeker grootte zal de toekenning van meer hoofdgeheugen voor een proces geen zichtbaar effect meer hebben op het aantal paginafouten (omwille van het localiteitsprincipe)
  • Met deze factoren in gedachten zijn er in hedendaagse besturingssystemen ook nog twee soorten van beleid gevonden:

  • Een vast allocatie beleid (fixed-allocation) geeft een proces een vast aantal van frames in het hoofdgeheugen waarin wat uit te voeren. Het aantal is bepaald op het moment dat het geladen werd (process creation time) en kan bepaald worden op het type van proces (interactief, batch, type of applicatie) of kan bepaald worden volgens de richtlijnen van de programmeur of systeembeheerder. Wanneer met een vast allocatie beleid een paginafout voordoet in de uitvoer van een proces moet één van de pagina's van dat proces vervangen worden door de benodigde pagina.
  • Een variabel allocatie beleid (variable-allocation) staat toe dat het aantal tot een proces toegewezen pagina frames kan variëren over de levensloop van het proces. Een proces dat aanhoudend last heeft van een hoog aantal paginafouten, hierbij aantonend dat het principe van lokaliteit alleen standhoudt in een zwakke vorm voor dat proces, zal worden voorzien van extra frames om paginafout-ratio omlaag te brengen. Echter een proces met bijzonder lage paginafout-ratio, aantonend dat het proces bijzonder goed functioneert op het gebied van lokaliteit, zal een kleinere allocatie krijgen, met de bedoeling dat dit niet het paginafout-ratio niet opmerkelijk zal toenemen.
  • Het variabel allocatiebeleid zou blijken van een krachtiger beleid. Hoewel de moeilijkheid van deze aanpak is dat het besturingssysteem toegang moet krijgen tot het gedrag van de actieve processen. Onvermijdelijk hierbij is de software overhead in besturingssystemen en de afhankelijkheid van door het processorplatform geleverde hardware mechanismen.

    8.2.4.2. Bereik van vervanging

    Het bereik van een vervangingsbeleid kan ingedeeld worden als globaal of lokaal.

  • Lokaal beleid (local replacement policy)
    Kiest enkel uit de residentiële pagina’s van het proces dat de paginafout genereert
  • Globaal beleid (global replacement policy)
    Kiest uit alle niet gelockte pagina’s in het geheugen los van het feit welk proces eigenaar is van een bepaalde pagina
  • Beiden worden pas geactiveerd indien er zich een paginafout voordoet en er geen vrije frames meer over zijn
  • 8.3. Opruimbeleid

    Een opruimbeleid is het tegengestelde van een ophaalbeleid; het is betrokken bij het bepalen wanneer een aangepaste pagina weggeschreven moet worden naar het secundair geheugen. Twee algemene alternatieven zijn opruiming op aanvraag (demand cleaning) en opruiming vooraf (precleaning).

    Opruiming op aanvraag

    Pagina wordt enkel naar het secundaire geheugen weggeschreven indien ze geselecteerd is voor vervanging

  • Is gekoppeld en gaat vooraf aan het inlezen van een nieuwe pagina
  • + : Kan aantal schrijfoperaties voor pagina’s beperken
  • -: Soms 2 paginaverplaatsingen nodig om proces te deblokkeren
  • Vermindering processorgebruik
  • Opruiming vooraf

  • Schrijft gewijzigde pagina’s weg voordat hun paginavensters nodig zijn zodanig dat ze in batch kunnen weggeschreven worden
  • Pagina blijft na wegschrijven in het geheugen tot ze moet gewisseld worden
  • -: Nutteloos wegschrijven van pagina’s
  • 8.3.1. Laadbeheer

  • Bepaal het aantal residentiële processen in het hoofdgeheugen (= multiprogramminglevel)
  • Indien er te weinig processen zijn
  • Veel gevallen waarbij alle processen geblokkeerd zijn
  • Veel swapping
  • Indien er te veel processen zijn
  • De gemiddelde residentiële set van een proces zal te klein zijn
  • Veel meer paginafouten
    => Trashing
  • 8.3.1.1. Multiprogramming level

    Mogelijke manieren van aanpak

  • Enkel processen met een residentiële set die groot genoeg is mogen uitgevoerd worden
  • Het niveau van multiprogramming aanpassen zodanig dat
    Tijd tussen paginafouten = tijd nodig om een paginafout te verwerken
  • Klokpaginavervangingsalgoritme aanpassen, als de ratio lager is dan de treshold dan kan dat een indicatie zijn dat
    Er weinig paginafouten zijn dus weinig aanvragen om de pointer op te schuiven
  • Voor elk verzoek, is het gemiddeld aantal gescande frames door de pointer laag, wat duidt op veel residentiële pagina’s waarnaar niet verwezen wordt
    => In beide gevallen kunnen we het niveau van multiprogrammering veilig verhogen
  • 8.3.1.2. Procesopschorting

    Als het we niveau van multiprogrammering verlagen moet er een (of meerdere) residentiële processen gepauzeerd worden (= swapped out). Hieronder worden de zes mogelijkheden besproken:

  • Proces met laagste prioriteit
  • Falend proces
  • Laatst geactiveerde proces
  • Proces met de kleinste residentiële set
  • Grootste proces
  • Proces dat het de meeste tijd nog nodig heeft om uit te voeren
  • Herhalingsvragen

    1. Wat is het verschil tussen eenvoudige paginering en paginering met virtueel geheugen?

      Eenvoudige paginering: Alle pagina's van een proces moeten zich in het hoofdgeheugen bevinden om een proces uit te voeren, tenzij overlays worden gebruikt.
      Paginering met virtueel geheugen:
      Niet alle pagina's van een proces hoeven zich in hoofdgeheugenframes te bevinden om een proces uit te voeren. Pagina's kunnen indien nodig worden ingelezen.
       
    2. Licht het begrip thrashing toe.

      Thrashing is een fenomeen in virtuele geheugenschema's, waarin de processor de meeste tijd spendeert aan het swappen van stukken in plaatst van uit te voeren.
       
    3. Waarom is het beginsel van lokaliteit essentieel voor het gebruik van virtueel geheugen?

      Algoritmes kunnen worden ontworpen om het principe van lokalitieit te benutten om thrashing te voorkomen. In het algemeen laat het algoritme toe om te voorspellen welke residente pagina's waarnaar in de nabije toekomst het meest waarschijnlijk naar wordt gerefereerd en daardoor goede kandidaten zijn om uitgeswapt te worden.
       
    4. Welke elementen vindt men doorgaans in een ingang van een paginatabel? Beschrijf in het kort elk element.

      Framenummer: Het volgnummer dat een pagina in het hoofdgeheugen identificeert.
      Present bit: Geeft aan of deze pagina zich momenteel in het hoofdgeheugen bevindt.
      Modify bit: Geeft aan of deze pagina is gewijzigd sinds in de de pagina het laatst in het hoofdgeheugen werd geladen.

       
    5. Wat is het doel van de translation lookaside buffer?

      De TLB is een cache dat de paginatabelingangen (PTE's) bevat die het meest recent zijn gebruikt. Het doe is om te voorkomen dat de meeste tijd naar schijf moet worden gegaan om een paginatabelingang op te halen.
       
    6. Omschrijf in het kort de alternatieve ophaalstrategieën bij paginering.

      Bij vraagpaginering (demand paging) wordt een pagina uitsluitend overgebracht naar het hoofdgeheugen bij een verwijzing naar een locatie binnen die pagina.
      Bij prepaginering worden nog andere pagina's binnengehaald behalve door de door een paginafout opgevrraagde pagina's.
       
    7. Wat is het verschil tussen het beheer van de residente set en de vervangingsstrategie bij paginering?

      Beheer van residente set behandelt de volgende twee kwesties: (1) hoeveel paginaframes toegewezen worden aan ieder actief proces; en (2) of de reeks van pagina's die vervangen zouden kunnen worden beperkt moeten blijven aan diegene van het proces dat de paginafout hebben veroorzaakt of alle paginaframes in het hoofdgeheugen moeten omvatten.
      Vervanginstrategie bij paginering behandelt de volgende kwestie: tussen een aangemerkte reeks van pagina's, welke specifieke pagina moet worden geselcteerd om vervangen te worden.
       
    8. Wat is het verband tussen de FIFO- en de klokalgoritme voor paginavervanging?

      Het klokstrategie is gelijkaardig aan dat van FIFO, behalve dat in een klokstategie, elk frame met een gebruikte bit van 1 overgedragen wordt door het algoritme.
       
    9. Wat wordt nagestreefd bij paginabuffering?

      (1) Als een pagina uit de residente set wordt genomen en binnenkort nodig is, blijft het in het hoofdgeheugen, dit beperkt aan aantal leesopdrachten van disk. (2) Gemodificeerde pagina's kunnen worden weggeschreven in clusters plaats van één voor één, het aantal I/O-bewerkingen wordt daarmee significant verminderd en daarmee de hoeveelheid schijftoegangstijd.
       
    10. Waarom is het onmogelijk een globale vervangingsstrategie te combineren met een vaste-toewijzingsstrategie?

      Omdat een vast toewijzingsbeleid vereist dat het aantal frames dat aan een proces toegewezen wordt aan vast aantal is, wanneer nodig is om een nieuwe pagina op te halen voor een proces, moet een van de residente pagina's voor dat proces worden verwisseld worden (om het aantal frames op hetzelfde aantal te behouden), welk een lokaal vervangingsstrategie is.
       
    11. Wat is het verschil tussen een residente set en een werkset?

      De residente set van een proces is het huidige aantal pagina's van dat proces in het hoofdgeheugen.
      De werkset van een
      proces is het aantal pagina's van dat proces, waarna onlangs zijn verwezen.

       
    12. Wat is het verschil tussen vraagopschoning en opschoning vooraf?

      Bij vraagopschoning (demand cleaining) wordt een pagina alleen weggeschreven naar secundair geheugen wanneer deze is geselecteerd voor vervanging.
      Bij een strategie met opschoning vooraf (precleaning policy) worden gewijzigde pagina's weggeschreven voordat hun paginaframes nodig zijn; hierdoor kunnen pagina's in batches worden weggeschreven.

    Probleemvraagstukken

    1. Veronderstel dat de paginatabel voor het proces dat op dit moment wordt uitgevoerd door de processor, eruitziet als de volgende tabel. Alle getallen zijn decimaal, alles is genummerd beginnend bij 0 en alle adressen zijn byteadressen. De paginagrootte is 1024 bytes.
       
      Nummer virtuele pagina valid-bit reference-bit modify-bit Nummer paginaframe
      0 1 1 0 4
      1 1 1 1 7
      2 0 0 0
      3 1 0 0 2
      4 0 0 0
      5 1 0 1 0

      1. Beschrijf precies hoe een door de processor gegenereerd, virtueel adres in het algemeen wordt omgezet naar een fysiek geheugenadres.
         
      2. Met welke fysieke adressen zouden de volgende virtuele adressen eventueel overeenkomen? (Probeer geen paginafouten af te handelen, als die zich al voordoen.)
        1. 1052
        2. 2221
        3. 5499
         
    2. Veronderstel een gepagineerd virtueel geheugensysteem met 32-bit virtuele adressen en pagina’s met een omvang van 1 kB. Voor elke paginatabelingang zijn 32 bits nodig. De wens is om de omvang van de paginatabel te beperken tot een pagina.
      1. Hoeveel paginatabelniveaus zijn nodig?
         
      2. Wat is de omvang van de paginatabel op elk niveau? Tip: Een omvang van een paginatabel is kleiner.
         
      3. De kleinere paginaomvang kan zowel boven in als onder in de hiërarchie van de paginatabel gebruikt worden. Welke strategie beslaat het kleinste aantal pagina’s?
         
      1. Hoeveel geheugenruimte is er nodig voor de gebruikerspaginatabel uit figuur 8.4?
         
      2. Veronderstel dat je een gehashte geïnverteerde paginatabel voor dezelfde adresseringsmethode wil implementeren zoals die is weergegeven in figuur 8.4, met een hashfunctie die het 20-bit paginanummer koppelt aan een hashwaarde van 6 bit. De tabelingang bevat het paginanummer, het framenummer en een kettingpointer. Als de paginatabel ruimte toewijst voor maximaal 3 overfiowingangen per gehashte ingang, hoeveel geheugenruimte neemt de gehashte geïnverteerde paginatabel dan in beslag?
         
    3. Aan een proces zijn vier paginaframes toegewezen. (Alle volgende getallen zijn decimaal en alles wordt beginnend bij nul genummerd.) De volgende tabel toont de tijd waarop een pagina voor het laatst in elk paginaframe werd geladen, de tijd van de laatste toegang tot de pagina in elk paginaframe, het nummer van de virtuele pagina in elk paginaframe en de reference- (R) en modify-bit (M) voor elk paginaframe. (De tijden zijn kloktikken vanaf de start van het proces op tijdstip 0 tot de gebeurtenis; niet het aantal tikken vanaf de gebeurtenis tot nu.)
       
      Nummer virtuele pagina Paginaframe Tijdstip laden Tijdstip verwijzing R-bit M-bit
      2 0 60 161 0 1
      1 1 130 160 1 0
      0 2 26 162 1 0
      3 3 20 163 1 1

      Er is een paginafout voor virtuele pagina 4 opgetreden. Van welk paginaframe wordt de inhoud vervangen bij elk van de volgende strategieën voor geheugenbeheer? Leg steeds uit waarom.

      1. FIFO (first in, first Out).
      2. LRU (least recently used).
      3. Klok.
      4. Optimaal (Gebruik de hierna volgende reeks met verwijzingen.)
      5. Veronderstel dat met de hiervoor genoemde toestand van het geheugen vlak voor de paginafout, de volgende reeks met verwijzingen naar virtuele pagina’s wordt gebruikt.

                  4, 0, 0, 0, 2, 4, 2, 1, 0, 3, 2

      Hoeveel paginafouten treden op als de werksetstrategie wordt gebruikt met een venster van 4 in plaats van een vaste toewijzing? Geef duidelijk aan wanneer elke paginafout optreedt.
       

    4. Een proces verwijst naar vijf pagina’s (A, B, C, D en E) in de volgende volgorde:

                  A; B; C; D; A; B; E; A; B; C; D; E

      Veronderstel dat de vervangingsalgoritme first in, first out is. Bepaal het aantal paginaoverdrachten tijdens deze reeks verwijzingen, beginnend met een leeg hoofdgeheugen met drie paginaframes. Herhaal dit voor vier paginaframes.
       
    5. Een proces bevat acht virtuele pagina’s op schijf en krijgt vier paginaframes in het hoofdgeheugen vast toegewezen. Het paginaspoor ziet er als volgt uit:

                  1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3, 3, 2, 3
       
      1. Laat de opeenvolgende pagina’s zien die zich in de vier paginaframes bevinden bij gebruik van de LRU-algoritme als vervangingsstrategie. Bereken de hit-ratio in het hoofdgeheugen. Ga ervan uit dat de frames in het begin leeg zijn.
         
      2. Herhaal de vorige vraag met FIFO als algoritme bij de vervangingsstrategie.
         
      3. Vergelijk de twee hit-ratio’s en geef commentaar op de effectiviteit van FIFO ah benadering van LRU in dit speciale geval van paginaspoor.
         
    6. Bij de VAX bevinden paginatabellen van gebruikers zich op virtuele adressen in de systeemruimte. Wat is het voordeel van het opslaan van deze paginatabellen in het
      virtuele geheugen in plaats van het hoofdgeheugen? En wat is het nadeel?
       
    7. Veronderstel dat de opdracht

                  for(i= 1; i<=n; i++)
                              a[i] = b[i] + c[i];

      wordt uitgevoerd in een geheugen met een paginagrootte van 1000 woorden. Er geldt dat n = 1000. Schrijf een hypothetisch programma voor het implementeren van deze opdracht voor een machine die een complete verzameling register-naar-registerinstructies heeft en indexregisters gebruikt. Beschrijf daarna de reeks paginaverwijzingen tijdens uitvoering.
       
    8. De architectuur van de IBM System/370 gebruikt een geheugenstructuur met twee niveaus die segmenten en pagina’s worden genoemd, hoewel de segmentaanpak veel kenmerken mist die in dit hoofdstuk zijn besproken. In de basisarchitectuur van de 370 kan de paginagrootte 2 of 4 kilobytes zijn en is de vaste segmentgrootte 64 kilo- bytes of 1 megabyte. Bij de architecturen 370/XA en 370/ESA is de paginagrootte 4 kilobytes en de segmentgrootte 1 megabyte. Welke voordelen van segmentatie ontbreken in dit systeem? Welk voordeel kan segmentatie de 370 bieden?
       
    9. Als een pagina 4 kilobytes groot is en een paginatabelingang 4 bytes kost, hoeveel niveaus van paginatabellen zijn dan nodig om een 64-bits adresruimte te vertalen als de paginatabel op het hoogste niveau in één pagina past?
       
    10. Ga uit van een systeem dat de adresvertaling per pagina uitvoert en een paginatabel
      met één niveau gebruikt. Ga ervan uit dat de benodigde paginatabel zich altijd in het geheugen bevindt.
      1. Als een geheugenverwijzing 200 ns kost, hoe lang duurt dan een verwijzing naar het gepagineerde geheugen?
         
      2. We voegen nu een MMU toe die een overhead van 20 ns veroorzaakt bij een hit
        of een miss. Als we ervan uitgaan dat 85% van alle geheugenverwijzingen hits zijn in de TLB van de MMU, wat is dan de effectieve geheugentoegangstijd (EMAT)?
         
      3. Leg uit wat de invloed van de hit-ratio van de TLB op de effectieve geheugentoegangstijd is.
         
    11. Ga uit van een reeks van paginaverwijzingen voor een proces met een werkset van M frames die in eerste instantie leeg zijn. De reeks van paginaverwijzingen heeft een lengte P met daarin N afzonderlijke paginanummers. Bepaal het volgende voor iedere vervangingsalgoritme:
      a. Wat is de ondergrens van het aantal paginafouten?

      b. Wat is de bovengrens van het aantal paginafouten?
       
    12. Bij de bespreking van een algoritme voor paginavervanging maakt iemand de volgende analogie. Een sneeuwschuiver maakt steeds hetzelfde rondje. Het blijft regelmatig sneeuwen en de eenzame sneeuwschuiver blijft maar rondjes draaien met een constante snelheid. De weggeschoven sneeuw verdwijnt achter de horizon.
      1. Voor welke algoritme bij paginavervanging, zoals is besproken in paragraaf 8.2.3, is dit een bruikbare analogie?
         
      2. Wat suggereert deze analogie over het gedrag van de betreffende algoritme bij paginavervanging?
         
    13. In de architectuur van de S/370 is een opslagsleutel (storage key) een besturingsveld dat is verbonden met elk (reëel) geheugenframe ter grootte van een pagina. Twee bits van die sleutel die van belang zijn voor de paginavervanging, zijn de reference-bit en de change-bit. De reference-bit wordt ingesteld op 1 bij de toegang tot een adres binnen het frame voor lezen of schrijven en op 0 wanneer een nieuwe pagina in het frame wordt geladen. De change-bit wordt ingesteld op 1 wanneer een schrijfbewerking wordt uitgevoerd met een locatie binnen het frame. Stel een benadering voor waarmee kan worden vastgesteld welke paginaframes het minst recent gebruikt zijn en maak daarbij uitsluitend gebruik van de reference-bit.
       
    14. Veronderstel de volgende reeks paginaverwijzingen (elk element in de reeks stelt een paginanummer voor):

                  1 2 3 4 5 2 1 3 3 2 3 4 5 4 5 1 1 3 2 5

      Definieer de gemiddelde omvang van de werkset na de kde verwijzing

      als



      en de kans op een ontbrekende pagina na de kde verwijzing

      als



      waarin F(t, ∆.) = 1 als in virtuele tijd t een paginafout ontstaat en een anders 0.
      1. Teken een diagram dat vergelijkbaar is met het diagram in figuur 8.19 voor de zojuist gedefinieerde verwijzingsreeks voor de waarden ∆.= 1, 2, 3, 4, 5 en 6.
         
      2. Teken S20() als functie van ∆.
         
      3. Teken W20() als functie van ∆.
         
    15. Een sleutel tot prestatie van de VSWS-strategie bij het beheer van de residente set, is de waarde van Q. De ervaring leert dat, bij een vaste waarde van Q voor een proces, er aanzienlijk verschil optreedt in de paginafoutfrequentie tijdens verschillende fasen van verwerking. Wordt één waarde van Q gebruikt voor verschillende processen, dan lopen bovendien de diverse frequenties van paginafouten sterk uiteen. Deze verschillen zijn een sterke aanwijzing dat een mechanisme dat de waarde van Q gedurende het bestaan van een proces dynamisch aanpast, het gedrag van de algoritme kan verbeteren. Beschrjf een eenvoudig mechanisme dat hiervoor kan worden gebruikt.
       
    16. Veronderstel dat een taak wordt verdeeld in vier even grote segmenten en dat het systeem voor elk segment een paginabeschrijvingstabel bouwt met acht ingangen. Het systeem gebruikt dus een combinatie van segmenteren en pagineren. Veronderstel bovendien dat de paginagrootte 2 kilobytes is.
      1. Wat is de maximumgrootte van elk segment?
         
      2. Wat is de maximale logische adresruimte voor de taak?
         
      3. Veronderstel dat deze taak toegang heeft tot een element op fysieke locatie 0x00021ABC. Wat is de indeling van het logische adres dat de taak hiervoor genereert? Wat is de maximale fysieke adresruimte voor het systeem?
         
    17. Ga uit van een gepagineerde, logische adresruimte (die bestaat uit 32 pagina’s vat ieder 2 kilobytes) die wordt vertaald naar een fysieke geheugenruimte van 1 megabyte.
      1. Wat is de indeling van het logische adres voor de processor?
         
      2. Wat is de lengte en breedte van de paginatabel (als we bits voor ‘toegangsrechter even vergeten)?
         
      3. Welke gevolgen heeft het halveren van de fysieke geheugenruimte voor de paginatabel?
         
    18. De kernel van UNIX kan dynamisch een processtack vergroten in virtueel geheuger maar zal nooit trachten deze kleiner te maken. Beschouw het geval waarbij een programma een C-subroutine aanroept die een lokaal array met een omvang van 10 kilobytes toevoegt aan de stack. De kernel zal de stack vergroten om ruimte te geven. Bij terugkeer uit de subroutine wordt de stackwijzer aangepast. Deze ruimte zou nu vrijgegeven kunnen worden door de kernel, maar dit gebeurt niet. Licht toe waarom het mogelijk is om op dit moment de stack te verkleinen en waarom de kernel van UNIX dit nalaat.