function gcmalloc( s )
-- garbage-collection version of malloc; calls malloc and then
-- initiates collection of malloc indicates the heap is full.
temp = malloc(s)
if temp = null
return temp
else
markroots
sweep
return malloc(s) -- if this returns null, we're really out of memory
endif
procedure markroots
for p = current_ar to global_ar do
-- for every word on the stack
b = block(p)
if b non null
-- if the word could be a pointer to a block on the heap
mark(b) -- mark that block
endif
endfor
procedure mark(b)
if b->gc not marked
-- mark the block b found on the heap
b->gc = marked
for p = b to b + sizeof(b) do
-- for every word in the block
bb = block(p)
if bb non null
-- if the word could be a pointer to a block on the heap
mark(bb) -- mark that block (recursively)
endif
endfor
endif
procedure sweep
b = first_block
loop
nb = next_block( b )
if b->gc is not marked
free( b )
else
b->gc = not marked
endif
b = nb
until b = last_block
Part B: Here is a correct but very slow implementation of the block(p) function:
function block(p)
if p >= first_block and p <= last_block then
-- p points somewhere inside the heap
b = first_block
while b > p or next_block(b) <= p
b = next_block(b)
end loop -- guaranteed to terminate because p is in heap
return b
else
-- p points outside the heap
return null
endif
Faster implementations of block(p) will be be approximate! Consider:
function block(p)
if p >= first_block and p <= last_block then
b = p
loop
if b -> gc marked
or b -> gc not marked then
-- passed test 1 -- gc field of block is valid
if b = prev_block( next_block(p) )
-- passed test 2 -- pointer fields make sense
return b
endif
endif
b = b - 1;
endloop
else
-- p points outside the heap
return null
endif
The above code searches backward from the given pointer until it finds
a data structure that resembles a boundary tag. The first test for
resemblance is simple -- does the candidate for a tag contain the expected
constants (either marked or not marked) in the garbage collection field.
If this field is a word, and if the values selected to represent marked and
not marked are distinctive, this test will rarely pass except when a real
boundary tag is found. The second test checks the integrety of the data
structure of the boundary tags, checking to see if the pointers to the
next and previous blocks make sense. It is still possible that this test
will be passed for a data structure that is not really a boundary tag, but
it is extremely unlikely. Additional tests could be added, for example,
if every boundary tag includes a checksum on the pointer fields of the tag,
this could be tested.
Yet another solution to this problem can be constructed, based on a binary search of the list of all blocks in the heap. This would require that an auxiliary index data structure be maintained to support this search, but the cost of maintaining this auxiliary index is almost certainly less than the cost of the linear search used in the first alternative used above, and the resulting solution would be formally correct.
Problem 4 on page 394 of Tannenbaum asks for the same figure for a 256 processor hypercube. This hypercube is 8 dimensional (an n dimensional hypercube has 2n vertices), and the maximum hop-count occurs between processors on opposite corners of the hypercube. Opposite, in n dimensions, is defined as having coordinates that differ in each of the n dimensions, and the hop-count therefore involves one hop along each dimension. So, for a 256 processor hypercube, the maximum hop-count is 8.