英文python讲解辅导、辅导外文pythonPolicies

Beyond Physical Memory: PoliciesIn a virtual memory manager, life is easy when you have a lot of freememory. A page fault occurs, you find a free page on the free-page list,and assign it to the faulting page. Hey, Operating System, congratulations!You did it again.Unfortunately, things get a little more interesting when little memoryis free. In such a case, this memory pressure forces the OS to start pagingout pages to make room for actively-used pages. Deciding which page(or pages) to evict is encapsulated within the replacement policy of theOS; historically, it was one of the most important decisions the early virtualmemory systems made, as older systems had little physical memory.Minimally, it is an interesting set of policies worth knowing a little moreabout. And thus our problem:THE CRUX: HOW TO DECIDE WHICH PAGE TO EVICTHow can the OS decide which page (or pages) to evict from memory?This decision is made by the replacement policy of the system, which usuallyfollows some general principles (discussed below) but also includescertain tweaks to avoid corner-case behaviors.22.1 Cache ManagementBefore diving into policies, we first describe the problem we are tryingto solve in more detail. Given that main memory holds some subset ofall the pages in the system, it can rightly be viewed as a cache for virtualmemory pages in the system. Thus, our goal in picking a replacementpolicy for this cache is to minimize the number of cache misses, i.e., tominimize the number of times that we have to fetch a page from disk.Alternately, one can view our goal as maximizing the number of cachehits, i.e., the number of times a page that is accessed is found in memory.Knowing the number of cache hits and misses let us calculate the averagememory access time (AMAT) for a program (a metric computerarchitects compute for hardware caches [HP06]). Specifically, given thesevalues, we can compute the AMAT of a program as follows:AMAT = TM + (PMiss · TD) (22.1)12 BEYOND PHYSICAL MEMORY: POLICIESwhere TM represents the cost of accessing memory, TD the cost of accessingdisk, and PMiss the probability of not finding the data in thecache (a miss); PMiss varies from 0.0 to 1.0, and sometimes we refer toa percent miss rate instead of a probability (e.g., a 10% miss rate meansPMiss = 0.10). Note you always pay the cost of accessing the data inmemory; when you miss, however, you must additionally pay the cost offetching the data from disk.For example, let us imagine a machine with a (tiny) address space:4KB, with 256-byte pages. Thus, a virtual address has two components: a4-bit VPN (the most-significant bits) and an 8-bit offset (the least-significantbits). Thus, a process in this example can access 24or 16 total virtualpages. In this example, the process generates the following memory references(i.e., virtual addresses): 0x000, 0x100, 0x200, 0x300, 0x400, 0x500,0x600, 0x700, 0x800, 0x900. These virtual addresses refer to the first byteof each of the first ten pages of the address space (the page number beingthe first hex digit of each virtual address).Let us further assume that every page except virtual page 3 is alreadyin memory. Thus, our sequence of memory references will encounter thefollowing behavior: hit, hit, hit, miss, hit, hit, hit, hit, hit, hit. We cancompute the hit rate (the percent of references found in memory): 90%, as9 out of 10 references are in memory. The miss rate is thus 10% (PMiss =0.1). In general, PHit + PMiss = 1.0; hit rate plus miss rate sum to 100%.To calculate AMAT, we need to know the cost of accessing memoryand the cost of accessing disk. Assuming the cost of accessing memory(TM) is around 100 nanoseconds, and the cost of accessing disk (TD) isabout 10 milliseconds, we have the following AMAT: 100ns + 0.1 · 10ms,which is 100ns + 1ms, or 1.0001 ms, or about 1 millisecond. If our hitrate had instead been 99.9% (Pmiss = 0.001), the result is quite different:AMAT is 10.1 microseconds, or roughly 100 times faster. As the hit rateapproaches 100%, AMAT approaches 100 nanoseconds.Unfortunately, as you can see in this example, the cost of disk accessis so high in modern systems that even a tiny miss rate will quickly dominatethe overall AMAT of running programs. Clearly, we need to avoidas many misses as possible or run slowly, at the rate of the disk. One wayto help with this is to carefully develop a smart policy, as we now do.22.2 The Optimal Replacement PolicyTo better understand how a particular replacement policy works, itwould be nice to compare it to the best possible replacement policy. As itturns out, such an optimal policy was developed by Belady many yearsago [B66] (he originally called it MIN). The optimal replacement policyleads to the fewest number of misses overall. Belady showed that a simple(but, unfortunately, difficult to implement!) approach that replacesthe page that will be accessed furthest in the future is the optimal policy,resulting in the fewest-possible cache misses.OPERATINGSYSTEMS[VERSION 0.92] WWW.OSTEP.ORGBEYOND PHYSICAL MEMORY: POLICIES 3TIP: COMPARING AGAINST OPTIMAL IS USEFULAlthough optimal is not very practical as a real policy, it is incrediblyuseful as a comparison point in simulation or other studies. Saying thatyour fancy new algorithm has a 80% hit rate isn’t meaningful in isolation;saying that optimal achieves an 82% hit rate (and thus your new approachis quite close to optimal) makes the result more meaningful and gives itcontext. Thus, in any study you perform, knowing what the optimal islets you perform a better comparison, showing how much improvementis still possible, and also when you can stop making your policy better,because it is close enough to the ideal [AD03].Hopefully, the intuition behind the optimal policy makes sense. Thinkabout it like this: if you have to throw out some page, why not throwout the one that is needed the furthest from now? By doing so, you areessentially saying that all the other pages in the cache are more importantthan the one furthest out. The reason this is true is simple: you will referto the other pages before you refer to the one furthest out.Let’s trace through a simple example to understand the decisions theoptimal policy makes. Assume a program accesses the following streamof virtual pages: 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1. Figure 22.1 shows the behaviorof optimal, assuming a cache that fits three pages.In the figure, you can see the following actions. Not surprisingly, thefirst three accesses are misses, as the cache begins in an empty state; sucha miss is sometimes referred to as a cold-start miss (or compulsory miss).Then we refer again to pages 0 and 1, which both hit in the cache. Finally,we reach another miss (to page 3), but this time the cache is full; a replacementmust take place! Which begs the question: which page shouldwe replace? With the optimal policy, we examine the future for each pagecurrently in the cache (0, 1, and 2), and see that 0 is accessed almost immediately,1 is accessed a little later, and 2 is accessed furthest in the future.Thus the optimal policy has an easy choice: evict page 2, resulting inpages 0, 1, and 3 in the cache. The next three references are hits, but thenResultingAccess Hit/Miss? Evict Cache State0 Miss 01 Miss 0, 12 Miss 0, 1, 20 Hit 0, 1, 21 Hit 0, 1, 23 Miss 2 0, 1, 30 Hit 0, 1, 33 Hit 0, 1, 31 Hit 0, 1, 32 Miss 3 0, 1, 21 Hit 0, 1, 2Figure 22.1: Tracing The Optimal Policyc 2014, ARPACI-DUSSEAUTHREEEASYPIECES4 BEYOND PHYSICAL MEMORY: POLICIESASIDE: TYPES OF CACHE MISSESIn the computer architecture world, architects sometimes find it usefulto characterize misses by type, into one of three categories: compulsory,capacity, and conflict misses, sometimes called the Three C’s [H87]. Acompulsory miss (or cold-start miss [EF78]) occurs because the cache isempty to begin with and this is the first reference to the item; in contrast,a capacity miss occurs because the cache ran out of space and hadto evict an item to bring a new item into the cache. The third type ofmiss (a conflict miss) arises in hardware because of limits on where anitem can be placed in a hardware cache, due to something known as setassociativity;it does not arise in the OS page cache because such cachesare always fully-associative, i.e., there are no restrictions on where inmemory a page can be placed. See H&P for details [HP06].we get to page 2, which we evicted long ago, and suffer another miss.Here the optimal policy again examines the future for each page in thecache (0, 1, and 3), and sees that as long as it doesn’t evict page 1 (whichis about to be accessed), we’ll be OK. The example shows page 3 gettingevicted, although 0 would have been a fine choice too. Finally, we hit onpage 1 and the trace completes.We can also calculate the hit rate for the cache: with 6 hits and 5 misses,the hit rate is HitsHits+Misses which is 66+5 or 54.5%. You can also computethe hit rate modulo compulsory misses (i.e., ignore the first miss to a givenpage), resulting in a 85.7% hit rate.Unfortunately, as we saw before in the development of schedulingpolicies, the future is not generally known; you can’t build the optimalpolicy for a general-purpose operating system1. Thus, in developing areal, deployable policy, we will focus on approaches that find some otherway to decide which page to evict. The optimal policy will thus serveonly as a comparison point, to know how close we are to “perfect”.22.3 A Simple Policy: FIFOMany early systems avoided the complexity of trying to approachoptimal and employed very simple replacement policies. For example,some systems used FIFO (first-in, first-out) replacement, where pageswere simply placed in a queue when they enter the system; when a replacementoccurs, the page on the tail of the queue (the “first-in” page) isevicted. FIFO has one great strength: it is quite simple to implement.Let’s examine how FIFO does on our example reference stream (Figure22.2, page 5). We again begin our trace with three compulsory misses topages 0, 1, and 2, and then hit on both 0 and 1. Next, page 3 is referenced,causing a miss; the replacement decision is easy with FIFO: pick the page1If you can, let us know! We can become rich together. Or, like the scientists who “discovered”cold fusion, widely scorned and mocked [FP89].OPERATINGSYSTEMS[VERSION 0.92] WWW.OSTEP.ORGBEYOND PHYSICAL MEMORY: POLICIES 5ResultingAccess Hit/Miss? Evict Cache State0 Miss First-in→ 01 Miss First-in→ 0, 12 Miss First-in→ 0, 1, 20 Hit First-in→ 0, 1, 21 Hit First-in→ 0, 1, 23 Miss 0 First-in→ 1, 2, 30 Miss 1 First-in→ 2, 3, 03 Hit First-in→ 2, 3, 01 Miss 2 First-in→ 3, 0, 12 Miss 3 First-in→ 0, 1, 21 Hit First-in→ 0, 1, 2Figure 22.2: Tracing The FIFO Policythat was the “first one” in (the cache state in the figure is kept in FIFOorder, with the first-in page on the left), which is page 0. Unfortunately,our next access is to page 0, causing another miss and replacement (ofpage 1). We then hit on page 3, but miss on 1 and 2, and finally hit on 3.Comparing FIFO to optimal, FIFO does notably worse: a 36.4% hitrate (or 57.1% excluding compulsory misses). FIFO simply can’t determinethe importance of blocks: even though page 0 had been accesseda number of times, FIFO still kicks it out, simply because it was the firstone brought into memory.ASIDE: BELADY’S ANOMALYBelady (of the optimal policy) and colleagues found an interesting referencestream that behaved a little unexpectedly [BNS69]. The memoryreferencestream: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. The replacement policythey were studying was FIFO. The interesting part: how the cache hitrate changed when moving from a cache size of 3 to 4 pages.In general, you would expect the cache hit rate to increase (get better)when the cache gets larger. But in this case, with FIFO, it gets worse! Calculatethe hits and misses yourself and see. This odd behavior is generallyreferred to as Belady’s Anomaly (to the chagrin of his co-authors).Some other policies, such as LRU, don’t suffer from this problem. Canyou guess why? As it turns out, LRU has what is known as a stack property[M+70]. For algorithms with this property, a cache of size N + 1naturally includes the contents of a cache of size N. Thus, when increasingthe cache size, hit rate will either stay the same or improve. FIFO andRandom (among others) clearly do not obey the stack property, and thusare susceptible to anomalous behavior.c 2014, ARPACI-DUSSEAUTHREEEASYPIECES6 BEYOND PHYSICAL MEMORY: POLICIESResultingAccess Hit/Miss? Evict Cache State0 Miss 01 Miss 0, 12 Miss 0, 1, 20 Hit 0, 1, 21 Hit 0, 1, 23 Miss 0 1, 2, 30 Miss 1 2, 3, 03 Hit 2, 3, 01 Miss 3 2, 0, 12 Hit 2, 0, 11 Hit 2, 0, 1Figure 22.3: Tracing The Random Policy22.4 Another Simple Policy: RandomAnother similar replacement policy is Random, which simply picks arandom page to replace under memory pressure. Random has propertiessimilar to FIFO; it is simple to implement, but it doesn’t really try to betoo intelligent in picking which blocks to evict. Let’s look at how Randomdoes on our famous example reference stream (see Figure 22.3).Of course, how Random does depends entirely upon how lucky (orunlucky) Random gets in its choices. In the example above, Random doesa little better than FIFO, and a little worse than optimal. In fact, we canrun the Random experiment thousands of times and determine how itdoes in general. Figure 22.4 shows how many hits Random achieves over10,000 trials, each with a different random seed. As you can see, sometimes(just over 40% of the time), Random is as good as optimal, achieving6 hits on the example trace; sometimes it does much worse, achieving 2hits or fewer. How Random does depends on the luck of the draw.0 1 2 3 4 5 6 701020304050Number of HitsFrequencyFigure 22.4: Random Performance Over 10,000 TrialsOPERATINGSYSTEMS[VERSION 0.92] WWW.OSTEP.ORGBEYOND PHYSICAL MEMORY: POLICIES 7ResultingAccess Hit/Miss? Evict Cache State0 Miss LRU→ 01 Miss LRU→ 0, 12 Miss LRU→ 0, 1, 20 Hit LRU→ 1, 2, 01 Hit LRU→ 2, 0, 13 Miss 2 LRU→ 0, 1, 30 Hit LRU→ 1, 3, 03 Hit LRU→ 1, 0, 31 Hit LRU→ 0, 3, 12 Miss 0 LRU→ 3, 1, 21 Hit LRU→ 3, 2, 1Figure 22.5: Tracing The LRU Policy22.5 Using History: LRUUnfortunately, any policy as simple as FIFO or Random is likely tohave a common problem: it might kick out an important page, one thatis about to be referenced again. FIFO kicks out the page that was firstbrought in; if this happens to be a page with important code or datastructures upon it, it gets thrown out anyhow, even though it will soon bepaged back in. Thus, FIFO, Random, and similar policies are not likely toapproach optimal; something smarter is needed.As we did with scheduling policy, to improve our guess at the future,we once again lean on the past and use history as our guide. For example,if a program has accessed a page in the near past, it is likely to access itagain in the near future.One type of historical information a page-replacement policy coulduse is frequency; if a page has been accessed many times, perhaps itshould not be replaced as it clearly has some value. A more commonlyusedproperty of a page is its recency of access; the more recently a pagehas been accessed, perhaps the more likely it will be accessed again.This family of policies is based on what people refer to as the principleof locality [D70], which basically is just an observation about programsand their behavior. What this principle says, quite simply, is thatprograms tend to access certain code sequences (e.g., in a loop) and datastructures (e.g., an array accessed by the loop) quite frequently; we shouldthus try to use history to figure out which pages are important, and keepthose pages in memory when it comes to eviction time.And thus, a family of simple historically-based algorithms are born.The Least-Frequently-Used (LFU) policy replaces the least-frequentlyusedpage when an eviction must take place. Similarly, the Least-RecentlyUsed(LRU) policy replaces the least-recently-used page. These algorithmsare easy to remember: once you know the name, you know exactlywhat it does, which is an excellent property for a name.To better understand LRU, let’s examine how LRU does on our examc 2014, ARPACI-DUSSEAUTHREEEASYPIECES8 BEYOND PHYSICAL MEMORY: POLICIESASIDE: TYPES OF LOCALITYThere are two types of locality that programs tend to exhibit. The firstis known as spatial locality, which states that if a page P is accessed,it is likely the pages around it (say P − 1 or P + 1) will also likely beaccessed. The second is temporal locality, which states that pages thathave been accessed in the near past are likely to be accessed again in thenear future. The assumption of the presence of these types of localityplays a large role in the caching hierarchies of hardware systems, whichdeploy many levels of instruction, data, and address-translation cachingto help programs run fast when such locality exists.Of course, the principle of locality, as it is often called, is no hard-andfastrule that all programs must obey. Indeed, some programs accessmemory (or disk) in rather random fashion and don’t exhibit much orany locality in their access streams. Thus, while locality is a good thing tokeep in mind while designing caches of any kind (hardware or software),it does not guarantee success. Rather, it is a heuristic that often provesuseful in the design of computer systems.ple reference stream. Figure 22.5 (page 7) shows the results. From thefigure, you can see how LRU can use history to do better than statelesspolicies such as Random or FIFO. In the example, LRU evicts page 2 whenit first has to replace a page, because 0 and 1 have been accessed more recently.It then replaces page 0 because 1 and 3 have been accessed morerecently. In both cases, LRU’s decision, based on history, turns out to becorrect, and the next references are thus hits. Thus, in our simple example,LRU does as well as possible, matching optimal in its performance2.We should also note that the opposites of these algorithms exist: MostFrequently-Used(MFU) and Most-Recently-Used (MRU). In most cases(not all!), these policies do not work well, as they ignore the locality mostprograms exhibit instead of embracing it.22.6 Workload ExamplesLet’s look at a few more examples in order to better understand howsome of these policies behave. Here, we’ll examine more complex workloadsinstead of small traces. However, even these workloads are greatlysimplified; a better study would include application traces.Our first workload has no locality, which means that each referenceis to a random page within the set of accessed pages. In this simple example,the workload accesses 100 unique pages over time, choosing thenext page to refer to at random; overall, 10,000 pages are accessed. In theexperiment, we vary the cache size from very small (1 page) to enoughto hold all the unique pages (100 page), in order to see how each policybehaves over the range of cache sizes.2OK, we cooked the results. But sometimes cooking is necessary to prove a point.OPERATINGSYSTEMS[VERSION 0.92] WWW.OSTEP.ORGBEYOND PHYSICAL MEMORY: POLICIES 90 20 40 60 80 1000%20%40%60%80%100%The No-Locality WorkloadCache Size (Blocks)Hit RateOPTLRUFIFORANDFigure 22.6: The No-Locality WorkloadFigure 22.6 plots the results of the experiment for optimal, LRU, Random,and FIFO. The y-axis of the figure shows the hit rate that each policyachieves; the x-axis varies the cache size as described above.We can draw a number of conclusions from the graph. First, whenthere is no locality in the workload, it doesn’t matter much which realisticpolicy you are using; LRU, FIFO, and Random all perform the same, withthe hit rate exactly determined by the size of the cache. Second, whenthe cache is large enough to fit the entire workload, it also doesn’t matterwhich policy you use; all policies (even Random) converge to a 100% hitrate when all the referenced blocks fit in cache. Finally, you can see thatoptimal performs noticeably better than the realistic policies; peeking intothe future, if it were possible, does a much better job of replacement.The next workload we examine is called the “80-20” workload, whichexhibits locality: 80% of the references are made to 20% of the pages (the“hot” pages); the remaining 20% of the references are made to the remaining80% of the pages (the “cold” pages). In our workload, there area total 100 unique pages again; thus, “hot” pages are referred to most ofthe time, and “cold” pages the remainder. Figure 22.7 (page 10) showshow the policies perform with this workload.As you can see from the figure, while both random and FIFO do reasonablywell, LRU does better, as it is more likely to hold onto the hotpages; as those pages have been referred to frequently in the past, theyare likely to be referred to again in the near future. Optimal once againdoes better, showing that LRU’s historical information is not perfect.c 2014, ARPACI-DUSSEAUTHREEEASYPIECES10 BEYOND PHYSICAL MEMORY: POLICIES0 20 40 60 80 1000%20%40%60%80%100%The 80-20 WorkloadCache Size (Blocks)Hit RateOPTLRUFIFORANDFigure 22.7: The 80-20 WorkloadYou might now be wondering: is LRU’s improvement over Randomand FIFO really that big of a deal? The answer, as usual, is “it depends.” Ifeach miss is very costly (not uncommon), then even a small increase in hitrate (reduction in miss rate) can make a huge difference on performance.If misses are not so costly, then of course the benefits possible with LRUare not nearly as important.Let’s look at one final workload. We call this one the “looping sequential”workload, as in it, we refer to 50 pages in sequence, starting at 0,then 1, ..., up to page 49, and then we loop, repeating those accesses, for atotal of 10,000 accesses to 50 unique pages. The last graph in Figure 22.8shows the behavior of the policies under this workload.This workload, common in many applications (including importantcommercial applications such as databases [CD85]), represents a worstcasefor both LRU and FIFO. These algorithms, under a looping-sequentialworkload, kick out older pages; unfortunately, due to the looping natureof the workload, these older pages are going to be accessed sooner thanthe pages that the policies prefer to keep in cache. Indeed, even witha cache of size 49, a looping-sequential workload of 50 pages results ina 0% hit rate. Interestingly, Random fares notably better, not quite approachingoptimal, but at least achieving a non-zero hit rate. Turns outthat random has some nice properties; one such property is not havingweird corner-case behaviors.OPERATINGSYSTEMS[VERSION 0.92] WWW.OSTEP.ORGBEYOND PHYSICAL MEMORY: POLICIES 110 20 40 60 80 1000%20%40%60%80%100%The Looping-Sequential WorkloadCache Size (Blocks)Hit RateOPTLRUFIFORANDFigure 22.8: The Looping Workload22.7 Implementing Historical AlgorithmsAs you can see, an algorithm such as LRU can generally do a betterjob than simpler policies like FIFO or Random, which may throw outimportant pages. Unfortunately, historical policies present us with a newchallenge: how do we implement them?Let’s take, for example, LRU. To implement it perfectly, we need todo a lot of work. Specifically, upon each page access (i.e., each memoryaccess, whether an instruction fetch or a load or store), we must updatesome data structure to move this page to the front of the list (i.e., theMRU side). Contrast this to FIFO, where the FIFO list of pages is onlyaccessed when a page is evicted (by removing the first-in page) or when anew page is added to the list (to the last-in side). To keep track of whichpages have been least- and most-recently used, the system has to do someaccounting work on every memory reference. Clearly, without great care,such accounting could greatly reduce performance.One method that could help speed this up is to add a little bit of hardwaresupport. For example, a machine could update, on each page access,a time field in memory (for example, this could be in the per-process pagetable, or just in some separate array in memory, with one entry per physicalpage of the system). Thus, when a page is accessed, the time fieldwould be set, by hardware, to the current time. Then, when replacing apage, the OS could simply scan all the time fields in the system to find theleast-recently-used page.c 2014, ARPACI-DUSSEAUTHREEEASYPIECES12 BEYOND PHYSICAL MEMORY: POLICIESUnfortunately, as the number of pages in a system grows, scanning ahuge array of times just to find the absolute least-recently-used page isprohibitively expensive. Imagine a modern machine with 4GB of memory,chopped into 4KB pages. This machine has 1 million pages, and thusfinding the LRU page will take a long time, even at modern CPU speeds.Which begs the question: do we really need to find the absolute oldestpage to replace? Can we instead survive with an approximation?CRUX: HOW TO IMPLEMENT AN LRU REPLACEMENT POLICYGiven that it will be expensive to implement perfect LRU, can we approximateit in some way, and still obtain the desired behavior?22.8 Approximating LRUAs it turns out, the answer is yes: approximating LRU is more feasiblefrom a computational-overhead standpoint, and indeed it is whatmany modern systems do. The idea requires some hardware support,in the form of a use bit (sometimes called the reference bit), the first ofwhich was implemented in the first system with paging, the Atlas onelevelstore [KE+62]. There is one use bit per page of the system, and theuse bits live in memory somewhere (they could be in the per-process pagetables, for example, or just in an array somewhere). Whenever a page isreferenced (i.e., read or written), the use bit is set by hardware to 1. Thehardware never clears the bit, though (i.e., sets it to 0); that is the responsibilityof the OS.How does the OS employ the use bit to approximate LRU? Well, therecould be a lot of ways, but with the clock algorithm [C69], one simpleapproach was suggested. Imagine all the pages of the system arranged ina circular list. A clock hand points to some particular page to begin with(it doesn’t really matter which). When a replacement must occur, the OSchecks if the currently-pointed to page P has a use bit of 1 or 0. If 1, thisimplies that page P was recently used and thus is not a good candidatefor replacement. Thus, the use bit for P set to 0 (cleared), and the clockhand is incremented to the next page (P + 1). The algorithm continuesuntil it finds a use bit that is set to 0, implying this page has not beenrecently used (or, in the worst case, that all pages have been and that wehave now searched through the entire set of pages, clearing all the bits).Note that this approach is not the only way to employ a use bit toapproximate LRU. Indeed, any approach which periodically clears theuse bits and then differentiates between which pages have use bits of 1versus 0 to decide which to replace would be fine. The clock algorithm ofCorbato’s was just one early approach which met with some success, andhad the nice property of not repeatedly scanning through all of memorylooking for an unused page.OPERATINGSYSTEMS[VERSION 0.92] WWW.OSTEP.ORGBEYOND PHYSICAL MEMORY: POLICIES 130 20 40 60 80 1000%20%40%60%80%100%The 80-20 WorkloadCache Size (Blocks)Hit RateOPTLRUFIFORANDClockFigure 22.9: The 80-20 Workload With ClockThe behavior of a clock algorithm variant is shown in Figure 22.9. Thisvariant randomly scans pages when doing a replacement; when it encountersa page with a reference bit set to 1, it clears the bit (i.e., sets itto 0); when it finds a page with the reference bit set to 0, it chooses it asits victim. As you can see, although it doesn’t do quite as well as perfectLRU, it does better than approaches that don’t consider history at all.22.9 Considering Dirty PagesOne small modification to the clock algorithm (also originally suggestedby Corbato [C69]) that is commonly made is the additional considerationof whether a page has been modified or not while in memory.The reason for this: if a page has been modified and is thus dirty, it mustbe written back to disk to evict it, which is expensive. If it has not beenmodified (and is thus clean), the eviction is free; the physical frame cansimply be reused for other purposes without additional I/O. Thus, someVM systems prefer to evict clean pages over dirty pages.To support this behavior, the hardware should include a modified bit(a.k.a. dirty bit). This bit is set any time a page is written, and thus can beincorporated into the page-replacement algorithm. The clock algorithm,for example, could be changed to scan for pages that are both unusedand clean to evict first; failing to find those, then for unused pages thatare dirty, and so forth.c 2014, ARPACI-DUSSEAUTHREEEASYPIECES14 BEYOND PHYSICAL MEMORY: POLICIES22.10 Other VM PoliciesPage replacement is not the only policy the VM subsystem employs(though it may be the most important). For example, the OS also has todecide when to bring a page into memory. This policy, sometimes calledthe page selection policy (as it was called by Denning [D70]), presentsthe OS with some different options.For most pages, the OS simply uses demand paging, which means theOS brings the page into memory when it is accessed, “on demand” asit were. Of course, the OS could guess that a page is about to be used,and thus bring it in ahead of time; this behavior is known as prefetchingand should only be done when there is reasonable chance of success. Forexample, some systems will assume that if a code page P is brought intomemory, that code page P +1 will likely soon be accessed and thus shouldbe brought into memory too.Another policy determines how the OS writes pages out to disk. Ofcourse, they could simply be written out one at a time; however, manysystems instead collect a number of pending writes together in memoryand write them to disk in one (more efficient) write. This behavior isusually called clustering or simply grouping of writes, and is effectivebecause of the nature of disk drives, which perform a single large writemore efficiently than many small ones.22.11 ThrashingBefore closing, we address one final question: what should the OS dowhen memory is simply oversubscribed, and the memory demands of theset of running processes simply exceeds the available physical memory?In this case, the system will constantly be paging, a condition sometimesreferred to as thrashing [D70].Some earlier operating systems had a fairly sophisticated set of mechanismsto both detect and cope with thrashing when it took place. Forexample, given a set of processes, a system could decide not to run a subsetof processes, with the hope that the reduced set of processes’ workingsets (the pages that they are using actively) fit in memory and thus canmake progress. This approach, generally known as admission control,states that it is sometimes better to do less work well than to try to doeverything at once poorly, a situation we often encounter in real life aswell as in modern computer systems (sadly).Some current systems take more a draconian approach to memoryoverload. For example, some versions of Linux run an out-of-memorykiller when memory is oversubscribed; this daemon chooses a memoryintensiveprocess and kills it, thus reducing memory in a none-too-subtlemanner. While successful at reducing memory pressure, this approachcan have problems, if, for example, it kills the X server and thus rendersany applications requiring the display unusable.OPERATINGSYSTEMS[VERSION 0.92] WWW.OSTEP.ORGBEYOND PHYSICAL MEMORY: POLICIES 1522.12 SummaryWe have seen the introduction of a number of page-replacement (andother) policies, which are part of the VM subsystem of all modern operatingsystems. Modern systems add some tweaks to straightforward LRUapproximations like clock; for example, scan resistance is an importantpart of many modern algorithms, such as ARC [MM03]. Scan-resistant algorithmsare usually LRU-like but also try to avoid the worst-case behaviorof LRU, which we saw with the looping-sequential workload. Thus,the evolution of page-replacement algorithms continues.However, in many cases the importance of said algorithms has decreased,as the discrepancy between memory-access and disk-access timeshas increased. Because paging to disk is so expensive, the cost of frequentpaging is prohibitive. Thus, the best solution to excessive paging is oftena simple (if intellectually dissatisfying) one: buy more memory.c 2014, ARPACI-DUSSEAUTHREEEASYPIECES16 BEYOND PHYSICAL MEMORY: POLICIESReferences[AD03] “Run-Time Adaptation in River”Remzi H. Arpaci-DusseauACM TOCS, 21:1, February 2003A summary of one of the authors’ dissertation work on a system named River. Certainly one place wherehe learned that comparison against the ideal is an important technique for system designers.[B66] “A Study of Replacement Algorithms for Virtual-Storage Computer”Laszlo A. BeladyIBM Systems Journal 5(2): 78-101, 1966The paper that introduces the simple way to compute the optimal behavior of a policy (the MIN algorithm).[BNS69] “An Anomaly in Space-time Characteristics of Certain Programs Running in a PagingMachine”L. A. Belady and R. A. Nelson and G. S. ShedlerCommunications of the ACM, 12:6, June 1969Introduction of the little sequence of memory references known as Belady’s Anomaly. How do Nelsonand Shedler feel about this name, we wonder?[CD85] “An Evaluation of Buffer Management Strategies for Relational Database Systems”Hong-Tai Chou and David J. DeWittVLDB ’85, Stockholm, Sweden, August 1985A famous database paper on the different buffering strategies you should use under a number of commondatabase access patterns. The more general lesson: if you know something about a workload, you cantailor policies to do better than the general-purpose ones usually found in the OS.[C69] “A Paging Experiment with the Multics System”F.J. CorbatoIncluded in a Festschrift published in honor of Prof. P.M. MorseMIT Press, Cambridge, MA, 1969The original (and hard to find!) reference to the clock algorithm, though not the first usage of a use bit.Thanks to H. Balakrishnan of MIT for digging up this paper for us.[D70] “Virtual Memory”Peter J. DenningComputing Surveys, Vol. 2, No. 3, September 1970Denning’s early and famous survey on virtual memory systems.[EF78] “Cold-start vs. Warm-start Miss Ratios”Malcolm C. Easton and Ronald FaginCommunications of the ACM, 21:10, October 1978A good discussion of cold-start vs. warm-start misses.[FP89] “Electrochemically Induced Nuclear Fusion of Deuterium”Martin Fleischmann and Stanley PonsJournal of Electroanalytical Chemistry, Volume 26, Number 2, Part 1, April, 1989The famous paper that would have revolutionized the world in providing an easy way to generate nearlyinfinitepower from jars of water with a little metal in them. Unforuntately, the results published (andwidely publicized) by Pons and Fleischmann turned out to be impossible to reproduce, and thus thesetwo well-meaning scientists were discredited (and certainly, mocked). The only guy really happy aboutthis result was Marvin Hawkins, whose name was left off this paper even though he participated in thework; he thus avoided having his name associated with one of the biggest scientific goofs of the 20thcentury.OPERATINGSYSTEMS[VERSION 0.92] WWW.OSTEP.ORGBEYOND PHYSICAL MEMORY: POLICIES 17[HP06] “Computer Architecture: A Quantitative Approach”John Hennessy and David PattersonMorgan-Kaufmann, 2006A great and marvelous book about computer architecture. Read it![H87] “Aspects of Cache Memory and Instruction Buffer Performance”Mark D. HillPh.D. Dissertation, U.C. Berkeley, 1987Mark Hill, in his dissertation work, introduced the Three C’s, which later gained wide popularity withits inclusion in H&P [HP06]. The quote from therein: “I have found it useful to partition misses ... intothree components intuitively based on the cause of the misses (page 49).”[KE+62] “One-level Storage System”T. Kilburn, and D.B.G. Edwards and M.J. Lanigan and F.H. SumnerIRE Trans. EC-11:2, 1962Although Atlas had a use bit, it only had a very small number of pages, and thus the scanning of theuse bits in large memories was not a problem the authors solved.[M+70] “Evaluation Techniques for Storage Hierarchies”R. L. Mattson, J. Gecsei, D. R. Slutz, I. L. TraigerIBM Systems Journal, Volume 9:2, 1970A paper that is mostly about how to simulate cache hierarchies efficiently; certainly a classic in thatregard, as well for its excellent discussion of some of the properties of various replacement algorithms.Can you figure out why the stack property might be useful for simulating a lot of different-sized cachesat once?[MM03] “ARC: A Self-Tuning, Low Overhead Replacement Cache”Nimrod Megiddo and Dharmendra S. ModhaFAST 2003, February 2003, San Jose, CaliforniaAn excellent modern paper about replacement algorithms, which includes a new policy, ARC, that isnow used in some systems. Recognized in 2014 as a “Test of Time” award winner by the storage systemscommunity at the FAST ’14 conference.c 2014, ARPACI-DUSSEAUTHREEEASYPIECES18 BEYOND PHYSICAL MEMORY: POLICIESHomeworkThis simulator, paging-policy.py, allows you to play around withdifferent page-replacement policies. See the README for details.Questions1. Generate random addresses with the following arguments: -s 0-n 10, -s 1 -n 10, and -s 2 -n 10. Change the policy fromFIFO, to LRU, to OPT. Compute whether each access in said addresstraces are hits or misses.2. For a cache of size 5, generate worst-case address reference streamsfor each of the following policies: FIFO, LRU, and MRU (worst-casereference streams cause the most misses possible. For the worst casereference streams, how much bigger of a cache is needed to improveperformance dramatically and approach OPT?3. Generate a random trace (use python or perl). How would youexpect the different policies to perform on such a trace?4. Now generate a trace with some locality. How can you generatesuch a trace? How does LRU perform on it? How much better thanRAND is LRU? How does CLOCK do? How about CLOCK withdifferent numbers of clock bits?5. Use a program like valgrind to instrument a real application andgenerate a virtual page reference stream. For example, runningvalgrind --tool=lackey --trace-mem=yes ls will outputa nearly-complete reference trace of every instruction and data referencemade by the program ls. To make this useful for the simulatorabove, you’ll have to first transform each virtual memoryreference into a virtual page-number reference (done by maskingoff the offset and shifting the resulting bits downward). How bigof a cache is needed for your application trace in order to satisfy alarge fraction of requests? Plot a graph of its working set as the sizeof the cache increases.