第八章目标程序运行时的存储组织1ppt课件

1、第八章目的程序运转时的存储组织第一节 数据空间的三种不同运用方法和管理方法第二节 栈式存储分配的实现第三节 参数传送第四节 过程调用、过程进入和过程前往8.1数据空间的三种不同运用方法和管理方法从逻辑上看，代码生成前，编译程序必需进展目的程序运转环境的设计和数据空间的分配数据空间包括：用户定义的各种类型的数据对象变量和常量所需的存储空间，作为保管中间结果和传送参数的暂时任务单元，调用过程时所需的衔接单元，组织输入输出所需的缓冲区运转时的存储区经常划分成：目的区、静态数据区、栈区、堆区图8.1就是一种典型划分：代码区用以存放目的代码，这是固定长度的，即编译时能确定的静态数据区用以存放编译时能确定

2、所占用空间的数据堆栈区用于可变数据以及管理过程活动的控制信息编译程序分配目的程序运转时的数据空间的根本根据是程序文语设计时对程序运转中存储空间的运用和管理办法的规定在程序设计言语语义学中，运用environment表示将一个名字映射到一个存储位置的函数，state表示存储位置到值的映射，如图8.2所示：数据空间的运用和管理方法分成三种：静态存储分配栈式动态存储分配堆式动态存储分配一.静态存储分配静态存储分配：在编译时能确定目的程序运转中所需的全部数据空间的大小，编译时安排好目的程序运转时的全部数据空间，确定每个数据对象的存储位置如像FORTRAN程序是段构造的，如图8.3所示：图8.4给出一个

3、FORTRAN77的程序例子：图8.4图8.5中描画了该程序中部分变量的静态存储位置：二.动态存储分配假设一个程序设计言语允许递归过程、可变数组或允许用户自在恳求和释放空间，那么，就需求采用动态存储管理技术三.栈式动态存储分配这种分配战略是将整个程序的数据空间设计为一个栈四.堆式动态存储分配假设程序运转时有一个大的存储空间，每当需求时就从这片空间中借用一块，不用时再退还，由于借还的时间先后不一，经一段运转之后，程序运转空间将被划分成许多块，有些占用，有些空闲。那么当运转程序要求一块体积为N的空间时，需求决议应该从哪个空闲块得到这个空间实际上讲,应该从比N稍大一些的空闲块中取出N个单元，以便使大

4、的空闲块派更大的用场，但实现难度很大实践中经常采用的方法：先遇到哪块比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(d)所示：经常运用两个指针指示栈最顶端的数据区：SP：总是指向现行过程活动记录的起点TOP：一直指向已占用的栈顶单元这种言语假设含有可变数组，那么其过

6、程活动记录的内容如图8.9所示：图8.10阐明分配数组区之后的运转栈情况，可以与图8.8a对照：二.嵌套过程言语的栈式实现Pascal言语程序构造的特点是允许过程嵌套定义，如图8.11所示：图8.11的Pascal程序中过程定义的嵌套情况如下：sort readarray exchange quicksort partition假设过程sort激活调用了过程quicksort，这时存储栈中的情形如图8.12所示，其中在quicksort过程活动记录中有一存储单元用斜线描画用以记录过程quicksort可以援用sort中定义的变量a和x。也就是说，为理处理对非部分变量的存取问题，必需设法跟踪每个

7、外层过程的最新活动记录的位置一种跟踪方法是：在过程活动记录中增设存取链,指向包含该过程的直接外层过程的最新活动记录的起始位置。过程活动记录的内容如图8.13a所示。图8.12所提到的情况可用图8.13b所示：由于PL/O的过程是无参过程，PL/O也无动态数组，所以它的过程活动记录的内容如图8.14所示：再回到图8.11例子，假设该程序的某次执行顺序为：sortquicksortquicksortpartitionexchange图8.15给出了进入过程exchange之后运转栈的表示，仅标明存取链和控制链的值另一种跟踪方法是：每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表di

