Browse Prior Art Database

Adaptive Time Stamp Mechanism

IP.com Disclosure Number: IPCOM000080410D
Original Publication Date: 1973-Dec-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 4 page(s) / 74K

Publishing Venue

IBM

Related People

Arnold, RF: AUTHOR [+3]

Abstract

Least Recently Used Page Replacement Algorithms.

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 36% of the total text.

Page 1 of 4

Adaptive Time Stamp Mechanism

Least Recently Used Page Replacement Algorithms.

Most studies of page replacement algorithms for demand paging storage hierarchies indicate that a Least Recently Used (LRU) replacement algorithm, results in a better hit ratio than that obtained from other page replacement algorithms.

An LRU page replacement algorithm requires a complete logical ordering of all pages in the level. The most obvious ways to implement this LRU ordering are: 1) Physical location implies relative time since last use. 2) A linked list can imply order of referencing.

1) has the disadvantage of requiring much movement within the level, while
2) would require a doubly linked list for efficient deletion of a page. Insertion and deletion routines with nontrivial execution times would be required.

Because of the difficulties involved with implementing an exact LRU replacement algorithm, an algorithm which can be made to closely approximate LRU performance without the attendant overhead is proposed called Adaptive Timestamping. Time Stamp Philosophy.

This approach calls for stamping a page with a "clock" value every time it is referenced. The clock should have only that degree of fineness necessary, to insure adequate dispersion of the pages in memory among the classes eligible and not eligible for replacement. The "clock" rate must be adequate to provide a large enough supply of "eligible for replacement" pages, so that the replacement function is not unduly hampered by looking for an eligible page. The time stamp clock can be generated from a realtime clock, or can be tied more directly to the paging activity at the level and the referencing pattern within the level. In either case, clock rate must be made a function of the memory performance, so that the algorithm can adapt to varying reference patterns. Time Stamp Tied to Realtime Clock.

Use of a realtime clock for the time stamp would be implemented by sampling some subset of the bits in a hardware clock. Stamping with a different subset of the bits in the hardware clock can be used to vary the time stamp clock rate.

This type of time stamp clock may cause the page replacement algorithm to stray far from LRU as the referencing pattern changes. If the time stamp clock runs too fast, the minimum residence time will be smaller than necessary for efficient storage management. Also, the time stamps on the pages tend to move from a LRU-like distribution toward a random distribution. If the clock runs too slowly, the granularity of the time stamp is not fine enough, and it is less likely that the page displaced will be the best LRU choice. Because pages will age more slowly than they should, the replacement function will have difficulty finding pages of terminal age, and lack of available space within the level may become a severe problem.

1

Page 2 of 4

To reduce the problems associated with time stamping from a realtime clock, the subset of bits, which is used as the time stamp, may...