第一章 简介

内存分配3种方式

静态分配：

局限 每个数据结构的大小必须在编译时可知 过程不能递归，因为对于过程的每个活动(过程体的一次执行)，局部名字在内存中共享相同位置(这时一般用的是栈分配) 无法动态创建数据结构 优点 效率高，不需要在程序执行时创建和销毁栈帧 编译器知道所有数据的内存位置，可直接访问存储位置 内存需求预知，不会发生OOM

栈分配：

特点 可递归调用 栈分配的局部值，无法从过程体的一次执行保存到过程体的下一次执行(这时一般用的是静态分配) 被调用者的生命周期<=它的调用者 只有大小能在编译时确定的对象，才能作为过程的结果返回

堆分配

动态大小的对象可作为过程结果返回 数据结构大小不固定 允许把一个过程作为另一个过程的结果返回

显式堆分配

即分配和释放堆对象交由程序员 会出现以下的问题

假设有这样的链表mList=[head|next]->[1|next]->[2|/]

垃圾

创建链表后加上 head.next=null 造成内存泄漏

mList=[head|/]     [1|next]->[2|/]`

导致只有链表第一个元素可以访问，2 3项不能访问和使用 自动内存管理就是为了解决恢复不可访问的内存

悬挂引用

假设dispose(Object o)方法为释放o的内存 创建链表后加上 dispose(head.next) 造成内存泄漏

mList=[head|next]-> [...]---> [2|/]`

导致第一项next域指向一个被释放的内存，第三项变成了垃圾 注意与上文“垃圾”的区别，上面是让head.next为null,next已经停止指向堆内存地址，这边的next仍然指向一个堆内存地址 那么程序在运行时如果不小心引用了释放对象，程序会出错

共享

销毁最后一个(可能出现多个对该对象的引用)对释放对象(最后未释放变成垃圾)的引用 将造成垃圾 仍然有引用指向对象时就释放对象 将造成悬挂引用 这时有个解决办法是让这两个动作同时发生

mList=[head|next]->[1|next]->[2|/]
倘若要回收[1|next]，[2|/]
应该递归的调用这两种动作(销毁最后一个引用和释放目标对象)同时发生
最后的执行效果是：dispose(2),1.next=null,dispose(1),head.next=null

对于单向引用这样是可以的 然而当出现如下情况

[head1|next]->[ 1 |next]->[2|next]
                ↑
[head2|next]____↑
//head1和head2的next都指向了1

