Browse Prior Art Database

Long Cycle Adaptive Time Stamp Mechanism

IP.com Disclosure Number: IPCOM000081687D
Original Publication Date: 1974-Jul-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 62K

Publishing Venue

IBM

Related People

Ouchi, NK: AUTHOR

Abstract

Pages in a level of a storage hierarchy must be replaced as other pages are moved to the level. The Least Recently Used (LRU) page replacement algorithm is based on the time of last usage, reference, of a page. The maintenance of a true LRU stack requires significant overhead and is not necessary for a system with a large number of pages. The determination of "old", least recently used, pages can be made using a time stamp. Every page referenced is stamped with the "time" of reference. The time is taken from a clock that is driven by the referencing pattern. The problem is the determination of the referencing pattern and the driving of the clock.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Long Cycle Adaptive Time Stamp Mechanism

Pages in a level of a storage hierarchy must be replaced as other pages are moved to the level. The Least Recently Used (LRU) page replacement algorithm is based on the time of last usage, reference, of a page. The maintenance of a true LRU stack requires significant overhead and is not necessary for a system with a large number of pages. The determination of "old", least recently used, pages can be made using a time stamp. Every page referenced is stamped with the "time" of reference. The time is taken from a clock that is driven by the referencing pattern. The problem is the determination of the referencing pattern and the driving of the clock.

The clock has N values 0, 1, 2... N1 and is cyclically advanced, i.e., 0, 1, 2... N1, 0, 1.... Since every page was referenced at least once, the pages can be divided into N classes corresponding to their stamp value. When a page is referenced, it is stamped and becomes a member of the class with the clock value. Thus, the number of pages in the clock value class increases monotonically as pages of other classes are referenced.

If the clock were not advanced, every page would eventually be a member of this class. To prevent this, the clock is incremented as a function of the referencing pattern. Arnold, Hartung, and Snow in "Adaptive Time Stamp Mechanism" IBM Technical Disclosure Bulletin, December 1973, Vol. 16, No. 7, pp. 2209-2213 describe a mechanism that uses the cumulative age of the pages to increment the clock. It requires N counters to account for the number of pages that move to the clock value class, due to the cyclic clock.

In the method described here, the clock is incremented when the number of pages moving to the clock value class due to referencing activity exceeds a predetermined threshold value. This value is based on the number of pages in the system and the percentage of pages exposed to the replacement mechanism.

The age of a page can be defined as (clock value stamp value) mod N. Let T be some threshold value for clock advancement and M be the number of pages. If all pages are referenced in a uniformly distributed random pattern, then the distribution of age vs. number of pages of each age can be approximated by a triangle with height T, area M, and base 2M/T. This is illustrated in Fig. 1. If the pages are not uniformly referenced, then the shape of the distribution changes to in...