Garbage Collection

Question

I am not able to understand few things on the Garbage collection.

Firstly, how is data allocated space ? i.e. on stack or heap( As per my knowledge, all static or global variables are assigned space on stack and local variables are assigned space on heap).

Second, GC runs on data on stacks or heaps ? i.e a GC algorithm like Mark/Sweep would refer to data on stack as root set right? And then map all the reachable variables on heap by checking which variables on heap refer to the root set.

What if a program does not have a global variable? How does the algorithm work then?

Regards, darkie

Answer 1

It might help to clarify what platform's GC you are asking about - JVM, CLR, Lisp, etc. That said:

First to take a step back, certain local variables of are generally allocated on the stack. The specifics can vary by language, however. To take C# as an example, only local Value Types and method parameters are stored on the stack. So, in C#, foo would be allocated on the stack:

public function bar() { 
    int foo = 2;
    ...
}

Alternatively, dynamically-allocated variables use memory from the heap. This should intuitively make sense, as otherwise the stack would have to grow dynamically each time a new is called. Also, it would mean that such variables could only be used as locals within the local function that allocated them, which is of course not true because we can have (for example) class member variables. So to take another example from C#, in the following case result is allocated on the heap:

public class MyInt
{         
    public int MyValue;
}

...
MyInt result = new MyInt();
result.MyValue = foo + 40;
...

Now with that background in mind, memory on the heap is garbage-collected. Memory on the stack has no need for GC as the memory will be reclaimed when the current function returns. At a high level, a GC algorithm works by keeping track of all objects that are dynamically allocated on the heap. Once allocated via new, the object will be tracked by GC, and collected when it is no longer in scope and there are no more references to it.

Answer 2

Check out the book Garbage Collection: algorithms for automatic dynamic memory management.