第八章 运行时存储空间的组织与管理 目标程序运行时的存储结构 过程活动记录和运行时栈 变量访问环境 是CPU能直接寻址的存储空间

运行时存储空间 运行时存储空间:目标程序运行时需一块存储区，用于容纳指令代码及其运行时所需的数据代码。 数据代码主要包括： 用户定义的各种类型的数据对象（变量和常量）所需的存储空间; 用于保留中间结果和传递参数的临时变量所需存储空间; 调用过程时所需的控制信息; 组织输入/输出所需的缓冲区。

1 目标程序运行时内存的划分 目标程序运行时的存储空间结构 高地址 库代码空间 目标代码空间 静态区空间 堆区空间 栈区空间 高地址 低地址 数据空间 代码空间 库代码区（libaray space）用于存放目标程序运行时用到的库程序代码（如C语言中通过#include包含进来的库代码）； 目标代码(code space)区:用以存放目标代码，目标代码所占空间的大小可以在编译时确定;

栈区（stack space）用于存放过程/函数的局部数据和过程/函数被中断时的中断现场内容； 库代码空间 目标代码空间 静态区空间 堆区空间 栈区空间 高地址 低地址 数据空间 代码空间 静态区(static space) :数据对象占用的空间在编译时确定，其地址可以编译进目标代码中，即静态区用于存放可分配绝对地址的数据和变量（如静态变量和全局变量）； 栈区（stack space）用于存放过程/函数的局部数据和过程/函数被中断时的中断现场内容； 堆区（heap space）：主要用于存放动态申请的数据对象 （如C，pascal ，Lisp等语言的malloc,calloc,free,new,delete）。 当目标代码运行时，栈区指针和堆区指针朝着对方方向不断增长。如果这两个区相交，则表示堆-栈区空间已满。

C程序运行时内存示意图 (assign, 0, _ , sum) 目标代码 (ENTRY, Lsqr, 3+off1, 1) (*,i,i,t1) (assign, t1,_, j ) (RETURN, _, _, j) (ENDFUN, _, _, _) (ENTRY, Lmain, 3+off2, 1) (VALACT, 5, offi, 1) (call, <square>, true,t2) (assign, t2, _, j) (+, sum, j, t3) (assign, t3, _, sum) 目标代码 sum 常量信息表等... main的控制信息 j t2 t3 square的控制信息 i t1 #define n 5 int sum = 0； int square(int i) { int j； j = i * i； return j； } void main() j =square(n)； sum=sum + j；

目标程序运行时的存储分配策略 存储空间使用和管理方法： 静态存储分配策略 动态存储分配策略 栈式动态存储分配策略 堆式动态存储分配策略 静态分配策略：在编译时为数据对象分配固定的存储空间，且存储对象的存储位置在程序的整个生命周期是固定的。 动态存储分配：在编译时无法知道程序在运行时需要的空间，只有在程序运行时才能动态确定。

（1）静态存储分配 尽可能多地对程序进行静态分配，减少目标程序中的地址分配指令，以缩短的运行时间。 完全采用静态分配策略的语言必须满足以下约束条件： 不允许递归过程。 不允许可变体积的数据，即数据对象的长度和它在内存中位置的限制，必须是在编译时可知。 不允许动态建立的数据结构（如动态数组、指针等），因为没有运行时的存储分配机制。

（1）.静态存储分配 FORTRAN 语言可以只采用静态分配策略， pascal,C不能完全采用静态分配策略， Lisp完全采用动态分配策略。 不能完全采用静态分配策略时，静态分配对象 全局变量 C语言中的static变量 常量(const定义的)及一些信息表（如常量表）

（2）栈式动态分配策略 栈式动态分配策略是在运行时把存储器作为一个栈进行管理，每当调用一个过程/函数，它所需的空间就动态地分配于栈顶（称为过程活动记录），一旦退出，它所占用的空间就予以释放。 栈的特点使得栈式分配策略特别适合描述过程的嵌套调用和递归调用。

