Browse Prior Art Database

Page Allocation Mechanism

IP.com Disclosure Number: IPCOM000075907D
Original Publication Date: 1971-Dec-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 5 page(s) / 56K

Publishing Venue

IBM

Related People

Belady, LA: AUTHOR [+2]

Abstract

In a paging machine, programs are usually executed in a space smaller than their size. Quite frequently, during such executions, a page which contains the next needed information is not present in direct access memory whereby a page exception is generated. In known systems, such page exception entails the involved actions of bringing in a page-size of information. Clearly, the reduction of the number of page exceptions is desirable. Such reduction can be achieved in essentially two ways. One of these ways is having a particular system design, such as the utilization of replacement algorithms, a scheme to allocate space for programs to run, etc. The other of these ways is the changing of the programs' internal topology, i.e.

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

Page 1 of 5

Page Allocation Mechanism

In a paging machine, programs are usually executed in a space smaller than their size. Quite frequently, during such executions, a page which contains the next needed information is not present in direct access memory whereby a page exception is generated. In known systems, such page exception entails the involved actions of bringing in a page-size of information.

Clearly, the reduction of the number of page exceptions is desirable. Such reduction can be achieved in essentially two ways. One of these ways is having a particular system design, such as the utilization of replacement algorithms, a scheme to allocate space for programs to run, etc. The other of these ways is the changing of the programs' internal topology, i.e., mapping of the collection of program objects to the set of pages as basic units of the virtual storage. However, manipulation of the program topology is rarely permissible to system designers because such topology is intricately intertwined with the correctness of the program. Thus, the program, as it is laid out in virtual storage, is considered as having the form when the program is to be run, and optimization techniques have to start at this latter point.

Heretofore, the sensing of certain properties of program topology have been proposed and many attempts have been made to improve performance by properly matching these properties with the system resource allocation scheme. Examples of such sensing are the principles of locality and working set, both of the latter concepts being related to the observed fact that, as programs are run in different size memories, additional pages which increase the memory size have a variable effect on performance. When a memory size is attained wherein a program runs reasonably well and wherein further increase of significant effect on performance, the set of pages in memory in such situations is considered to form a working set. The concept of a working set, since its origin, has been employed as if it were a program invariant and valid for the entire duration of the program run. However, this has been found not to be the case, and, in fact, the set of pages as well as their number, which are associated with good performance, are a function of time.

It is readily appreciated from the foregoing, that in a multiprogramming environment, program topology properties assume an even greater importance. Not only is more memory space available to large systems than would be necessary to accommodate a single program into the remaining available additional space, but other programs can be loaded whereby delays such as paging delays, for example, of one program can be overlapped with the useful processing activities of the others. However, this general, i.e. multiprogramming situation is quite complex since upon the occurring of a need to remove a page from memory, there arises a question as to which program is to lose a page.

The mechanism described herein is...