CSE 153 Design Of Operating Systems

CSE 153Design of OperatingSystemsSummer 2022Lecture 14/15: Page Replacement Policies

Memory Management!Memory management systemsuuu!Physical and virtual addressing; address translationTechniques: Partitioning, paging, segmentationPage table size, TLBs, VM tricksPoliciesuPage replacement algorithms (3)2

Demand Paging (OS)!We use demand paging (similar to other caches):uuu!What is the alternative to demand paging?u!Pages loaded from disk when referencedPages may be evicted to disk when memory is fullPage faults trigger paging operationsSome kind of prefetchingLazy vs. aggressive policies in systems3

Demand Paging (Process)!!Demand paging when a process first starts upWhen a process is created, it hasuu!A brand new page table with all valid bits offNo pages in memoryWhen the process starts executinguuuuInstructions fault on code and data pagesFaulting stops when all necessary code and data pages are inmemoryOnly code and data needed by a process needs to be loadedThis, of course, changes over time 4

Page Replacement!!When a page fault occurs, the OS loads the faulted pagefrom disk into a page frame of memoryAt some point, the process has used all of the pageframes it is allowed to useu!This is likely (much) less than all of available memoryWhen this happens, the OS must replace a page for eachpage faulted inuuIt must evict a page to free up a page frameWritten back only if it is has been modified (i.e., “dirty”)!5

Page replacement policy!!!What we discussed so far (page faults, swap, pagetable structures, etc ) is mechanismsPage replacement policy: determine which page toremove when we need a victimDoes it matter?uuYes! Page faults are super expensiveGetting the number down, can improve the performance of thesystem significantly6

Considerations!Page replacement support has to be simple duringmemory accessesu!They happen all the time, we cannot make that part slowBut it can be complicated/expensive when a page faultoccurs – why?uuReason 1: if we are successful, this will be rareReason 2: when it happens we are paying the cost of I/O» I/O is very slow: can afford to do some extra computation» Worth it if we can save some future page faults!What makes a good page replacement policy?7

Locality to the Rescue!Recall that virtual memory works because of localityuu!Temporal and spatialWork at different scales: for cache, at a line level, for VM, atpage level, and even at larger scalesAll paging schemes depend on localityuuuWhat happens if a program does not have locality?High cost of paging is acceptable, if infrequentProcesses usually reference pages in localized patterns,making paging practical8

Evicting the Best Page!!Goal is to reduce the page fault rateThe best page to evict is the one never touched againu!Never is a long time, so picking the page closest to“never” is the next best thinguu!Will never fault on itEvicting the page that won’t be used for the longest period oftime minimizes the number of page faultsProved by BeladyWe’re now going to survey various replacementalgorithms, starting with Belady’s9

Belady’s Algorithm!Belady’s algorithmuuu!Idea: Replace the page that will not be used for the longesttime in the futureOptimal? How would you show?Problem: Have to predict the futureWhy is Belady’s useful then?uuUse it as a yardstick/upper boundCompare implementations of page replacement algorithmswith the optimal to gauge room for improvement» If optimal is not much better, then algorithm is pretty gooduWhat’s a good lower bound?» Random replacement is often the lower bound10

First-In First-Out (FIFO)!FIFO is an obvious algorithm and simple to implementuu!Why might this be good?u!Maybe the one brought in the longest ago is not being usedWhy might this be bad?uu!Maintain a list of pages in order in which they were paged inOn replacement, evict the one brought in longest time agoThen again, maybe it’s notWe don’t have any info to say one way or the otherFIFO suffers from “Belady’s Anomaly”uThe fault rate might actually increase when the algorithm isgiven more memory (very bad)11

Heuristic: Least frequentlyused!Keep track of whether a page is accessed since thelast page faultuIncrement a counter for each page that has been referencedwhen a page fault occurs» Infrequent operation, so overhead is okuWhen page fault occurs, remove the page with the lowestcounter» Least frequently used!Thoughts?uWhat if a page that used to be popular is no longer popular?» Age counter (reduce its value over time)12

Another heuristic – NotRecently Used!Keep track ofuu!whether a page has been referenced or notwhether it has been updated or not (updated page called dirty)When a page fault occurs, pick a page that has notbeen referenced to be victimuPrefer that victim pages are not dirty» If not dirty, we don’t have to save it back to swap!Periodically reset all the reference bits13

Least Recently Used (LRU)!LRU uses reference information to make a moreinformed replacement decisionuuu!Idea: We can’t predict the future, but we can make a guessbased upon past experienceOn replacement, evict the page that has not been used for thelongest time in the past (Belady’s: future)When does LRU do well? When does LRU do poorly?ImplementationuuTo be perfect, need to time stamp every reference (ormaintain a stack) – much too costlySo we need to approximate it14

