内存管理器（二十二）标记-整理回收算法

小鱼儿 2022-07-18 20:57 167阅读 0赞

我们今天来看看第二种垃圾回收方法：
    
    标记-整理回收算法

双指针整理算法

使用两个指针，一个从前向后遍历，我们称之为free指针，接着使用另一个指针，我们称之为scan指针，他从后像前遍历，当free 遇到空闲且大小合适的内存块时，将scan 所指向的内存拷贝到free 中,当free  和 sacn 指针相遇或者产生交互，我们就完成了这一次的标记-整理回收工作。 至于这个两个指针的交互地点，是回收器预预先计算出该区域整理完成后存活对象的“高水位”标记。 伪代码：

compact():                                /*内存压缩*/
        relocate(headpstart,heapend);         /*压缩*/
        undatereference(heapstart,free);      /*更新指向*/
    
    relocate(start,end)
        free = start;
        scan = end;
        while(free < scan)                    /*寻找下一个空洞*/
              while(ismarked(free))
                 unsetmarked(free);
                 free +=  sizeof(free);
              while (!ismarked(scan) && scan > free)   /*寻找前一个存活对象*/
                 scan -=  sizeof(scan);
              if(scan > free){                          /*移动对象*/
                    unsertmarked(free);
                    move(scan,free);
                    free += sizeof(free);
                    scan -= sizeof(scan);
    
    updatereferences(start,end):                 /*修改引用*/
          for each fld in roots
               ref = *fld;
               if(ref >= end)
                   *fld = *ref
          scan = start;
          while(scan < end){                     /*修改存活对象*/
               for each fld in Pointers(scan)
                     ref = *fld
                     if(ref >= end)
                          *fld = *ref
               scan = scan + sizeof(scan)

此算法吞吐量较低，因为大多数对象总是成簇诞生,成簇死亡的。所以这个算法效果良好。

lisp 2 整理算法

从名字就可以感受到这是一种历史悠久的算法了，思想就是标记-整理算法。不过他更加的原始,更加的简单，因为这个算法诞生的时候还没有高速缓存，分页管理，所以这个算法在硬件上的优化并不是那么近乎人意的。下来直接上伪代码，至于模拟代码，我会在基础四个算法学习完成后统一进行编写。

compact :
         compactlocation(heapstart,heapend,heapstart);
         updatereference(headpstart,heapstart);
         relocate(heapstart,heapend);
    
    comactlocation(start,end,tobegin):
         
         scan = start;
         free = tobegin;
         while(scan < end)
              if(ismarked(scan))
                   forwardingaddress(scan) = free;
                   free += sizeof(scan);
              scan += sizeof(scan);
    
    updatereference(start,end):
         for each fld in roots
             ref = *fld;
             if(ref != NULL)
                 *fld = forwardingaddress(ref);
         scan = start;
         while(scan < end)
             if(ismarked(scan))
                for each fld in pointers(scan)
                      if(*fld != NULL)
                            *fld = forwardingaddress(*fld);
             scan += sizeof(scan);
    
    relocate(start,end):
        scan = start;
        while(scan < end)
             if(isMarked(scan))
                 dest = forwardingaddress(scan);
                 move(scan,dest);
                 unsetmarked(dest);
             scan += sizeof(scan);

这个算法总共需要遍历三次堆空间。 @在标记阶段结束后，回收器会计算出每个存活对象的最终地址，并且保存。 @回收器更新引用 @最后一次，移动对象

引线整理算法：

这个思想更简单，将所有对象和引用的共享内存以类似“双向链表”的形式串连起来。进行三次遍历。 @建立后向引用 @建立前向引用 @复制对象到新地址 最后一种标记-整理算法

单次遍历算法

这个算法有很多衍生的版本，我们来讨论Abuaiadh \[2004\] 的哪个版本，这是一个基于并行式，万物静止的算法。 这个算法虽然只遍历一次，但是却产生较大的空间占用量。 首先，他需要算个向量。 \#标记向量 \#偏移向量 \#整理之后的向量 这个算法通过一次遍历，同时构建偏移向量，然后选定新的位置，并且复制数据到新的位置。 小结： 我们来说说各算法的缺陷吧 双指针算法：只能处理大小统一内存 引线算法：破坏指针，不可并发