Adresruimten en adresvertaling

Een actief programma werkt met een adresruimte: zijn eigen beeld van het geheugen, met genummerde bytelocaties. Het besturingssysteem plaatst het geheugen van het programma in de machine en zorgt dat de adressen de juiste fysieke bytes bereiken. De indeling die het programma ziet en de indeling in de hardware zijn verschillende zaken.

Waarom meerdere programma's in het geheugen blijven

Vroege systemen konden één programma naast het besturingssysteem houden. Het besturingssysteem kon bijvoorbeeld de eerste 64 KB innemen en het programma de rest van het geheugen. Met multiprogrammering stonden meerdere processen klaar, zodat de CPU kon werken terwijl een ander proces op invoer of uitvoer wachtte. Bij tijdsverdeling wisselde de CPU vaak genoeg tussen processen om interactieve gebruikers te bedienen.

Het volledige geheugen van een proces bij elke wisseling op schijf opslaan zou het wisselen veel te traag maken. Door meerdere processen in fysiek geheugen te houden is dat kopiëren niet nodig, maar ontstaat een beschermingsprobleem. Een adres dat door een proces wordt gevormd, mag het proces niet in staat stellen het besturingssysteem of een ander proces te overschrijven.

Geheugengroottes volgen hier de binaire conventie die in deze modellen wordt gebruikt: 1 KB is 1.024 bytes, ook geschreven als 1 KiB; 1 MB is 1.024 KB. Een adresruimte van 16 KB heeft 16.384 bytelocaties, genummerd van 0 tot en met 16.383. Het getal 16.384 is de eindgrens, geen geldig byteadres.

Code, data, heap en stack

In een klassieke onderwijsindeling van 16 KB gebruikt code de lage adressen, van 0 tot aan de grens van 1 KB. De heap begint boven de code en groeit omhoog. De stack begint bij de bovengrens en groeit omlaag. De vrije ruimte ertussen geeft beide gebieden ruimte om te groeien. Werkelijke indelingen verschillen; elke thread heeft bijvoorbeeld een eigen stack. De functies van de gebieden blijven ook nuttig als hun posities veranderen.

Volg een pointer naar het juiste geheugen

Een virtueel adres duidt een byte in de adresruimte van een proces aan. Een fysiek adres duidt een byte in de geheugenhardware van de machine aan. Wanneer C-code printf("%p", (void *) &x) afdrukt, wordt een virtueel adres afgedrukt. De afgedrukte pointer onthult niet welke fysieke byte x opslaat.

Stel dat twee processen allebei virtueel adres 1.000 gebruiken. Elk adres wordt geïnterpreteerd binnen de eigen adresruimte van het proces, zodat de toegangen verschillende fysieke bytes kunnen bereiken. Ook hoeft code op virtueel adres 0 niet op fysiek adres 0 te staan. Het besturingssysteem kan die elders plaatsen en hardwarevertaling instellen om die te bereiken.

De processor vertaalt het ophalen van instructies en lees- en schrijfbewerkingen. Het besturingssysteem kiest en beheert de koppelingen en kan daarbij fysieke locaties veranderen terwijl de virtuele adressen van het programma gelijk blijven.

Een geheugensysteem moet meer doen dan een getal correct vertalen. Het moet gewone programma's laten draaien zonder dat die de fysieke plaatsing beheren, de vertaling snel houden en de grenzen handhaven die delen veilig maken. Deze vereisten zijn transparantie, efficiëntie en bescherming.

Behoud het beeld van het programma

Transparantie betekent dat een programma draait alsof het eigen afgeschermd geheugen heeft. Het gebruikt zijn eigen adressen voor code en data zonder bij te houden welke andere processen aanwezig zijn of waar hun bytes liggen. Het besturingssysteem en de hardware behouden dit beeld achter de schermen. Als een proces in het fysieke geheugen wordt verplaatst, zou het zijn pointers niet hoeven te herschrijven.

Voor de illusie is geen afzonderlijke fysieke kopie van elke byte voor elk proces nodig. Beschermde alleen-lezen-code kan bijvoorbeeld worden gedeeld. Het gaat erom dat het delen het gedrag en de toegangsrechten behoudt waarop elk proces recht heeft.

Houd rekening met beide soorten kosten

Elke instructie die wordt opgehaald en elke lees- en schrijfbewerking vereist vertaling. Een routine van het besturingssysteem uitvoeren voor elke toegang zou de normale uitvoering te traag maken. Hardware voert de veelvoorkomende bewerkingen uit; code van het besturingssysteem verzorgt de instelling, wijzigingen en foutafhandeling.

Ruimte-efficiëntie is ook van belang. Een klein, snel vertaalmechanisme kan toch veel geheugen verspillen. Eén gebied met een basis en een grens reserveert de ongebruikte ruimte tussen heap en stack. Segmentatie voorkomt dat voor die ruimte fysiek geheugen nodig is, maar introduceert fysieke gebieden van verschillende grootte en gaten daartussen. Metadata, ongebruikte gereserveerde ruimte en gaten beïnvloeden allemaal hoeveel nuttig werk in het geheugen past.

Houd ongeldige toegang tegen bij de grens

Zonder bescherming zou een verdwaalde pointer in een teksteditor een ander proces of de kernel kunnen overschrijven. Schade kan dan veel later in niet-gerelateerde code zichtbaar worden. Als grenzen worden gehandhaafd, wijst de hardware toegang buiten het toegestane gebied af en veroorzaakt die een exceptie. Het besturingssysteem handelt de exceptie af en beëindigt meestal het proces met de fout, vaak met een melding van een segmentatiefout.

Bescherming isoleert processen van elkaar. Ze maakt geheugengebruik in C binnen een toegestaan heapgebied niet veilig. Een schrijfbewerking voorbij een toegewezen blok kan nog steeds een ander blok van hetzelfde proces raken. Procesgrenzen en grenzen van allocatorblokken zijn verschillende grenzen.

Scheid de bewerking van de keuze

Een mechanisme is de manier waarop een bewerking wordt uitgevoerd. De waarde van een basisregister optellen en een grensregister controleren zijn mechanismen. Beleid kiest tussen mogelijke acties: waar een proces wordt geplaatst, welk vrij gat wordt gebruikt of wanneer een segment wordt verplaatst.

Door deze twee te scheiden kan het besturingssysteem zijn plaatsingsstrategie wijzigen terwijl dezelfde hardwarevertaling behouden blijft. Geheugenvirtualisatie begint met dit eigen, beschermde geheugenbeeld; ze wordt niet gedefinieerd door de schijf als extra geheugen te gebruiken.

Een pointervariabele en het geheugen waarnaar die wijst, zijn afzonderlijke objecten. Inzicht in hun levensduur is het uitgangspunt voor de geheugen-API van C. Gewone lokale variabelen gebruiken doorgaans automatische stackopslag, heapblokken blijven bestaan totdat ze worden vrijgegeven en globale variabelen en lokale variabelen met static hebben opslag voor de hele uitvoering van het programma.

Volg de toewijzing, niet alleen de pointer

void f(void) {
    int x;
    int *p = malloc(sizeof(int));
}

In de gebruikelijke stackindeling horen x en p bij deze aanroep van f. Het aangevraagde gehele getal hoort bij de heap. Bij terugkeer verdwijnt de lokale pointervariabele; het heapblok wordt niet vrijgegeven. Als er geen kopie van het adres overblijft, heeft het programma de toegang tot nog toegewezen geheugen verloren: een geheugenlek.

malloc(size) vraagt minstens dat aantal bytes aan en geeft een pointer terug, of NULL als niet aan de aanvraag kan worden voldaan. De bytes worden niet voor het programma geïnitialiseerd. Gebruik voor 10 gehele getallen malloc(10 * sizeof(int)); waar een geheel getal 4 bytes groot is, vraagt dit 40 bytes aan. Reserveer voor een string ruimte voor de tekens plus één byte voor het afsluitende nullteken: malloc(strlen(s) + 1).

sizeof(a) meet het object met de naam a. Als a een pointer is, geeft het de grootte van de pointer, niet die van de toewijzing. Een pointer van 8 bytes kan naar een blok van 40 bytes verwijzen.

Weet wat elke bibliotheekbewerking doet

free krijgt de teruggegeven pointer mee, zonder argument voor de grootte. De allocator bewaart metadata over de grootte, meestal in een header vóór het blok. Geef de teruggegeven pointer van een momenteel toegewezen blok door; een pointer naar een locatie binnen het blok is geen geldig alternatief. free(NULL) is geldig en doet niets. Deze functies zijn routines uit de C-bibliotheek, geen systeemaanroepen.

Herken de fout aan de levensduur of grens

Een pointer zonder geldige toewijzing kan niet worden gebruikt alsof die al naar opslag wijst. Nieuw toegewezen bytes lezen voordat ze zijn geïnitialiseerd, is lezen van niet-geïnitialiseerd geheugen. Voorbij het toegewezen einde schrijven is een bufferoverloop; die kan ontstaan als de byte voor het afsluitende nullteken van een string ontbreekt.

Na free zijn oude pointers naar het blok ongeldig. Toegang via zo'n pointer is gebruik na vrijgave (use-after-free). Het blok opnieuw vrijgeven is een dubbele vrijgave. Een adres vrijgeven dat de allocator niet voor een nog toegewezen blok heeft teruggegeven, is een ongeldige vrijgave. Een blok lekken is anders: het blok blijft toegewezen, maar het programma geeft het niet meer vrij wanneer dat zou moeten.

Begrijp wat de hardware kan controleren

Compilatie kan ondanks al deze fouten slagen. Hardware controleert normaal gesproken procesgebieden en toegangsrechten, niet elke bibliotheektoewijzing. Een blokgrens overschrijden terwijl je binnen de toegestane heap van het proces blijft, kan ongedefinieerd gedrag opleveren zonder directe foutmelding. Het programma kan gegevens beschadigen, later vastlopen, betekenisloze waarden lezen of lijken te werken. Valgrind en AddressSanitizer kunnen veel van zulke fouten tijdens de uitvoering detecteren.

De C-bibliotheek en het besturingssysteem beheren geheugen op verschillende niveaus. Het besturingssysteem legt gebieden in de adresruimte van een proces vast en voorziet die van fysiek geheugen. De allocator verdeelt beschikbaar heapgeheugen in blokken, registreert vrije blokken en gebruikt die opnieuw bij volgende aanroepen.

Verplaats de heapgrens

De heapgrens is het adres direct na het einde van de traditionele heap. brk stelt die grens in op een gekozen adres. sbrk(n) verplaatst de grens met een aantal bytes en geeft bij succes de oude grens terug. sbrk(0) geeft de huidige grens zonder die te verplaatsen.

Stel dat de heapgrens 40.960 is en de allocator sbrk(8192) met succes aanroept. De teruggegeven waarde is 40.960. De nieuwe grens is:

De toegevoegde bytes beslaan de virtuele adressen 40.960 tot en met 49.151. De nieuwe heapgrens, 49.152, ligt direct voorbij het toegevoegde gebied. Als je de teruggegeven waarde met de nieuwe grens verwart, verschuift elke latere plaatsingsberekening.

Toepassingen gebruiken de toewijzingsbibliotheek in plaats van de heapgrens rechtstreeks te verplaatsen. De bibliotheek houdt bij welke delen van het gebied haar toebehoren. Onafhankelijke wijzigingen van die grens kunnen de administratie ongeldig maken.

Verkrijg een afzonderlijke geheugenkoppeling

mmap kan een anoniem gebied aanmaken: geheugen dat niet aan een bestand is gekoppeld en aanvankelijk met nulbytes is gevuld. munmap verwijdert een geheugenkoppeling. Een allocator kan afzonderlijke geheugenkoppelingen voor grote toewijzingen gebruiken en die aan het besturingssysteem teruggeven wanneer ze worden vrijgegeven.