Approximating LRU!LRU approximations use the PTE reference bituuKeep a counter for each pageAt regular intervals, for every page do:» If ref bit 0, increment counter» If ref bit 1, zero the counter» Zero the reference bituu!The counter will contain the number of intervals since the lastreference to the pageThe page with the largest counter is the least recently usedSome architectures don’t have a reference bituCan simulate reference bit using the valid bit to induce faults15

LRU Clock!Builds on Not Recently Used (NRU) – Used by UnixuuuReplace page that is “old enough”Arrange all of physical page frames in a big circle (clock)A clock hand is used to select a good LRU candidate» Sweep through the pages in circular order like a clock» If the ref bit is off, it hasn’t been used recently"What is the minimum “age” if ref bit is off?» If the ref bit is on, turn it off and go to next pageuuuArm moves quickly when pages are neededLow overhead when plenty of memoryIf memory is large, “accuracy” of information degrades» What does it degrade to?» One fix: use two hands (leading erase hand, trailing select hand)17

LRU ClockP3: 1P2: 1P3: 0P4: 0P1: 1P5: 1P8: 0P6: 0P7: 0P2: 0P4: 0P1: 0P5: 1P8: 1P6: 0P7: 018

Example: gcc Page Replace19

Example: Belady’s Anomaly20

Other ideas!Victim bufferuuuuAdd a buffer (death row!) we put a page on when we decide toreplace itBuffer is FIFOIf you get accessed while on death row – clemency!If you are the oldest page on death row – replacement!21

Fixed vs. Variable Space!!In a multiprogramming system, we need a way toallocate memory to competing processesProblem: How to determine how much memory to giveto each process?uFixed space algorithms» Each process is given a limit of pages it can use» When it reaches the limit, it replaces from its own pages» Local replacement"uSome processes may do well while others sufferVariable space algorithms» Process’ set of pages grows and shrinks dynamically» Global replacement"One process can ruin it for the restCSE 153 – Lecture 18/19 – Page Replacement22

Working Set Model!A working set of a process is used to model thedynamic locality of its memory usageu!Definitionuu!Defined by Peter Denning in 60sWS(t,w) {set of pages P, such that every page in P wasreferenced in the time interval (t, t-w)}t – time, w – working set window (measured in page refs)A page is in the working set (WS) only if it wasreferenced in the last w references23

Working Set Size!The working set size is the number of pages in theworking setu!The working set size changes with program localityuu!The number of pages referenced in the interval (t, t-w)During periods of poor locality, you reference more pagesWithin that period of time, the working set size is largerIntuitively, want the working set to be the set of pagesa process needs in memory to prevent heavy faultinguuEach process has a parameter w that determines a workingset with few faultsDenning: Don’t run a process unless working set is inmemory24

Example: gcc Working Set25

Working Set Problems!Problemsuu!Too hard to answeru!How do we determine w?How do we know when the working set changes?So, working set is not used in practice as a page replacementalgorithmHowever, it is still used as an abstractionuuThe intuition is still validWhen people ask, “How much memory does Firefox need?”,they are in effect asking for the size of Firefox’s working set26

Page Fault Frequency (PFF)!Page Fault Frequency (PFF) is a variable spacealgorithm that uses a more ad-hoc approachuuMonitor the fault rate for each processIf the fault rate is above a high threshold, give it more memory» So that it faults less» But not always (FIFO, Belady’s Anomaly)uIf the fault rate is below a low threshold, take away memory» Should fault more» But not always!Hard to use PFF to distinguish between changes inlocality and changes in size of working set27

Thrashing!Page replacement algorithms avoid thrashinguuuWhen most of the time is spent by the OS in paging data backand forth from diskNo time spent doing useful work (making progress)In this situation, the system is overcommitted» No idea which pages should be in memory to reduce faults» Could just be that there isn’t enough physical memory for all ofthe processes in the system» Ex: Running Windows95 with 4 MB of memory uPossible solutions» Swapping – write out all pages of a process» Buy more memory28

Summary!Page replacement algorithmsuuuBelady’s – optimal replacement (minimum # of faults)FIFO – replace page loaded furthest in pastLRU – replace page referenced furthest in past» Approximate using PTE reference bituuu!LRU Clock – replace page that is “old enough”Working Set – keep the set of pages in memory that hasminimal fault rate (the “working set”)Page Fault Frequency – grow/shrink page set as a function offault rateMultiprogramminguShould a process replace its own page, or that of another?29

Design of Operating Systems Winter 2022 Lecture 14/15: Memory Management (1) Some slides from Dave O'Hallaron. OS Abstractions 2 Operating System Hardware Applications . CSE 153 -Lecture 14 -Memory Management 55 Segmentation! Segmentation: partition memory into logically related units u Module, procedure, stack, data, file, etc.