8、splay嵌套层次：指过程定义的层数，一直假定主程序的层数为0，因此主程序称为0层过程计数过程的层数用一个计数器Level，初值为0，每遇到过程阐明那么增1，过程阐明终了那么减1display是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，直至最外层0层，主程序层等每一层过程的最新活动记录的地址图8.11的程序，假定有如下四种调用情况：asortquicksortbsortquicksort quicksortc sortquicksort quicksortpartitiond sort quicksortquicksortpartition exchang

9、e图8.16(a)-(d)分别阐明上述四种情形的运转栈和displaydisplay本身的体积在编译时可确定，它作为单独的表分配存储还是作为活动记录的一部分，比如置于实参的上端如图8.17所示，那么取决于编译程序的设计者当过程P1调用过程P2而进入P2后，P2应如何建立起本人的display?当P1调用P2时必需把P0的display地址作为衔接数据之一传给P2假设P2是一个真实过程，那么P0或者就是P1本身或者既是P1又是P2的直接外层图8.18的(a)(b)两种情形，不论哪一种情形，只需在进入P2后可以知道P1的display就能知道P0的display，从而可直接构造出P2的displa

10、y。也就是说，在这种情况下，只需所P1的display地址作为连接数据之一传送给P2就可以建立P2的display假设P2是方式参数，那么调用P2意味着调用P2当前相应的真实过程此时的P0应是这个真实过程的直接外层过程假定P0的display地址可从方式单元P2所指示的地方获得为了能在P2中获得P0的display地址，必需在P1调用P2时设法把P1的display地址作为衔接数据之一传送给P2于是衔接数据变为三项：1老SP值；2前往地址；3全局display地址这样，整个活动记录的组织就如图8.17所示例：有如下表示的Pascal源程序program main;var a,b,c:integ

11、er;procedure X(i,j:integer);var d,e:real;procedure Y;var f,g:real;begin .end;Yprocedure Z(k:integer);var h,i,j:real;begin.end;Zbegin.10:Y;.11:Z;.end;Xbegin.X(a,b);.end.main 并知在运转时辰，以过程为单位对程序中的变量进展动态存储分配。当运转主程序而调用过程语句X时，试分别给出以下时辰的运转栈的内容和DISPLAY的内容。1已开场而尚未执行终了的标号为10的语句。2已开场而尚未执行终了的标号为11的语句。临时变量内情向量简单变

12、量display形式单元形参个数全局display返回地址老SPgf1660012返回地址6ed60ji22返回地址0cb a0返回地址0 解：1程序已开场而尚未执行终了标号为10的语句时，运转栈的内容和Display表的内容如以下图所示 0123456789101112131415161718192021222324全局display全局display全局displaydisplaydisplayTOP SP2 SP1 SP0 (2)程序已开场而尚未执行终了标号为11的语句时，运转栈的内容和Display表的内容如以下图所示 jih1660k112返回地址6ed60ji22返回地址0cba0

13、返回地址0全局displaydisplaydisplay全局display全局display012 34 567891011121314151617181920212223242526TOP SP2 SP1 SP0 三.分程序构造的存储管理自习一个分程序是一个含有它本人的部分数据变量声明的语句在C言语中，一个分程序的语法方式是： 声明语句例如图8.19的C程序中的分程序B0，B1，B2和B3，分程序的特征是它们的嵌套构造，运用界符标明分程序的开始和终了，C言语用 分程序构造可以用栈式存储分配实现一种方法是把分程序看成一个“无参过程，只不过是在该分程序入口处调用，分程序出口处前往。分程序在哪里定

14、义就在哪里被调用另一种方法是每次为一个完好的过程体分配存储，即把一个过程体中的一切分程序所需的存储一次分配好，如图8.19的C程序,可以为这里一切声明的名字分配一块存储，如图8.20所示：ALGOL的构造特点是除了允许过程嵌套定义还含有分程序的构造，如图8.21的一个ALGOL过程：如采用将分程序看成“无参过程，那么效率很低，由于：第一，分程序不存在被调用的问题，不用要在进入一个分程序时，将衔接数据和display都放进活动记录中第二，当从内层分程序向外转移时能够同时要终了假设干个分程序，那么怎样恢复所要到达的那个分程序的数据区呢？抑制上述缺陷的方法是：首先，替代原来的那个一致的栈顶指示器，让

