• Tags
  •         
  • www.breakyizhan.com
  •    

    Mark-and-Sweep:垃圾收集算法的背景

    动态创建的所有对象(在C ++和Java中使用new)都在堆中分配内存。如果我们继续创建对象,我们可能会出现Out Of Memory错误,因为无法将堆内存分配给对象。因此,我们需要通过为程序(或无法访问的对象)不再引用的所有对象释放内存来清除堆内存,以便空间可用于后续新对象。这个内存可以由程序员自己释放,但它似乎是程序员的开销,这里垃圾收集来救我们,它会自动释放所有未引用对象的堆内存。
    有许多垃圾收集算法在后台运行。其中之一是标记和扫描。

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

    标记阶段
    创建对象时,其标记位设置为0(false)。在Mark阶段,我们将所有可到达对象(或用户可以引用的对象)的标记位设置为1(true)。现在要执行此操作,我们只需要进行图遍历,深度优先搜索方法对我们有效。在这里,我们可以将每个对象视为一个节点,然后访问从该节点(对象)可到达的所有节点(对象),并且它一直持续到我们访问了所有可到达的节点。

    • Root是一个引用对象的变量,可以通过局部变量直接访问。我们假设我们只有一个根。
    • 我们可以通过:markedBit(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。
    Mark-and-Sweep:垃圾收集算法

    b)可达对象标记为true

    Mark-and-Sweep:垃圾收集算法

    c)从堆中清除不可到达的对象。

    Mark-and-Sweep:垃圾收集算法

    标记和扫描算法的优点

    • 它处理具有循环引用的情况,即使在循环的情况下,该算法也不会以无限循环结束。
    • 在执行算法期间不会产生额外的开销。

    标记和扫描算法的缺点

    • 标记和清除方法的主要缺点是在垃圾收集算法运行时正常程序执行被暂停。
    • 另一个缺点是,在标记和扫描算法在程序上运行多次之后,可到达的对象最终被许多小的未使用的存储区域分开。请查看下图以便更好地理解。
      数字:
    • Mark-and-Sweep:垃圾收集算法

    这里白色块表示空闲内存,而灰色块表示所有可到达对象占用的内存。
    现在,自由段(用白色表示)具有不同的大小,假设5个自由段的大小为1,1,2,3,5(单位大小)。
    现在我们需要创建一个占用10个单元内存的对象,现在假设只能以连续的块形式分配内存,尽管我们有12个单元的可用内存空间,但是无法创建对象,这将导致OutOfMemory错误。这个问题被称为“碎片化”。我们在“片段”中有内存,但我们无法利用该内存空间。
    我们可以通过压缩来减少碎片; 我们将内存内容混洗以将所有空闲内存块放在一起以形成一个大块。现在考虑上面的例子,在压缩之后我们有一个大小为12个单位的连续空闲内存块,所以现在我们可以将内存分配给一个大小为10个单位的对象。

     
    转载请保留页面地址:https://www.breakyizhan.com/java/4988.html