next up previous
Next: A garbage collector Up: Data Structures Used Previous: Backing store organisation

The persistent heap

Figure 3.11: The organisation of the heap within a data segment. Note tha all heap blocks are of the same length.

The persistence manager can be thought of as having 3 layers of software.

  1. The segmented store manager, which handles the swapping of segments to and from disk and which provides primitives to allocate and extend persistent segments.

  2. The heap manager, which provides a multiplicity of persistent heaps and a garbage collector operating over them.

  3. The class manager, which is responsible for the allocation of intsances of persistent classes and ensuring that their methods are reachable.
The heap manager has to allocate and recover space for a large number of objects, of differing but generally small sizes. It would clearly be unwise to allocate whole segments to individual objects, as this would only permit the creation of a few thousand objects at the most. Instead, some scheme has to be divised to split up segments allowing each one to hold a number of logical objects. Object allocation has to be reasonably rapid, and there has to and, where possible, it should occur without triggering excessive segment swapping.

The approach taken has been to create a multiplicity of heaps, each of which occupies one segment. Within a heap, space is organised as a sequence of heap blocks of uniform size. For example figure 3.11 shows a heap made up of 13 byte heap blocks, each of which contains 12 bytes of usable space. Each block has a header byte which contains 3 flag bits. These indicate if a block is free or used, marked or unmarked, a leaf node or one containing pointers.

Since all blocks are the same size, no freelist is needed, instead, a pointer indicates the last block to have been allocated. Allocation proceeds as a cyclical search of the heap to find the next unused block. Should none be found, the heap is extended by growing the segment that contains it. Growth occurs according to the golden ratio . When the heap can grow no more, because of the 64K segment limit, a garbage collection is initiated. The unless the proportion of free space in the heap becomes very low, the cyclical search for a free block only has to visit a few block headers. The uniformity of block sizes within the heap means that the algorithm does not have to waste time visiting any nodes that are too small.

Figure 3.12: The storage allocation scheme uses multiple heaps. Each class has one or more heaps. Distinct heaps are provided for ranges of array sizes.

The restriction of a heap to the supply of blocks of a single size, implies that there must be multiple heaps available, if a range of object sizes is to be supported. Since one can not afford to have a unique heap for each possible object size, a compromise is reached whereby each distinct object class is assigned a heap whose storeage blocks are just large enough for the instances of the class. This leaves those data objects that do not belong to definite classes, basically arrays of various sizes. These are handled by a vector of heaps with ascending block sizes. Arrays are allocated from the heap with the smallest practicable block size. The overall arrangement is seen in figure 3.12.

Since the number of objects required for a class or a given range of array sizes may exceed what can reside in one heap, each class or array range can potentially have a list of heaps. The existence of lists of heaps could lead to delays and thrashing when allocating new objects. An attempt is made to obviate this by providing two pointers to the list. One points at the head of the list. A second, points at the heap currently being used for allocation. Thus if the first three heaps on the list were full, the current allocation might come from the fourth. This avoids visiting the full heaps each time an allocation occurs.

next up previous
Next: A garbage collector Up: Data Structures Used Previous: Backing store organisation

W Paul Cockshott
Fri Sep 6 10:29:18 BST 1996