算法

本文是《垃圾回收的算法与实现》读书笔记 上一篇为《GC 标记-清除算法》 引用计数算法 给对象中添加一个引用计数器，每当有一个地方引用它时，计数器的值就加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() 函数 ...

本文是《垃圾回收的算法与实现》读书笔记 什么是GC标记-清除算法（Mark Sweep GC） GC 标记-清除算法由标记阶段和清除阶段构成。在标记阶段会把所有的活动对象都做上标记，然后在清除阶段会把没有标记的对象，也就是非活动对象回收。 名词解释： 在 GC 的世界里对象指的是通过应用程序利用的数据的集合。是 GC 的基本单位。一般由头（header）和域（field）构成。 活动对象:能通过引用程序引用的对象就被称为活动对象。（可以直接或间接从全局变量空间中引出的对象） 非活动对象:不能通过程序引用的对象呗称为非活动对象。（这就是被清除的目标） 标记-清除算法的伪代码如下所示： func mark_sweep(){ mark_phase() // 标记阶段 sweep_phase() // 清除阶段 } 标记阶段 标记阶段就是遍历对象并标记的处理过程。 标记阶段伪代码如下： func mark_phase(){ for (r : $roots) // 在标记阶段，会给所有的活动对象打上标记 mark(*r) } func mark(){ if (obj.mark == False) obj.mark = True // 先标记找出的活动对象 for (child: children(obj)) // 然后递归的标记通过指针数组能访问到的对象 mark(*child) } 这里 $root 是指针对象的起点，通过$root 可以遍历全部活动对象。 下图是标记前和标记后内存中堆的状态 清除阶段 在清除阶段，collector 会遍历整个堆，回收没有打上标记的对象（垃圾），使其能再次利用。 sweep_phase() 函数伪代码实现如下： func sweep_phase(){ sweeping = $heap_start // 首先将堆的首地址赋值给 sweeping while(sweeping < $head_end){ if(sweeping.mark == TRUE) // 如果是标记状态就设为 FALSE，如果是活动对象，还会在标记阶段被标记为 TRUE sweeping.mark == FALSE else: sweeping.next = $free_list // 将非活动对象 拼接到 $free_list 头部位置 $free_list = sweeping sweeping += sweeping.size } } size 域指的是存储对象大小的域，在对象头中事先定义。 ...