DOC PREVIEW
CORNELL CS 414 - Virtual Memory

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

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

Unformatted text preview:

Virtual MemoryResident Set SizeReplacement ScopeFixed allocation and Local scopeFixed allocation and Global scopeVariable Allocation and Global ScopeVariable Allocation and Local ScopeThe Working Set StrategyThe Working Set StrategySlide 10Slide 11The Page-Fault Frequency StrategyLoad ControlProcess Suspension1Virtual MemoryVirtual MemoryChapter 9Chapter 92Resident Set SizeResident Set SizeFixed-allocation policyAllocates a fixed number of frames that remains constant over timeThe number is determined at load time and depends on the type of the application Variable-allocation policyThe number of frames allocated to a process may vary over timeMay increase if page fault rate is highMay decrease if page fault rate is very lowRequires more OS overhead to assess behavior of active processes3Replacement ScopeReplacement ScopeReplacement scope determines the set of frames to be considered for replacement when a page fault occursLocal replacement policyChooses only among the frames that are allocated to the process that issued the page faultGlobal replacement policyAny unlocked frame is a candidate for replacementLet us consider the possible combinations of replacement scope and resident set size policy4Fixed allocation and Local scopeFixed allocation and Local scopeEach process is allocated a fixed number of pages Determined at load time and depends on application typeWhen a page fault occurs, page frames considered for replacement are local to the page-fault processThe number of frames allocated is thus constantPrevious replacement algorithms can be usedProblem: difficult to determine ahead of time a good number for the allocated framesIf too low: page fault rate will be highIf too large: multiprogramming level will be low5Fixed allocation and Global scopeFixed allocation and Global scopeImpossible to achieveIf all unlocked frames are candidate for replacement, the number of frames allocated to a process will necessary vary over time6Variable Allocation and Global ScopeVariable Allocation and Global ScopeSimple to implement--adopted by many OS (like Unix SVR4) A list of free frames is maintainedWhen a process issues a page fault, a free frame (from this list) is allocated to itHence the number of frames allocated to a page fault process increasesThe choice for the process that will loose a frame is arbitrary: far from optimalPage buffering can alleviate this problem since a page may be reclaimed if it is referenced again soon7Variable Allocation and Local ScopeVariable Allocation and Local ScopeMay be the best combination (used by Windows NT)Allocate at load time a certain number of frames to a new process based on application type Use either pre-paging or demand paging to fill up the allocationWhen a page fault occurs, select the page to replace from the resident set of the process that suffers the faultReevaluate periodically the allocation provided and increase or decrease it to improve overall performance8The Working Set Strategy The Working Set Strategy It is a variable-allocation method with local scope based on the assumption of locality of referencesThe working set for a process at time t, W(D,t), is the set of pages that have been referenced in the last D virtual time unitsVirtual time = time elapsed while the process was in execution (eg: number of instructions executed)D is a window of time At any t, |W(D,t)| is non decreasing with DW(D,t) is an approximation of the program’s locality9The Working Set StrategyThe Working Set StrategyThe working set of a process first grows when it starts executing then stabilizes by the principle of localityIt grows again when the process enters a new locality (transition period)Up to a point where the working set contains pages from two localitiesIt then decreases after a sufficiently long time spent in the new locality10The Working Set StrategyThe Working Set StrategyThe working set concept suggests the following strategy to determine the resident set size:Monitor the working set for each processPeriodically remove from the resident set of a process those pages that are not in the working setWhen the resident set of a process is smaller than its working set, allocate more frames to itIf not enough free frames are available, suspend the process (until more frames are available)•ie: a process may execute only if its working set is in main memory11The Working Set StrategyThe Working Set StrategyPractical problems with this working set strategyMeasurement of the working set for each process is impracticalNecessary to time stamp the referenced page at every memory reference Necessary to maintain a time-ordered queue of referenced pages for each processThe optimal value for D is unknown and varies with time Solution: rather than monitor the working set, monitor the page fault rate!12The Page-Fault Frequency StrategyThe Page-Fault Frequency StrategyDefine an upper bound U and lower bound L for page fault ratesAllocate more frames to a process if fault rate is higher than U Allocate less frames if fault rate is < L The resident set size should be close to the working set size WWe suspend the process if the PFF > U and no more free frames are available13Load ControlLoad ControlA working set or page fault frequency algorithm implicitly incorporates load controlOnly those processes whose resident set is sufficiently large are allowed to executeAnother approach is to adjust explicitly the multiprogramming level so that the mean time between page faults equals the time to process a page faultPerformance studies indicate that this is the point where processor usage is at maximum14Process SuspensionProcess SuspensionExplicit load control requires that we sometimes swap out (suspend) processesPossible victim selection criteria:Faulting processThis process may not have its working set in main memory so it will be blocked anywayLast process activatedThis process is least likely to have its working set residentProcess with smallest resident setThis process requires the least future effort to reloadLargest processThis yields the most free


View Full Document

CORNELL CS 414 - Virtual Memory

Documents in this Course
Security

Security

49 pages

Processes

Processes

24 pages

Deadlocks

Deadlocks

57 pages

Threads

Threads

5 pages

Threads

Threads

29 pages

Deadlocks

Deadlocks

36 pages

Load more
Download Virtual Memory
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 Virtual Memory 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 Virtual Memory 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?