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 SizeFixed-allocation policyAllocates a fixed number of frames that remains constant over timeThe number is determined at load time and depends on the type of the application Variable-allocation policyThe number of frames allocated to a process may vary over timeMay increase if page fault rate is highMay decrease if page fault rate is very lowRequires more OS overhead to assess behavior of active processes3Replacement ScopeReplacement ScopeReplacement scope determines the set of frames to be considered for replacement when a page fault occursLocal replacement policyChooses only among the frames that are allocated to the process that issued the page faultGlobal replacement policyAny unlocked frame is a candidate for replacementLet us consider the possible combinations of replacement scope and resident set size policy4Fixed allocation and Local scopeFixed allocation and Local scopeEach process is allocated a fixed number of pages Determined at load time and depends on application typeWhen a page fault occurs, page frames considered for replacement are local to the page-fault processThe number of frames allocated is thus constantPrevious replacement algorithms can be usedProblem: difficult to determine ahead of time a good number for the allocated framesIf too low: page fault rate will be highIf too large: multiprogramming level will be low5Fixed allocation and Global scopeFixed allocation and Global scopeImpossible to achieveIf 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 ScopeSimple to implement--adopted by many OS (like Unix SVR4) A list of free frames is maintainedWhen a process issues a page fault, a free frame (from this list) is allocated to itHence the number of frames allocated to a page fault process increasesThe choice for the process that will loose a frame is arbitrary: far from optimalPage buffering can alleviate this problem since a page may be reclaimed if it is referenced again soon7Variable Allocation and Local ScopeVariable Allocation and Local ScopeMay 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 allocationWhen a page fault occurs, select the page to replace from the resident set of the process that suffers the faultReevaluate 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 referencesThe 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 unitsVirtual 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 DW(D,t) is an approximation of the program’s locality9The Working Set StrategyThe Working Set StrategyThe working set of a process first grows when it starts executing then stabilizes by the principle of localityIt grows again when the process enters a new locality (transition period)Up to a point where the working set contains pages from two localitiesIt then decreases after a sufficiently long time spent in the new locality10The Working Set StrategyThe Working Set StrategyThe working set concept suggests the following strategy to determine the resident set size:Monitor the working set for each processPeriodically remove from the resident set of a process those pages that are not in the working setWhen the resident set of a process is smaller than its working set, allocate more frames to itIf 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 StrategyPractical problems with this working set strategyMeasurement of the working set for each process is impracticalNecessary to time stamp the referenced page at every memory reference Necessary to maintain a time-ordered queue of referenced pages for each processThe 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 StrategyDefine an upper bound U and lower bound L for page fault ratesAllocate 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 WWe suspend the process if the PFF > U and no more free frames are available13Load ControlLoad ControlA working set or page fault frequency algorithm implicitly incorporates load controlOnly those processes whose resident set is sufficiently large are allowed to executeAnother approach is to adjust explicitly the multiprogramming level so that the mean time between page faults equals the time to process a page faultPerformance studies indicate that this is the point where processor usage is at maximum14Process SuspensionProcess SuspensionExplicit load control requires that we sometimes swap out (suspend) processesPossible victim selection criteria:Faulting processThis process may not have its working set in main memory so it will be blocked anywayLast process activatedThis process is least likely to have its working set residentProcess with smallest resident setThis process requires the least future effort to reloadLargest processThis yields the most free
View Full Document