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

1、第13章 运转时存储空间的组织第一节 程序的存储空间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) 静态变量编译时可以确定活动记录的首地址D

3、和变量的相对位置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 静态分配 可用于静态变量的分配，变量与存储区域的绑定关系在编译时便可建立，并完成存储分配； 不允许递归调用，不允许动态数组，不允许动态类型的数据对象。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 动态衔接和动态链 动态衔接：A调用B时，B的活动记录中保管的A的活动记录地址。 动态链：由动态衔接组成的一个调用链。AEFGF例：A call E; E call F; F call G; G call F;.1.4 CALL P的翻译(1) D f

7、ree := 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. 半动态变量的栈式分配 在活动记录中为变量 i建立描画符； 在活动记录的最后分配变量 i ； 用描画中的指针域指向变量 i 的存储位置。变量区变量 i 的存储区参数区现场维护静态衔接动态衔接前往地址currentfree(1) 编译时创建描画符，并产生在运转时动态修正描画符和创建变量存储空间的指令。(2) 一个单元激活后进入该单元，遇到变量 i 的阐明时，调用上述指令填描画符，分配存储空间，并调整free := free + L。3. 动态变量的存储分配 在活动记录中为

9、变量 i 分配两个指针 在堆上分配动态变量的描画符和存储空间 用活动记录中的两个指针指向上述两个位置变量区前往地址currentfree变量 i 的描述符变量 i 的存储区堆空间 程序单元间通讯方式是经过非部分环境和参数传送来实现的。 对非部分环境的援用必需思索变量的作用域，变量的作用域是指可访问该变量的程序范围。第三节 非部分环境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的地址的求法nB - nA = 0：A和B是同一层A就是BDA = currentnB - nA = 1：A是B的直接外层第1个外层DA Dcu

12、rrent + 2nB - nA = 2：A是B的第2个外层DA = DDcurrent + 2 + 2nB - 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 BBXc

13、all 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 := free 建立新的current(5) free := free +

14、L 调整free(6) ip := P转移到P(4) CALL P的处置 形参和实参形参(Formal Parameter)：被调用单元的参数实参(Actual Parameter) ：调用单元的参数 参数传送的类型传值、传值得结果、传地址第四节 参数传送参数传送实例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 :=

15、 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时。重点留意动态衔接和静态衔接的情况。program A;procedure B;procedure C; call B; end C; call C; end Bprocedure D; cal