Re: Register Allocators and Garbage Collectors

George Neuner <gneuner2@comcast.net>
Sat, 13 Sep 2008 20:49:59 -0400

          From comp.compilers

Related articles
Register Allocators and Garbage Collectors rand.chars@gmail.com (Ori Bernstein) (2008-09-09)
Re: Register Allocators and Garbage Collectors gneuner2@comcast.net (George Neuner) (2008-09-13)
Re: Register Allocators and Garbage Collectors marcov@stack.nl (Marco van de Voort) (2008-09-14)
Re: Register Allocators and Garbage Collectors niktechc@niktech.com (Sandeep Dutta) (2008-09-15)
Re: Register Allocators and Garbage Collectors rand.chars@gmail.com (Ori Bernstein) (2008-09-15)
Re: Register Allocators and Garbage Collectors rand.chars@gmail.com (Ori Bernstein) (2008-09-15)
Re: Register Allocators and Garbage Collectors gneuner2@comcast.net (George Neuner) (2008-09-16)
Re: Register Allocators and Garbage Collectors rand.chars@gmail.com (Ori Bernstein) (2008-09-17)
| List of all articles for this month |

From: George Neuner <gneuner2@comcast.net>
Newsgroups: comp.compilers
Date: Sat, 13 Sep 2008 20:49:59 -0400
Organization: A noiseless patient Spider
References: 08-09-052
Keywords: GC, parallel
Posted-Date: 14 Sep 2008 16:55:07 EDT

On Tue, 9 Sep 2008 20:28:36 -0700 (PDT), Ori Bernstein
<rand.chars@gmail.com> wrote:


>I was wondering how garbage collectors running in a thread in compiled
>languages typically would handle interactions with the register
>allocator keeping variables in use only in registers.
>
>For example, suppose we have code that looks like this:
>
>int x[];
>x = new int[10];
>x[3] = 42;
>
>
>And suppose it compiles to look like this:
>
>
> ; allocate 10 4 byte ints
>1 pushl $40
>2 call gc_alloc
> ; store 42 to the 3rd element of the array
>3 movl $42,12(%eax)
>
>
>If we get a context switch between lines 2 and 3, then the only record
>of a root pointing to the newly allocated value is in register %eax,
>and is hidden from the debugger thread.
>
>How do garbage collectors deal with this problem typically? Does the
>compiler have to insert spill points which force the values onto the
>stack and invoke the GC? Am I just on crack thinking that there might
>be a problem?


You're correct that your scenario will not work.


In a typical multi-threaded implementation, each thread maintains a
private heap which it can collect independently at any time. Objects
normally are created in the private heap. If the thread passes (hands
off) the object to another thread, it is copied to the new thread's
heap and becomes garbage to the original thread. If a thread stores a
reference to a private object in a shared object - a global binding or
anything transitively referenced from one - the private object will be
copied to the shared heap. Of course if the compiler can tell that
the object will immediately be shared it can directly allocate the
object in the shared heap. The shared heap may be collected either by
a dedicated thread or, in some systems, by any thread.


Collecting the shared heap requires collecting all the private heaps
as well because thread private objects may reference shared ones.
When a global collection is necessary, a typical method is send a
software interrupt each thread. The interrupt performs a private
collection and then either resumes or idles the thread. As part of
the private collection, the thread records references to shared
objects to be used as roots for the collection of the shared heap.


Whether threads are allowed to continue while the shared collection is
in progress depends on how the collector works. If it does not move
objects, it is safe to let the threads run. If the collector moves
objects, the threads generally must be idled while the collection is
running. If the threads are allowed to run, allocations in the shared
heap require synchronization with the collector so they are not
missed.


George


Post a followup to this message

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