Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Let's say it is a concurrent mark-and-sweep garbage collector.

When such GC handles constant pointers it just walks through them (starting from roots), and marks every encountered data block. Then sweeps everything unmarked. A client code should mark the data blocks it uses as roots.

But what to do with variables? Here is a situation:

  1. V is a variable, which stores a pointer to object A.
  2. Thread 1 reads V and suspends.
  3. Thread 2 modifies V and makes it point to object B.
  4. The garbage collector runs its "mark" phase and encounters that A is no longer referenced, then deallocates it during the "sweep" phase.
  5. Thread 1 awakens and tries to use A (already read from V at step 2) by marking it as root. And fails, because A is no longer exists.

So, how to handle this?

The Thread 2 can mark the replaced object A with a special do-not-remove flag (similar flag is used for newly allocated objects). But when this flag should be removed? Of course Thread 1 could do that. But Thread 2 knows nothing about Thread 1, and thus can not be sure that this will be done ever. This may lead to A will never be freed. And if GC will remove that flag, then nothing prevents A from being removed when GC runs for the second time...

The on-the-fly mark-and-sweep garbage collector descriptions I've read just mention that the replaced object should be "grayed". But without any specifics. A link to a more detailed description of the solution would be highly appreciated.

share|improve this question

2 Answers 2

Depending on the precise details of the garbage collector implementation, this may not be a problem at all in your step 4. For example, in step 2, thread 1 presumably reads V into a register. The garbage collector will probably need to examine the contents of the registers for all active (running and suspended) threads to see if there is a reference to any object held in the registers.

Inevitably, a garbage collector implementation is tightly coupled to the operating (and threading) environment in which it runs. There are many implementation techniques for ensuring that all stored and transient references are considered.

share|improve this answer
    
But is there any way to do it in a platform-independent way? The register may contain the data, which only looks like a pointer, but in fact it is not. My GC implementation is exact and relies on the fact that any pointer it processes points to a data block of certain structure. –  lorus Mar 6 '13 at 4:08
    
Hmm, but this is an idea! I can place such such pointer to some known place in the stack (or thread-local variable) and make GC examine it. –  lorus Mar 6 '13 at 4:10
    
@lorus - for many garbage collectors, the tables generated by the compiler tell the GC what registers contain pointers at any given point in a method. For others, the GC only runs at a "safe point" which implicitly invalidates the register contents. Also, GC implementations are inherently platform dependent at some level. –  Stephen C Mar 6 '13 at 4:49
    
@StephenC Well, I don't think so general purpose algorithm like garbage collection requires to be so platform-dependent. Atomic operations and memory barriers - yes. But direct access to registers? No, I don't think so. It would be efficient, but I believe it is not absolutely required. I would like to know more about such platform-independent algorithms. –  lorus Mar 6 '13 at 5:07

You have to mark local variables sometime during the mark phase. All local variables, including those that normally live on stack. Somehow.

I additionally think it has to be done during the synchronous (all mutators stopped) phase of scanning modified objects. In fact the same problem might arise even without considering local variables/registers. Consider object A pointing to null and object B pointing to C. Now you scan object A, a mutator thread comes, copies the reference to C from B to A, nulls out B. And now you get around to scanning B. And C slipped under your fingers.

I don't know about any way for dealing with this that wouldn't involve stopping the mutators. The usual technique is at the end of mark phase to stop all mutators and re-mark all objects that they mutated during the main marking phase. And include stacks and registers in that.

Marking registers is normally worked around by doing it synchronously by calling the collector in the thread sometimes. Inside the collector function, only it's own local variables (which are not roots) can be in registers, all other local variables in the call chain are on stack, so you can walk the stack.

Alternatively you can send a signal to the thread. The signal handler will again force all variables on the stack, so you can walk them. Disadvantage of this method is that it is platform dependent.

share|improve this answer
    
Yes. But situation a was talking about is not about a local variable. It is about a global one, which can be simultaneously accessed and modified by different threads. –  lorus Mar 6 '13 at 8:27
    
if after thread1 has read V and A isn't in a local variable of thread1 then A won't be reachable after thread2 modified V, so it will be ready for collection anyway –  ratchet freak Mar 6 '13 at 8:32
    
@lorus: If a thread loads something into register, the register is it's local variable. Whether it was mentioned in high-level source or added by the compiler does not matter. You just treat it as local variable. –  Jan Hudec Mar 6 '13 at 8:44
    
@JanHudec Ok. Now I get it. So, the calling the collector in the (client) thread is actually some kind of a global lock? –  lorus Mar 6 '13 at 8:53
1  
@JanHudec unless the threads work with the GC and can add objects to a to-mark queue, each time a thread reads a reference –  ratchet freak Mar 6 '13 at 15:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.