内存管理器（二十三）标记-复制式回收算法

今天药忘吃喽~ 2022-07-19 01:54 196阅读 0赞

标记-复制式回收算法
    
    GC 机制在一个系统中占重要地位，但是在使用过程中占用整体时间的最小部分，赋值器的执行开销产生的影响反而切实的影响这整个系统的性能。
    
    半区复制回收
    
    基本复制回收器会将堆划分为两个大小相等的半区，分别设置为来源空间，目标空间。

/*半区复制回收算法*/ /*初始化以及分配*/ createSemispases(): topspace = heapstart; /*堆开始的位置*/ extent = (heapend - heapstart)/2; /*半区大小*/ top = fromspaces = heapstart + extent; /*半区开始位置*/ free = topspace; /*空想开始位置*/ atmoic allocate(size): /*分配空间*/ result = free; newfree = result + size; if (newfree > top){ return null; } free = newfree; return result;

这个思想简要来说：就是把一个堆空间分成两个部分，一个为使目标区，就是已经被使用的，一个是回收区，就是要回收使用的区，当一个区域需要回收的时候则将目标区域中的内容复制进回收区。这个算法最明显的一个问题就是整个区域只有一半可以使用。 回收过程：在回收初始化完成后，半区复制回收器，首先将根对象复制到目标空间，并填充工作列表。然后逐步扫描复制相关内容。

atomic collect():              /*分配内存*/
         flip();                   /*设置工作半区*/
         init(worklist);           /*初始化分配列表*/
         for each fld in roots     /*复制根*/
               process(fld);
         while not isEmpty(worklist)    /*复制传递闭包关系*/
               ref = remove(worklist);
               scan(ref);
    
    flip():                             /*翻转半区*/
         fromspace,tospace = topspace,fromspace;
         top = topspace + extent;
         free = topspace;
    
    scan(ref):
         for each fld in pointers(ref);
               process(fld);
    
    process(fld):                    /*使用目标中新副本来更新域*/
          fromref = *fld;
          if(fromref  != NULL)
               *fld = forward(fromref); /*使用目标空间中新地址来更新*/
    
    forward(fromref):
          toRef = forwardingAddress(fromRef);
          if (toRef == NULL)                      /* 没有复制*/
              toref = copy(fromRef);
          return toRef;
    
    copy(fromRef):                                /*复制对象，返回转发地址*/
          toRef = free;
          free = free + size(fromRef);
          move(fromRef,toRef);
          forwardingAddress(fromRef) = toRef;
          add(worklist,toRef);
          return toRef;

这个算法的核心是工作列表的实现与遍历循环的方式。 这里Cheney 在1970年提出了Cheney 扫描，该算法利用目标空间中灰色对象实现先进先出队列。

initi(worklist):  /*初始化工作列表*/
        scan = free;
    
    isEmpty(worklist):    /*判堆是否完成分配*/
        return scan = free;
    
    remove(worklist):    /*移动scan指针*/
        ref = scan;
        scan += size(scan);
        return ref;
    
    add(worklist,ref):   /*添加在这事实是没有什么用*/

算法思想如下图：   就是如此复制。