第六章 运行时的存储空间
? 运行时存储空间的结构和分配
? 过程活动记录 AR
? 运行时变量的访问
运行时的存储空间结构
? 要保存的信息：
目标代码；数据；库函数代码；数据信息表；
控制信息等
? 运行时的存储空间结构：
目标代码空间
静态区空间
库代码空间
堆区空间
栈区空间
最大地址
最小地址
运行时静态区的分配
? 存储对象的存储位置在程序的整个生命
周期是固定的。
? 分配对象：
全程变量 常量 信息表
? 分配方法：
块地址法,(DataArea,Offset)
变址模式,(Register,Offset)
栈区的存储分配
? 存在递归调用
? 存储对象：
过程中被声明的形参、局部变量 临时变量
? 分配方法：
对每个被调用过程分配一段存储空间,sp存放当前
过程空间的开始地址；对变量 X：（ Level,off),
则其存放地址为 off[sp]。
过程结束时自动释放空间；
? 不能存储：
值的生命周期长于过程的变量；
动态申请空间的变量；
堆区的存储分配
? 可随时分配和释放空间
? 存储对象：
动态申请空间的变量的值
? 释放空间方法：
显示释放：
隐式释放：单指针释放
计数释放法
标记释放法
? 分配空间方法：
最佳符合法；首次优先法；循环首次优先法
运行时的过程活动记录与
栈区的组织结构
? 过程活动记录 (AR):过程的一个现场记录
? 记录内容：
?过程控制信息,先行活动记录的动态链指针、
返回地址、层数和长度等
?机器状态信息,寄存器状态等
?全局变量信息, 非局部变量的信息
?局部变量值,形参变量、局部变量和临时变量
AR的结构：
动态链指针
返回地址
过程层数
机器状态
全局变量环境
返回值
形参变量区
局部变量区
临时变量区
控制状态信息
机器状态信息
全局变量信息
本层变量和返回值
sp
例：
Procedure p(i:integer);
Var y:real; a:array[1..10]of integer;
Begin y:=a[i]*25 end
则过程 p被调用时的活动记录 AR结构如下：
控制信息
机器信息
全局信息
返回值
i
y
a
Offset = 10
Offset = 11
Offset = 13
Offset = 23
sp Offset = 0
动态链
? 调用链, 过程名序列
若 M是主程序名，则（ M） 是一个调用链；
若 ( M,…,R )是调用链，且在 R中有 S的
调用，则（ M,…,R,S） 也是调用链。
记为,CallChain(S)= (M,…,R,S)
? 动态链：
如果有调用链 CallChain(S)=(M,…,R,S)，
则它对应的动态链为：
DynamicChain=[AR(M),…,AR(R),AR(S)]
? 调用过程 Q时,
? 新产生活动记录 NewAR
? 填写 NewAR的内容,
动态链指针,=sp;
填写返回地址、层数、大小和机器状态
? sp:=sp+CurrentAR.Size;
? 转向 Q子程序。
? 退出过程 Q时：
? (R1,R2,...,Rn),= CurrentAR.Machine;
? Value:=CurrentAR.ReturnValue;
? sp:=CurrentAR.DynPointer;,
? 按原 CurrentAR.return返回；
活跃活动记录 (LAR)
? LiveAR（ LAR）,
一个过程 S在动态链中可有多个 AR,但其中只有最
新 AR(S)是可访问的，称此 AR(S)为 S的活跃活动记
录，并记为 LiveAR(S),简写为 LAR（ S）。
? 例,假设有当前调用链是（ M,P1,P2,Q1,R1,R2,R3 )
则当前动态 AR链为：
[AR(M),AR(P1),AR(P2),AR(Q),AR(R1),AR(R2),AR(R3)]
活跃活动记录 LAR为：
LAR( M ) = AR(M) LAR( P ) = AR(P2)
LAR( Q ) = AR(Q1) LAR( R ) = AR(R3)
运行时的变量访问
? 过程声明链 (DeclaChain):过程名序列
（ M） 是过程声明链,M是主程序名；
若 (M,…,P)是过程声明链，且 P中有过程 Q
的声明，则 (M,…,P,Q)也是过程声明链；
记为,DeclaChain(Q)=( M,…,P,Q )
? 当前变量访问环境 VarVisitEnv:
若 DeclaChain(Q)= [M,…,P,Q]则
VarVisitEnv(LAR(Q))=
[LAR(M),…,LAR(P),LAR(Q)]
? 若 (M,…,P,Q)?CallChain(Q)，且 Q的层数为 N，
则有 DeclaChain(Q)= DeclaChain(P)N ? Q
? 设 [AR(M),…,AR(Pi),AR(Qj)]?DynamicChain(Q),且 Q
的层数为 N,则有：
VarVisitEnv(AR(Qj))=VarVisitEnv(AR(Pi))N ?AR(Qj)
PROC P;
… …
Begin
Q
End
PROC P;
Begin
Q
End
… …
PROC Q;
Begin … end
PROC P;
… …
PROC Q
Begin End
… …
Begin Q End
PROC Q;
… …
PROC P;
Begin Q
End
Begin End
? Display表方法
全局表法
局部表法
? 静态链方法
? 寄存器方法
变量访问环境的实现方法
局部 Display表方法
? 对于每个 AR求出其变量访问环境，并把它以
地址表的形式 (Display表）保存在 AR中。因
为每个 AR都自带 Display表，称这种方法为 局
部化 Display表方法。
? 如果层数为 N的过程 P的变量访问环境为：
VarVisitEnv(AR(P))=[ARi1,…,ARi,n+1],
arij表示 ARij的始地址，则
[ari1,…,ari,n+1]是 AR(P)的 Display表,
Display表的求法
? NewAR.Display= CurrentAR.Display的前 N项 ?newsp；
动态链指针
… …
Display表
… …
newsp
动态链指针
… …
Display表
… …
sp
[ar0,ar1,…,arN-1,… ]
[ar0,ar1,…,arN-1,newsp]
例,有过程 M,Q,R,S,其中
level(M)=0;level(Q)=1;level(R)=1;level(S)= 2，
各 AR的 Display表分别如下：
Z单元
ar0
ar1
newsp
X单元
Y单元
AR(M) AR(Q) AR(R)
AR(S)
ar1 ar2ar0
sp
Display
表
Off-
Display
局部 Display表时变量的访问
? 对一个变量 X(L,off),地址为：
当 L= CurrentAR.level时,addr(X)=sp+off
否则,
addr(X)=CurrentAR.Display[L]+ off
静态链方法
? 原 Display表部分变成一个单元，称为静态链
单元，存放静态链指针。
? 静态链指针的确定：
若 NewAR.level= CurrentAR.level+1-k,则
NewAR.StaticChainPointer=Indir(sp,k)
其中 Indir(sp,k)表示 sp的 k次间接内容。
nil
AR(M)
ar0 ar0
AR1
ar1 ar1
AR2
ar2 ar2
CurrentAR
ar3 ar?
NewAR
ar4
sp
使用静态链时变量的访问
? 变量 X(L,off)的地址：
若 L= CurrentAR.Level,则 addr(X)= sp+ off
若 L= CurentAR.Level +1 -k,则
addr(X)= Indir(sp,k)+ off
全局 Display表和寄存器方法
? 设置一个总的 Display表，其长度为最大嵌
套层数（系统确定），其中 Display[i]存放
第 i层最新 AR的指针。 D[i]表示。
? 当层数为 j的过程 Q被调用时：
将旧的 D[j]的内容保存到 NewAR(Q)中：
NewAR(Q).RessumeAddr = D[j];
改写 D[j]的内容,D[j] = NewAR(Q)的地址；
当退出 Q时,恢复原来 D[j]的内容：
D[j] = CurrentAR.ResumeAddr
? 变量 X(L,off)的地址,addr(X)= D[L]+off
全局 Display表方法的实现
D(3)
D(2)
D(1)
AR5(T)
AR4(S)
AR3(R)
AR2(Q)
AR1(P)
sp
全局 Display表
proc P;
proc Q;
begin R end
proc R;
proc S;
begin T end
proc T;
begin end
begin S end
begin Q end
第六章 —— 总结
? 存储结构
? 静态、栈式、堆式存储分配的特点及所
适用的语言。
? AR的结构、内容
? 调用链、动态链、声明链、静态链、变
量访问环境的定义、构造
? 变量访问环境的实现
? 运行时存储空间的结构和分配
? 过程活动记录 AR
? 运行时变量的访问
运行时的存储空间结构
? 要保存的信息：
目标代码；数据；库函数代码；数据信息表；
控制信息等
? 运行时的存储空间结构：
目标代码空间
静态区空间
库代码空间
堆区空间
栈区空间
最大地址
最小地址
运行时静态区的分配
? 存储对象的存储位置在程序的整个生命
周期是固定的。
? 分配对象：
全程变量 常量 信息表
? 分配方法：
块地址法,(DataArea,Offset)
变址模式,(Register,Offset)
栈区的存储分配
? 存在递归调用
? 存储对象：
过程中被声明的形参、局部变量 临时变量
? 分配方法：
对每个被调用过程分配一段存储空间,sp存放当前
过程空间的开始地址；对变量 X：（ Level,off),
则其存放地址为 off[sp]。
过程结束时自动释放空间；
? 不能存储：
值的生命周期长于过程的变量；
动态申请空间的变量；
堆区的存储分配
? 可随时分配和释放空间
? 存储对象：
动态申请空间的变量的值
? 释放空间方法：
显示释放：
隐式释放：单指针释放
计数释放法
标记释放法
? 分配空间方法：
最佳符合法；首次优先法；循环首次优先法
运行时的过程活动记录与
栈区的组织结构
? 过程活动记录 (AR):过程的一个现场记录
? 记录内容：
?过程控制信息,先行活动记录的动态链指针、
返回地址、层数和长度等
?机器状态信息,寄存器状态等
?全局变量信息, 非局部变量的信息
?局部变量值,形参变量、局部变量和临时变量
AR的结构：
动态链指针
返回地址
过程层数
机器状态
全局变量环境
返回值
形参变量区
局部变量区
临时变量区
控制状态信息
机器状态信息
全局变量信息
本层变量和返回值
sp
例：
Procedure p(i:integer);
Var y:real; a:array[1..10]of integer;
Begin y:=a[i]*25 end
则过程 p被调用时的活动记录 AR结构如下：
控制信息
机器信息
全局信息
返回值
i
y
a
Offset = 10
Offset = 11
Offset = 13
Offset = 23
sp Offset = 0
动态链
? 调用链, 过程名序列
若 M是主程序名，则（ M） 是一个调用链；
若 ( M,…,R )是调用链，且在 R中有 S的
调用，则（ M,…,R,S） 也是调用链。
记为,CallChain(S)= (M,…,R,S)
? 动态链：
如果有调用链 CallChain(S)=(M,…,R,S)，
则它对应的动态链为：
DynamicChain=[AR(M),…,AR(R),AR(S)]
? 调用过程 Q时,
? 新产生活动记录 NewAR
? 填写 NewAR的内容,
动态链指针,=sp;
填写返回地址、层数、大小和机器状态
? sp:=sp+CurrentAR.Size;
? 转向 Q子程序。
? 退出过程 Q时：
? (R1,R2,...,Rn),= CurrentAR.Machine;
? Value:=CurrentAR.ReturnValue;
? sp:=CurrentAR.DynPointer;,
? 按原 CurrentAR.return返回；
活跃活动记录 (LAR)
? LiveAR（ LAR）,
一个过程 S在动态链中可有多个 AR,但其中只有最
新 AR(S)是可访问的，称此 AR(S)为 S的活跃活动记
录，并记为 LiveAR(S),简写为 LAR（ S）。
? 例,假设有当前调用链是（ M,P1,P2,Q1,R1,R2,R3 )
则当前动态 AR链为：
[AR(M),AR(P1),AR(P2),AR(Q),AR(R1),AR(R2),AR(R3)]
活跃活动记录 LAR为：
LAR( M ) = AR(M) LAR( P ) = AR(P2)
LAR( Q ) = AR(Q1) LAR( R ) = AR(R3)
运行时的变量访问
? 过程声明链 (DeclaChain):过程名序列
（ M） 是过程声明链,M是主程序名；
若 (M,…,P)是过程声明链，且 P中有过程 Q
的声明，则 (M,…,P,Q)也是过程声明链；
记为,DeclaChain(Q)=( M,…,P,Q )
? 当前变量访问环境 VarVisitEnv:
若 DeclaChain(Q)= [M,…,P,Q]则
VarVisitEnv(LAR(Q))=
[LAR(M),…,LAR(P),LAR(Q)]
? 若 (M,…,P,Q)?CallChain(Q)，且 Q的层数为 N，
则有 DeclaChain(Q)= DeclaChain(P)N ? Q
? 设 [AR(M),…,AR(Pi),AR(Qj)]?DynamicChain(Q),且 Q
的层数为 N,则有：
VarVisitEnv(AR(Qj))=VarVisitEnv(AR(Pi))N ?AR(Qj)
PROC P;
… …
Begin
Q
End
PROC P;
Begin
Q
End
… …
PROC Q;
Begin … end
PROC P;
… …
PROC Q
Begin End
… …
Begin Q End
PROC Q;
… …
PROC P;
Begin Q
End
Begin End
? Display表方法
全局表法
局部表法
? 静态链方法
? 寄存器方法
变量访问环境的实现方法
局部 Display表方法
? 对于每个 AR求出其变量访问环境，并把它以
地址表的形式 (Display表）保存在 AR中。因
为每个 AR都自带 Display表，称这种方法为 局
部化 Display表方法。
? 如果层数为 N的过程 P的变量访问环境为：
VarVisitEnv(AR(P))=[ARi1,…,ARi,n+1],
arij表示 ARij的始地址，则
[ari1,…,ari,n+1]是 AR(P)的 Display表,
Display表的求法
? NewAR.Display= CurrentAR.Display的前 N项 ?newsp；
动态链指针
… …
Display表
… …
newsp
动态链指针
… …
Display表
… …
sp
[ar0,ar1,…,arN-1,… ]
[ar0,ar1,…,arN-1,newsp]
例,有过程 M,Q,R,S,其中
level(M)=0;level(Q)=1;level(R)=1;level(S)= 2，
各 AR的 Display表分别如下：
Z单元
ar0
ar1
newsp
X单元
Y单元
AR(M) AR(Q) AR(R)
AR(S)
ar1 ar2ar0
sp
Display
表
Off-
Display
局部 Display表时变量的访问
? 对一个变量 X(L,off),地址为：
当 L= CurrentAR.level时,addr(X)=sp+off
否则,
addr(X)=CurrentAR.Display[L]+ off
静态链方法
? 原 Display表部分变成一个单元，称为静态链
单元，存放静态链指针。
? 静态链指针的确定：
若 NewAR.level= CurrentAR.level+1-k,则
NewAR.StaticChainPointer=Indir(sp,k)
其中 Indir(sp,k)表示 sp的 k次间接内容。
nil
AR(M)
ar0 ar0
AR1
ar1 ar1
AR2
ar2 ar2
CurrentAR
ar3 ar?
NewAR
ar4
sp
使用静态链时变量的访问
? 变量 X(L,off)的地址：
若 L= CurrentAR.Level,则 addr(X)= sp+ off
若 L= CurentAR.Level +1 -k,则
addr(X)= Indir(sp,k)+ off
全局 Display表和寄存器方法
? 设置一个总的 Display表，其长度为最大嵌
套层数（系统确定），其中 Display[i]存放
第 i层最新 AR的指针。 D[i]表示。
? 当层数为 j的过程 Q被调用时：
将旧的 D[j]的内容保存到 NewAR(Q)中：
NewAR(Q).RessumeAddr = D[j];
改写 D[j]的内容,D[j] = NewAR(Q)的地址；
当退出 Q时,恢复原来 D[j]的内容：
D[j] = CurrentAR.ResumeAddr
? 变量 X(L,off)的地址,addr(X)= D[L]+off
全局 Display表方法的实现
D(3)
D(2)
D(1)
AR5(T)
AR4(S)
AR3(R)
AR2(Q)
AR1(P)
sp
全局 Display表
proc P;
proc Q;
begin R end
proc R;
proc S;
begin T end
proc T;
begin end
begin S end
begin Q end
第六章 —— 总结
? 存储结构
? 静态、栈式、堆式存储分配的特点及所
适用的语言。
? AR的结构、内容
? 调用链、动态链、声明链、静态链、变
量访问环境的定义、构造
? 变量访问环境的实现
