OS: Some solutions to exercise 5

Varje process som körs har sin egen adressrymd, så kallade virtuella adresser, som måste översättas till fysiska adresser för att avgöra var i det fysiska minnet som processens data verkligen är lagrade. Det kan vara en enkel översättning, till exempel att man lägger till en konstant, eller en mer komplicerad översättning med tabelluppslagning.

När man talar om virtuellt minne menar man ofta att hela eller delar av processens minnesinnehåll kan flyttas till sekundärminne, så kallad "swapping" eller "paging". Det är något som underlättas av virtuellt minne, men det är inte det som är virtuellt minne. Virtuellt minne innebär bara just detta att man har virtuella minnesadresser, som måste översättas till fysiska adresser för att hitta var minnesinnehållet faktiskt finns lagrat.

Annars blir det för långsamt. Om översättningen gjordes i mjukvara skulle det behövas minst en maskininstruktion för att räkna ut den fysiska adressen, och kanske många fler om det är en komplicerad översättningsmetod eller om minnesgränser ska kontrolleras. Om man dessutom använder en tabell (som inte är mycket liten) för översättningen kommer den att behöva lagras i primärminne, och då behövs minst en minnesåtkomst för varje översättning. Det skulle fördubbla belastningen på primärminnet, eftersom varje minnesåtkomst nu kräver två minnesåtkomster.

Man allokerar inte sammanhängande fysiskt minne, utan använder en virtuell minnesrymd som delas in i lika stora "sidor" (på engelska "pages"), exempelvis med storleken fyra kilobyte. Det fysiska minnet delas in i "frames" (på svenska kanske "ramar"), med samma storlek som sidorna, och en sida kan sedan placeras i vilken ledig frame som helst. Processens sidor behöver inte lagras sammanhängande eller i ordning. "Sidtabellen" (på engelska "page table") översätter mellan sidnummer och ramnummer, dvs mellan virtuella och fysiska adresser.

Man kombinerar ofta detta med "paging", som innebär att en sidas innehåll kan flyttas till sekundärminne om det inte används just då. Då kan man frigöra plats i det fysiska primärminnet, för innehåll som faktiskt ska användas. Det gör att en process kan använda mer minne än vad som fysiskt finns, och det underlättar att hitta lediga frames, men det som löser problemet med att hitta ett tillräckligt stort, sammanhängande utrymme är den sidindelade virtuella adressrymden, inte att minnesinnehåll sparas på sekundärminne.

För att effektivt (dvs snabbt och utan stora mängder hårdvara) kunna dela upp den virtuella minnesadressen i sidnummer (på engelska "page number") och offset inom sidan. Den uppdelningen behövs för att göra översättningen från virtuell adress till fysisk adress.

Om sidstorleken exempelvis är 2¹¹, dvs 2048, är de 11 lägsta bitarna offset i den virtuella adressen offset inom sidan, och de övriga, högre bitarna sidnummer. Dessa högre bitar kan skickas direkt till uppslagningen i sidtabellen, utan att några matematiska operationer behöver utföras. (Man behöver bara dra sladdarna med bitarna i till rätt plats!), Uppslagningen ger ett ramnummer (på engelska "frame number") i det fysiska minnet. Bitarna i ramnumret kombineras med offset-bitarna till en fysisk minnesadress.

Om vi också antar att både det virtuella och det fysiska minne arbetar med 33-bitarsadresser, kan vi titta på översättningen av den virtuella adressen 7645000999 (decimalt). 7645000999 decimalt = 111000111101011010111010100100111 binärt, som består av sidadressen 1110001111010110101110 binärt (3732910 decimalt) och offset 10100100111 binärt (1319 decimalt).

Vi antar att sidan 3732910 är lagrad i frame 65536 decimalt (0000010000000000000000 binärt). Uppslagningen i sidtabellen ger alltså framenummer 65536 decimalt (0000010000000000000000 binärt), och vi kombinerar framenummer 0000010000000000000000 binärt med offset 10100100111 binärt till den fysiska adressen 000001000000000000000010100100111 binärt = 134219047 decimalt.

Orimligt liten. Vi skulle visserligen få mindre intern fragmentering (under vissa förutsättningar i genomsnitt 1,5 byte per sammanhängande virtuellt minnesutrymme), men det skulle bli mycket ineffektivt att skyffla runt tusentals eller miljoner små minnessidor i varje process. Pagetabellen skulle också bli mycket stor. Åtminstone krävs en plats i pagetabellen för varje page som finns inläst i en frame i det fysiska minnet, och om vi antar att datorn har 16 GB minne blir det 4 G frames, vilket kräver 4 G stycken platser i pagetabellen om alla fysiska frames används för virtuella minnessidor. 4 G olika frames kräver framenummer på 32 bitar, dvs 4 byte. Alltså går hela primärminnet på 16 GB åt enbart för att lagra framenumren i pagetabellen (eller de olika pagetabellerna, om man har flera virtuella minnesrymder). Man kan minska pagetabellens storlek genom att slå ihop flera av dessa 4-bytessidor och hantera dem gemensamt, men då har vi i praktiken ändrat till en större pagestorlek. Så små minnessidor skulle också fungera dåligt med processorns minnescache, eftersom minnesinnehållet skulle vara så utspritt i minnet att en cache-line innehåller flera helt olika sidor, som kan innehålla helt skilda data. I stället för att exempelvis en 16 byte stor struct (oftast) ligger i en enda minnessida och en enda cache-line, ligger den nu i fyra olika sidor och fyra olika cache-lines, tillsammans med en massa andra data. Cachen kommer att innehålla en massa förmodligen ointressanta data, och det går åt fyra cache-lines i stället för en. Eftersom minnet blir uppdelat i väldigt många minnessidor, behövs också en orimligt stor TLB.

