Re: Ada GC (was about Java VM)

"It seems to me that in order to make progress in this discussion we
need an example of a hard real-time system that uses a general purpose
allocator with explicit deallocation. I claimed it can't be done if
you need reasonable space bounds. (Cf. Knuth, vol.1, 2nd ed, p. 255,
and the answers in the back. He cites a 1971 paper by Robson.) I have
also never seen a general purpose allocator/deallocator that supplied
time bounds adequate for a hard real-time system. (A buddy system
allocator without coalescing could probably do OK, but it's allocation
time is still quite variable, and its space utilization is
suboptimal.)"


Well there are several applicable algorithms, but we don't need to get
into that to argue this point. Just consider an application which can
successfully use fixed-length blocks. In this case it is trivial to
write a dynamuc storage allocator with constant time allocation and
deallocation, and no fragmentation effects. Note that fixed sized
blocks do not significantly help GC, but they certainly help
allocators with explicit deallocation.


I have seen a number of real time systems written in this kind of
allocation environment.


By having separate pools for separate lengths of blocks, one can
extend this technique to multiple sizes of blocks.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.