In glibc is de standaarddrempel voor deze aanpak aanvankelijk 128 KB, oftewel 131.072 bytes, en die kan naar boven worden aangepast. Een voldoende grote toewijzing krijgt doorgaans een afzonderlijke geheugenkoppeling als de aanvraag niet uit bestaande vrije ruimte kan worden voldaan. Dit is beleid van de bibliotheek, geen universele scheidslijn in de taal C.

Geef vrij op bibliotheekniveau of op het niveau van het besturingssysteem

Een aanroep van free plaatst een klein blok meestal terug in de voorraad van de bibliotheek. Het proces kan daarna dus hetzelfde geheugengebruik melden. Het geheugen is beschikbaar voor hergebruik zonder een nieuwe aanvraag aan het besturingssysteem.

Bij beëindiging van een proces worden zelfs toewijzingen teruggenomen die het programma heeft gelekt. Tijdens de levensduur van een langdurig actieve server blijven herhaalde lekken echter het beschikbare geheugen verbruiken. Terugname bij beëindiging voorkomt die druk tijdens de uitvoering niet.

Verbind heapgroei met vertaling

In het segmentatiemodel is de heap een aaneengesloten fysiek segment. Om te groeien zijn direct erboven vrije fysieke bytes nodig. Als die bytes bezet zijn, kan het besturingssysteem het segment naar een groter gat verplaatsen en de vertaaltoestand bijwerken. Als geen geschikt gebied beschikbaar is, mislukt de groei. Als de allocator niet genoeg ruimte kan verkrijgen, geeft malloc NULL terug.

Dynamische relocatie vertaalt adressen terwijl een programma draait. In het model met een basis en een grens neemt één proces één aaneengesloten fysiek gebied in. Begin met even grote adresruimten die in het fysieke geheugen passen; één registerpaar beschrijft dan het gebied van het proces dat op dat moment draait.

Controleer eerst het virtuele adres

Het basisregister bevat het fysieke adres van de eerste byte van het gebied. Het grensregister, of limietregister, bevat de grootte van het gebied in bytes. Voor een niet-negatief virtueel adres geldt:

Als de controle slaagt:

Anders veroorzaakt de hardware een exceptie. Een grootte is een aantal, dus het adres dat gelijk is aan de grens ligt al buiten het gebied. Negatieve virtuele adressen zijn ook ongeldig.

Doorloop de bytegrenzen

Neem een adresruimte van 8 KB met basis 20.480 en grens 8.192. De virtuele bytes lopen van 0 tot en met 8.191. Virtueel adres 1.000 komt door de controle en bereikt fysieke byte 21.480. De laatste toegestane virtuele byte, 8.191, bereikt 28.671. Adres 9.000 komt niet door de controle omdat het minstens 8.192 is; de hardware moet het afwijzen voordat de fysieke toegang plaatsvindt.

Het ophalen van instructies gebruikt dezelfde vertaling als data. Als een instructie op virtueel adres 128 vanaf virtueel adres 3.000 laadt, bereikt het ophalen fysiek adres 20.608 en het laden 23.480. Dit zijn twee geheugentoegangen met twee vertaalde adressen, niet één gedeelde vertaling voor de hele instructie.

Houd de grensconventies uit elkaar

Hetzelfde gebied van 8 KB heeft fysieke eindgrens 28.672. Beide conventies staan precies de bytes 20.480 tot en met 28.671 toe. Als je fysiek adres 21.480 met grootte 8.192 vergelijkt, haal je de twee conventies door elkaar en wijs je een toegestane toegang ten onrechte af.

Verplaats geheugen zonder pointers te veranderen

De MMU, of geheugenbeheereenheid, voert de controles en de optelling uit. Het besturingssysteem kan een proces onderbreken, zijn gebied naar een andere plaats kopiëren en de basis wijzigen. Het proces blijft dezelfde virtuele adressen gebruiken; daarom is de relocatie dynamisch.

Bij statische relocatie herschrijft een laadprogramma daarentegen de opgenomen adressen bij het laden van code. Een verwijzing van 1.000 naar 21.480 herschrijven legt een fysieke plaatsing vast in het programma. Als je het later verplaatst, moet je opnieuw adressen herschrijven, en herschrijven alleen voorkomt niet dat een programma een adres buiten zijn gebied vormt.

Tel een basis alleen op bij een virtueel adres. Als je die optelt bij een al vertaald fysiek adres, verschuif je de locatie een tweede keer en gaat de koppeling verloren.

De hardware bevat vertaalregisters voor het proces dat op een CPU draait. Het besturingssysteem bewaart de opgeslagen toestand van processen die wachten. Voor bescherming is het nodig dat alleen geprivilegieerde code van het besturingssysteem die toestand kan wijzigen.

Zorg voor de hardwarebewerkingen

De CPU heeft gebruikers- en kernelmodus nodig, een basis-grenspaar in de MMU en schakelingen voor de controle en optelling. Ook zijn geprivilegieerde bewerkingen nodig om het paar te wijzigen en exceptieafhandelaars te installeren. Ongeldige adressen en pogingen om in gebruikersmodus geprivilegieerde instructies uit te voeren moeten excepties veroorzaken.

Als een gebruikersprogramma zijn basis kon wijzigen, zou het zijn adressen naar de kernel of een ander proces kunnen omleiden. Grenscontroles zouden dan het verkeerde gebied beschermen. Het beperken van wijzigingen maakt daarom deel uit van het beschermingsmechanisme en is niet alleen een administratief hulpmiddel.

Maak een proces aan en voer het uit

Bij het opstarten installeert het besturingssysteem zijn trap- en exceptieafhandelaars, start het de interrupttimer en bereidt het de registratie van vrij geheugen voor. Wanneer een proces start, zoekt het besturingssysteem een fysieke plaats voor de adresruimte. Bij even grote plaatsen kan een vrijelijst eenvoudig bijhouden welke plaatsen ongebruikt zijn.

Het besturingssysteem markeert de gekozen plaats als bezet, legt de basis en grens van het proces vast, laadt de registers en gaat naar gebruikersmodus. Het proces draait daarna rechtstreeks op de CPU. Hardware vertaalt gewone toegangen zonder voor elke byte het besturingssysteem aan te roepen.

