Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.csd.uwm.edu!bionet!agate!saturn!wilson@carcoar.Stanford.EDU From: wilson@carcoar.Stanford.EDU (Paul Wilson) Newsgroups: comp.os.research Subject: adaptive replacement better than Working Set? Message-ID: <8919@saturn.ucsc.edu> Date: 29 Aug 89 07:34:36 GMT Sender: usenet@saturn.ucsc.edu Organization: Stanford University Lines: 111 Approved: comp-os-research@jupiter.ucsc.edu I'm looking for information on adaptive virtual memory replacement algorithms, like the "learning" replacement algorithm used in the Ferranti ATLAS. That algorithm used observed reference patterns to give different pages different caching weights, in hopes of caching regularly-accessed pages. It seems to me that such an adaptive algorithm could perform significantly better than the ubiquitous LRU and WS policies. The policy I have in mind is *not* as loop-oriented as the ATLAS algorithm, and is based on a more refined notion of frequency of access. I realize that the ATLAS algorithm only worked better than LRU for a minority of programs, but I think I know why, and my algorithm would do better for typical programs. My impression is that the only similar algorithm ever tested to any real degree was in fact exactly the same algorithm, (as published in IRE Transactions in 1962(?)). The simulation was part of Belady's study of replacement algorithms (IBM Syst. J., 1966(?)). If different adaptive algorithms have been tested, so that the idea is actually known to be wrongheaded, I would very much like to know about it. If not, it seems that the idea was prematurely laid to rest after testing only one flawed instance of a family of algorithms. In that case some similar algorithms may in fact be better than LRU or WS, and everybody's been going the wrong way for 15 or 20 years by assuming that recency of reference is *the* best available predictor of future referencing. I know that working set works very well, but I think you could do significantly better. Not dramatically better, mind you, but enough to make it worthwhile. And even if WS is unbeatable for general-purpose OS applications, adaptive algorithms may be useful for programs that have wacky locality characteristics, like most garbage collected heaps and persistent virtual memories used to implement databases. One algorithm I've been toying with adaptively shifts toward LRU for "normal" programs, and towards a DBMS-like "hot set" strategy when locality suddenly goes to pot. That way, if you scan through an array (or memory mapped file) bigger than memory, it doesn't displace your whole working set for nothing. (By the way, I *have* read Denning's argument as to why nobody will ever do much better than WS ("Working Sets Past and Present," IEEE TSWE 1980). I'm not quite convinced yet, though. I wonder about the problem of a single dominant process making WS degenerate into (fixed-space) LRU, so that something has to be evicted before its time. And Denning argues from data on programs with "marked" phase changes, when more than half of all page faults come in the periods in between.) Any info relevant to this would be *very* helpful. I'm wondering if more tests were done on the ATLAS than were reported, particularly tests with variant replacement algorithms that might not have the same flaw. For those who know the ATLAS algorithm, here's the flaw I'm talking about. That system assumes that patterns of references to a given page are roughly periodic, and that once a page has stopped being referenced in the same period, it's probably not going to be referenced for a long time. E.g., a page may be referenced once every iteration of an outer loop, while several pages are scanned by an inner loop, e.g., when forming a cartesian product. According to Denning ["Virtual Memory," _Computing_Surveys_, 1970], this strategy only worked well for stereotypical loop programs. My hypothesis is similar, but somewhat more sophisticated. I also assume that future reference patterns are likely to be similar to past reference patterns, *but* with two differences: 1) "periodicity" is very approximate, and 2) reference patterns have multiple frequency components, only some of which are relevant to a replacement policy. Take this example: suppose some program accesses some page of memory every millisecond or so while it's executing, and that there's usually an interval of a tenth of a second between calls to that program. You may notice the 1000 Hz frequency and ditch the page if goes unreferenced for two milliseconds, on the assumption that the current clump of references is finished. But that's a mistake because you fail to notice the 100 Hz component that would let you predict that it would be touched again in about a tenth of a second. (Assuming here that pages typically stay in memory for at least a tenth of a second.) You want to key off of the lower frequencies, unless they're so low that they indicate that the page won't be referenced for a very long time, so that it's better to use the space some other way in the meantime. The problem with the ATLAS algorithm (as published) is that it keys off of the highest observable frequency, which is probably too short to be interesting to a replacement policy. (By "observable frequency" I just mean the resolution of the system's LRU approximation -- how often the use bits are checked, or whatever. Smaller interreference gaps than that will not be noticed, of course.) It also assumes that references are fairly literally periodic, rather than merely having approximate frequency components; this may also eject pages prematurely. If anybody knows of any relevant experiments, or if I've misunderstood the ATLAS algorithm, please drop me a note at the address below. Thanks prematurely, Paul Paul R. Wilson Software Systems Laboratory lab ph.: (312) 996-9216 U. of Illin. at C. EECS Dept. (M/C 154) wilson@bert.eecs.uic.edu Box 4348 Chicago,IL 60680 Paul R. Wilson Software Systems Laboratory lab ph.: (312) 996-9216 U. of Illin. at C. EECS Dept. (M/C 154) wilson@bert.eecs.edu Box 4348 Chicago,IL 60680