PLS Lab

Garbage Collection

Garbage collection is a process that automatically frees up memory not being used by a program. A garbage collector is a link that is also required to serve memory allocation requests.

The garbage collection process typically works by periodically scanning the memory used by a program to identify objects that are no longer being referenced or used. These objects are then marked as "garbage", and the memory they occupy is freed up by the garbage collector. This helps prevent memory leaks, which can cause a program to use up more and more memory over time and eventually crash.

There are different types of garbage collection algorithms, such as mark-and-sweep, reference counting, and copying. Each algorithm has its own advantages and disadvantages, and the choice of algorithm depends on the specific requirements of the program being developed.

Modeling the Memory as a Graph

The heap area of memory can be thought of as a set of objects with the following attributes: a memory address, size, and a set of references to other objects. This way, the objects and their references constitue vertices and edges of a graph.

Similarly, the stack area of memory can also be modeled as a graph, we label the stack objects as "root" objects which have references pointing to the heap objects (or non-root objects).

More formally, we have modeled the memory as a graph M=(O,R) where O is the set of memory objects (vertices), and R is the set of references (edges). The graph M here represents the memory as a whole. Two subgraphs S=(O_s,R_s) and H=(O_h, R_h) of the graph M. THe subgraph S represents the stack area of memory and the subgraph H represents the heap area of memory, respectively.

Reachability: We say that some object o \in O_h is "reachable" if there is a o' \rightsquigarrow o path in M for some object o' \in S.

Notion of "aliveness"

We define the set Alive \subseteq O_h of "alive" objects. An object in H is alive if and only if its is reachable from some object on the stack. That is, \forall{a \in Alive}, \exists{s \in O_s} such that there is a path from s to a in M.

Garbage: All objects in the heap, that are not reachable from the stack are classified as "garbage".

Syntactic Garbage: Heap memory blocks that are not reachable from the stack area.

Semantic Garbage: Heap memory blocks that the program would never use again.

The Perfect Garbage Collector

An ideal garbage collector should have the following properties:

These are some of the goals while desigining a garbage collection algorithm.

Garbage Collection Algorithms

Garbage collection algorithms have been an active field of research since the 1960's. There are different variations of the basic algorithm. Some of the metrics and optimization areas in garbage collection algorithms are:

A Naïve Tracing Algorithm

A tracing algorithm is used to determine objects that are alive. Given the graph M=(O,R), and subgraphs S=(O_s,R_s) where O_s \subseteq O, R_s \subseteq R, and H=(O_h,R_h) where O_h \subseteq O, R_h \subseteq R, and O_s \cap O_h = \emptyset. A garbage collection algorithm will compute the alive and garbage sets. Consider this naïve garbage collection algorithm called "Find the Reachable".

Input:M=(O,R), S=(O_s,R_s), H=(O_h,R_h)
Output: Alive, Garbage

Find the Reachable:

  Alive=\empty
  Garbage=\empty

  for each u \in O_s:
    if u\rightsquigarrow v where v \in O_h:
      Alive = Aive \cup \{v\}

  for each u \in Alive:
    if u \rightsquigarrow v such that v \in O_h \wedge v \notin Alive:
      Alive = Aive \cup \{v\}
  Garbage= O_h \setminus Alive
  return (Alive,Garbage)

Mark-Sweep Collector

A Mark-Sweep garbage collector would perfrom a scan of the heap area of memory and mark them as "dead" or "alive". Usually, an additional data structure is needed for this task to store a mark bit (0/1) for each object. A memory cell is marked "alive" when the cell has references pointing to it from stack area or from someother memory cell in the heap that is alive.

  1. Initially, the mark bit for all memory cells is set to 0. In the marking phase, the mark-bit of memory cells that are alive is set to 1. The naïve tracing algorithm (or variations of it) mentioned in the previous section can be used for the marking phase The marking phase is followed by a sweeping phase.
  2. In the sweeping phase, unmarked objects (objects that have thier mark bit set as 0) are deleted from the heap. This might cause the heap to be fragmented (have holes). New allocation requests can be served by trying to allocate a fragment if large enough for the size of the object requested to be allocated.
  3. Some implementations might perform a compaction of the heap memory after the sweeping phase to remove holes in the heap. Not having holes in the heap will make it easier to serve new allocation requests.

Compaction can be an expensive operation and this leads to necessity of better and more efficient garbage collection algorithms. The time complexity of the mark-sweep algorithm is linear w.r.t the heap size. However, there is an overhead involved during memory allocation due to fragmentation. Hence, a mark-sweep algorithm might be optimal in a scenario where there is a series of allocation requests in the initial stage of the program, followed by objects becoming unreachable after that. This will eliminate the need to allocate objects when the heap is fragmented.

Copying Collector

  1. A copying collector would divide the heap into a "from-space" and "to-space".
  2. During a garbage collection cycle, memory locations in the from space are traced and live locations are copied to the "to-space". The "from-space" is cleared up.
  3. When the "to-space" fills up, the roles switch: "to-space" becomes "from-space" and vice-versa.

The advantage of a copying collector is that it has a very low allocation cost. Allocation can be done in O(1) time (amortized). Hence, a copying collector would be ideal when a program has a large number of allocation requests. A drawback would be the need for more garbage collection cycles as there is only half of the heap available for allocation (and "alive" objects).

Generational Garbage Collector

Emprical analysis of applications has shown that most objects are short lived. This observation motivated the idea of having a generational garbage collector.

Generational garbage collectors are usually concurrent garbage collectors where a garbage collection cycle happens simultaneously during program execution by using multiple CPU cores.

References