精华内容
下载资源
问答
  • 引用计数法
    2022-05-01 10:29:08

    引用计数法

    关于引用计数法,我们可以先看一段wiki上的描述:

    As a collection algorithm, reference counting tracks, for each object, a count of the number of references to it held by other objects. If an object's reference count reaches zero, the object has become inaccessible, and can be destroyed.

    When an object is destroyed, any objects referenced by that object also have their reference counts decreased.

           作为一种回收算法,引用计数法记录着每一个对象被其它对象所持有的引用数。如果一个对象的引用计数为零,那么该对象就变成了所谓的不可达对象,亦即可以被回收的。

           当一个对象被回收后,被该对象所引用的其它对象的引用计数都应该相应减少。

           而所谓的循环引用(circular referrence)有是什么意思呢?举个简单的例子:

     
    
    public class MyObject {
    
    public Object ref = null;
    
    public static void main(String[] args) {
    
    MyObject myObject1 = new MyObject();
    
    MyObject myObject2 = new MyObject();
    
    myObject1.ref = myObject2;
    
    myObject2.ref = myObject1;
    
    myObject1 = null;
    
    myObject2 = null;
    
    }
    
    }

           从上面的代码可以轻易地发现myObject1与myObject2互为引用,我们知道如果采用引用计数法,myObject1和myObject2将不能被回收,因为他们的引用计数无法为零。

    wKioL1MyZ-SDBSeHAAFo1QsAt2U761.jpg

           但是具体是为什么呢?已上图为例,当代码执行完line7时,两个对象的引用计数均为2。此时将myObject1和myObject2分别置为null,以前一个对象为例,它的引用计数将减1。若要满足垃圾回收的条件,需要清除myObject2中的ref这个引用,而要清除掉这个引用的前提条件是myObject2引用的对象被回收,可是该对象的引用计数也为1,因为myObject1.ref指向了它。以此类推,也就进入一种死循环的状态。

    可达性分析

    为了解决引用计数法的循环引用问题,Java 使用了可达性分析的方法。通过一系列的“GC roots” 对象作为起点搜索。如果在“GC roots”和一个对象之间没有可达路径,则称该对象是不可达的。

    要注意的是,不可达对象不等价于可回收对象,不可达对象变为可回收对象至少要经过两次标记过程。两次标记后仍然是可回收对象,则将面临回收

    更多相关内容
  • 本文是《垃圾回收的算法与实现》读书笔记引用计数算法给对象中添加一个引用计数器,每当有一个地方引用它时,计数器的值就加1;当引用失效时,计数器值就减1;...计数器的增减引用计数法没有明确启动 G...

    本文是《垃圾回收的算法与实现》读书笔记

    引用计数算法

    给对象中添加一个引用计数器,每当有一个地方引用它时,计数器的值就加1;当引用失效时,计数器值就减1;任何时刻计数器为0的对象就是不可能再被使用的。这也就是需要回收的对象。

    引用计数算法是对象记录自己被多少程序引用,引用计数为零的对象将被清除。

    计数器表示的是有多少程序引用了这个对象(被引用数)。计数器是无符号整数。

    计数器的增减

    引用计数法没有明确启动 GC 的语句,它与程序的执行密切相关,在程序的处理过程中通过增减计数器的值来进行内存管理。

    new_obj() 函数

    与GC标记-清除算法相同,程序在生成新对象的时候会调用 new_obj()函数。

    func new_obj(size){

    obj = pickup_chunk(size, $free_list)

    if(obj == NULL)

    allocation_fail()

    else

    obj.ref_cnt = 1 // 新对象第一只被分配是引用数为1

    return obj

    }

    这里 pickup_chunk()函数的用法与GC标记-清除算法中的用法大致相同。不同的是这里返回 NULL 时,分配就失败了。这里 ref_cnt 域代表的是 obj 的计数器。

    在引用计数算法中,除了连接到空闲链表的对象,其他对象都是活跃对象。所以如果 pickup_chunk()返回 NULL,堆中也就没有其它大小合适的块了。

    update_ptr() 函数

    update_ptr() 函数用于更新指针 ptr,使其指向对象 obj,同时进行计数器值的增减。

    func update_ptr(ptr, obj){

    inc_ref_cnt(obj) // obj 引用计数+1

    dec_ref_cnt(*ptr) // ptr之前指向的对象(*ptr)的引用计数-1

    *ptr = obj

    }

    这里 update_ptr 为什么需要先调用 inc_ref_cnt,再调用dec_ref_cnt呢?

    是因为有可能 *ptr和 obj 可能是同一个对象,如果先调用dec_ref_cnt可能会误伤。

    inc_ref_cnt()函数

    这里inc_ref_cnt函数只对对象 obj 引用计数+1

    func inc_ref_cnt(obj){

    obj.ref_cnt++

    }

    dec_ref_cnt() 函数

    这里 dec_ref_cnt 函数会把之前引用的对象进行-1 操作,如果这时对象的计数器变为0,说明这个对象是一个垃圾对象,需要销毁,那么被它引用的对象的计数器值都需要相应的-1。

    func dec_ref_cnt(obj){

    obj_ref_cnt--

    if(obj.ref_cnt == 0)

    for(child : children(obj))

    dec_ref_cnt(*child) // 递归将被需要销毁对象引用的对象计数-1

    reclaim(obj)

    }

    231816d3e99e5eb80cf0a5795e6d69b9.png

    上图这里开始时,A 指向 B,第二步 A 指向了 C。可以看到通过更新,B 的计数器值变为了0,因此 B 被回收(连接到空闲链表),C 的计数器值由1变成了2。

    通过上边的介绍,应该可以看出引用计数垃圾回收的特点。

    在变更数组元素的时候会进行指针更新

    通过更新执行计数可能会产生没有被任何程序引用的垃圾对象

    引用计数算法会时刻监控更新指针是否会产生垃圾对象,一旦生成会立刻被回收。

    所以如果调用 pickup_chunk函数返回 NULL,说明堆中所有对象都是活跃对象。

    引用计数算法的优点

    可立即回收垃圾

    每个对象都知道自己的引用计数,当变为0时可以立即回收,将自己接到空闲链表

    最大暂停时间短

    因为只要程序更新指针时程序就会执行垃圾回收,也就是每次通过执行程序生成垃圾时,这些垃圾都会被回收,内存管理的开销分布于整个应用程序运行期间,无需挂起应用程序的运行来做,因此消减了最大暂停时间(但是增多了垃圾回收的次数)

    最大暂停时间,因执行 GC 而暂停执行程序的最长时间。

    不需要沿指针查找

    产生的垃圾立即就连接到了空闲链表,所以不需要查找哪些对象是需要回收的

    引用计数算法的缺点

    计数器值的增减处理频繁

    因为每次对象更新都需要对计数器进行增减,特别是被引用次数多的对象。

    计数器需要占用很多位

    计数器的值最大必须要能数完堆中所有对象的引用数。比如我们用的机器是32位,那么极端情况,可能需要让2的32次方个对象同时引用一个对象。这就必须要确保各对象的计数器有32位大小。也就是对于所有对象,必须保留32位的空间。

    假如对象只有两个域,那么其计数器就占用了整体的1/3。

    循环引用无法回收

    这个比较好理解,循环引用会让计数器最小值为1,不会变为0。

    循环引用

    class Person{ // 定义 Person 类

    string name

    Person lover

    }

    lilw = new Person("李雷") // 生成 person 类的实例 lilw

    hjmmwmw = new Person("韩梅梅") // 生成 person 类的实例 hjmwmw

    lilw.lover = hjmwmw // lilw 引用 hjmwmw

    hjmwmw.lover = lilw // hjmwmw 引用 lilw

    像这样,两个对象相互引用,所以各个对象的计数器都为1,且这些对象没有被其他对象引用。所以计数器最小值也为1,不可能为0。

    延迟引用计数法

    引用计数法虽然缩小了最大暂停时间,但是计数器的增减处理特别多。为了改善这个缺点,延迟引用计数法(Deferred Reference Counting)被研究了出来。

    通过上边的描述,可以知道之所以计数器增减处理特别繁重,是因为有些增减是根引用的变化,因此我们可以让根引用的指针变化不反映在计数器上。比如我们把 update_ptr($ptr, obj)改写成*$ptr = obj,这样频繁重写对重对象中引用关系时,计数器也不需要修改。但是这有一个问题,那就是计数器并不能正确反映出对象被引用的次数,就有可能会出现,对象仍在活动,却被回收。

    在延迟引用计数法中使用ZCT(Zero Count Table),来修正这一错误。

    ZCT 是一个表,它会事先记录下计数器在 dec_ref_cnt()函数作用下变成 0 的对象。

    1a67350a5d8cb64c489f5ff054a10d29.png

    dec_ref_cnt 函数

    在延迟引用计数法中,引用计数为0 的对象并不一定是垃圾,会先存入到 zct 中保留。

    func dec_ref_cnt(obj){

    obj_ref_cnt--

    if(obj.ref_cnt == 0) //引用计数为0 先存入到 $zct 中保留

    if(is_full($zct) == TRUE) // 如果 $zct 表已经满了 先扫描 zct 表,清除真正的垃圾

    scan_zct()

    push($zct, obj)

    }

    scan_zct 函数

    func scan_zct(){

    for(r: $roots)

    (*r).ref_cnt++

    for(obj : $zct)

    if(obj.ref_cnt == 0)

    remove($zct, obj)

    delete(obj)

    for(r: $roots)

    (*).ref_cnt--

    }

    第二行和第三行,程序先把所有根直接引用的计数器都进行增量。这样,来修正计数器的值。

    接下来检查 $zct 表中的对象,如果此时计数器还为0,则说明没有任何引用,那么将对象先从 $zct中清除,然后调用 delete()回收。

    delete() 函数定义如下:

    func delete(obj){

    for(child : children(obj)) // 递归清理对象的子对象

    (*child).ref_cnt--

    if (*child).ref_cnt == 0

    delete(*child)

    reclaim(obj)

    }

    new_obj() 函数

    除 dec_ref_cnt 函数需要调整,new_obj 函数也要做相应的修改。

    func new_obj(size){

    obj = pickup_chunk(size, $free_list)

    if(obj == NULL) // 空间不足

    scan_zct() // 扫描 zct 以便获取空间

    obj = pickup_chunk(size, $free_list) // 再次尝试分配

    if(obj == NULL)

    allocation_fail() // 提示失败

    obj.ref_cnt = 1

    return obj

    }

    如果第一次分配空间不足,需要扫描 $zct,以便再次分配,如果这时空间还不足,就提示失败

    在延迟引用计数法中,程序延迟了根引用的计数,通过延迟,减轻了因根引用频繁变化而导致的计数器增减所带来的额外的负担。

    但是,延迟引用计数却不能马上将垃圾进行回收,可立即回收垃圾这一优点也就不存在了。scan_zct函数也会增加程序的最大暂停时间。

    Sticky 引用计数法

    对于引用计数法,有一个不能忽略的部分是计数器位宽的设置。假设为了反映所有引用,计数器需要1个字(32位机器就是32位)的空间。但是这会大量的消耗内存空间。比如,2个字的对象就需要一个字的计数器。也就是计数器会使对象所占的空间增大1.5倍。

    sticky 引用计数法就是用来减少位宽的。

    如果我们为计数器的位数设为5,那么计数器最大的引用数为31,如果有超过31个对象引用,就会爆表。对于爆表,我们怎么处理呢?

    1. 什么都不做

    这种处理方式对于计数器爆表的对象,再有新的引用也不在增加,当然,当计数器为0 的时候,也不能直接回收(因为可能还有对象在引用)。这样其实是会产生残留的对象占用内存。

    不过,研究表明,大部分对象其实只被引用了一次就被回收了,出现5位计数器溢出的情况少之又少。

    爆表的对象大部分也都是重要的对象,不会轻易回收。

    所以,什么都不做也是一个不错的办法。

    2. 使用GC 标记-清除算法进行管理

    这种方法是,对于爆表的对象,使用 GC 标记-清除算法来管理。

    func mark_sweep_for_counter_overflow(){

    reset_all_ref_cnt()

    mark_phase()

    sweep_phase()

    }

    首先,把所有对象的计数器都设为0,然后进行标记和清除阶段。

    标记阶段代码为:

    func mark_phase(){

    for (r: $roots) // 先把根引用的对象推到标记栈中

    push(*r, $mark_stack)

    while(is_empty($mark_stack) == False) // 如果堆不为空

    obj = pop($mark_stack)

    obj.ref_cnt++

    if(obj.ref_cnt == 1) // 这里必须把各个对象及其子对象堆进行标记一次

    for(child : children(obj))

    push(*child, $mark_stack)

    }

    在标记阶段,先把根引用的对象推到标记栈中

    然后按顺序从标记栈中取出对象,对计数器进行增量操作。

    对于循环引用的对象来说,obj.ref_cnt > 1,为了避免无谓的 push 这里需要进行 if(obj.ref_cnt == 1) 的判断

    清除阶段代码为:

    func sweep_phase(){

    sweeping = $heap_top

    while(sweeping < $heap_end) // 因为循环引用的所有对象都会被 push 到 head_end 所以也能被回收

    if(sweeping.ref_cnt == 0)

    reclaim(sweeping)

    sweeping += sweeping.size

    }

    在清除阶段,程序会搜索整个堆,回收计数器仍为0的对象。

    这里的 GC 标记-清除算法和上一篇GC 标记-清除算法 主要不同点如下:

    开始时将所有对象的计数器值设为0

    不标记对象,而是对计数器进行增量操作

    为了对计数器进行增量操作,算法对活动对象进行了不止一次的搜索。

    这里将 GC 标记-清除算法和引用计数法结合起来,在计数器溢出后,对象称为垃圾也不会漏掉清除。并且也能回收循环引用的垃圾。

    因为在查找对象时不是设置标志位而是把计数器进行增量,所以需要多次查找活动对象,所以这里的标记处理比以往的标记清除花的时间更长,吞吐量会相应的降低。

    参考链接

    最后,感谢女朋友支持和包容,比❤️

    也可以在公号输入以下关键字获取历史文章:公号&小程序 | 设计模式 | 并发&协程

    展开全文
  • GC-引用计数法

    千次阅读 2019-04-08 21:16:19
    GC-引用计数法 GC:释放怎么都无法被引用的对象的机制。 引用计数法在对象的元数据区,加入了计数器,用于表示当前对象被引用了多少次。 引用计数法与其他GC算法相比,在于GC的的调用时机:GC标记-清除算法是在没有...

    GC-引用计数法

    GC:释放怎么都无法被引用的对象的机制。

    引用计数法在对象的元数据区,加入了计数器,用于表示当前对象被引用了多少次。
    在这里插入图片描述
    引用计数法与其他GC算法相比,在于GC的的调用时机:GC标记-清除算法是在没有可用分块时,会调用GC函数,进行垃圾处理回收,即是一种无侵入式的GC,这样就造成,最大暂停时间较大,此外,标记-清除算法即是产生了垃圾,也不会将其马上回收,只会在没有分块的时候,将垃圾一并回收;GC引用计数法是一种侵入式算法,其最大暂停时间表现较好,比较均匀,内存管理和mutator同时运行是引用计数法的一大特征。

    在引用计数法中,只有两种,连接到空闲链表的对表,其余都是活动对象。引用计数法中,对象的状态监控是实时的。

    GC-引用计数法的主要内容:

    new_obj(size){//创建对象,分配内存块
        obj=pickup_chunk(size,$free_list)
        if(obj==NULL)
            allocation_fail()
        else
            obj.ref_cnt=1
            return obj
    }
    update_ptr(){ //mutator,引用改变
        inc_ref_cnt(obj)//计数增量
        dec_ref_cnt(*ptr)//计数减量
        *ptr=obj
    }
    //先增量,再减量,主要原因是解决obj和ptr指向同一对象的问题,若先减量,则该对象
    //可能已经成为垃圾,从而造成bug
    inc_ref_cnt(obj){
        obj.ref_cnt++
    }
    dec_ref_cnt(obj){
        obj.ref_cnt--
        if(obj.ref_cnt==0)//没有引用了,即是垃圾了,遍历子对象,进行减量操作
            for(child:children(obj))
                dec_ref_cnt(*child)
            reclaim(obj) //回收
    }
    

    优点:可即刻回收垃圾,当对象计数为0时,会立刻回收;最大暂停时间短,mutator更新指针时才会执行垃圾回收,是一种侵入式,可有效消减最大暂停时间,即将该时间分散到了指针更新时;没有必要沿指针查找,不会像标记-清除算法一样从跟开始遍历。

    在分布式环境中,如果要沿各个计算节点之间的指针进行查找,成本就会增加,就需要极力控制沿指针查找的次数,所以有一种做法是,在各个计算节点内回收垃圾使用GC垃圾-清除算法,在考虑到节点间的引用关系时则采用引用计数法。

    缺点:计数器值的增减处理繁重,只要更新指针,就会进行计数器更新,所以值的增减处理会变得繁重;计数器需要占用很多位,32位机器,可能要让2的32次方个对象同时引用一个对象,考虑这种情况,就需要32位大小,这会使内存空间的使用效率降低;实现繁琐复杂,因为该算法是侵入式的,即需要把*ptr=obj全部更换成update_ptr(ptr,obj);循环引用无法回收,每个对象都有引用计数,就无法回收,但其本身已经是垃圾了。

    class Person{
        string name
        person laver
    }
    A=new Person("A")
    B=new Person("B")
    A.lover=B //循环引用
    B.lover=A
    A=NULL //对于根指针,没有对象引用,已经是垃圾了
    B=NULL
    

    针对GC-引用计数法的一些缺点,进行相关改进:延时引用计数法可解决计数器增减繁重的问题;Sticky引用计数法,可一降低计数器的宽度,提高空间利用率;1位引用计数法,是一种特殊的Sticky引用计数法,使用指针的的后两位作为计数器;部分标记-清除算法,可解决循环引用问题。

    延迟引用计数法:对引用计数延迟操作

    指针引用对象变化,不会立即更新到,这将引用变化更新推迟,推迟到空闲链表中没有满足的分块,同一进行扫描更新。具体体现在将upate_ptr( p t r , o b j ) 改 为 ∗ ptr,obj)改为* ptr,obj)ptr=obj,也就是计数更新只在创建对象时。
    延迟引用计数法,引入一个ZCT(Zero Count Table)表,会事先记录下计数器值在dec_ref_cnt()函数的作用下变为0的对象。之后会扫描该表,更新计数,更新方法同标记-引用算法,从根开始递归扫描。
    在这里插入图片描述

    计数器值为0的对象不一定都是垃圾?因为该改进算法,只在对象生成是计数器+1,之后的引用,并没有更新,所以为0,不一定是垃圾,记录到zct表中,后续遍历确认。

    dec_rec_cnt(obj){
        obj.ref_cnt-- 
        if(obj.ref_cnt==0)//表中记录可能是垃圾的对象
            if(is_full($zct)==TRUE)
                scan_zct()//表满时,进行垃圾扫描和回收
            push($zct,obj)
    }
    new_obj(size){
        obj=pickup_chunk(size,$free_list)//没有满足的分块
        if(obj==NULL)
            scan_zct()//扫描zct表,清理垃圾
            obj=pickup_chunk(size,$free_list)//再次申请分块,主要是回收垃圾获取的分块
            if(obj==NULL)
                allocation_fail()
            
        obj.ref_cnt=1 
        //mutator不会进行计数更新,只在创建对象时,有个标记1,所以需要zct表扫描。
        return obj
    }
    
    scan_zct(){
        for(r:$roots) //所有活动对象,计数增加;从这看,计数器的宽度问题还在
            (*r).ref_cnt++
        
        for(obj:$zct)//检查zct表,遍历之后,计数仍未0,则该对象真的是垃圾了
            if(obj.ref_cnt==0)
                remove($zct,obj)//回收垃圾
                delete(obj)     
        for(r:$roots) //恢复之前的引用计数
            (*r).ref_cnt--
    }
    delete(obj){
        for(child:children(obj))//将垃圾对象中的子对象的引用减量
            (*child).ref_cnt--
            if((*child).ref_cnt==0)
                delete(*child)
        reclaim(obj)
    }
    

    优点:延迟了根引用的计数,将垃圾一并回收,通过延迟,减轻了因根频繁变化而导致的计数器增减所带来的额外负担。
    缺点:延迟计数器值增减,致使垃圾不能马上回收,并压迫堆,也就失去了引用计数法的一大优点–可即刻回收垃圾;另scan_zct()函数导致最大暂停时间延长。

    Sticky引用计数法:对计数器的改进处理
    其解决的是计数器占用空间过大的问题,比如采用5位的计数器,这会带来计数溢出问题,通过增加对计数器的管理,来解决该问题;此外,之所以可以采用该问题,是因为实际中极高引用数的情况很少,一般引用数不大,甚至大多对象创建,之后就释放了。

    计数器溢出处理:

    1. 什么也不做,溢出就溢出了,也就无法回收该对象,正如之前所说,因为溢出的对象较少,另外,溢出的对象在程序中占有较高地位,成为垃圾的可能性也较低,所以问题也不大…但终究是有问题的。
    2. 使用GC标记-清除算法进行管理,该后援会刷新对象的引用计数,即活动对象仍有引用,垃圾对象引用数为0,这保证可以回收之前引用溢出无法回收的垃圾;并且该后援可以处理循环引用问题,因为遍历根了嘛,不在根下,计数被置0后,没有增长,即是垃圾。但标记-清除算法是要花费更多时间的,所以吞吐量也会相应减少。

    GC标记-清除算法管理引用计数:

    1. 一开始就把所有对象的计数器值设为0
    2. 不标记对象,而是对计数器进行增量操作
    3. 为了对计数器进行增量操作,算法对活动对象进行了布置一次的搜索
    mark_sweep_for_counter_overflow(){
        reset_all_ref_cnt()//将计数清零,方便处理计数溢出的对象
        mark_phase() //更新引用计数
        sweep_phase() //回收垃圾
    }
    mark_phase(){//dfs方式搜索
        for(r:$roots) //所有活动对象入栈,以更新其计数
            push(*r,$mark_stack)
           
        while(is_empty($mark_stack)==FALSE)
            obj=pop($mark_stack)
            obj.ref_cnt++ //更新计数
            if(obj.ref_cnt==1) //每个对象的子对象只遍历一次,就是扫描整个树一次
                for(child: children(obj))//若被引用,还会入栈
                    push(*child,$mark_stack)
    }
    sweep_phase(){
        sweeping = $heap_top
        while(sweeping<$heap_end)//还是通过遍历对象,回收的,费时
            if(sweeping.ref_cnt==0)//回收垃圾
                reclaim(sweeping)
            sweeping+=sweeping.size
    }
    

    1位引用计数法:

    该算法更激进了些,是Sticky引用计数法的特殊情况,其作者认为,大多对象,在创建后,就会立马死亡,所以可以只用1位计数器。
    这里的计数器称为tag更为合理,这里对象只有两种情况:0-一定不是垃圾(UNIQUE),1-可能是垃圾(MULTIPLE)。

    指针通常默认4个字节对齐,所以没法利用低2位,可以利用该性质,就能拿出1位作为计数tag,用作内存管理。为什么指针4b对齐,没法利用低2位?
    经询问本科时的师兄,指针指向的是数据是4B对齐,指针变化都是4倍进行的,所以最低两位,都是0。这里吐槽一下该书!
    这里用这个特性,就要求系统数据必须4B对齐。巧是巧,但就是对系统有要求,反而不好。

    1位引用计数法也是在更新指针的时候进行内存管理的,不过它不像以往那样要引用对象来更新指针,而是通过复制某个指针来更新指针。
    次改进,只需将mutator的update_ptr()更换成copy_str()即可。

    copy_ptr(dest_ptr,src_ptr){
        //原对象丢失一个引用,
        //之前状态unique或者multiple,若是unique则可进行回收
        delete_ptr(dest_ptr)
        *dest_ptr=*src_ptr
        set_multiple_tag(dest_ptr)//此时一定是multiple
        if(tag(src_ptr)==UNIQUE)
            set_multiple_tag(src_ptr)
    }
    delete_ptr(ptr){
        if(tag(ptr)==UNIQUE)//回收
        reclaim(*ptr)
    }
    

    优点:不容易出现告诉缓存缺失,应该是不会像标记-清除算法那样遍历对象,就会造成较多的不在缓存中的对象,从而访问内存,增加时间;对象元数据不需要计数器,所以节省内存空间。
    缺点:跟Sticky引用计数算法基本一样,在1位计数器下,可能出现大量对象计数器溢出的情况,这会给堆带来较大负担,即垃圾压迫堆。

    部分标记-清除算法:引用计数的后援,负责循环引用垃圾的处理

    该算法针对之前的通过标记-清除算法要进行全部搜索的后援,进行了优化,提出一中部分标记-清除算法,将垃圾限定可能产生垃圾的对象集中。
    这里定义了四种颜色,占用2位空间:

    1. 黑:绝对不是垃圾的对象(对象产生时的初始颜色)
    2. 白:绝对是垃圾的对象
    3. 灰:搜索完毕的对象
    4. 阴影(hatch):可能是循环垃圾的对象

    该算法是较为复杂的,可通过如下图示理解,其思想:
    0. 对于循环引用,环节点就在外部引用那个点,即其计数是大于2的,所以通过遍历确定外部引用的节点,已被断开即可。

    1. 确定方法就是颜色标记法,有对象释放,引用减少,其就可能时循环引用的节点,标记为阴影,并不马上确定是否时循环引用垃圾;
    2. 在空闲链表上的分块无法满足时,就会启动该标记-清除算法,扫描所有阴影对象,这里要进行多次扫描,因为颜色要经历几次变化,首先从阴影到灰色,并对子对象的引用数减量;知道所有的阴影对象便会灰色;
    3. 接着,再次遍历hatch_queue,这时都是灰色的,根据其引用数,确定是否是白色,引用数为0,则是垃圾,否则是活动对象,置为黑色。
      注意这里是减量是对其子对象操作的,若是环,则减量操作会作用到最终的起点上,并形成一个环的逻辑,为什么不对该对象本身减量,见bad_paint_gray(obj)。

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    dec_ref_cnt(obj){
        obj.ref_cnt--
        if(obj.ref_cnt==0)
            delete(obj)
        else if(obj.color!=HATCH)
            obj.color=HATCH
            enquere(obj,$hatch_queue)
    }
    new_obj(size){
        obj=pickup_chunk(size)
        if(obj!=NULL)//新创建的对象是黑色的
            obj.color=BLACK
            obj.ref_cnt=1
            return obj
        else if(is_empty($hatch_queue)==FALSE)
            scan_hatch_queue()//分块失败,则要扫描,清理垃圾
            return new_obj(size)
            //递归进行的,扫描一次不行么?应该可以,这里也只需一次递归吧,
            //再次递归,scan_hatch_queue,没有变化啊,该处理的已经处理完了
        else
            allocation_fail()
    }
    scan_hatch_queue(){
        obj=dequeue($hatch_queue)
        if(obj.color==HATCH)//或是嘤嘤的,则要进行判断,是否是循环引用垃圾
            paint_gray(obj)//标记访问过的
            scan_gray(obj)//扫描访问过的,并确定出白色,即垃圾
            collect_white(obj)//回收垃圾
        else if(is_empty($hatch_queue)==FALSE)
            scan_hatch_queue()//递归进行,将hatch_queue处理完
    }
    paint_gray(obj){
        if(obj.color==(BLACK|HATCH))
            obj.color=GRAY
            for(child:children(obj))
            //减量操作在子对象上,这样可以表示循环,a->b,b->a,最后操作在自己本身,可以确定是循环
            //若对自己减量,则无法区别,a->b,b->c 和a->b,b->a
                (*child).ref_cnt--
                paint_gray(*child)
    }
    scan_gray(){
        if(obj.color==GRAY)
            if(obj.ref_cnt>0)//活动的对象,其子对象多是活动的
                paint_black(obj)
            else //循环中的垃圾,回收
                obj.color=WHITE
                for(child:children(obj))//遍历子对象,将垃圾标为白色,活动对象,置黑,待下回扫描
                    scan_gray(*child)
    }
    paint_black(obj){//将活动对象标黑
        obj.color=BLACK
        for(child:children(obj))
            (*child).ref_cnt++
            if((*child).color!=BLACK)
                paint_black(*child)
    }
    collect_white(obj){//对白色对象的子对象进行减量操作,并回收白色对象
        if(obj.color==WHITE)
            obj.color=BLACK
            for(child:children(obj))
                collect_white(*child)
            reclaim(obj)
    }
    
    

    扫描hatch_queue时,为什么对子对象减量,而不是本身,见如下代码
    减量操作在子对象上,这样可以表示循环,a->b,b->a,最后操作在自己本身,可以确定是循环;若对自己减量,则无法区别,a->b,b->c 和a->b,b->a。可见下图的例子。

    bad_paint_gray(obj){
        if(obj.color==(BLACK|HATCH))
            obj.ref_cnt--
            obj.color=GRAY
            for(child:children(obj))
                bad_paint_gray(*child)
    }
    

    在这里插入图片描述
    评价:部分标记-清除算法因为从队列搜索对象所付出的成本太大了,队列中的对象是候选垃圾,所以搜索的对象不在少数;且因为颜色标记,所以需要遍历3次(mark_gray、scan_gray、collect_white),所以这也大大增加内存管理时间,即引用计数法的一大优点,最大暂停时间不复存在了。

    以上内容为读书笔记,参考资料《垃圾回收的算法与实现》。

    展开全文
  • 如何判断对象是否存活引用计数法概念引用计数法就是如果一个对象没有被任何引用指向,则可视之为垃圾。这种方法的缺点就是不能检测到环的存在。首先需要声明,至少主流的Java虚拟机里面都没有选用引用计数算法来管理...

    如何判断对象是否存活

    引用计数法

    概念

    引用计数法就是如果一个对象没有被任何引用指向,则可视之为垃圾。这种方法的缺点就是不能检测到环的存在。

    首先需要声明,至少主流的Java虚拟机里面都没有选用引用计数算法来管理内存。

    什么是引用计数算法:

    给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值加1;

    当引用失效时,计数器值减1.任何时刻计数器值为0的对象就是不可能再被使用的。

    那为什么主流的Java虚拟机里面都没有选用这种算法呢?

    其中最主要的原因是它很难解决对象之间相互循环引用的问题。

    根搜索算法

    概念

    这个算法的基本思想是通过一系列称为“GC Roots”的对象作为起始点,从这些节点向下搜索,搜索所走过的路径称为引用链,当一个对象到GC Roots没有任何引用链(即GC Roots到对象不可达)时,则证明此对象是不可用的。

    那么问题又来了,如何选取GCRoots对象呢?

    在Java语言中,可以作为GCRoots的对象包括下面几种:

    (1). 虚拟机栈(栈帧中的局部变量区,也叫做局部变量表)中引用的对象。

    (2). 方法区中的类静态属性引用的对象。

    (3). 方法区中常量引用的对象。

    (4). 本地方法栈中JNI(Native方法)引用的对象。

    下面给出一个GCRoots的例子,如下图,为GCRoots的引用链。

    106e12cf5cd7a6a6c3964fe36570589e.png

    举例分析,看下面的图:

    bb8b41d0be539587f7bda91fba4d4b48.png

    根搜索算法的基本思路就是通过一系列名为”GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链(Reference Chain),当一个对象到GC Roots没有任何引用链相连时,则证明此对象是不可用的。

    从上图,reference1、reference2、reference3都是GC Roots,可以看出:

    reference1-> 对象实例1;

    reference2-> 对象实例2;

    reference3-> 对象实例4;

    reference3-> 对象实例4 -> 对象实例6;

    可以得出对象实例1、2、4、6都具有GC Roots可达性,也就是存活对象,不能被GC回收的对象。

    而对于对象实例3、5直接虽然连通,但并没有任何一个GC Roots与之相连,这便是GC Roots不可达的对象,这就是GC需要回收的垃圾对象。

    引用计数法 已经被淘汰了!因为循环依赖问题!

    A a = new A()    每个对象有个年龄 大于了一定年龄(15) 存放老年代 否则 新生代

    GC线程不定时进行回收,如果对象被应用的话,年龄就+1,如果没有被继续回收则-1

    如果年龄为0的话,被回收

    循环依赖问题:

    A a = new A()

    B b = new B()

    a.x=b

    b.x=a

    a=null

    b=null

    很难判断 然后 怎么去标记为0  去回收

    根搜索算法  GCRoots 没有和GCRoots  需要和根节点有依赖关系 如果没有和GCRoots有任何引用关系情况,GC认为不可达对象。

    遍历一遍看看 与GCRoots有引用没

    30a0afe5dd97470c3c9a696fad8d59fb.png

    只有 user3和user5 不可达 。

    展开全文
  • 关于引用计数法,我们可以先看一段wiki上的描述:As a collection algorithm, reference counting tracks, for each object, a count of the number of references to it held by other objects. If an object's ...
  • 引用计数法的原理和优缺点

    千次阅读 2021-04-13 15:00:36
    垃圾标记阶段:对象存活判断 堆里存放着几乎所有的Java对象实例,在GC执行垃圾回收之前,首先需要区分出内存中那些是存活对象,哪些是已经死亡的对象。只有被标记为已经死亡的对象...引用计数法(ReferenceCounting).
  • 10 引用计数法

    千次阅读 2020-06-14 23:35:10
    客观的说,引用计数算法的实现简单,判定的效率很高,在大部分的情况下是一个不错的算法. 默认标记次数 = 15次,当标记 = 0,gc直接回收 对象被引用的话,就会 +1,然后放到 s0或者s1区,如果还是被频繁使用,那么...
  • 引用计数法

    千次阅读 2016-12-17 18:55:48
    引用计数法是在mutator(应用程序)的启动过程中通过增减计数器的值来进行内存管理 涉及到new_obj和update_ptr函数 //在mutator生成新的对象的时候会调用new_obj函数 new obj ( size ){ obj = pickup_...
  • 啥是引用计数法 顾名思义,就是当一个对象被引用的时候进行数字计数,当增加一次引用的时候计数+1,当删除一个对象的引用时-1;当一个对象的引用变成0的时候,就可以被回收了 出现的问题 请先看代码: public ...
  • GC内存回收之引用计数法
  • 垃圾回收-- 引用计数法

    千次阅读 2019-06-29 23:35:11
    引用计数法 引用计数法,最重要的就是计数器,记录有多少引用该对象 引用计数法与mutator 的执行密切相关,在mutator 的处理过程中通过增减计数器的值来进行内存管理, 在分配和更新对象时会发生计数的变化 更新操作...
  • GC算法-引用计数法

    2020-04-05 18:37:17
    GC算法-引用计数法 概述 引用计数法又是什么鬼呢? 顾名思义, 对对象的引用进行计数. 通过记录每个对象被引用的次数, 来确定这个对象是否可以被回收. 实现 首先, 对对象的引用数量进行管理, 什么时候会更新呢? 创建...
  • JVM详解-GC-引用计数法

    2020-11-07 19:13:35
    引用计数法 1. GC概述 GC:垃圾回收机制 作用区域: JVM在进行GC时,并不是对堆中的三个区域(新生代、幸存区、老年区)进行统一回收。大部分时候,回收都是在新生代区域。 新生代 幸存区:from 、to 老年...
  • 关于引用计数法的循环引用问题

    千次阅读 2020-03-11 18:02:34
    现在JVM大多不采用引用计数法 进行GC,很大程度上是因为引用计数法不能解决循环引用的问题。 如下代码 public class TestClass { private Object ref; public static void main(String[] args) { TestClass o1...
  • 引用计数法意如了一个概念,那就是“计数器”,计数器表示的是对象的人气指数, 也就是有多少程序引用了这个对象(被引用书),计数器是无符号的整数。 在引用计数法中并没有mutator明确启动GC的语句。引用计数法与...
  • jvm GC引用计数法

    2019-01-07 17:46:07
  • 基本概念在对象中引入计数器(无符号整数),用于记录有多少对象引用了该对象。通过增减计数器实现对内存的管理。分配对象时将计数器置1。更新引用时先对新指定的对象进行计数器加,而后才对旧对象进行减。在对计数器...
  • 垃圾回收算法--引用计数法1
  • GC_3_引用计数法

    千次阅读 2017-04-03 10:28:55
    3 引用计数法   GC是一种,释放怎么都无法被引用的对象的机制。可以让所有对象事先记录下有多少程序引用自己,让各对象知道自己的人气指数,从而让没有人气的对象自己消失,这就是引用计数法(Reference Counting...
  • 当存在循环引用时,引用计数器失效,如下面代码所示: public class CircleReference { public Object instance = null; public static void main(String[] args) { CircleReference a = new CircleReference...
  • 引用计数法 引用计数法优缺点 引用计数法的简单缺点实例 可达性分析法 可以作为GCRoot的对象
  • 网抑云二面面经 ...Java GC中使用引用计数法所存在的缺点 首先是Javaer人尽皆知的循环依赖,然后呢? 说实话,面试时因为【突如其来的没有自我介绍就直入主题 和 跳表刚讲了一句就被示意下一题】这种
  • 1.引用计数法 引用计数法是历史最悠久的一种算法,最早George E.Collins 在1960的时候首次提出,50年后的今天,该算法依然被很多编程语言使用。 1.1原理 假设有一个对象A,任何一个对象对A的引用,那么对象A的...
  • 垃圾回收的五种算法——引用计数法 1.引用计数法 1.1简介 引用计数是计算机编程语言中的一种内存管理技术,是指将资源(可以是对象、 内存或磁盘空间等等)的被引用次数保存起来,当被引用次数变为零时就将其 ...
  • 引用计数法(Reference Counting) 由1960年GeorgeE.Collins提出。引用计数法为每个对象引入技术器,当对象被引用(被其他对象指向)时技术器+1,当技术器为0时表示对象不可达则被视为垃圾处理。优点:与不同标记-...
  • 实现思路:给对象添加一个引用计数器。每当有一个地方引用它时,...A引用B,B引用A——循环引用(引用计数算法)由于A、B彼此引用对方,导致引用计数都不为0,所以GC无法回收它们 1 public class MyObject {...
  •  但是,在主流的JVM中没有选用引用计数法来管理内存,最主要的原因就是引用计数法无法解决对象的循环引用问题。 /** * JVM运行参数: -XX:+PrintGC 打印GC日志 * @author xucc */ public class ...
  • JVM中的堆和方法区主要用来存放对象(方法区中也储存了一些静态变量和全局变量等信息),那么我们要使用GC算法对其进行回收时首先要考虑的就是该对象是否应该被回收。... 引用计数法在对象头处维护一个cou...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,724
精华内容 28,289
关键字:

引用计数法

友情链接: 材料分拣.zip