Browse Prior Art Database

Storage Allocation Mechanism for Different Length Data Elements

IP.com Disclosure Number: IPCOM000083177D
Original Publication Date: 1975-Apr-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 7 page(s) / 78K

Publishing Venue

IBM

Related People

Albert, AJ: AUTHOR [+3]

Abstract

This storage allocation mechanism is useful in virtual storage data processing systems, wherein data is stored in the form of data elements of different sizes. The described mechanism minimizes the amount of traffic back and forth between primary storage and auxiliary storage, by minimizing the number of pages of virtual storage actually in use. This is accomplished by allocating a new data element to an existing and partially filled virtual storage page whenever possible and before reusing a page which has become empty, or resorting to the use of a new virtual storage page.

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

Page 1 of 7

Storage Allocation Mechanism for Different Length Data Elements

This storage allocation mechanism is useful in virtual storage data processing systems, wherein data is stored in the form of data elements of different sizes. The described mechanism minimizes the amount of traffic back and forth between primary storage and auxiliary storage, by minimizing the number of pages of virtual storage actually in use. This is accomplished by allocating a new data element to an existing and partially filled virtual storage page whenever possible and before reusing a page which has become empty, or resorting to the use of a new virtual storage page.

The described storage allocation mechanism is particularly useful where the following conditions exist: (1) the virtual storage address space is subdivided into a relatively large number of fixed size storage areas called "pages"; (2) data is stored in the form of elements of some small known number of different fixed sizes; (3) the element size is considerably smaller than the page size; and (4) the total number of elements of any given size which are stored in virtual storage varies as a function of time. For sake of an example, the following assumptions are made: (1) the size of each page is 2048 bytes; (2) the different permissible data element lengths are 16, 32 and 64 bytes; and (3) the data elements, when placed in storage, are aligned on multiples of their own lengths.

Fig. 1 shows a map of a storage page meeting the foregoing assumptions and showing a typical distribution of 16, 32 and 64-byte data elements. For simplicity of explanation, the map shows the storage page as having 128 vertically spaced page locations, each having a width of 16 bytes. In order to satisfy the alignment requirements, the allocation mechanism is such that the 32- byte elements appear in groups of two and the 16 byte elements appear in groups of four.

In order to minimize the number of pages actually in use, a mechanism is provided for keeping track of the currently unused space on each page and for keeping track of which pages have unused space thereon. To accomplish these purposes, a storage allocation element is stored in the last four page locations on each page. This allocation element includes a 64-byte storage element mask (64B mask) at page location 124, a 32-byte storage element mask (32B mask) at page location 125 and a 16-byte storage element mask (16B mask) at page location 126. These masks are, respectively, employed to keep track of the unused or "free" 64, 32 and 16-byte storage spaces on the page.

The 64-byte mask is 32 bits in length, the 32-byte mask is 64 bits in length and the 16-byte mask is 128 bits in length, these numbers of bits corresponding to the maximum number of possible spaces on the page for the corresponding size elements. For example, since there are 128 possible 16-byte locations on a page, the 16-byte mask includes 128 bits in order to keep track of the status of each of these...