Editing Tracing garbage collection (section)

=== Naïve mark-and-sweep ===
[[File:Animation of the Naive Mark and Sweep Garbage Collector Algorithm.gif|thumb|upright=1.5|Naive mark-and-sweep in action on a [[Dynamic memory allocation#Manual memory management|heap]] containing eight [[Object (computer science)|objects]].  Arrows represent [[Reference (computer science)#References in object oriented languages|object references]]. Circles represent the objects themselves.  Objects #1, #2, #3, #4, and #6 are strongly referenced from the root set. On the other hand, objects #5, #7, and #8 are not strongly referenced either directly or indirectly from the root set; therefore, they are garbage. ]]

In the naive mark-and-sweep method, each object in memory has a flag (typically a single bit) reserved for garbage collection use only. This flag is always ''cleared'', except during the collection cycle. 

The first stage is the ''mark stage'' which does a tree traversal of the entire 'root set' and marks each object that is pointed to by a root as being 'in-use'. All objects that those objects point to, and so on, are marked as well, so that every object that is reachable via the root set is marked.

In the second stage, the ''sweep stage'', all memory is scanned from start to finish, examining all free or used blocks; those not marked as being 'in-use' are not reachable by any roots, and their memory is freed. For objects which were marked in-use, the in-use flag is cleared, preparing for the next cycle.

This method has several disadvantages, the most notable being that the entire system must be suspended during collection; no mutation of the working set can be allowed. This can cause programs to 'freeze' periodically (and generally unpredictably), making some real-time and time-critical applications impossible. In addition, the entire working memory must be examined, much of it twice, potentially causing problems in [[paged memory]] systems.