Memory Implementation IssuesCS241 AdministrativeContentsSecond Chance ExampleBasic Paging Process Implementation(1)Basic Paging Process Implementation(2)Frame Allocation for Multiple ProcessesMulti-Programming Frame AllocationMulti-Programming Frame AllocationThrashing: exposing the lie of VMPage Fault Rate vs. Size CurveWhy Thrashing?Results of ThrashingWhy?Solution: Working SetWorking set (1968, Denning)Working SetCalculating Working SetWorking Set in Action to Prevent ThrashingWorking sets of real programsWorking Set Implementation IssuesWorking Set ImplementationPage Fault Frequency Working SetPage Fault Frequency Working SetPage Size ConsiderationsMemory Mapped FilesMemory Mapped FilesMemory Mapped FilesPOSIX <sys/mman.h> Protection AttributesMap first 4kb of file and read intMap first 4kb of file and read intmunmapSummaryCS 241 Spring 2007System Programming1Memory Implementation IssuesLecture 33Klara Nahrstedt2CS241 Administrative Read Stallings Chapter 8.1 and 8.2 about VM LMP3 starts today Start Early!!!3ContentsBrief Discussion of Second Chance Replacement AlgorithmPaging basic process implementationFrame allocation for multiple processesThrashingWorking SetMemory-Mapped Files4Second Chance Example12 references, 9 faults5Basic Paging Process Implementation(1)Separate page out from page inKeep a pool of free frameswhen a page is to be replaced, use a free frameread the faulting page and restart the faulting process while page out is occurringWhy?Alternative: Before a frame is needed to read in the faulted page from disk, just evict a pageDisadvantage with alternative:A page fault may require 2 disk accesses: 1 for writing-out the evicted page, 1 for reading in the faulted page6Basic Paging Process Implementation(2)Paging outWrite dirty pages to disk whenever the paging device is free and reset the dirty bitBenefit?Remove the paging out (disk writes) process from the critical pathallows page replacement algorithms to replace clean pagesWhat should we do with paged out pages?Cache paged out pages in primary memory (giving it a second chance)Return paged-out pages to a free pool but remember which page frame they are.If system needs to map page in again, reuse page.7Frame Allocation for Multiple ProcessesHow are the page frames allocated to individual virtual memories of the various jobs running in a multi-programmed environment?. Simple solution Allocate a minimum number (??) of frames per process. One page from the current executed instructionMost instructions require two operandsinclude an extra page for paging out and one for paging in8Multi-Programming Frame AllocationSolution 2allocate an equal number of frames per job but jobs use memory unequallyhigh priority jobs have same number of page frames and low priority jobsdegree of multiprogramming might vary9Multi-Programming Frame AllocationSolution 3:allocate a number of frames per job proportional to job size how do you determine job size: by run command parameters or dynamically? Why multi-programming frame allocation is important?If not solved appropriately, it will result in a severe problem--- Thrashing10Thrashing: exposing the lie of VMThrashing: As page frames per VM space decrease, the page fault rate increases.Each time one page is brought in, another page, whose contents will soon be referenced, is thrown out.Processes will spend all of their time blocked, waiting for pages to be fetched from diskI/O devs at 100% utilization but system not getting much useful work doneMemory and CPU mostly idleReal memP1P2P311Page Fault Rate vs. Size Curve12Why Thrashing?Computations have localityAs page frames decrease, the page frames available are not large enough to contain the locality of the process.The processes start faulting heavilyPages that are read in, are used and immediately paged out.13Results of Thrashing14Why?As the page fault rate goes up, processes get suspended on page out queues for the disk.The system may try to optimize performance by starting new jobs.Starting new jobs will reduce the number of page frames available to each process, increasing the page fault requests.System throughput plunges.15Solution: Working SetMain ideafigure out how much memory does a process need to keep most the recent computation in memory with very few page faults? How?The working set model assumes locality the principle of locality states that a program clusters its access to data and text temporallyA recently accessed page is more likely to be accessed againThus, as the number of page frames increases above some threshold, the page fault rate will drop dramatically16Working set (1968, Denning)What we want to know: collection of pages process must have in order to avoid thrashingThis requires knowing the future. And our trick is?Working set:Pages referenced by process in last Τ seconds of execution considered to comprise its working setΤ : the working set parameterUsages of working set sizes?Cache partitioning: give each app enough space for WSPage replacement: preferentially discard non-WS pages Scheduling: process not executed unless WS in memory17Working SetAt least allocatethis many framesfor this process18Calculating Working Set12 references, 8 faults Window size is Ì19Working Set in Action to Prevent ThrashingAlgorithmif #free page frames > working set of some suspended processi, then activate processiand map in all its working setif working set size of some processkincreases and no page frame is free, suspend processkand release all its pages20Working sets of real programsTypical programs have phasesWorking set sizetransition, stable21Working Set Implementation IssuesMoving window over reference string used for determinationKeeping track of working set22Working Set ImplementationApproximate working set model using timer and reference bitSet timer to interrupt after approximately x references, τ.Remove pages that have not been referenced and reset reference bit.23Page Fault Frequency Working SetAnother approximation of pure working set Assume that if the working set is correct there will not be many page faults.If page fault rate increases beyond assumed knee of curve, then increase number of page frames available to process.If page fault rate decreases below foot of knee of curve, then decrease number of page frames available to process.24Page Fault Frequency Working Set25Page Size Considerationssmall pages require large page tableslarge pages imply significant amounts of page may not be
View Full Document
Unlocking...