Browse Prior Art Database

Replacement Algorithm Using Priority Class Structure

IP.com Disclosure Number: IPCOM000079177D
Original Publication Date: 1973-May-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 48K

Publishing Venue

IBM

Related People

Chia, DK: AUTHOR [+2]

Abstract

Described is a replacement algorithm which is more flexible than previous algorithms such as Least Recently Used (LRU), Least Frequency Used (LFU) and First In-First Out (FIFO).

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

Page 1 of 3

Replacement Algorithm Using Priority Class Structure

Described is a replacement algorithm which is more flexible than previous algorithms such as Least Recently Used (LRU), Least Frequency Used (LFU) and First In-First Out (FIFO).

In a memory hierarchy system, the replacement algorithm is complicated by the fact that within each memory level there exist different classes based on status bits. These are: 1) Invalid status. 2) Unmodified status. 3) Modified status. 4) Lock status.

Class 1 consists of pages which have been destroyed and, therefore, can be overlaid immediately. This class should have the highest priority for replacement. Class 2 consists of pages which have duplicate copy in a slower memory level. This class can be overlaid. Since the data are still valid and useful, class 2 should have a lower priority for replacement than class 1. Class 3 consists of pages which do not have duplicate copy anywhere; therefore, they cannot be overlaid. A duplicate copy must be written down to a slower memory level before it can be replaced. The priority for replacement should then rank below classes 1 and 2. Class 4 consists of pages which cannot be removed from the memory level. Examples are "bind" pages, system work spaces, and error pages. This class cannot be replaced.

With refinement the division of entries on the basis of status, bits can be used as a basis of a replacement system. The refinement takes the form of splitting each of classes 2 and 3 into two separate classes. This can be done by adding a reference bit to each directory entry. The addition of reference bit will, in effect, give six replacement classes: 1) Invalid (V)

2) Unmodified & Unreferenced (M, REF)

3) Unmodified & Referenced (M, REF)

4) Modified & Unreferenced (M, REF)

5) Modified & Referenced (M, REF)

6) Lock (L).

The reference bit can be turned on each time a reference is made to the page. This will, in effect, move a page from class 2 to class 3 or from class 4 to class 5, giving it a lower priority for replacement. When completed, a change of class can be performed by turning off the reference bit of all members of class 3. Similarly, change of class can be done on data in class 5 when class 4 is depleted. Furthermore, a page in class 3 can be changed directly to class 5 if unmodified data becomes modified data through a WRITE operati...