CS241 System Programming Memory Management (V)ContentAdministrativeLRULeast Recently Used IssuesLRU and AnomaliesNFU: A LRU ApproximationSecond ChanceSecond Chance ExampleClock Page Replacement AlgorithmPage ClassesAd Hoc TechniquesFrame Allocation: MinimumEqual AllocationProportional AllocationLocal versus Global Allocation PoliciesSummaryCS241 System ProgrammingMemory Management (V)Klara NahrstedtLecture 324/12/200601/14/19 CS 241 - System Programming, Klara Nahrstedt2Content Replacement Policies–LRU–NFU–Second Chance–Clock Page AlgorithmDesign Issues for Paging Systems–Frame allocation policies01/14/19 CS 241 - System Programming, Klara Nahrstedt3Administrative MP4 is posted, due April 17, 2006Quiz 9 is April 14, 2006–Topics for Quiz 9:Basic memory management (T: Chapter 4.1)Swapping (T: Chapter 4.2) Paging (T: Chapter 4.3..1-4.3.3)01/14/19 CS 241 - System Programming, Klara Nahrstedt4LRU12 references, 10 faults01/14/19 CS 241 - System Programming, Klara Nahrstedt5Least Recently Used IssuesDoes not suffer from Belady's anomalyHow to track “recency”?–use time record time of reference with page table entryuse counter as clocksearch for smallest time. –use stack remove reference of page from stack (linked list)push it on top of stack both approaches require large processing overhead, more space, and hardware support.01/14/19 CS 241 - System Programming, Klara Nahrstedt6LRU and AnomaliesAnomalies cannot occur, why? 12 references, 8 faults01/14/19 CS 241 - System Programming, Klara Nahrstedt7NFU: A LRU ApproximationNFU (Not Frequently Used): Evict a page that is NOT frequently used;LRU: evict a page that is LEAST recently used;NFU Implementation: simpler than LRU–additional reference bits –a register is kept per page–a one bit is set in the register if the page is referenced–the register is shifted by one after some time interval–00110011 would be accessed more recently than 00010111–the page with register holding the lowest number is the least recently used.–the value may not be unique. use FIFO to resolve conflicts.01/14/19 CS 241 - System Programming, Klara Nahrstedt8Second ChanceOnly one reference bit in the page table entry. –0 initially –1 When a page is referencedpages are kept in FIFO order using a linked list.Choose “victim” to evict–Select head of FIFO–If page has reference bit (R ) set, reset bit and select next page in FIFO list.–keep processing until reach page with zero reference bit and page that one out.01/14/19 CS 241 - System Programming, Klara Nahrstedt9Second Chance Example12 references, 9 faults01/14/19 CS 241 - System Programming, Klara Nahrstedt10Clock Page Replacement AlgorithmSimilar to second chance, however –Keep all page frames on a circular list in the form of a clock ABCDEFGHIJCheck the R Bit, if R= 0, evict the page, if R=1, clear the bit and advance01/14/19 CS 241 - System Programming, Klara Nahrstedt11Page Classes1.(0,0) neither referenced nor dirtied2.(0,1) not referenced (recently) but dirtied3.(1,0) referenced but clean4.(1,1) referenced and dirtied select a page from lowest class if conflict, use random or FIFO.01/14/19 CS 241 - System Programming, Klara Nahrstedt12Ad Hoc TechniquesSeparate Page Out from Page In. –Keep a pool of free frames. –When a page is to be replaced, use a free frame. –Read the faulting page and restart the faulting process while page out is occurring. Write dirty pages to disk whenever the paging device is free and reset the dirty bit. This allows page replacement algorithms to replace clean pages. Cache paged out pages in primary memory. –Page out dirty pages as before. –Return pages to a free pool but remember which page frame they are. –If system needs to map page in again, reuse page. –If system needs to page in data, choose any page in pool. –System V, R4 implements this strategy01/14/19 CS 241 - System Programming, Klara Nahrstedt13Frame Allocation: MinimumHow are the page frames allocated to individual virtual memories in a multi- programmed environment? The simple case would be to allocate a minimum number of frames per process. –most instructions require two operands–include an extra page for paging out and one for paging in.–moves and indirection instructions might require more.01/14/19 CS 241 - System Programming, Klara Nahrstedt14Equal Allocationallocate an equal number of frames per job –but jobs use memory unequally–high priority jobs have same number of page frames and low priority jobs–degree of multiprogramming might vary01/14/19 CS 241 - System Programming, Klara Nahrstedt15Proportional Allocationallocate a number of frames per job proportional to job size –Challenge: how do you determine job size: by run command parameters or dynamically?01/14/19 CS 241 - System Programming, Klara Nahrstedt16Local versus Global Allocation PoliciesLocal allocation policy uses only a fixed fraction of memory from process’ own pages for allocating frames for each process.–Number of page frames assigned to each process is constantGlobal allocation policy uses page frames among all runnable processes–Number of page frames assigned to each process varies in time01/14/19 CS 241 - System Programming, Klara Nahrstedt17SummaryMostly used replacement algorithms in virtual memory systems can be found –second chance, clock page replacement, working set, and approximations of LRURead Chapter T: 4.4.1, 4.4.2, 4.4.3, 4.4.4, 4.4.5, 4.4.6, and
View Full Document