《{目标管理}第八章目标程序运行时的存储组织1》由会员分享，可在线阅读，更多相关《{目标管理}第八章目标程序运行时的存储组织1（66页珍藏版）》请在金锄头文库上搜索。
1、第八章目标程序运行时的存储组织,第一节 数据空间的三种不同使用方法和管理方法,第二节 栈式存储分配的实现,第三节 参数传递,第四节 过程调用、过程进入和过程返回,8.1数据空间的三种不同使用方法和管理方法,从逻辑上看，代码生成前，编译程序必须进行目标程序 运行环境的设计和数据空间的分配 数据空间包括：用户定义的各种类型的数据对象（变量 和常量）所需的存储空间，作为保留中间结果和传递参 数的临时工作单元，调用过程时所需的连接单元，组织 输入输出所需的缓冲区 运行时的存储区常常划分成：目标区、静态数据区、栈 区、堆区,图8.1就是一种典型划分：,代码区用以存放目标代码，这是固定长度的，即编译时 能
2、确定的 静态数据区用以存放编译时能确定所占用空间的数据 堆栈区用于可变数据以及管理过程活动的控制信息 编译程序分配目标程序运行时的数据空间的基本依据是 程序语言设计时对程序运行中存储空间的使用和管理办 法的规定 在程序设计语言语义学中，使用environment表示将一个 名字映射到一个存储位置的函数，state表示存储位置到 值的映射，如图8.2所示：,数据空间的使用和管理方法分成三种： 静态存储分配 栈式动态存储分配 堆式动态存储分配,一.静态存储分配 静态存储分配：在编译时能确定目标程序运行中所需的 全部数据空间的大小，编译时安排好目标程序运行时的 全部数据空间，确定每个数据对象的存储位
3、置 如像FORTRAN程序是段结构的，如图8.3所示：,图8.4给出一个FORTRAN77的程序例子：,图8.4,图8.5中描述了该程序中局部变量的静态存储位置：,二.动态存储分配 如果一个程序设计语言允许递归过程、可变数组或允许 用户自由申请和释放空间，那么，就需要采用动态存储 管理技术 三.栈式动态存储分配 这种分配策略是将整个程序的数据空间设计为一个栈,四.堆式动态存储分配 假设程序运行时有一个大的存储空间，每当需要时就从 这片空间中借用一块，不用时再退还，由于借还的时间 先后不一，经一段运行之后，程序运行空间将被划分成 许多块，有些占用，有些空闲。那么当运行程序要求一 块体积为N的空间
4、时，需要决定应该从哪个空闲块得到这 个空间 理论上讲,应该从比N稍大一些的空闲块中取出N个单元， 以便使大的空闲块派更大的用场，但实现难度很大,实际中常常采用的办法：先遇到哪块比N大就从其中取出 N个单元 即使这样，也会发生找不到一块比N大的空闲块，但所有 空闲块总和比N大得多，这时，有的分配管理系统采用废 品回收的办法来应付,8.2栈式存储分配的实现,过程的活动记录AR(Activation Record)：是一段连续的存 储区，用以存放过程的一次执行所需要的信息，这些信 息如图8.6所示：,临时工作单元：如计算表达式过程存放的中间结果 局部变量：一个过程的局部变量 机器状态信息：如程序计数
5、器、寄存器的值 存取链：用以存取非局部变量 控制链：指向调用该过程的那个过程的活动记录 实参：由调用过程向该被调过程提供实参的值(或地址) 返回地址：保存该被调过程返回后的地址,一.简单的栈式存储分配的实现 最简单的程序设计语言结构如图10.7所示：,例如，图8.7的程序结构中，若主程序调用了过程Q，Q 又调用了R,在R进入运行后的存储结构如图10.8(a)所示： 若主程序调用了过程Q，Q递归调用自己，在Q过程第2次 进入运行后的存储结构如图10.8(b)所示： 若主程序先调用过程Q，然后主程序接着调用R，且Q过 程没有调用Q和R，这时Q和R进入运行后的存储结构分 别如图8.8(c)和8.8(
6、d)所示：,常常使用两个指针指示栈最顶端的数据区： SP：总是指向现行过程活动记录的起点 TOP：始终指向已占用的栈顶单元 这种语言若含有可变数组，则其过程活动记录的内容如 图8.9所示：,图8.10表明分配数组区之后的运行栈情况，可以与图 8.8（a）对照：,二.嵌套过程语言的栈式实现 Pascal语言程序结构的特点是允许过程嵌套定义，如图 8.11所示：,图8.11的Pascal程序中过程定义的嵌套情况如下： sort readarray exchange quicksort partition 假如过程sort激活（调用）了过程quicksort，这时存储栈 中的情形如图8.12所示，其
7、中在quicksort过程活动记录 中有一存储单元（用斜线描绘）用以记录过程quicksort 可以引用sort中定义的变量a和x。也就是说，为了解决对 非局部变量的存取问题，必须设法跟踪每个外层过程的 最新活动记录的位置,一种跟踪方法是：在过程活动记录中增设存取链,指向包 含该过程的直接外层过程的最新活动记录的起始位置。 过程活动记录的内容如图8.13（a）所示。图8.12所提 到的情况可用图8.13（b）所示：,因为PL/O的过程是无参过程，PL/O也无动态数组，所以 它的过程活动记录的内容如图8.14所示：,再回到图8.11例子，如果该程序的某次执行顺序为： sortquicksortq
8、uicksortpartition exchange 图8.15给出了进入过程exchange之后运行栈的示意，仅 标明存取链和控制链的值,另一种跟踪方法是：每进入一个过程后，在建立它的活 动记录的同时建立一张嵌套层次显示表display 嵌套层次：指过程定义的层数，始终假定主程序的层数 为0，因此主程序称为0层过程 计数过程的层数用一个计数器Level，初值为0，每遇到过 程说明则增1，过程说明结束则减1 display是一个指针数组d，也可看做是一个小栈，自顶向 下每个单元依次存放着现行层，直接外层，直至最 外层（0层，主程序层）等每一层过程的最新活动记录的 地址,图8.11的程序，假定有
9、如下四种调用情况： （a）sortquicksort （b）sortquicksort quicksort （c） sortquicksort quicksortpartition （d） sort quicksortquicksortpartition exchange 图8.16(a)-(d)分别说明上述四种情形的运行栈和display,display本身的体积在编译时可确定，它作为单独的表分配 存储还是作为活动记录的一部分，比如置于实参的上端（ 如图8.17所示），则取决于编译程序的设计者,当过程P1调用过程P2而进入P2后，P2应如何建立起自己的 display? 当P1调用P2时必须
10、把P0的display地址作为连接数据之一传 给P2 如果P2是一个真实过程，那么P0或者就是P1自身或者既是 P1又是P2的直接外层（图8.18的(a)(b)两种情形），不 论哪一种情形，只要在进入P2后能够知道P1的display就 能知道P0的display，从而可直接构造出P2的display。也 就是说，在这种情况下，只需所P1的display地址作为连 接数据之一传送给P2就能够建立P2的display,如果P2是形式参数，那么调用P2意味着调用P2当前相应的 实在过程 此时的P0应是这个实在过程的直接外层过程 假定P0的display地址可从形式单元P2所指示的地方获得 为了能在
11、P2中获得P0的display地址，必须在P1调用P2时设 法把P1的display地址作为连接数据之一传送给P2 于是连接数据变为三项： （1）老SP值； （2）返回地址； （3）全局display地址 这样，整个活动记录的组织就如图8.17所示,例：有如下示意的Pascal源程序 program main; var a,b,c:integer; procedure X(i,j:integer); var d,e:real; procedure Y; var f,g:real; begin . end;Y procedure Z(k:integer); var h,i,j:real; beg
12、in . end;Z begin . 10:Y; . 11:Z; . end;X begin . X(a,b); . end.main,并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和DISPLAY的内容。 （1）已开始而尚未执行完毕的标号为10的语句。 （2）已开始而尚未执行完毕的标号为11的语句。,解：（1）程序已开始而尚未执行完毕标号为10的语句时，运行栈的内容和Display表的内容如下图所示,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,2
13、2,23,24,全局display,全局display,全局display,display,display,TOP,SP2,SP1,SP0,(2)程序已开始而尚未执行完毕标号为11的语句时，运行栈的内容和Display表的内容如下图所示,全局display,display,display,全局display,全局display,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,TOP,SP2,SP1,SP0,三.分程序结构的存储管理（自习） 一个分程序是一个含有它自己的局部数据（变量）声明 的语句 在C
14、语言中，一个分程序的语法形式是： 声明语句 例如图8.19的C程序中的分程序B0，B1，B2和B3，分程 序的特征是它们的嵌套结构，使用界符标明分程序的开 始和结束，C语言用 ,分程序结构可以用栈式存储分配实现 一种办法是把分程序看成一个“无参过程”，只不过是在 该分程序入口处调用，分程序出口处返回。分程序在哪 里定义就在哪里被调用 另一种办法是每次为一个完整的过程体分配存储，即把 一个过程体中的所有分程序所需的存储一次分配好，如 图8.19的C程序,可以为这里所有声明的名字分配一块存 储，如图8.20所示：,ALGOL的结构特点是除了允许过程嵌套定义还含有分程 序的结构，如图8.21的一个A
15、LGOL过程：,如采用将分程序看成“无参过程”，则效率很低，因为： 第一，分程序不存在被调用的问题，不必要在进入一个 分程序时，将连接数据和display都放进活动记录中 第二，当从内层分程序向外转移时可能同时要结束若干 个分程序，那么怎样恢复所要到达的那个分程序的数据 区呢？ 克服上述缺点的办法是： 首先，代替原来的那个统一的栈顶指示器，让每个过程 和分程序都有自己的栈顶指示器TOP，它的值保存在各 自的活动记录中,其次，不把分程序看作“无参过程”，而让每个分程序享 用包围它的那个最小过程的display 每个过程的活动记录所含的内容有： 1.过程的TOP单元，指向活动记录的栈顶位置 2.连
16、接数据： (1)老SP值 (2)返回地址 (3)全局display地址 (4)调用时的栈顶单元地址，称作老TOP 3.参数个数和形式单元 4.display表,5.过程所管辖的各分程序的局部数据单元对每个分程序来说, 它们包括： (1)一个名为TOP的单元，当进入时它含现行栈顶地址，以后 用来存放栈的新高度 (2)分程序的局部变量、数组内情向量和临时工作单元,图8.22给出了过程A（见图10.21）的活动记录的结构：,下面用一个例子说明进出分程序时数据区的变化过程： 图8.23（a）表示已调用了图10.21的过程A，控制已转入 A中，但尚未开始执行过程体时栈的内容 图8.23（b）反映了已进入过程体分程序（B1），但尚未 分配数组空间时栈的内容。分程序B1的TOP值直接抄自 外层分程序的TOP单元 图8.23（c）反映了分配数组B后的情形，此时B1的TOP 值上升到指示新栈顶，但过程A的TOP值不动 图8.23（d）反映了进入分程序B2之后的情形,进入分程序B4时又抄写B1的TOP,并对数组C进行分配， 于是得到
