标记和清除：垃圾收集算法

有很多 垃圾收集 在后台运行的算法，其中一个是标记和扫描。

所有动态创建的对象（使用C++和java中的新）都在堆中分配内存。如果我们继续创建对象，可能会出现内存不足的错误，因为无法将堆内存分配给对象。因此，我们需要通过释放程序不再引用的所有对象（或无法访问的对象）的内存来清除堆内存，以便为后续的新对象提供空间。这个内存可以由程序员自己释放，但对程序员来说，这似乎是一个开销，垃圾收集是我们的救星，它会自动释放所有未引用对象的堆内存。

标记扫描算法

任何垃圾收集算法都必须执行2个基本操作。首先，它应该能够检测到所有无法访问的对象，其次，它必须回收垃圾对象使用的堆空间，并使该空间再次可供程序使用。上述操作通过标记和扫描算法分两个阶段执行，如下所列，并进一步描述：

• 标记阶段
• 扫描阶段

第一阶段：标记阶段

创建对象时，其标记位设置为0（false）。在标记阶段，我们将所有可访问对象（或用户可以引用的对象）的标记位设置为1（真）。现在要执行这个操作，我们只需要做一个图遍历 深度优先搜索法 会对我们有用。在这里，我们可以考虑每个对象作为节点，然后访问从该节点（对象）可访问的所有节点（对象），并继续下去，直到我们访问了所有可达节点。

• 根是一个引用对象的变量，可由局部变量直接访问。我们假设我们只有一个根。
• 我们可以通过 “标记位（obj）” .

算法： 标记阶段

Mark(root)
If markedBit(root) = false then
                     markedBit(root) = true
                                       For each v referenced by root
                                       Mark(v)

注： 如果我们有多个根，那么我们只需要为所有根变量调用Mark（）。

第二阶段：扫描阶段

顾名思义，它会“扫描”不可访问的对象，即清除所有不可访问对象的堆内存。将从堆内存中清除标记值设置为false的所有对象，对于所有其他对象（可访问对象），将标记位设置为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个内存单元的对象，现在假设内存只能以块的连续形式分配，创建一个对象是不可能的，尽管我们有12个单元的可用内存空间，这将导致 OutOfMemory错误 .

这个问题被称为“碎片化”。我们有可用的“片段”内存，但我们无法利用这些内存空间。我们可以通过压实来减少碎片；我们洗牌内存内容，将所有空闲内存块放在一起，形成一个大块。现在考虑上面的例子，在压缩之后，我们有一个大小为12个单位的连续内存块，所以现在我们可以将内存分配给大小为10个单位的对象。

本文由 希拉格·阿加瓦尔。 如果你喜欢GeekSforgeks，并且想贡献自己的力量，你也可以写一篇文章，然后把你的文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。