运行时存储空间组织课件

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

2、单元的活动记录。 一个程序单元在执行过程中所需要的数据信息、管理信息都是通过它的活动记录来存放的。 一个程序单元的每一次激活，都应在内存中建立相应的活动记录。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 栈式分配 用栈分配活动记录； 各程序单元之间的调用遵循“后进先出模式； 活动记录的建立和撤消也满足“后进先出模式； 分配方法：当一个程序单元被激活时,

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

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

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

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

10、中说明的变量。一、动态作用域规那么1. 静态作用域规那么这是一种最近嵌套规那么，对非局部变量，引用的应是最近的“嵌套外层中说明的变量。例：嵌套的层次假设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就是BnDA = currentnn

12、B - nA = 1：A是B的直接外层第1个外层nDA Dcurrent + 2nnB - nA = 2：A是B的第2个外层nDA = DDcurrent + 2 + 2nnB - nA = 3：A是B的第3个外层nDA = 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-

13、nB=1(4)nX-nB1(1)nX-nB=-1XBcall BBXcall BBcall BX(2)nX-nB=0BXcall 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 :=

14、 free 建立新的current(5) free := free + L 调整free(6) ip := P转移到P(4) CALL P的处理n 形参和实参形参(Formal Parameter)：被调用单元的参数实参(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) 传值得结果双向传递实参的值形参的值形参的结果值实参的结果值运行结果：1 , 21 , 22 , 12 , 1(3) 传地址共用同一数据