1、第八章 运行时存储空间组织 8.1 静态存储分配静态存储分配 8.2 简单的栈式存储分配简单的栈式存储分配 8.3 嵌套过程语言的栈式实现嵌套过程语言的栈式实现 8.4 堆式动态存储分配堆式动态存储分配 第八章 运行时存储空间组织第九章 运行时存储空间组织 编译程序在完成词法、语法和语义分析后，在编译程序在完成词法、语法和语义分析后，在生成目标代码之前，需要把程序的静态正文和实现生成目标代码之前，需要把程序的静态正文和实现这个程序的运行时的活动联系起来这个程序的运行时的活动联系起来,弄清楚将来在代弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定码运行时刻，源代码中的各种变量、常量等用
2、户定义的量是如何存放的，如何去访问它们。义的量是如何存放的，如何去访问它们。 在程序的执行过程中，程序中数据的存取是通在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。在程序语言中，过与之对应的存储单元来进行的。在程序语言中，程序使用的存储单元都是由标识符来表示的。它们程序使用的存储单元都是由标识符来表示的。它们对应的内存地址都是由编译程序在编译时或由其生对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。所以对于编译程序成的目标程序运行时进行分配。所以对于编译程序来说存储组织与管理是一个复杂而又十分重要的问来说存储组织与管理是一个复杂而又十分重要的问题
3、。题。变量及存储空间管理变量及存储空间管理一、一、 目标程序运行时的活动目标程序运行时的活动 一个过程的一个过程的活动活动指的是该过程的一次执行。即每指的是该过程的一次执行。即每次执行一个过程体，就产生该过程的一个活动。次执行一个过程体，就产生该过程的一个活动。 过程过程P P的一个的一个活动的生存期活动的生存期，指的是从执行该过程，指的是从执行该过程体第一步操作到最后一步操作之间的操作序列，包括执体第一步操作到最后一步操作之间的操作序列，包括执行行P P时调用其他过程花费的时间。时调用其他过程花费的时间。一个说明在程序里能起作用的范围称为该说明的一个说明在程序里能起作用的范围称为该说明的作用
4、域作用域。二、二、 活动记录活动记录 为了管理过程在一次执行中所需要的信息，使用一为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，我们把这样的一个连续存储块称为个连续的存储块，我们把这样的一个连续存储块称为活动记录活动记录AR。当前活动记录一般包括如下内容：当前活动记录一般包括如下内容： . 返回地址：返回地址：保存该被调过程返回后的地址。保存该被调过程返回后的地址。 . 动态链（也称控制链或老动态链（也称控制链或老SP）:指向调用该过程的那指向调用该过程的那个过程的活动记录地址。个过程的活动记录地址。 . 静态链（或称存取链）：静态链（或称存取链）：用以存取非局部变量，这些用以存
5、取非局部变量，这些变量存放于其它过程活动记录中。变量存放于其它过程活动记录中。 .形式单元：形式单元：存放相应的实在参数的地址或值。存放相应的实在参数的地址或值。 .局部数据区：局部数据区：局部变量、内情向量、临时工作单元局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）。如图（如存放对表达式求值的结果）。如图三、存储分配模式三、存储分配模式 不同的编译程序关于数据空间的存储分配策略可能不同的编译程序关于数据空间的存储分配策略可能不同。存储分配可采取三种形式：不同。存储分配可采取三种形式：1、静态分配、静态分配 在编译时对所有对象分配固定的存储单元。在编译时对所有对象分配固定的存储单
6、元。且在运行时保持不变。且在运行时保持不变。2、栈式动态分配、栈式动态分配 在运行时把存储器作为一个栈进行管在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空理，运行时，每当调用一个过程，它所需要的存储空间就动态的分配于栈顶，一旦退出，它所占空间就予间就动态的分配于栈顶，一旦退出，它所占空间就予以释放。以释放。3、堆式动态存储、堆式动态存储 在运行时把存储器组织成堆结构，以在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请便用户关于存储空间的申请与归还（回收），凡申请者分给一块，凡释放者退回给堆。者分给一块，凡释放者退回给堆。8.1 静态
7、存储分配 如果在编译时就能够确定一个程序在运行时所需的存储空间大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址，存储空间的这种分配方法叫做静态分配。第八章 运行时存储空间组织 静态存储分配是一种最简单的存储管理。一般而言，适于静态存储分配的语言必须满足以下条件： (1) 数组的上下界必须是常数； (2) 过程调用不允许递归； (3) 不允许采用动态的数据结构(即在程序运行过程中申请和释放的数据结构)。第八章 运行时存储空间组织 满足这些条件的语言有FORTRAN，还有BASIC等语言。在这些语言中，编译程序可以完全确定程序中数据项所在的地址(通常为相对于各
8、数据区起始地址的位移量)。由于过程调用不允许递归，因此数据项的存储地址就与过程相联系。过程调用所使用的局部数据区可以直接安排在过程的目标代码之后，并把各数据项的存储地址填入相关的目标代码中，以便在过程运行时访问这个局部数据区。在此，不存在对存储区的再利用问题；目标程序执行时不必进行运行时的存储空间管理，过程的进入和退出变得极为简单。 第八章 运行时存储空间组织8.2 简单的栈式存储分配 我们首先考虑一种简单程序语言的实现，这种语言没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用，允许过程含有可变数组。例如，C语言除不允许含有可变数组外，就是这样一种语言。C语言的程序结构如下：第八章 运
9、行时存储空间组织 全局数据说明 main() main中的数据说明 void R() R中的数据说明 第八章 运行时存储空间组织 void Q( ) Q中的数据说明 第八章 运行时存储空间组织 例如，下面计算n！的C语言程序就是一个递归调用的程序，它的执行过程可以用栈来实现。 # include “stdio.h” long factorial (int n) if (n1) return (n*factorial (n1); else return (1); 第八章 运行时存储空间组织 main () int num; do scanf (“%d” , &num); if (num=0 &
10、num =0); 第八章 运行时存储空间组织 8.2.1 栈式存储分配与活动记录 使用栈式存储分配法意味着程序运行时，每当进入一个过程(或函数)就有一个相应的活动记录累筑于栈顶，此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等； 在进入过程和执行过程的可执行语句之前，再把局部数组所需空间累筑于栈顶，从而形成过程工作时的完整数据区。第八章 运行时存储空间组织 注意，每个过程的活动记录的体积在编译时可以静态地确定。但由于允许含有可变数组，所以数组的大小只有在运行时才能知道。因数组区的大小不能预先获知，为了扩充方便，所以只能将数组区累筑于活动记录之上的当前栈顶。当一个过程工
11、作完毕返回时，它在栈顶的数据区(包括活动记录和数组区)也随即不复存在。第八章 运行时存储空间组织 对C语言来说，由于其不含可变数组，因而它的活动记录本身包含了局部数组的空间。图82和图83分别给出了C语言和含可变数组的某简单语言程序运行时的数据空间结构，即显示了主程序在调用了过程Q，Q又调用了过程R，且在R投入运行后的存储结构。 SP指示器总是指向执行过程活动记录的起点，而TOP指示器则始终指向(已占用)栈顶单元。当进入一个过程时，TOP指向为此过程创建的活动记录的顶端；在分配数组区之后(如果有的话)，TOP又改为指向数组区(从而是该过程整个数据区)的顶端。第八章 运行时存储空间组织SPTOP
12、R的活动记录Q的活动记录main的活动记录全局数据区第八章 运行时存储空间组织R的数组区R的活动记录Q的数组区Q的活动记录主程序全局数据区TOPSP第八章 运行时存储空间组织 C的活动记录含有以下几个区段(如图84所示)： (1) 连接数据(两项)：老SP值(即前一活动记录的起始地址)和返回地址； (2) 参数个数； (3) 形式单元(存放实在参数的值或地址)； (4) 过程的局部变量(简单变量)、数组的内情向量和临时工作单元。第八章 运行时存储空间组织1TOP临时工作单元内情向量简单变量形式单元参数个数返回地址老SPSP20第八章 运行时存储空间组织 C语言不允许过程(函数)嵌套，也即不允许
13、一个过程的定义出现在另一个过程的定义之内。因此，C语言的非局部变量仅能出现在源程序头，非局部变量可采用静态存储分配并在编译时确定它们的地址。 由图84可知，过程的每一局部变量或形参在活动记录中的位置都是确定的；也就是说，这些变量或形参所分配的存储单元其地址都是相对于活动记录的基址SP的。因此，变量和形参运行时在栈上的绝对地址是： 绝对地址=活动记录基址(SP)+相对地址第八章 运行时存储空间组织 于是，对当前正在执行(即活动)的过程，其任何局部变量或形参X的引用均可表示为变址访问XSP。此处X代表X相对于活动记录基址的偏移量，这个偏移量(即相对数)在编译时可完全确定下来。过程的局部数组的内情向
14、量的相对地址在编译时也同样可完全确定下来，一旦数据空间在过程里获得分配后，对数组元素的引用也就容易用变址的方式进行访问。第八章 运行时存储空间组织 6.2.2 过程的执行 1过程调用 过程调用的四元式序列为： par T1 par T2 par Tn call P,n第八章 运行时存储空间组织 由于此时TOP是指向被调用过程P之前的栈顶，而P的形式单元和活动记录起点之间的距离是确定的(等于3，参见图84)，因而由调用者过程给将要调用的过程P的活动记录(正在形成中)的形式单元传递实参值或实参地址，即每个par Ti (i=1,2,n)可直接翻译成如下指令： (i+3)TOP=Ti /*传递参 或
15、 (i+3)TOP=addrTi /*传递参数地址*/第八章 运行时存储空间组织 而四元式call P,n则翻译成： 1TOP=SP /*保护现行SP*/ 3TOP=n /*传递参数个数*/ JSR P /*转子指令，转向P过 程的第 一条指令*/ 过程P调用之前，先构造出P的活动记录部分内容，见图85所示。第八章 运行时存储空间组织参数个数nTOP3SPT2T1现行SP值P的活动记录调用过程TOP43210第八章 运行时存储空间组织 2过程进入 转入过程P后，首先要做的工作是定义新活动记录的SP，保护返回地址和定义新活动记录的TOP值，即执行下述指令： SP= TOP+1 /*定义新SP*/
16、 1SP=返回地址 /*保护返回地址*/ TOP=TOP+L /*定义新TOP*/ 其中，L是过程P的活动记录所需的单元数，这个数在编译时可静态地计算出来。第八章 运行时存储空间组织 对含可变数组(非C语言)的情况来说，因为过程可含可变数组且所有数组都分配在活动记录的顶上，所以紧接上述指令之后应是对数组进行存储分配的指令(如果含有局部数组)，这些指令是在翻译数组说明时产生的。对每个数组说明，相应的目标指令组将做以下几件工作： (1) 计算各维的上、下限； (2) 调用数组空间分配子程序，其参数是各维的上、下限和内情向量单元首地址。第八章 运行时存储空间组织 数组空间分配子程序计算并填好内情向量
17、的所有信息，然后在TOP所指的位置之上留出数组所需的空间，并将TOP调整为指向数组区的顶端。进入过程P后所做的工作如图86所示。 此后，在过程段执行语句的工作过程中，凡引用形式参数、局部变量或数组元素都将以SP为基址进行相对访问。第八章 运行时存储空间组织P 的数组区返回地址P的活动记录(长度为L)1调用过程SPTOP0第八章 运行时存储空间组织 3过程返回 C语言以及其它一些相似的语言含有return(E)形式的返回语句，其中E为表达式。假定E值已计算出来并存放在某临时单元T中，则此时即可将T值传送到某个特定的寄存器中(调用过程将从这个特定的寄存器中获得被调用过程P的结果)。剩下的工作就是恢
18、复SP和TOP为进入过程P之前的原值(即指向调用过程的活动记录及工作空间)，并按返回地址实行无条件转移，即执行下述指令序列： 第八章 运行时存储空间组织 TOP= SP1 /*恢复调用过程的TOP值*/ SP=0SP /*恢复调用过程的SP值*/ X=2TOP /*将返回地址送X*/ UJ 0X /*无条件转移，即按X的地址返回到调用过程*/ 一个过程也可通过它的end语句(对C语言则是该过程(函数)体结束时的“”)自动返回。如果此过程是一个函数过程，则按上述办法传递结果值，否则仅直接执行上述返回指令序列。过程P的返回示意如图87所示。第八章 运行时存储空间组织SPTOP返回地址老SPP空间调
19、用过程空间第八章 运行时存储空间组织例题与习题解答例题与习题解答1 对于下面程序：对于下面程序： 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） 传值传值 执行时所输出的执行时所输出的a分别是什么？分别是什么？ 解：解： （1）参数传递方法为：传名）参数传递方法为：传名 当执行调用当执行调用p ( a+b, a ,a)时，相当于被调用者被替换成时，相当于被
20、调用者被替换成 procedure p (a+b , a , a) begin a:=a+1 a:=a+a+b end; p 调用者的数据区为：调用者的数据区为： a: 2 b: 3 执行语句执行语句“a:=a+1”后，调用者数据区为：后，调用者数据区为： a: 3 b: 3 执行语句：执行语句：a:=a+a+b 后，调用者的数据区为：后，调用者的数据区为： a: 9 b: 3 因此程序输出为因此程序输出为9。 （2）设参数传递方法为：传地址，）设参数传递方法为：传地址， 则将实在参数的地则将实在参数的地址，传递给调用者址，传递给调用者 p 运行时有（运行时有（ 假设假设a的地址为的地址为ad
21、d_a, b的地址为的地址为add_b ); 调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a: 2 x : T add_b: 3 y : add_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 a
22、dd_b 3 y : add_a 临时单元临时单元T: 5 z : add_a所以程序输出所以程序输出 8。 （3）参数传递方法为：）参数传递方法为： 传值传值.则将实参的值传递给被调则将实参的值传递给被调用者用者 p .程序运行时有（假设程序运行时有（假设a的地址为的地址为add_a, b的地址的地址为为 add_b); 调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_a 2 x : 5 add_b 3 y : 2临时单元临时单元T: 5 z : 2程序运行执行了语句程序运行执行了语句“y:=y+1”后有后有: 调用者数据区调用者数据区 被调用者数据区被调用者数据区 add_
23、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。6.3 嵌套过程语言的栈式实现 在简单程序语言实现中是允许过程的递归调用的，并且过程中可含有可变数组。现在，我们再加上一种功能，即允许过程的嵌套性。从结构上看，PASCAL就是这样的一种语言；但由于PASCAL含有“文件”和“动态变量”，因此，它的存储分配不能简单地用栈式方法来
24、实现。采用PASCAL的一个子集，例如去掉“文件”和“动态变量”这种数据类型，那就可以用我们下面将要讨论的方法实现存储分配。第八章 运行时存储空间组织 6.3.1 嵌套层次显示表(DISPLAY)和活动记录 在讨论中，常常要用到过程定义的“嵌套层次”(简称层数)这个概念。我们始终假定主程序的层数为0，因此主程序称为第0层过程。如果过程Q是在层数为i的过程P内定义的，并且P是包围Q的最小过程，则Q的层数就为i+1。当编译程序处理过程说明时，过程的层数将作为过程名的一个重要属性登记在符号表中。第八章 运行时存储空间组织 由于过程定义是嵌套的，因而一个过程可以引用包围它的任一外层过程所定义的变量或数
25、组。也就是说，运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运行时必须知道它的所有外层的最新活动记录的地址。由于允许递归和可变数组的存在，过程的活动记录位置(即使是相对位置)也往往是变迁的，因而必须设法跟踪每个外层过程的最新活动记录的位置。第八章 运行时存储空间组织 一种常用的跟踪每个外层过程最新活动记录位置的有效办法是，每进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表DISPLAY。假定现在进入的过程层数为i，则它的DISPLAY表含有i+1个单元。此表本身是一个小栈，自顶而下每个单元依次存放着现行层、直接外层直至最外层(第0层，即主程
26、序层)的每一层的最新活动记录的起始地址。例如，令过程R的外层为Q，Q的外层为主程序P，则过程R运行时的DISPLAY表内容如表8.1所示。 第八章 运行时存储空间组织第八章 运行时存储空间组织 由于过程的层数可静态确定，因此每个过程的DISPLAY表的体积在编译时即可知道。为了便于组织存储区和简化处理手续，我们把DISPLAY作为活动记录的一部分置于形式单元的上端，如图88所示。第八章 运行时存储空间组织 由于每个过程的形式单元数目在编译时是知道的，因此DISPLAY的相对地址d(相对于活动记录的起点)在编译时也是完全确定的。被调用过程为了建立自己的DISPLAY，就必须知道它的直系外层过程的
27、DISPLAY，这意味着必须把直系外层的DISPLAY地址作为连接数据之一(称为“全局DISPLAY地址”)传送给被调用过程。于是，此时的连接数据包含老SP值、返回地址和全局DISPLAY地址这三项内容。整个活动记录的结构如图88所示。第八章 运行时存储空间组织连接数据临时变量内情向量简单变量dDISPLAY 表形式单元3参数个数2全局 DISPLAY 地址1返回地址0老SPTOPSPd个单元k第k层SP2最外层过程SP1主程序SP第八章 运行时存储空间组织 6.3.2 嵌套过程的执行 1过程调用 过程调用所做的工作与简单栈式存储分配大体相同，只是增加了一个连接数据，所以每个par Ti 相应
28、的指令应改为： (i+4)TOP=Ti 或者 (i+4)TOP=addrTi 第八章 运行时存储空间组织 call P,n所对应的指令应为： 1TOP=SP /*保护现行SP*/ 3TOP=SP+d /*将直接外层的DISPLAY始址作为P的全局DISPLAY地址*/ 4TOP=n /*传递参数个数*/ JSR P /*转向P的第一条指令*/第八章 运行时存储空间组织 2过程进入 转入过程P后，首先执行和简单栈式存储分配相同的指令： SP= TOP+1 /*定义新的SP*/ 1SP=返回地址 /*保护返回地址*/ TOP=TOP+L /*定义新的TOP*/ 其次，应按第三项连接数据所提供的全局
29、DISPLAY地址，自底而上地抄录k个单元内容(k为P的层次)，最后再添上新的SP值形成现行过程P的DISPLAY(共k+1个单元)。其过程如图89所示。第八章 运行时存储空间组织4参数个数n3全局 DISPLAY 地址21调用过程的SPd调用过程空间P过程空间SPTOP定义新的SP;定义新的TOP;按全局DISPLAY地址复制DISPLAY表至P的活动记录;DISPLAY表第八章 运行时存储空间组织 3过程返回 当过程P工作完毕要返回到调用段时，若return语句含有返回值或P是函数过程，则把已算好的值传送到某个特定的寄存器，然后执行： TOP= SP1 /*恢复调用过程的TOP值*/ SP
30、=0SP /*恢复调用过程的SP值*/ X=2TOP /*将返回地址送X*/ UJ 0X /*无条件转移，返回*/ 过程返回执行的指令与简单栈式存储分配的过程返回完全一样。第八章 运行时存储空间组织 6.3.3 访问非局部名的另一种实现方法 在允许嵌套的过程中，一个过程可以引用包围它的任一外层过程所定义的变量或数组；也即在运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据(这些数据视为过程Q的非局部量)。为了在活动记录中查找非局部名字所对应的存储空间，过程Q运行时必须知道它的所有外层过程的最新活动记录的地址。因为过程活动记录的位置(即使是相对位置)往往也因过程的递归而变迁，
31、所以必须设法跟踪每个外层过程的最新活动记录的位置。 第八章 运行时存储空间组织 跟踪的一种有效办法是采用嵌套层次显示表DISPLAY，其优点是访问非局部量的速度较快。在此，我们介绍另一种访问非局部名的方法存取链(也称静态链)方法。 存取链方法引入一个称为存取链的指针，该指针作为活动记录的一项指向直接外层的最新活动记录的地址，这就意味着在运行时栈中的每个数据区(活动记录)之间又拉出一条链，这个链称为存取链。注意，运行时栈中数据区之间原先就存在一条链，即每个活动记录中所保存的老SP值这一项，第八章 运行时存储空间组织 它是指向调用该过程(子过程)的那个过程(父过程)的最新活动记录的起点，由此向前形
32、成了一条SP链。为了区别于存取链，称SP链为控制链(也称动态链)，它记录了在运行中过程之间相互调用的关系。注意，控制链是动态的，而存取链是静态的。控制链记录了当前时刻程序中各过程相互调用的情况；而存取链则始终记录着程序静态定义时该过程所有的直接外层(嵌套过程规定，内层过程只允许调用其静态定义时的外层过程说明的变量和数组)；因此，存取链指出了一个过程的当前活动记录指向其直接定义的外层过程直至最外层的最新活动记录的起点。具有存取链的活动记录结构如图810所示。 假定过程的嵌套关系如下：第八章 运行时存储空间组织 P: var a; Q(b); var i; R; var c,d; call R;
33、S; var c,i; call Q; call S; 第八章 运行时存储空间组织TOP SP临时单元内情向量简单变量形式参数形参个数存取链(静态链)返回地址控制链(动态链)：老SP第八章 运行时存储空间组织 程序中每个过程的静态结构(嵌套层次)是确定的，如嵌套深度为2的过程R引用了非局部量a和b，其嵌套深度分别为0和1。从R的活动记录开始，分别沿着20=2和21=1个存取链向前查找，则可找到包含这两个非局部量的活动记录。 上述过程P调用S以及S调用Q运行时栈的变化过程如图811(a)、(b)所示。第八章 运行时存储空间组织 由图811可以看出，指针SP总是指向当前正在执行过程的活动记录起点，
34、控制链(老SP)则指向调用运行过程的父过程的活动记录起点。因此，当运行过程调用结束返回时，利用控制链老SP值可以得到调用前原父过程活动记录的起点。从程序的静态结构来看，P是S和Q的静态直接外层，所以，S和Q活动记录中的存取链均指向其直接外层P的活动记录起点。第八章 运行时存储空间组织SPTOPic形参个数：0存取链：0返回地址老SP：0a形参个数：0存取链：0返回地址0S过程P过程i形式参数：b形参个数：1存取链：0返回地址老SPic形参个数：0存取链：0返回地址老SP：0a形参个数：0存取链：0返回地址0TOPSPQ过程S过程P过程(b)(a)00第八章 运行时存储空间组织 例8.1 某程序
35、的结构如图812所示，其中A、B、C为过程名，请分别画出过程C调用A前后的栈顶活动记录。第八章 运行时存储空间组织主程序ABC var x: int x=5 call A第八章 运行时存储空间组织 解答 过程C调用A前后的栈顶活动记录示意如图813所示。由图813可知，当过程C执行时，它可使用主程序、A、B和C过程所说明的变量，且其外层嵌套的过程活动记录始址由DISPLAY表指出。当C调用A而使过程A执行时，我们看到此时的DISPLAY表已变为两项，即主程序和A过程自身；也即此时A只可使用主程序和A过程所说明的变量。第八章 运行时存储空间组织DISPLAY表A_SP主程序_SP参数个数：0全局
36、DISPLAY地址返回地址C_SP局部变量：xDISPLAY表C_SPB_SPA_SP主程序_SP参数个数：0全局DISPLAY地址返回地址B_SPA_TOPA_SPC_TOPC_SP调用A后的活动记录(在此标记为A)调用A前C的活动记录第八章 运行时存储空间组织 例8.2 在下面的PASCAL程序中，已经第二次(递归地)进入了f，请给出第三次进入f后的运行栈及DISPLAY的示意图 PROGRAM test(input, output); VAR K: integer; FUNCTION f(n: integer): integer; BEGIN IF n=0 THEN f:=1第八章 运行
37、时存储空间组织f的DISPLAY(n8)SP2SP30SP20SP100f的DISPLAY(n9)f的DISPLAY(n10)SP1test的DISPLAY第三次递归第二次递归第一次递归主程序SP30第八章 运行时存储空间组织 解答 第三次进入f后的运行栈及DISPLAY的示意图如图814所示。由于静态嵌套层次只有两层，故每一次递归调用产生的DISPLAY表只有两项，一项是test的SP(即0)，另一项是当前活动记录的SPi(i=1,2,3)。 第八章 运行时存储空间组织前后活动记录的过程前后活动记录的过程返回地址返回地址ex_SP ex_SP a a DISPLA DISPLA丫表丫表ex_
38、SPex_SP参数个数：参数个数：0 0 全局全局DISPLDISPLLYLY地址地址返回地址返回地址ex _SP ex _SP 6.4 堆式动态存储分配 6.4.1 堆式存储的概念 如果一种程序语言允许数据对象能够自由地分配和释放，或者不仅有过程而且有进程(process)这样的程序结构，那么由于空间的使用不一定遵循“先申请后释放”的原则，则栈式存储分配就不适用了。在这种情况下，通常使用一种称之为堆的动态存储分配方案。假定程序运行时有一个大的存储空间，需要时就从这个空间中借用一块，不用时再退还给它。 第八章 运行时存储空间组织 由于借、还的时间先后不一，因而经过一段时间的运行后，这个大空间就
39、必然被分割成如图615所示的许多小块，这些块有些正在使用，有些则是空闲的(未被使用)。第八章 运行时存储空间组织BAC D可分配空间ABCD使用块记录第八章 运行时存储空间组织 对于堆式存储分配来说，需要解决两个问题：一是堆空间的分配，即当运行程序需要一块空间时应分配哪一块给它；另一个问题是分配空间的回收，由于返回堆的不用空间是按任意次序进行的，所以需要研究专门的回收分配策略。 在许多语言中都有显式的堆空间分配和回收语句或函数，如PASCAL语言中的new和dispose、C语言中的alloc和free以及C+语言中的new和delete。第八章 运行时存储空间组织 6.4.2 堆式存储管理的
40、方法 由于堆式分配方式和存储管理技术较为复杂，并且有效的堆管理是数据结构课程研究的问题，故我们只对堆式分配方式作简单的讨论。 当运行程序要求一块体积为N的存储空间时应如何分配？从理论上讲，这时应从比N稍大一些的空闲块中取出N个单元予以分配，这种做法的目的是保持较大的空闲块以备将来之需。但这种方法实现起来难度较大，实际中采用的办法是：扫描空闲块链并在首次遇到的比N大的空闲块中取出N个单元进行分配。第八章 运行时存储空间组织 如果找不到一块比N大的空闲块，但所有空闲块的总和却比N大，这时就需要用某种方法使这些空闲块拼接在一起，形成一个可分配的连续空间。如果所有空闲块的总和都不及N大，则需要采用更复
41、杂的办法，如废品回收技术(即寻找那些运行程序已不使用但仍未释放的存储块或运行程序目前很少使用的存储块)，把这些存储块回收后再重新分配。 可以采用多种策略进行堆式动态存储管理。在此，我们介绍一种使用可利用空间表进行动态分配的方法。可利用空间表是指将所有空闲块用一张表记录下来，表的结构可以是目录表，也可以是链表，其结构分别如图616(b)、(c)所示。第八章 运行时存储空间组织050012001700200026003600(a)块编号起始地址 内存大小150070021700300326001000heap7003001000(b)50017002600(c)第八章 运行时存储空间组织 使用可利
42、用空间表进行动态存储分配的方法又可分为如下两种： (1) 定长块的管理。最简单的堆式存储管理方法是采用定长块的管理方法，即将堆存储空间在初始化时就划分成大小相同的若干块，将各个块通过链表链接起来形成一个单向线性链表。由于各块大小相同，故分配时无需查找，只需将头指针所指的第一块分配给用户即可，然后头指针指向下一块。同样，当回收时，系统将待回收的存储块插入到表头即完成了该块的回收。第八章 运行时存储空间组织 (2) 变长块的管理。变长块管理方法是一种常用的堆式存储管理方法，它可以根据实际需要来分配长度不同的空闲块；对空闲块的管理则可以采用图616(c)中的链表形式。 系统开始时，存储空间是一完整空
43、间，可利用空间表中只有一个大小为整个存储空间的空闲块。当系统运行一段时间后，随着分配和回收的进行，可利用空间表中空闲块的大小和个数也随之改变。由于可利用空间表中的空闲块大小不同，因而存在着如何进行空闲块分配的问题。若可利用空间表存在多个大于所要求空间的空闲块，可采取以下三种方法之一进行存储分配：第八章 运行时存储空间组织 (1) 首次满足法。从表头开始查找可利用空间表，将找到的第一个满足需要的空闲块或空闲块的一部分分配出去(当空闲块略大于所要求的空间时，则整块分配出去)，而其余部分仍作为一个空闲块留在表中。 (2) 最优满足法。系统扫描整个可利用空间表，从中找出一块不小于要求的最小空闲块予以分
44、配。为了避免每次分配都要扫描整个表，通常将空闲块按由小到大的顺序进行排列。这样，所找到的第一个大于或等于所需空间的空闲块即为所求，无须再扫描整个表。第八章 运行时存储空间组织 (3) 最差满足法。系统将可利用空间表中最大的空闲块予以分配(当然也要求其不小于所需空间的大小)，这种方法应使空闲块按由大到小的顺序排列，此时表头的空闲块即为所求。 最优满足法和最差满足法在回收时都需将待回收的空闲块插入到链表中适当的位置上去。第八章 运行时存储空间组织 以上三种方法各有所长。一般来说，最优满足法适用于请求分配的内存大小范围较广的系统；最差满足法适用于请求分配的内存大小范围较窄的系统；而首次满足法则适用于
45、事先无法获知请求分配和回收情况的系统。从时间上来看，最优满足法无论分配与回收都需要查表，故最费时间；最差满足法分配时无需查表，但回收时却需查表并根据回收空闲块的大小确定其在表中应插入的位置；而首次满足法在分配时需要查表，回收时直接插入到表头即可。第八章 运行时存储空间组织 对于已分配的存储块，可以采用不同的回收策略。有的程序语言干脆不做回收工作，直到内存空间用完为止；如果当空间用完后还有分配存储块的请求，就停止程序的运行。这样做的缺点是浪费空间，但如果系统具有海量虚存或堆中的多数数据是一分配就一直使用的情形，则这种方法也是可行的。如果程序语言有显式的分配命令，那么就可用显式的回收命令(如C语言
46、中的free)来回收不用的空间。第八章 运行时存储空间组织*6.5 参数传递补遗 定义和调用过程是程序语言的主要特征之一。过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言能力的主要途径。PASCAL语言的设计者N.Wirth曾经说过：“在程序设计技巧中，过程是很少几种基本工具中的一种，掌握了这种工具，就能对程序员工作的质量和风格产生决定性的影响”。第八章 运行时存储空间组织 一个过程一旦定义后，就可以在别的地方调用它。调用与被调用(过程)两者之间的信息往来通过全局量或参数传递。例如，下面的C语言程序： #include “stdio.h” void showme (int a, i
47、nt b, int c) printf (“a=%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则称为实在参数(简称实参)。实参甚至也可以是一个较复杂的表达式而不仅仅只是一个变量。实参和对应的形参在性质上应相容不悖。 第八章 运行时存储空间组织 6.5.1 参数传递的方法 形式参数提供了参数替换的手段，在过程调
48、用时可以使用不同的数据作为实在参数来替换形式参数，从而实现了同一个过程可以对不同的实在参数进行相同操作的功能。那么，如何把实在参数传递给相应的形式参数呢？程序语言中参数传递的方式主要有传值(call by value)、传地址(call by reference)和传名(call by name)三种。第八章 运行时存储空间组织 1传值 传值是最简单的参数传递方法。所谓传值，就是计算出实在参数的值然后把它传给被调用过程相对应的形式参数，具体过程如下： (1) 把形式参数当作过程的局部变量处理，即在被调用过程的活动记录中开辟形式参数的存储空间(即形式单元)。 (2) 调用过程计算出实在参数的值，
49、并将该值放入为形式单元开辟的空间中。第八章 运行时存储空间组织 (3) 被调用过程执行时就像使用局部变量一样使用这些形式单元。 传值的一个重要特点是对形式参数的任何运算都不影响调用过程的活动记录中实在参数的值，即参数传递后实在参数与对应的形式参数不再发生联系了。第八章 运行时存储空间组织 2传地址 所谓传地址，是指把实在参数的地址传递给相应的形式参数所对应的形式单元。如果实在参数是一个变量(包括下标变量)，则直接将该变量的地址传给相应的形式单元；如果实在参数是常数或表达式，则先计算其值并存放在某一临时单元中，然后将这个临时单元的地址传给相应的形式单元。被调用过程执行时，对形式参数的任何引用或赋
50、值都被处理成对形式单元的间接访问，即按形式单元中存放的地址转到调用过程的活动记录中去访问实在参数。 第八章 运行时存储空间组织 对形式参数的任何运算实际上都是对实在参数的运算，而形式参数只不过起到辅助查找到实在参数的指针的作用。因此，当被调用过程工作完毕返回时，形式单元所指的实在参数单元就保留了运算的结果。第八章 运行时存储空间组织 3传名 传名是高级语言ALGOL 60所定义的一种特殊的参数传递方式，其传递参数的方法如下： (1) 过程调用的作用相当于把被调用过程的过程体复制到调用处(替换调用语句)，并将过程体中所有出现的形式参数在文字上替换成相应的实在参数。这种文 字 上 的 替 换 称