15、每个过程和分程序都有本人的栈顶指示器TOP，它的值保管在各自的活动记录中其次，不把分程序看作“无参过程，而让每个分程序享用包围它的那个最小过程的display每个过程的活动记录所含的内容有：1.过程的TOP单元，指向活动记录的栈顶位置2.衔接数据：(1)老SP值(2)前往地址(3)全局display地址(4)调用时的栈顶单元地址，称作老TOP3.参数个数和方式单元4.display表5.过程所管辖的各分程序的部分数据单元对每个分程序来说,它们包括：(1)一个名为TOP的单元，当进入时它含现行栈顶地址，以后用来存放栈的新高度(2)分程序的部分变量、数组内情向量和暂时任务单元图8.22给出了过程A

16、见图10.21的活动记录的构造：下面用一个例子阐明进出分程序时数据区的变化过程：图8.23a表示已调用了图10.21的过程A，控制已转入A中，但尚未开场执行过程体时栈的内容图8.23b反映了已进入过程体分程序B1，但尚未分配数组空间时栈的内容。分程序B1的TOP值直接抄自外层分程序的TOP单元图8.23c反映了分配数组B后的情形，此时B1的TOP值上升到指示新栈顶，但过程A的TOP值不动图8.23d反映了进入分程序B2之后的情形进入分程序B4时又誊写B1的TOP,并对数组C进展分配，于是得到图8.23e当进入分程序B5时，再次誊写直接外层的TOP值，得到图8.23f8.3参数传送把真实参数传送

17、给相应的方式参数方法：传值、传地址、传名、传结果等一.传值值调用将实参计算出它的值，然后把它传给被调过程：1.方式参数当作过程的部分变量处置2.调用过程计算实参的值，并将它们的值放在为方式单元开辟的空间中3.被调用过程执行时，就像运用部分变量一样运用这些方式单元传值的重要特点是对方式参数的任何运算不影响调用过程的活动记录中实参的值经过值调用的过程可以由非部分量或由指针而对调用过程发生影响二.传地址当参数经过援用传送时，也称作传地址，或援用调用调用过程传给被调过程的是指针，指向实参存储位置的指针1.照实参是一个名字，那么名字的地址传送过去2.照实参是一个表达式，比如a+b或2，而没有左值，那么表

18、达式先求值，并存入某一位置，然后该位置的地址传送过去3.被调过程中对方式参数的任何援用和赋值都经过传送到被调过程的指针被处置成间接访问二.传名当参数经过名字传送时，也称作传名调用调用过程传给被调过程的是名字，实参名字替代形参名字1.照实参是一个名字，那么名字直接替代相应的方式参数2.照实参是一个表达式，比如a+b， a+b替代相应的方式参数3.被调过程中对方式参数的任何援用和赋值都经过传送名字到被调过程的指针被处置成间接访问二.传结果调用过程传给被调过程的是指针和值，每个方式参数对应两个单元，一个存实参的地址，一个存实参的值。1.照实参是一个名字，那么名字的地址和值传送过去2.照实参是一个表达

19、式，比如a+b或2，那么表达式先求值，并存入某一位置，然后该位置的地址和值传送过去3.调用终了前，再将执行的结果写到对应的实参单元例： 对于下面程序： Procedure p (x,y,z) ; begin y:=y+1; z:=z+x; end; p begin a:=2; b:=3; p (a+b , a , a) print a end. 假设参数传送的方法分别为 1传值2传地址 3传名4传结果 。 执行时所输出的a分别是什么？1传值.那么将实参的值传送给被调用者 p .程序运转时有假设a的地址为add_a, b的地址为 add_b); 调用者数据区 被调用者数据区 add_a 2 x

