第13章运行时存储空间的组织

第13章运行时存储空间的组织第一节程序的存储空间1.代码空间和数据空间1.1程序投入运行的必要条件程序要投入运行，必须在内存中分配一定的存储空间，并将程序装入其中，包括：可运行的代码（代码空间）代码运行的环境（数据空间）1.2代码空间（C）内容：线性存放着目标指令序列。当前执行的指令位置由指令指针ip指示。1.3数据空间（D）内容：变量、常数、控制信息、描述符等。静态分配：在运行前就可确定数据空间的大小,在编译时刻就能进行的存储分配。动态分配：运行时才能进行的存储分配。2.活动记录程序由程序单元（函数、子程序）组成，因此程序的数据空间由相应程序单元的数据空间组成。一个程序单元的数据空间叫做该程序单元的活动记录。一个程序单元在执行过程中所需要的数据信息、管理信息都是通过它的活动记录来存放的。一个程序单元的每一次激活，都应在内存中建立相应的活动记录。2.1活动记录的内容(1)返回地址(2)动态连接(3)静态连接(4)现场保护(5)参数区(6)变量区变量区参数区现场保护静态连接动态连接返回地址2.2活动记录的特点除了变量存储区外，其余部分存储长度编译时可以确定，所以变量i的地址可用下式表示：D+offset(i)其中，D是活动记录的首地址；offset(i)是变量i在活动记录中的位移。2.3变量的类型1)静态变量编译时可以确定活动记录的首地址D和变量的相对位置offset(i)。不管在程序单元的哪一次激活中，变量的存储位置均为：D+offset(i)。2)半静态变量编译时可确定变量i的相对位置offset(i)，单元激活时可确定活动记录的首地址D。则每一次激活，变量对应一个不同的存储位置：D+offset(i)。3)半动态变量编译时不能确定变量i的相对位置offset(i)，但能确定i的存储格式。可在活动记录中为i建立一个描述符，用于记录i在内存中的存储格式，并在描述符中建立一个指针域，用于记录i在运行时的具体存储地址。例：动态数组inta[1..m];intb[1..m][1..n];4)动态变量编译时不能确定变量i的相对位置offset(i)，也不能确定i的存储格式。即描述符需要到运行时才能确定，因此可在活动记录中为i设置两个指针，一个记录运行时描述符的地址，另一个记录运行时i的地址。例：某些语言中类型可变的变量；某些语言中维数可变的数组。4.存储分配模式4.1静态分配可用于静态变量的分配，变量与存储区域的绑定关系在编译时便可建立，并完成存储分配；不允许递归调用，不允许动态数组，不允许动态类型的数据对象。4.2栈式分配用栈分配活动记录；各程序单元之间的调用遵循“后进先出”模式；活动记录的建立和撤消也满足“后进先出”模式；分配方法：当一个程序单元被激活时,在栈顶分配其活动记录；当程序单元退出时，在栈顶将其活动记录撤销。例子：某程序中各程序单元的调用顺序为：……P运行P调用QQ调用R……R退出Q退出P退出……P的活动记录Q的活动记录R的活动记录.........4.3堆分配由于动态变量的首地址、长度、类型等在编译时无法确定，在执行过程中也可能改变，所以不可能在栈上为这样的对象分配存储区。对于这些变量，必须分配在堆上。例如：C中通过malloc分配的变量；某些语言中的动态变量等。4.4存储空间的组织代码静态数据栈堆第二节栈式分配1.半静态变量的栈式分配1.1特点变量及活动记录的长度都可静态确定；一个程序单元可能被多次激活，活动记录是在程序单元激活时动态建立，并与代码段建立联系的。1.2处理方法(1)设置当前栈指针current，表示当前活动记录的开始位置（活动记录首地址D）；(2)指针free表示数据存储器下一个可用单元；(3)变量绑定于它在活动记录中的常数位移i，变量通过current变址访问；(4)A调用B时，在A活动记录的栈顶之上建立B的当前实例的活动记录；(5)从B返回时，释放其活动记录。1.3动态连接和动态链动态连接：A调用B时，B的活动记录中保存的A的活动记录地址。动态链：由动态连接组成的一个调用链。AEFGF例：AcallE;EcallF;FcallG;GcallF;...............1.4CALLP的翻译(1)D[free]:=ip+5（保存返回地址）(2)D[free+1]:=current（保存current）(3)current:=free（建立新的current）(4)free:=free+L（调整free）(5)ip:=P（转移到P）例子：过程A调用过程P返回地址动态连接返回地址动态连接A的活动记录P的活动记录currentfreefreecurrentcurrentcurrent1.5RETURN语句的翻译(1)恢复freefree:=current(2)恢复主调过程的currentcurrent:=D[current+1](3)返回ip:=D[free]返回地址动态连接返回地址动态连接A的活动记录P的活动记录freecurrent过程P退出，返回过程Acurrentfree2.半动态变量的栈式分配在活动记录中为变量i建立描述符；在活动记录的最后分配变量i；用描述中的指针域指向变量i的存储位置。变量区……变量i的存储区参数区现场保护静态连接动态连接返回地址currentfree(1)编译时创建描述符，并产生在运行时动态修改描述符和创建变量存储空间的指令。(2)一个单元激活后（进入该单元），遇到变量i的说明时，调用上述指令（填描述符，分配存储空间），并调整free:=free+L。3.动态变量的存储分配在活动记录中为变量i分配两个指针在堆上分配动态变量的描述符和存储空间用活动记录中的两个指针指向上述两个位置变量区…………返回地址currentfree变量i的描述符变量i的存储区堆空间程序单元间通信方式是通过非局部环境和参数传递来实现的。对非局部环境的引用必须考虑变量的作用域，变量的作用域是指可访问该变量的程序范围。第三节非局部环境1.动态作用域规则这是一种最近活动规则，对非局部变量，引用的应是最近的“调用外层”中说明的变量。例：A-C-F的调用序列，F的直接调用外层为C、C的直接调用外层为A。2.引用方法通过“动态链”找到最近的“调用外层”中说明的变量。一、动态作用域规则1.静态作用域规则这是一种最近嵌套规则，对非局部变量，引用的应是最近的“嵌套外层”中说明的变量。例：嵌套的层次若A是B的直接外层，则B的层次=A的层次+1。A(0)、B(1)、C(2)、D(3)、E(1)、F(2)、G(2)二、静态作用域规则unitA;y:int;unitB;endB;y:int;unitC;endD;endC;…...unitD;………...ABCDEFGendE;z:int;unitF;endG;unitG;x,y:int;…...………...unitE;z:=x+y;endF;………...endA;x:int;ABCDEFG2.引用方法通过“静态链”找到最近的“嵌套外层”中说明的变量。(1)静态连接和静态链静态连接：指向嵌套直接外层的最新活动记录的指针。静态链：各嵌套程序单元的活动记录中，静态连接的序列构成一个静态链。AEFGF例：AcallE;EcallF;FcallG;GcallF;...............假设当前处在栈顶的是单元B的活动记录，单元B中引用了单元A中的变量x。单元A的层次为nA、单元B的层次为nB。要找到变量x的存放地址，即：DA+offset(x)关键是要找到单元A的活动记录DA。(2)非局部变量x的地址的求法nB-nA=0：A和B是同一层（A就是B）DA=currentnB-nA=1：A是B的直接外层（第1个外层）DA＝D[current+2]nB-nA=2：A是B的第2个外层DA=D[D[current+2]+2]nB-nA=3：A是B的第3个外层DA=D[D[D[current+2]＋2]＋2]DA的求法令nB-nA=d，定义函数f(d)，表示从B的活动记录出发，沿静态链搜索d步，可以到达A的活动记录。f(d){if(d=0)thenreturncurrent;elsereturnD[f(d-1)+2];}(3)静态连接的建立（单元X调用单元B时）当前栈顶为X的活动记录，需要建立B的活动记录。(3)nX-nB=1(4)nX-nB1(1)nX-nB=-1XBcallBBXcallBBcallBX(2)nX-nB=0BXcallB……………(1)nX-nB=-1,B的静态连接＝f(0)(2)nX-nB=0,B的静态连接＝f(1)(3)nX-nB=1,B的静态连接＝f(2)(4)nX-nB=d,B的静态连接＝f(d+1)因此，静态连接算法为：D[free+2]=f(d+1)(1)D[free]:=ip+6（保存返回地址）(2)D[free+1]:=current（设置动态链接）(3)D[free+2]:=f(d+1)（设置静态链接）(4)current:=free（建立新的current）(5)free:=free+L（调整free）(6)ip:=P（转移到P）(4)CALLP的处理形参和实参形参(FormalParameter)：被调用单元的参数实参(ActualParameter)：调用单元的参数参数传递的类型传值、传值得结果、传地址第四节参数传递参数传递实例proceduremainbegina,b:integer;a:=1;b:=2;print(a,b);swap(a,b);print(a,b);endprocedureswap(x,y)varx,y:intger;beginprint(x,y);x:=x+y;y:=x-y;x:=x-y;print(x,y)end(1)传值（单向传递）实参的值形参的值运行结果：1,21,22,11,2(2)传值得结果（双向传递）实参的值形参的值形参的结果值实参的结果值运行结果：1,21,22,12,1(3)传地址（共用同一数据单元）实参的地址形参的地址运行结果：1,21,22,12,1注意(3)和(2)的区别，如调用swap(a,a)时的运行结果。习题1.对下列程序，试描述每次调用时活动记录栈的状况，直到C中调用B时。重点注意动态连接和静态连接的情况。programA;procedureB;procedureC;…callB;…endC;…callC;…endBprocedureD;…callB;…endD;…callD;…endA2.下列程序在静态作用域规则或动态作用域规则下会有什么输出？programmain;varr:real;proceduref1;write(r);endf1proceduref2;varr:real;r:=0.125;callf1;endf2r:=0.25;callf1;callf2;write(“\n”);callf1;callf2;write(“\n”);endmain