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.
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.