栈式管理中的过程活动记录 过程活动记录是栈式管理中最重要的内容 栈区中通常需要设立两个指针： sp 指向当前活动记录的起始位置 top指向栈顶最新可分配地址 Sp和top通常保存在寄存器中 堆区 Q活动记录 P活动记录 main活动记录 静态区 目标代码区 库代码区 top sp 栈区 在栈式管理中一个最重要的内容就是过程活动记录。 在栈区中通常要设立两个指针 一个sp是指向当前活动记录的起始位置， top指向第一个可用的存储单元。为什么我们用两个指针呢？ 因为我们的栈区中元素大小是不同的，不同的函数占用的大小不同，如果不用两个指针表示，那么退栈的时候就没办法退栈了，所以我们用两个~~ 通常在实现的时候我们会有两个寄存器专门存sp和top，因为经常有运算，把他放在寄存器里，运算速度比较快，所以从目标机选两个寄存器，专门~~ 从栈式的角度来说我们是这样做的。 多变量共享同一个存储空间 存储空间 10

例.描述过程的嵌套调用和递归调用

情况1：若main调用了过程Q，Q又调用了R，在R进入运行后的存储结构 : TOP R的活动记录 SP Q的活动记录 main的活动记录 静态区 存储空间

TOP Q的活动记录 SP Q的活动记录 main的活动记录 静态区 情况2：若main调用了过程Q，Q递归调用自己，在Q过程第二次进入运行后的存储结构 TOP Q的活动记录 SP Q的活动记录 main的活动记录 静态区 存储空间

TOP R的活动记录 Q的活动记录 SP main的活动记录 静态区 情况3：若main先调用过程Q，在过程Q结束后接着调用R，这时Q和R进入运行后的存储结构 : TOP R的活动记录 Q的活动记录 SP main的活动记录 静态区 存储空间

（3）堆区的存储分配 可随时分配和释放空间 存储对象： 释放空间方法： 动态申请空间的变量的值 new malloc 显式释放： free 隐式释放：当执行的程序退出时，系统会自动回收相应的内存等程序运行中所使用的资源。

2 过程活动记录和运行时栈 过程：本章将把过程和函数这样的程序单元统称为过程。 过程的活动：过程体的一次执行称为该过程的一个活动。 它的生存期是从执行该过程体的第一步操作开始到最后一步操作结束之前的时间。

2.1 过程活动记录 过程的活动记录： 为管理过程的一次活动所需要的信息，目标程序要在栈区中给被调过程分配一段连续的存储空间，以便存放该过程的局部变量值、控制信息和寄存器内容等，称这段连续的存储空间为过程的活动记录，简称活动记录（Activation Record），并记为AR。 存放在栈区的一段连续的存储单元中，由目标程序进行管理。 是过程一次活动的一个现场记录

活动记录AR结构 临时变量区 变量访问环境 返回值 Size 过程层数 top 寄存器状态 sp 本层局部变量 和临时变量 控制状态信息 局部变量区 临时变量区 形参变量区 变量访问环境 过程层数 动态链指针 sp 返回地址 top 寄存器状态 返回值 Size 本层局部变量 和临时变量 控制状态信息

2.2 过程活动记录的申请和释放 遇到过程调用时申请地址，具体来看在遇到(call,<f>,true,t)四元式中间代码时，要生成相应的目标代码。要做的主要工作有： 产生一个新的活动记录，即sp=top，top=top+size 填写过程活动记录的管理信息，返回地址、返回值、寄存器内容、动态链指针等等 转向f的入口地址 释放一个是遇到了return，一个是遇到了过程的结束(ENDFUNC,-,-,-)要做的主要工作有： 恢复现场，将寄存器里的值恢复 释放当前活动记录即top=sp; sp=动态链指针 根据返回地址创建跳转指令 过程活动记录的申请和释放，什么时候申请地址呢，我们从中间代码这一级看吧，~在这个位置生成相应的目标代码，也就说有个call四元式，做什么事儿？ 要填过程记录的管理信息，填sp 填返回地址 寄存器的内容等等，第二个任务是产生一个新的过程活动记录，把top送给sp，top=top+size，当前活动记录的大小在哪找到呢？ 在函数的信息表中找到的，符号表中函数信息表，有一项是函数的大小，拿出来就是我们的size。什么时候释放呢？ 释放有两个地方一个是return； 一个是函数的结束，也是要做这样几项工作，第一是回复现场，所谓回复现场，就是把调用时寄存器中的内容回复回去，大家知道我们这里都保存在过程活动记录里，现在我们就把保存的这些信息存回到寄存器中，第二是我们要把当前的活动记录释放掉，很简单，把top=sp，原来老的sp送给sp，我们还要返回，根据前面的返回地址产生一条跳转指令，返回回去。这样我们就实现了申请释放的过程。

