37
存储管理器

基本功能


分配：为每个内存请求分配一段连续的、适当大 小的堆空间。首先从空闲的堆空间分配；如果不 行则从操作系统中获取内存、增加堆空间。 回收：把被回收的空间返回空闲空间缓冲池，以 满足其他的分配。

评价存储管理器的特性：



空间效率：是程序需要的堆空间最小，即减小碎 片 程序效率：充分运用内存系统的层次，提高效率 低开销：使分配/收回内存的操作尽可能高效

用访问链访问数据时，如果嵌套深度大，则 访问的效率差。 显示表：使用数组d为每个嵌套深度保留一个 指针


显示表的维护

指针d[i]指向最高的深度为i的的活动记录。 如果程序p中访问深度为i的过程q的变量x，那么 d[i]直接指向相应的q活动记录；
调用过程p时，在p的活动记录中保留d[np]的值， 并将d[np]设置为当前活动记录。 从p返回时，恢复d[np]的值。
25

Return sequence

调用代码序列的例子
26
7.3.4栈中的 变长数据



如果数据对象 的生命期局限 于过程活动的 生命期，就可 以分配在运行 时刻栈中。 top指向实际的 栈顶 top_sp用于寻 找顶层记录的 定长字段
27
7.4 非局部数据的访问（无嵌套过程）

没有嵌套过程时的数据访问

调用这计算实在参数的值 将返回地址和原top_sp存放到被调用者的活动记 录中。调用者增加top_sp的值（越过了局部数据、 临时变量、被调用者的参数、机器状态字段） 被调用者保存寄存器值和其他状态字段 被调用者初始化局部数据、开始运行。 被调用者将返回值放到和参数相邻的位置 恢复top_sp和寄存器，跳转到返回地址。

程序运行的所有过程活动可以用树表示

13
活动树的例子（1）


程序：P277，图7-2 过程调用（返回）序 列和活动树的前序 （后序）遍历对应 假定当前活动对应结 点N，那么所有尚未 结束的结点对应于N 及其祖先结点。
14
活动树的例子（1）
m r p(1,9) q(1,9) q(1,3) q(5,9) p(5,9) q(5,5) q(7,9) p(7,9) q(7,7) q(9,9)
28
7.4.1非局部数据的访问（无嵌套过程）



PASCAL中，如果过程A 的声明中包含了过程B的 声明，那么B可以使用在A 中声明的变量。 当B的代码运行时，如果 它使用的是A中的变量。 那么这个变量指向运行栈 中最上层的同名变量。 但是，我们不能通过嵌套 层次直接得到A的活动记 录的相对位置。
void A() {
int void { } void C();
}
x,y; B() int b; x = b+y;
C(){B();}
当A调用C，C又调用B时:
B的活动记录
C的活动记录
A的活动记录
29
7.4.2 嵌套深度

嵌套深度是正文概念，可以根据源程序静 态地确定 不内嵌于任何其他过程中的过程，嵌套 深度为1 嵌套在深度为i的过程中的过程，深度 为i+1.
3
7.1 概述


为什么要使用数据区 程序运行时各种数据必须放在内存中， 便于访问和使用。 数据区的管理 内存永远不能满足需要； 必须找到存贮的数据； 按照程序单位（过程、函数）分配和 管理数据区。
4
7.1 概述

1. 2.
数据区存贮的内容
变量和常数（用户自己定义） 临时单元：源程序中没有，编译程序在生成 中间代码时建立和使用。 形式单元：存放过程或函数间传递的参数； 返回地址：返回主调程序的入口。 保护区：保存主调程序的寄存器内容，恢复 现场。 数据访问控制信息

分配方式 在符号表中按照对象属性顺序分配 数据区，从而建立一个数据映像，运 行时按照此映像分配实际的内存数据 区。
10
7.2 静态存贮分配
符号表如下，DA栏表示数据区编号，ADDR栏是 相对地址 NAME 入 VA TYPE KIND DA ADDR 位 长 口 L 置 度 01 0 4 integer 简变 K a 02 4 1 integer 简变 K a+4 03 5 1 integer 简变 K a+8 ┋
11
7.3 栈式分配

内容： 活动树 活动记录 调用代码序列 栈中的变长数据
12
7.3.1 活动树

过程调用（过程活动）在时间上总是嵌套的：

