Markingbased

Markingbased, often written as marking-based, refers to a class of garbage collection techniques in memory management that determine object liveness by performing a marking pass over the object graph starting from a set of root references. In marking-based collectors, objects are either marked as reachable or unmarked; after marking, unmarked objects are reclaimed either by sweeping their memory or by relocation during a subsequent compaction step.

The core process typically involves two or more phases. The marking phase traverses all references from roots, recursively or iteratively marking reachable objects. A subsequent collection phase then reclaims the memory of objects that remain unmarked. Variants differ in whether they sweep immediately after marking (mark-and-sweep), or whether they relocate live objects to reduce fragmentation (mark-compact). Some implementations separate marking into incremental or concurrent steps to reduce pauses, enabling interleaved execution with the program.

Tri-color marking is a formal model frequently associated with marking-based collectors. In this model objects can be white (unseen), gray (seen but not fully scanned), or black (fully scanned). This abstraction helps manage the marking process, especially in concurrent or incremental garbage collectors.

Advantages of marking-based collectors include straightforward implementation, applicability to arbitrary object graphs, and the ability to reclaim cycles. Disadvantages can include pause times during marking or sweeping, potential disruption from compaction, and complexity when extending to concurrent or incremental variants.

Markingbased approaches have influenced many language runtimes and are foundational to classic garbage collection designs such as mark-and-sweep and mark-compact, as well as more advanced incremental and concurrent collectors used in modern environments.