DOC PREVIEW
U of I CS 241 - Memory Paging and Replacement

This preview shows page 1-2-22-23 out of 23 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 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 23 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 23 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 23 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 241 Fall 2007System Programming1Memory Paging and ReplacementLawrence Angrave2Concepts this LectureTwo-Level Paging ExampleInverted Page TableSharing and ProtectionIntroduction to Demand Paging3Multilevel PagingAddress of Size 4Bytes in32-bit ArchitectureAddress of Size 4Bytes In 32-bit ArchitectureMemory Space of Size 1 Byte4Addressing on Two-Level Page Table32-bit Architecture, 4096= 2^12 Bytes Page Size4K Page of Logical Memory has 4096 addressable bytesPage the Page Table with 4K pages as well 4K Page of Page Table has 1024 addressable 4byte addresses5Multilevel Paging and PerformanceSince each level is stored as a separate table inmemory, converting a logical address to aphysical one with a three-level page table maytake four memory accesses. Why?6Inverted Page Table7Inverted Page Table004 006005 00640101101Page TableVirtual Address (004006)Physical Address (005006)58Inverted Page Table ImplementationTLB is same as beforeTLB miss is handled by softwareIn-memory page table is managed using a hash tableNumber of entries ≥ number of physical framesNot found: page faultHash tableVirtual pagePhysical page9Inverted Page Tableone entry for each real page of memory.entry consists of the virtual address of the pagestored in that real memory location, withinformation about the process that owns thatpage.10Inverted Page TableDecreases memory needed to store each pagetable, but increases time needed to searchtable when a page reference occurs.Use hash table to limit the search to one -- or atmost a few page-table entries.11Sharing PagesCode and data can be shared by mapping theminto pages with common page frame mappings.Code and data must be position independent if VMmappings for the shared data are different.12Shared Pages13ProtectionCan add read, write, execute protection bits to page tableto protect memory.Check is done by hardware during access.Can give shared memory location different protections fromdifferent processes by having different page tableprotection access bits.14Page ProtectionLegend: reference - page has been accessed valid - page exists resident - page is cached in primary memory dirty - page has been changed since page in15Introduction to Demand Paging - PagingPoliciesFetch StrategiesWhen should a page be brought into primary (main)memory from secondary (disk) storage.Placement StrategiesWhen a page is brought into primary storage, where isit to be put?Replacement StrategiesWhich page now in primary storage is to be removedfrom primary storage when some other page orsegment is to be brought in and there is not enoughroom.16Demand PagingAlgorithm Never bring a page into primary memory until its needed.Page faultCheck if a valid virtual memory address. Kill job if not.If valid reference, check if its cached in memory already (perhapsfor some other process.) If so, skip to 7).Find a free page frame.Map address into disk block and fetch disk block into page frame.Suspend user process.When disk read finished, add vm mapping for page frame.If necessary, restart process.17Demand Paging ExampleLoad MiFree framePagetableVMreffault18Page ReplacementFind location of page on diskFind a free page frameIf free page frame use itOtherwise, select a page frame using the page replacementalgorithmWrite the selected page to the disk and update any necessarytablesRead the requested page from the disk.Restart the user process.It is necessary to be careful of synchronization problems.For example, page faults may occur for pages beingpaged out.19Issue: EvictionHopefully, kick out a less-useful pageDirty pages require writing, clean pages don’tHardware has a dirty bit for each page frame indicating this page hasbeen updated or notWhere do you write? To “swap space”Goal: kick out the page that’s least usefulProblem: how do you determine utility?Heuristic: temporal locality existsKick out pages that aren’t likely to be used again20TerminologyReference string: the memory referencesequence generated by a program.Paging – moving pages to (from) diskOptimal – the best (theoretical) strategyEviction – throwing something outPollution – bringing in useless pages/lines21Page Replacement StrategiesThe Principle of OptimalityReplace the page that will not be used again the farthest time in thefuture.Random page replacementChoose a page randomlyFIFO - First in First OutReplace the page that has been in primary memory the longestLRU - Least Recently UsedReplace the page that has not been used for the longest timeLFU - Least Frequently UsedReplace the page that is used least oftenNRU - Not Recently UsedAn approximation to LRU.Working SetKeep in memory those pages that the process is actively using.22Principal of OptimalityDescription:Assume that each page can be labeled with the number ofinstructions that will be executed before that page is firstreferences, i.e., we would know the future reference string fora program.Then the optimal page algorithm would choose the page with thehighest label to be removed from the memory.This algorithm provides a basis for comparison with otherschemes.Impractical because it needs future referencesIf future references are knownshould not use demand pagingshould use pre paging to allow paging to be overlapped withcomputation.23SummaryTwo Level PagingInverted Page TableSharing/ProtectionIntroduction to Demand PagingFetch PoliciesReplacement PoliciesPrinciple of


View Full Document

U of I CS 241 - Memory Paging and Replacement

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 Paging and Replacement
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 Paging and Replacement 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 Paging and Replacement 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?