Herstel het juiste paar bij een contextwisseling

Een timerinterrupt draagt de besturing over aan het besturingssysteem. Dat slaat de registers van het oude proces, inclusief basis en grens, op in het procesbesturingsblok en herstelt daarna de waarden van het volgende proces voordat het terugkeert naar gebruikersmodus.

Stel dat de basis van A 20.480 is en die van B 40.960, beide met grens 8.192. Het virtuele adres 1.000 van A bereikt 21.480. Na de wisseling naar B bereikt hetzelfde virtuele getal 41.960. Als de CPU-registers worden hersteld zonder de vertaaltoestand te herstellen, zou B met zijn pointers toegang krijgen tot het gebied van A.

De CPU bevat het actieve paar; elk proces heeft zijn eigen opgeslagen paar. Stel je dus niet één permanent paar voor de hele machine voor en neem niet aan dat de paren van alle processen tegelijk op één CPU actief zijn.

Verplaatsen, fouten afhandelen en beëindigen

Om A naar fysiek adres 49.152 te verplaatsen haalt het besturingssysteem A van de CPU, kopieert het zijn gebied van 8 KB en werkt het de opgeslagen basis van A bij. Zodra A verdergaat met die basis ingesteld, bereikt virtueel adres 1.000 het adres 50.152. De virtuele pointerwaarden hoeven niet te worden aangepast.

Bij ongeldige toegang veroorzaakt de hardware een exceptie en draagt die de uitvoering in kernelmodus over aan de geregistreerde afhandelaar. Het besturingssysteem beëindigt meestal het proces dat de fout veroorzaakte. Bij beëindiging geeft het de plaats terug aan de vrijelijst en geeft het de procesregistratie vrij.

De methode met een basis en een grens bereikt twee doelen tegen lage kosten: de vertaling is transparant en elk adres wordt aan het toegewezen gebied getoetst. De belangrijkste zwakte is de verhouding tussen dat gebied en de bytes die het proces daadwerkelijk gebruikt.

Reserveer het hele bereik

De hardware heeft voor de veelvoorkomende bewerking alleen een optelling en een vergelijking nodig. Een allocator met plaatsen van vaste grootte kan ook snel een vrije plaats kiezen. Geen van beide voordelen betekent dat de plaats vol nuttige data staat.

In de klassieke indeling staan code en heap dicht bij het ene uiteinde en de stack dicht bij het andere. Eén basis-grenspaar vertaalt het hele interval. De ongebruikte ruimte tussen heap en stack neemt net als de nuttige delen fysiek geheugen in.

Voor een adresruimte van 16 KB die 1 KB code, 2 KB heap en 1 KB stack gebruikt:

De verspilling is interne fragmentatie: ongebruikte bytes binnen een gebied dat al aan een proces is toegewezen. Ze ontstaat niet doordat de heapallocator een slecht blok kiest. Zelfs bij een volledig benutte heap van 2 KB blijft het grote gat in het midden gereserveerd.

Onderscheid drie vragen over grootte

De omvang van de adresruimte, de bytes die momenteel worden gebruikt en het beschikbare fysieke geheugen zijn verschillende grootheden. Een 32-bitsadresruimte met byteadressering omvat $2^{32}$ bytes, oftewel 4 GB. Om die als één fysiek blok te reserveren is de volledige 4 GB nodig, ook als het proces momenteel maar enkele megabytes gebruikt.

Plaatsen van verschillende grootte maken neemt de beperking van gelijke grootte weg, maar niet de noodzaak van een aaneengesloten gat. Het levert ook een plaatsingsprobleem op: het besturingssysteem moet kiezen tussen vrije gaten van verschillende grootte. Eén plaats verkleinen kan niet zowel lage codeadressen als een verafgelegen hoog stackadres behouden als het hele bereik binnen dezelfde eenvoudige koppeling geldig moet blijven.

Reloceer de gebieden afzonderlijk

Code, heap en stack hoeven niet naast elkaar in het fysieke geheugen te staan om het geheugenbeeld van het programma te behouden. Door elk gebied een eigen basis en grens te geven kan het besturingssysteem alleen de gebruikte delen toewijzen en het virtuele gat zonder fysiek geheugen laten. Dit is segmentatie, de uitbreiding van één relocatiepaar naar meerdere logische gebieden.

Voor de indeling van 16 KB hierboven hebben de drie gebruikte gebieden samen slechts 4 KB nodig, afgezien van hun eigen beheeroverhead. De ruimtebesparing ontstaat doordat verandert wat als één eenheid wordt gereloceerd, niet doordat de optelling met het basisregister sneller wordt.

Een segment is een aaneengesloten gebied van een adresruimte met één doel. In het klassieke model krijgen code, heap en stack elk een eigen basis en grootte. Hun fysieke gebieden kunnen onafhankelijk van elkaar worden geplaatst, terwijl het proces zijn vertrouwde virtuele indeling behoudt.

Koppel alleen de gebruikte delen

Gebruik een adresruimte van 16 KB met de volgende plaatsing. De groottes gebruiken binaire KB, oftewel KiB.

Code en heap groeien naar hogere adressen; de vertaling van de stack gebruikt de bovengrens en een negatieve offset. De drie fysieke gebieden gebruiken samen slechts 7 KB. Voor de virtuele gaten ertussen is geen fysieke opslag nodig. Een segment blijft aaneengesloten; alleen de segmenten hoeven niet meer naast elkaar te liggen.

Vertaal een segment dat omhoog groeit

Bepaal eerst het segment. Bereken vervolgens de offset vanaf het virtuele begin. Controleer of de offset niet-negatief en kleiner dan de huidige grootte is en tel die dan op bij de fysieke basis:

Voor virtueel adres 500 is de codeoffset 500. Die is kleiner dan 2.048, dus de toegang bereikt fysiek adres 41.460.

Voor virtueel adres 5.000 is de heapoffset:

De groottecontrole slaagt omdat 904 kleiner is dan 3.072. Het resultaat is:

Als je het volledige virtuele adres bij de heapbasis optelt, krijg je 31.624. Daarmee neem je ten onrechte de virtuele beginpositie van de heap mee in een berekening die alleen de afstand binnen het segment nodig heeft.

