Browse Prior Art Database

Activity Indicator for Pages

IP.com Disclosure Number: IPCOM000077730D
Original Publication Date: 1972-Sep-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Gaudette, CH: AUTHOR [+3]

Abstract

In a multiprogramming computer system, it is often necessary to replace an existing page in memory with a newly referenced page. The decision regarding the choice of a page to replace with the referenced page can be made more intelligently, if some indication of which pages are in the working set of the program is available. The working set at any instant consists of the set of pages referred to during some period, r, of execution immediately preceding the instant under consideration. It is hypothesized to contain pages that are quite likely to be referred to in the immediate future and thus represents those pages that should be used for replacement purposes only as a last resort.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Activity Indicator for Pages

In a multiprogramming computer system, it is often necessary to replace an existing page in memory with a newly referenced page. The decision regarding the choice of a page to replace with the referenced page can be made more intelligently, if some indication of which pages are in the working set of the program is available. The working set at any instant consists of the set of pages referred to during some period, r, of execution immediately preceding the instant under consideration. It is hypothesized to contain pages that are quite likely to be referred to in the immediate future and thus represents those pages that should be used for replacement purposes only as a last resort.

To enable one to decide whether a page belongs to the current working set of a program, an Activity Indicator (AI) is associated with each page and a Program Activity Indicator (PAI) with each program. The AI's and PAI's are manipulated as follows:
(1) All PAI's initially have zero values.
(2) Whenever a program is run, every T units of execution time

(called the quantum), its PAI is incremented by I. Then the

AI of each page that is used by the program and that has its

"reference-bit" [2] SET (i.e., equal to 1) is set equal to

the PAI value, and the reference-bits are RESET.
(3) When a new page is brought in, its AI is initialized to the

value of the PAI for the program that referenced it and

caused it to be brought in.

Owing to the manner in which the AI values are updated, the AI value of a page starts out equal to the PAI and remains equal to it until an entire quantum passes without a reference to the page being made - at which point it falls behind the PAI by 1. It continues falling behind by 1 for every subsequent quantum that passes without a reference to the page being made. However, if in some later quantum a reference is made, the AI immediately catches up with the PAI. The deficit, or difference in values of the PAI and AI, for a page thus represents the number of immediately preceding quanta of execution time for which a page has not been referred to.

In order to accommodate pages that are shared between programs, the algorithm, described previously, for updating of the AI's is modified as follows. Initially all PAI's have zero values. When a program is run, every T units of execution time, its PAI is incremented by 1. Then, for each page that has its "reference-bit" SET (i'e' equal to 1), its AI is compared with the PAI of this program. If the AI is less than or equal to the PAI then the AI is set equal to the PAI and...