Physical memory manager

Wat doet een physical memory manager?

De pmm houdt een overzicht bij welke pages vrij zijn. Een page is een aaneensluitend blok geheugen van precies 4kb (4096 bytes) groot. Het adres van zo'n page heeft als laatste 12 bits 0. De adressen overlappen elkaar dan ook niet. In de loop van de tijd zijn er steeds meer manieren bedacht om bij te houden welke pages vrij zijn en welke niet. Het kan handig zijn om een onderscheid te maken tussen de adressen onder 16mb en de adressen daarboven. Voor dma is het noodzakelijk dat de adressen uit de eerste 16mb van het fysieke geheugen komen.Je kunt bijvoorbeeld voor de adressen onder 16mb een bitmap gebruiken en voor de adressen daarboven een stack. Ik zal hierna een paar van die manieren uitleggen en aan het eind een overzicht van de voor en nadelen geven.

Bitmap

De meest simpele manier om dit overzicht te houden is voor elke page in het fysieke geheugen 1 bit op 1 in te stellen als de page bezet is en op 0 te zetten als deze 4kb vrij zijn. Voor een computer met 1gb aan geheugen neemt een bitmap 8kb (twee pages) in beslag. Het dealloceren van een page is erg gemakkelijk: je moet gewoon het bijbehorende bitje op 0 instellen. Het alloceren kan echter wat meer tijd kosten omdat je de hele bitmap moet doorzoeken op zoek naar een bitje die op 0 staat. Gelukkig kan dit met 32 bits tegelijk. Een mogelijke uitbreiding hierop kan zijn dat je het adres bijhoudt waar je tijdens het zoeken in de bitmap gebleven bent. De volgende keer kun je zo makkelijk weer verdergaan waar je gebleven was met zoeken. Een andere variatie hierop kan zijn dat je verschillende lagen bitmaps hebt. Je maakt een aantal bitmaps voor bijvoorbeeld 32mb elk, en dan nog een bitmap die aangeeft in welke van die bitmaps nog vrije pages zitten. Als er nu een stuk van 32mb niet meer vrij is, hoef je daar in ieder geval niet meer in te zoeken.

Stack

De naam van dit algoritme zegt het eigenlijk al: we houden gewoon een stack bij met de adressen van de vrije pages. Als we nu een vrije page moeten aanleveren poppen we gewoon een adres van de stack en als er weer een page vrij gemaakt wordt pushen we dat adres weer op de stack. Een groot nadeel van een stack is dat het erg lastig is om een reeks adressen achter elkaar te verkrijgen. Hiervoor moet vaak de stack doorzocht worden en dat kost erg veel tijd.

Buddy Allocation System

Dit is het algoritme dat de linux kernel gebruikt. Het is een stuk lastiger om te implementeren dan een bitmap of een stack, maar kan bij grote allocaties een stuk sneller zijn. De benodigte ruimte zit ergens tussen die van een bitmap en van een stack in, en de snelheid ook. Het is dus een mooi compromis. De totale vrije ruimte wordt opgedeelt in een aantal stukken van 16 pages, 8 pages, 2 pages en losse pages. Die blokken worden dan in meerdere linked lists (een voor elke grootte) bijgehouden. Als er nu om een losse page gevraagt wordt en de linked list voor losse pages is leeg, moet er eentje uit de linked list voor 2 pages gehaald worden en in twee stukken gehakt. Een wat geavanceerdere allocator zou ook de linked list kunnen doorzoeken als er verder niks te doen is en dan pages die naast elkaar passen aan elkaar plakken. Ook zou je de voor elke grootte twee linked list kunnen gebruiken: een voor adressen onder en een voor adressen boven 16mb.

Combinaties van deze systemen

Je zou ipv een stack een combinatie van een stack en een bitmap kunnen gebruiken: Je gebruikt een stack met bijvoorbeeld maximaal 20 pages erop en verder een bitmap. Je kunt dan de stack gebruiken om snel een vrij adres te vinden. Als er een adres vrijkomt en de stack is vol geef je dat aan in de bitmap. Als je een adres moet hebben en de stack is leeg doorzoek je de bitmap en vul je de stack.

Overzicht voor en nadelen

Hieronder geef ik een vergelijking tussen de eerste drie algoritmes. De nummer 1 is telkens de beste.
Snelheid (voor losse pages):

1. Stack
2. Buddy
3. Bitmap

Snelheid (meerdere pages achter elkaar), let op, meerdere pages achter elkaar in fysiek geheugen is bijna alleen nodig voor dma.

1. Buddy
2. Bitmap
3. Stack

Geheugengebruik:

1. Bitmap
2. Buddy
3. Stack