20、: 5 add_b 3 y : 2暂时单元T: 5 z : 2程序运转执行了语句“y:=y+1后有: 调用者数据区 被调用者数据区 add_a 2 x : 5 add_b 3 y : 3暂时单元T: 5 z : 2程序运转执行了语句“z:=z+x后有: 调用者数据区 被调用者数据区 add_a 2 x : 5 add_b 3 y : 3暂时单元T: 5 z : 7所以程序输出 2。 2传地址， 那么将真实参数的地址传送给被调用者， p 运转时有 假设a的地址为add_a, b的地址为add_b ); 调用者数据区 被调用者数据区 add_a: 2 x : T add_b: 3 y : add_

21、a 暂时单元T: 5 z : add_a(a + b)的值程序运转执行了语句“y:=y+1后，有:调用者数据区 被调用者数据区 add_a 3 x: T add_b 3 y: add_a 暂时单元T: 5 z: add_a 执行了语句“z:=z+x后有： 调用者数据区 被调用者数据区 add_a 8 x : T add_b 3 y : add_a 暂时单元T: 5 z : add_a所以程序输出 8。 解： 3传名 当执行调用p ( a+b, a ,a)时，相当于被调用者被交换成 procedure p (a+b , a , a) begin a:=a+1 a:=a+a+b end; p 调用

22、者的数据区为： a: 2 b: 3 执行语句“a:=a+1后，调用者数据区为： a: 3 b: 3执行语句：a:=a+a+b 后，调用者的数据区为： a: 9 b: 3 因此程序输出为9。2传结果， 那么将真实参数的地址和值传送给被调用者， p 运转时有 假设a的地址为add_a, b的地址为add_b，暂时单元T的地址为add_T); 调用者数据区 被调用者数据区 add_a: 2 x : T 5 add_b: 3 y : add_a 2暂时单元T: 5 z : add_a(a + b)的值 2程序运转执行了语句“y:=y+1后，有:调用者数据区 被调用者数据区 add_a: 2 x : T

23、 5 add_b: 3 y : add_a 3暂时单元T: 5 z : add_a 2 执行了语句“z:=z+x后有： 调用者数据区 被调用者数据区 add_a: 2 x : T 5 add_b: 3 y : add_a 3暂时单元T: 5 z : add_a 7调用终了前，被调用者数据存放到对应的调用者数据单元即：调用者数据区 被调用者数据区 add_a: 7 x : T 5 add_b: 3 y : add_a 3暂时单元T: 5 z : add_a 7所以程序输出 7。8.4过程调用、过程进入和过程前往对于过程调用的四元式序列：par T1par T2par Tncall P,n在运转时

24、是如何执行的？/par和call产生什么相应的目的代码对于par Tii=1,2,n)的处置是：根据par Tii=1,2,n)中Ti的种别而生成传送指令，或将参数的值或将参数的地址传送至新的过程的活动记录的方式单元中此节自习对于call p,n那么应生成传送参数个数n的指令；维护现行SP至新过程的活动记录老SP；转子，转向P的第一条指令；定义新SP；维护前往地址；定义新值；填写display或存取链内容等指令假设过程含动态数组部分，那么应生成对数组进展存储分配的指令，即生成运转时动态地建立内情向量和分配数组空间的目的指令在过程执行语句的任务过程中，凡援用形参、部分变量或数组元素都可根据过程活动记录起点的相对位置访问当过程P任务终了要前往到调用段时，假设言语有形如returnE的前往语句，或P是个函数过程时，那么可把已算好的值传送至某个特定的存放器中，调用段将从这个特定的寄存器中获得被调过程的结果值。然后所生成的目的指令那么应完成的任务是：恢复SP；恢复TOP，按保管的前往地址实行无条件转移【本章小结】目的代码运转时，存储区域的整体规划,以及各区域的作用各种不同数据变量区的不同分配组织方式允许过程嵌套定义的言语，栈式动态