Browse Prior Art Database

Transient Adaptive Memory Allocation

IP.com Disclosure Number: IPCOM000089422D
Original Publication Date: 1977-Oct-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Chiu, WW: AUTHOR [+2]

Abstract

A memory allocation scheme for demand paging systems which employ working-set strategies is described below. Two types of page faults are detected and classified for the purpose of identifying transitions between localities of memory references in programs and adapting to the changing needs of memory space during transitions.

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

Page 1 of 2

Transient Adaptive Memory Allocation

A memory allocation scheme for demand paging systems which employ working-set strategies is described below. Two types of page faults are detected and classified for the purpose of identifying transitions between localities of memory references in programs and adapting to the changing needs of memory space during transitions.

Programs in execution are known to exhibit localities of references, and programs can shift from one locality to another quite frequently. A locality shift is characterized by the rapid loading of new pages or pages which have not been used recently. When a shift occurs, most pages in the last locality are not likely to be rereferenced. But, most algorithms to date do not consider this fact. As a consequence, rapid loading of new pages can cause unnecessary temporary expansion of working-sets. The following scheme detects locality shifts by classifying two types of page faults.

A program's locality is defined as the set of K pages that last entered its working-set. Such entries are recorded in a pushdown stack called the locality stack. Pages in the working-set, i.e., those allocated to the program, may correspond to a subset of the entries in the locality stack. Reference to a page which is not in the working-set is referred to as a fault. A fault to a page having an entry in the locality stack is called a rereference fault. Otherwise, it is called a loading fault. Whenever N successive faults are detected to be loading faults, the working-set size is frozen, i.e., no expansion is allowed. Thus, any subsequent loading faults will cause older pages to be pushed out of the working-set in a least recently used fashion. Normal working-set processing will be resumed when a rereference fault occurs or when a loading fault occurs after all the old pages have been pushed out.

Loading faults are bursty and transitional in nature. Thus, when using normal working-set processing, there may be a sudden shortage of pages during the rapid loading period. This may lead to a swapping out of programs unnecessarily to compensate for a memory space shortage which is only temporary.

Locality stacks are used also because only rereference faults are likely to be reduced by incremental allocating of memory. Since most modern operating systems have dynamic allocation algorithms which employ measured page fault rates as a crucial parameter, it is necessary to distinguish between the two types of page faults.

The working-set storage is managed such that each resident program is allocated only those pages which were referenced in the last Tau units as CPU time (working-set window size). A program's pages are kept on a list. Each entry on the list points to an allocated page and has three fields: (1) a reference bit, (2) an unreferenced interval count (UIC), and (3) its virtual page address (or
I.D.). The program's allocated page list is updated whenever a fixed amount of CPU time has been accumulate...