Browse Prior Art Database

Method for Dynamic Storage Management

IP.com Disclosure Number: IPCOM000074266D
Original Publication Date: 1971-Apr-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 43K

Publishing Venue

IBM

Related People

Blair, FW: AUTHOR

Abstract

This is an improved method of data storage management, hereinafter referred to as the "growing pain". The method applies to the case where space is allocated dynamically from various regions. It operates in such a manner that the various regions are all used up at about the same rate. This is important because whenever any region becomes filled the active data in that region must be identified, compacted and the space of abandoned data reclaimed for subsequent calculation. Furthermore, because of the nature of the identification process and the subsequent relocation process, it pays to reclaim all the regions whenever one becomes exhausted. Such a method is known in the prior art as a "garbage collecter".

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

Page 1 of 3

Method for Dynamic Storage Management

This is an improved method of data storage management, hereinafter referred to as the "growing pain". The method applies to the case where space is allocated dynamically from various regions. It operates in such a manner that the various regions are all used up at about the same rate. This is important because whenever any region becomes filled the active data in that region must be identified, compacted and the space of abandoned data reclaimed for subsequent calculation. Furthermore, because of the nature of the identification process and the subsequent relocation process, it pays to reclaim all the regions whenever one becomes exhausted. Such a method is known in the prior art as a "garbage collecter". Also shown, is the creation of super regions in which two data classes grow together from opposite ends of the super region.

The growing pain is an improvement to the technique of compacting garbage collectors for dynamic storage management. The typical situation that exists in the IBM System 360 LISP garbage collector is illustrated in the figure which shows a detail of storage layout. Thus, R = Cn + k over C1 - k

or, k = C1(R) - Cn over R + 1 where k is the adjustment which would achieve the desired apportionment.

Since k will always be nonzero it is uneconomical to redistribute every garbage collection. Instead, the ratio of the expected time between garbage collections (with current distributions) to the expected time between garbage collection is calculated if k is redistributed. The ratio is as follows: T over Tk = MIN[Cn, C1(R)] over MIN[Cn+k,(C1-k)R] This ratio is compared with a constant threshold v, and if it is greater than v the redistribution by k is carried out. An empirically useful value of v has been determined to be .75.

The redistribution by k is rounded to an integral number of pages. Page size moves may then be implemented in an efficient manner (e.g., on TSS by updating the system page table entries). It should be apparent that an entire block is shifted upward or downward as a whole. There is no difficulty in finding space for some useful data while other data is moved into its space, because the first moves are made into available space.

Each pointer quantity is the system is then examined to see if it falls into the area originally occupied by the moved block. If it does, it is updated by the amount that the block was shifted. The garbage collector acts to compact all active data. Garbage collection is activated whenever an attempt to allo...