现在要回收[1|next]，[2|next] 以刚刚的解决方法，最后将是剩下一个元素和一个悬挂引用( 例如：[head1|next] [head2|next]->

失败

内存泄漏在测试或正常使用时可能处于潜伏状态，一般只有长时间运行才会发现 失败难以重现

为什么需要垃圾收集

创建过程介绍后可能存活，被传递给更多的过程和函数，程序员和编译器无法确定何时安全释放他们

数据对象出栈时是否应该释放？

静态分配一般答案为否 若没有其他对该对象的引用(栈为最后一个引用)，答案为是 若这些数据被压入其他栈，答案为也许。

这使得栈的接口复杂化，降低适用性

显示内存管理会破坏软件工程的原则

垃圾收集的开销

上面讲诉了为什么要进行垃圾收集，其实，如今垃圾收集的开销已经是大大减小了。 本文主要在于研究各种GC算法

GC算法比较

难以分析复杂度，故主要考虑以下几点

1.安全性：存活数据不能被错误回收 2.全面性：不能出现无法回收的“垃圾”。如引用计数法的垃圾若出现环形则无法回收 3.回收时间：渐进式收集器在完成GC时不会挂起用户程序，短暂的中断可能是必要的。支持实时响应，对任意时间段GC耗费时间所占比加以限制，确保用户程序良好的交互性。 4.空间管理：在堆中分配新数据的开销不亚于GC花费的时间。与 缩并的堆相比，破碎堆分配内存开销更大 5.额外开销：

引用计数每次创建和销毁指针都要更新该单元的引用计数。 渐进式和分代式执行堆的部分收集，渐进式通常保证在一个回收周期中回收该周期开始前产生的垃圾；分代式只收集堆的一个分代(详情见后文)。 所谓额外开销即，渐进式要求用户程序报告它在收集器运行时对堆数据图连通性所做的改变，而分代式则要求若某个分代(通常为老分代)的单元保存了指向另一个分代的单元的引用，那么用户程序要保存一份记录 辅助数据结构：为保证缩并拷贝到新内存空间，节点复制式需要2倍于非搬迁式的地址空间

6.通用性：不同语言是否适用，不同体系架构编译器是否适用该算法

许多因素是对立的：

交互式程序注重更短的中断时间， 非交互式注重总体运行时间， 实时应用要求中断时间和任意时间端收集器占用比例都不得超过一个上限， 运行在虚存机制的工作站程序，良好的换页是个重要因素 PC则要求更低的内存开销

下面我们开始介绍经典算法

---

第二章 经典算法

本章讨论的只是经典算法，改进将在后面章节提到

引用计数

手段：每个单元计算指向它的引用的数量 特点：

天生渐进式，内存管理的开销分布到整个程序之中 每个单元都有一个引用域用于存放计数值，可简单判断单元是否正在使用->自由单元的引用计数值为0

应用：Adobe Photoshop、OS判断一个文件是否可删除(被其他程序引用)、早期程序语言

算法略解：

所有单元被放入一个自由单元池，用RC(R)记录R的被引用值 RC(自由单元)=0，RC(新分配单元)=1，删除指向单元的引用RC--,否则++ 当单元RC降至0，说明程序不再需要该单元，将它放入自由单元列表free_list

算法详解： 为了简化讨论，此刻我们假定所有单元有着固定大小 下面介绍的数据结构为另外开辟，需要占用一个的内存空间 假设每个单元结构都为

struct T{
    int refValue;//引用值计数大小 即RC(T)<==>T.refValue
    T left;
    T right;
}

实际中每个T结构的T引用是不固定的 free_list：自由单元列表(类似指针链表的用法) Children(T)：T单元中有引用其他单元的槽列表,如：[T.left,T.right]

//分配空间
allocate(){
    newcell=free_list; //弹出自由单元列表的第一个元素
    free_list=free_list.next;
    return newcell;
}
//从自由链表取出一个新单元，RC置为1
new(){
    if(free_list==null)abort "内存耗尽";//结束操作
    newcell = allocate() ;
    RC(newcell) = 1;
    return newcell;
}
//下面更新默认修改引用指的是left的引用修改，即*U <=> *(U.left) 更复杂的例子见后面
//单元N归还到自由链表,N放在表头减少检索操作
free(N){
    N.next = free_list;
    free_list = N;
}
//删除对单元T的一次引用
delete(T){
    RC(T) --;
    if(RC(T)==0){
        //说明没有其他单元引用T,此时可以释放资源，在此之前还得递归删除T对其他单元的引用
        for U in Children(T)
            delete(*U);
        free(T);
    }
}
//将单元R引用的地址改为S
Update(R,S){
    if(S==null){
        //如果S为null，即删除R的引用
        
    }
    RC(S)++;
    delete(*R);//*R为原来的引用单元
    *R=S;//更新R的引用单元为S
}

例子：

此时执行Update(R.right,nil), 由于这是指向S的唯一指针，所以S出发的每个指针递归调用delete过程，然后把S加入自由链表 过程1：

过程2：

最后：

引用计数法的优缺点

优点：

1.由于内存管理的开销分布在整个计算过程之中，与基于追踪的收集器相比，有更加平滑的响应时间 注意我们上面的简单算法在分布处理开销存在起伏：删除最后一个引用的代价依赖于子图大小，下一章将改进这个问题。 2.当某单元引用计数为0时，系统无需访问位于堆中其他页面的单元就能回收它。基于追踪的算法需要在回收废弃单元之前遍历所有存活单元 注意还可能访问该单元的后代，下一章将讨论该问题 3.[了解，未深入]标准的引用计数法允许"短命"单元以一种类似栈分配的方式在刚丢弃时就立刻回收重用，而基于追踪的算法，废弃单元会保持未分配状态直到整个堆耗尽。与简单的追踪式算法总是从堆中申请fresh单元的方式相比，立刻重用单元会产生更少的缺页error和良好的cache行为。

缺点：

1.开销大。基于追踪的机制下，更新指针没有任何内存管理开销 2.维护难。若用户程序耦合较高，引用计数系统必须谨慎维护计数，一处遗漏将带来严重后果。[这边举例的不是编译器，而是类似photoShop的用户程序] 3.额外的空间来存放引用计数值，[下一章将改进这个问题] 4.环形数据结构无法回收[可采用与追踪式结合或其他方式，下一章将讨论]

标记-清扫算法

算法简述 内存单元在变成垃圾时不会马上被回收，而是保持不可达到，直到内存耗尽。 如果此时有新单元的请求，系统暂时挂起，并调用垃圾回收，将不可达到的单元清扫回自由单元池 算法详解：

//从自由单元池获取一个新单元
new(){
    if(free_list.isEmpty()){
        mark_sweep();//进行标记清扫
    }
    newcell = allocate();//同上一个算法
    return newcell;
}
//标记清扫分为标记/清扫
mark_sweep(){
    //从每个根节点出发开始向下标记
    for R in Roots
        mark(R);
    sweep();//清扫
    //如果空间还是不够
    if(free_pool.isEmpty())
        abort "内存耗尽"
}
//每个单元需要保留一个二进制让垃圾收集器使用，记录能否从根出发到该单元
//其实就是广搜，这里我们用简单的递归标记算法
mark(N){
    if(N.mark_bit == unmarked){
        N.mark_bit = marked;
        for M in Children(N)
            mark(*M);
    }
}

如图 这样我们可以安全的将未被标记的单元归还给自由单元池，这个清扫的工作，如下：

//对堆的eager(急切) sweep
sweep(){
    //从堆的底部出发，线性的清扫整个堆
    N = Heap_bottom;
    while(N<Heap_top){
        if(N.mark_bit==unmarked){
            free(N);//释放空间，实现可参考引用计数法
        }else{
            //说明单元存活，清除它的标记位，为下一次GC做准备
            N.mark_bit=unmarked;
        }
        N+=size(N);//堆地址向上移动
    }
}

优势和弱点(相比引用计数法)

优点

1.可处理环形结构 2.操作指针没有额外开销

弱点

1.是一种**“停止-启动”**算法，造成中断的可能是巨大的，不适合实时系统。 **注意：**一个解决办法是在关键的时间段禁止垃圾收集。后面章节会提到 **注意2：**如果响应时间不是重要因素，该算法能够提供比引用计数法更好的性能。 2.会造成内存空间更破碎，导致cache容易失效。

节点复制算法

算法简介 将整个堆分为两个半区，一个包含现有数据，一个包含已被废弃的数据； 垃圾收集从切换两个半区的角色开始： 1.收集器到老半区(FormSpace)遍历存活的数据结构,在第一次访问单元时把它负责到新半区(ToSpace); 2.FormSpace所有存活单位都访问过后，垃圾收集器在ToSpace建立了一个存活数据结构的副本，这些结构缩并的排列在ToSpace的底部，用户程序可以开始重新运行了。

算法详解

//初始分区
init(){
    //举例;Head_bottom =100 Head_size=200
    ToSpace = Head_bottom; //100
    space_size = Head_size/2; //100
    topOfSpace = ToSpace + space_size - 1; //199 [100-199]
    FromSpace = topOfSpace + 1; //200 [200-299] 
    free = ToSpace; //100 自由空间开始处的指针
}
//该算法能处理可变大小的对象，n为对象的大小
New(n){
    if(free + n > topOfSpace){
        //自由空间不足，执行交换Space压缩空间
        flip();
    }
    if(free + n > topOfSpace){
        //交换Space和压缩空间还是空间不足
        abort "内存耗尽"
    }
    newcell = free; //新单元从自由空间头指针开始分配 即allocate()
    free+=n;
    return newcell;
}
//交换ToSpace和FromSpace的角色
flip(){
    //重置ToSpace,FromSpace,topOfSpace
    //      100     200       199
    swap(FromSpace,ToSpace);//ToSpace = 200,FromSpace = 100
    topOfSpace = ToSpace + space_size - 1; //299
    free = ToSpace; //200
    //复制可到达单元到ToSpace
    for R in Roots
        R = copy(R);//返回的新R是ToSpace的地址
}
//复制数据结构必须小心保持共享结构的拓扑，否则会出现多个复本，其影响：
//可能只是增大空间占用，可能引发错误(更新其中一个复本，却读取另一个复本)，可能出现环形数据结构占用巨大空间

//复制节点时，FromSpace中的对象会保留一个迁移地址来保持共享，迁移地址为ToSpace中复本的地址
//每当FromSpace中的单元被访问，Copy过程会检查该单元是否被复制
//若是，则返回迁移地址，否则在ToSpace保留空间以备复制

//假设单元P保存迁移地址的域为P[0]
//该函数传入的参数P不是一整个单元，只是单元的一个域/(字)
copy(P){ 
    if(P没有指向其他单元了 || P == null) return P;
    if(P没有迁移地址){
        n=size(P);
        P_NEW = free; //在ToSpace中保留空间
        free += n;
        temp = P[0];//原文有这句，感觉没用
        P[0] = P_NEW ;//设置迁移地址
        P_NEW [0] = copy(temp);//原文有这句，感觉没用
        //复制P的其他域到P_NEW 
        for i = 1 to n-1;
            P_NEW [i] = copy(p[i]);
    }
    return P[0];
}

例子：

A没有迁移地址
n=size(A);//3个域
A_NEW = free //200
temp=A[0];//null
A[0]=A_NEW;//200
A_NEW [0] = copy(temp);//null
    A_NEW [1]=copy(A[1]);//更新A的left域 下图
    A_NEW [2]=copy(A[2]);//更新A的right域 下下图

A_NEW [1]=copy(A[1]);/A[1]指向的是B,进入新的copy
    B没有迁移地址
    n=size(B);//2个域
    B_NEW = free; //203
    temp=B[0];//null
    B[0]=B_NEW;//203
    B_NEW [0] = copy(temp);//null
        B_NEW[1]=copy(B[1]);//B[1]没有指向其他单元，直接返回. B_NEW[1]=B[1]
A_NEW [1]=B_NEW;//最后返回,A_NEW[1]指向B_NEW

A_NEW [2]=copy(A[2]);//A[2]指向的是C
    C没有迁移地址
    n=size(C);//3个域
    C_NEW = free;//205
    temp=C[0];//null
    C[0]=C_NEW;//205
    C_NEW [0] = copy(temp);//null
        C_NEW[1]=copy(C[1]);//C[1]指向的D,copy(D)的最后返回D_NEW,即C_NEW[1]=D_NEW;
        C_NEW[2]=copy(C[2]);//C[2]指向A,A存在迁移地址，直接返回，即C_NEW[2]=A_NEW;

节点复制算法的优缺点

优点：

极大降低内存分配的开销： 检查空间是否耗尽只要做简单指针比较; 获取新内存可简单通过递增自由空间实现; 内存碎片问题不再出现

缺点：

使用了2个半区，空间代价是2倍，可能出现更多的缺页错误

比较标记-清扫和节点复制

节点复制收集器，划分2个半区。随程序内存占用率的升高，收集器的性能会不断下降，这是因为每次收集回收的自由内存越来越少。比标记-清扫性能下降更快。

节点复制收集器的渐进复杂度比标记-清扫要小，其正比于存活数据结构的大小，非整个半区的大小。

比较两者的渐进复杂度

堆的容量：M , 存活数据占用的内存大小： R

时间复杂度 节点复制收集器必须追踪并更新根集合和存活数据结构的每个指针，搬迁到ToSpace,故执行一次GC的时间复杂度 t(节点复制)=aR 标记-清扫追踪指向存活数据结构的指针，并在清扫阶段线性清扫整个堆 t(标记-清扫)=bR+cM

每次GC恢复的内存数量 m(复制节点)=M/2-R m(标记清扫)=M-R

算法效率e为单位时间内回收的内存数量 e(节点复制)=1/(2ar)-1/a e(标记清扫)=(1-r)/(br+c) 其中r=R/M,表示程序的内存占用率

---

第三章 引用计数

本章 将对上一章简单引用计数算法进行改进