Java Reference
In-Depth Information
as auxiliary bookkeeping information. (The size information is necessary to
properly “recycle” the block if it is later deallocated.) A minimum heap block
size (commonly 16 bytes) is usually imposed to simplify bookkeeping and
guarantee alignment.
The complexity of heap allocation depends in large measure on how heap
deallocation is done. Initially, the heap is one large block of unallocated
memory. Memory requests can be satisfied by simply modifying an “end of
heap”pointer,verymuchasastackispushedbymodifyingastackpointer.
Heap allocation gets more involved when previously allocated heap objects
are deallocated and reused. Some deallocation techniques compact the heap,
moving all “in use” objects to one end of the heap. This means unused heap
space is always contiguous, making allocation (via a heap pointer) almost
trivial.
Some heap deallocation algorithms have the useful property that their
speed depends not on the total number of heap objects allocated, but rather
only on those objects still in use . If most heap objects “die” soon after their
allocation (and often this does seem to be the case), deallocation of these objects
is essentially free.
Unfortunately, many deallocation techniques do not perform compaction.
Deallocated objects must be stored for future reuse. The most common ap-
proach is to create a free space list . A free space list is a linked (or doubly-
linked) list that contains all the heap blocks known to not be in use. Initially
it contains one immense block representing the entire heap. As heap blocks
are allocated, this block shrinks. When heap blocks are returned, they are
appended to the free space list.
The most common way of maintaining the free space list is to append
blocks to the head of the list as they are deallocated. This simplifies deallocation
a bit, but makes coalescing of free space di
cult.
It often happens that two blocks that are physically adjacent in the heap
are eventually deallocated. If we can recognize that the two blocks are now
both free and adjacent, then they can be coalesced into one larger free block.
One large block is preferable to two smaller blocks since the combined block
can satisfy requests too large for either of the individual blocks.
The boundary tags approach [Knu73a] allows us to identify and coalesce
adjacent free heap blocks. Each heap block, whether allocated or on the free
space list, contains a tag word on both of its ends. This tagword contains a flag
indicating “free” or “in use” and the size of the block. When a block is freed,
the boundary tags of its neighbors are checked. If either or both neighbors are
marked as free, then they are unlinked from the free space list and coalesced
with the current free block.
A free space list may also be kept in address order ; that is, sorted in order
of increasing heap addresses. Boundary tags are no longer needed to identify
 
Search WWH ::




Custom Search