Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Sorting of Dynamically Allocated Storage

IP.com Disclosure Number: IPCOM000044946D
Original Publication Date: 1983-Jan-01
Included in the Prior Art Database: 2005-Feb-06
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Pinnell, MC: AUTHOR

Abstract

Variable length segments of data or of transient procedure arranged contiguously in a working store or cache are accessed (possibly for reading, for updating, for deletion, or for execution) as required by an application program run on a computer. To permit the application program to create new segments on demand, and to permit a demand paging mechanism to fetch transient procedures or data into the cache, a background procedure from time to time writes modified segments to a backing store, so that storage space can be obtained in the cache as required, by drop-out of unmodified or backed-up segments on a least recently used (LRU) basis.

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

Page 1 of 2

Sorting of Dynamically Allocated Storage

Variable length segments of data or of transient procedure arranged contiguously in a working store or cache are accessed (possibly for reading, for updating, for deletion, or for execution) as required by an application program run on a computer. To permit the application program to create new segments on demand, and to permit a demand paging mechanism to fetch transient procedures or data into the cache, a background procedure from time to time writes modified segments to a backing store, so that storage space can be obtained in the cache as required, by drop-out of unmodified or backed-up segments on a least recently used (LRU) basis. Free space can become available in the cache as a result either of the explicit deletion by the application program of its temporary segments, or of LRU drop-out, and since in both cases the segment being removed from the cache is selected without regard to its location in the cache, free space will arise at unpredictable locations and the total of free space will tend to become fragmented. Areas of free space are made to migrate to the high-address end of the cache by a low priority background procedure which repeatedly looks for a segment which lies at the high-address boundary of a free-space fragment and moves such a segment to the low- address boundary of that free-space fragment. Additionally, when all fragments of storage have been merged into one area of free space, the background procedure physically sorts segments so that those subsequently selected for drop-out are more likely to be physically located adjacent the consolidated free space, thus avoiding the generation of further space fragments on drop-out of segments.

A working store or cache adapted for accepting and processing variable length segments of data or of transient procedure is described in European Patent Application 43391. In the arrangement described, all segments fetched into the cache (or created in the cache) have unique segment identifiers and are linked to each other in one of a number of double-threaded lists which serve as "access chains", where the choice of access chain in which to link a segment is made by hashing the segment identifier. Accordingly, a particular segment whose location is unknown is found by a sequential search through an access chain, starting from a chain header located in a reserved region of storage set aside for this purpose, until the required segment is found. The segments are also linked in one or other of a number of double-threaded lists which serve as control chains , one of which identifies modified segments which await writing to a backing store, and another of which identifies unmodified or backed-up segments which are available for LRU drop out. Any binding by the application program to a...