24 Page Replacement Lecture Notes PDF

Agenda November 19 – Lecture 24 Reminders Read 3 EP: Chapters 20 – 22 Virtual Memory Module 8 Project 4 – Driving Simulation using threads and concurrency Demo Due Wednesday 11/20 Project 5 – Implementing a Simple File System 3rd deliverable 11/20 Attendance Quiz Tomorrow...

Agenda November 19 – Lecture 24 Reminders Read 3 EP: Chapters 20 – 22 Virtual Memory Module 8 Project 4 – Driving Simulation using threads and concurrency Demo Due Wednesday 11/20 Project 5 – Implementing a Simple File System 3rd deliverable 11/20 Attendance Quiz Tomorrow 1 Last Time Demand Paging Page Replacement FIFO Optimal Today When poll is active respond at PollEv.com​/gkwatny9 Page Replacement Send gkwatny9 to 22333 FIFO Optimal LRU LRU Approximations Policies for managing memory allocation  FIFO Page Replacement Test Reference String 15 Faults  FIFO The algorithm is easy to implement, requiring only a single pointer to designate the oldest page in memory. When the page is replaced, the pointer is advanced to the next frame modulo n (# frames). FIFO Takes advantage of locality [a positive] In programs, most instructions execute sequentially Branch is very small % of instructions Likelihood of referencing page from distant past, diminishes with time Large data structures often referenced sequentially What could be the best we can do in terms of an algorithm?  MIN: Optimal Algorithm Replace page that will not be used for longest period of time 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 4 6 page 2 faults 3 4 5 How can you determine this when a program is running? Used for measuring how well your algorithm performs  MIN Page Replacement 9 Faults Since we cannot implement this, Can we approximate the behavior? Least Recently Used Replacement: LRU FIFO fails to recognize that a program does return to pages referenced in the distant past. replaces the oldest resident pages even if the pages have been referenced again recently In other words, ignores when a page is referenced LRU selects to remove from memory the page that has not been referenced for the longest time.  LRU Implementation An implementation uses a queue of length n, where n is the number of memory frames. The queue contains the page numbers of all resident pages. Whenever a resident page p is referenced, p is moved to the end of the queue. Result: the queue is always sorted - most recently used page to least recently used page. When there is a reference to a non-resident page p, p is moved to the end of the queue and the least recently referenced page q at the head of the queue is removed. Page p then replaces q in q’s memory frame. LRU Replacement Initially in Memory MRU LRU  Least Recently Used (LRU) Algorithm Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 1 1 1 5 2 2 2 2 2 Frame Contents 3 5 5 4 4 4 4 3 3 3 An Alternative Implementation requires determining time of use Counter (time reference) Every page entry has a time reference; each time a page is referenced through the PTE, copy the clock value into the PTE time reference When a page needs to be replaced, look at the time references to determine which are to be selected LRU Page Replacement 12 Faults FIFO 15 MIN (OPTIMAL) 9 How to Approximate LRU Replacement ? [LRU Approximates Optimal] What Information is “Collected” as a Process executes that we can use? The Page Table is our connection between Virtual Addresses & Physical Addresses  Which bits of a PTE entry are useful to us for LRU Algorithm(s)? Example: Intel PTE: Page Frame Number Free PCD PWT PTE: 0 D A UW P PS (Physical Page Number) (OS) 31-12 11-9 8 7 6 5 4 3 2 1 0 The “Present” bit (called “Valid” elsewhere): P==0: Page is not in memory/invalid and a reference will cause page fault P==1: Page frame number is in memory/valid and MMU is allowed to proceed with translation The “Writable” bit (could have opposite sense and be called “Read-only”): W==0: Page is read-only and cannot be written. W==1: Page can be written The “Accessed” bit (called “Used” or “Referenced”elsewhere): A==0: Page has not been accessed (or used) since last time software set A→0 A==1: Page has been accessed (or used) since last time software set A→0 The “Dirty” bit (called “Modified” elsewhere): D==0: Page has not been modified (written) since PTE was loaded D==1: Page has changed since PTE was loaded When to Apply Page Replacement A Page Fault Occurs There are no free frames Find a page to evict, retrieve its frame Keep most frequently used pages in memory based on usage history Clock Algorithms Use Page Table Entry bits (USE) & a circular list of pages A pointer moves through the list of pages like the “hand of a clock” moving around the clock face Only doing work at PF time Second chance Need a reference bit per page, and an ordered list of pages a ‘Clock replacement’ algorithm If page to be replaced (in ‘clock order’) has reference bit = 1 then: set reference bit to 0 leave page in memory check next page (in clock order), subject to same rules; replace if 0 Second-Chance (clock) Page-Replacement Algorithm  Enhanced 2nd Chance & Ad Hoc Use referenced and modified bits together to form a Priority for replacement. Still using circular list of pages RM 0, 0: neither used recently nor modified 0, 1: not used recently, but modified 1, 0: recently used but clean (not modified) 1, 1: recently used and modified Page Buffering LRU algorithms yield very good performance in minimizing page faults But, the overhead in implementation is high and hardware is required for some level of efficiency FIFO is simple to implement and requires no additional hardware, not even a Reference bit. How can we improve FIFO? Introduce a type of 2nd chance type policy.  Page Buffering Each process is given a maximum A replaced page is number of frames (Resident Set, not lost, but rather RS) to use and organized in a assigned to one of two in-memory lists FIFO list. When a process tries to exceed its RS (page fault), a page is removed, FIFO, and placed in a ‘clean list’ (M-bit 0) or a ‘dirty list’ of frames managed by OS Free page list Modified page list (M-bit 1) At a Page Fault: A frame is removed from clean frame list and added to the faulting list of page frames process. available for reading pages are written out in clusters An Example of Variable in pages Allocation, Global Scope Fetch Policy The Fetch Policy determines when a page should be brought into main memory Two Common alternatives & could be used together Demand Paging Prepaging Demand Paging only brings pages into main memory when a reference is made to a location on the page many page faults when process is first started principle of locality suggests that as more and more pages are brought in, most future references will be to pages that have recently been brought in, and page faults should drop to a very low level  Fetch Policy Prepaging (sometimes pages are organized in clusters of contiguous pages) pages other than the one demanded by a page fault are brought to memory exploits the characteristics of most secondary memory devices if pages of a process are stored contiguously in secondary memory it is more efficient to bring in a number of pages at one time ineffective if extra pages are not referenced once loaded in memory not to be confused with “swapping” Where the entire resident set is moved out and brought back when resumed  Resident Set Management The OS must decide how many pages to bring into main memory for a process The smaller the amount of memory allocated to each process, the more processes can reside in memory Trade-Offs Small number of pages loaded, increases # of page faults Beyond a certain size, further allocations of frames will not affect the page fault rate Resident Set => Set of pages of a process currently in physical memory  Policies for Resident Set Size Fixed-allocation Variable-allocation Gives a process a fixed Allows the number of number of frames in page frames allocated to main memory within a process to be varied which to execute over the lifetime of the process When a page fault occurs, one of the pages of that process must be replaced Replacement Scope The scope of a replacement strategy can be categorized as global or local For each type, replacement is activated by a page fault when there are no free page frames for the process Local Chooses only among the resident pages of the process that generated the page fault Global Considers all unlocked pages in main memory  Local Replacement Global Replacement Fixed Allocation Number of frames allocated Not possible. to a process is fixed. Page to be replaced is chosen from among the frames allocated to that process. Variable Allocation The number of frames Page to be replaced is chosen from allocated to a process may be all available frames in main changed from time to time to memory; this causes the size of the maintain the working set of resident set of processes to vary. the process. Page to be replaced is chosen from among the frames allocated to that process. Resident Set Management Policy