Controleer het segment, niet alleen de omvang van de adresruimte

Virtueel adres 7.500 past nog steeds in 14 bits, maar is daarom niet automatisch toegestaan. De heapoffset is 3.404 en ligt daarmee buiten de huidige omvang van 3.072 bytes. De hardware veroorzaakt een exceptie. Een adres kan dus binnen het totale bereik van de adresruimte liggen en toch buiten elk geldig gebied vallen.

De term segmentatiefout ontstond voor ongeldige toegang bij segmentatie en wordt nog steeds gebruikt voor ongeldige toegang op systemen met andere vertaalmethoden. De foutnaam alleen geeft niet aan welk vertaalmechanisme de machine gebruikt.

Voordat hardware de basis en grootte van een segment kan gebruiken, moet die bepalen naar welk segment een toegang verwijst. Een expliciet ontwerp legt die keuze vast in adresbits. Een impliciet ontwerp leidt de keuze af uit de manier waarop de CPU het adres heeft gevormd.

Splits een 14-bitsadres

Gebruik de hoogste twee bits voor het segmentnummer en de laagste twaalf bits voor de offset. Het veld van twee bits heeft vier mogelijke waarden. Gebruik 00 voor code, 01 voor heap en 11 voor stack; laat 10 ongebruikt.

Het offsetveld kan 4.096 verschillende waarden voorstellen, van 0 tot en met 4.095. Het maximale virtuele bereik van elk segment is daarom 4 KB, ook als de huidige geldige omvang van het segment kleiner is. Maximale capaciteit en huidige grootte zijn verschillende grenzen.

Voor virtueel adres 5.000 is de 14-bitsweergave:

01 0011 1000 1000

De voorste 01 kiest de heap. De resterende 0011 1000 1000 is decimaal 904. Bij een heapgrootte van 3.072 en fysieke basis 26.624 komt de offset door de groottecontrole en wordt fysiek adres 27.528 bereikt.

Gebruik een masker en een verschuiving

Dezelfde splitsing kan als code worden uitgedrukt:

segment = (va & 0x3000) >> 12;
offset = va & 0x0FFF;

Het masker 0x3000 behoudt de twee selectiebits; een verschuiving met twaalf brengt die naar de laagste posities en levert zo het segmentnummer op. Het masker 0x0FFF wist de selectiebits en behoudt de offset. Voor va = 0x1388 zijn de resultaten segment 1 en offset 0x388, oftewel 904.

Tel 0x1388 niet rechtstreeks bij de heapbasis op. Die waarde bevat zowel de segmentselector als de offset. De selector kiest de registers; alleen de offset wordt gebruikt voor de vertaling binnen het segment. Het resulterende fysieke adres hoeft het bitpatroon van de selector niet te behouden.

Herken de kosten van de splitsing

Een selector van twee bits maakt vier bereiken. Als 10 ongebruikt blijft, is een kwart van het virtuele bereik van 16 KB niet beschikbaar. Geen segment kan groter worden dan zijn bereik van 4 KB, alleen doordat meer fysiek geheugen vrijkomt. Andere ontwerpen kunnen een andere splitsing gebruiken; als code en heap worden gecombineerd in één segment, kan één selectorbit dat segment van de stack onderscheiden.

Laat in plaats daarvan het type toegang kiezen

In een impliciet ontwerp gebruikt het ophalen van instructies het codesegment, omdat het adres uit de programmateller komt. Verwijzingen via de stackpointer of framepointer gebruiken het stacksegment. Andere toegangen gebruiken in dit vereenvoudigde model het heapsegment.

De stack groeit naar lagere adressen. Voor de vertaling zijn naast een basis en grootte ook een richtingsbit nodig. In dit model staat 1 voor groei omhoog en 0 voor groei omlaag. Toegangsrechten vormen nog een onafhankelijke controle: een byte kan binnen de grenzen liggen terwijl de gevraagde bewerking toch verboden is.

Behandel de stackbasis als bovengrens

Bij een segment dat omhoog groeit, duidt de basis de eerste fysieke byte aan. Bij een segment dat omlaag groeit, duidt de basis de grens direct boven de hoogste fysieke byte aan. In de doorlopende indeling omvatten stackbasis 53.248 en grootte 2.048 de fysieke bytes 51.200 tot en met 53.247.

Voor het stackbereik van 4 KB dat door 11 wordt geselecteerd, zet je het offsetveld van twaalf bits om in een negatieve verplaatsing:

Het veld loopt van 0 tot en met 4.095, dus deze verplaatsing is altijd negatief. Ze is geldig als haar absolute waarde niet groter is dan de huidige stackgrootte. Tel daarna de verplaatsing met teken bij de basis op.

Werk een toegestane stacktoegang uit

Virtueel adres 15.500 selecteert de stack. Het bereik begint virtueel op 12.288, dus het offsetveld is 3.212. Zet het veld om:

De diepte 884 valt binnen grootte 2.048. De vertaling geeft:

Als je de positieve waarde 3.212 bij de basis optelt, wijs je boven de stack. Het veld is nog niet de verplaatsing die voor een segment nodig is dat omlaag groeit.

Virtueel adres 13.000 geeft daarentegen veld 712 en verplaatsing −3.384. De diepte is groter dan 2.048, dus veroorzaakt de hardware een exceptie. Als het besturingssysteem de stack met succes laat groeien, kunnen door de grotere omvang meer lage adressen geldig worden.

Neem het onderste eindpunt mee

Een verplaatsing van −2.048 bereikt de laagste byte van de stack, 51.200, en is toegestaan. Een verplaatsing van −2.049 ligt erbuiten. De controle voor een segment dat omlaag groeit, staat dus ook een absolute waarde toe die gelijk is aan de grootte. Dit komt overeen met het aantal bytes bij de regel voor groei omhoog, hoewel die een offset gelijk aan de grootte uitsluit: de basis bij groei omhoog is een byte, terwijl de basis bij groei omlaag een eindgrens is.

Controleer de gevraagde bewerking

