HW 3 due 11 10 Lecture 12 Demand Paging CSE 120 Principles of Operating Systems Alex C Snoeren Memory Management Last lecture on memory management Goals of memory management Mechanisms To provide a convenient abstraction for programming To allocate scarce memory resources among competing processes to maximize performance with minimal overhead Physical and virtual addressing 1 Techniques Partitioning paging segmentation 1 Page table management TLBs VM tricks 2 Policies Page replacement algorithms 3 2 CSE 120 Lecture 12 Lecture Overview Review paging and page replacement Survey page replacement algorithms Discuss local vs global replacement Discuss thrashing 3 CSE 120 Lecture 12 Locality All paging schemes depend on locality Temporal locality Locations referenced recently likely to be referenced again Spatial locality Processes reference pages in localized patterns Locations near recently referenced locations are likely to be referenced soon Although the cost of paging is high if it is infrequent enough it is acceptable Processes usually exhibit both kinds of locality during their execution making paging practical 4 CSE 120 Lecture 12 Demand Paging OS Recall demand paging from the OS perspective Pages are evicted to disk when memory is full Pages loaded from disk when referenced again References to evicted pages cause a TLB miss PTE was invalid causes fault OS allocates a page frame reads page from disk When I O completes the OS fills in PTE marks it valid and restarts faulting process Dirty vs clean pages Actually only dirty pages modified need to be written to disk Clean pages do not but you need to know where on disk to read them from again 5 CSE 120 Lecture 12 Demand Paging Process Demand paging is also used when a process first starts up When a process is created it has A brand new page table with all valid bits off No pages in memory When the process starts executing Instructions fault on code and data pages Faulting stops when all necessary code and data pages are in memory Only code and data needed by a process needs to be loaded This of course changes over time 6 CSE 120 Lecture 12 Page Replacement When a page fault occurs the OS loads the faulted page from disk into a page frame of memory At some point the process has used all of the page frames it is allowed to use When this happens the OS must replace a page for each page faulted in This is likely less than all of available memory It must evict a page to free up a page frame The page replacement algorithm determines how this is done And they come in all shapes and sizes 7 CSE 120 Lecture 12 Evicting the Best Page The goal of the replacement algorithm is to reduce the fault rate by selecting the best victim page to remove The best page to evict is the one never touched again Never is a long time so picking the page closest to never is the next best thing Will never fault on it Evicting the page that won t be used for the longest period of time minimizes the number of page faults Proved by Belady We re now going to survey various replacement algorithms starting with Belady s 8 CSE 120 Lecture 12 Belady s Algorithm Belady s algorithm is known as the optimal page replacement algorithm because it has the lowest fault rate for any page reference stream Idea Replace the page that will not be used for the longest time in the future Problem Have to predict the future Why is Belady s useful then Use it as a yardstick Compare implementations of page replacement algorithms with the optimal to gauge room for improvement If optimal is not much better then algorithm is pretty good If optimal is much better then algorithm could use some work Random replacement is often the lower bound 9 CSE 120 Lecture 12 First In First Out FIFO FIFO is an obvious algorithm and simple to implement Why might this be good Maybe the one brought in the longest ago is not being used Why might this be bad Maintain a list of pages in order in which they were paged in On replacement evict the one brought in longest time ago Then again maybe it s not We don t have any info to say one way or the other FIFO suffers from Belady s Anomaly The fault rate might actually increase when the algorithm is given more memory very bad 10 CSE 120 Lecture 12 Belady s Anomaly w FIFO Page References 1 2 3 4 1 2 5 1 2 3 4 5 1 1 3 3 1 1 5 5 2 2 4 4 12 1 1 2 2 4 4 2 2 1 1 4 4 4 2 2 2 1 3 3 3 1 1 1 5 5 2 2 2 2 1 3 1 1 3 3 5 5 5 5 1 1 3 3 2 2 2 4 5 5 4 4 1 1 1 5 9 3 3 3 2 2 2 2 4 4 4 4 3 3 3 11 CSE 120 Lecture 12 10 Least Recently Used LRU LRU uses reference information to make a more informed replacement decision Idea We can t predict the future but we can make a guess based upon past experience On replacement evict the page that has not been used for the longest time in the past Belady s future When does LRU do well When does LRU do poorly Implementation To be perfect need to time stamp every reference or maintain a stack much too costly So we need to approximate it 12 CSE 120 Lecture 12 Approximating LRU LRU approximations use the PTE reference bit Keep a counter for each page At regular intervals for every page do If ref bit 0 increment counter If ref bit 1 zero the counter Zero the reference bit The counter will contain the number of intervals since the last reference to the page The page with the largest counter is the least recently used Some architectures don t have a reference bit Can simulate reference bit using the valid bit to induce faults What happens when we make a page invalid 13 CSE 120 Lecture 12 LRU Clock Not Recently Used NRU Used by Unix Replace 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 page Arm moves quickly when pages are needed Low overhead when plenty of memory If memory is large accuracy of information degrades Use additional hands 14 CSE 120 Lecture 12 Fixed vs Variable Space In a multiprogramming system we need a way to allocate memory to competing processes Problem How to determine how much memory to give to each process Fixed space algorithms Each process is given …
View Full Document
Unlocking...