Browse Prior Art Database

Space Management for Pages

IP.com Disclosure Number: IPCOM000084512D
Original Publication Date: 1975-Nov-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Wolff, CH: AUTHOR [+2]

Abstract

Described is a paging method for assigning radix-2 index entries in a binary tree to pages in a virtual store computer system.

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

Page 1 of 2

Space Management for Pages

Described is a paging method for assigning radix-2 index entries in a binary tree to pages in a virtual store computer system.

Each page is associated with a two-bit field that records the amount of usable space in the page. 00 means that less than one-fourth of the page is available, 01 means that from one-fourth to one-half of the page is available, 10 means that from three-fourths to all of the page is available, and 11 means that the page is not used.

The two-bit fields are stored one after another in a long bit string, and they are, respectively, associated with pages numbered consecutively from 0 to N-1, representing N pages. For example, if there are 64 mega-bytes of storage divided into 4K byte pages, then a single page can contain the index for a complete set of two-bit fields for all the pages.

In addition to the long bit string, for each set of 32 consecutive two-bit fields, there is a three-bit field that summarizes the status of the set of two-bit fields. Bit 0 is a one if any of the 32 fields has a value of 01, bit 1 is a one if any field has a value of 10, and bit 3 is a one if any field has a value of 11. This three-bit field forms a second index level in a tree arrangement.

The string of three-bit fields is kept in a bit string that is physically in front of the long string of two-bit fields. The space for the string of three-bit fields is 3/64 as much as that for the string of two-bit fields, or about 4.6%.

For the case of 16,384 pages, the three-bit fields require 1536 bits, which is 192 bytes. Each set of consecutive 32 three-bit fields is similarly summarized by a third-level three-bit field, which is formed by ORing together the 32 three-bit fields, and the string of these is stored in front of the other string of three-bit fields. For this example, there are sixteen of these three-bit fields requiring 6 bytes of storage.

Suppose a page must be located that has enough space to hold a space request. The requested space is rounded to an exact multiple of 1/4 page, and...