Rimlig. Kanske lite liten för en vanlig modern persondator, i synnerhet om det är den enda sidstorleken som processorn stöder. Redan 32-bitars Pentium-processorer arbetade med två olika sidstorlekar, 4 KB och 4 MB.

Rimlig.

Inte rimlig. Inte en jämn tvåpotens, och därför blir adressöversättningen komplicerad och långsam. I stället för att pagenummer är de högre värda bitarna i adressen, och de lägre värda bitarna är offset inom sidan, så att det bara är att "dra ledningsbanorna till rätt ställe på chipet", måste vi implementera division. Dagens vanliga datorer har primärminnesstorlekar som är (summor av) tvåpotenser, till exempel 16 GB och 24 GB, och det skulle inte gå att fylla upp hela minnet med 8193-bytessidor.

Inte rimlig, av samma skäl som ovan. Man skulle förstås kunna tänka sig en dator som arbetar med basen 10 i stället för binära tal, till exempel genom att en ledning inte bara kan ha två olika spänningsnivåer som representerar 0 och 1, utan tio olika. Eller att varje siffra representeras av tio olika radiorör, för värdena 0-9, som i ENIAC. I en dator med decimala adresser skulle 10000 vara en mycket rimlig storlek.

Orimligt stor. Detta är en terabyte minne, och mer än vad som totalt finns i hela datorn, utom de allra största servrarna. (Lenovo ThinkSystem SR950 kan ha upp till 24 terabyte minne.) Även om datorn har så mycket minne skulle det ge mycket stor intern fragmentering, utom för väldigt specialiserade tillämpningar, och vara helt opraktiskt. En vanlig, stor hårddisk eller SSD är på 1-10 terabyte, så en normal swap-partition på en enda sekundärminnesenhet skulle bara ha plats för några få minnessidor. Paging skulle bli oerhört långsam om man ska flytta runt så stora sidor. (Att läsa 1 TB data tar flera minuter, även från de snabbaste SSD:er jag provkört.)

2048 minnesplatser. Med 11 bitar kan man lagra 2¹¹ = 2048 olika binära tal, så det är så många olika minnesplatser man kan adressera inom en minnessida.

Innehållet på en minnessida (page) är egentligen data, och man lagrar den i en ram (frame). Därför bör de vara lika stora. Minessidan måste förstås få plats i ramen, så ramen måste vara minst lika stor som sidan, och det finns ingen anledning att göra ramen större än minnessidan, för då blir det bara oanvänd plats i den.

Det är inget konstigt, men ovanligt numera på vanliga datorer, och innebär att det fysiska minnet kan vara större än det virtuella minnet. Om man utnyttjar hela den fysiska adressrymden, dvs datorn är bestyckad med så mycket fysiskt minne som går med hänsyn till de fysiska adresserna, så kan upp till 16 olika processer som utnyttjar hela sin virtuella minnesrymd vara inladdade i fysiskt minne samtidigt.

Sidnummer är 22 bitar, dvs den virtuella minnesrymden består av 2²² = 4194304 minnessidor (pages). Det behövs alltså, om man inte använder några trick för att "klumpa ihop" en del av minnessidorna till större, 4194304 platser i page-tabellen. Hur många olika ramar (frames) finns i datorn? När man tar bort offseten på 11 bitar från den fysiska adressens 37 bitar, återstår 26 bitar för ramnumret. Vi behöver minst 26 bitar för att lagra ett ramnummer, och för att det åtminstone ska bli hela 8-bitarsbytes använder vi 32 bitar, dvs 4 byte. Alltså tar hela page-tabellen 4 * 4194304 byte, dvs 16777216 byte (16 megabyte).

1

Den virtuella adressen är uppdelad i de 11 lägsta bitarna som är offset, och resten av bitarna som är sidnummer, dvs (binärt) 10 och 00000000001. Sidnumret 10 binärt motsvarar 2 decimalt, och minnessida 2 (decimalt) lagrades ju i frame 0 (decimalt). 0 (decimalt) = 0 (binärt). Den fysiska adressen blir alltså (binärt) 0 sammanfogat med 00000000001, dvs 000000000001 (binärt) = 1 (binärt) = 1 (decimalt).