第10章目标程序运行时的存储组织

第十章目标程序运行时的存储组织1.概述2.栈式存储分配的实现1)简单的栈式存储分配的实现2)嵌套过程语言的栈式实现3)分程序结构的存储管理3.参数传递4.过程调用、过程进入和过程返回概述任务：编译程序对目标程序运行时的数据空间的组织和管理（设计运行环境和分配存储）如通常栈式存储分配布局可为：目标代码区静态数据区Stackheap运行环境和存储分配设计分析逻辑阶段：在目标代码生成前，作准备实质：关联（Binding）将源程序的文本程序运行动作的实现源文件中的名字N运行时的存储S在语义学中，使用术语environment函数表示env:N→S(N到S的映射)静态文本中运行时动作及为实现其动作的准备（与运行时数据对象的表示有关）过程定义过程名执行过程体过程体控制数据对象的分配，为执行过程体使用源文本中同样的名字目标程序中不同的数据空间因为一个过程可以是递归的，这时同一个名字在不同的时间可能代表不同的存储单元决定存储管理复杂程度的因素——源语言本身1.允许的数据类型的多少2．语言中允许的数据项是静态确定动态确定3．程序结构决定名字的作用域的规则和结构A．段结构B．过程定义不嵌套，只允许过程递归调用C．分程序结构分程序嵌套过程定义嵌套存储分配方案策略：静态存储分配动态存储分配——栈式堆式声明的作用域词法作用域动态作用域例：（1）programdynamic(i,0);(2)varr:real(3)procedureshow;(4)beginwrite(r:5:3)end;(5)procedruesmall;(6)varr:real;(7)beginr:=0.125;showend;(8)begin(9)r:=0.25;(10)show;small;write/n;(11)show;small;write/n;(12)end.lexicalscope0.2500.2500.2500.250dynamicscope0.2500.1250.2500.125术语•静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。•动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。•可变(动态)数组：若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变(动态)数组。•例procedureA(m,n:integer);•beginrealz;•arrayB[m:n];•begin•·•·•·•end;•end;数组内情向量:编译中，将数组的有关信息记录在一些单元中，称为“内情向量”，确定数组，放在符号表中；可变数组，运行时建立相应的内情向量。A[l1:u1,l2:u2,,ln:un]l1u1l2u2::typea（首地址）nC过程活动记录AR:为说明方便，假定程序是由过程组成，过程区分为源文本，运行时称作过程的激活。一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区（块）叫做一个活动记录或frame（帧）一般这个段要记录：临时值，如计算表达式时的中间工作单元。局部变量（数据）保存运行过程前的状态（返回地址，寄存器值……）存取链（可选）对于非局部量的引用。控制链（可选）指向调用者的活动记录，释放栈。实参（形式单元）返回值（对函数）（有时可使用寄存器存放返回值）简单的栈式分配方案•程序结构特点:过程定义不嵌套，过程可递归调用，含可变数组;•例:main•全局变量的说明•procR•……•endR;•procQ•……•endQ;•主程序执行语句•endmainMain----Q----RMain---Q----QTOP-----R的活动记录Q的活动记录SP------Q的活动记录Q的活动记录主程序全局主程序全局数据区数据区TOP----临时工作单元局部简单变量局部数组的内情向量保存运行过程前的状态（返回地址，寄存器值……）实参（形式单元）和参数个数SP-----控制链（老SP）TOPR的数组区SPR的活动记录Q的活动记录主程序全局数据区嵌套过程语言的栈式分配方案主要特点：•（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。•（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。•关键技术：解决对非局部量的引用（存取）。•设法跟踪每个外层过程的最新活动记录AR的位置。•跟踪办法：1.用静态链（如PL/0的SL）。2.用DISPLAY表。例：programmain(i,0);程序结构图……procR(c,d);……Rend/*R*/procP(a);主……procQ(b);……PQcallRR(x,y);end/*Q*/callQ……Q(z);callPend/*P*/……callRP（W）；……R（U，V）；……end/*main*/用Display表的方案(1)主程序---(2)P---(3)Q---(4)RP的活动记录主程序的活动记录d[1]d[0]displaysptop主程序的活动记录d[0]spdisplaytop（1）（2）用Display表的方案•主程序---P---Q---RR的活动记录Q的活动记录P的活动记录主程序的活动记录Q的活动记录P的活动记录主程序的活动记录displayd[2]d[1]d[0]d[1]d[0]displaysptoptopsp（3）（4）DISPLAY表的维护和建立DISPLAY表d运行栈0主程序活动记录地址1R活动记录地址...0老SP1返回地址2全局DISPLAY地址3参数个数4形式单元...dDISPLAY...简单变量数组内情向量临时变量•当过程的层次为n，它的display为n+1个值。•一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。•全局DISPLAY地址ProcedureA(m,n);integerm,n;B1:beginrealz;arrayB[m:n];B2:beginreald,e;L3:2end;B4:beginarrayC[1:m];1B5:beginreale;L6:54end;end;L8:end;分程序结构的存储分配方案处理分程序结构存储分配方案的一种简单办法是，把分程序看成“无参过程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。一则，每逢进入一个分程序，就照样建立连接数据和DISPLAY表,这是不必要的。二则，当从内层分程序向外层转移时，可能同时要结束若干个分程序。按照过程处理办法，意味着必须一层一层地通过“返回”来恢复所要到达的那个分程序的数据区，但不能直接到达。例如：如果有一个从第5层分程序转出到达第1层分程序的标号L，虽然在第5层分程序工作时知道L所属的层数，我们极易从DISPLAY中获得第1层分程序的活动记录基址（SP），但是怎么知道第1层分程序进入时的TOP呢？唯一的办法是从5,4,3和2各层顺序退出。但这种办法是很浪费时间的。为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己的栈顶指示器TOP，代替原来仅有过程的栈顶指示器,每个TOP的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作“无参过程”，每个分程序享用包围它的那个最近过程的DISPLAY。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。每个过程被当作是0层分程序。而过程体分程序（假定是一个分程序）当作是它所管辖的第1层分程序。这样，每个过程的活动记录所含的内容有：1.过程的TOP值，它指向过程活动记录的栈顶位置。2.连接数据，共四项：（1)老SP值；（2)返回地址；(3)全局DISPAY地址；（4)调用时的栈顶单元地址，老TOP。3.参数个数和形式单元4.DISPAY表。5.过程所辖的各分程序的局部数据单元。对于每个分程序来说，它们包括：（1)分程序的TOP值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的新高度（分程序的TOP值）；（2)分程序的局部变量，数组内情向量和临时工作单元。变量eB5的TOP数组C的内情向量变量e和dB4的TOPB2的TOP数组B的内情向量变量zKB1的TOPDDISPLAY6形式单元m,n5参数个数：24调用时的栈顶地址（老TOP）3全局DISPLAY地址2返回地址1老SP0过程的TOP，指向活动记录之顶B的内情向量ZB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据 A的TOPA的TOP∶∶∶∶(a)(b)(a)到达标号B1处;(b)进入分程序B1;BZB1TO数组B数组BedB22的TOPB的内情向量B的内情向量zzB1的TOPB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(c)(d)(c)数组B分配之后；（d）进入分程序B22;数组C数组C数组B数组BC的向量内情eB5的TOPC的内情向量B4的TOPB4的TOPB的内情向量B的内情向量zZB1的TOPB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(e)(f)(e)进入分程序B4分配数组C之后；(f)进入分程序B5。参数传递(1)procedureexchangel(i,j:integer);(2)varx:integer;(3)begin;(4)x:=a[i];a[i]:=a[j];a[j]:=x(5)end;带有非局部变量和形参的PASCAL过程非局变量a[i]和a[j]的值进行交换，i,j为形参（在这里是传值）(1)programreference(input,output);(2)vara,b:integer;(3)procedureswap({var}x,y:integer);(4)vartemp:integer;(5)begin(6)temp:=x;(7)x:=y;(8)y:=temp(9)end;(10)begin(11)a:=1;b:=2;(12)swap(a,b);(13)writeln(‘a=‘,a);writeln(‘b=‘,b)(14)end.带有过程swap的PASCAL程序•传地址（变量参数）例如：过程swap(varx,y:integer);swap(a,b）；（a,b为调用时的实参）调用结果a,b的值被改变。•传值（值调用）特点是对形式参数的任何运算不影响实参的值。例如：过程swap(x,y:integer);swap(a,b）；其结果：a,b调用前的值不改变。传值的实现•1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。•2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。•3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；调用swap(a,b)过程将不会影响a和b的值。其结果等价于执行下列运算：x:=a；y:=b；temp:=x；x:=y；y:=temp传地址的实现（call-by-reference)(call-by-address)(call-by-location)把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：1实在参数是一个名字，或具有左值的表达式----传递左值2实在参数是无左值的表达式----计算值，放入一存储单元，传此存储单元地址3目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用procedureswap(x,y:integer);vartemp:integer;begintemp:=x