OS: Exercise 5: Memory

You can do this exercise in any size group you wish. Don't worry if you find some of the questions difficult to answer, since they may be intended to initiate a discussion rather than have a single correct answer.

There might also be more questions than you have time to answer, but do as many as you can.

There are solutions to some of the questions, but try to solve them yourself first.

Preparations

Before this exercise, you should (ideally) have:

Watched (Swedish) video lectures 14-17 from the playlist.

Uppgift 1

a) Vad innebär virtuellt minne?

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

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?

Uppgift 3

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

Uppgift 4

Virtuellt minne brukar numera vara sidindelat, på engelska i "pages". Sidorna har en viss storlek. Vi ska utveckla en ny processorarkitektur för vanliga moderna datorer, och här är förslag på några sidstorlekar som man skulle kunna använda. Ange för var och en av dem om det är en rimlig storlek eller inte, och om det inte är en rimlig storlek så förklara (detaljerat) varför den inte är rimlig.

a) 4 byte
b) 1024 byte
c) 8192 byte
d) 8193 byte
e) 10000 byte
f) 1099511627776 byte (2⁴⁰ byte, dvs en tebibyte)

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.

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

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?

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!

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

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":

"Real mode", utan virtuellt minne, där processorn arbetar direkt mot det fysiska minnet, och minnesadresser bara är 20 bitar.
"Protected mode", som är den vanligaste 32-bitarsmoden, där man har virtuellt minne med både virtuella och fysiska adresser på 32 bitar.
Protected mode med "Physical Address Extension", som fungerar som protected mode, men fysiska adresser är på 36 bitar.
"Long mode", som är den vanligaste 64-bitarsmoden, där man har virtuellt minne med virtuella adresser på 48 bitar och fysiska adresser på 52 bitar. (Adresserna lagras normalt med 64 bitar, men det är alltså bara 48 respektive 52 som faktiskt används.)

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?"

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?"

c) "I long mode är virtuella adresser 48 bitar, så man kan ha 2⁴⁸ = 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!"

Uppgift 7

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

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.

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

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

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

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

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

Uppgift 9

Vi har en byteadresserad dator som arbetar med minnesadresser på 16 bitar. Det finns alltså 2¹⁶, 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")?

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

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

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

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

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?

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), May 16, 2022