Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Interval Stack Processing for Least Recently used Replacement Algorithm

IP.com Disclosure Number: IPCOM000085563D
Original Publication Date: 1976-Apr-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 51K

Publishing Venue

IBM

Related People

Slutz, DR: AUTHOR

Abstract

Stack Processing (see "Evaluation Techniques for Storage Hierarchies" by Mattson, Geisei, Slutz, and Traiger, IBM Systems Journal, Vol. 9, No. 2, 1970) is a procedure for calculating miss ratios for certain replacement algorithms from page reference strings. The procedure maintains a list of all referenced pages called ""the stack'' and scans the reference string once. For each reference x the stack is searched for x. If x is found its stack position (called the stack distance) is recorded; if not, x is added to the stack. The stack distances are sufficient to calculate miss ratios.

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

Page 1 of 2

Interval Stack Processing for Least Recently used Replacement Algorithm

Stack Processing (see "Evaluation Techniques for Storage Hierarchies" by Mattson, Geisei, Slutz, and Traiger, IBM Systems Journal, Vol. 9, No. 2, 1970) is a procedure for calculating miss ratios for certain replacement algorithms from page reference strings. The procedure maintains a list of all referenced pages called ""the stack'' and scans the reference string once. For each reference x the stack is searched for x. If x is found its stack position (called the stack distance) is recorded; if not, x is added to the stack. The stack distances are sufficient to calculate miss ratios.

If the stack exceeds the available main memory, it must, in part, be maintained on secondary storage. If, in addition, the stack distances are large, portions of the stack must be repeatedly overlaid in main memory causing severe performance degradation. Interval Stack Processing is a procedure that largely avoids this problem for the least recently used (LRU) replacement algorithm. The procedure involves scanning a sequence of references (an interval) during which a fixed amount of main memory is required. The stack is accessed only at the end of each interval. The procedure makes no approximations; the exact LRU miss ratios are obtained.

The flow chart summarizes the procedure. The main stack is the stack of all pages on secondary storage. The scan of an interval of references (entry 1 in the flow chart) involve...