COMP 3430 Operating Systems – Chapter 18 and 20 reading notes
Winter 2022
About these reading notes
Chapter 18: Paging: Introduction
Copyright By PowCoder代写 加微信 powcoder
18.1Asimpleexampleandoverview………………………. 2 18.2Wherearepagetablesstored? ………………………. 3 18.3What’sactuallyinthepagetable? …………………….. 3 18.4Paging:alsotooslow …………………………… 4 18.5Amemorytrace ……………………………… 4
Chapter 20: Paging: Smaller tables 4 20.1Simplesolution:biggerpages……………………….. 5 20.2Hybridapproach:pagingandsegments………………….. 5 20.3Multi-levelpagetables ………………………….. 5 20.4Invertedpagetables …………………………… 6 20.5Swappingthepagetablestodisk……………………… 6
COMP 3430 Operating Systems – Chapter 18 and 20 reading notes Winter 2022
About these reading notes
These are my own personal reading notes that I took (me, Franklin) as I read the textbook. I’m pro- viding these to you as an additional resource for you to use while you’re reading chapters from the textbook. These notes do not stand alone on their own — you might be able to get the idea of a chap- ter while reading these, but you’re definitely not going to get the chapter by reading these alone.
These notes are inconsistently all of the following:
• Mesummarizingpartsofthetext.
• Mecommentingonpartsofthetext.
• Measkingquestionstomyselfaboutthetext.
– …andsometimesansweringthosequestions.
The way that I would expect you to read or use these notes is to effectively permit me to be your in- ner monologue while you’re reading the textbook. As you’re reading chapters and sections within chapters, you can take a look at what I’ve written here to get an idea of how I’m thinking about this content.
Chapter 18: Paging: Introduction
• “… it may be worth considering the second approach: to chop up space into fixed-size pieces.”, that sounds almost the same as what we were doing originally with allocating the full address space. What was wrong with that? How is this going to fix things for us now?
• “The Atlas” that the authors are referring to is here: https://en.wikipedia.org/wiki/Atlas/_(co mputer)
• Make sure you’re keeping the terminology straight here: a page is a small piece of the virtual address space for a process, a page frame is where that page might go in physical memory. Just like in real life, you’ve got a picture and you put it into a picture frame.
18.1 A simple example and overview
• Lookingatfigure18.1:beforeyougettoofarintothischapter,trytothinkaboutwhatavirtual address is (a number), and how you might get information from that virtual address to figure out which page an address belongs to.
– Howmanybitsmightyouneedtorepresent4pages?
COMP 3430 Operating Systems – Chapter 18 and 20 reading notes Winter 2022
• “We won’t for example make assumptions about the direction the heap and stack grow and how they are used.” — but, but, but, our programs still have a heap and a stack! How can the underlying virtual memory implementation not care about those things?
• Onpg3:“Torecordwhereeachvirtualpageoftheaddressspaceisplacedinphysicalmemory, the operating system usually keeps a per-process data structure known as a page table.”
– Intermsofwhatyouknowaboutprocesses,wheredoyouthinkthispagetablemightbe stored?
• Theanswertoourfirstquestionabove(howmanybits)isatthebottomofpage3.
• Something important to note about the discussion here is that the virtual address space is smaller than the physical address space again (we have 8 page frames and 4 pages of virtual memory per process). This is explicitly not required though, the virtual address space can be
as big or bigger than the physical size of memory.
– This idea is reinforced in the middle of page 4, where the number of bits in the virtual address is smaller than the number of bits in a physical address.
• BeabletoconvinceyourselfthattheVPN(onthebottomofpg3)canuniquelymapeachaddress to a page in the virtual address space.
• GiventhenumberofbitsinaVPN(saywehave5bitsforVPN),howmanypageswouldwehave in virtual memory?
• Before you get much farther than page 4, try to think about this: how much of this address translation work is the OS responsible for? Hardware?
• Onpage5:“Notetheoffsetstaysthesame(i.e.,itisnottranslated),becausetheoffsetjusttells us which byte within the page we want.”
– Whyisn’ttheoffsettranslated?Whatwoulditbetranslatedtoifyoudidtranslateit? 18.2 Where are page tables stored?
• Near the top of page 6: “Instead, we store the page table for each process in memory some- where.” — wait a minute. We store the table that has the mappings between virtual and physical memory in memory?
18.3 What’s actually in the page table?
• We’re starting to talk about this idea of valid bits here. Try drawing a diagram that shows the “page table”, and how it might correspond to physical memory.
– Whatmightthatdiagramlooklike?
COMP 3430 Operating Systems – Chapter 18 and 20 reading notes Winter 2022
• If you are currently taking or have already taken COMP 3370, some of this might look awfully
familiar to you, both in the context of paging and in the context of caching.
• Ifyou’reactuallyinterestedintakingalookattheIntelArchitectureManuals,youcanfindthem
https://software.intel.com/content/www/us/en/develop/articles/intel-sdm.html
Note that these are pointing at PDFs that are bigger than textbooks, weighing in at about 60+MB a piece.
• Theaside“whynovalidbit?”isaprettyniceexampleofhardwareandtheOSworkingtogether to do something better than the hardware might be able to provide alone.
18.4 Paging: also too slow
• Trytothinkabouthowmanymemoryaccessesareactuallyrequiredtodothislookup,consid- ering that we have to both translate the virtual address to a physical address, then actually go to that physical address to get the value. Add on top of that the idea that we’re also needing to fetch an instruction, how many additional accesses would that take?
18.5 A memory trace
• Atthetopofpage10,theauthorsrefertoobjdumpandotool,trythemoutonaprogramyou compile!
• Thissection(18.5)isslowlysteppingthroughtheanswertothequestionposedabovefor18.4, use this to confirm what you thought about how many memory accesses this would take.
Chapter 20: Paging: Smaller tables
• Beforeyoustartreadingthischapter,trytothinkonyourownabouthowyoumightchangethis idea of a page table to make it “smaller”. It’s hard to do this entirely independently of looking at the chapter, since the title of the first subsection is on the first page, so try to think about it in terms of data structures. What kind of a data structure could you use to implement a page table? How would you incorporate this idea of a valid bit (the page is allocated or not allocated) into that data structure?
COMP 3430 Operating Systems – Chapter 18 and 20 reading notes Winter 2022
20.1 Simple solution: bigger pages
• Logicallyconvinceyourselfthatthismakessense:biggerpageswiththesamesizeaddressspace means fewer pages.
– Ifyouhave4KBpagesonanx86systemwithavirtualaddressspaceof64GB(thisisnota real number, just for thought’s sake), how many pages are there? How big would that page table be?
• Internalfragmentation:it’sback!
• Theasidehere“Multiplepagesizes”tellsalittlebitmoreaboutthatideafromchapter19.
20.2 Hybrid approach: paging and segments
• Make sure you get what this structure is: we’re not getting segments back, but instead we’re getting sets of pages, one for each of code, heap, or stack.
• Thissortofmakessensethattheallocatedpagesforthesesegmentsaresmallerthantheentire page table; does this mean that we’ve got a limit on how big the segments can be now, though?
• Argh! External fragmentation! Again!
20.3 Multi-level page tables
• OK,datastructurestime.
• This basic idea on the bottom of page 5 kind of seems similar to the idea of indirect pointers in
the file system. Is it a similar idea?
• Figure 20.3 does a great job of showing how a linear page table might be translated into this
multi-level page table.
• Willthismulti-levelpagetablerequiremorememoryaccessesthanalinearpagetable?
– Seethemiddleofpage7forananswer. A detailed multi-level example
• This example really steps through the translation from linear page tables to multi-level page tables, so make sure you’ve got the basic idea of what the linear page table is doing before you try grokking the translation to multi-level page tables.
• How much of this multi-level page table stuff do you think could be done in hardware? How much of it has to be done in software? Does address translation happen in software or hard- ware?
COMP 3430 Operating Systems – Chapter 18 and 20 reading notes Winter 2022
More than two levels
• “Inthisexample,assumewehavea30-bitvirtualaddressspace”;thisisgettingprettycloseto reality with 64-bit systems. How big of an address space is 30 bits? How many pages are there in this virtual address space when you’ve got 512 byte pages as the authors are doing?
• Stepthroughthepseudocodeonpage12;howisthisdifferentfromthebasiclinearpagetable? What parts of this do you recognize in terms of error states?
The translation process: remember the TLB
• You’renotrequiredtoreadabouttheTLB,butit’sacachethathelpsimprovetheperformanceof lookups from virtual addresses to physical addresses. You can find more about TLBs in chapter 19.
• (Ohno,weforgotabouttheTLB.https://www.youtube.com/watch?v=tgMyaAK-aZw) 20.4 Inverted page tables
• Howexactlydoesthisideachangehowbigpagetablesare?Doesthischangethevirtualaddress space for a process?
20.5 Swapping the page tables to disk
• Swappingiscominguprealsoon,butyoumighthavenoticed:processescanhaveavirtualad- dress space that’s bigger than physical memory. What happens when a process actually uses more than physical memory? What happens when all processes together use more than avail- able physical memory? (like what happens when you start Chrome and open 10 tabs)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com