运行时存储空间组织概述

《运行时存储空间组织概述》由会员分享，可在线阅读，更多相关《运行时存储空间组织概述（78页珍藏版）》请在金锄头文库上搜索。

1、第七章 运行时存储空间组织,本章讨论目标程序运行时的活动和运行时的存储组织与管理 本章要点： 过程的活动与参数传递 静态存储分配 简单的栈式存储分配 嵌套过程语言的栈式实现 堆式动态存储分配,过程的活动与参数传递,定义和调用过程（函数）是程序语言的主要特征之一。过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言能力的主要途径。 一个过程一旦定义后，就可以在别的地方调用它。调用与被调用(过程)两者之间的信息往来通过全局量或参数传递。,例如，下面的C语言程序： #include “stdio.h” void showme (int a, int b, int c) printf (“a=

2、%d, b=%d, c=%dn”, a, b, c); main ( ) int x=10, y=20, z=30; showme (z, y, x); ,其中a、b、c称为形式参数(简称形参) 函数调用语句： showme (z, y, x)中的z、y、x则称为实在参数(简称实参)。实参甚至也可以是一个较复杂的表达式而不仅仅只是一个变量。实参和对应的形参在性质上应相容不悖。,过程的活动,一个过程的活动是指该过程的一次执行。 过程的生存期是指从执行该过程体第一步操作到最后一步操作之间的操作程序，包括执行该过程时调用其他过程花费的时间。,形式参数提供了参数替换的手段，在过程调用时可以使用不同的数

3、据作为实在参数来替换形式参数，从而实现了同一个过程可以对不同的实在参数进行相同操作的功能。那么，如何把实在参数传递给相应的形式参数呢？程序语言中参数传递的方式主要有传值(call by value)、传地址(call by reference)和传名(call by name)三种。,参数的传递,1传值 传值是最简单的参数传递方法。所谓传值，就是计算出实在参数的值然后把它传给被调用过程相对应的形式参数，具体过程如下： (1) 把形式参数当作过程的局部变量处理，即在被调用过程中开辟形式参数的存储空间(即形式单元)。 (2) 调用过程计算出实在参数的值，并将该值放入为形式单元开辟的空间中。,(3)

4、 被调用过程执行时就像使用局部变量一样使用这些形式单元。 传值的一个重要特点是对形式参数的任何运算都不影响调用过程实在参数的值，即参数传递后实在参数与对应的形式参数不再发生联系了。,2传地址 所谓传地址，是指把实在参数的地址传递给相应的形式参数所对应的形式单元。如果实在参数是一个变量，则直接将该变量的地址传给相应的形式单元；如果实在参数是常数或表达式，则先计算其值并存放在某一临时单元中，然后将这个临时单元的地址传给相应的形式单元。,被调用过程执行时，对形式参数的任何引用或赋值都被处理成对形式单元的间接访问，即按形式单元中存放的地址转到调用过程中去访问实在参数。 对形式参数的任何运算实际上都是对

5、实在参数的运算，而形式参数只不过起到辅助查找到实在参数的指针的作用。因此，当被调用过程工作完毕返回时，形式单元所指的实在参数单元就保留了运算的结果。,3传名 传名是高级语言ALGOL 60所定义的一种特殊的参数传递方式，其传递参数的方法如下： (1) 过程调用的作用相当于把被调用过程的过程体复制到调用处(替换调用语句)，并将过程体中所有出现的形式参数在文字上替换成相应的实在参数。这种文字上的替换称为宏扩展(Marcro Expansion)。,(2) 被调用过程中的局部名如果与过程调用的实在参数名发生冲突，则在宏扩展前对被调用过程中的这些局部名重新命名以避免重名冲突。 (3) 为表现实在参数的

