清扫式垃圾回收器复原标记课件.pptVIP

7.5垃圾回收?垃圾：不能被引用的数据?垃圾回收的机制：–手动垃圾回收?程序员完成–自动垃圾回收?自动回收不可达数据的机制–优点：解除了程序员的负担–最早出现在LISP语言中–其他例子：?Java、Perl、ML、Modula-3、Prolog、Smalltalk

垃圾回收器的设计目标?基本要求：–语言必须是类型安全的。–回收器能够知道数据元素是否是一个指向某个内存块的指针。–类型不安全的语言：C，C++.?性能目标–总体运行时间：不能显著增加应用程序的总运行时间；–空间使用：最大限度地利用可用内存；–停顿时间：当垃圾回收机制启动时，可能引起应用程序的停顿。这个停顿应该比较短；–程序局部性：改善空间局部性和时间局部性。

可达性（Reachability）?可达性指一个存储块可被程序访问?根集(rootset)–先验可达数据?不需要对任何指针解引用(dereference)就可以直接访问的数据。?例：Java的根集由所有静态字段成员和栈中所有变量变量组成；?可达数据（具有可达性的对象）–根集＋任何可达数据引用的对象–一旦一个对象变得不可达，它就不会再变成可达的。

改变可达对象集合的操作?对象分配–返回一个指向新存储块的引用；?参数传递/返回值–对象引用从实在参数传递到形式参数，从返回值传递给调用者；?引用赋值：u=v–v的引用被复制到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标记－压缩详例

拷贝回