COMP 3430 Operating Systems – Chapter 16 and 17 reading notes
Winter 2022
About these reading notes
Chapter 16: Segmentation
Copyright By PowCoder代写 加微信 powcoder
16.1Segmentation:GeneralizedBase/Bounds …………………. 2 16.2Whichsegmentarewereferringto? ……………………. 3 16.3Whataboutthestack?…………………………… 4 16.4Supportforsharing ……………………………. 4 16.5Fine-grainedvscoarse-grainedsegmentation . . . . . . . . . . . . . . . . . . . . 4 16.6OSSupport………………………………… 4
Chapter 17: Free-Space management 5 17.1Assumptions ……………………………….. 5 17.2Low-levelmechanisms ………………………….. 6 17.3Basicstrategies………………………………. 7 17.4Otherapproaches …………………………….. 8 17.5Summary…………………………………. 9
COMP 3430 Operating Systems – Chapter 16 and 17 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 16: Segmentation
• “Segmentation”. That’s a word you’ve seen before. Uh, a lot probably. Where have you seen that word before?
• Howdowesupportvirtualaddressspacesthatarelargerthanphysicalmemory?Wehadques- tions like this from the last couple of chapters, now we’re going to figure out (a less than ideal and currently unused) solution to this problem!
16.1 Segmentation: Generalized Base/Bounds
• Basic idea: don’t allocate the full address space, allocate the space you need for the different known “segments” of memory that your process needs (like code, heap, and stack), have each of those segments be relocatable by adding hardware support for 𝑛 different pairs of base/bounds registers for 𝑛 different segments.
– Notethatthesesegmentsareexplicitlynotthesamesize.
– Whatkindofproblemscanyoupredicthappeningwithsegmentsthatdifferinsize?
• Thehardwaresupporthereseemstoknowalotaboutwhat’sgoingonwithaprograminthat it assumes that the program uses a heap. What if your program doesn’t use dynamic memory
COMP 3430 Operating Systems – Chapter 16 and 17 reading notes Winter 2022
allocation? What do you think the OS will do in terms of allocating a segment for heap if you never try to use dynamic memory allocation?
– Extendingonthis,figure16.3shows3setsofregisters.Howmanysetsofregistersisreason- able? Is it reasonable to assume that 3 will always be enough? Is it reasonable to assume that all operating systems will forever use this idea of 3 different code regions?
• When we allocated the full virtual address space for a process, we had this issue of internal fragmentation. One idea we saw from our classmates to solve the problem was to put code/heap/stack regions into the middle of the virtual address space and grow outwards. This was a great idea, but internal fragmentation still remained because we were allocating the full address space.
– Does the idea of a sparse address space resemble the proposed solution above? Before you read on past pg 3, does sparse address spaces solve the issue of internal fragmenta- tion?
• Onthetopofpg4isanextraordinarilyimportantaside.
– Readit,then:https://www.youtube.com/watch?v=03QuygM0YB8
• Beforeyougettosection16.2“Whichsegmentarewereferringto”,startingatthetopofpage4, try to predict: given an address, how might you figure out which base and bounds registers to use? Would the hardware test them all? Something else?
16.2 Which segment are we referring to?
• IfyouhaveorarecurrentlytakingCOMP3370(orsomeequivalentcourseinadifferentfaculty), this process of splitting an address up into parts is directly related to cache memory implemen- tations (e.g., the tag, offset, index, etc).
• Ifweusethetop2bitstoindicatewhichsegmentwe’rereferringto,howmanysegmentscould we have? What if we used 3 bits? 𝑛 bits?
• Inshort:themappingofsegmenttobase/boundsregisterpairsissomethingtheOSandhard- ware would have to agree on. The hardware doesn’t know the difference (necessarily) between the “heap” and the “stack”, it just knows that there are different segments. The OS would have to keep track of the semantic meaning of each of the segments, and configure the hardware such that “01” (or whatever it chooses) should use one pair of base/bounds registers, “00” (or whatever it chooses) should use another pair of base/bounds registers, etc
• Onthebottomofpg5:“Somesystemsputcodeinthesamesegmentastheheapandthususe only one bit to select which segment to use”.
COMP 3430 Operating Systems – Chapter 16 and 17 reading notes Winter 2022
– Can you think of any issues with this solution? (hint: should the heap be executable? code?)
– Whywouldtheychoosetheheapandnotthestack?(hint:lookatthedirectionthateach of those segments “grows”)
• On the bottom of pg 5: “Specifically, each segment is limited to a maximum size, which in our example is 4KB”, can you convince yourself based on how these addresses are separated into segment and offset that this is true?
16.3 What about the stack?
• OK,nowthingsaregoingtogetweird.
– The arithmetic is straightforward (not easy, straightforward), but your mind might be throwing exceptions while you’re reading it. Take the time to make sure you get this idea of computing negative offsets.
• Seriousquestion:Whydon’twealljustagreetoletthestackgrowforwardsliketheheap?
16.4 Support for sharing
• Whatkindofcodememorydoyouthinkwouldbesharedbetweenprocesses?
• Whydowehavetoaddbits(protectionbits)tosharememory?Isn’tthatcounterintuitive?
• The authors are again using the terms protection and isolation here. Do they mean the same
thing as we saw last time?
16.5 Fine-grained vs coarse-grained segmentation
• OK,sothisisaddressingaquestionthatwesawearlier.
• Rememberthisterm“segmenttable”,theideaisgoingtocomebackagainrealsoon.
• Whyonearthwouldweevenwantfine-grainedsegmentation?“…expectedacompilertochop
code and data into separate segments which the OS and hardware would then support.” — what kind of maniac would come up with a system like that? Compilers supporting OS-specific ideas?
16.6 OS Support
• Yay,wesolvedinternalfragmentation.
• Surprise: when we have multiple segments instead of a fully-allocated address space, the OS
still has to do many of the same things!
COMP 3430 Operating Systems – Chapter 16 and 17 reading notes Winter 2022
• “thememory-allocationlibrarywillperformasystemcalltogrowtheheap”.
– Whenyoucallmalloc(),you’realmostalwaysusingtheglibcimplementationofmal- loc(), but musl has its own allocator, and there are also dynamic memory allocators that are entirely separate from standard libraries, like jemalloc.
• Checkoutmansbrk,thisisarealthing.Italsokindofmeansthatyoucouldwriteyourown memory allocator.
• Wetalkedaboutexternalfragmentationlastweek,nowwe’regoingtoseeitrearit’suglyhead. – Isexternalfragmentationthesamethingthathappenswithfilesystemsondisk?
• “One solution to this would be to compact physical memory by rearranging the existing seg- ments.” — depending on when you took COMP 2160, this is literally the same word we used to describe the feature of our compacting garbage collector that would shuffle allocated mem- ory back to the beginning of the array. In fact, this entire idea of virtual addresses aligns very closely with that assignment, specifically about using an ID or tag instead of an actual address to interact with the memory allocator.
• “Compactionalso(ironically)makesrequeststogrowexistingsegmentshardtoserve”
– Isthisironic?https://www.youtube.com/watch?v=Jne9t8sHpUc
– Why is this true? Why does compacting memory segments make growing segments
• Tracking free memory sounds like a “hard problem” TM; “There are literally hundreds of approaches that people have taken”. Maybe that means it’s easy? How would you track free memory and decide which free space you should allocate a request in? Does this remind you of any algorithms?
Chapter 17: Free-Space management
• Don’tlet“Page1of18”scareyou!Therearemanypageswithnearlyfull-pagediagrams.
• “Let’stakealookatsomealgorithmsforfree-spacemanagement”,thenquicklydecidethatit’s easier to use fixed-size things (pages) and mostly forget about the idea of free-space manage-
17.1 Assumptions
• Alwayswiththeassumptions.
COMP 3430 Operating Systems – Chapter 16 and 17 reading notes Winter 2022
• Notethatthischapterassumesyou’refamiliarwiththememorymanagementAPI(mallocand free). I don’t know how you couldn’t be at this point, but if you need a refresher, you can read chapter 14.
• “Note the implementation of this interface: the user, when freeing the space, does not inform the library of its size” — …? Think about that for a second. When using malloc and free, have you ever cared about telling free how much space you’re freeing?
• Dynamic memory allocation is kind of a split responsibility between the standard library and the OS. In fact, all of the things this chapter talks about apply both to the OS’s management of free memory (physical memory) and your dynamic allocator of choice’s free memory (virtual memory within the heap).
– WhynotjustmakethisanOSresponsibility?Whyaren’tmallocandfreesystemcalls?
• “Allocatorscouldofcoursealsohavetheproblemofinternalfragmentation”—doyouthink your allocator cares about internal fragmentation? What even is internal fragmentation to a memory allocator library? Should a memory allocator library care about internal fragmenta- tion?
• “We’llalsoassumethatoncememoryishandedouttoaclient,itcannotberelocatedtoanother location in memory” ← note that this is specifically talking about “relocated to another virtual address”, the OS is free to move the segment in physical memory wherever it wants, as long as it correctly updates the base/bounds registers for that segment.
• Again,checkoutmansbrkandthinkabouthowyoucouldwriteyourownmemoryallocator using this system call.
17.2 Low-level mechanisms
Splitting and coalescing
• Afreelistisliterallyalist,andyoucanseeavisualdepictionofthatonthebottomofpg3.
– This diagram alone looks extraordinarily similar to an assignment in COMP 2160. Ask someone on your team about it if you don’t recognize this image.
• Thisideaofsplittingandcoalescingisprettyneat,particularlyintermsofhowthelistchanges. The authors don’t include what the physical memory allocation looks like corresponding to the list as regions are split and coalesced, take the time to draw out how this physical memory changes as the list changes.
Tracking the size of allocated regions
COMP 3430 Operating Systems – Chapter 16 and 17 reading notes Winter 2022
• OK, this idea is actually super cool. Not lame cool, but super cool. This same idea is actually used in some C string management libraries (“Cello”, a C library liberally uses this pattern: http: //libcello.org/).
How would you use this idea to build a “string library” in C?
• Whywouldalibrarythatusesthisapproachcheckandconfirma“magicnumber”?(hint:what happens when you free a pointer that you didn’t get back from malloc? What would free even do if you give it a pointer you didn’t get back from malloc?)
Embedding a free list
• “Inamoretypicallist,whenallocatinganewnode,youwouldjustcallmalloc()….Unfortu- nately, within the memory-allocation library, you can’t do this!” — Think about this for a second, and make sure that you understand why this is true. Why can’t a dynamic allocation library call malloc()?
• mmap()? What’s that? Check out man mmap. – Whatdoesthishavetodowiththeheap?
• Whattheheckisgoingonhere?Thislistdoesn’tlookanythinglikewhatIimaginedalisttolook like! Where are the circles?!
– Seriously, though: why is this list embedded within the free space? Why wouldn’t they allocate a chunk at the beginning and use that for the list?
– Whatthey’redoinghereisdirectlyrequiredbythisideathatthedynamicmemoryallocator doesn’t have its own dynamic memory allocator to fall back on (insert Xzibit here).
• Theauthorsdescribefigure17.7as“abigmess”.Iwouldagreewiththem.Whenshouldamem- ory allocator like this decide to coalesce memory?
Growing the heap
• Again, check out this system call sbrk. What does it do? What does sbrk stand for as an acronym or abbreviation?
• “Toservicethesbrkrequest,theOSfindsfreephysicalpages”…whatdoesthishavetodowith segments?
17.3 Basic strategies
• As you’re reading about each of these different policies, think about this: are these in any way related to the scheduling policies that we looked at? Thinking about time and space this way is
COMP 3430 Operating Systems – Chapter 16 and 17 reading notes Winter 2022
a little bit weird, but definitely think about it.
• Foreachofthepolicies,trytoimagine,or,youknow,drawapictureof,theworst-casescenario
for the policy.
• Istherea“best”policyoftheonesthataredescribedhere?Whatdoes“best”evenmeaninthis
context? With scheduling policies we had some pretty good metrics, what are the metrics here?
• Thesepoliciesareallfairlystraightforward,sooutsideof“Worstfit”,therearen’tanyquestions
about them.
Best fit Worst fit
• Wait,what?Worstfit?Doesn’t“worst”imply“bad”?
• Worst fit is related to best fit in that it’s sort of the opposite. Are these policies similar in any
other ways?
17.4 Other approaches Segregated lists
• Howwouldadynamicmemoryallocatorknowwhata“popular-sized”requestis?Thinkabout the memory API (the interface; how it would get that information), and think about what the memory allocator could use that information in its implementation.
• Isthisideaeffectivelythesameashavingfixedsizeblocksintermsofwhatwesawwithvirtual memory implementations?
• “when the kernel boots up, it allocates a number of object caches for kernel objects that are likely to be requested frequently” — that sounds awfully familiar. What is this idea similar to?
• DoyouthinkthisideaisatallrelatedtotheMLFQschedulingpolicy?Howisitrelated?
COMP 3430 Operating Systems – Chapter 16 and 17 reading notes Winter 2022
Buddy allocation
• https://www.youtube.com/watch?v=9jyCfRHumHU
• This whole idea of dividing spaces by two is an idea that comes up constantly in CS. Where’s
another place you’ve seen this?
– Oneplaceyoumayneverhaveseenthisisintwodimensions:Quadtrees,andthreedimen-
sions: Octrees
• “notethatthisschemecansufferfrominternalfragmentation,asyouareonlyallowedtogive out power-of-two-sized blocks.” Do the other allocation policies that you’ve seen suffer from this problem of internal fragmentation? Why or why not?
• Whatkindofallocationpatternsdoyouthinkwouldcausethispolicytobehavepoorly?Specif- ically, given a 64kb chunk, what general kind of size requests would cause this policy to behave poorly?
Other ideas
• “Failingthat,readabouthowtheglibcallocatorworks”;you’remorethanwelcometodothat, but know in advance that glibc source code is notoriously impenetrable to read.
– Youcouldalsoreadaboutjemalloc – Or,uh,manyothers
17.5 Summary
• Alotofthissoundslikeit’sresponsibilityofadynamicmemoryallocatorlibrarythat’srunning in user space. What does this have to do with operating systems?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com