运行时存储空间的组织课件ehxn.pptx

《运行时存储空间的组织课件ehxn.pptx》由会员分享，可在线阅读，更多相关《运行时存储空间的组织课件ehxn.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第13章 运行时存储空间的组织第一节 程序的存储空间1.代码空间和数据空间1.1 程序投入运行的必要条件程序要投入运行，必须在内存中分配一定的存储空间，并将程序装入其中，包括：n 可运行的代码（代码空间）n 代码运行的环境（数据空间）1.2 代码空间（C）内容：线性存放着目标指令序列。当前执行的指令位置由指令指针ip指示。1.3 数据空间（D）内容：变量、常数、控制信息、描述符等。n 静态分配：在运行前就可确定数据空间的大小,在编译时刻就能进行的存储分配。n 动态分配：运行时才能进行的存储分配。2.活动记录程序由程序单元（函数、子程序）组成，因此程序的数据空间由相应程序单元的数据空间组成。n

2、一个程序单元的数据空间叫做该程序单元的活动记录。n 一个程序单元在执行过程中所需要的数据信息、管理信息都是通过它的活动记录来存放的。n 一个程序单元的每一次激活，都应在内存中建立相应的活动记录。2.1 活动记录的内容(1)返回地址(2)动态连接(3)静态连接(4)现场保护(5)参数区(6)变量区变量区变量区变量区参数区现场保护静态连接动态连接返回地址2.2 活动记录的特点除了变量存储区外，其余部分存储长度编译时可以确定，所以变量 i 的地址可用下式表示：D+offset(i)其中，D是活动记录的首地址；offset(i)是变量 i 在活动记录中的位移。2.3 变量的类型1)静态变量编译时可以确

3、定活动记录的首地址D和变量的相对位置offset(i)。不管在程序单元的哪一次激活中，变量的存储位置均为：D+offset(i)。2)半静态变量编译时可确定变量i的相对位置offset(i)，单元激活时可确定活动记录的首地址D。则每一次激活，变量对应一个不同的存储位置：D+offset(i)。3)半动态变量编译时不能确定变量 i 的相对位置offset(i)，但能确定 i 的存储格式。可在活动记录中为 i 建立一个描述符，用于记录 i 在内存中的存储格式，并在描述符中建立一个指针域，用于记录 i 在运行时的具体存储地址。例：动态数组 int a1.m;int b1.m1.n;4)动态变量编译时

4、不能确定变量 i 的相对位置offset(i)，也不能确定 i 的存储格式。即描述符需要到运行时才能确定，因此可在活动记录中为 i 设置两个指针，一个记录运行时描述符的地址，另一个记录运行时 i 的地址。例：某些语言中类型可变的变量；某些语言中维数可变的数组。4.存储分配模式4.1 静态分配n 可用于静态变量的分配，变量与存储区域的绑定关系在编译时便可建立，并完成存储分配；n 不允许递归调用，不允许动态数组，不允许动态类型的数据对象。4.2 栈式分配n 用栈分配活动记录；n 各程序单元之间的调用遵循“后进先出”模式；n 活动记录的建立和撤消也满足“后进先出”模式；n 分配方法：当一个程序单元被

5、激活时,在栈顶分配其活动记录；当程序单元退出时，在栈顶将其活动记录撤销。例子：某程序中各程序单元的调用顺序为：P运行P调用QQ调用RR退出Q退出P退出P的活动记录Q的活动记录R的活动记录.4.3 堆分配由于动态变量的首地址、长度、类型等在编译时无法确定，在执行过程中也可能改变，所以不可能在栈上为这样的对象分配存储区。对于这些变量，必须分配在堆上。例如：C中通过malloc分配的变量；某些语言中的动态变量等。4.4 存储空间的组织代码代码静态数据静态数据栈栈堆堆第二节 栈式分配1.半静态变量的栈式分配1.1 特点n 变量及活动记录的长度都可静态确定；n 一个程序单元可能被多次激活，活动记录是在程

6、序单元激活时动态建立，并与代码段建立联系的。1.2 处理方法(1)设置当前栈指针current，表示当前活动记录的开始位置（活动记录首地址D）；(2)指针free表示数据存储器下一个可用单元；(3)变量绑定于它在活动记录中的常数位移 i，变量通过current变址访问；(4)A调用B时，在A活动记录的栈顶之上建立B的当前实例的活动记录；(5)从B返回时，释放其活动记录。1.3 动态连接和动态链n 动态连接：A调用B时，B的活动记录中保存的A的活动记录地址。n 动态链：由动态连接组成的一个调用链。AEFGF例：例：A call E;E call F;F call G;G call F;.1.4

7、CALL P的翻译(1)D free :=ip+5（保存返回地址）(2)Dfree+1:=current（保存current）(3)current:=free（建立新的current）(4)free:=free+L（调整free）(5)ip:=P（转移到P）例子：过程A调用过程P返回地址动态连接返回地址动态连接A的活动记录P的活动记录currentfreefreecurrentcurrentcurrent1.5 RETURN语句的翻译(1)恢复freefree:=current(2)恢复主调过程的currentcurrent:=Dcurrent+1(3)返回ip:=Dfree返回地址动态连接返

