Browse Prior Art Database

# Implementation of the Stack Operation Circuit for LRU Algorithm

IP.com Disclosure Number: IPCOM000085940D
Original Publication Date: 1976-Jun-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 4 page(s) / 62K

IBM

## Related People

Maruyama, K: AUTHOR

## Abstract

In one well-known page replacement policy called "least recently used" (LRU), the least recently used page is removed from the main memory when a page fault occurs. To keep the necessary information for LRU, a stack may be used. Instead of using a stack, which is generally realized by a LIST (cells and pointers), a binary string may be used. Shown is a circuit which performs operations (which are equivalent to stack operations) on the binary string B, so that the least recently used page can be determined easily and quickly.

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

Page 1 of 4

Implementation of the Stack Operation Circuit for LRU Algorithm

In one well-known page replacement policy called "least recently used" (LRU), the least recently used page is removed from the main memory when a page fault occurs. To keep the necessary information for LRU, a stack may be used. Instead of using a stack, which is generally realized by a LIST (cells and pointers), a binary string may be used. Shown is a circuit which performs operations (which are equivalent to stack operations) on the binary string B, so that the least recently used page can be determined easily and quickly.

Let n denote the number of page frames in the main memory and let m = absolute value log(2)n. Let B be a binary string of length mn bits, called "stack string", which is denoted by:

(Image Omitted)

In the binary string B, B/m/(0) corresponds to the top of the stack and its value denotes the page frame number which contains the "most" recently used page. B/m/(n-1) corresponds to the bottom of the stack and its value denotes the page frame number which contains the "least" recently used page.

The LRU algorithm requires the following operations on B whenever a page is referenced by CPU:

If the virtual address which is referenced by the CPU causes no page fault,
i.e., the page which contains the virtual address resides in the main memory, say in the k-th page frame in the main memory, then the k-th page frame has its stack position s, where 0 < or - s < or - n-1. In other words: B/m/(s) = (the binary representation of k).

Since the page in the k-th page frame is referenced by CPU, B/m/(s) must be put on top of the stack, i.e., the following operation on B, which is called the "stack updating operation," has to be performed;

When a page fault occurs, since B/m/(n-1) of B corresponds to the bottom of the stack and its value denotes the page frame number in which the least recently used page resides, the page in the frame number B/m/(n-1) will be removed from the main memory to provide a free-page frame so that the demanded page by CPU can be brought from the auxiliary memory and put in the main memory.

Fig. 1 shows the circuit for the stack updating operation on B. Since it is difficult to depict the circuit for large n, where n is the number of page frames in the main memory, the case of n=4 is illustrated in Fig. 1. The switches designated Sc in Fig. 1 are shown in detail in Fig. 2. These switches are used to control the path of signal flow. If C=0 to INVERT gate I and AND gates A in Fig. 2, then terminals between 0 and 1 are connected. If C=1 then terminals between 0 and 2 are connected.

(Image Omitted)

1

Page 2 of 4

Whenever a page in the main memory is referenced by the CPU, then r=1, otherwise r=0. To see how the circuit of Fig. 1 operates, the terminals between 0 and 1 are first connected, i.e., in block S, s(0)s(1) = 11. Then, when r=1, the input bits;

Thus, for s(0)s(1) = 1 1 , the circuit becomes a 2-bit position rotate circuit.

The switches a...