6、整体性，必要时在替换前把实在参数用括号括起来。 传名这种参数传递方法因其操作过于复杂现在已很少采用。 不同的参数传递方法得到的结果不同，因此，如何选择参数传递的方法将影响语言的语义，这是编译程序在处理参数传递时应引起重视的问题。,运行时存储器的划分,管理过程的活动，过程调用时相关信息存入栈中,存放动态数据,图7-1,静态存储分配,如果在编译时就能够确定一个程序在运行时所需的存储空间大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址，存储空间的这种分配方法叫做静态分配。,FORTRAN语言的特点： 不允许过程有递归性； 每个数据名所需的存储空间大小都是常量(即

7、不允许含可变体积的数据，如可变数组)； 所有数据名的性质是完全确定的(不允许出现在运行时再动态确定其性质的名字)。这些特点确保整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配。,静态存储分配是一种最简单的存储管理。一般而言，适于静态存储分配的语言必须满足以下条件： (1) 数组的上下界必须是常数； (2) 过程调用不允许递归； (3) 不允许采用动态的数据结构(即在程序运行过程中申请和释放的数据结构)。,在编译过程中，给程序中的变量或数组分配存储单元的一般做法是：为每一个变量(或数组)确定一个有序的整数对；其中，第一个整数用来指示数据区(局部数据区或公用区

8、)的编号，第二个整数则用来指明该变量(或数组)所对应的存储起始单元相对于其所在数据区起点的位移(即相对于数据区起点的地址)；并将这一对整数填入符号表相应登记项的信息栏中。至于各数据区的起始地址在编译时可暂不确定，待各程序段全部编译完成之后，再由连接装配程序最终确定，并将各程序段的目标代码组装成一个完整的目标程序。,一个FORTRAN程序段的局部数据区可由图7-2所示的项目组成。其中，隐参数是指过程调用时的连接信息(不在源程序中明显出现)，如调用时的返回地址、调用时寄存器的保护等；形式单元用来存放过程调用时形参与实参结合的实参地址或值。,一个FORTRAN程序段的局部数据区,保存调用此程序段时的

9、返回地址,保存调用段留在寄存器中的相关信息,存放实参的地址或值,图7-2,简单的栈式存储分配,我们首先考虑一种简单程序语言的实现，这种语言没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用，允许过程含有可变数组。例如，C语言除不允许含有可变数组外，就是这样一种语言。C语言的程序结构如下：,全局数据说明 main( ) main中的数据说明 void R( ) R中的数据说明 void Q( ) Q中的数据说明 ,例如，下面计算n！的C语言程序就是一个递归调用的程序，它的执行过程可以用栈来实现。 # include “stdio.h” long factorial (int n) if (

