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( $ptr,obj)改为*$ ptr=obj,也就是计数更新只在创建对象时。
延迟引用计数法，引入一个ZCT(Zero Count Table)表，会事先记录下计数器值在dec_ref_cnt()函数的作用下变为0的对象。之后会扫描该表，更新计数，更新方法同标记-引用算法，从根开始递归扫描。
GC-引用计数法

计数器值为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位的计数器，这会带来计数溢出问题，通过增加对计数器的管理，来解决该问题；此外，之所以可以采用该问题，是因为实际中极高引用数的情况很少，一般引用数不大，甚至大多对象创建，之后就释放了。

计数器溢出处理：

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

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

一开始就把所有对象的计数器值设为0
不标记对象，而是对计数器进行增量操作
为了对计数器进行增量操作，算法对活动对象进行了布置一次的搜索

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位空间：

黑：绝对不是垃圾的对象（对象产生时的初始颜色）
白：绝对是垃圾的对象
灰：搜索完毕的对象
阴影（hatch):可能是循环垃圾的对象

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

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

GC-引用计数法

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)
}

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

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

GC-引用计数法

GC-引用计数法

相关推荐