Multi-Threading and Garbage Collection

boehm@parc.xerox.com (Hans Boehm) writes:
>eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig) writes:
>>
>> I just don't see how you're going to allow garbage collection to
>>occur _anywhere_ and handle any sort of tagged heap. Are you assuming
>>that procedure calls and heap allocations are atomic? What happens if I
>>have to garbage collect while I'm in the middle of allocating a record,
>>and haven't written the length of the record to the heap yet?
>
>There are two ways of dealing with this. With high allocation rates, you
>probably need to give each thread its own chunk of memory that it can
>allocate from without synchronization. With lower allocation rates,
>allocation can acquire a lock to prevent conflicts. The PCR allocator
>acquires and releases a monitor lock (perhaps with some minor shortcut)
>for each allocation. This isn't free, but the only cost is during
>allocation. With Cedar-like (or Modula-3 like or C-like) allocation
>frequencies this probably makes sense. It's almost never a bottleneck.
>With SML-of-NJ like allocation rates, it's a bad idea.


Of course, even if the allocation rate _per_thread_ is fairly low,
one can still get into trouble if the number of threads is very high. If
enough threads are executing, it becomes likely that _some_ thread is
suspended in the middle of allocation, making any allocation by any other
thread _very_ expensive. Generally, though, this isn't much of a problem,
since few programs have a lot of threads. It is another good argument
against a single, multi-process heap (at the operating system lever),
however.


Strangely enough, I've recently stumbled onto a short
communication by Appel relating an interesting brute-force way around this
problem. One partitions the heap into several pages, and assign these
pages to threads on a as-needed basis; this allows each thread to allocate
without interfering with the others. When all the pages have run out, a
single, process-level garbage collector is used to recover the garbage
pages.


The _code_ of each thread is examined to determine if it was in
the process of allocating when it was suspended. If so, the allocation is
completed by the garbage collector by interpreting the machine
instructions of the thread. This is of course extremely expensive, but
since garbage collection is such a rare event the amortized cost can be
cheaper than manipulating some sort of monitor or semaphore.


(Appel, Andrew W, "Allocation Without Locking," _Soft._Prac._Exp
19(7) pp. 703-5)


--
Jack Eifrig (eifrig@cs.jhu.edu) The Johns Hopkins University, C.S. Dept.
--

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