运行时刻环境-南京大学计算机系.PPT

例子 相邻的存储块A、B、C 当回收B时，通过对free/used位的查询，可以知道B左边的A是空闲的，而C不空闲。 同时还可以知道A、B合并为长度为300的块。 修改双重链表，把A替换为A、B接合后的空闲块 注意：双重链表中一个结点的前驱并不一定是它邻近的块 处理手工存储管理 两大问题： 内存泄露：未能删除不可能再被引用的数据 悬空指针引用：引用已被删除的数据 其他问题 空指针访问/数组越界访问 解决方法： 自动存储管理 正确的编程模式 正确的编程模式（1） 对象所有者（Object ownership） 每个对象总是有且只有一个所有者（指向此对象的指针）；只有通过Owner才能够删除这个对象； 当Owner消亡时，这个对象要么也被删除，要么已经被传递给另一个owner。 语句v=new ClassA；创建的对象的所有者为v； 即将对v进行赋值的时刻（v的值即将消亡） 要么v已经不是它所指对象的所有者；比如g=v可以把v的ownership传递给g 要么需要在返回/赋值之前，执行delete v操作； 编程时需要了解各个指针在不同时刻是否owner。 防止内存泄漏，避免多次删除对象。不能解决悬空指针问题。 正确的编程模式（2） 引用计数 每个动态分配的对象附上一个计数：记录有多少个指针指向这个对象； 在赋值/返回/参数传递时维护引用计数的一致性； 在计数变成0之时删除这个对象； 可以解决悬空指针问题；但是在递归数据结构中仍然可能引起内存泄漏； 需要较大的运行时刻开销。 基于区域的分配 将一些生命期相同的对象分配在同一个区域中； 整个区域同时删除。 垃圾回收 垃圾： 狭义：不能被引用（不可达）的数据 广义：不需要再被引用的数据 垃圾回收：自动回收不可达数据的机制，解除了程序员的负担。 使用的语言 Java、Perl、ML、Modula-3、Prolog、Smalltalk 垃圾回收器的设计目标 基本要求： 语言必须是类型安全的：保证回收器能够知道数据元素是否为一个指向某内存块的指针。 类型不安全的语言：C，C++. 性能目标 总体运行时间：不显著增加应用程序的总运行时间； 空间使用：最大限度地利用可用内存； 停顿时间：当垃圾回收机制启动时，可能引起应用程序的停顿。这个停顿应该比较短； 程序局部性：改善空间局部性和时间局部性。 可达性 直观地讲，可达性就是指一个存储块可以被程序访问到。 根集：不需要指针解引用就可以直接访问的数据。 Java：静态成员、栈中变量； 可达性 根集的成员都是可达的； 对于任意一个对象，如果指向它的一个指针被保存在可达对象的某字段中、或数组元素中，那么这个对象也是可达的。 性质： 一旦一个对象变得不可达，它就不会再变成可达的。 改变可达对象集合的操作 对象分配：返回一个指向新存储块的引用； 参数传递/返回值：对象引用从实在参数传递到形式参数，从返回值传递给调用者； 引用赋值：u=v；v的引用被复制到u中，u中原来的引用丢失。可能使得u原来指向的对象变得不可达，并且递归地使得更多对象变得不可达。 过程返回：活动记录出栈，局部变量消失，根集变小；可能使得一些对象变得不可达。 垃圾回收方法分类 跟踪相关操作，捕获对象变得不可达的时刻，回收对象占用的空间 在需要时，标记出所有可达对象、回收其它对象 基于引用计数的垃圾回收器 每个对象有一个用于存放引用计数的字段，并按照如下方式维护 对象分配：引用计数设为1 参数传递：引用计数加1 引用赋值：u=v：u指向的对象引用减1、v指向的对象引用加1 过程返回：局部变量指向对象的引用计数减1 如果一个对象的引用计数为0，在删除对象之前，此对象中各个指针所指对象的引用计数减1 回收器有缺陷，可能引起内存泄漏 开销较大、但是不会引起停顿 引用计数的例子 考虑如下操作: y=x y是当前函数f的局部变量,且f返回 修改计数后总是先考虑是否释放； 释放一个对象之前总是先处理对象内部的指针 循环垃圾的例子 基于跟踪的垃圾回收 标记-清扫式垃圾回收 标记-清扫式垃圾回收的优化 标记并压缩垃圾回收 拷贝垃圾回收 标记-清扫式垃圾回收 一种直接的、全面停顿的算法 分成两个阶段 标记：从根集开始，跟踪并标记出所有可达对象； 清扫：遍历整个堆区，释放不可达对象； 如果我们把数据对象看作顶点，引用看作有向边，那么标记的过程实际上是从根集开始的图遍历的过程。 标记-清扫垃圾回收算法 因为语言是强类型的，所有垃圾回收机制可以知道每个数据对象的类型，以及这个对象有哪些字段是指针 例子 假设x是全局变量，y是当前函数活动的局部变量； 当前活动返回之后，进行标记清扫 A，D，E，F，I，G，H B，C不可达 基本抽象分类 每个存储块处于四种状态之一 空闲 未被访问 待扫描 已扫描 对存储块的操作