Virtual Memory II: Thrashing Working Set Algorithm Dynamic Memory ManagementAnnouncementsLast TimeExample Page Replacement: LRU, =3Goals for todayThrashingApproach 1: Working SetWorking SetsWorking Set ApproximationUsing the Working SetTheoretical asideKey insight in proofHow do WSOpt and WS differ?How do WS and LRU compare?Approach 2: Page Fault FrequencyWorking Sets and Page Fault RatesOther Issues – Program StructureDynamic Memory Management: Contiguous Memory Allocation - Part IIAllocation and deallocationMemory allocation goalsMemory AllocatorImpossibility ResultsBest Fit AllocationBest Fit gone wrongA simple schemeWhich chunk to allocate?What happens on free?ExampleSlide 29Design featuresBuddy-Block SchemeSlide 32Slide 33How to get more space?SummaryVirtual Memory II: ThrashingWorking Set AlgorithmDynamic Memory Management2Announcements•Prelim this week:–Thursday March 8th, 7:30—9:00pm, 1½ hour exam–203 Phillips–Closed book, no calculators/PDAs/…–Bring ID•Make-up exam will be early Thursday morning, March 8th 8:30am-10:00am.–Three people signed up so far.•Topics: Everything up to (and including) Today, March 5th–Lectures 1-18, chapters 1-9 (7th ed)•Review Session:–Tomorrow, Tuesday, March 6th, during second half of 415 section•Homework 3 and Project 3 Design Doc due Today, March 5th–Make sure to look at the lecture schedule to keep up with due dates!3Last Time•We’ve focused on demand paging–Each process is allocated pages of memory–As a process executes it references pages–On a miss a page fault to the O/S occurs–The O/S pages in the missing page and pages out some target page if room is needed•The CPU maintains a cache of PTEs: the TLB.•The O/S must flushes the TLB before looking at page reference bits during context switching (because this changes the page table)4Example Page Replacement: LRU, =3R3 7 9 5 3 6 3 5 6 7 9 7 9 3 8 6 3 6 8 3 5 63 7 9 5 3 6 3 5 6 7 9 7 9 3 8 6 3 6 8 3 5 6S3 7 9 5 3 6 3 5 6 7 9 7 9 3 8 6 3 6 8 3 5 3 7 9 5 5 6 3 5 6 6 6 7 9 3 8 8 3 6 8 3In3 7 9 5 3 6 7 9 3 8 6 5 6Out 3 7 9 3 5 6 7 9 6 8R(t): Page referenced at time t. S(t): Memory state when finished doing the paging at time t. In(t): Page brought in, if any. Out(t): Page sent out. : None.Hit ratio: 9/19 = 47%Miss ratio: 10/19 = 53%While “filling” memory we are likely to get a page fault on almost every reference. Usually we don’t include these events when computing the hit ratio5Goals for today•Review demand paging•What is thrashing?•Solutions to thrashing–Approach 1: Working Set–Approach 2: Page fault frequency•Dynamic Memory Management–Memory allocation and deallocation and goals–Memory allocator - impossibility result•Best fit•Simple scheme - chunking, binning, and free•Buddy-block scheme•Other issues6Thrashing•Def: Excessive rate of paging that occurs because processes in system require more memory –Keep throwing out page that will be referenced soon–So, they keep accessing memory that is not there•Why does it occur?–Poor locality, past != future–There is reuse, but process does not fit–Too many processes in the system7Approach 1: Working Set•Peter Denning, 1968–He uses this term to denote memory locality of a programDef: pages referenced by process in last time-units comprise its working setFor our examples, we usually discuss WS in terms of , a “window” in the page reference string. But while this is easier on paper it makes less sense in practice! In real systems, the window should probably be a period of time, perhaps a second or two.8Working Sets•The working set size is num pages in the working set –the number of pages touched in the interval [t-Δ+1..t].•The working set size changes with program locality.–during periods of poor locality, you reference more pages.–Within that period of time, you will have a larger working set size.•Goal: keep WS for each process in memory.–E.g. If WSi for all i runnable processes > physical memory, then suspend a process9Working Set Approximation•Approximate with interval timer + a reference bit•Example: = 10,000–Timer interrupts after every 5000 time units–Keep in memory 2 bits for each page–Whenever a timer interrupts copy and sets the values of all reference bits to 0–If one of the bits in memory = 1 page in working set•Why is this not completely accurate?–Cannot tell (within interval of 5000) where reference occured•Improvement = 10 bits and interrupt every 1000 time units10Using the Working Set•Used mainly for prepaging–Pages in working set are a good approximation •In Windows processes have a max and min WS size–At least min pages of the process are in memory–If > max pages in memory, on page fault a page is replaced–Else if memory is available, then WS is increased on page fault–The max WS can be specified by the application11Theoretical aside•Denning defined a policy called WSOpt–In this, the working set is computed over the next references, not the last: R(t)..R(t+-1)•He compared WS with WSOpt.–WSOpt has knowledge of the future…–…yet even though WS is a practical algorithm with no ability to see the future, we can prove that the Hit and Miss ratio is identical for the two algorithms!12Key insight in proof•Basic idea is to look at the paging decision made in WS at time t+-1 and compare with the decision made by WSOpt at time t•Both look at the same references… hence make same decision–Namely, WSOpt tosses out page R(t-1) if it isn’t referenced “again” in time t..t+-1–WS running at time t+-1 tosses out page R(t-1) if it wasn’t referenced in times t...t+-113How do WSOpt and WS differ?•WS maintains more pages in memory, because it needs time “delay” to make a paging decision–In effect, it makes the same decisions, but it makes them after a time lag–Hence these pages hang around a bit longer14How do WS and LRU compare?•Suppose we use the same value of –WS removes pages if they aren’t referenced and hence keeps less pages in memory–When it does page things out, it is using an LRU policy!–LRU will keep all pages in memory, referenced or not•Thus LRU often has a lower miss rate, but needs more memory than WS15Approach 2: Page Fault Frequency•Thrashing viewed as poor ratio of fetch to work•PFF = page
View Full Document
Unlocking...