8、回地址动态连接A的活动记录P的活动记录freecurrent过程P退出，返回过程Acurrentfree2.半动态变量的栈式分配n 在活动记录中为变量 i建立描述符；n 在活动记录的最后分配变量 i；n 用描述中的指针域指向变量 i 的存储位置。变量区变量 i 的存储区参数区现场保护静态连接动态连接返回地址currentfree(1)编译时创建描述符，并产生在运行时动态修改描述符和创建变量存储空间的指令。(2)一个单元激活后（进入该单元），遇到变量 i 的说明时，调用上述指令（填描述符，分配存储空间），并调整free:=free+L。3.动态变量的存储分配n 在活动记录中为变量 i 分配两个指

9、针n 在堆上分配动态变量的描述符和存储空间n 用活动记录中的两个指针指向上述两个位置变量区返回地址currentfree变量 i 的描述符变量 i 的存储区堆空间n 程序单元间通信方式是通过非局部环境和参数传递来实现的。n 对非局部环境的引用必须考虑变量的作用域，变量的作用域是指可访问该变量的程序范围。第三节 非局部环境1.动态作用域规则这是一种最近活动规则，对非局部变量，引用的应是最近的“调用外层调用外层”中说明的变量。例：A-C-F的调用序列，F的直接调用外层为C、C的直接调用外层为A。2.引用方法通过“动态链动态链”找到最近的“调用外层调用外层”中说明的变量。一、动态作用域规则1.静态作

10、用域规则这是一种最近嵌套规则，对非局部变量，引用的应是最近的“嵌套外层嵌套外层”中说明的变量。例：嵌套的层次若A是B的直接外层，则B的层次=A的层次+1。A(0)、B(1)、C(2)、D(3)、E(1)、F(2)、G(2)二、静态作用域规则unit A;y:int;unit B;end B;y:int;unit C;end D;end C;.unit D;.ABCDEFGend E;z:int;unit F;end G;unit G;x,y:int;.unit E;z:=x+y;end F;.end A;x:int;ABCDEFG2.引用方法通过“静态链静态链”找到最近的“嵌套外层嵌套外层”中

11、说明的变量。(1)静态连接和静态链静态连接：指向嵌套直接外层嵌套直接外层的最新最新活动记录的指针。静态链：各嵌套程序单元的活动记录中，静态连接的序列构成一个静态链。AEFGF例：例：A call E;E call F;F call G;G call F;.假设当前处在栈顶的是单元B的活动记录，单元B中引用了单元A中的变量x。单元A的层次为nA、单元B的层次为nB。要找到变量x的存放地址，即：DA+offset(x)关键是要找到单元A的活动记录DA。(2)非局部变量x的地址的求法nnB-nA=0：A和B是同一层（A就是B）DA=currentnnB-nA=1：A是B的直接外层（第1个外层）DA

12、Dcurrent+2nnB-nA=2：A是B的第2个外层DA=DDcurrent+2+2nnB-nA=3：A是B的第3个外层DA=DDDcurrent+2 2 2DA的求法令nB-nA=d，定义函数f(d)，表示从B的活动记录出发，沿静态链搜索d步，可以到达A的活动记录。f(d)if(d=0)then return current;else return D f(d-1)+2 ;(3)静态连接的建立（单元X调用单元B时）当前栈顶为X的活动记录，需要建立B的活动记录。(3)nX-nB=1(4)nX-nB1(1)nX-nB=-1XBcall BBXcall BBcall BX(2)nX-nB=0B

13、Xcall B(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)因此，静态连接算法为：Dfree+2=f(d+1)(1)D free :=ip+6（保存返回地址）(2)Dfree+1:=current（设置动态链接）(3)Dfree+2:=f(d+1)（设置静态链接）(4)current:=free（建立新的current）(5)free:=free+L（调整free）(6)ip:=P（转移到P）(4)CALL P的处理n 形参和实参形参(Formal Parameter

14、)：被调用单元的参数实参(Actual Parameter)：调用单元的参数n 参数传递的类型传值、传值得结果、传地址第四节 参数传递参数传递实例procedure main begin a,b:integer;a:=1;b:=2;print(a,b);swap(a,b);print(a,b);endprocedure swap(x,y)var x,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)传值得结果（双向传递）实参的值形参的值形参的结果值实

15、参的结果值运行结果：1,21,22,12,1(3)传地址（共用同一数据单元）实参的地址形参的地址运行结果：1,21,22,12,1注意(3)和(2)的区别，如调用swap(a,a)时的运行结果。习题1.对下列程序，试描述每次调用时活动记录栈的状况，直到C中调用B时。重点注意动态连接和静态连接的情况。program A;procedure B;procedure C;call B;end C;call C;end Bprocedure D;call B;end D;call D;end A2.下列程序在静态作用域规则或动态作用域规则下会有什么输出？program main;var r:real;procedure f1;write(r);end f1procedure f2;var r:real;r:=0.125;call f1;end f2r:=0.25;call f1;call f2;write(“n”);call f1;call f2;write(“n”);end main