virtual memory 4463

re:

one of the issues with cycling around real memory for global LRU was that it tended to be naturally adaptive (self-regulating) over a relatively broad range of environments and configurations.

the point of LRU replacement ... is that *least recently used* is supposedly predictive of future use ... pages used in the recent past have a high probability being used in the near future (than pages that haven't been used in the recent past).

the interval between the reset of the reference bit and the next examination of the reference bit is supposed to represent a "recent interval" that retains the predictive characteristics buttociated with *least recently used* observations (pages that have the reference bit off haven't been used in the recent interval and pages that have the reference bit on have been used in the recent interval).

the naturally adaptive characteristics is that if the implementation has cycled memory too quickly (cycled around storage once) ... then there will be a larger precentage of pages with the reference bit off ... which means it will take much longer to make one complete cycle through all of memory (increasing the interval that allows pages to have their reference bit set). if the implemenation has cycled memory too slowly ... then there will be a larger percentage of pages with the reference bit on ... which means that it will take much shorter time to make one complete cycle through all of memory (one complete cycle of memory is a function by the rate of page-faults and the percentage of pages with their reference bits off).

so naturally adaptive worked over a fairly broad range ... but not completely. In page thrashing scenario (severe over commitment of real storage), everybody is waiting for page fault and not executing ... so nobody is getting any page reference bit set. majority of reference bits are always off and the algorithm degenerates to pretty much FIFO (as in the case of "alogorithm 1" for cp67 which had effectively buttumed all the reference bits were the same and didn't even both to check).

the other situation where the natural adaptive starts to break down is where there was increasing amounts of available real storage and the time it takes to cycle around all storage begins to consistently exceed any common definition of "recent" ... as applied to least recently used algorithms. large percentage of pages may have their reference bit on (because the interval since recent was so long) and there was no differentiation between pages that had been "recently used" and pages that hadn't been used for quite some time.

this is where the "offset reset" started to appear. you can think of the original implementation as having a "offset reset" exactly equal to one complete cycle of all storage. however, with increasing real storage sizes the avg. interval to cycle around all pages (interval between reset and examiniation) was becoming excesively larger and no longer conformed to any reasonable definition of "recent". so a new variation was introduced to offset the resetting the reference bit from the examination of the reference bit. this offset could be adjusted based on reasonable definition and expectation of "recent" having some valid prediction of future page reference behavior. This could possibly be one-half of all memory .... so the pages being reset were effectively "half of real pages" away from the pages being examined (cutting the average interval between reset and examination in half).