DOC PREVIEW
U of I CS 241 - System Programming Memory Management

This preview shows page 1-2-3-4-5-6 out of 17 pages.

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

Unformatted text preview:

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 AlgorithmDesign Issues for Paging Systems–Frame allocation policies01/14/19 CS 241 - System Programming, Klara Nahrstedt3Administrative MP4 is posted, due April 17, 2006Quiz 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 IssuesDoes not suffer from Belady's anomalyHow to track “recency”?–use time record time of reference with page table entryuse counter as clocksearch 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 ApproximationNFU (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 ChanceOnly one reference bit in the page table entry. –0 initially –1 When a page is referencedpages 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 AlgorithmSimilar 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 TechniquesSeparate 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: MinimumHow 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 Allocationallocate 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 Allocationallocate 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 PoliciesLocal 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 constantGlobal 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 Nahrstedt17SummaryMostly used replacement algorithms in virtual memory systems can be found –second chance, clock page replacement, working set, and approximations of LRURead Chapter T: 4.4.1, 4.4.2, 4.4.3, 4.4.4, 4.4.5, 4.4.6, and


View Full Document

U of I CS 241 - System Programming Memory Management

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 System Programming Memory Management
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 System Programming Memory Management 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 System Programming Memory Management 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?