Re: Ada GC (was about Java VM)

dewar@cs.nyu.edu (Robert Dewar)
1 Feb 1996 21:41:27 -0500

          From comp.compilers

Related articles
[5 earlier articles]
Re: Ada GC (was about Java VM) Steve_Kilbane@cegelecproj.co.uk (1996-01-31)
Re: Ada GC (was about Java VM) kelvin@cs.iastate.edu (1996-01-31)
Re: Ada GC (was about Java VM) boehm@parc.xerox.com (1996-01-31)
Re: Ada GC (was about Java VM) jacobi@parc.xerox.com (1996-01-31)
Re: Ada GC (was about Java VM) jsa@organon.com (1996-01-31)
Re: Ada GC (was about Java VM) dewar@cs.nyu.edu (1996-02-01)
Re: Ada GC (was about Java VM) dewar@cs.nyu.edu (1996-02-01)
Re: Ada GC (was about Java VM) dewar@cs.nyu.edu (1996-02-01)
Re: Ada GC (was about Java VM) darius@phidani.be (Darius Blasband) (1996-02-01)
Re: Ada GC (was about Java VM) dave@occl-cam.demon.co.uk (Dave Lloyd) (1996-02-02)
Re: Ada GC bobduff@world.std.com (1996-02-02)
Re: Ada GC (was about Java VM) mg@asp.camb.inmet.com (1996-02-02)
Re: Ada GC jmartin@cs.ucla.edu (1996-02-02)
[17 later articles]
| List of all articles for this month |

From: dewar@cs.nyu.edu (Robert Dewar)
Newsgroups: comp.compilers,comp.lang.ada
Date: 1 Feb 1996 21:41:27 -0500
Organization: Courant Institute of Mathematical Sciences
References: 96-01-037 96-01-125 96-01-132 96-01-146
Keywords: Ada, GC, realtime

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


Post a followup to this message

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