10、n1) return (n*factorial (n1); else return (1); ,main ( ) int num; do scanf (“%d” , ,使用栈式存储分配法意味着程序运行时，每当进入一个过程(或函数)就有一个相应的活动记录累筑于栈顶，此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等；在进入过程和执行过程的可执行语句之前，再把局部数组所需空间累筑于栈顶，从而形成过程工作时的完整数据区。,栈式存储分配与活动记录,注意，每个过程的活动记录的体积在编译时可以静态地确定。但由于允许含有可变数组，所以数组的大小只有在运行时才能知道。因数组区的大小不能

11、预先获知，为了扩充方便，所以只能将数组区累筑于活动记录之上的当前栈顶。当一个过程工作完毕返回时，它在栈顶的数据区(包括活动记录和数组区)也随即不复存在。,对C语言来说，由于其不含可变数组，因而它的活动记录本身包含了局部数组的空间。图73和图74分别给出了C语言和含可变数组的某简单语言程序运行时的数据空间结构，即显示了主程序在调用了过程Q，Q又调用了过程R，且在R投入运行后的存储结构。,图73 C语言程序的存储组织,SP指示器总是指向执行过程活动记录的起点，而TOP指示器则始终指向(已占用)栈顶单元。当进入一个过程时，TOP指向为此过程创建的活动记录的顶端；在分配数组区之后(如果有的话)，TOP

12、又改为指向数组区(从而是该过程整个数据区)的顶端。,图74 含可变数组程序的存储组织,C的活动记录含有以下几个区段(如图75所示)： (1) 连接数据(两项)：老SP值(即前一活动记录的起始地址)和返回地址； (2) 参数个数； (3) 形式单元(存放实在参数的值或地址)； (4) 过程的局部变量(简单变量)、数组的内情向量和临时工作单元。,图75 C过程的活动记录,C语言不允许过程(函数)嵌套，也即不允许一个过程的定义出现在另一个过程的定义之内。因此，C语言的非局部变量仅能出现在源程序头，非局部变量可采用静态存储分配并在编译时确定它们的地址。 由图75可知，过程的每一局部变量或形参在活动记录

13、中的位置都是确定的；也就是说，这些变量或形参所分配的存储单元其地址都是相对于活动记录的基址SP的。因此，变量和形参运行时在栈上的绝对地址是： 绝对地址=活动记录基址(SP)+相对地址,对当前正在执行(即活动)的过程，其任何局部变量或形参X的引用均可表示为变址访问XSP。此处X代表X相对于活动记录基址的偏移量，这个偏移量(即相对数)在编译时可完全确定下来。过程的局部数组的内情向量的相对地址在编译时也同样可完全确定下来，一旦数据空间在过程里获得分配后，对数组元素的引用也就容易用变址的方式进行访问。,过程的执行 1过程调用 过程调用的中间代码序列为： par T1 par T2 par Tn cal

14、l P,n,由于此时TOP是指向被调用过程P之前的栈顶，而P的形式单元和活动记录起点之间的距离是确定的(等于3，参见图75)，因而由调用过程给将要调用的过程P的活动记录(正在形成中)的形式单元传递实参值或实参地址，即每个par Ti (i=1,2,n)可直接翻译成如下指令： (i+3)TOP=Ti /*传递参数值*/ 或 (i+3)TOP=addrTi /*传递参数地址*/,而四元式call P,n则翻译成： 1TOP=SP /*保护现行SP*/ 3TOP=n /*传递参数个数*/ JSR P /*转子指令，转向P过程的第一条指令*/ 过程P调用之前，先构造出P的活动记录部分内容，见图76所示

15、。,图76 过程P调用前先构造P的活动记录部分内容,2过程进入 转入过程P后，首先要做的工作是定义新活动记录的SP，保护返回地址和定义新活动记录的TOP值，即执行下述指令： SP= TOP+1 /*定义新SP*/ 1SP=返回地址 /*保护返回地址*/ TOP=TOP+L /*定义新TOP*/ 其中，L是过程P的活动记录所需的单元数，这个数在编译时可静态地计算出来。,对含可变数组(非C语言)的情况来说，因为过程可含可变数组且所有数组都分配在活动记录的顶上，所以紧接上述指令之后应是对数组进行存储分配的指令(如果含有局部数组)，这些指令是在翻译数组说明时产生的。对每个数组说明，相应的目标指令组将做

16、以下几件工作： (1) 计算各维的上、下限； (2)调用数组空间分配子程序，其参数是各维的上、下限和内情向量单元首地址。,数组空间分配子程序计算并填好内情向量的所有信息，然后在TOP所指的位置之上留出数组所需的空间，并将TOP调整为指向数组区的顶端。 进入过程P后所做的工作如图77所示。 此后，在过程段执行语句的工作过程中，凡引用形式参数、局部变量或数组元素都将以SP为基址进行相对访问。,图77 进入过程P后所做的工作示意,3过程返回 C语言以及其它一些相似的语言含有return(E)形式的返回语句，其中E为表达式。假定E值已计算出来并存放在某临时单元T中，则此时即可将T值传送到某个特定的寄存器中(调用过程将从这个特定的寄存器中获得被调用过程P的结果)。剩下的工作就是恢复SP和TOP为进入过程P之前的原值(即指向调用过程的活动记录及工作空间)，并按返回地址实行无条件转移，