Browse Prior Art Database

Hardware Assisted Paging Algorithm

IP.com Disclosure Number: IPCOM000073420D
Original Publication Date: 1970-Dec-01
Included in the Prior Art Database: 2005-Feb-22
Document File: 4 page(s) / 85K

Publishing Venue

IBM

Related People

Duffie, CA: AUTHOR

Abstract

A method of paging programs using a hardware assist is described. The main goals in the development of this algorithm have been transparency to the assembler, transparency to the user, and functional simplicity so as to use as little as possible of resident memory for paging management.

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

Page 1 of 4

Hardware Assisted Paging Algorithm

A method of paging programs using a hardware assist is described. The main goals in the development of this algorithm have been transparency to the assembler, transparency to the user, and functional simplicity so as to use as little as possible of resident memory for paging management.

Since the algorithm has been developed for a theoretical machine, certain assumptions have been made and this description is centered around those assumptions. It has been attempted to keep the assumptions to a minimum, however, to keep the algorithm as general purpose as possible. The assumptions made are: 1) There exists a given number of interrupt levels within the machine.
2) There will be unique functions executing within these interrupt levels. 3) There will be fixed core allocations per interrupt level. 4) Functions will be link-edited to virtual memory. 5) There will exist one hardware base register per page per program executing in memory at any given point in time. 6) The effective instruction address will be computed by the hardware via base-replacement technique. 7) Assembled programs cannot physically exceed 4096 (8bit) bytes.
8) The algorithm must function such that a reassembly of applications programs is not required when run on machines of varying resident core sizes. 9) The machine will have 256 byte pages with a maximum resident memory of 64K bytes.

The key to the paging algorithm is the machine instruction counter which appears as in drawing A.

The significance of the bits in the instruction counter are defined as follows:

The Program Page Counter and Page Displacement fields are resolved by the Assembler program. The fields together form the Assembler location counter and represent the instruction address as displaced from the origin of the program.

The Base Bank Locator field is resolved by the Linkage Editor program. As can be seen from drawing B, the hardware page base registers exist in sixteen banks of 16 registers each. This Base Bank Locator field allows the Linkage Editor to assign all (or subsets) of these sixteen banks to programs according to interrupt level priority, processing priority, etc.

Resident memory is managed in the machine by a Virtual Memory Map Table that is constructed in parallel with the 256 Hardware page base registers and appears as in drawing B where: F = flags defined as follows .Bit 0 (on) = corresponding page area exists in resident memory .Bit 1 (on) = map entry allocated to currently executable program .Bit 2 (on) = associated program page is currently resident in memory .Bit 3 (on) = associated page is designated a program page A1 = corresponding resident page area base address (Note: this field is valid only if Bit 0 of the flag field is on) A2 = corresponding nonresident program page segment address (Note: this field is valid only if Bit 1 is on and Bit 2 is off in the flag field)

1

Page 2 of 4

This defines all of the primary ingredients of the paging alg...