编译原理 7
运行时刻环境
- 存储管理: 栈分配, 堆管理, 垃圾回收
- 对变量, 数据的访问
存储分配的典型方式
- 代码, 静态区, 堆区, 空闲内存, 栈区
- 静态分配
- 动态分配
- 栈式存储: 和过程调用/返回同步, 值的声明周期与过程生命周期相同
- 堆存储: 数据对象比创建它的过程更加长寿
- 活动树
- 在时间上是嵌套的: 后调用的先返回, 栈数据结构
- 程序运行的所有过程活动可以用树表示
- 结点: 过程活动
- 根节点: main过程活动
- 过程p的某次活动对应的结点的所有子节点
- 调用序列->前序遍历; 返回序列->后序遍历
- 活动记录
- 过程调用和返回由控制栈进行管理
- 每个活跃的活动对应于栈中的一个活动记录
- 活动记录按照活动的开始时间, 从栈底到栈顶排列
- 实在参数->返回值->控制链->访问链->保存的机器状态->局部数据->临时变量
- 调用者和被调用者之间传递的值被放在活动记录的开始位置
- 固定长度的项(控制链, 访问链, 机器状态): 放在中间位置
- 早期不知道大小的栈在活动记录尾部
- 栈顶指针指向固定长度字段的末端
- 调用代码序列
- 调用代码序列: 为活动记录分配空间, 填写记录中的信息
- 返回代码序列: 恢复机器状态, 使调用者继续运行
- 调用代码序列会被分隔到调用者和被调用者中
- 调用代码序列的例子
- 调用者计算实在参数的值
- 将返回地址和原top_sp存放到被调用者的活动记录
- 调用者增加top_sp, 越过调用者的局部数据和临时变量, 以及参数和机器状态
- 被调用者保存机器状态
- 被调用者初始化局部数据, 开始运行
- 返回序列
- 被调用者将返回值放到与参数相邻的位置
- 恢复top_sp和寄存器, 跳转到返回地址
- 栈中的变长数据
- 非局部数据的访问
- 没有嵌套过程的数据访问
- 所有的函数都是全局的
- 函数的局部变量: 相对地址已知, 存放在当前活动记录内, 直接访问
- 全局变量: 在静态区, 地址编译时可知
- 函数很容易地作为参数传递: 首地址
- 有嵌套过程
- A中定义了过程B, 当他使用A中变量时, 必须通过访问链访问
- 嵌套深度
- 根据源程序静态确定: 全局为1, 嵌套于i的深度为i+1
- 访问链和访问链的使用
- 访问链被用于访问非局部的数据
- 如果过程p声明时, (直接)嵌套在过程q中, 那么p活动记录中的访问链指向上层最近的q的活动记录
- 从栈顶的活动记录开始, 访问链形成了一个链路, 嵌套深度随链路递减
- 设深度为np的过程p访问x, 而x在深度为nq的过程q中声明
- 差值np-nq在编译时已知; 从当前记录出发, 沿访问链前进这么多次, 找到活动记录
- x相对于这个记录的偏移量在编译时已知
- 访问链的维护: 过程q调用p时
- p深度大于q, 根据作用域规则, p必然在q中直接定义, p的访问链指向当前记录
- p = q, 新访问链等于当前活动记录的访问链
- p深度小于q, 必然过程r, p直接在r中定义, 而q嵌套在r中, p的访问链指向栈中r的活动记录
- 支持访问链的语言
- 显示表
- 用访问链访问数据, 访问开销和嵌套深度差有关
- 显示表: 数组d为每个嵌套深度保留一个指针
- 指针$d[i]$指向栈中最近的, 嵌套深度为i的活动记录
- 如果过程p访问嵌套深度为i的过程q中声明的变量x, 那么$d[i]$直接指向相应的活动记录
- 维护
- 调用p时, 在p的活动记录中保存$d[n_p]$的值, 并将$d[n_p]$设置为当前活动记录, 即p
- 从p返回时, 恢复$d[n_p]$的值
- 堆管理
- 堆空间
- 用于存放生命周期不确定, 或生存到被明确删除为止的对象
- 存储管理器
- 分配/回收堆区空间的子系统
- 根据语言而定: C/C++手动, JAVA自动
- 基本功能
- 分配: 为内存请求分配一段连续适当大小的堆空间, 首先从空闲空间取, 不行则从系统获取更多
- 回收: 把被回收的空间返回空闲空间缓冲池, 以满足其他需求
- 评价存储管理器的特性
- 空间效率: 使程序需要的堆空间最小
- 程序效率: 运用内存系统的层次, 使程序运行更快
- 低开小: 分配回收的操纵尽可能高效
- 计算机的存储层次结构
- 寄存器->一级缓存->二级缓存->物理内存->虚拟内存(磁盘)
- 程序执行的局部性
- 时间局部性: 一个被访问的存储位置, 很可能在一个很短的时间段内被再次访问
- 空间局部性: 一个被访问的存储位置, 其临近位置很可能在一个很短的时间段内被再次访问
- 90%时间被用来执行10%的代码
- 局部性可以充分利用层次存储结构
- 堆空间的碎片问题
- 每次分配通常只能用到一个窗口的部分空间, 留下更小的碎片
- 分配方法
- best-fit: 分配能够满足请求的最小的窗口, 留下大窗口, 容易产生碎片
- first-fit: 空闲的内存第一个能用的, 放置对象效率高, 总体性能差, 数据局部性好
- 使用容器的堆管理方法
- 设定不同大小的块规格, 相同的块放入同一容器
- 较小的尺寸设设置较多容器
- 空闲块大小: 16, 24, …, 512
- 大于512的按照对数划分, 每一尺寸是前一个的2倍
- 荒野块: 可以拓展的内存块
- 小尺寸的直接在容器中找, 大尺寸的在适当容器中寻找适当的空闲块, 可能需要分割, 可能需要从荒野块分割
- 管理和结合空闲空间
- 回收一个块时, 可以把这个块和相邻的块接合构成更大的块
- 支持邻接块结合的数据结构
- 手工存储管理
- 内存泄漏: 未能删除不可能再被引用的数据
- 悬空指针引用: 引用已被删除的数据
- 其他问题: 空指针, 数组越界
- 垃圾回收
- 垃圾
- 广义: 不需要再被引用的数据
- 狭义: 不能被引用(不可达)的数据
- 垃圾回收
- 垃圾回收器的设计目标
- 语言必须是类型按权的, 保证回收器能够知道数据元素是否为一个指向某内存块的指针
- c/c++类型不安全
- 性能目标
- 总体运行时间: 不显著增加应用程序的总运行时间
- 空间使用: 最大限度地利用可用内存
- 停顿时间: 当垃圾回收机制启动时, 可能引起应用程序的停顿
- 程序局部性: 改善空间局部性和时间局部性
- 可达性
- 指一个存储块可以被程序访问到
- 根集: 不需要指针解引用就可以直接访问到的数据
- 可达性: 根集可达; 任意对象, 如果指针保存在可达对象中, 那么这个对象也是可达的
- 性质: 一旦一个对象变成不可达, 它就不会再变成可达
- 改变可达对象集合的操作
- 对象分配: 返回一个新对象的引用
- 参数传递/返回值: 对象引用从实参传到形参, 从返回值传给调用者
- 引用赋值: u=v, v被赋值到u, u中原有的引用丢失, 使得其原来指向的对象不可达
- 过程返回: 活动记录出栈, 局部变量消失, 根集变小
- 垃圾回收方法
- 关注不可达: 捕获对象变成不可达的时刻, 回收占用空间
- 关注可达: 在需要时标出所有可达对象, 回收其他对象
- 基于引用计数的垃圾回收器
- 每个对象有引用计数字段
- 对象分配: 设为1
- 参数传递: 加1
- 引用赋值: u=v, u指向的-1, v指向的+1
- 过程返回: 局部变量指向对象的引用-1
- 一个对象的计数为0, 删除其之前, 其成员指针指向的对象引用计数-1
- 开销较大, 但不会引起停顿
- 循环垃圾的例子
- 对象相互引用, 没有来自外部的指针, 又不是根集成员, 都是垃圾, 但是引用计数大于0
- 基于跟踪的垃圾回收
- 标记-清扫式垃圾回收
- 直接的, 全面停顿的算法, 图遍历
- 分成2阶段
- 标记: 根集开始, 跟踪并标记出所有可达对象
- 清扫: 遍历整个堆区, 释放不可达对象
- 基本抽象分类: 每个存储块处于4种状态之一, 空闲, 未被访问, 待扫描, 已扫描
- 标记并压缩垃圾回收
- 重定位可达对象, 消除内存碎片
- 把可达对象移动到堆区的一端, 另一端则是空闲空间
- 空闲空间合并成单一块
- 整个过程分成3个步骤
- 拷贝垃圾回收
- 堆空间分为2个半空间
- 充满某个半空间时, 开始打击回收
- 回收时, 可达对象拷贝到另一个半空间
- 回收完成后, 两个空间角色对调
扫一扫，分享到微信
{title}