后调用的先返回 因此可以用栈式分配来处理过程活动所需要的 内存空间。 每个结点对应于一个过程活动 根结点对应于main过程的活动 过程p的某次活动对应的结点的子结点对应于 此次活动调用的各个过程活动（从左向右，表 示调用的先后顺序）。
30
深度为1 sort 深度为2 readArray， exchange， quicksort 深度为3 partition
31
7.4.3 访问链


访问链被用于访问非局部的数据 如果过程p在声明时嵌套在过程q的声明中， 那么p的活动记录中的访问链指向最上层的 q的活动记录。 从栈顶活动记录开始，访问链形成了一个 链路，嵌套深度逐一递减。
17
指向调用者的 活动记录 用来访问存于其 它活动记录中的 非局部数据
运行时刻栈的例子

a[11]为全局变量 main没有局部变量 r有局部变量I q的局部变量i，和参 数m,n。
18
运行时刻栈的例子
运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录）
m a : array
23
调用/返回代码序列的要求

数据方面

能够把参数正确地传递给被调用者 能够把返回值传递给调用者 能够正确转到被调用者的代码的开始位置 能够正确转会调用者的调用位置（的下一条指 令）
24

控制方面


调用代码序列和活动记录的布局相关
调用代码序列的例子

Calling sequence

15
p(1,3) q(1,0) q(2,3)
p(2,3) q(2,1) q(3,3)
7.3.2 活动记录


过程调用和返回由控制栈进行管理 每个活跃的活动对应于栈中的一个活动 记录 活动记录按照活动的开始时间，从栈底 到栈顶排列
16
一般的活动记录的布局
实参 返 回 值 可选的控制链 可选的访问链 保存的机器状态 局部数据 临时数据
35
显示表的例子
q(1,9)调用q(1,3) 时，q的深度为2
q(1,3)调用p， p的深度为3
q调用e，e存贮分配


含义 在编译时无法确定数据区的大小，在过 程的入口处也确定不了数据区的大小， 因此无法使用静态或栈式分配方法。 条件 有static类型、指针类型和表单(form)等 变量。



调用代码序列(calling sequence)为活动记录 分配空间，填写记录中的信息； 返回代码序列(return sequence)恢复及其状 态，是调用者继续运行。 调用代码序列会分割到调用者和被调用者 中。


根据源语言、目标机器、操作系统的限制，可 以有不同的分割方案 把代码尽可能放在被调用者中。
第7 章 运行时刻环境
1
概 述 静态存储管理 栈式存储管理 堆式存储管理
2
7.1 概述

运行时刻环境

为数据分配安排存储位置 确定访问变量时使用的机制 过程之间的连接 参数传递 和操作系统、输入输出设备相关的其它接口

目的
编译程序除了要关心目标代码生成问题外， 还必须要考虑程序运行时使用的数据区域的管理 问题。
5
3. 4. 5.
6.
7.1 概述

主题

存储管理：栈分配、堆管理、垃圾回收 对变量、数据的访问 本章核心问题
如何访问到数据
6
1）存储分配的典型方式


目标程序的代码放置在代码 区 静态区、堆区、栈区分别放 置不同类型生命期的数据值， 即数据区
7
2）静态和动态存储分配

静态分配




编译器在编译时刻就可以做出存储分配决 定，不需要考虑程序运行时刻的情形 不存在可变长的数组、可变长的字符串、 指针； 不存在函数或过程的嵌套和递归。 全局变量
32
7.4.3 访问链

设深度为np的过程p访问变量x，而变量x在 深度为nq的过程中声明，那么


从当前活动记录出发，沿访问链前进np-nq 次找到的活动记录中的x就是要找的变量位 置 x相对于活动记录的偏移量在编译时刻已知 np-nq在编译时刻已知；
33
访问链的例子
34
7.4.4 显示表
m r q(1,9)
21
运行时刻栈的例子
运行栈：把控制栈中的信息拓广到包括过程 活动所需的所有局部信息（即活动记录） m a : array q (1, 9) k: integer m r q(1,9)
p(1,9) q(1,3) p(1,3) q(1,0)
22
q (1, 3)
k: integer
7.3.3 调用代码序列
38

堆空间的分配及管理


固定长分块法：将堆空间分成大小相同的块，使用链 表连接各个单元；适用于类型单一或长度一致的数据 类型。 可变长分块法：将堆空间分成长度不同的块。