2.2 过程活动记录的申请和释放 调用链：调用链是过程的一个调用序列。CallChain(S)=(M，…，R，S） 动态链：栈中活动记录序列 表示S的调用链，表示当前正在执行的是S的过程体，而M，…，R则是已经开始执行但被中断了的过程。 动态链：栈中活动记录序列 [AR（M),AR（N),…，AR（R),AR（S）]， 称为调用链（M，N ， …，R，S）的动态链，也称控制链。 DynamicChains（S） = [AR（M),AR（N),…，AR（R),AR（S）]

调用链和动态链的示例 program P; var a, x : integer; procedure Q(b: integer); var i: integer; procedure R(u: integer; var v: integer); var c, d: integer; begin if u=1 then R(u+1, v) ...... v:=(a+c)*(b-d); end {R} R(1,x); end {Q} procedure S; var c, i:integer; a:=1; Q(c); end {S} a:=0; S; end. {P} 主程序P  过程 S  过程 Q  过程 R  过程 R 调用链CallChain(R) =(P,S,Q,R,R)

    主程序P 过程 S 过程 Q 过程 R 过程 R 空间申请过程 动态链： ………………………… AR(R) [ AR(P)， AR(S)， AR(Q)，AR(R)，AR(R) ] 动态链（控制链）指针 ←sp ………………………… AR(R) [ AR(P)， AR(S)， AR(Q)，AR(R) ] 动态链（控制链）指针 ←sp ………………………… AR(Q) [ AR(P)， AR(S)， AR(Q) ] 动态链（控制链）指针 ←sp ………………………… AR(S) [ AR(P)， AR(S) ] 动态链（控制链）指针 ←sp ………………………… AR(P) [ AR(P) ] NIL ←sp

    主程序P 过程 S 过程 Q 过程 R 过程 R 空间释放过程 执行下述指令: TOP:=SP SP:=0[SP] ←top ………………………… AR(R) 动态链（控制链）指针 ←top ←sp ………………………… AR(R) 动态链（控制链）指针 ←sp ←top ………………………… AR(Q) 动态链（控制链）指针 ←top ←sp ………………………… AR(S) 动态链（控制链）指针 ←top ←sp ………………………… AR(P) NIL ←top ←sp

变量的地址映射 并列式语言： 相对简单只有0层和1层，可以用两个指针来解决，gp指向全局量的首地址，sp指向当前活动记录的首地址，根据变量的层数来确定是gp+off还是sp+off。 例如int x,y; int f(){ int i; y=x*i; return y; } 下面要考虑的是变量的地址映射的问题，对于一个变量来说如何才能计算出他所对应的存储单元。一种是并列式程序设计语言，他相对来说比较简单，要么是0层要么是1层，我们有两个指针，sp0指向全局量的首地址，sp就是当前的，来了一个变量我们看他是l=0还是l=1；如果是0就是sp0+off 否则就是sp+off，所以并列型的地址映射相对来说比较简单，嵌套型语言的地址映射就复杂一些，抽象地址是l off，如果l等于当前层，那就是说他所对应的变量是处于当前的活动记录中，如果l不等于当前层，那么我们就要找到他所对应的活动记录的首地址+off，那他的首地址怎么着，我们后面会给介绍，我们要构造一个display表，把每一个活动记录要把它活跃的静态外层的首地址都存在display表里，然后找到他所对应的那一层的首地址加上off就可以了~

变量的地址映射 嵌套式语言：相比之下复杂一些 若抽象地址是L,off,如果L等于当前层，则说明他所对应的变量处于当前的活动记录中，如果L不等于当前层，就要找到他所对应的活动记录的首地址，为此要构造一个display表，把每一个活动记录活跃的静态外层的首地址都存起来，然后找到L所对应的那一层的首地址加上off就可以了。 嵌套型语言的地址映射就复杂一些，抽象地址是l off，如果l等于当前层，那就是说他所对应的变量是处于当前的活动记录中，如果l不等于当前层，那么我们就要找到他所对应的活动记录的首地址+off，那他的首地址怎么着，我们后面会给介绍，我们要构造一个display表，把每一个活动记录要把它活跃的静态外层的首地址都存在display表里，然后找到他所对应的那一层的首地址加上off就可以了~