目标程序运行时的存储组织概论

第十章目标程序运行时的

存储组织

概述栈式存储分配的实现简单的栈式存储分配的实现嵌套过程语言的栈式实现分程序结构的存储管理参数传递过程调用、过程进入和过程返回概述任务：编译程序对目标程序运行时的数据空间的组织和管理（设计运行环境和分配存储）如通常栈式存储分配布局可为：

目标代码区

静态数据区

Stackheap 运行环境和存储分配设计分析逻辑阶段：在目标代码生成前，作准备实质：

关联（Binding）将源程序的文本程序运行动作的实现源文件中的名字N

运行时的存储S在语义学中，使用术语environment函数表示env:N→S(N到S的映射)术语静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。可变(动态)数组：若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变(动态)数组。例procedureA(m,n:integer);beginrealz;arrayB[m:n];begin···end;

end;简单的栈式分分配方案程序结构特点点:过程定义义不嵌套，过过程可递归调调用，含可变变数组;例:main全局变量的说说明procR……endR;procQ……endQ;主程序执行语语句endmain嵌套过程语言言的栈式分分配方案主要特点：（语言）一个个过程可以引引用包围它的的任一外层过过程所定义的的标识符（如如变量，数组组或过程等））。（实现）一个个过程可以引引用它的任一一外层过程的的最新活动记记录中的某些些数据。关键技技术：：解决决对非非局部部量的的引用用（存存取））。设法跟跟踪每每个外外层过过程的的最新新活动动记录录AR的位位置。。跟踪办办法：：1.用用静静态链链（如如PL/0的SL））。2.用用DISPLAY表。。用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活活动记记录地地址...当过程程的层层次为为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)分程程序的的局部部变量量，数数组组内情情向量量和临临时工工作单单元。。BZB1TO

数

组B

数

组Be

dB22的TOPB的

内

情

向

量B的

内

情

向

量

z

zB1的TOPB1的TOPDISPLAYDISPLAY形式单单元m,n2形式单单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(c)(d)(c)数组B分配之之后；；（d）进入入分程程序B22;参数传传递(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;x:=y；y:=tempend；；调用swap(i,a[i])其结果等等价于执执行下列列运算：：1把I和a[i]的的地址分分别放到到x和y相应的的单元a1,a22(temp:=x；)temp的内内容置为为a1所所指单元元中存的的内容3(x:=y;)a1所指单单元的内内容置为为a2所所指单元元值4(y:=temp)a2所所指单元元的内容容置为temp的值(1)swap(x,y)(2)int*x,*y;(3){inttemp;(4)temp=*x;*x=*y;*y=temp;(5)}(6)main()(7){inta=1,b=2;(8)swap(&a,&b);(9)printf(“aisnow%d,bisnow%d\n””,a,b);(10)}在一个值值调用过过程中使使用指针针的C程程序在C程序序中无传传地址所所以用指指针实现现。过程调用用的四元元式序列列Scallid(<arglist>)<arglist><arglist>,E<arglist>EparT1parT2parTncallid,n过程作为为参数传传递三种环境境：词法法环境传递环境境活动环境境programparam(input,output);procedureb(functionh(n:integer):integer);(*)varm:integer;beginm:=3;writeln(h(2))end{b};procedurec;(*)varm:integer;functionf(n:integer):integr;(&)beginf:=m+nend{f};beginm:=0;b(f)end{c}begincend.(1)programparam(input,output);(2)procedureb(functionh(n:integer):integer);(3)beginwriteln(h(2))end{b};(4)procedurec;(5)varm:integer;(6)functionf(n:integer):integr;(7)beginf:=m+nend{f};(8)beginm:=0;b(f)end{c};(9)begin(10)c(11)end图10-27嵌嵌套过程程作为参参数传递递各种数据据对象的的存储分分配数据对象象name名字字，名称称type类类型location内内存地址址value值值component成成分分建立内