Beschermingsbits leggen lees-, schrijf- en uitvoerrechten vast. Code heeft doorgaans lees- en uitvoerrecht; heap en stack hebben doorgaans lees- en schrijfrecht. Schrijven naar code met lees- en uitvoerrecht veroorzaakt een exceptie, ook als de offset geldig is. Data uitvoeren veroorzaakt ook een exceptie als uitvoerrecht ontbreekt.

Alleen-lezen-code kan worden gedeeld. Het besturingssysteem kan de codesegmenten van twee processen naar hetzelfde fysieke gebied laten wijzen en schrijven voor beide verbieden. De instructiebytes nemen één fysieke kopie in, terwijl elk proces een afzonderlijke heap en stack houdt.

Segmentatie vervangt één groot gebied door meerdere kleinere gebieden. Daardoor is geen fysiek geheugen nodig voor lege virtuele gaten, maar moet het besturingssysteem nu gebieden van verschillende grootte plaatsen en laten groeien terwijl het de vertaaltoestand van elk proces behoudt.

Sla elk onderdeel van de koppeling op

Bij een contextwisseling zijn basis en grootte alleen niet meer voldoende. Het besturingssysteem slaat de basis, grootte, groeirichting en toegangsrechten van elk segment op en herstelt die. Een stack met de verkeerde richting of code met de verkeerde toegangsrechten herstellen zou de betekenis van verder identieke adressen veranderen.

Als een allocator meer heapruimte nodig heeft, moet het besturingssysteem het fysieke heapsegment uitbreiden. Vrije bytes direct erboven maken directe groei mogelijk. Anders kan het besturingssysteem het segment naar een geschikt groter gat verplaatsen en de basis bijwerken. Als het geen geschikt gebied kan verkrijgen, mislukt de groei.

Kies de granulariteit

Multics gebruikte fijnmazige segmentatie. Meer segmenten maken kleinere beheereenheden mogelijk, maar vereisen meer vertaalmetadata en beheer.

Zoek een voldoende groot gat

Fysieke segmenten van verschillende grootte laten vrije gaten van verschillende grootte achter wanneer processen starten, groeien en eindigen. Externe fragmentatie ontstaat wanneer in totaal genoeg bytes vrij zijn, maar geen afzonderlijk gat het aangevraagde segment kan bevatten.

Stel dat de vrije gaten 8 KB, 6 KB en 10 KB groot zijn. Samen is dat 24 KB. Een heapsegment van 12 KB past nog steeds niet: het grootste beschikbare gat is slechts 10 KB. De gaten op papier samenvoegen zorgt er niet voor dat hun fysieke adressen naast elkaar liggen.

Geheugencompactie kan deze indeling herstellen. Het besturingssysteem onderbreekt processen, kopieert segmenten naast elkaar en werkt hun bases bij. Virtuele adressen blijven werken omdat vertaling de fysieke verplaatsingen verborgen houdt. Het resultaat is een groot aaneengesloten vrij gebied, maar het kopiëren is kostbaar en nieuwe toewijzingen kunnen het geheugen opnieuw fragmenteren.

Plaatsingsbeleid zoals het eerste passende blok en het kleinst passende blok probeert ongunstige resten te beperken zonder te kopiëren. Geen plaatsingsbeleid voor blokken van verschillende grootte neemt externe fragmentatie voor elke reeks aanvragen weg. Ook kan één groot segment ruimte binnen zijn eigen omvang verspillen wanneer slechts verspreide delen worden gebruikt.

Herken het model in moderne systemen

Paginering verdeelt geheugen in stukken van vaste grootte en voorkomt dat elk logisch gebied één fysiek gat moet innemen. Het segmentatiemodel blijft nuttig om gebieden, bescherming en gedeeld gebruik te begrijpen. In de 64-bitsmodus van x86-64 gedragen de gewone segmentbases voor code, data en stack zich als nul en worden hun grenzen niet gecontroleerd; FS en GS behouden bruikbare bases voor gegevens per thread of per CPU. Een melding van ongeldige toegang die segmentatiefout heet, betekent niet dat het klassieke model met drie segmenten actief is.

Beheer van vrije ruimte registreert beschikbaar geheugen en kiest waar elke aanvraag terechtkomt. Voor even grote aanvragen kan een lijst van uitwisselbare blokken worden gebruikt. Verschillende groottes zijn moeilijker: zowel een heapallocator als een besturingssysteem dat segmenten plaatst, moet een aaneengesloten blok vinden dat groot genoeg is voor de volgende aanvraag.

Vind externe fragmentatie

Neem een gebied van 60 bytes met vrije bytes op 0–19, een toegewezen blok op 20–39 en vrije bytes op 40–59. Er zijn veertig bytes vrij, maar geen van beide vrije gaten kan een aanvraag van 25 bytes bevatten. Het nog toegewezen middelste blok verhindert dat die gaten als één gebied worden behandeld.

Dit is externe fragmentatie: er is capaciteit vrij buiten toegewezen blokken, maar door de indeling is die onbruikbaar voor een bepaalde aaneengesloten aanvraag. De vrije bytes zijn niet verdwenen. Ze kunnen nog steeds kleinere aanvragen bedienen of bruikbaar worden wanneer tussenliggende blokken worden vrijgegeven.

Vind interne fragmentatie

Een allocator die aanvragen afrondt op veelvouden van 16, geeft voor een aanvraag van 20 bytes een blok van 32 bytes. De 12 extra bytes zitten binnen een al uitgegeven toewijzing. Die verspilling is interne fragmentatie.

De ongebruikte ruimte tussen heap en stack binnen een plaats met een basis en een grens is een ander voorbeeld. Buddyallocatie veroorzaakt dezelfde soort verspilling wanneer die afrondt op machten van twee. Het beheerniveau verschilt, maar de plaats van de ongebruikte ruimte is het bepalende kenmerk.

Eén allocator kan van beide last hebben. Een aanvraag afronden kan bytes binnen het blok verspillen, terwijl elders andere vrije blokken gescheiden blijven.

Voeg vrije aangrenzende blokken samen zonder gebruikte data te verplaatsen

