清扫式垃圾回收器复原标记

7.5垃圾回收垃圾：不能被引用的数据垃圾回收的机制：手动垃圾回收程序员完成自动垃圾回收自动回收不行达数据的机制优点：解除了程序员的负担最早出现在LISP语言中其他例子：Java、Perl、ML、Modula-3、Prolog、Smalltalk垃圾回收器的设计目标基本要求：语言必需是类型平安的。回收器能够知道数据元素是否是一个指向某个内存块的指针。类型担忧全的语言：C，C++.性能目标总体运行时间：不能显著增加应用程序的总运行时间；空间运用：最大限度地利用可用内存；停突然间：当垃圾回收机制启动时，可能引起应用程序的停顿。这个停顿应当比较短；程序局部性：改善空间局部性和时间局部性。可达性（Reachability）可达性指一个存储块可被程序访问根集(rootset)先验可达数据不须要对任何指针解引用(dereference)就可以干脆访问的数据。例：Java的根集由全部静态字段成员和栈中全部变量变量组成；可达数据（具有可达性的对象）根集＋任何可达数据引用的对象一旦一个对象变得不行达，它就不会再变成可达的。变更可达对象集合的操作对象支配返回一个指向新存储块的引用；参数传递/返回值对象引用从实在参数传递到形式参数，从返回值传递给调用者；引用赋值：u=vv的引用被复制到u中，u中原来的引用丢失可能使u原来指向的对象变得不行达，并且递归地使得更多对象不行达。过程返回活动记录出栈，根集变小；可能使得一些对象变得不行达垃圾回收方法找寻不行达对象基本方法捕获对象变得不行达的时刻周期性地定位全部的可达对象，推断其它对象为不行达的两类垃圾回收方法引用计数法近似实现第一种方法跟踪那些变更可达对象集合的操作，维护指向各个对象的引用计数当计数变为0时，对象变为不行达基于跟踪的方法跟踪全部的引用，从而计算可达性7.5.3引用计数垃圾回收器每个对象设一个引用计数表示指向该对象的引用个数当对象没有内部循环引用时有效维护引用计数的方式对象支配：引用计数设为1参数传递：引用计数加1引用赋值：u=v：u指向的对象引用减1、v指向的对象引用加1过程返回：局部变量指向对象的引用计数减1当对象引用计数变为为0时，该对象成为垃圾，其空间变为可用多米诺效应：该对象各个指针指向的对象的引用计数减1缺点：可能引起内存泄漏开销较大优点：不会引起停顿引用计数计算的实例循环垃圾的例子此时运用引用计数无效7.6基于跟踪的垃圾回收基于跟踪的回收器并不在垃圾产生时进行回收，而是会周期性地运行，找寻不行达对象并回收它们的空间常在空间耗尽或空闲空间低于某个阈值时启动垃圾回收器7.6基于跟踪的垃圾回收基本的标记-清扫式垃圾回收标记-清扫式垃圾回收的优化标记并压缩垃圾回收拷贝垃圾回收7.6.1基本的标记-清扫式垃圾回收一种干脆的全面停顿的算法分成两个阶段标记：从根集起先，跟踪并标记全部可达对象；清扫：遍历整个堆区，并释放不行达对象；若把数据对象看作顶点，引用看作有向边，标记过程事实上是从根集起先的图遍历过程。标记-清扫垃圾回收算法P287图7-21一个标记－清扫式垃圾回收器复原标记存储块状态每个存储块处于四种状态之一空闲（Free)没有对象，可用于支配未被访问的(Unreached)有一个对象，但目前从根集还不能到达待扫描(Unscanned)从根集可达，但其引用还未跟踪已扫描(Scanned)从根集可达，且其引用已跟踪不可达基本抽象分类对存储块的操作会变更存储块的状态应用程序支配垃圾回收器访问、扫描收回图7-23在一个垃圾回收循环中的存储块状态优化的标记-清扫垃圾回收算法(Baker算法）基本算法需扫描整个堆优化：只扫描已支配对象运用一个已支配对象列表不行达对象等于已支配对象减去可达对象好处扫描范围缩小整个堆－>已支配对象列表坏处需维护已支配对象列表Baker的标记－清扫算法运用了四个列表：Scanned,Unscanned,Unreached,Free;7.6.4标记—压缩垃圾回收p290对可达对象进行重新定位可以消退存储碎片；可以把可达对象移动到堆区的一端，空闲空间合并成单一的块。整个过程分成三个步骤标记计算新位置移动并设置新的引用标记—压缩垃圾回收图7-26标记—压缩垃圾回收图7-26（续）标记—压缩垃圾回收图7-27标记－压缩详例拷贝回收器堆空间被分为两个半空间；应用程序在某个半空间内支配存储，当充溢这个半空间时，起先垃圾回收回收时，可达对象被拷贝到另一个半空间；然后两个半空间角色对调。拷贝回收器图7-28拷贝回收器图7-28（续）内部引用举例（略）//A.h

class

A

{

use

b;

}

//B.h

class

B

{