Paging

Inleiding

Toen computers voor het eerst beschikbaar werden voor universiteiten en later ook voor thuisgebruikers, was geheugen duur (1 KB = EUR 400). Het was erg zeldzaam voor computer om veel geheugen te hebben, maar mensen wilden wel altijd grote programma's draaien.

In het begin gebeurde swappen nog handmatig: de programmeur verdeelde het programma in kleinere delen (overlays), die één voor één in het geheugen werden geladen en uitgevoerd. Dit was erg vermoeiend en mensen werden er gek van. Een groep uit Manchester bedacht een methode om het gehele proces te automatiseren: programma's kunnen geheugenlocaties aanroepen, ongeacht of ze bestaan of niet. Hierdoor is de grens van het geheugen niet meer de grootte van het fysieke geheugen, maar de grote van de harde schijf en het aantal adresbits. Omdat het geheugen wat aangeroepen wordt niet echt bestaat, heet het virtueel geheugen.

Swapping is een programma uit het geheugen halen en een ander programma er in laden. Dit kan zonder hardware-ondersteuning geimplementeerd worden door het besturingssysteem. Paging staat toe om je harde schijf te gebruiken alsof het geheugen is.

Implementatie

Om paging mogelijk te maken, worden het programma en de data (op de schijf) die in het geheugen moet worden geladen verdeeld in pagina's. Het geheugen wordt ook verdeeld in pagina's van dezelfde grootte (meestal enkele KiB's) en de pagina's die het eerst nodig zijn worden in het geheugen geladen. Het geheugen wordt helemaal vol gestopt. Wordt er op een gegeven moment verwezen naar een pagina die niet in het geheugen zit, dan wordt er een pagina weggegooid en de goede pagina er voor in de plaats gezet.

Er is bij paging een afweging wanneer je een pagina op de harde schijf schrijft en weg gooit uit het geheugen. Het is efficient om alle pagina's op de harde schijf te hebben, zodat je een pagina niet nog eens hoeft weg te schrijven voordat hij weggegooid moet worden. Dit bespaart tijd, maar als de swap-space (de harde-schijfruimte toegewezen aan het paging-proces) groot is, willen sommige besturingssystemen nogal eens het hele geheugen naar de schijf schrijven en vervolgens alle pagina's uit het geheugen verwijderen. De computer is daarna alleen maar bezig met pagina's laden en weer verwijderen, wat resulteert in trashing. Trashing is het proces waarbij de computer meer bezig is met paging dan met andere dingen doen. Er blijft geen tijd meer over voor de gewone programma's.

Vervanging van pagina's

Least Recently Used

Als er een page-fault is en het geheugen is vol, moet er een pagina uit het geheugen gehaald worden, eventueel na weggeschreven te zijn naar de harde schijf. LRU gooit de pagina eruit die het langst geleden gebruikt is. Het is niet waarschijnlijk dat deze pagina tot de verzameling pagina's van het huidige programma behoort. Passen niet alle pagina's van een programma in het geheugen, dan kan dit systeem echter tot trashing leiden, waar steeds pagina's moeten worden geladen die er nog maar pas zijn uit gegooid.

First-In First-Out

FIFO verwijdert de pagina die het langst geleden geladen is (in tegenstelling tot LRU, die de pagina weggooit die het langst geleden gebruikt is).

First non-dirty

Een hele simpele methode om de pagina te kiezen die er uit moet is de eerste pagina te pakken die niet dirty is. Pagina's met het dirty bit geset moeten eerst naar de harde schijf teruggeschreven worden alvorens te kunnen worden verwijderd. Dit kost veel tijd, waardoor dit systeem een tijdsbesparende oplossing is. Het moet echter in combinatie met een ander systeem gebruikt worden, anders is er op een gegeven moment maar één pagina niet-dirty en wordt deze de hele tijd vervangen.

Vervanging van pagina's in Linux

Linux maakt gebruik van Least Recently Used: de pagina die het langst niet is gebruikt wordt uit het geheugen gegooid. Verder wordt er eerder geswapt als de hoeveelheid vrij geheugen afneemt. Dit schema kan nog steeds tot trashing leiden, als er sneller pagina's nodig zijn dan dat ze weggeschreven kunnen worden.

Linux swap spaces

In linux kan een swapspace zowel in een partitie als een bestand gestopt worden. Een partitie is beter, omdat er dan geen filesystem-overhead plaats vind. Een bestand maak je echter sneller aan dan een partitie en is dynamischer. Zowel het bestand als de partitie moeten een vaste grootte hebben en kunnen niet van omvang veranderen zodra ze als swap in gebruik genomen zijn.

Net zoals alle andere partities staan swap partities gewoon in \etc\fstab.

Er zijn twee versies swapspace. Het verschil hiertussen wordt aangegeven door de laatste 10 bytes van de eerste pagina: SWAP_SPACE of SWAPSPACE2.

Versie 1: SWAP_SPACE

De eerste pagina van deze swapspace is een bitmap: er staat een 1 voor elke bruikbare pagina en een 0 voor elke onbruikbare pagina. Alle pagina's moeten een bit in de eerste pagina hebben, waardoor er een maximum is aan het aantal pagina's: 8*(S-10)-1, waar S de grootte is van de pagina's in bytes. Met S=4096 (i386) zijn er dus maximaal 32687 pagina's mogelijk, wat een maximum swapgrootte oplevert van bijna 128 MiB. Met S=8192 (sparc64, alpha) zijn er maximaal 65455 pagina's, een maximum swapgrootte van bijna 512 MiB. Is de swappartitie groter, dan wordt de overbodige ruimte niet gebruikt.

Versie 2: SWAPSPACE2

De oude partitieindeling liet de eerste pagina voor het grootste deel verloren gaan en werkte omslachtig, want deze was gevuld met allemaal enen tot het einde van de partitie, vervolgens allemaal nullen. Een betere manier is om de grootte van de swapspace aan te geven met een integer en onbruikbare delen (bad-blocks op de harde schijf) gewoon op te schrijven. Dit gebruikt het nieuwe swapsysteem. Dit vergrootte de maximale beschikbare ruimte tot 512MiB op een MIPS tot 3TiB op een sparc64.

Sinds linux versie 2.1.117 gebruikt de kernel 2 bytes per swappagina aan geheugen, dus om een swap van 2 GiB te hebben met een paginagrootte van 2KiB, heb je 2 MiB aan kernelgeheugen nodig.

Op dit moment kunnen er maximaal 8 verschillende swap bestanden of partities zijn. Alle swap locaties staan in /proc/swaps (vanaf linux 2.1.25), met de grootte, hoeveel er in gebruik is en wat de prioriteit is.

Een swap-bestand mag niet gefragmenteerd zijn, en moet aangemaakt worden voordat het tot een swapindeling gezegend mag worden. Een leeg bestand aanmaken zonder gaten erin kan met dd.

Het nut van paging

Paging is alleen nuttig als een bepaalde vorm van opslag veel groter dan het geheugen (zoals een harde schijf) veel goedkoper is dan het geheugen zelf. Paging stelt je dan in staat het goedkope opslagmiddel te gebruiken om een groter geheugen te realiseren.

Harde schijven zijn goedkoper geworden, maar geheugen is nog veel goedkoper geworden. Een systeem met een paar gigabyte aan geheugen is betaalbaar, en paging is dan niet nuttig meer.

Paging is traag, sloom, langzaam en het vreet CPU tijd. Het was een noodzaak in de tijd dat er echt niet meer dan 64 KiB geheugen in je computer kon en je toch grote programma's wilde draaien, maar tegenwoordig wegen de nadelen niet meer op tegen de voordelen. Je computer wordt langzamer van paging, terwijl je het extra geheugen waarschijnlijk niet nodig hebt.

De toekomst van paging

Paging kan echter nog wel gebruikt worden voor erg grote programma's, zoals grafische applicaties. Verder wordt paging misschien ooit weer interessant als we naar een ander soort geheugen overstappen. Snel geheugen is nog erg duur, maar er zal een dag komen dat je gewone geheugen vervangen wordt door een soort geheugen wat tien maal sneller is. Zolang dat nog duur is, kan paging een uitkomst bieden.

Paging kan ook gebruikt worden in geintegreerde computers, in auto's, wasmachines, etc. Daar is misschien geen harde schijf aanwezig, maar wellicht wel snel en minder snel geheugen (RAM en Flash, bijvoorbeeld).

Bronnen

Meer informatie:

Einde