Samenvoegen van aangrenzende vrije blokken verenigt fysiek aangrenzende vrije blokken. Als het middelste blok in het gebied van 60 bytes wordt vrijgegeven, kunnen alle drie de stukken één gat van 60 bytes vormen. Als het middelste blok toegewezen blijft, kan het samenvoegen niet over dat blok heen gaan. Samenvoegen vermindert externe fragmentatie, maar garandeert niet voor elke aanvraag een voldoende groot gat.

Meer geheugen aan een heap toevoegen kan de druk verlichten, maar verandert de adressen van bestaande toegewezen blokken niet. Hun plaatsing kan nog steeds onbruikbare kleine gaten achterlaten.

Leg uit waarom het besturingssysteem segmenten kan comprimeren

Het besturingssysteem kan fysieke segmenten kopiëren en hun bases bijwerken. Programma's behouden virtuele adressen, zodat de koppeling die verplaatsingen kan verbergen. Een algemene heapallocator voor C mist een vertaallaag tussen teruggegeven pointers en locaties binnen de heap. Een programma kan een pointer naar veel objecten hebben gekopieerd en de allocator kan niet elke kopie vinden en herschrijven.

Als de allocator zelfstandig een toegewezen heapblok zou verplaatsen, zouden die pointers nog naar de oude locatie wijzen. Daarom houdt gewoon malloc-beheer toegewezen blokken op hun teruggegeven adres totdat ze worden vrijgegeven. Het moet fragmentatie beheersen door plaatsing, hergebruik en het opsplitsen en samenvoegen van vrije ruimte.

Een vrijelijst registreert vrije blokken op adres en grootte. Bij toewijzing wordt een blok opgesplitst of van de lijst verwijderd; bij vrijgave keert een blok terug en wordt het mogelijk met aangrenzende blokken samengevoegd. De grootteconventie is van belang: een geregistreerde grootte kan de bruikbare gegevensruimte betekenen of het hele blok inclusief metadata.

Splits eenvoudige bereiken op en voeg ze samen

Laat headers eerst buiten beschouwing. In een gebied van 60 bytes met vrije vermeldingen (0, 20) en (40, 20) geeft een aanvraag van 8 bytes die aan het begin wordt geplaatst adres 0 terug. De resterende vermeldingen zijn (8, 12) en (40, 20).

Begin opnieuw met de oorspronkelijke indeling en geef de middelste toegewezen bytes 20–39 vrij. Zonder samenvoegen kunnen de drie vermeldingen van 20 bytes afzonderlijk nog steeds geen aanvraag van 30 bytes afhandelen. Door aangrenzende bereiken samen te voegen ontstaat (0, 60), dat wel groot genoeg is. Adresvolgorde helpt de allocator aangrenzende blokken te herkennen; naast elkaar op de lijst staan is op zichzelf niet voldoende, tenzij hun fysieke bereiken elkaar raken.

Vind de header via de gebruikerspointer

free(ptr) ontvangt geen grootte. Een eenvoudige allocator slaat direct vóór de bruikbare gegevensruimte een header met de grootte op, soms met een controlewaarde of herkenningsgetal. Door de headerlengte af te trekken vind je de metadata.

Met een header van 16 bytes neemt een aanvraag van 96 bytes in totaal 112 bytes in. Het programma ontvangt een pointer 16 bytes na het begin van het blok. Bij vrijgave komt het hele bereik van 112 bytes, inclusief header, terug voor toekomstig beheer. Uitlijning kan extra afronding toevoegen; de groottes in dit voorbeeld voldoen al aan uitlijning op 16 bytes.

Volg een ingebedde vrijelijst

Stel dat een heap van 4.096 bytes begint op 32.768. Een vrije knoop gebruikt 16 bytes en registreert bruikbare bytes na de knoop. Aanvankelijk registreert die 4.080 bruikbare bytes.

Drie aanvragen van 96 bytes verbruiken elk 112 bytes:

De resterende vrije knoop begint op 33.104. De bruikbare grootte is 3.744 bytes. De telling is:

Bij vrijgave van pointer 32.896 wordt de header op 32.880 gevonden. Dat blok wordt een vrije knoop met 96 bruikbare bytes. Het kan niet met de laatste knoop op 33.104 worden samengevoegd, omdat de derde toewijzing ertussen ligt. Wanneer alle drie de toewijzingen zijn vrijgegeven en samengevoegd, beschrijft één knoop weer 4.080 bruikbare bytes. Door de oude headers in het midden op te nemen, komen hun bytes beschikbaar binnen het samengevoegde bereik.

Houd de administratie binnen het beheerde gebied

Ingebedde lijstknopen staan in het vrije geheugen zelf, dus voor het beheer van de lijst is geen afzonderlijke toewijzing voor elke vermelding nodig. De knoop bevat een grootte en een verwijzing naar het volgende vrije blok. Als geen blok past, kan de allocator met sbrk of mmap meer geheugen aanvragen; als niet genoeg geheugen kan worden verkregen, leidt dat tot NULL.

Een overloop kan een aangrenzende header of knoop overschrijven. Dat verklaart waarom de zichtbare fout kan optreden tijdens een latere malloc of free, na de schrijfbewerking die de lijst beschadigde.

Plaatsingsbeleid kiest tussen blokken die groot genoeg zijn voor een aanvraag. Verschillende keuzes laten verschillende gaten achter voor toekomstige aanvragen. Naast fragmentatie is de zoektijd van belang en geen beleid wint voor elke werklast.

Vergelijk de zoekregels

Voor het kleinst en grootst passende blok is bij een gewone ongesorteerde lijst een volledige zoekactie nodig. Andere structuren kunnen sneller geschikte groottes vinden. Het eerste passende blok is het eerste in de gekozen lijstvolgorde; dat hoeft niet het laagste adres te zijn, tenzij de lijst op adres is gesorteerd.

Volg de eerste aanvraag

Neem vrije blokken van 30, 12, 50 en 20 bytes in adresvolgorde. Laat headers buiten beschouwing en neem aan dat opsplitsen elke rest kan behouden. Een aanvraag van 18 bytes verandert de lijst als volgt:

• Het kleinst passende blok gebruikt 20 en laat 30, 12, 50, 2 over.
• Het grootst passende blok gebruikt 50 en laat 30, 12, 32, 20 over.
• Het eerste passende blok gebruikt 30 en laat 12, 12, 50, 20 over.
• Het volgende passende blok begint bij het vierde blok, gebruikt 20 en laat 30, 12, 50, 2 over.

Voor het volgende passende blok is een startpositie nodig om de keuze te bepalen. De naam alleen betekent niet dat bij de eerste vermelding van de lijst wordt begonnen. Bij het volgen van aanvragen moet je die zoektoestand tussen aanvragen bewaren.

Zie waarom de volgende aanvraag het oordeel verandert

Een volgende aanvraag vraagt om 45 bytes. Het kleinst passende blok en het eerste passende blok hebben beide het blok van 50 bytes behouden, dus slagen beide. Bij het grootst passende blok is het grootste resterende blok 32 bytes, dus mislukt de aanvraag ondanks 94 vrije bytes in totaal:

Deze mislukking is externe fragmentatie. De eerdere beslissing heeft het enige voldoende grote gat opgesplitst. Omgekeerd liet het kleinst passende blok een snipper van 2 bytes achter die mogelijk te klein is voor bruikbare toekomstige aanvragen. Een directe kleine rest bewijst niet dat beleid over de hele reeks aanvragen goed met ruimte omgaat.

Weeg beleid en gegevensstructuur af

Duizenden vermeldingen doorzoeken kan kostbaar zijn, ook als elke plaatsing goed is. Praktische allocators groeperen blokken op grootte of gebruiken doorzoekbare structuren zoals gebalanceerde bomen. Een lijst op adresvolgorde ondersteunt ook het samenvoegen, doordat fysiek aangrenzende blokken gemakkelijker te vinden zijn.

Het toewijzingsmechanisme: zoeken, opsplitsen en metadata bijwerken, kan gelijk blijven terwijl het beleid verandert. Om beleid eerlijk te vergelijken, volg je dezelfde aanvragen en vrijgaven, houd je de regels voor overhead gelijk en houd je rekening met zowel de ontstane gaten als de hoeveelheid zoekwerk.

Algemeen zoeken in een vrijelijst is flexibel, maar kan kostbaar zijn. Gespecialiseerde allocators maken veelvoorkomende aanvragen voorspelbaar door groottes te groeperen, herbruikbare objecten te behouden of blokgroottes te beperken tot machten van twee.

Hergebruik veelvoorkomende groottes en geïnitialiseerde objecten

Gescheiden vrijelijsten houden afzonderlijke vrijelijsten bij voor veelvoorkomende groottes, met een algemene allocator voor andere aanvragen. Een veelvoorkomende grootte kan rechtstreeks een blok uit de bijbehorende lijst krijgen. Even grote blokken veroorzaken onderling geen externe fragmentatie, maar de verdeling van capaciteit over lijsten is een beleidskeuze: vrije blokken van de ene grootte zijn mogelijk niet bruikbaar voor een andere grootte.

Een slaballocator houdt een objectcache bij voor een terugkerend type kernelobject, zoals een inode, vergrendeling of procesdescriptor. Een slab is verdeeld in objecten van dat type. De cache verkrijgt zo nodig meer slabs en kan een volledig vrije slab aan een algemene allocator teruggeven. Jeff Bonwick ontwierp deze aanpak voor Solaris.

De cache houdt vrijgegeven objecten in een geïnitialiseerde toestand, zodat herhaald instellen en vernietigen wordt vermeden. Dat bespaart naast het zoeken zelf ook tijd.

Splits een buddygebied

Een binaire buddyallocator begint met een gebied waarvan de grootte een macht van twee is en rondt elke aanvraag af op een blokgrootte die een macht van twee is. De allocator splitst een vrij blok herhaaldelijk in gelijke helften totdat een helft precies groot genoeg is. De twee helften van één splitsing zijn partnerblokken.

Rond voor een aanvraag van 5 KB in een gebied van 64 KB 5 KB af op 8 KB. Splits 64 in twee blokken van 32 KB, vervolgens de gekozen 32 in twee blokken van 16 KB en daarna de gekozen 16 in twee blokken van 8 KB. Als het eerste blok van 8 KB wordt teruggegeven, blijven vrije partnerblokken over op offsets 8 KB, 16 KB en 32 KB, met respectievelijk groottes van 8 KB, 16 KB en 32 KB.

De toewijzing verspilt 3 KB binnen haar blok van 8 KB. Dit is interne fragmentatie, die wordt geaccepteerd in ruil voor regelmatig opsplitsen en samenvoegen.

Vind de enige toegestane samenvoegpartner

Met offsets gemeten vanaf het begin van het beheerde gebied:

De exclusieve of keert de bit om die overeenkomt met de blokgrootte. Voor een blok van 8 KB op offset 0 ligt het partnerblok op offset 8.192. Voor een blok van 16 KB op offset 16.384 ligt het partnerblok op 0.

Wanneer het eerste blok van 8 KB wordt vrijgegeven, wordt het samengevoegd met zijn vrije partnerblok van 8 KB. Het resulterende blok van 16 KB kan met zijn vrije partnerblok worden samengevoegd, waarna het resulterende blok van 32 KB opnieuw kan worden samengevoegd. Het samenvoegen stopt als het vereiste even grote partnerblok in gebruik is. Aangrenzend en vrij zijn is niet voldoende als twee blokken geen partnerblokken van dezelfde splitsing zijn.

Een aanvraag van 20 KB krijgt 32 KB, waardoor 12 KB, oftewel 37,5% van het blok, wordt verspild. Linux combineert buddyallocatie van fysiek geheugen met objectcaches volgens het slabprincipe. Allocators voor meerdere threads gebruiken ook lokale caches of meerdere arena's om minder te hoeven wachten op één gedeelde toewijzingsvergrendeling; glibc, jemalloc en tcmalloc gebruiken varianten van deze ideeën.