COS 318: Operating SystemsVirtual Memory Paging2Today’s Topics!Paging mechanism!Page replacement algorithms3Virtual Memory Paging!Simple world"Load entire process into memory. Run it. Exit. !Problems"Slow (especially with big processes)"Wasteful of space (doesn’t use all of its memory all the time)"Reduces number of processes ready to run at a time!Solution"Demand paging: only bring in pages actually used"Paging: only keep frequently used pages in memory!Mechanism: "Programs refer to addresses in virtual address space"Virtual memory maps some to physical pages in memory, some to disk4VM Paging StepsSteps!Memory reference (may cause a TLB miss)!TLB entry invalid triggers a page fault and VM handler takes over!Move page from disk to memory!Update TLB entry w/ pp#, valid bit!Restart the instruction!Memory reference again...subl $20 %esp movl 8(%esp), %eax ...vp#v vp#i vp#v vp#v vp#TLBpp#pp#dp#pp#pp#...vVMsystempp#vReferencefaultRestartVP# = virtual page no.PP# = physical page no.5Virtual Memory Issues!How to switch a process after a fault?"Need to save state and resume"Is it the same as an interrupt?!What to page in?"Just the faulting page or more?"Want to know the future…!What to replace?"Memory is a software-managed cache on disk"Caches always too small, which page to replace?"Want to know the future...6How Does Page Fault Work?!User program should not be aware of the page fault!Fault may have happened in the middle of the instruction! !Can we skip the faulting instruction? !Is a faulting instruction always restartable? . . .subl $20 %esp movl 8(%esp), %eax . . .VM fault handler(){ Save states . . . iret}7What to Page In? !Page in the faulting page"Simplest, but each “page in” has substantial overhead!Page in more pages each time"May reduce page faults if the additional pages are used"Waste space and time if they are not used"Real systems do some kind of prefetching!Applications control what to page in"Some systems support for user-controlled prefetching"But, many applications do not always know8VM Page Replacement!Things are not always available when you want them"It is possible that no unused page frame is available"VM needs to do page replacement!On a page fault"If there is an unused frame, get it"If no unused page frame available,• Find a used page frame• If it has been modified, write it to disk• Invalidate its current PTE and TLB entry"Load the new page from disk"Update the faulting PTE and remove its TLB entry"Restart the faulting instruction!General data structures"A list of unused page frames"A table to map page frames to PID and virtual pages, why?PageReplacement9Which “Used” Page Frame To Replace?!Random!Optimal or MIN algorithm!NRU (Not Recently Used)!FIFO (First-In-First-Out)!FIFO with second chance!Clock!LRU (Least Recently Used)!NFU (Not Frequently Used)!Aging (approximate LRU)!Working Set!WSClock10Optimal or MIN!Algorithm: "Replace the page that won’t be used for the longest time (Know all references in the future)!Example"Reference string: "4 page frames"6 faults!Pros"Optimal solution and can be used as an off-line analysis method!Cons"No on-line implementation1 2 3 4 1 2 5 1 2 3 4 511Revisit TLB and Page Table!Important bits for paging"Reference: Set when referencing a location in the page"Modify: Set when writing to a location in the pageoffsetVirtual address...PPage#...PPage#...PPage#…PPage # offsetVPage #TLBHitMissPage TableVPage#VPage#VPage#12Not Recently Used (NRU)!Algorithm"Randomly pick a page from lowest-numbered non-empty class below• Not referenced and not modified• Not referenced and modified (huh?)• Referenced and not modified• Referenced and modified"Clear reference bits periodically (e.g. at clock interrupts)!Example"4 page frames"Reference string"8 page faults!Pros"Implementable!Cons"Require scanning through reference bits and modified bits1 2 3 4 1 2 5 1 2 3 4 513First-In-First-Out (FIFO)!Algorithm"Throw out the oldest page!Example"4 page frames"Reference string"10 page faults!Pros"Low-overhead implementation!Cons"May replace the heavily used pages5 3 4 7 9 11 2 1 15PageoutRecentlyloaded1 2 3 4 1 2 5 1 2 3 4 514More Frames ! Fewer Page Faults?!Consider the following with 4 page frames"Algorithm: FIFO replacement"Reference string:"10 page faults!Same string with 3 page frames"Algorithm: FIFO replacement"Reference string:"9 page faults!!This is so called “Belady’s anomaly” (Belady, Nelson, Shedler 1969)1 2 3 4 1 2 5 1 2 3 4 51 2 3 4 1 2 5 1 2 3 4 515FIFO with 2nd Chance!Algorithm"Check the reference-bit of the oldest page"If it is 0, then replace it"If it is 1, clear the referent-bit, put it to the end of the list (as if it had just been loaded), and continue searching!Example"4 page frames"Reference string:"8 page faults!Pros"Simple to implement!Cons"The worst case may take a long time (moving pages around on the list)5 3 4 7 9 11 2 1 15RecentlyloadedPageoutIf ref bit = 11 2 3 4 1 2 5 1 2 3 4 516Clock!FIFO clock algorithm"Hand points to the oldest page"On a page fault, follow the hand to inspect pages!Second chance"If the reference bit is 0, use it for replacement, new page replaces it, advance the hand"If the reference bit is 1, set it to 0 and advance the hand Oldest page17Least Recently Used!Algorithm"Replace page that hasn’t been used for the longest time• Order the pages by time of reference• Timestamp for each referenced page!Example"4 page frames"Reference string: "8 page faults!Pros"Good to approximate MIN!Cons"Expensive: maintain list of pages by reference, update on every reference5 3 4 7 9 11 2 1 15RecentlyloadedLeastRecentlyused1 2 3 4 1 2 5 1 2 3 4 518Approximations of LRU!Use CPU ticks"For each memory reference, store the ticks in its PTE"Find the page with minimal ticks value to replace!Use a smaller counterMost recently usedLeast recently usedN categoriesPages in order of last referenceLRUCrudeLRU2 categoriesPages referenced since the last page faultPages not referenced since the last page fault8-bitcount256 categories254 25519Aging: Not Frequently Used (NFU)!Algorithm"Shift reference bits into counters at every clock interrupt"Pick the page with the smallest counter to replace!Old example"4 page frames"Reference string: "8 page faults!Main difference between NFU and LRU?"NFU can’t distinguish LRU within a clock interrupt period"NFU has a short history (counter length)!How many bits are enough?"In practice 8 bits are quite