有许多垃圾回收算法在后台运行，其中之一就是标记清除算法。
所有动态创建的对象（在 C++ 和 Java 中使用 new）都在堆中分配内存。如果我们不断创建对象，可能会因为无法为对象分配堆内存而遇到内存溢出错误。因此，我们需要通过释放那些不再被程序引用的对象（即不可达对象）的内存来清理堆，以便为后续的新对象腾出空间。虽然这些内存可以由程序员自己释放，但这显然增加了程序员的负担。于是，垃圾回收机制应运而生，它会自动释放所有未被引用对象的堆内存。
标记清除算法
任何垃圾回收算法都必须执行两个基本操作。首先，它必须能够检测所有不可达的对象；其次，它必须回收垃圾对象占用的堆空间，并将这些空间重新提供给程序使用。上述操作由标记清除算法通过两个阶段完成，具体如下：
- 标记阶段
- 清除阶段
第一阶段：标记阶段
当对象被创建时，其标记位被设置为 0（false）。在标记阶段，我们将所有可达对象（或用户可以引用的对象）的标记位设置为 1（true）。为了执行此操作，我们只需要进行图遍历，深度优先搜索方法就可以满足我们的需求。在这里，我们可以将每个对象视为一个节点，然后访问从该节点（对象）可达的所有节点（对象），一直持续到我们访问了所有可达的节点为止。
- 根是一个引用对象的变量，并且可以直接被局部变量访问。为了方便讨论，我们假设只有一个根。
- 我们可以通过 ‘markedBit(obj)‘ 来访问对象的标记位。
算法： 标记阶段
Mark(root)
If markedBit(root) = false then
markedBit(root) = true
For each v referenced by root
Mark(v)
> 注意： 如果我们有不止一个根，那么我们只需要对所有根变量调用 Mark() 即可。
第二阶段：清除阶段
顾名思义，该阶段“清除”不可达的对象，即清空所有不可达对象的堆内存。所有标记位仍为 false 的对象将从堆内存中清除，而对于所有其他对象（可达对象），其标记位被设置为 true（实际上在遍历前可达对象已标记为true，这里原文逻辑意为后续重置）。
现在，我们将所有可达对象的标记值重置为 false，因为如果需要再次运行算法，我们将再次进入标记阶段来标记所有可达对象。
算法： 清除阶段
Sweep()
For each object p in heap
If markedBit(p) = true then
markedBit(p) = false
else
heap.release(p)
标记清除算法被称为追踪式垃圾回收器，因为它会追踪程序可以直接或间接访问的整个对象集合。
示例：
A. 所有对象的标记位都设置为 false。
B. 可达对象被标记为 true
C. 不可达对象从堆中被清除。
标记清除算法的优点如下：
- 它可以处理循环引用的情况，即使存在循环，该算法也永远不会陷入死循环。
- 算法执行期间不会产生额外的开销。
标记清除算法的缺点如下：
- 这种方法的主要缺点是，在垃圾回收算法运行期间，正常的程序执行会被暂停。
- 另一个缺点是，在程序上多次运行标记清除算法后，可达对象最终会被许多细小的、未使用的内存区域隔开。请看下图以更好地理解。
这里白色块表示空闲内存，而灰色块表示所有可达对象占用的内存。
现在，让我们看看空闲段（用白色表示）的大小各不相同，假设 5 个空闲段的大小分别为 1、1、2、3、5（单位大小）。
假设我们需要创建一个占用 10 个单位内存的对象，并假设内存只能以连续形式分配，