Browse Prior Art Database

The Nth Chance Algorithm for Virtual Memory

IP.com Disclosure Number: IPCOM000038730D
Original Publication Date: 1987-Feb-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Merritt, CR: AUTHOR

Abstract

In a demand-paging, virtual memory system conditions may occur in which there are no available real page frames and a page fault occurs. The Virtual Memory System must then select an in-use page frame to be replaced by the faulted page. A method is described that extends the second chance (or "clock") algorithm in the following way. a. Associate with each real page frame a counter of some selected precision. b. When a page frame is assigned, initialize its corresponding counter to its maximum value. c. Using a static index, examine a candidate frame reference bit. d. If the candidate frame reference bit is on, set it off and move to the next frame. e.

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

Page 1 of 1

The Nth Chance Algorithm for Virtual Memory

In a demand-paging, virtual memory system conditions may occur in which there are no available real page frames and a page fault occurs. The Virtual Memory System must then select an in-use page frame to be replaced by the faulted page. A method is described that extends the second chance (or "clock") algorithm in the following way. a. Associate with each real page frame a counter of

some selected precision.

b. When a page frame is assigned, initialize its

corresponding counter to its maximum value.

c. Using a static index, examine a candidate frame

reference bit.

d. If the candidate frame reference bit is on, set it

off and move to the next frame.

e. Otherwise, if the candidate frame reference bit is

off, then examine the corresponding counter.

f. If the counter is zero, then the candidate frame

to be taken has been found.

g. Otherwise, decrement the value of the counter and

move to the next frame. When the "Nth Chance Algorithm" and its array of counters in one- to-one correspondence with the available real page frames is employed, a Virtual Memory Service Call, referred to as Hold Page, is provided to allow a program to specify a range of virtual pages in which a corresponding frame, if there is one, is to have its associated counter set to the maximum value. Example:

Let fp = first page of range

#p = number of pages

Then:

Hold Page (fp, #p); - says to set each counter in the

specified range to max for each frame ass...