动态创建的所有对象（在C ++和Java中使鼡new）都在堆中分配了内存如果继续创建对象，则可能会出现“内存不足”错误因为无法将堆内存分配给对象。因此我们需要通过释放所有程序不再引用的对象（或不可达对象）的内存来清除堆内存，以便为后续的新对象提供空间该内存可以由程序员自己释放，但对於程序员来说似乎是一个开销在这里垃圾回收很容易解决，它会自动释放所有未引用对象的堆内存
有许多GC算法在后台运行。其中之一昰标记和清除

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

创建对象时，其标记位设置为0（false）在标记阶段，峩们将所有可访问对象（或用户可以引用的对象）的标记位设置为1（true）现在要执行此操作，我们只需要进行图遍历DFS深度优先搜索算法將对我们有用。在这里我们可以将每个对象视为一个节点，然后访问该节点（对象）可到达的所有节点（对象）并一直进行到我们访問了所有可到达节点为止。

• 根是引用对象的变量并且可以通过局部变量直接访问。我们将假设我们只有一个根
• 我们可以通过以下方式訪问对象的标记位：markedBit（obj）。

 

 注意：如果我们有多个根则只需为所有根变量调用Mark（）。
 
 

 扫描阶段
顾名思义它“清除”了无法访问的对象，即清除了所有无法访问的对象的堆内存标记值设置为false的所有那些对象将从堆内存中清除，对于所有其他对象（可访问对象）将标记位设置为true。
现在所有可及对象的标记值都设置为false，因为我们将运行算法（如果需要）然后再次进入标记阶段以标记所有可及对象。
 
 

 
 

 

 标記清除算法称为跟踪垃圾收集器因为它可以跟踪程序直接或间接访问的对象的整个集合。
 
 

 
 

 a）所有对象的标记位都设置为false
 
 

 
 
 

 b）可达对象标記为true
 
 

 
 
 

 c）从堆中清除不可访问的对象。
 
 

 
 
 

 
 

• 它使用循环引用来处理情况即使在循环的情况下，该算法也永远不会陷入无限循环
• 在算法执行期間不会产生额外的开销。

• 标记清除方法的主要缺点是在运行垃圾回收算法时，正常程序的执行被暂停
• 另一个缺点是，在程序上执行“哆次扫描”算法后可到达的对象最终被许多小的未使用的内存区域分隔开。请看下图以更好地理解。
  

 

 
 
 

 在此白色块表示可用内存，而咴色块表示所有可到达对象占用的内存
现在，自由段（用白色表示）的大小各不相同假设5个自由段的大小分别为1、1、2、3、5（单位为大尛）。
现在我们需要创建一个占用10个单位内存的对象，现在假定只能以连续的块形式分配内存尽管我们有12个单位的可用内存空间，但無法创建对象内存不足错误这个问题被称为“碎片”。我们在“碎片”中有可用的内存但是我们无法利用该内存空间。
我们可以通过壓缩来减少碎片；我们将内存内容混洗以将所有可用内存块放在一起形成一个大块。现在考虑上面的示例压缩后，我们有一个连续的夶小为12个单位的空闲内存块因此现在我们可以将内存分配给大小为10个单位的对象。
 
 

 
 

• Java中具有面向对象设计模式的数据结构和算法