7.1 存储组织
内存可以分为代码区、静态区、堆区、栈区等。
- 对齐和补白(padding)
- 堆区向正方向增长,栈区向负方向增长
- 人工分配和释放数据对象(
malloc
和free
)
静态和动态存储分配
静态分配:编译器在编译时刻就可以做出存储分配决定,不需要考虑程序运行时刻的情形。适用于全局常量、全局变量。
动态分配:
- 栈式存储:和过程的调用/返回同步进行分配和回收,值的生命期和过程的生命期相同;
- 堆存储:数据对象比创建他的过程调用更长寿,需要手工进行回收、建立垃圾回收机制。
7.2 空间的栈式分配
7.2.1 活动树
过程调用(活动)在时间上总是嵌套的。
- 后调用的先返回
- 适合用栈来分配活动过程中所需的内存空间
程序运行的所有过程活动可以用活动树来表示:
- 每个节点对应于一个过程活动
- 根节点对应于
main
过程的活动 - 过程$p$的(某次活动对应的节点的所有子节点)表示(此次活动所调用的各个过程活动),顺序为从左到右先后调用
7.2.2 活动记录
- 过程调用和返回由控制栈进行管理
- 每个活跃的活动对应于栈中的一个活动记录
活动记录按照活动的开始时间,从栈底到栈顶排列。
一个概括性的活动记录包括:
- 实在参数(实参)
- 返回值
- 控制链:指向调用者的活动记录
- 访问链:当被调用过程需要其他地方的某个数据时需要使用访问链进行定位
- 保存的机器状态:保存的现场(寄存器)、返回地址
- 局部数据
- 临时变量
7.2.3 调用代码序列
- 调用代码序列(calling sequence):为活动记录分配空间,天蝎记录中的信息
- 返回代码序列(return sequence):恢复机器状态,使调用者继续运行
调用代码序列会分割到调用者和被调用者中,根据源语言、目标机器和操作系统的限制,可以有不同的分割方案;把代码尽可能放在被调用者中。
调用/返回代码序列的要求:
- 数据方面:
- 能够把参数正确的传递给被调用者
- 能够把返回值传递给调用者
- 控制方面:
- 能够正确转到被调用过程的开始位置
- 能够正确转回调用者的调用位置(的下一条指令)
活动记录的布局原则:
- 调用者和被调用者之间传递的值在被调用者活动记录的开始位置
- 固定长度的项(控制链、访问链、机器状态)放在中间位置
- 早期不知道大小的项`放在活动记录尾部
- 栈顶指针(
top\_sp
)通常指向固定长度字段的末端(机器状态后)
7.2.4 栈中的变长数据
如果数据对象的生命局限于过程活动的生命期,就可以把数据分配在运行时刻栈中。
- 在分配数组的位置分配一个指针,指向数组存放的位置。
- 两个指针
top
和top_sp
,前者指向下一个活动记录降压开始的位置,后者用来找到顶层活动记录的局部定长字段。
7.3 栈中非局部数据的访问
7.3.1 没有嵌套过程时的数据访问
不支持嵌套过程:某个变量要么在函数内定义,要么在全局定义。
- 函数的局部变量:相对地址已知,且存放在当前活动记录内,使用
top_sp
指针加上相对地址即可访问 - 全局变量:在静态区,地址在编译时刻可知
7.3.2 和嵌套过程相关的问题
一个过程可以访问另一个过程的变量,只要后一个过程的声明包含了前一个过程的声明即可。如A的声明包含了过程B的说明,那么B可以使用在A中声明的变量。
当B的代码运行时,如果它使用的是A中的变量,必须通过访问链访问,而不能通过控制链来访问调用者获得变量:
- 间接调用:
A -> C -> B
- 直接调用:
A -> B
7.3.4 嵌套深度
对于不内嵌在任何其他过程中的过程,定义其嵌套深度为$1$;如果一个过程$p$在深度为$i$的过程中定义,则$p$的嵌套深度为$i + 1$。
7.3.5 访问链
访问链(access link)被用于访问非局部的数据:
- 如果过程$p$在声明时(直接)嵌套在过程$q$中,那么$p$的活动记录中访问链指向上层最近的$q$的活动记录
- 从栈顶活动开始,访问链形成了一个链路,嵌套深度沿着链路逐一递减
设深度为$n_p$的过程$p$访问变量$x$,而变量$x$在深度为$n_q$的过程$q$中声明:
- 从当前活动记录触发,沿访问链前进$n_p - n_q$(编译时刻已知)找到活动记录
- $x$相对于这个活动记录的偏移量在编译时刻已知
7.4 堆管理
7.4.4 碎片整理
堆空间分配方法:
- Best-fit:总是讲请求的内存分配在满足请求的最小窗口中
- 好处:可以将大的窗口保留下来,应对更大的请求
- First-fit:总是将对象放置在第一个能够容纳请求的窗口中
- 放置对象花费时间较少,但是总体性能较差
- 经常具有良好的数据局部性,同一时间段内生成的对象经常被分配在连续的空间内
使用容器机制的堆管理方法:
- 设定不同大小的块规格,相同的块放入同一容器
- 较小的(常用的)尺寸设置较多的容器
- 小尺寸直接在容器中找,大尺寸寻找适当的空闲块或进行分割
管理和接合空闲空间:
- 当回收一个块时,可以把这个块和相邻的块接合起来,形成更大的块
- 数据结构:
- 边界标记
- 双向链表
7.4.5 人工回收请求
人工回收带来的问题:
- 内存泄漏:未能删除不可能再被引用的数据
- 悬空指针引用:引用已被删除的数据
其他问题:空指针访问/数组越界访问
7.5 垃圾回收概述
垃圾:(广义)不需要再被引用的数据,(狭义)不能被引用(不可达)的数据。
垃圾回收:自动回收不可达数据的机制,解除了程序员的负担。
7.5.1 垃圾回收器的设计目标
基本要求:
- 语言必须是类型安全的,保证回收器能够知道数据元素是否为一个指向某内存块的指针
- 类型不安全的语言:如C/C++,无法确定数据的类型
性能目标:
- 总体运行时间:不显著增加应用程序的总运行时间
- 空间使用:最大限度地利用可用内存
- 停顿时间:当垃圾回收机制启动时,可能引起应用程序的停顿,这个停顿应该比较短
- 程序局部性:改善空间局部性和时间局部性
7.5.2 可达性
可达性:一个存储块可以被程序访问到
根集:不需要指针解引用就可以直接访问的数据,如静态成员和栈中变量
- 根集的成员都是可达的
- 对于任意一个对象,如果指向它的一个指针被保存在可达对象的某字段或数组元素中,那么这个对象也是可达的
可达性的性质:一旦一个对象变得不可达,它就不会再变成可达的。
改变可达对象集合的操作:
- 对象分配
- 参数传递、返回值
- 引用赋值
- 过程返回(出栈)
垃圾回收方法:
- 关注不可达:变为不可达的时候回收内存
- 关注可达:在需要时标出所有可达对象,回收其他对象
7.5.3 引用计数垃圾回收器
每个对象有一个用于存放引用计数的字段,并按如下方式维护:
- 对象分配:引用计数设为1
- 参数传递:引用计数加1
- 引用赋值:$u=v$,$u$指向的对象引用减1,$v$指向的对象引用加1
- 过程返回:局部变量指向对象的引用减1
如果一个对象的引用计数为0,在删除对象前,此对象各个指针成员所指对象的引用计数减1。
引用计数进行垃圾回收的方式开销较大,但不会引起停顿。
循环垃圾:多个对象相互引用,没有来自外部的指针,又不是根集成员,但都是垃圾,却无法被基于引用的垃圾回收机制回收。
7.6 基于跟踪的垃圾回收
7.6.1 标记-清扫式垃圾回收
一种直接的、全面停顿的算法。
分成两个阶段:
- 标记:从根集开始,跟踪并标记出所有的可达对象;
- 清扫:遍历整个堆区,释放不可达对象。
7.6.2 基本抽象
基本抽象分类:
- 每个存储块处于四种状态之一:空闲、未被访问(未知)、待扫描、已扫描
- 对存储块的操作会改变存储块的状态:应用程序分配、垃圾回收器扫描、回收
7.6.4 标记并压缩垃圾回收
对可达对象进行重定位可以消除存储碎片
- 堆区的一端是可达对象,另一端是空闲空间
- 空闲空间合并成单一块,提高分配内存时的效率
整个过程分成三个步骤:
- 标记
- 计算新位置
- 移动并设置新的引用
7.6.5 拷贝垃圾回收
堆空间被分成两个半空间:
- 应用程序在某个半空间分配存储
- 垃圾回收时可达对象被拷贝到另一个半空间
- 回收完成后两个半空间角色对调
优点:不涉及任何不可达对象
Loading Comments By Disqus