Algorithm. Mark sweep GC [cs-0008]

Mark-Sweep is a classic GC algorithm, it's combined with two parts, mark and sweep.

mark(root):
  if not marked?(root):
    mark(root)
  for obj in knowns(root):
    mark(obj)
sweep(heap):
  for obj in heap:
    if marked?(obj):
      unmark(obj)
    else:
      release(obj)

If we run collection (mark-sweep), then since each object is reachable from root, so no one would be released.

After do some executions, obj1 don't need obj3 anymore, so it became:

Now when we run collection, obj3 is unreachable from root, so it won't be marked! When running to sweep, it will be dropped.