Operating System Principles: Memory Management – Swapping, Paging, and Virtual Memory
Operating Systems
CS 111 Spring 2022
Copyright By PowCoder代写 加微信 powcoder
Lecture 6 Page 1
How Much of Our Problem
Have We Solved? • We can use variable sized partitions
– Cutting down on internal fragmentation
• We can move partitions around
– Which helps coalescing be more effective
– But segments still need contiguous chunks of memory
– So external fragmentation is still a problem
• We still can’t support more process data needs
than we have physical memory
CS 111 Spring 2022
Lecture 6 Page 2
• Swapping
• Virtual memory
CS 111 Spring 2022
Lecture 6 Page 3
• What if we don’t have enough RAM? – To handle all processes’ memory needs – Perhaps even to handle one process
• Maybe we can keep some of their memory somewhere other than RAM
• Maybe on a disk (hard or flash)
• Of course, you can’t directly use code or data on a disk . . .
CS 111 Spring 2022
Lecture 6 Page 4
Swapping To Disk
• An obvious strategy to increase effective memory size
• When a process yields or is blocked, copy its memory to disk
• When it is scheduled, copy it back
• If we have relocation hardware, we can put the
memory in different RAM locations
• Each process could see a memory space as big
as the total amount of RAM
CS 111 Spring 2022
Lecture 6 Page 5
Downsides To Simple Swapping
• If we actually move everything out, the costs of a context switch are very high
– Copy all of RAM out to disk
– And then copy other stuff from disk to RAM
– Before the newly scheduled process can do anything
• We’re still limiting processes to the amount of RAM we actually have
CS 111 Spring 2022
Lecture 6 Page 6
• What is paging?
– What problem does it solve? – How does it do so?
• Paged address translation
• Paging and fragmentation
• Paging memory management units
CS 111 Spring 2022
Lecture 6 Page 7
Segmentation Revisited
• Segment relocation solved the relocation problem for us
• It used base registers to compute a physical address from a virtual address
– Allowing us to move data around in physical memory
– By only updating the base register
• It did nothing about external fragmentation
– Becausesegmentsarestillrequiredtobe contiguous
• We need to eliminate the “contiguity requirement”
CS 111 Spring 2022
Lecture 6 Page 8
The Paging Approach
Dividephysicalmemoryintounitsofasinglefixed size
– A pretty small one, like 1-4K bytes or words – Typically called a page frame
Treatthevirtualaddressspaceinthesameway – Call each virtual unit a page
Foreachvirtualaddressspacepage,storeitsdatain one physical address page frame
– Any page frame, not one specific to this page Usesomemagicper-pagetranslationmechanismto
convert virtual to physical pages Spring 2022
Lecture 6 Page 9
Paged Address Translation
process virtual address space
CS 111 Spring 2022
physical memory
Lecture 6 Page 10
Paging and Fragmentation
• A segment is implemented as a set of virtual pages
• Internal fragmentation
− Averages only 1⁄2 page (half of the last one)
• External fragmentation
− Completely non-existent
− We never carve up pages Spring 2022
Tremendous
reduction in
fragmentation costs!
Lecture 6 Page 11
Providing the Magic Translation Mechanism
• On per page basis, we need to change a virtual address to a physical address
– On every memory reference • Needs to be fast
– So we’ll use hardware
• The Memory Management Unit (MMU)
– A piece of hardware designed to perform the magic quickly
CS 111 Spring 2022
Lecture 6 Page 12
Paging and MMUs
Virtual address
Physical address
Offset within page remains the same
V used as an index into V
Virtual page number is the page table
Valid bit is checked to ensure that this virtual page number is legal
V 0 V 0 V V
Page Table
Selected entry contains physical page number
Lecture 6 Page 13
CS 111 Spring 2022
Some Examples
Virtual address
Physical address
Hmm, no address Why might that happen?
And what can we do about it?
130CE102008
CS 111 Spring 2022
V V V 0 V 0 V V
Page Table
Lecture 6 Page 14
The MMU Hardware
• MMUs used to sit between the CPU and bus
– Now they are typically integrated into the CPU
• What about the page tables?
– Originally implemented in special fast registers
– But there’s a problem with that today
– If we have 4K pages, and a 64 Gbyte memory, how many pages are there?
– 236/212 = 224
– Or 16 M of pages
– We can’t afford 16 M of fast registers
CS 111 Spring 2022
Lecture 6 Page 15
Handling Big Page Tables
16Mentriesinapagetablemeanswecan’tuse registers
’tafford2buscyclesforeachmemory access
– One to look up the page table entry – One to get the actual data
SowehaveaveryfastsetofMMUregistersusedas a cache
– Which means we need to worry about hit ratios, cache invalidation, and other nasty issues
– TANSTAAFL Spring 2022
Lecture 6 Page 16
The MMU and Multiple Processes
• There are several processes running
• Each needs a set of pages
• We can put any page anywhere
• But if they need, in total, more pages than we’ve physically got,
• Something’s got to go
• How do we handle these ongoing paging
requirements?
CS 111 Spring 2022
Lecture 6 Page 17
Where Do We Keep Extra Pages?
• We have more pages than RAM
• So some of them must be somewhere other than RAM
• Where else do we have the ability to store data?
• How about on our disk or flash drive?
• In paged system, typically some pages are kept
on persistent memory device
• ButcodecanonlyaccessapageinRAM …
CS 111 Spring 2022
Lecture 6 Page 18
Ongoing MMU Operations
• Whatifthecurrentprocessaddsorremovespages? – Directlyupdateactivepagetableinmemory
– Privilegedinstructiontoflush(stale)cachedentries
• Whatifweswitchfromoneprocesstoanother? – Maintainseparatepagetablesforeachprocess
– Privilegedinstructionloadspointertonewpagetable – Areloadinstructionflushespreviouslycachedentries
• Howtosharepagesbetweenmultipleprocesses?
– Makeeachpagetablepointtosamephysicalpage
– Canberead-onlyorread/writesharing
CS 111 Spring 2022
Lecture 6 Page 19
Demand Paging
• If we can’t keep all our pages in RAM, some are out on disk
• But we can’t directly use them on disk
• So which ones do we put out on disk?
• And how do we get them back if it turns out we need to use them?
• Demand paging is the modern approach to that problem
CS 111 Spring 2022
Lecture 6 Page 20
What Is Demand Paging?
• A process doesn’t actually need all its pages in memory to run
• It only needs those it actually references
• So, why bother loading up all the pages when a
process is scheduled to run?
• And, perhaps, why get rid of all of a process’ pages when it yields?
• Move pages onto and off of disk “on demand”
CS 111 Spring 2022
Lecture 6 Page 21
How To Make Demand Paging Work
• The MMU must support “not present” pages
– Generates a fault/trap when they are referenced
– OS can bring in the requested page and retry the faulted reference
• Entire process needn’t be in memory to start running
– Start each process with a subset of its pages
– Load additional pages as program demands them
• The big challenge will be performance
CS 111 Spring 2022
Lecture 6 Page 22
Achieving Good Performance for
Demand Paging
• Demand paging will perform poorly if most
memory references require disk access
– Worse than swapping in all the pages at once, maybe
• So we need to be sure most don’t
• By ensuring that the page holding the next memory reference is already there
– Almost always
CS 111 Spring 2022
Lecture 6 Page 23
Demand Paging and Locality of Reference
• How can we predict what pages we need in memory?
– Since they’d better be there when we ask
• Primarily, rely on locality of reference
– Put simply, the next address you ask for is likely to be close to the last address you asked for
• Do programs typically display locality of reference?
• Fortunately, yes! CS 111
Spring 2022
Lecture 6 Page 24
Why is Locality of Reference
Usually Present?
• Codeusuallyexecutessequencesofconsecutiveor
nearby instructions
– Most branches tend to be relatively short distances (into code in the same routine)
• Wetypicallyneedaccesstothingsinthecurrentor previous stack frame
• Manyheapreferencestorecentlyallocatedstructures – E.g., creating or processing a message
• Noguarantees,butallthreetypesofmemoryare likely to show locality of reference
CS 111 Spring 2022
Lecture 6 Page 25
Page Faults
• Page tables no longer necessarily contain pointers to pages of RAM
• In some cases, the pages are not in RAM, at the moment
– They’re out on disk (hard or flash)
• When a program requests an address from
such a page, what do we do?
• Generate a page fault
– Which is intended to tell the system to go get it
CS 111 Spring 2022
Lecture 6 Page 26
A Page Fault Example
Virtual address
Physical address
Hmm, no address Why might that happen?
PAGE FAULT! Now what . . . ?
CS 111 Spring 2022
V V V 0 V 0 V V
Page Table
Lecture 6 Page 27
Handling a Page Fault
• Initialize page table entries to “not present”
• CPU faults if “not present” page is referenced – Fault enters kernel, just like any other exception
– Forwarded to page fault handler
– Determine which page is required, where it resides – Schedule I/O to fetch it, then block the process
– Make page table point at newly read-in page
– Back up user-mode PC to retry failed instruction – Return to user-mode and try again
• Meanwhile, other processes can run CS 111
Spring 2022
Lecture 6 Page 28
Page Faults Don’t Impact
Correctness
Page faults only slow a process down
After a fault is handled, the desired page is in RAM
And the process runs again and can use it
– Based on the OS ability to save process state and restore it
Programs never crash because of page faults
But they might be very slow if there are too
many Spring 2022
Lecture 6 Page 29
Demand Paging Performance • Page faults may block processes
• Overhead (fault handling, paging in and out) – Process is blocked while we are reading in pages – Delaying execution and consuming cycles
– Directly proportional to the number of page faults
• Key is having the “right” pages in memory – Right pages -> few faults, little paging activity – Wrong pages -> many faults, much paging
• We can’t control which pages we read in
– Key to performance is choosing which to kick out
CS 111 Spring 2022
Lecture 6 Page 30
Virtual Memory
A generalization of what demand paging allows
A form of memory where the system provides a useful abstraction
– A very large quantity of memory
– For each process
– All directly accessible via normal addressing – At a speed approaching that of actual RAM
The state of the art in modern memory
abstractions Spring 2022
Lecture 6 Page 31
The Basic Concept
Give each process an address space of immense size
– Perhaps as big as your hardware’s word size allows
Allow processes to request segments within that space
Use dynamic paging and swapping to support the abstraction
The key issue is how to create the abstraction
when you don’t have that much real memory Lecture 6 Spring 2022 Page 32
The Key VM Technology:
Replacement Algorithms
• The goal is to have each page already in
memory when a process accesses it
• We can’t know ahead of time what pages will be accessed
• We rely on locality of access
– In particular, to determine which pages to move
out of memory and onto disk
• If we make wise choices, the pages we need in
memory will still be there
CS 111 Spring 2022
Lecture 6 Page 33
The Basics of Page Replacement
• We keep some set of all pages in memory – As many as will fit
– Probably not all belonging to a single process
• Under some circumstances, we need to replace one of them with another page that’s on disk
– E.g., when we have a page fault
• Paging hardware and MMU translation allows
us to choose any page for ejection to disk
• Which one of them should go?
CS 111 Spring 2022
Lecture 6 Page 34
The Optimal Replacement Algorithm
• Replace the page that will be next referenced
furthest in the future Oracles are systems
• A slight problem:
– We would need an oracle to know which page this
• Why is this the right page?
– It delays the next page fault as long as possible
– Fewer page faults per unit time = lower overhead
algorithm calls for
– And we don’t have one
CS 111 Spring 2022
Lecture 6 Page 35
that perfectly predict the future.
Do We Require Optimal
Algorithms? Not absolutely
What’s the consequence being wrong?
– We take an extra page fault that we shouldn’t have
– Which is a performance penalty, not a program correctness penalty
– Often an acceptable tradeoff Themoreoftenwe’reright,thefewerpagefaultswe
Fortraces,wecanruntheoptimalalgorithm,
comparing it to what we use when live Spring 2022
Lecture 6 Page 36
Approximating the Optimal
• Rely on locality of reference
• Note which pages have recently been used – Perhaps with extra bits in the page tables
– Updated when the page is accessed
• Use this data to predict future behavior
• If locality of reference holds, the pages we
accessed recently will be accessed again soon
CS 111 Spring 2022
Lecture 6 Page 37
Candidate Replacement Algorithms • Random, FIFO
– These are dogs, forget ‘em • Least Frequently Used
– Sounds better, but it really isn’t
• Least Recently Used
– Assert that near future will be like the recent past
– If we haven’t used a page recently, we probably won’t use it soon
– How to actually implement LRU?
CS 111 Spring 2022
Lecture 6 Page 38
Naïve LRU
• Each time a page is accessed, record the time
• When you need to eject a page, look at all timestamps for pages in memory
• Choose the one with the oldest timestamp
• Will require us to store timestamps somewhere
• And to search all timestamps every time we need to eject a page
With 64 Gbytes of RAM and 4K pages, 16 megabytes of timestamps – sounds expensive.
CS 111 Spring 2022
Lecture 6 Page 39
True LRU Page Replacement
Reference stream
Page table using true LRU
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
frame0 a0 frame 1 frame 2 frame 3
CS 111 Spring 2022
Lecture 6 Page 40
Loads 4 Replacements 7
Maintaining Information for LRU
• CanwekeepitintheMMU?
– MMU would note the time whenever a page is referenced
– MMU translation must be blindingly fast
• Getting/storingtimeoneveryfetchwouldbeveryexpensive
– At best MMU will maintain a read and a written bit per page
• Canwemaintainthisinformationinsoftware?
– Complicated and time consuming
– If we maintain real timestamps, multiple overhead instructions for each real memory reference
• WeneedacheapsoftwaresurrogateforLRU
– No extra instructions per memory reference
– Mustn’t cause extra page faults
– Can’t scan entire list each time on replacement, since it’s big
CS 111 Spring 2022
Lecture 6 Page 41
Clock Algorithms
• AsurrogateforLRU
• Organizeallpagesinacircularlist
• MMUsetsareferencebitforthepageonaccess
• Scanwheneverweneedanotherpage
– For each page, ask MMU if page’s reference bit is set
– If so, clear the reference bit in the MMU & skip this page – If not, consider this page to be the least recently used
– Next search starts from this position, not head of list
• Usepositioninthescanasasurrogateforage
• Noextrapagefaults,usuallyscanonlyafewpages
CS 111 Spring 2022
Lecture 6 Page 42
Remember guess pointers from Next Fit algorithm?
Clock Algorithm Page Replacement
Reference Stream
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
frame0 a ! ! ! ! f d ! frame1 b !!! a !! frame2 c e b e frame3 d !!! c
0 1 2 3 0 0 0 012 30 1 2 3 0 1 21 3
loads 4, replacements 7
frame0a a f d d frame 1 b Rbeplacemenats 7 a
frame2 c e c
frame3 d d b
CS 111 Spring 2022
e Lecture6 Page 43
Comparing True LRU To Clock
• Same number of loads and replacements
– But didn’t replace the same pages
• What, if anything, does that mean?
• Both are just approximations to the optimal
• If LRU clock’s decisions are 98% as good as true LRU
– And can be done for 1% of the cost (in hardware and cycles)
– It’s a bargain!
CS 111 Spring 2022
Lecture 6 Page 44
Page Replacement and Multiprogramming
• We don’t want to clear out all the page frames on each context switch
– When switched out process runs again, we don’t want a bunch of page faults
• How do we deal with sharing page frames?
• Possible choices:
– Single global pool
– Fixed allocation of page frames per process
CS 111 – Working set-based page frame allocations Spring 2022
Lecture 6 Page 45
Single Global Page Frame Pool
Treat the entire set of page frames as a shared resource
Approximate LRU for the entire set
Replace whichever process’ page is LRU
Probably a mistake
– Bad interaction with round-robin scheduling
– The guy who was last in the scheduling queue will find all his pages swapped out
CS 111 Spring 2022
– And not because he isn’t using them
– When he’s scheduled, lots of page faults
Lecture 6 Page 46
Per-Process Page Frame Pools
• Set aside some number of page frames for each running process
– Use an LRU approximation separately for each
• How many page frames per process?
• Fixed number of pages per process is bad
– Different processes exhibit different locality • Which pages are needed changes over time
• Number of pages needed changes over time
– Much like different natural scheduling intervals
• We need a dynamic customized allocation CS 111
Spring 2022
Lecture 6 Page 47
Working Sets
• Giveeachrunningprocessanallocationofpage frames matched to its needs
• Howdoweknowwhatitsneedsare?
• Useworkingsets
• Setofpagesusedbyaprocessinafixedlength sampling window in the immediate past1
• Allocateenoughpageframestoholdeachprocess’ working set
• Eachprocessrunsreplacementwithinitsownset 1This definition paraphrased from ’s definition
CS 111 Spring 2022
Lecture 6 Page 48
Number of page faults
Little marginal benefit for additional space
More, is just “more”.
The Natural Working Set Size
Insufficient space leads to huge numbers of page faults
The sweet spot
CS 111 Spring 2022
Working set size
Lecture 6 Page 49
Optimal Working Sets
• What is optimal working set for a process?
– Number of pages needed during next time slice • What if we run the process in fewer pages?
– Needed pages will replace one another continuously
– Process will run very slowly
• How can we know what working set size is?
– By observing the process’ behavior
• Which pages should be in the working-set?
CS 111 – No need to guess, the process will fault for themLecture 6 Spring 2022 Page 50
Implementing Working Sets
• Managetheworkingsetsize
– Assign page frames to each in-memory process
– Processes page against themselves in working set
– Observe paging behavior (faults per unit time)
– Adjust number of assigned page frames accordingly
• Pagestealingalgorithmstoadjustworkingsets
– E.g., Working Set-Clock
– Track last use time for each page, for owning process
– Find page (approximately) least recently used (by its owner)
– Processes that need more pages tend to get more
– Processes that don’t use their pages tend to lose them
Lecture 6 Page 51
CS 111 Spring 2022
• Workingsetsizecharacterizeseachprocess
– How many pages it needs to run for t milliseconds
• Whatifwedon’thaveenoughmemory?
– Sum of working sets exceeds available page frames
– No one will have enough pages in memory
– Whenever anything runs, it will grab a page from someone else
– So they’ll get a page fault soon after
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com