OS: Some solutions to exercise 5

Please note that these are suggested solutions. There can be other solutions that are also correct.

Uppgift 1

a) Vad innebär virtuellt minne?

Svar:

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.

b) Varför måste man ha stöd i hårdvaran när man använder virtuellt minne?

Svar:

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.

Uppgift 2

När man ska lagra de data som hör till en process kan det vara svårt att hitta ett tillräckligt stort, sammanhängande utrymme i det fysiska primärminnet. Hur löser man det problemet på vanliga moderna datorer och med vanliga moderna operativsystem som Linux och Windows?

Svar:

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.

Uppgift 3

Varför är sidstorlekar ("page size" på engelska) alltid jämna tvåpotenser? Visa med exempel!

Svar:

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 211, 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.

Uppgift 4

Här nedan använder jag B i betydelsen byte, K i betydelsen 210 = 1024, M i betydelsen 220 = 1048576, G i betydelsen 230 = 1073741824, och T i betydelsen 240 = 1099511627776. Ibland används i stället enhetsprefixen kibi ("kilo-binär"), mebi, gibi och tebi.

a) 4 byte

Svar:

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.

b) 1024 byte

Svar:

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.

c) 8192 byte

Svar:

Rimlig.

d) 8193 byte

Svar:

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.

e) 10000 byte

Svar:

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.

f) 1099511627776 byte (240 byte)

Svar:

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.)

Uppgift 5

Vi konstruerar en processor där fysiska adresser är 37 bitar, medan virtuella adresser är 33 bitar, varav 22 bitar är sidnummer ("page number" på engelska) och 11 bitar är offset.

a) Hur stor är en minnessida ("page")? Visa hur du räknat.

Svar:

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

b) Fysiska ramar ("frames") kommer att vara lika stora som minnessidorna. Förklara varför!

Svar:

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.

c) På den här processorn har fysiska adresser fler bitar än virtuella adresser. Är det något konstigt med det? Vad innebär det?

Svar:

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.

d) Hur mycket plats (i byte) tar page-tabellen för en process? Gör rimliga antaganden, redovisa dem, och förklara hur du räknat!

Svar:

Sidnummer är 22 bitar, dvs den virtuella minnesrymden består av 222 = 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).

e) Den virtuella minnessidan nummer 2 (binärt: 10) lagras i fysisk frame nummer 0 (binärt: 0). På vilken fysisk minnesplats finns den virtuella adressen 4097 (binärt 1000000000001)?

Svar:

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).

Uppgift 6

Om man läser om x86-arkitekturen, ser man att x86-processorer kan köras på flera olika sätt, i olika "moder":

En student (som eventuellt kan ha slarvat lite när hen läste OS-kursen) behöver hjälp med några frågor. Svara på dessa frågor, och red ut eventuella missförstånd!

a) "Hur fungerar page-tabellen i real mode? Är det en för varje process fortfarande, eller vad?"

Svar:

Det finns ingen page-tabell! Eftersom man använder de fysiska adresserna direkt, och inte virtuella adresser, behövs ingen översättning och ingen page-tabell.

b) "I vanliga fall brukar den virtuella minnesrymden vara större än det fysiska minnet, och data i den virtuella minnesrymden som inte får plats i det fysiska minnet pagas ut till disk. Men när man använder Physical Address Extension är fysiska adresser 36 bitar, medan virtuella är 32 bitar, så man kan ha mer fysiskt minne än virtuellt minne. Hur fungerar det med paging? Gör man tvärtom mot vanligt, så de data som inte får plats på disken pagas till RAM-minnet, eller vad?"

Svar:

Nej, om det sker någon paging av data som inte får plats så görs den som vanligt från primärminnet och ut till disk, SSD eller annat sekundärminne. Det är inget konstigt med det. Man kan ha flera olika processer med varsin virtuell adressrymd, och då kan man utnyttja mer fysiskt minne än vad en enda process kan ha. (Se även 5c ovan.)

