DOC PREVIEW
U of I CS 241 - Memory Replacement Policies

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Memory Replacement PoliciesCS241 AdministrativeConcepts this LectureIntroduction to Demand Paging - Paging PoliciesDemand Paging ExamplePage Replacement AlgorithmPage ReplacementPage Replacement IssuesPage Replacement IssuesPage Replacement StrategiesTerminologyPage Replacement StrategiesPrincipal of OptimalityPrincipal of OptimalityOptimal ExampleFIFOPaging Behavior with Increasing Number of Page FramesBelady's Anomaly (for FIFO)LRULeast Recently Used IssuesLRU and AnomaliesNUR: A LRU ApproximationSecond ChanceSecond ChanceSecond Chance ExamplePage ClassesSummaryCS 241 Spring 2007System Programming1Memory Replacement PoliciesLecture 32Klara Nahrstedt2CS241 Administrative Read Stallings Chapter 8.1 and 8.2 about VM LMP2 (Part II due on Monday, April 16) See also lecture notes, self-assessment quiz, discussion section LMP2 quiz on Monday, April 16 If you found Dr. Cerf’s lecture interesting, you can Pay attention next two weeks in cs241 were we cover socket interfaces to TCP/IP - Internet Learn more about Internet material in classes cs438 (Communication Networking – TCP/IP), cs425 (Distributed Systems), ece435 (Computer Networking Lab – Implementation of TCP/IP), cs414 (Multimedia Systems), cs463 (Computer Security3Concepts this LectureIntroduction to Demand PagingReplacementPrinciple of Optimality Replacement Policies4Introduction to Demand Paging - Paging PoliciesFetch Strategies When should a page be brought into primary (main) memory from secondary (disk) storage. Placement StrategiesWhen a page is brought into primary storage, where is it to be put? Replacement StrategiesWhich page now in primary storage is to be removed from primary storage when some other page or segment is to be brought in and there is not enough room.5Demand Paging ExampleLoad MiFree framePagetableVMreffault6Page Replacement Algorithmfind a free page frame if free page frame use itotherwise, select a page frame using the page replacement algorithmwrite the selected page to the disk and update any necessary tables find location of page on diskread the requested page from the disk.restart the user process.7Page ReplacementIt is necessary to be careful of synchronization problems. For example, page faults may occur for pages being paged out.8Page Replacement Issuesif no frames are free, a disk read and write of page is requiredif the page to be replaced has not been changed since it was read in, it can be discarded and does not need to be copied out to secondary storage.read only pages are never written but may be shared!9Page Replacement Issuesa dirty bit is set in the page table by hardware to indicate that the page has been modified.need to minimize page faults.reference string is the memory references generated by a program.10Page Replacement Strategiesthe principle of optimalityreplace the page that will not be used again the farthest time in the future.random page replacementchoose a page randomlyFIFO - first in first outreplace the page that has been in primary memory the longest11TerminologyReference string: the memory reference sequence generated by a program. Paging – moving pages to (from) diskOptimal – the best (theoretical) strategyEviction – throwing something out Pollution – bringing in useless pages/lines12Page Replacement StrategiesLRU - least recently usedreplace the page not used for the longest timeLFU - least frequently usedreplace the page that is used least oftenNUR - not used recentlyan approximation to LRU.working setkeep in memory those pages that the process is actively using.13Principal of Optimalityprovides a basis for comparison with other schemes.is difficult to implement because of trying to predict the reference string for a program.compiler technology can help by providing hints.14Principal of Optimalityif the reference string can be predicted accurately, then shouldn't use demand paging but should use pre-paging instead as this would allow paging activity of pages needed in the future to be overlapped with computation.15Optimal Example12 references, 7 faults16FIFO12 references, 9 faults17Paging Behavior with IncreasingNumber of Page Frames18Belady's Anomaly (for FIFO)As the number of page frames increase, so does the fault rate.12 references, 10 faults19LRU12 references, 10 faults20Least Recently Used Issuesdoes not suffer from Belady's anomalyuse 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.21LRU and AnomaliesAnomalies cannot occur, why? 12 references, 8 faults22NUR: A LRU Approximationadditional reference bits a register is kept per pagea one bit is set in the register if the page is referencedthe register is shifted by one after some time interval00110011 would be accessed more recently than 00010111the page with register holding the lowest number is the least recently used.the value may not be unique. use fifo to resolve conflicts.23Second Chancesecond chance algorithm uses a register size one: a reference bit. the page table entry has a reference bitinitially, the reference bit for a page is set to 0when a page is referenced, the page is set to 1pages are kept in FIFO order using a circular list.select head of FIFO24Second Chanceif page has reference bit set, reset bit and select next page inFIFO list.keep processing until reach page with zero reference bit and page that one out.system v, r4 uses a variant of second chance.25Second Chance Example12 references, 9 faults26Page 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 classif conflict, use random or FIFO.27SummaryFetch, placement, page replacement.Demand paging algorithm.Simple page replacement policies. OptimalFIFO LRUNURSecond chance, page


View Full Document

U of I CS 241 - Memory Replacement Policies

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Memory Replacement Policies
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Memory Replacement Policies and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Memory Replacement Policies 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?