第七章 运行时存储空间管理
第一节 变量及存储分配
程序投入运行的必要条件,
?一组可运行的代码
?一个运行环境：分配空间、提供运行信
息
一, 程序的存储空间
1,代码空间, 线性存放着目标指令序列
在 GAM中,当前执行的指令位置由指
令指针 ip指示。
2,数据空间
(1)内容, 变量、常数、控制和管理信
息、描述符等
(2)静态分配, 在运行前就可确定数据
空间的大小,在编译时刻就能进行的存储
分配
(3)动态分配, 运行时才能进行的存储
分配
?栈分配, 因变量生存期的嵌套性
?堆分配, 因生存期的随机交叉特性
二, 活动记录
一个程序单元的一次激活所需的信息管
理是通过相应的活动记录来实施的。一
个单元的每次激活，都应建立相应的活
动记录，它是单元实例的一部分。
1,活动记录的内容
(1)返回地址
(2)动态链和静态链
(3)形式单元
(4)局部变量或其描述符，以及临时变
量
返回地址
动态链
静态链
变量存储区
形式单元
2,活动记录的特点
除了变量存储区外,其余部分存储长
度编译时可以确定,则元素 i的地址可用下
式计算
D+offset(i)
其中,offset(i)是 i在活动记录中的位移 ; D是
活动记录的首地址
三, 变量的存储分配
1,静态变量, 不管在程序单元的哪一次
活动中,均绑定于相同的存储位置
条件是, 活动记录,变量的存储位置在
编译时可以确定
2,半静态变量, 编译时确定相对位置,
单元被激活后,x绑定于 D+offset(x)
条件是, 语言允许递归调用
3,半动态变量, 动态数组 ; 编译时在活
动记录中建立描述符
例, [1..m] int a;
[1..n] int b;
4,动态变量, 动态分配。编译时在活动
记录中为动态变量设置二个指针,一个指
向该变量的描述符,另一个指向该变量的
存储空间
四, 存储分配模式
1,静态分配
只允许静态变量,变量与存储区域的
绑定关系在编译时便可建立,并完成存储
分配。
不允许递归调用,不允许动态数组,不
允许动态类型的数据对象,即不允许有非
静态变量。如, FORTRAN语言。
2,栈式分配
?各单元之间的调用关系遵循“后进先出”
模式 ;
?活动记录的建立和撤消也满足“后进先
出”模式 ;
?用栈分配活动记录 ;
?分配方法, 当激活一个程序单元时,其活
动记录就动态地分配于栈顶。
R的活动记录
Q的活动记录
P的活动记录
如,P调用 Q,Q调用 R
..,
..,
..,
3,堆分配
由于动态变量表示的数据对象,它的长度、
个数都有可能在执行中改变,即在其生存期中
动态改变,就不可能在栈上为这样的对象作分
配。
出现下列情况时,必须用堆式分配,
(1)单元活动结束后,局部变量的值还需保留 ;
(2)调用单元与被调用单元的生存期不满足
嵌套关系,即出现交叉现象。
4,存储空间的组织
代码
静态数据
栈
堆
第二节 静态分配
O,FORTRAN语言的特点
1,模块结构
一个主程序段和若干个 (可以是 0个 )辅
程序段组成 ; 辅程序段可以是子程序、函
数段或数据块；各段可以独立编译。
2,说明语句无严格语序,且具有显式说
明和隐式说明。
INTEGER A,B
DIMENSION X,Y
DIMENSION B(10)
REAL X(20)
INTEGER Y(10,20)
COMMOM A,X
EQUIVALENCE (I,B(4)),(X(2),Z)
例,
3,公用 (COMMON)和等价
(EQUIVALENCE)语句建立了数据空间的
同一性。
4,不允许过程的递归性 ; 每个数据名所
需的存储空间大小都是常量 ; 所有数据名
的性质是确定的。
一, FORTRAN程序运行时的结构
由 FORTRAN的特点知，每个单元的活
动记录及变量在运行前便可建立，其生
存期延续到整个程序结束。
1,FORTRAN程序编译过程
(1)编译时, 变量约束于活动记录的常
量位移, 对变量的引用可用二元式
（ 单元名, 位移 ） 表示；转换控制
语句中对指令的引用也可翻译成二
元式 （ 单元名, 指令在代码段中的
位移 ） 。
(2)连接时，须将程序所有单元连接起
来，将代码段分配到代码区，活动
记录分配到数据区。同时将编译时
的二元式转换为地址。
(3)装入时，将连接后的可重定位代码
程序装入主存储器并定位，成为可
直接执行的机器代码，并将 ip指向程
序第一条指令，使程序处于可执行
状态。
2,FORTRAN程序在 GAM中的存储结构
单元 1代码段
单元 2代码段
单元 n代码段
全局数据活动记录
单元 1活动记录
单元 2活动记录
单元 n活动记录
…...
…...
ip
二, 运行环境的转换
约定,
?d [i,j] —— 单元 i的活动记录中位移为 j的
存储单元内容
?c [i,j] —— 单元 i的代码段中位移为 j的指
令
?D [ m ],C[m]—— 连接后的实际存储地址
?& X —— X 的地址
1,GOTO X语句
ip,= & c [ i,j ]
其中,c[i,j]是编译后标号 X对应的二元式
2,过程调用语句 CALL P
(1)保存返回地址
d [P,0 ],= ip + 8
(2)转入 P
ip,= & c [ P,0 ]
连接后,D [m ],= ip + 8
ip,= n
其中,m为 P的活动记录的首址 ;n为 P代码段
首址
3,返回语句 RETURN
取返回地址 ip,= d [ P,0 ]
连接后 ip,= D [m ]
其中 m 是单元 P的活动记录的首址
举例, INTEGER I,J /*主程序 */
COMMON I
CALL X
GOTO 10
10 CONTINUE
END
SUBROUTINE X /*子程序 */
INTEGER K,J
COMMON I
K = 5
I = 6
J = I + K
RETURN
END
D[3]:=ip+8
ip:=20
ip:=12
noop
halt
D[4]:=5
D[0]:=6
D[5]:=D[0]+D[4]
ip:=D[3]
halt
0
4
8
12
16
20
24
28
32
36
代码存储器
0
1
2
3
4
5
common
main
X
I
返回地址
J
返回地址
K
J
ip=0
数据存储器
0
1
2
3
4
5
common
main
X
I
返回地址
J
返回地址
K
J
ip=20
数据存储器
8
0
1
2
3
4
5
common
main
X
I
返回地址
J
返回地址
K
J
ip=28
数据存储器
6
8
5
0
1
2
3
4
5
common
main
X
I
返回地址
J
返回地址
K
J
ip=8
数据存储器
6
8
5
11
第三节 栈式分配
?语言特点：允许递归，允许动态数组，
允许过程嵌套定义
一, 只含半静态变量的栈式分配
1,特点,
?仅允许递归调用
?变量及活动记录长度可静态确定
?一个单元可多次激活而有多个实例,
每个活动记录是在单元每次激活时
动态建立并与代码段建立绑定关系
的
2,处理方法
(1)设置当前栈指针 current,表示当前活动
记录的开始位置
(2)指针 free表示数据存储器下一个可用单元
(3)变量绑定于它在活动记录中的常数位移 i,
变量通过 current变址访问
(4)A调用 B时, 在 A活动记录的栈顶之上建
立起绑定于 B的当前实例的活动记录
(5)从 B返回时, 释放其活动记录
3,动态连接和动态链
?动态连接,A调用 B时, B的活动记
录中保存的 A的活动记录地址
?动态链：由动态连接组成的一个调
用链
A
E
F
G
F
A call E; E call F; F call G; G call F;
..,
..,
..,
..,
..,
4,CALL P 的处理
(1)保存返回地址
D [ free ],= ip + 20
(2)保存主调过程的 current
D [free + 4],= current
(3)建立 P的 current
current,= free
(4)调整 free
free,= free + L
(5)转子
ip,= P的代码段首地址
返回地址
动态连接
返回地址
动态连接
A的活动记录
即将建立的
P的活动记录
current
free
过程 A中调用了 P
返回地址
动态连接
返回地址
动态连接
A的活动记录
P的活动记录
current
free
进入过程 P以后
5,RETURN语句的处理
(1)恢复 free
free,= current
(2)恢复主调过程的 current
current,= D[current + 4]
(3)返回
ip,= D [free]
二, 半静态变量的栈式分配
1,活动记录内容
返回地址
动态链
静态链
保护区
参数单元
局部变量
临时变量
数组存储区
其中，局部变量中包括数组的描述符
2,动态数组空间的分配
(1)编译时, 分配内情向量表区, 并产
生在运行时动态的建立内情向量和
分配数组空间的指令 ;
(2)一个单元激活后 （ 进入该单元 ）,
遇到动态数组说明时, 调用上述指
令 （ 填内情向量, 分配数组空间 ）,
并调整 free,= free + L。
三, 动态变量的存储分配
在堆上进行存储分配
第一节 变量及存储分配
程序投入运行的必要条件,
?一组可运行的代码
?一个运行环境：分配空间、提供运行信
息
一, 程序的存储空间
1,代码空间, 线性存放着目标指令序列
在 GAM中,当前执行的指令位置由指
令指针 ip指示。
2,数据空间
(1)内容, 变量、常数、控制和管理信
息、描述符等
(2)静态分配, 在运行前就可确定数据
空间的大小,在编译时刻就能进行的存储
分配
(3)动态分配, 运行时才能进行的存储
分配
?栈分配, 因变量生存期的嵌套性
?堆分配, 因生存期的随机交叉特性
二, 活动记录
一个程序单元的一次激活所需的信息管
理是通过相应的活动记录来实施的。一
个单元的每次激活，都应建立相应的活
动记录，它是单元实例的一部分。
1,活动记录的内容
(1)返回地址
(2)动态链和静态链
(3)形式单元
(4)局部变量或其描述符，以及临时变
量
返回地址
动态链
静态链
变量存储区
形式单元
2,活动记录的特点
除了变量存储区外,其余部分存储长
度编译时可以确定,则元素 i的地址可用下
式计算
D+offset(i)
其中,offset(i)是 i在活动记录中的位移 ; D是
活动记录的首地址
三, 变量的存储分配
1,静态变量, 不管在程序单元的哪一次
活动中,均绑定于相同的存储位置
条件是, 活动记录,变量的存储位置在
编译时可以确定
2,半静态变量, 编译时确定相对位置,
单元被激活后,x绑定于 D+offset(x)
条件是, 语言允许递归调用
3,半动态变量, 动态数组 ; 编译时在活
动记录中建立描述符
例, [1..m] int a;
[1..n] int b;
4,动态变量, 动态分配。编译时在活动
记录中为动态变量设置二个指针,一个指
向该变量的描述符,另一个指向该变量的
存储空间
四, 存储分配模式
1,静态分配
只允许静态变量,变量与存储区域的
绑定关系在编译时便可建立,并完成存储
分配。
不允许递归调用,不允许动态数组,不
允许动态类型的数据对象,即不允许有非
静态变量。如, FORTRAN语言。
2,栈式分配
?各单元之间的调用关系遵循“后进先出”
模式 ;
?活动记录的建立和撤消也满足“后进先
出”模式 ;
?用栈分配活动记录 ;
?分配方法, 当激活一个程序单元时,其活
动记录就动态地分配于栈顶。
R的活动记录
Q的活动记录
P的活动记录
如,P调用 Q,Q调用 R
..,
..,
..,
3,堆分配
由于动态变量表示的数据对象,它的长度、
个数都有可能在执行中改变,即在其生存期中
动态改变,就不可能在栈上为这样的对象作分
配。
出现下列情况时,必须用堆式分配,
(1)单元活动结束后,局部变量的值还需保留 ;
(2)调用单元与被调用单元的生存期不满足
嵌套关系,即出现交叉现象。
4,存储空间的组织
代码
静态数据
栈
堆
第二节 静态分配
O,FORTRAN语言的特点
1,模块结构
一个主程序段和若干个 (可以是 0个 )辅
程序段组成 ; 辅程序段可以是子程序、函
数段或数据块；各段可以独立编译。
2,说明语句无严格语序,且具有显式说
明和隐式说明。
INTEGER A,B
DIMENSION X,Y
DIMENSION B(10)
REAL X(20)
INTEGER Y(10,20)
COMMOM A,X
EQUIVALENCE (I,B(4)),(X(2),Z)
例,
3,公用 (COMMON)和等价
(EQUIVALENCE)语句建立了数据空间的
同一性。
4,不允许过程的递归性 ; 每个数据名所
需的存储空间大小都是常量 ; 所有数据名
的性质是确定的。
一, FORTRAN程序运行时的结构
由 FORTRAN的特点知，每个单元的活
动记录及变量在运行前便可建立，其生
存期延续到整个程序结束。
1,FORTRAN程序编译过程
(1)编译时, 变量约束于活动记录的常
量位移, 对变量的引用可用二元式
（ 单元名, 位移 ） 表示；转换控制
语句中对指令的引用也可翻译成二
元式 （ 单元名, 指令在代码段中的
位移 ） 。
(2)连接时，须将程序所有单元连接起
来，将代码段分配到代码区，活动
记录分配到数据区。同时将编译时
的二元式转换为地址。
(3)装入时，将连接后的可重定位代码
程序装入主存储器并定位，成为可
直接执行的机器代码，并将 ip指向程
序第一条指令，使程序处于可执行
状态。
2,FORTRAN程序在 GAM中的存储结构
单元 1代码段
单元 2代码段
单元 n代码段
全局数据活动记录
单元 1活动记录
单元 2活动记录
单元 n活动记录
…...
…...
ip
二, 运行环境的转换
约定,
?d [i,j] —— 单元 i的活动记录中位移为 j的
存储单元内容
?c [i,j] —— 单元 i的代码段中位移为 j的指
令
?D [ m ],C[m]—— 连接后的实际存储地址
?& X —— X 的地址
1,GOTO X语句
ip,= & c [ i,j ]
其中,c[i,j]是编译后标号 X对应的二元式
2,过程调用语句 CALL P
(1)保存返回地址
d [P,0 ],= ip + 8
(2)转入 P
ip,= & c [ P,0 ]
连接后,D [m ],= ip + 8
ip,= n
其中,m为 P的活动记录的首址 ;n为 P代码段
首址
3,返回语句 RETURN
取返回地址 ip,= d [ P,0 ]
连接后 ip,= D [m ]
其中 m 是单元 P的活动记录的首址
举例, INTEGER I,J /*主程序 */
COMMON I
CALL X
GOTO 10
10 CONTINUE
END
SUBROUTINE X /*子程序 */
INTEGER K,J
COMMON I
K = 5
I = 6
J = I + K
RETURN
END
D[3]:=ip+8
ip:=20
ip:=12
noop
halt
D[4]:=5
D[0]:=6
D[5]:=D[0]+D[4]
ip:=D[3]
halt
0
4
8
12
16
20
24
28
32
36
代码存储器
0
1
2
3
4
5
common
main
X
I
返回地址
J
返回地址
K
J
ip=0
数据存储器
0
1
2
3
4
5
common
main
X
I
返回地址
J
返回地址
K
J
ip=20
数据存储器
8
0
1
2
3
4
5
common
main
X
I
返回地址
J
返回地址
K
J
ip=28
数据存储器
6
8
5
0
1
2
3
4
5
common
main
X
I
返回地址
J
返回地址
K
J
ip=8
数据存储器
6
8
5
11
第三节 栈式分配
?语言特点：允许递归，允许动态数组，
允许过程嵌套定义
一, 只含半静态变量的栈式分配
1,特点,
?仅允许递归调用
?变量及活动记录长度可静态确定
?一个单元可多次激活而有多个实例,
每个活动记录是在单元每次激活时
动态建立并与代码段建立绑定关系
的
2,处理方法
(1)设置当前栈指针 current,表示当前活动
记录的开始位置
(2)指针 free表示数据存储器下一个可用单元
(3)变量绑定于它在活动记录中的常数位移 i,
变量通过 current变址访问
(4)A调用 B时, 在 A活动记录的栈顶之上建
立起绑定于 B的当前实例的活动记录
(5)从 B返回时, 释放其活动记录
3,动态连接和动态链
?动态连接,A调用 B时, B的活动记
录中保存的 A的活动记录地址
?动态链：由动态连接组成的一个调
用链
A
E
F
G
F
A call E; E call F; F call G; G call F;
..,
..,
..,
..,
..,
4,CALL P 的处理
(1)保存返回地址
D [ free ],= ip + 20
(2)保存主调过程的 current
D [free + 4],= current
(3)建立 P的 current
current,= free
(4)调整 free
free,= free + L
(5)转子
ip,= P的代码段首地址
返回地址
动态连接
返回地址
动态连接
A的活动记录
即将建立的
P的活动记录
current
free
过程 A中调用了 P
返回地址
动态连接
返回地址
动态连接
A的活动记录
P的活动记录
current
free
进入过程 P以后
5,RETURN语句的处理
(1)恢复 free
free,= current
(2)恢复主调过程的 current
current,= D[current + 4]
(3)返回
ip,= D [free]
二, 半静态变量的栈式分配
1,活动记录内容
返回地址
动态链
静态链
保护区
参数单元
局部变量
临时变量
数组存储区
其中，局部变量中包括数组的描述符
2,动态数组空间的分配
(1)编译时, 分配内情向量表区, 并产
生在运行时动态的建立内情向量和
分配数组空间的指令 ;
(2)一个单元激活后 （ 进入该单元 ）,
遇到动态数组说明时, 调用上述指
令 （ 填内情向量, 分配数组空间 ）,
并调整 free,= free + L。
三, 动态变量的存储分配
在堆上进行存储分配
