ref: http://www.garlic.com/~lynn/2006b.html#14 Expanded Storage http://www.garlic.com/~lynn/2006b.html#15 {SPAM?} Expanded Storage
minor addeda to what went wrong in the initial morph from cp67 to vm370. as i mentioned, LRU is based on the reference history being an correct predictor of future references. a one-bit clock basically orders all pages in real memory and then cycles around them testing and resetting the reference bit. the cycle interval looking at all other pages in storage establishes a uniform interval between resetting the bit and testing it again. the initial vm370 implementation went wrong by both reordering all pages at queue interval as well as resetting the reference bits. for small storage sizes ... the time it took to cycle thru all pages in memory was less than the nominal queue stay ... so we are looking at a reference bit that represents an elapsed period less than a queue stay. as real storage sizes got larger ... the time to cycle all pages became longer than the avg. queue stay. that required that the reference period represented by the reference bit be a period longer than the queue stay. however, at queue transition ... the pages were both being reordered and the reference bit being reset. as a result it only had memory about the most recent queue stay ... even tho pages had real storage lifetimes that were becoming much longer than the most recent queue stay. as a result of both the queue transition reset and the constant reordering ... the testing and resetting implementation bore little actual resemblance to any algorithm based on theoritical foundation (even tho the testing and resetting code looked the same). on the other hand, the same could be said of my slight-of-hand change to the testing and resetting code. however, I could demonstrate that my change actually corresponded to well provable theoritical principles and had well describable and predictable behavior under all workloads and configurations. again, collect postings related to wsclock, global lru, local lru, etc. http://www.garlic.com/~lynn/subtopic.html#wsclock -- Anne & Lynn Wheeler | http://www.garlic.com/~lynn/