c) "I long mode är virtuella adresser 48 bitar, så man kan ha 248 = 281474976710656 byte virtuellt minne, dvs mer än 200 terabyte, eller 200000 gigabyte. Men hur kan det fungera? Min dator har bara en disk på en enda terabyte, eller 1000 gigabyte, och även om man pagar ut data ur primärminnet till disken skulle det ju inte få plats!"

Svar:

Adressrymden anger hur många olika adresser som det är möjligt att ha. Bara för att det maximalt går att ha 248 = 281474976710656 adresser, behöver inte alla användas. De är inte, som det heter, "inmappade" i adressrymden. En process kanske, bara som ett exempel, lagrar sin körbara programkod i den första megabyten minne (adress 0-1048575), data i den andra megabyten (adress 1048576-2097151), och de resterande 99.999999 procenten av minnesrymden, dvs adress 2097151-281474976710655, används inte. Det minnet finns inte. Försöker programmet komma åt en adress där, får man ett avbrott.

Uppgift 7

Ju mindre storleken är på minnessidorna ("pages"), desto mer plats tar page-tabellen. Förklara varför!

Svar:

För en given storlek på den virtuella adressrymden blir den indelad i fler minnessidor ju mindre varje sida är, och därför behövs fler platser i page-tabellen. Dessutom behövs det också fler frames, så frame-numren kan vara större, och det går åt fler bitar för att lagra varje frame-nummer.

Uppgift 8

Vi konstruerar en processor där fysiska adresser är 20 bitar, medan virtuella adresser är 36 bitar, varav 23 bitar är sidnummer ("page number" på engelska) och 13 bitar är offset.

a) Hur mycket fysiskt minne kan man adressera? Visa också hur du räknat.

Svar:

220 = 1048576 byte, dvs 1 MB

b) Hur mycket virtuellt minne kan man adressera? Visa också hur du räknat.

Svar:

236 = 68719476736 byte, dvs 64 GB

c) Hur stora är minnessidorna? Visa också hur du räknat.

Svar:

213 = 8192 byte, dvs 8 KB

d) Hade det varit rimligt att ha en offsetdel som var 12 bitar i stället för 13? Motivera svaret.

Svar:

Ja. Då blir sidstorleken 4 KB, och det är mycket rimligt.

e) Hade det varit rimligt att ha en offset som var 3 bitar? Motivera svaret.

Svar:

Nej. Då blir sidstorleken 8 byte, och det är alldeles för litet. Se även uppgift 4a ovan.

f) Hade det varit rimligt att ha en offset som var 34 bitar? Motivera svaret.

Svar:

Nej. Då blir sidstorleken 234 = 16 GB, och det är alldeles för stort. Se även uppgift 4f ovan.

Uppgift 9

Vi har en byteadresserad dator som arbetar med minnesadresser på 16 bitar. Det finns alltså 216, dvs 65536, olika minnesadresser. Datorn har bara hälften så mycket fysiskt minne (32768 byte), som dessutom ska delas mellan de olika processerna. Med hjälp av virtuellt minne och så kallad "paging" kan varje process ändå ha tillgång till 65536 byte virtuellt minne.

a) Vi antar att en sida ("page") är 128 minnesadresser stor. Hur många bitar går det åt för att ange en minnesplats inom en sida ("offset")?

Svar:

7 bitar.

b) Hur många bitar går det åt för att ange sidnumret ("page number")?

Svar:

20 - 7 = 13 bitar.

c) Hur många olika sidor kan varje process ha?

Svar:

213 = 8192 virtuella sidor.

d) Hur många olika ramar ("frames") finns det i det fysiska minnet?

Svar:

32768 / 128 = 256 frames

e) Hur stor (i byte räknat) blir varje process sidtabell ("page table")? Redovisa hur du räknat!

Svar:

Om vi tänker oss en page-tabell i form av en array med 8192 platser, där varje plats innehåller ett 8-bitarstal som anger numret på en frame, blir tabellen 8192 byte stor, dvs 8 KB.

f) Förklara, med den beskrivna datorn som exempel, hur paging fungerar. Hur är det möjligt att en process kan ha mer minne än vad som finns? Och hur är det möjligt att flera processer var och en kan ha mer minne än vad som finns?

Svar:

...


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), May 14, 2024