搜索
1第十章目标程序运行时的存储组织10.1概述（略）10.2数据表示（略）10.3目标程序运行时的栈式存储组织10.4参数传递10.5堆式存储组织的讨论（略）2数据空间的使用方法存储分配策略：静态存储分配栈式动态存储分配堆式动态存储分配栈式存储分配方案基本思想：运行时每当进入一个过程，就在栈顶为该过程分配所需的数据空间，当一个过程工作完毕之后，它在栈顶的数据空间也将被释放。3术语-过程活动记录：AR(ActivationRecord)为说明方便，假定程序是由过程组成，过程区分为源文本，运行时称作过程的激活。一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区（块）叫做一个活动记录或frame桢一般这个段要记录：•临时值，如计算表达式时的中间工作单元。•局部变量（数据）•保存运行过程前的状态（程序计数器，寄存器值……）•存取链（可选）对于非局部量的引用。•控制链（可选）指向调用者的活动记录，释放栈。•实参（形式单元）•返回值（对函数）（有时可使用寄存器存放返回值）•返回地址，保存该被调过程返回后的地址4简单的栈式分配方案•语言结构特点：过程可递归调用，可含可变数据结构，但不允许嵌套定义，没有分程序结构。•例:main全局变量的说明procR……endR;procQ……endQ;主程序执行语句endmain5Main----Q----RMain---Q----QTOP-----R的活动记录Q的活动记录SP------Q的活动记录Q的活动记录主程序全局主程序全局数据区数据区TOP----临时工作单元局部简单变量局部数组的内情向量保存运行过程前的状态（计数器，寄存器值)返回地址实参（形式单元）和参数个数SP-----控制链（老SP）6TOPR的数组区SPR的活动记录Q的活动记录主程序全局数据区7嵌套过程语言的栈式分配方案1、主要特点：•（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。•（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。82、关键技术：解决对非局部变量的引用(存取)也就是说，设法跟踪每个外层过程的最新活动记录AR的位置。3、跟踪办法：1.用静态链（如PL/0的SL）。2.用DISPLAY表。9consta=10;varb,c;procedurep;beginc:=b+a;end;beginread(b);whileb#0dobegincallp;write(2*c);read(b);endend.(0)jmp08转向主程序入口(1)jmp02转向过程p入口(2)int03过程p入口,为过程p开辟空间(3)lod13取变量b的值到栈顶(4)lit010取常数10到栈顶(5)opr02次栈顶与栈顶相加(6)sto14栈顶值送变量c中(7)opr00退栈并返回调用点(16)(8)int05主程序入口开辟5个栈空间(9)opr016从命令行读入值置于栈顶(10)sto03将栈顶值存入变量b中(11)lod03将变量b的值取至栈顶(12)lit00将常数值0进栈(13)opr09次栈顶与栈顶是否不等(14)jpc024等时转(24)（条件不满足转）(15)cal02调用过程p(16)lit02常数值2进栈(17)lod04将变量c的值取至栈顶(18)opr04次栈顶与栈顶相乘(2*c)(19)opr014栈顶值输出至屏幕(20)opr015换行(21)opr016从命令行读取值到栈顶(22)sto03栈顶值送变量b中(23)jmp011无条件转到循环入口(11)(24)opr00结束退栈10目标代码解释执行时数据栈的布局（运行栈的存储分配）每个过程的AR有3个联系单元：–SL：静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。–DL：动态链，指向调用该过程前正在运行过程的数据段基地址。–RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址。局部变量中间结果11目标代码的解释执行运行栈•M调用过程PSRADLSLb..ttbPM12解决对非局部变量的引用（存取）用Display表Display表——嵌套层次显示表当前激活过程的层次为K，它的Display表含有K+1个单元，依次存放着现行层，直接外层…直至最外层的每一过程的最新活动记录的基地址13例：programmain(i,0);程序结构图……procR(c,d);……end/*R*/procP(a);……procQ(b);……end/*Q*/……Q(z);end/*P*/……P（W）；……R（U，V）；……end/*main*/14用Display表的方案(1)主程序---(2)P---(3)Q---(4)R主程序的活动记录d[0]spdisplaytop（1）P的活动记录主程序的活动记录d[1]d[0]displaysptop（2）15用Display表的方案主程序---(2)P---(3)Q---(4)RR的活动记录Q的活动记录P的活动记录主程序的活动记录d[1]d[0]displaytopsp（3）（4）Q的活动记录P的活动记录主程序的活动记录displayd[2]d[1]d[0]sptop16DISPLAY表的维护和建立DISPLAY表d运行栈0主程活动记录地址1R活动记录地址...170老SP1返回地址2全局DISPLAY地址3参数个数4形式单元...dDISPLAY...简单变量数组内情向量临时变量•当过程的层次为n，它的display为n+1个值。•一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。•全局DISPLAY地址18分程序结构ProcedureA(m,n);integerm,n;B1:beginrealz;arrayB[m:n];B2:beginreald,e;L3:end;B4:beginarrayC[1:m];B5:beginreale;L6:end;end;L8:end;19分程序结构的存储分配方案处理分程序结构存储分配方案的一种简单办法是，把分程序看成“无名无参过程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。1）每逢进入一个分程序，就照样建立连接数据和DISPLAY表,这是不必要的。2）当从内层分程序向外层转移时，可能同时要结束若干个分程序。20按照过程处理办法，意味着必须一层一层地通过“返回”来恢复所要到达的那个分程序的数据区，但不能直接到达。例如：如果有一个从第5层分程序转出到达第1层分程序的标号L，虽然在第5层分程序工作时知道L所属的层数，我们极易从DISPLAY中获得第1层分程序的活动记录基址（SP），但是怎么知道第1层分程序进入时的TOP呢？唯一的办法是从5,4,3和2各层顺序退出。但这种办法是很浪费时间的。21为了解决上述问题，可采取两种措施：第一，对每个过程或分程序都建立有自己的栈顶指示器TOP，代替原来仅有过程的栈顶指示器,每个TOP的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作“无参过程”，每个分程序享用包围它的那个最近过程的DISPLAY。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。22：每个过程被当作是0层分程序。而过程体分程序（假定是一个分程序）当作是它所管辖的第1层分程序。这样，每个过程的活动记录所含的内容有：1.过程的TOP值，它指向过程活动记录的栈顶位置。2.连接数据，共四项：（1)老SP值；（2)返回地址；(3)全局DISPAY地址；（4)调用时的栈顶单元地址，老TOP。233.参数个数和形式单元4.DISPAY表。5.过程所辖的各分程序的局部数据单元。对于每个分程序来说，它们包括：（1）分程序的TOP值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的新高度（分程序的TOP值）；（2）分程序的局部变量，数组内情向量和临时工作单元。24变量eB5的TOP数组C的内情向量变量e和dB4的TOPB2的TOP数组B的内情向量变量zKB1的TOPDDISPLAY6形式单元m,n5参数个数：24调用时的栈顶地址（老TOP）3全局DISPLAY地址2返回地址1老SP0过程的TOP，指向活动记录之顶25B的内情向量ZB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(a)(b)(a)到达标号B1处;(b)进入分程序B1;ZTO26数组B数组BedB22的TOPB的内情向量B的内情向量zzB1的TOPB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(c)(d)(c)数组B分配之后；（d）进入分程序B22;27数组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。28参数传递(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为形参（在这里是传值）29(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/*reference*/(11)a:=1;b:=2;(12)swap(a,b);(13)writeln(‘a=‘,a);writeln(‘b=‘,b)(14)end./*swap*/带有过程swap的PASCAL程序30•传地址（变量参数）例如：过程swap(varx,y:integer);swap(a,b）；（a,b为调用时的实参）调用结果a,b的值被改变。•传值（值调用）例如：过程swap(x,y:integer);特点是对形式参数的任何运算不影响实参的值。swap(a,b）；其结果：a,b调用前的值不改变。31传值的实现•1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。•2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。•3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。32procedureswap(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:=temp33传地址的实现把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：1、实在参数是一个名字，或具有左值的表达式——传递左值2、实在参数是无左值的表达式——计算值，放入到一存储单元，传此存储单元地址3、目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用34procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；调用swap(i,a[i])其结果等价于执行下列运算：1.把i和a[i]的地址分别放到x和y相应的单元a1,a22.(t