Geheugenbeheer

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 een enkelvoudig programmeerbaar systeem is het hoofdgeheugen verdeeld over twee gedeelten: één deel voor het besturingssysteem (residente monitor, kernel) en het andere deel voor het huidig uitvoerend programma. In een meervoudig programmeerbaar systeem, moet het gebruikersgedeelte verder opgedeeld worden om plaats te bieden aan meerdere processen. De onderverdeeltaak wordt dynamisch door het besturingssysteem uitgevoerd en is gekend als het geheugenbeheer.

Effectief geheugenbeheer is essentieel is meervoudig programmeerbare systemen. Als er enkele een paar processen in het geheugen zitten, dan zullen de processen de meeste tijd wachten op een I/O en zal de processor inactief zijn. Dus geheugen moet toegewezen zijn om verzekerd te zijn dat er een voldoende aantal Ready processen klaarstaan om de beschikbare processortijd te vullen.

7.1. Geheugenbeheer vereisten

7.1.1. Relocatie

In een multiprogrammeringssysteem geld het volgende:

  • Het beschikbare hoofdgeheugen is gedeeld over het aantal processen.
  • De programmeur weet niet op voorhand welke andere programma’s resident in geheugen zitten op het moment van uitvoering van het programma.
  • Het wisselen van actieve processen om de processor maximaal te benutten door het aanleggen van een grote pool van Ready processen die klaar zijn om uitgevoerd te worden.
  • Eenmaal dat een programma uitgewisseld is naar disk zou het zeer beperkend zijn dat wanneer het terug uitgewisseld moet worden naar geheugen dat het in het zelfde geheugengebied moet worden geplaatst. Als alternatief kan het nodig zijn om het proces naar een ander geheugengebied te verplaatsen (reallocation).

    We kunnen dus van te voren niet weten waar een programma geplaatst is in het hoofdgeheugen we moeten de mogelijkheid laten dat een programma in het hoofdgeheugen verplaatst kan worden door het uitwisselen (swapping).

    7.1.2. Beveiliging

    Elk proces moet worden beschermt tegen invloed van andere processen.

  • Het zou niet mogelijk mogen zijn dat programma's, om te lezen of te schrijven, in andere processen refereren naar geheugenlocaties in een proces.
  • In één opzicht betekent het verhogen van de reallocatievereisten dat de moeilijkheid van de vereisten voor beveiliging ook hoger worden.
  • Merk op dat het geheugen beveiligingsvereiste voldaan moet worden door de processor (hardware) in plaatst van het besturingssysteem (software).
  • 7.1.3. Delen

    Eender welk beveiligingsmechanisme moet de flexibiliteit hebben om toe te staan dat verscheidene processen hetzelfde deel van het hoofdgeheugen te benaderen.

  • Als een aantal processen hetzelfde programma uitvoeren is het beter dat ieder proces toegestaan wordt om toegang te geven aan dezelfde kopie van het programma dan om een eigen aparte kopie te hebben.
  • Het geheugenbeheersysteem moet daarom toestaan gecontroleerde toegang te bieden aan gebieden van het geheugen zonder dat de essentiële beveiliging gecompromitteerd wordt.
  • 7.1.4. Logische indeling

    Bijna altijd is het hoofdgeheugen in een computersysteem georganiseerd als een lineaire of één-dimensionale lijst van adresruimte, bestaande uit een sequentie van bytes of woorden. Secundair geheugen is op fysiek niveau gelijkaardig gestructureerd. Terwijl deze manier van structureren de actuele machine hardware het dichtst benadert, komt deze niet overeen met de manier waarop programma's zijn geconstrueerd. De meeste programma's zijn gestructureerd in modules, waarvan sommigen niet aan te passen zijn (alleen leesrechten, alleen uitvoerrechten) en sommigen bevatten data die aangepast mogen worden. Als het besturingssysteem en de computer hardware effectief kunnen omgaan met gebruikersprogramma's en data in een of andere vorm van modules dan kan een aantal voordelen worden gerealiseerd.

  • Modules kunnen onafhankelijk worden geschreven en gecompileerd, waarbij alle verwijzingen van de ene naar de andere module tijdens de uitvoering door het systeem worden opgelost.
  • Ten koste van een bescheiden extra overhead kunnen verschillende modules andere beschermingsniveaus krijgen (bijvoorbeeld alleen lezen of alleen uitvoeren).
  • Het wordt mogelijk mechanismen te gebruiken waarmee processen modules kunnen delen. Het voordeel van de mogelijkheid te delen op het niveau van de module is dat dit aansluit bij hoe een gebruiker aankijkt tegen het probleem. De gebruiker kan daarom gemakkelijk de gewenste deling opgeven.
  • Als hulpmiddel voor deze vereisten is segmentatie meest geschikt welke een van de onderzochte geheugenbeheertechnieken van de hoofdstuk is.

    1.1.5. Fysieke indeling

    Zoals we in sectie 1.5 hebben besproken is computergeheugen op zijn minst ingedeeld op twee niveaus, waarnaar verwezen wordt als hoofdgeheugen en secundair geheugen.

    Primair geheugen

  • Snelle toegang met een betrekkelijke hoge kostprijs
  • Vluchtig welke betekent dat het niet voorziet in permanente opslag
  • Bevat de data en programma die op dat moment in gebruik zijn
  • Secundair geheugen

  • Trager en goedkoper dan hoofdgeheugen
  • Is meestal niet vluchtig
  • Kan worden gebruikt voor lange termijn opslag van programma's en data
  • In dit twee niveau schema is het organiseren van de informatiestroom tussen hoofd- en secundair geheugen een belangrijk systeemgedeelte. De verantwoordelijkheid van deze stroom kan toegewezen worden aan de individuele programmeur, echter is dit in niet praktisch en niet gewenst voor de volgende twee redenen:

  • Het beschikbaar hoofdgeheugen voor een programma en zijn data kan niet toereiken zijn. In dat geval moet de programmeur zich bezig houden met het gebruik van overlaying, waarin het programma en data zo gestructureerd zijn dat verschillende modules toegewezen kunnen worden aan dezelfde regio van het geheugen met een hoofdprogramma-verantwoordelijkheid voor het uitwisselen van de benodigde modules. Zelf met behulp van compiler-hulpprogramma’s is overlay programmering een verspilling van programmeertijd.
  • In een multiprogrammering omgeving zal de programmeur bij het coderen niet weten hoeveel ruimte er beschikbaar zal zijn of waar deze ruimte zal zijn.
  • Het is dan duidelijk dat de taak van het verplaatsen van informatie tussen twee geheugenniveaus een systeemverantwoordelijkheid moet zijn. In wezen is deze taak geheugenbeheer.
  • 7.2. Geheugenpartitionering

    Het hoofddoel van geheugenbeheer is om processen in hoofdgeheugen te plaatsen voor uitvoering door de processor. In bijna alle moderne multiprogrammeringssystemen gaat dit gepaard met een vernuftig schema gekend als virtueel geheugen. Virtueel geheugen is op zijn beurt gebaseerd op het gebruik van twee technieken: segmentatie en paginering. Voordat we naar de deze virtuele geheugentechnieken kunnen kijken moeten we de basis leggen door eerst te kijken naar eenvoudigere technieken waar geen virtueel geheugen mee gemoeid is. (Tabel 7.2 somt alle technieken op die in dit en volgend hoofdstuk worden besproken). Een van deze technieken, partitionering, zijn op verschillende manieren gebruikt op enkele nu ondertussen verouderde besturingssystemen. De andere twee technieken, eenvoudige paginering en eenvoudige segmentatie worden niet door zichzelf gebruikt. Hoe dan ook zal dit duidelijker worden als we naar deze technieken bestuderen zonder te kijken naar het virtueel geheugen.

    7.2.1. Vaste partitionering

    In de meeste geheugenbeheerschema's kunnen we aannemen dat een besturingssysteem een vaste hoeveelheid hoofdgeheugen bezet en dat de rest van het hoofdgeheugen beschikbaar is voor meerdere processen. Het eenvoudigste schema om dit beschikbaar geheugen te beheren is om dit in te delen in regio's met vaste begrenzingen.

    7.2.1.1. Partitiegroottes

    Figuur 7.2 laat twee voorbeelden zien voor vaste partitionering. Een mogelijkheid is het gebruik van partities met gelijke grootte. In dit geval kan ieder proces van welke de grootte is kleiner of gelijk aan de partitiegrootte geladen worden in eender welk beschikbare partitie. Als alle partities vol zijn en geen proces in de Ready of Running toestand bevind, kan het besturingssysteem een proces uitwisselen (swap-out) uit een of andere partitie en inladen in een ander proces, zodat er werk is voor de processor.

    Er zijn twee moeilijkheden met het gebruik van vaste gelijke-grootte partities:

  • Een programma kan te groot zijn om te passen in een partitie. In dit geval moet de programmeur het programma zo ontwerpen dat het gebruik maakt van overlays zodat enkel maar een gedeelte van het programma in het hoofdgeheugen moet zitten. Als een niet aanwezige module nodig is, moet het gebruikersprogramma deze module inladen in de partitie van het programma, door de aanwezige programma's of data te overschrijven.
  • Hoofdgeheugengebruik is extreem inefficiënt. Welk programma, hoe klein ook, bezet een hele partitie. In ons voorbeeld kan ons programma welk kleiner is dan 2MByte toch een partitie bezetten van 8MByte wanneer deze uitgewisseld (swapped-in) wordt. Dit wordt ook wel interne fragmentatie genoemd.
  • Beide problemen kunnen deels verbeteren door gebruik te maken van partities met verschillende groottes (figuur 7.2b). In dit voorbeeld kunnen programma's met een grootte van 16MByte gehuisvest worden zonder het gebruik van overlays. Partities kleiner dan 8MByte laten toe dat programma's gehuisvest worden met minder interne fragmentatie.

    7.2.1.2. Plaatsingsalgoritme

    Met partities van gelijke grootte is het onbelangrijk waar je de processen plaatst in het geheugen. Zo lang er een beschikbare partitie is kan een proces in die partitie worden geladen. Omdat alle partities van gelijke grootte zijn maakt het niet uit welke partitie wordt gebruikt. Als alle processen bezet zijn met processen die niet klaar zijn om uitgevoerd te worden dan moet een van die processen uitgewisseld (swapped-out) worden om plaats te maken voor een nieuw proces. Welke om uit te wisselen (swap-out) is een beslissing van de planning.

    Met partities van ongelijke grootte zijn er twee mogelijke manieren om processen aan partities toe te wijzen. De eenvoudigste manier is om ieder proces aan de kleinste partitie toe te wijzen waarin het past. In dit geval moet voor iedere bestemd partitie een planningswachtrij aangemaakt worden om de processen te bevatten die uitgewisseld (swapped-out) moeten worden (figuur 7.3a). Het voordeel hiervan is dat processen altijd dusdanig toegewezen zijn om verspild geheugen binnen een partitie te verminderen (interne fragmentatie).

    Alhoewel deze techniek optimaal lijkt in het oogpunt van een individuele partitie is dit niet optimaal voor het systeem in zijn geheel. Beschouw in figuur 7.2b bijvoorbeeld een zaak waarin er op een bepaald moment geen processen zijn met een grootte tussen 12 en 16M. In dat geval zal de 16M partitie ongebruikt blijven, zelfs als een kleiner proces eraan toegewezen zou kunnen worden. Dus een aanbevelende aanpak zou het gebruik zijn om alle processen door één enkel wachtrij te laten behandelen (figuur 7.3b). Zodra het tijd is om een proces in te laden in het hoofdgeheugen, zal de kleinst beschikbare partitie geselecteerd worden die het proces kan bevatten. Als alle partities bezet zijn dan zal een beslissing tot uitwisseling (swapping) gemaakt moeten worden. De voorkeur gaat uit om de kleinst mogelijke partitie uit te wisselen (swapping-out) die het inkomende proces kan bevatten. Het is ook mogelijk om andere factoren te overwegen zoals prioriteit en een voorkeur om geblokkeerde versus klaarstaande processen uit te wisselen (swapping-out).

    Het gebruik van ongelijke partities voorziet in een bepaalde mate de flexibiliteit van vaste partitionering. Toegevoegd kan er gezegd worden dat vaste partitieschema's relatief eenvoudig zijn en minimale besturingssysteemsoftware en verwerkingsoverhead vereist. Hoe dan ook zijn er ook nadelen:

  • Het aantal partities bepaald op systeem generatie tijd limiteert het aantal actieve (niet opgeschorte) processen in het systeem.
  • Omdat partitiegroottes vooraf zijn ingesteld op systeem generatie tijd, zullen kleine jobs de partitieruimte niet optimaal benutten. In een omgeving waar de hoofdgeheugenvereisten voor alles jobs op voorhand zijn gekend kan dit redelijk zijn, maar in de meeste gevallen is dit een inefficiënte techniek.
  • Het gebruik van vaste partitionering is tegenwoordig haast niet meer gekend. Een voorbeeld van een succesvol besturingssysteem die deze techniek gebruikte was een vroege IBM mainframe besturingssysteem, Os/MFT (Multiprogramming with a Fixed Number of Tasks).

    7.2.2. Dynamische partitionering

    Om problemen van vaste partitionering te vermijden is een aanpak gekend als dynamische partionering ontwikkeld. Deze aanpak is vervangen door de meer gesofisticeerde geheugenbeheertechnieken.

    Met dynamische partitionering zijn de partities van variabele grootte en aantal. Als een proces ingeladen word in het hoofdgeheugen, is het toegewezen met precies hetzelfde benodigd geheugen en niets meer. In een voorbeeld met gebruikmaking van 64 MBytes aan hoofdgeheugen wordt getoond in figuur 7.4. Initieel is het geheugen leeg, behalve voor het besturingssysteem (a). De eerste drie processen zijn geladen, en starten waar het besturingssysteem eindigt en bezet neemt precies genoeg plaats in voor ieder proces (b, c, d). Dit laat een gat over op eind van het geheugen dat te klein is voor een vierde proces. Op een gegeven moment zijn geen van de processen in het geheugen klaar. Het besturingssysteem wisselt proces 2 (e) uit (swaps-out), welk genoeg ruimte overlaat om een nieuw proces (f) te laden. Omdat proces 4 kleiner is dan proces 2 is een ander gat ontstaan. Nadien wordt een punt bereikt waarop geen van de processen klaar zijn, maar proces 2 die zich in de Ready/Suspend toestand bevind is beschikbaar. Omdat er te weinig ruimte in het geheugen is voor proces 2 zal het besturingssysteem proces 1 (g) uitwisselen (swap-out) en proces 2 (h) terug in-verwisselen (swap-in).

    Zoals dit voorbeeld laat zien, begint deze methode goed, maar na een tijd komt er een situatie dat er veel gaten ontstaan in het systeem. Na verloop van tijd zal het geheugen meer en meer gefragmenteerd raken en zal het geheugengebruik achteruitgaan. Dit fenomeen wordt ook wel externe fragmentatie genoemd, dat aangeeft dat het geheugen dat extern is naar alle partities in toenemende mate gefragmenteerd raakt. Dit staat in contrast tot de eerder vermelde interne fragmentatie.

    Een techniek om de externe fragmentatie aan te pakken is het gebruik van compressie: van tijd tot tijd zal het besturingssysteem de processen verschuiven zodat ze weer aaneensluitend zijn en op een manier dat al het vrij geheugen samen in één blok zit. Bijvoorbeeld, in figuur 7.4h, compressie zal resulteren in een vrij geheugenblok met een grootte van 16M. Dit kan groot genoeg zijn om andere processen te laden. De moeilijkheid met compressie is dat het een tijdrovende procedure is en een verspilling van processortijd. Merk op dat compressie de noodzaak van dynamische her-verplaatsing (relocatie) met zich meebrengt. Dat wil zeggen dat het mogelijk moet zijn om een programma van de ene regio naar een andere regio in het hoofdgeheugen te verplaatsen zonder de geheugenreferenties in het programma ongeldig te maken.

    7.2.2.1. Plaatsingsalgoritme

    Omdat geheugencompressie een tijdrovende zaak is moet de besturingssysteemontwerper slim zijn om te beslissen hoe processen toegewezen worden in het geheugen (hoe de gaten te vullen). Als het tijd is om een proces in het hoofdgeheugen te laden of te verwisselen en is zijn meer dan één voldoende groot vrij geheugenblok dan moet het besturingssysteem beslissen aan welk vrij blok het zal toewijzen.

    Drie plaatsingsalgoritmes die overwogen kunnen worden zijn best-fit, first-fit en next-fit. Ze zijn natuurlijk allemaal beperkt om te kiezen tussen de vrije geheugenblokken die van gelijke grootte of groter zijn dan het proces wat binnengebracht moet worden.

  • Best-Fit kiest het blok dat het beste overeenkomt met grootte van het aangevraagde proces.
  • First-Fit begint met het geheugen vanaf het begin te scannen en kiest het eerste beschikbare blok dat groot genoeg is.
  • Next-Fit begint het geheugen te doorzoeken vanaf het laatste geplaatste blok en kiest het eerstvolgende blok dat groot genoeg is.
  • Figuur 7.5a toont een voorbeeld van een geheugen configuratie nadat een aantal plaatsing en verwisseling (swapping-out) bewerkingen hebben plaatsgevonden. Het laatst gebruikte blok was een 22-Mbyte blok van welk een 14-Mbyte partitie was gecreëerd. Figuur 7.5b laat het verschil zien tussen best-, first- en next-fit plaatsingsalgoritmes om te voldoen aan een 16-Mbyte toewijzingsaanvraag. Best-fit zal de hele lijst van beschikbare blokken doorzoeken en zal gebruik maken van het 18-Mbyte blok wat een fragment van 2-Mbyte overlaat. First-fit resulteert in een 6-Mbyte fragment en next-fit resulteert in een 20-Mbyte fragment.

    7.2.2.2. Vervangingsalgoritme

    In een multiprogrammeringssysteem dat gebruik maakt van dynamische partitionering zal er een moment komen dat alle processen in het hoofdgeheugen in een geblokkeerde toestand staan en dat er niet genoeg geheugen voor een extra proces is, zelfs niet na compressie. Om de te vermijden dat er processortijd wordt verkwist doordat het aan het wachten is op een niet-geblokkeerd actief proces zal het besturingssysteem één van de processen verwisselen (swap-out) uit het hoofdgeheugen om plaatst te maken voor een nieuw proces of een proces in de Ready-Suspend toestand. Daarom moet een besturingssysteem kiezen welk proces het gaat vervangen.

    7.2.3. Buddysysteem

    Zowel vaste als dynamische partitionering hebben hun keerzijde. Een vaste partitioneringsschema beperkt het aantal actieve processen en kan de ruimte inefficiënt gebruiken als de beschikbare partitiegroottes en procesgroottes niet goed overeenkomen. Een dynamisch partitioneringsschema is complexer om te onderhouden en bevat de overhead van compressie. Een interessant compromis is het gebruik van het buddy systeem.

    Werking

  • Partitie splitsen tot
    1ste deel = even groot als proces
    2de deel = rest grootte partitie
  • Partities samenvoegen
    Als er 2 opeenvolgende delen van een zelfde grootte vrij komen
  • 7.2.4. Relocatie

    Voordat we manieren overwegen om te gaan met de tekortkomingen van partitionering moeten we enkele zaken verduidelijken met betrekking tot de plaatsing van processen in het geheugen. Als een vast partitioneringsschema uit figuur 7.3a is gebruikt dan kunnen we verwachten dat een programma altijd toegewezen wordt aan dezelfde partitie. Dat wil zeggen, om het even welke partitie geselecteerd is als een nieuw proces wordt geladen zal die partitie altijd gebruikt worden om dat proces terug te verwisselen in het geheugen nadat het verwisseld (swapped-out) is.

    In het geval van gelijke partitiegroottes (figuur 7.2) en in het geval van een enkele wachtrij voor partities van ongelijke groottes (figuur 7.3b) kan een proces verschillende partities bezetten gedurende zijn levensduur. Als de eerste maal een procesbeeld gemaakt wordt, wordt het geladen in een of andere partitie van het hoofdgeheugen. Nadien kan het proces verwisselt worden uit (swapped-out); als het vervolgens terug verwisseld worden in (swapped-in) kan het aan een andere partitie worden toegewezen dan voorheen. Hetzelfde is waar voor dynamische partitionering. Merk op dat in figuur 7.4c en figuur 7.4h dat proces 2 twee verschillende geheugenregio's bezet van de twee kansen als het ingeladen wordt. Verder als compressie wordt gebruikt, worden processen verplaatst als ze in het hoofdgeheugen zitten. Dus de locaties (van instructies en data) die door een proces verwezen zijn liggen niet vast. Iedere keer dat een proces verwisseld word in (swapped-in) of verplaatst wordt zullen deze veranderen. Om dit probleem op te lossen zal een onderscheid gemaakt moeten worden tussen verschillende soorten adressen.

  • Een logisch adres is een referentie naar een onafhankelijke geheugenlocatie van de huidige toewijzing van data aan het geheugen; een vertaling naar een fysiek adres moet gemaakt worden voordat geheugen benaderd kan worden.
  • Een relatief adres is een specifiek voorbeeld van een logisch adres waarvan het adres uitgedrukt wordt als een relatieve locatie ten opzichte van een bekend punt, gebruikelijk een waarde in een processor register.
  • Een fysiek adres of absoluut adres is een werkelijke locatie in het hoofdgeheugen.
  • 7.3. Paginering

    Zowel ongelijke vaste- als dynamische partitiegroottes zijn inefficiënt in het geheugengebruik; de eerste resulteert in interne fragmentatie en de laatste in externe fragmentatie. Veronderstel dat het hoofdgeheugen echter ingedeeld is in gelijke vaste-grootte delen die relatief klein zijn (2 tot 4K). Dan kunnen de blokken die gekend zijn als pagina's toegewezen worden als beschikbare blokken geheugen, gekend als frames, of pagina frames. We laten in deze sectie zien dat de oorzaak van de verspilde geheugenruimte voor ieder proces aan de interne fragmentatie ligt en dat het enkel een fractie bevat van de laatste pagina van een proces. Er is geen externe fragmentatie.

    Figuur 7.0 illustreert het gebruik van pagina's en frames. Op een gegeven moment zijn sommige frames in het geheugen in gebruik en andere vrij. Een lijst met vrije frames wordt onderhouden door het besturingssysteem. Proces A, op disk opgeslagen, bestaat uit vier pagina's. Als het tijd is om dit proces te laden, vind het besturingssysteem vier vrije frames en laad de vier pagina's van proces A in deze vier frames (figuur 7.9b). Proces B, bestaande uit drie pagina's, en proces C bestaande uit vier pagina's worden vervolgens geladen. Dan zal proces B opgeschort worden en uitgewisseld worden uit (swapped-out) het hoofdgeheugen. Nadien zullen alle processen in het hoofdgeheugen geblokkeerd zijn en het besturingssysteem moet nieuwe processen ophalen, proces D, welk uit vijf pagina's bestaat.

    Veronderstel nu, zoals in dit voorbeeld, dat er niet genoeg ongebruikte frames zijn om het proces te bevatten. Zal dit het besturingssysteem belemmeren om proces D te laden? Het antwoord is nee, omdat we alweer het concept van logisch adres kunnen gebruiken. Een eenvoudig basis adresregister volstaat niet langer. Het besturingssysteem onderhoudt een paginatabel voor ieder proces. De paginatabel laat voor iedere pagina van het proces de frame locatie zien. Binnen het programma bestaat ieder logisch adres uit een paginanummer en een offset binnen die pagina. Herinner dat in het geval van eenvoudige partitionering een logisch adres de locatie is van een woord relatief tot het begin van het programma; de processor vertaalt dat in een fysiek adres. Met paginering zal de logische-naar-fysieke adresvertaling nog steeds gedaan worden door de processor hardware. De processor moet weten hoe het toegang krijgt tot de paginatabel van het huidig proces. Voorgesteld door een logisch adres (paginanummer, offset) gebruikt de processor de paginatabel om een fysiek adres (frame nummer, offset) te maken.

    Verdergaand met ons voorbeeld, de vijf pagina's van proces D zijn geladen in frames 4, 5, 6 en 12. Figuur 7.10 laat de verschillende paginatabellen op dit moment zien. Een paginatabel bevat één ingang voor iedere pagina van het proces, zodat de tabel eenvoudig indexeerbaar is door het paginanummer (beginnend bij pagina 0). Iedere paginatabelingang bevat het aantal van de frames in het hoofdgeheugen, als er een is dat de corresponderende pagina bevat. Het besturingssysteem onderhoud een enkelvoudige vrije-frame lijst van alle frames in het hoofdgeheugen die momenteel niet bezet zijn en beschikbaar voor pagina's.

    We zien dus dat eenvoudige paginering, zoals hier beschreven, gelijkaardig is als vaste partitionering. De verschillen met paginering zijn dat de partities eerder klein zijn; een programma kan meer dan één partitie bezetten; en deze partities moeten niet aaneensluitend zijn.

    Om samen te vatten zal het hoofdgeheugen met eenvoudige paginering opgedeeld worden in veel kleine frames van gelijke grootte. Elk proces is opgedeeld in frame-grootte pagina's. Kleinere processen vereisen minder pagina's; grote processen vereisen meer. Als een proces ingeladen word, dan zullen alle pagina's in de beschikbare frames geladen worden en zal er een paginatabel opgemaakt worden. Deze manier van aanpak lost een aantal problemen inherent aan partitionering op.

    7.4. Segmentatie

    Een gebruikersprogramma kan opgedeeld worden door gebruikmaking van segmentatie, in welke het programma en zijn bijbehorende data opgedeeld zijn in een aantal segmenten. Het niet vereist dat alle segmenten van alle programma dezelfde grootte hebben, alhoewel er een maximum segment grootte is. Zoals met paginering, bestaat een logisch adres dat gebruik maakt van segmentatie uit twee delen, in dit geval een segmentnummer en een offset.

    Door het gebruik van segmenten van niet gelijke grootte, is segmentatie gelijkaardig aan dynamische partitionering. In de afwezigheid van een overlayschema of het gebruik van virtueel geheugen zou het noodzakelijk zijn dat alle programmasegmenten voor uitvoering in het hoofdgeheugen geladen zijn. Het verschil ten opzichte van dynamische partitionering is dat met segmentatie een programma meer dan één partitie kan bezetten en deze partities niet aaneensluitend hoeven te zijn. Segmentatie elimineert interne fragmentatie, maar lijdt het aan externe fragmentatie zoals dynamische partitionering. Omdat een proces opgesplitst is in een aantal kleinere stukken zal de externe fragmentatie kleiner zijn.

    Waar paginering onzichtbaar is voor de programmeur, is segmentatie gebruikelijk zichtbaar en is voor het gemak voorzien om programma's en data te organiseren. Kenmerkend is dat programmeur of compiler programma's en data aan verschillende segmenten wil toewijzen. Het voornaamste ongemak van deze dienst is dat de programmeur zich bewust moet zijn van de maximale segment grootte.

    Een andere consequentie van niet gelijke segmentgroottes is dat er geen eenvoudige relatie is tussen logische adressen en fysieke adressen. Overeenkomstig met paginering zal een eenvoudig segmentatieschema gebruikmaken van een segmenttabel voor ieder proces en een lijst van vrije hoofdgeheugenblokken. Iedere segmenttabelingang zou het startadres van het corresponderend segment in het hoofdgeheugen moeten geven. De ingang zou ook lente van het segment moeten bepalen om er zeker van te zijn dat er geen ongeldige adressen worden gebruikt. Als een proces de naar de Running toestand gaat wordt het adres van zijn segmenttabel in een speciaal register geladen dat door de geheugenbeheerhardware wordt gebruikt.

    Om samen te vatten, wordt een proces met eenvoudige segmentatie opgesplitst in een aantal segmenten dat niet van gelijke grootte moet zijn. Als een proces ingeladen wordt, worden al zijn segmenten in de beschikbare geheugenregio's geladen en een segmenttabel opgezet.

    7.5. Beveiligingskwesties

    Hoofdgeheugen en virtueel geheugen zijn systeem bronnen die onderworpen zijn aan beveiligingsdreigingen en waarvoor beveiligingstegenmaatregelen tegen genomen moet worden. De meest voor de hand liggende vereiste voor beveiliging is de preventie van niet geoorloofde toegang tot de geheugeninhoud van processen. Als een proces een deel van zijn geheugen niet gedeclareerd heeft als deelbaar, dan zou geen enkel ander proces toegang mogen hebben tot de inhoud van dat deel van het geheugen. Als een proces verklaart dat dat een deel van zijn geheugen deelbaar is voor andere aangewezen processen, dan moet het beveiligingsservice van het besturingssysteem garanderen dat alleen de aangewezen processen toegang hebben. De beveiligingsdreigingen en tegenmaatregelen zoals besproken in hoofdstuk 3 zijn relevant voor dit type van geheugenbeveiliging. 

    7.5.1. Buffer overflow attacks

    Een buffer overflow kan gebeuren als een resultaat van een programmeerfout wanneer een proces, data probeert op te slaan buiten de limieten van een vaste-grootte buffer en bijgevolg aansluitende geheugenlocaties overschrijft. De consequenties van deze fout kan de corruptie van de door programma's gebruikte data bevatten, niet verwachte overdracht van de programmacontrole, mogelijke overtredingen van geheugentoegang en heel waarschijnlijk eventuele programma beëindiging. Als dit bewust wordt gedaan als deel van een systeemaanval, kan de overdracht van controle de code worden van de aanvaller wat kan resulteren in de mogelijkheid om arbitraire code uit te voeren met dezelfde rechten van het aangevallen proces. Buffer overflows zijn een van de meest gangbare en kwetsbare types van beveiligingsaanvallen.

    7.5.2. Bescherming tegen buffer overflows

    Het vinden van en uitbuiten van een stack buffer overflow is niet zo moeilijk. Het grote aantal aanvallen over de laatste tien jaar illustreert dit duidelijk. Er is duidelijk een behoefte om systemen te beschermen tegen zulke aanvallen door ze te voorkomen of op zijn minst te detecteren en zulke aanvallen af te breken. Tegenmaatregelen kunnen ruim ingedeeld worden in twee categorieën:

  • Compile-time defensie, welke zich richt om programma's harder te maken om aanvallen te weerstaan in nieuwe programma's.
  • Run-time defensie, welke zich richt tot het detecteren en afbreken van aanvallen in bestaande programma's.
  • Terwijl er al een tiental jaar geschikte verdedigingen gekend zijn, belemmeren de bestaande kwetsbare software en systemen hun implementatie. Vandaar de interesse in run-time defensie, welke uitgerold kan worden in besturingssystemen en updates. Ze kunnen voorzien van enige beveiliging voor reeds bestaande kwetsbare software.

    Herhalingsvragen

    1. Aan welke eisen behoort geheugenbeheer te voldoen?

      Relocatie, bescherming, delen, logische indeling, fysieke indeling.
       
    2. Waarom is het gewenst dat de mogelijkheid bestaat processen te kunnen verplaatsen (relocate)?

      Meestal weet de programmeur niet van tevoren welke andere programma's in het hoofdgeheugen aanwezig zijn op het moment dat het programma wordt uitgevoerd. Bovendien willen we actieve processen uit en naar het hoofdgeheugen kunnen swappen. Als we beschikken over een groot aantal processen die gereed staan voor uitvoering, kunnen we het processorgebruik maximaliseren. In beide gevallen is de specifieke locatie van het proces in het hoofdgeheugen niet voorspellen.
       
    3. Waarom is het niet mogelijk geheugenbescherming tijdens het compileren af te dwingen?

      Omdat de locatie van een programma in het hoofdgeheugen onbekend is, is het onmogelijk absolute adressen te controleren bij het compileren om te zorgen voor de juiste bescherming. Bovendien bieden de meeste programmeertalen de mogelijkheid adressen dynamisch te berekenen tijden de uitvoering (bijvoorbeeld door het berekenen van een array-index of van een verwijzing naar een gegevensstructuur). Daarom moeten alle geheugenverwijzingen die een proces maakt, tijd de uitvoering worden gecontroleerd. Zo kan men er zeker van zijn dat alleen wordt verwezen naar het geheugengedeelte van het proces zelf.
       
    4. Geef een paar redenen waarom twee of meer processen toestemming krijgen om toegang te hebben tot een bepaald geheugengebied.

      Als een aantal processen hetzelfde programma uitvoeren, is het zinvol alle processen toegang te geven tot hetzelfde exemplaar van het programma en niet elk proces een eigen kopie te laten gebruiken. Processen die samenwerken aan een taak kunnen toegang tot dezelfde gegevensstructuur moeten delen.
       
    5. Wat zijn de voordelen van het gebruik van partities van ongelijke omvang bij vaste partitionering?

      1. Het is mogelijk om één of twee vrij grote partities te voorzien en nog een groot aantal partities te over hebben. De grote partities kunnen het mogelijk maken de volledige grootte van het programma te laden.
      2. Interne fragmentering wordt verminderd omdat een klein programma in een kleine partitie kan worden geplaatst.

       
    6. Wat is het verschil tussen interne en externe fragmentatie?

      Interne fragmentering verwijst naar de verspilde ruimte interne binnen een partitie vanwege het feit dat het blok gegevens dat geladen is kleiner is dan de partitie.
      Externe
      fragmentatie is een fenomeen geassocieerd met dynamische partitionering, en verwijst naar het feit dat een groot aantal kleine gebieden hoofdgeheugen buiten een partitie accumuleert.

       
    7. Wat is het onderscheid tussen een logisch, een relatief en een fysiek adres?

      Een logisch adres is een verwijzing naar een geheugenlocatie die onafhankelijk is van de huidige toewijzing van gegevens aan het geheugen. Een logisch adres moet worden vertaald in een fysiek adres voordat geheugentoegang mogelijk is.
      Een relatief adres
      is een speciaal geval van een logisch adres waarbij een adres wordt uitgedrukt als een locatie ten opzichte van een bekend punt, doorgaans het begin van een programma.
      Een fysiek
      of absoluut adres is een echte locatie in het hoofdgeheugen.
       
    8. Wat is het verschil tussen een pagina en een frame?

      In een pagineringsysteem worden programma's en gegevens die op schijf worden opgeslagen, verdeeld in blokken van gelijke vaste grootte die pagina's worden genoemd. En het  hoofdgeheugen is verdeeld in blokken van dezelfde grootte die frames worden genoemd. Precies één pagina past in een frame.
       
    9. Wat is het verschil tussen een pagina en een segment?

      Een andere manier waarop het gebruikersprogramma kan worden onderverdeeld is segmentatie. In dit geval, wordt het programma en de bijbehorende data verdeeld in een aantal segmenten. Het is niet vereist dat alle segmenten van de programma's dezelfde lengte moeten hebben, hoewel er een maximale segmentlengte is.

    Probleemvraagstukken

    1. In paragraaf 2.3.2 werden vijf hoofdtaken van het geheugenbeheer genoemd en paragraaf 7.1 vijf vereisten. Toon aan dat elke lijst automatisch de punten uit de andere lijst bevat.
       
    2. Ga uit van een systeem voor dynamische partitionering. Laat zien dat het aantal gaten in het geheugen gemiddeld de helft is van het aantal segmenten.
       
    3. Voor het implementeren van de verschillende plaatsingsalgoritmen bij dynamische partitionering, die werden besproken in paragraaf 7.2, moet een lijst met vrije geheugenblokken worden bijgehouden. Wat is bij elk van de drie besproken methoden (best-fit, first-fit en last-fit) de gemiddelde zoeklengte?
       
    4. Een andere plaatsingsalgoritme bij dynamische partitionering wordt soms slechts-passend blok (worst-fit) genoemd. Hierbij wordt het grootste vrije geheugen gebruikt voor het binnenhalen van een proces. Bespreek de voordelen en nadelen van deze aanpak in vergelijking met first-fit, next-fit en best-fit. Wat is de gemidde7t zoeklengte bij worst-fit?
       
    5. Een geheugenblok van 1 megabyte (MB) wordt toegewezen met het buddysysteem.
      1. Toon de resultaten van de volgende reeks in een overzicht, vergelijkbaar met figuur 7.6:
      2. verzoek A om 70 KB
      3. verzoek B om 35 KB
      4. verzoek C om 80 KB
      5. vrijgeven van A
      6. verzoek D om 60 KB
      7. vrijgeven van B
      8. vrijgeven van D
      9. vrijgeven van C
      10. Toon de binaire boomstructuur die volgt op het vrijgeven van B.
         
    6. Ga uit van een buddysysteem waarin een bepaald blok bij de huidige toewijzing het adres 011011110000 heeft.
      1. Als de blokgrootte 4 bedraagt, wat is dan het binaire adres van zijn buddy?
         
      2. Als de blokgrootte 16 bedraagt, wat is dan het binaire adres van zijn buddy?
         
    7. Veronderstel dat buddyk(x) = adres van de buddy van het blok met de grootte 2k waarvan het adres x is. Schrijf een algemene vergelijking voor buddyk(x).
       
    8. De reeks van Fibonacci wordt als volgt gedefinieerd:


       
      1. Kan deze reeks worden gebruikt voor het opzetten van een buddysysteem?
         
      2. Wat is het voordeel van dit systeem in vergelijking met het binaire buddy-systeem dat in dit hoofdstuk is beschreven?
         
    9. Tijdens het verwerken van een programma verhoogt de processor de inhoud van het instructieregister (de programmateller) met één woord na het ophalen van elke instructie; de inhoud van dit register wordt echter gewijzigd als de processor een sprongopdracht of subroutineaanroep tegenkomt die ertoe leidt dat de uitvoering ergens anders in het programma wordt voortgezet. Ga nu uit van figuur 7.8. Voor instructieadressen bestaan twee alternatieven:
      1. Een relatief adres bijhouden in het instructieregister en de dynamische adresvertaling uitvoeren met het instructieregister als invoer. Bij een geslaagde sprongopdracht of subroutine-aanroep wordt het door die sprongopdracht of subroutineaanroep gegenereerde adres geladen in het instructieregister.
      2. Een absoluut adres bijhouden in het instructieregister. Bij een geslaagde sprong- opdracht of subroutineaanroep wordt een dynamische adresvertaling toegepast, waarvan de resultaten worden opgeslagen in het instructieregister.
        Welke benadering verdient de voorkeur?
         
    10. In een systeem met paginering is een virtueel adres a gelijkwaardig aan een koppel (p,w); hierbij is p het paginanummer en w een bytenummer (positie) binnen de pagina. Verder is z het aantal bytes binnen een pagina. Stel een algebraïsche vergelijking op waarin p en w functies zijn van z en a.
       
    11. Ga uit van een geheugen waarin de aaneengesloten segmenten S1, S2,... Sn achter elkaar worden geplaatst in de volgorde waarin ze zijn gemaakt, zoals wordt getoond in de volgende figuur.
       
      S1 S2 ? ? ? Sn Gat

      Wordt segment Sn + 1 gecreëerd, dan wordt dit direct achter segment Sn geplaatst, zelfs als enkele van de segmenten S1, S2,... Sn al zijn verwijderd. Bereikt de begrenzing tussen de (gebruikte of verwijderde) segmenten en het gat het einde van het geheugen, dan wordt samenpakken (compaction) toegepast op de gebruikte segmenten.

      1. Toon aan dat de fractie van de tijd F die wordt besteed aan het samenpakken, voldoet aan de volgende ongelijkheid:

        met
        s = gemiddelde lengte van een segment in woorden;
        t = gemiddelde levensduur van een segment in geheugenverwijzingen;
        f = deel van het geheugen dat ongebruikt is in een evenwichtstoestand.
        Aanwijzing: zoek de gemiddelde snelheid waarbij de begrenzing het geheugen overschrijdt en ga ervan uit dat het kopiëren van één woord ten minste twee geheugenverwijzingen vereist.
         
      2. Zoek F als f = 0,2, t = 1000 en s = 50.