第6章运行时存储空间组织-资料课件

第第6 6章章 运行时存储空间组织运行时存储空间组织 6.1 静态存储分配静态存储分配 如果在编译时就能够确定一个程序在运行时所需的存储空间大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址，存储空间的这种分配方法叫做静态分配。第第6 6章章 运行时存储空间组织运行时存储空间组织 对FORTRAN语言来说，其特点是不允许过程有递归性，每个数据名所需的存储空间大小都是常量(即不允许含可变体积的数据，如可变数组)，并且所有数据名的性质是完全确定的(不允许出现在运行时再动态确定其性质的名字这种情况)。这些特点确保整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配。静态存储分配是一种最简单的存储管理。一般而言，适于静态存储分配的语言必须满足以下条件：第第6 6章章 运行时存储空间组织运行时存储空间组织 (1)数组的上下界必须是常数；(2)过程调用不允许递归；(3)不允许采用动态的数据结构(即在程序运行过程中申请和释放的数据结构)。第第6 6章章 运行时存储空间组织运行时存储空间组织 满足这些条件的语言除了FORTRAN之外，还有BASIC等语言。在这些语言中，编译程序可以完全确定程序中数据项所在的地址(通常为相对于各数据区起始地址的位移量)。由于过程调用不允许递归，因此数据项的存储地址就与过程相联系。过程调用所使用的局部数据区可以直接安排在过程的目标代码之后，并把各数据项的存储地址填入相关的目标代码中，以便在过程运行时访问这个局部数据区。在此，不存在对存储区的再利用问题；目标程序执行时不必进行运行时的存储空间管理，过程的进入和退出变得极为简单。第第6 6章章 运行时存储空间组织运行时存储空间组织 FORTRAN语言的静态存储管理特点是FORTRAN程序中的各程序段均可独立地进行编译。在编译过程中，给程序中的变量或数组分配存储单元的一般做法是：为每一个变量(或数组)确定一个有序的整数对；其中，第一个整数用来指示数据区(局部数据区或公用区)的编号，第二个整数则用来指明该变量(或数组)所对应的存储起始单元相对于其所在数据区起点的位移(即相对于数据区起点的地址)；并将这一对整数填入符号表相应登记项的信息栏中。至于各数据区的起始地址在编译时可暂不确定，待各程序段全部编译完成之后，再由连接装配程序最终确定，并将各程序段的目标代码组装成一个完整的目标程序。第第6 6章章 运行时存储空间组织运行时存储空间组织 一个FORTRAN程序段的局部数据区可由图61所示的项目组成。其中，隐参数是指过程调用时的连接信息(不在源程序中明显出现)，如调用时的返回地址、调用时寄存器的保护等；形式单元用来存放过程调用时形参与实参结合的实参地址或值。第第6 6章章 运行时存储空间组织运行时存储空间组织 图61一个FORTRAN程序段的局部数据区第第6 6章章 运行时存储空间组织运行时存储空间组织 6.2 简单的栈式存储分配简单的栈式存储分配我们首先考虑一种简单程序语言的实现，这种语言没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用，允许过程含有可变数组。例如，C语言除不允许含有可变数组外，就是这样一种语言。C语言的程序结构如下：第第6 6章章 运行时存储空间组织运行时存储空间组织 全局数据说明main()main中的数据说明voidR()R中的数据说明第第6 6章章 运行时存储空间组织运行时存储空间组织 voidQ()Q中的数据说明第第6 6章章 运行时存储空间组织运行时存储空间组织 例如，下面计算n！的C语言程序就是一个递归调用的程序，它的执行过程可以用栈来实现。#include“stdio.h”longfactorial(intn)if(n1)return(n*factorial(n1);elsereturn(1);第第6 6章章 运行时存储空间组织运行时存储空间组织 main()intnum;doscanf(“%d”,&num);if(num=0&num=0);第第6 6章章 运行时存储空间组织运行时存储空间组织 6.2.1栈式存储分配与活动记录使用栈式存储分配法意味着程序运行时，每当进入一个过程(或函数)就有一个相应的活动记录累筑于栈顶，此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等；在进入过程和执行过程的可执行语句之前，再把局部数组所需空间累筑于栈顶，从而形成过程工作时的完整数据区。第第6 6章章 运行时存储空间组织运行时存储空间组织 注意，每个过程的活动记录的体积在编译时可以静态地确定。但由于允许含有可变数组，所以数组的大小只有在运行时才能知道。因数组区的大小不能预先获知，为了扩充方便，所以只能将数组区累筑于活动记录之上的当前栈顶。当一个过程工作完毕返回时，它在栈顶的数据区(包括活动记录和数组区)也随即不复存在。第第6 6章章 运行时存储空间组织运行时存储空间组织 对C语言来说，由于其不含可变数组，因而它的活动记录本身包含了局部数组的空间。图62和图63分别给出了C语言和含可变数组的某简单语言程序运行时的数据空间结构，即显示了主程序在调用了过程Q，Q又调用了过程R，且在R投入运行后的存储结构。SP指示器总是指向执行过程活动记录的起点，而TOP指示器则始终指向(已占用)栈顶单元。当进入一个过程时，TOP指向为此过程创建的活动记录的顶端；在分配数组区之后(如果有的话)，TOP又改为指向数组区(从而是该过程整个数据区)的顶端。第第6 6章章 运行时存储空间组织运行时存储空间组织 图62C语言程序的存储组织第第6 6章章 运行时存储空间组织运行时存储空间组织 图63含可变数组程序的存储组织第第6 6章章 运行时存储空间组织运行时存储空间组织 C的活动记录含有以下几个区段(如图64所示)：(1)连接数据(两项)：老SP值(即前一活动记录的起始地址)和返回地址；(2)参数个数；(3)形式单元(存放实在参数的值或地址)；(4)过程的局部变量(简单变量)、数组的内情向量和临时工作单元。第第6 6章章 运行时存储空间组织运行时存储空间组织 图64C过程的活动记录第第6 6章章 运行时存储空间组织运行时存储空间组织 C语言不允许过程(函数)嵌套，也即不允许一个过程的定义出现在另一个过程的定义之内。因此，C语言的非局部变量仅能出现在源程序头，非局部变量可采用静态存储分配并在编译时确定它们的地址。由图64可知，过程的每一局部变量或形参在活动记录中的位置都是确定的；也就是说，这些变量或形参所分配的存储单元其地址都是相对于活动记录的基址SP的。因此，变量和形参运行时在栈上的绝对地址是：绝对地址=活动记录基址(SP)+相对地址第第6 6章章 运行时存储空间组织运行时存储空间组织 于是，对当前正在执行(即活动)的过程，其任何局部变量或形参X的引用均可表示为变址访问XSP。此处X代表X相对于活动记录基址的偏移量，这个偏移量(即相对数)在编译时可完全确定下来。过程的局部数组的内情向量的相对地址在编译时也同样可完全确定下来，一旦数据空间在过程里获得分配后，对数组元素的引用也就容易用变址的方式进行访问。第第6 6章章 运行时存储空间组织运行时存储空间组织 6.2.2过程的执行1过程调用过程调用的四元式序列为：parT1parT2parTncallP,n第第6 6章章 运行时存储空间组织运行时存储空间组织 由于此时TOP是指向被调用过程P之前的栈顶，而P的形式单元和活动记录起点之间的距离是确定的(等于3，参见图64)，因而由调用者过程给将要调用的过程P的活动记录(正在形成中)的形式单元传递实参值或实参地址，即每个parTi(i=1,2,n)可直接翻译成如下指令：(i+3)TOP=Ti/*传递参数值*/或(i+3)TOP=addrTi/*传递参数地址*/第第6 6章章 运行时存储空间组织运行时存储空间组织 而四元式callP,n则翻译成：1TOP=SP/*保护现行SP*/3TOP=n/*传递参数个数*/JSRP/*转子指令，转向P过程的第一条指令*/过程P调用之前，先构造出P的活动记录部分内容，见图65所示。第第6 6章章 运行时存储空间组织运行时存储空间组织 图65过程P调用前先构造P的活动记录部分内容第第6 6章章 运行时存储空间组织运行时存储空间组织 2过程进入转入过程P后，首先要做的工作是定义新活动记录的SP，保护返回地址和定义新活动记录的TOP值，即执行下述指令：SP=TOP+1/*定义新SP*/1SP=返回地址/*保护返回地址*/TOP=TOP+L/*定义新TOP*/其中，L是过程P的活动记录所需的单元数，这个数在编译时可静态地计算出来。第第6 6章章 运行时存储空间组织运行时存储空间组织 对含可变数组(非C语言)的情况来说，因为过程可含可变数组且所有数组都分配在活动记录的顶上，所以紧接上述指令之后应是对数组进行存储分配的指令(如果含有局部数组)，这些指令是在翻译数组说明时产生的。对每个数组说明，相应的目标指令组将做以下几件工作：(1)计算各维的上、下限；(2)调用数组空间分配子程序，其参数是各维的上、下限和内情向量单元首地址。第第6 6章章 运行时存储空间组织运行时存储空间组织 数组空间分配子程序计算并填好内情向量的所有信息，然后在TOP所指的位置之上留出数组所需的空间，并将TOP调整为指向数组区的顶端。进入过程P后所做的工作如图66所示。此后，在过程段执行语句的工作过程中，凡引用形式参数、局部变量或数组元素都将以SP为基址进行相对访问。第第6 6章章 运行时存储空间组织运行时存储空间组织 图66进入过程P后所做的工作示意第第6 6章章 运行时存储空间组织运行时存储空间组织 3过程返回C语言以及其它一些相似的语言含有return(E)形式的返回语句，其中E为表达式。假定E值已计算出来并存放在某临时单元T中，则此时即可将T值传送到某个特定的寄存器中(调用过程将从这个特定的寄存器中获得被调用过程P的结果)。剩下的工作就是恢复SP和TOP为进入过程P之前的原值(即指向调用过程的活动记录及工作空间)，并按返回地址实行无条件转移，即执行下述指令序列：第第6 6章章 运行时存储空间组织运行时存储空间组织 TOP=SP1/*恢复调用过程的TOP值*/SP=0SP/*恢复调用过程的SP值*/X=2TOP/*将返回地址送X*/UJ0X/*无条件转移，即按X的地址返回到调用过程*/一个过程也可通过它的end语句(对C语言则是该过程(函数)体结束时的“”)自动返回。如果此过程是一个函数过程，则按上述办法传递结果值，否则仅直接执行上述返回指令序列。过程P的返回示意如图67所示。第第6 6章章 运行时存储空间组织运行时存储空间组织 图67过程P的返回示意第第6 6章章 运行时存储空间组织运行时存储空间组织 6.3 嵌套过程语言的栈式实现嵌套过程语言的栈式实现在简单程序语言实现中是允许过程的递归调用的，并且过程中可含有可变数组。现在，我们再加上一种功能，即允许过程的嵌套性。从结构上看，PASCAL就是这样的一种语言；但由于PASCAL含有“文件”和“动态变量”，因此，它的存储分配不能简单地用栈式方法来实现。采用PASCAL的一个子集，例如去掉“文件”和“动态变量”这种数据类型，那就可以用我们下面将要讨论的方法实现存储分配。第第6 6章章 运行时存储空间组织运行时存储空间组织 6.3.1嵌套层次显示表(DISPLAY)和活动记录在讨论中，常常要用到过程定义的“嵌套层次”(简称层数)这个概念。我们始终假定主程序的层数为0，因此主程序称为第0层过程。如果过程Q是在层数为i的过程P内定义的，并且P是包围Q的最小过程，则Q的层数就为i+1。当编译程序处理过程说明时，过程的层数将作为过程名的一个重要属性登记在符号表中。第第6 6章章 运行时存储空间组织运行时存储空间组织 由于过程定义是嵌套的，因而一个过程可以引用包围它的任一外层过程所定义的变量或数组。也就是说，运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运行时必须知道它的所有外层的最新活动记录的地址。由于允许递归和可变数组的存在，过程的活动记录位置(即使是相对位置)也往往是变迁的，因而必须设法跟踪每个外层过程的最新活动记录的位置。第第6 6章章 运行时存储空间组织运行时存储空间组织 一种常用的跟踪每个外层过程最新活动记录位置的有效办法是，每进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表DISPLAY。假定现在进入的过程层数为i，则它的DISPLAY表含有i+1个单元。此表本身是一个小栈，自顶而下每个单元依次存放着现行层、直接外层直至最外层(第0层，即主程序层)的每一层的最新活动记录的起始地址。例如，令过程R的外层为Q，Q的外层为主程序P，则过程R运行时的DISPLAY表内容如表6.1所示。第第6 6章章 运行时存储空间组织运行时存储空间组织 表6.1DISPLAY表2R的现行活动记录的始址(SP的现行值)1Q的最新活动记录的始址0P的活动记录的始址第第6 6章章 运行时存储空间组织运行时存储空间组织 由于过程的层数可静态确定，因此每个过程的DISPLAY表的体积在编译时即可知道。为了便于组织存储区和简化处理手续，我们把DISPLAY作为活动记录的一部分置于形式单元的上端，如图68所示。第第6 6章章 运行时存储空间组织运行时存储空间组织 由于每个过程的形式单元数目在编译时是知道的，因此DISPLAY的相对地址d(相对于活动记录的起点)在编译时也是完全确定的。被调用过程为了建立自己的DISPLAY，就必须知道它的直接外层过程的DISPLAY，这意味着必须把直接外层的DISPLAY地址作为连接数据之一(称为“全局DISPLAY地址”)传送给被调用过程。于是，此时的连接数据包含老SP值、返回地址和全局DISPLAY地址这三项内容。整个活动记录的结构如图68所示。第第6 6章章 运行时存储空间组织运行时存储空间组织 图68活动记录结构第第6 6章章 运行时存储空间组织运行时存储空间组织 6.3.2嵌套过程的执行1过程调用过程调用所做的工作与简单栈式存储分配大体相同，只是增加了一个连接数据，所以每个parTi相应的指令应改为：(i+4)TOP=Ti或者(i+4)TOP=addrTi第第6 6章章 运行时存储空间组织运行时存储空间组织 callP,n所对应的指令应为：1TOP=SP/*保护现行SP*/3TOP=SP+d/*将直接外层的DISPLAY始址作为P的全局DISPLAY地址*/4TOP=n/*传递参数个数*/JSRP/*转向P的第一条指令*/第第6 6章章 运行时存储空间组织运行时存储空间组织 2过程进入转入过程P后，首先执行和简单栈式存储分配相同的指令：SP=TOP+1/*定义新的SP*/1SP=返回地址/*保护返回地址*/TOP=TOP+L/*定义新的TOP*/其次，应按第三项连接数据所提供的全局DISPLAY地址，自底而上地抄录k个单元内容(k为P的层次)，最后再添上新的SP值形成现行过程P的DISPLAY(共k+1个单元)。其过程如图69所示。第第6 6章章 运行时存储空间组织运行时存储空间组织 图69过程P进入示意第第6 6章章 运行时存储空间组织运行时存储空间组织 3过程返回当过程P工作完毕要返回到调用段时，若return语句含有返回值或P是函数过程，则把已算好的值传送到某个特定的寄存器，然后执行：TOP=SP1/*恢复调用过程的TOP值*/SP=0SP/*恢复调用过程的SP值*/X=2TOP/*将返回地址送X*/UJ0X/*无条件转移，返回*/过程返回执行的指令与简单栈式存储分配的过程返回完全一样。第第6 6章章 运行时存储空间组织运行时存储空间组织 6.3.3访问非局部名的另一种实现方法在允许嵌套的过程中，一个过程可以引用包围它的任一外层过程所定义的变量或数组；也即在运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据(这些数据视为过程Q的非局部量)。为了在活动记录中查找非局部名字所对应的存储空间，过程Q运行时必须知道它的所有外层过程的最新活动记录的地址。因为过程活动记录的位置(即使是相对位置)往往也因过程的递归而变迁，所以必须设法跟踪每个外层过程的最新活动记录的位置。第第6 6章章 运行时存储空间组织运行时存储空间组织 跟踪的一种有效办法是采用嵌套层次显示表DISPLAY，其优点是访问非局部量的速度较快。在此，我们介绍另一种访问非局部名的方法存取链(也称静态链)方法。存取链方法引入一个称为存取链的指针，该指针作为活动记录的一项指向直接外层的最新活动记录的地址，这就意味着在运行时栈中的每个数据区(活动记录)之间又拉出一条链，这个链称为存取链。注意，运行时栈中数据区之间原先就存在一条链，即每个活动记第第6 6章章 运行时存储空间组织运行时存储空间组织 录中所保存的老SP值这一项，它是指向调用该过程(子过程)的那个过程(父过程)的最新活动记录的起点，由此向前形成了一条SP链。为了区别于存取链，称SP链为控制链(也称动态链)，它记录了在运行中过程之间相互调用的关系。注意，控制链是动态的，而存取链是静态的。控制链记录了当前时刻程序中各过程相互调用的情况；而存取链则始终记录着程序静态定义时该过程所有的直接外层(嵌套过程规定，内层过程只允许调用其静态定义时的外层过程说明的变量和数组)；因此，存取链指出了一个过程的当前活动记录指向其直接定义的外层过程直至最外层的最新活动记录的起点。具有存取链的活动记录结构如图610所示。假定过程的嵌套关系如下：第第6 6章章 运行时存储空间组织运行时存储空间组织 第第6 6章章 运行时存储空间组织运行时存储空间组织 图610具有存取链的活动记录结构第第6 6章章 运行时存储空间组织运行时存储空间组织 程序中每个过程的静态结构(嵌套层次)是确定的，如嵌套深度为2的过程R引用了非局部量a和b，其嵌套深度分别为0和1。从R的活动记录开始，分别沿着20=2和21=1个存取链向前查找，则可找到包含这两个非局部量的活动记录。上述过程P调用S以及S调用Q运行时栈的变化过程如图611(a)、(b)所示。第第6 6章章 运行时存储空间组织运行时存储空间组织 由图611可以看出，指针SP总是指向当前正在执行过程的活动记录起点，控制链(老SP)则指向调用运行过程的父过程的活动记录起点。因此，当运行过程调用结束返回时，利用控制链老SP值可以得到调用前原父过程活动记录的起点。从程序的静态结构来看，P是S和Q的静态直接外层，所以，S和Q活动记录中的存取链均指向其直接外层P的活动记录起点。第第6 6章章 运行时存储空间组织运行时存储空间组织 图611过程调用时运行栈的变化第第6 6章章 运行时存储空间组织运行时存储空间组织 例6.1某程序的结构如图612所示，其中A、B、C为过程名，请分别画出过程C调用A前后的栈顶活动记录。第第6 6章章 运行时存储空间组织运行时存储空间组织 图612例6.1的程序结构示意第第6 6章章 运行时存储空间组织运行时存储空间组织 解答过程C调用A前后的栈顶活动记录示意如图613所示。由图613可知，当过程C执行时，它可使用主程序、A、B和C过程所说明的变量，且其外层嵌套的过程活动记录始址由DISPLAY表指出。当C调用A而使过程A执行时，我们看到此时的DISPLAY表已变为两项，即主程序和A过程自身；也即此时A只可使用主程序和A过程所说明的变量。第第6 6章章 运行时存储空间组织运行时存储空间组织 图613例6.1的运行栈与活动记录示意第第6 6章章 运行时存储空间组织运行时存储空间组织 例6.2在下面的PASCAL程序中，已经第二次(递归地)进入了f，请给出第三次进入f后的运行栈及DISPLAY的示意图PROGRAMtest(input,output);VARK:integer;FUNCTIONf(n:integer):integer;BEGINIFn=0THENf:=1第第6 6章章 运行时存储空间组织运行时存储空间组织 图614例6.2的运行栈及DISPLAY示意图第第6 6章章 运行时存储空间组织运行时存储空间组织 解答第三次进入f后的运行栈及DISPLAY的示意图如图614所示。由于静态嵌套层次只有两层，故每一次递归调用产生的DISPLAY表只有两项，一项是test的SP(即0)，另一项是当前活动记录的SPi(i=1,2,3)。第第6 6章章 运行时存储空间组织运行时存储空间组织 6.4 堆式动态存储分配堆式动态存储分配6.4.1堆式存储的概念如果一种程序语言允许数据对象能够自由地分配和释放，或者不仅有过程而且有进程(process)这样的程序结构，那么由于空间的使用不一定遵循“先申请后释放”的原则，则栈式存储分配就不适用了。在这种情况下，通常使用一种称之为堆的动态存储分配方案。假定程序运行时有一个大的存储空间，需要时就从这个空间中借用一块，不用时再退还给它。第第6 6章章 运行时存储空间组织运行时存储空间组织 由于借、还的时间先后不一，因而经过一段时间的运行后，这个大空间就必然被分割成如图615所示的许多小块，这些块有些正在使用，有些则是空闲的(未被使用)。第第6 6章章 运行时存储空间组织运行时存储空间组织 图615堆式存储分配示意第第6 6章章 运行时存储空间组织运行时存储空间组织 对于堆式存储分配来说，需要解决两个问题：一是堆空间的分配，即当运行程序需要一块空间时应分配哪一块给它；另一个问题是分配空间的回收，由于返回堆的不用空间是按任意次序进行的，所以需要研究专门的回收分配策略。在许多语言中都有显式的堆空间分配和回收语句或函数，如PASCAL语言中的new和dispose、C语言中的alloc和free以及C+语言中的new和delete。第第6 6章章 运行时存储空间组织运行时存储空间组织 6.4.2堆式存储管理的方法由于堆式分配方式和存储管理技术较为复杂，并且有效的堆管理是数据结构课程研究的问题，故我们只对堆式分配方式作简单的讨论。当运行程序要求一块体积为N的存储空间时应如何分配？从理论上讲，这时应从比N稍大一些的空闲块中取出N个单元予以分配，这种做法的目的是保持较大的空闲块以备将来之需。但这种方法实现起来难度较大，实际中采用的办法是：扫描空闲块链并在首次遇到的比N大的空闲块中取出N个单元进行分配。第第6 6章章 运行时存储空间组织运行时存储空间组织 如果找不到一块比N大的空闲块，但所有空闲块的总和却比N大，这时就需要用某种方法使这些空闲块拼接在一起，形成一个可分配的连续空间。如果所有空闲块的总和都不及N大，则需要采用更复杂的办法，如废品回收技术(即寻找那些运行程序已不使用但仍未释放的存储块或运行程序目前很少使用的存储块)，把这些存储块回收后再重新分配。可以采用多种策略进行堆式动态存储管理。在此，我们介绍一种使用可利用空间表进行动态分配的方法。可利用空间表是指将所有空闲块用一张表记录下来，表的结构可以是目录表，也可以是链表，其结构分别如图616(b)、(c)所示。第第6 6章章 运行时存储空间组织运行时存储空间组织 图616内存状态和可利用空间表第第6 6章章 运行时存储空间组织运行时存储空间组织 使用可利用空间表进行动态存储分配的方法又可分为如下两种：(1)定长块的管理。最简单的堆式存储管理方法是采用定长块的管理方法，即将堆存储空间在初始化时就划分成大小相同的若干块，将各个块通过链表链接起来形成一个单向线性链表。由于各块大小相同，故分配时无需查找，只需将头指针所指的第一块分配给用户即可，然后头指针指向下一块。同样，当回收时，系统将待回收的存储块插入到表头即完成了该块的回收。第第6 6章章 运行时存储空间组织运行时存储空间组织 (2)变长块的管理。变长块管理方法是一种常用的堆式存储管理方法，它可以根据实际需要来分配长度不同的空闲块；对空闲块的管理则可以采用图616(c)中的链表形式。系统开始时，存储空间是一完整空间，可利用空间表中只有一个大小为整个存储空间的空闲块。当系统运行一段时间后，随着分配和回收的进行，可利用空间表中空闲块的大小和个数也随之改变。由于可利用空间表中的空闲块大小不同，因而存在着如何进行空闲块分配的问题。若可利用空间表存在多个大于所要求空间的空闲块，可采取以下三种方法之一进行存储分配：第第6 6章章 运行时存储空间组织运行时存储空间组织 (1)首次满足法。从表头开始查找可利用空间表，将找到的第一个满足需要的空闲块或空闲块的一部分分配出去(当空闲块略大于所要求的空间时，则整块分配出去)，而其余部分仍作为一个空闲块留在表中。(2)最优满足法。系统扫描整个可利用空间表，从中找出一块不小于要求的最小空闲块予以分配。为了避免每次分配都要扫描整个表，通常将空闲块按由小到大的顺序进行排列。这样，所找到的第一个大于或等于所需空间的空闲块即为所求，无须再扫描整个表。第第6 6章章 运行时存储空间组织运行时存储空间组织 (3)最差满足法。系统将可利用空间表中最大的空闲块予以分配(当然也要求其不小于所需空间的大小)，这种方法应使空闲块按由大到小的顺序排列，此时表头的空闲块即为所求。最优满足法和最差满足法在回收时都需将待回收的空闲块插入到链表中适当的位置上去。第第6 6章章 运行时存储空间组织运行时存储空间组织 以上三种方法各有所长。一般来说，最优满足法适用于请求分配的内存大小范围较广的系统；最差满足法适用于请求分配的内存大小范围较窄的系统；而首次满足法则适用于事先无法获知请求分配和回收情况的系统。从时间上来看，最优满足法无论分配与回收都需要查表，故最费时间；最差满足法分配时无需查表，但回收时却需查表并根据回收空闲块的大小确定其在表中应插入的位置；而首次满足法在分配时需要查表，回收时直接插入到表头即可。第第6 6章章 运行时存储空间组织运行时存储空间组织 对于已分配的存储块，可以采用不同的回收策略。有的程序语言干脆不做回收工作，直到内存空间用完为止；如果当空间用完后还有分配存储块的请求，就停止程序的运行。这样做的缺点是浪费空间，但如果系统具有海量虚存或堆中的多数数据是一分配就一直使用的情形，则这种方法也是可行的。如果程序语言有显式的分配命令，那么就可用显式的回收命令(如C语言中的free)来回收不用的空间。第第6 6章章 运行时存储空间组织运行时存储空间组织 *6.5 参数传递补遗参数传递补遗定义和调用过程是程序语言的主要特征之一。过程是模块程序设计的主要手段，同时也是节省程序代码和扩充语言能力的主要途径。PASCAL语言的设计者N.Wirth曾经说过：“在程序设计技巧中，过程是很少几种基本工具中的一种，掌握了这种工具，就能对程序员工作的质量和风格产生决定性的影响”。第第6 6章章 运行时存储空间组织运行时存储空间组织 一个过程一旦定义后，就可以在别的地方调用它。调用与被调用(过程)两者之间的信息往来通过全局量或参数传递。例如，下面的C语言程序：#include“stdio.h”voidshowme(inta,intb,intc)printf(“a=%d,b=%d,c=%dn”,a,b,c);第第6 6章章 运行时存储空间组织运行时存储空间组织 main()intx=10,y=20,z=30;showme(z,y,x);就是一个含函数调用的程序。其中a、b、c称为形式参数(简称形参)，而函数调用语句：showme(z,y,x)第第6 6章章 运行时存储空间组织运行时存储空间组织 中的z、y、x则称为实在参数(简称实参)。实参甚至也可以是一个较复杂的表达式而不仅仅只是一个变量。实参和对应的形参在性质上应相容不悖。第第6 6章章 运行时存储空间组织运行时存储空间组织 6.5.1参数传递的方法形式参数提供了参数替换的手段，在过程调用时可以使用不同的数据作为实在参数来替换形式参数，从而实现了同一个过程可以对不同的实在参数进行相同操作的功能。那么，如何把实在参数传递给相应的形式参数呢？程序语言中参数传递的方式主要有传值(callby value)、传地址(call by reference)和传名(call byname)三种。第第6 6章章 运行时存储空间组织运行时存储空间组织 1传值传值是最简单的参数传递方法。所谓传值，就是计算出实在参数的值然后把它传给被调用过程相对应的形式参数，具体过程如下：(1)把形式参数当作过程的局部变量处理，即在被调用过程的活动记录中开辟形式参数的存储空间(即形式单元)。(2)调用过程计算出实在参数的值，并将该值放入为形式单元开辟的空间中。第第6 6章章 运行时存储空间组织运行时存储空间组织 (3)被调用过程执行时就像使用局部变量一样使用这些形式单元。传值的一个重要特点是对形式参数的任何运算都不影响调用过程的活动记录中实在参数的值，即参数传递后实在参数与对应的形式参数不再发生联系了。第第6 6章章 运行时存储空间组织运行时存储空间组织 2传地址所谓传地址，是指把实在参数的地址传递给相应的形式参数所对应的形式单元。如果实在参数是一个变量(包括下标变量)，则直接将该变量的地址传给相应的形式单元；如果实在参数是常数或表达式，则先计算其值并存放在某一临时单元中，然后将这个临时单元的地址传给相应的形式单元。被调用过程执行时，对形式参数的任何引用或赋值都被处理成对形式单元的间接访问，即按形式单元中存放的地址转到调用过程的活动记录中去访问实在参数。第第6 6章章 运行时存储空间组织运行时存储空间组织 对形式参数的任何运算实际上都是对实在参数的运算，而形式参数只不过起到辅助查找到实在参数的指针的作用。因此，当被调用过程工作完毕返回时，形式单元所指的实在参数单元就保留了运算的结果。第第6 6章章 运行时存储空间组织运行时存储空间组织 3传名传名是高级语言ALGOL60所定义的一种特殊的参数传递方式，其传递参数的方法如下：(1)过程调用的作用相当于把被调用过程的过程体复制到调用处(替换调用语句)，并将过程体中所有出现的形式参数在文字上替换成相应的实在参数。这种文字上的替换称为宏扩展(MarcroExpansion)。第第6 6章章 运行时存储空间组织运行时存储空间组织 (2)被调用过程中的局部名如果与过程调用的实在参数名发生冲突，则在宏扩展前对被调用过程中的这些局部名重新命名以避免重名冲突。(3)为表现实在参数的整体性，必要时在替换前把实在参数用括号括起来。传名这种参数传递方法因其操作过于复杂现在已很少采用。第第6 6章章 运行时存储空间组织运行时存储空间组织 6.5.2不同参数传递方法的比较为了描述不同参数传递方法下程序的执行，我们将动态栈和活动记录结合起来简化为一种动态图。采用动态图的方法来对程序的执行进行描述时，即记录主程序和过程(或函数)的调用、运行及撤消各个阶段的状态，以及程序运行期间所有变量和过程(或函数)中传值与传地址的变化过程。动态图规则如下：第第6 6章章 运行时存储空间组织运行时存储空间组织 (1)动态图纵向描述主程序、过程或函数各层之间的调用关系，横向由左至右按执行的时间顺序记录主程序、过程(或函数)中各变量值的变化情况。(2)过程(或函数)的传值的形式参数均看作是带初值的局部变量(也可用箭头来表示实在参数传给形式参数的指向)，其后，形式参数就作为局部变量参与过程(或函数)的操作。对于传地址方式，由于形式参数的作用就像指向实在参数的指针，故动态图中形式参数一律指向与其对应的实在参数变量(注意，两者位于动态图相邻的两层上；第第6 6章章 运行时存储空间组织运行时存储空间组织 如果实在参数为表达式，则用一个临时变量来代表这个表达式)；此后，所有对形式参数的操作都是根据形式参数箭头所指对实参变量进行的。(3)主程序，过程(或函数)按运行中的调用关系由上向下分层，各层(相当于活动记录)说明的变量(包括形式参数)都依次列于该层首列，各变量值的变化情况按时间顺序记录在与该变量对应的同一行上。第第6 6章章 运行时存储空间组织运行时存储空间组织 以下面的程序为例，对三种参数传递方法进行比较。programparament;int:A,BprocedureP(x,y,z);Y=Y+1;Z=Z+X第第6 6章章 运行时存储空间组织运行时存储空间组织 A=2;B=3;P(A+B,A,A);printA(1)传值：用T代表A+B的临时变量，则对图617所示的动态图分析得A=2。(2)传地址：用T代表A+B的临时变量，则对图618所示的动态图分析得A=8。第第6 6章章 运行时存储空间组织运行时存储空间组织 图617传值时的动态图第第6 6章章 运行时存储空间组织运行时存储空间组织 图618传地址时的动态图第第6 6章章 运行时存储空间组织运行时存储空间组织 (3)传名：由于传名时的过程调用就是把过程体抄到调用出现的地方，所以实际执行的程序为：A=2;B=3;A=A+1;/*形参Y换成A*/A=A+(A+B);/*形参Z换成A，形参X换成(A+B)*/printA经分析得A=9。第第6 6章章 运行时存储空间组织运行时存储空间组织 不同的参数传递方法得到的结果不同，因此，如何选择参数传递的方法将影响语言的语义，这是编译程序在处理参数传递时应引起重视的问题。