Java Reference
In-Depth Information
Another variant is to maintain a number of free space lists, each containing
a range of sizes. When a request for size
s
is received, the free space list covering
s
's range is searched using a best fit strategy.
Fixed-Size Subheaps
Rather than linking free objects onto lists according to
their size, we can divide the heap into a number of
subheaps
, each allocating
objects of a single fixed size. We can then use a
bitmap
to track an object's
allocation status. That is, each object is mapped to a single bit in a large array.
A 1 indicates the object is in use; a 0 indicates it is free. We need no explicit
headers or free space lists. Moreover, since all objects are of the same size, any
object whose status bit is 0 may be allocated. However, subheaps may be used
unevenly, which can lead to poor memory utilization.
Allocating heap space is fairly straightforward. Requests for space are satisfied
by adjusting an end-of-heap pointer, or by searching a free space list. But how
do we deallocate heap memory no longer in use? Sometimes we may never
need to deallocate. If heap objects are allocated infrequently or are very long-
lived, deallocation is unnecessary. We simply fill heap space with “in use”
objects.
Unfortunately, many (perhaps most) programs cannot simply ignore deal-
location. Many programs allocate huge numbers of short-lived heap objects.
If we “pollute” the heap with large numbers of
dead objects
(that are no
longer accessible), locality can be severely impacted, with active objects spread
throughout a large address range. Long-lived or continuously running pro-
grams can also be plagued by
memory leaks
, in which dead heap objects
slowly accumulate until a program's memory needs exceed system limits.
User-Controlled Deallocation
Deallocation can be manual or automatic.
Manual deallocation involves explicit programmer-initiated calls to routines
like free(p) or delete(p).Pointerp identifies the heap object to be freed. The
object's size is stored in its header. The object may be merged with adjacent
unused heap objects (if boundary tags or an address-ordered free space list is
used). It is then added to a free space list for subsequent reallocation.
It is the programmer's responsibility to free unneeded heap space by
executing deallocation commands. The heap manager merely keeps track of
freed space and makes it available for later reuse. The really hard decision
(when space should be freed) is shifted to the programmer, possibly leading
to catastrophic
dangling pointer
errors. Consider the following C program
fragment:
