标记-清除算法

GC 算法，可以称之为内存回收算法，是将程序不用的内存空间回收以便与重复利用。可以简单分为两个步骤：找垃圾和回收垃圾

第一章 GC的简单介绍

GC 的作用

防止内存泄漏，不使用的内存空间自动释放，无需手动释放，无需进行手动内存管理。

GC的历史

John McCarthy，1960， 标记-清除算法

1960，引用计数算法

1963，GC复制算法

目前的GC算法只是这三种的排列组合应用

第二章 GC的基本概念

mutator

mutator 实际进行两个操作：

1. 生成对象
2. 更新指针

堆

堆用于动态（执行程序时）存放对象的内存空间，当mutator 申请存放空间时，所需的空间就是从堆中被分配到 mutator

分配

分配是指在内存空间中分配对象。当mutator需要新对象时，就会向分配器（allocator）申请一个合适大小的空间。分配器会从堆的可用空间中寻找合适的空间，返回给mutator

GC Root

全局变量空间、调用栈、寄存器 （每一种语言都不相同）

分块 chunk

初始状态下，堆是一个完整的大块，后面会根据需求的大小，逐渐分为一个个小块，作为活动对象使用。不使用的小块，构成一个空闲链表

评价GC优劣的标注

1. 吞吐量： 单位时间内的处理能力
2. 最大暂停时间： GC执行过程中暂停 mutator 的最长时间
3. 堆的利用效率：
4. 访问的局部性：考虑访问的局部性，将具有引用关系的对象安排在堆中较近的位置，提高缓存的命中率

GC 算法

第三章 GC 标记-清除算法 Mark Sweep GC

算法分为两阶段

mark-sweep-gc(){
  // mark phase
  // 标记阶段
  mark-phase()
  // 清除阶段
  // sweep phase
  sweep-phase()
}

标记阶段

标记阶段是把所有活动对象都做上标记（如 flags位置1）

mark(obj){
  if(obj.mark == False){
     obj.mark = True;
     for(child: obj){
       mark(*child);
     }
  }
}

从GC ROOT 出发，标记所有的活动对象

mark_phase(){
  for(r: $root){
     mark(*r)
  }
}

清除阶段

清除阶段，收集器（collector）会遍历整个堆，将所有未被标记的对象（非活动对象）清除回收。

sweep_phase(){
  sweeping = $sweep_start
  while(sweeping < $sweep_end){
      if(sweeping.mark = True){
          sweeping.mark = False
      }else{
          sweeping.next = $free_list
          $free_list = sweeping
      }
  sweeping += sweeping.size
}

堆是分为一个个小块的，sweeping 可以看作是一个个小块的引用

执行标记和清除之后，后面还有两个操作：分配和合并

分配是指从空闲链表中找到一个合适的块，将其分配给新的对象。

这跟操作系统一章中的内存管理非常相近，可以参考学习, best fit、first fit、 worst fit

合并是指将空闲链表中首尾相连的多个块合并成一个的过程，这个过程通常在清除阶段执行

优缺点

优点	缺点
实现简单	碎片化
可以与保守式GC算法兼容	分配速度慢
	与copy-on-write 不兼容

如何避免碎片化？

copy-on-write 是啥？

如何快速的找到合适的空闲块？