运行时存储空间组织

第七章运转时存储空间组织本章讨论目的程序运转时的活动和运转时的存储组织与管理本章要点：过程的活动与参数传送 静态存储分配 简单的栈式存储分配嵌套过程言语的栈式实现堆式动态存储分配

过程的活动与参数传送定义和调用过程〔函数〕是程序文语的主要特征之一。过程是模块程序设计的主要手段，同时也是节省程序代码和扩展言语才干的主要途径。一个过程一旦定义后，就可以在别的地方调用它。调用与被调用(过程)两者之间的信息往来经过全局量或参数传送。例如，下面的C言语程序：#include“stdio.h〞voidshowme(inta,intb,intc){printf(“a=%d,b=%d,c=%d\n〞,a,b,c);}main( ){intx=10,y=20,z=30;showme(z,y,x);}其中a、b、c称为方式参数(简称形参)函数调用语句：showme(z,y,x)中的z、y、x那么称为真实参数(简称实参)。实参甚至也可以是一个较复杂的表达式而不仅仅只是一个变量。实参和对应的形参在性质上应相容不悖。过程的活动一个过程的活动是指该过程的一次执行。过程的生存期是指从执行该过程体第一步操作到最后一步操作之间的操作程序，包括执行该过程时调用其他过程破费的时间。方式参数提供了参数交换的手段，在过程调用时可以运用不同的数据作为真实参数来交换方式参数，从而实现了同一个过程可以对不同的真实参数进展一样操作的功能。那么，如何把真实参数传送给相应的方式参数呢？程序文语中参数传送的方式主要有传值(callbyvalue)、传地址(callbyreference)和传名(callbyname)三种。参数的传送1．传值传值是最简单的参数传送方法。所谓传值，就是计算出真实参数的值然后把它传给被调用过程相对应的方式参数，详细过程如下：(1)把方式参数当作过程的部分变量处置，即在被调用过程中开辟方式参数的存储空间(即方式单元)。(2)调用过程计算出真实参数的值，并将该值放入为方式单元开辟的空间中。(3)被调用过程执行时就像运用部分变量一样运用这些方式单元。传值的一个重要特点是对方式参数的任何运算都不影响调用过程真实参数的值，即参数传送后真实参数与对应的方式参数不再发生联络了。2．传地址所谓传地址，是指把真实参数的地址传送给相应的方式参数所对应的方式单元。假照真实参数是一个变量，那么直接将该变量的地址传给相应的方式单元；假照真实参数是常数或表达式，那么先计算其值并存放在某一暂时单元中，然后将这个暂时单元的地址传给相应的方式单元。被调用过程执行时，对方式参数的任何援用或赋值都被处置成对方式单元的间接访问，即按方式单元中存放的地址转到调用过程中去访问真实参数。对方式参数的任何运算实践上都是对真实参数的运算，而方式参数只不过起到辅助查找到真实参数的指针的作用。因此，当被调用过程任务终了前往时，方式单元所指的真实参数单元就保管了运算的结果。3．传名传名是高级言语ALGOL60所定义的一种特殊的参数传送方式，其传送参数的方法如下：(1)过程调用的作用相当于把被调用过程的过程体复制到调用途(交换调用语句)，并将过程体中一切出现的方式参数在文字上交换成相应的真实参数。这种文字上的交换称为宏扩展(MarcroExpansion)。(2)被调用过程中的部分名假设与过程调用的真实参数名发生冲突，那么在宏扩展前对被调用过程中的这些部分名重新命名以防止重名冲突。(3)为表现真实参数的整体性，必要时在交换前把真实参数用括号括起来。传名这种参数传送方法因其操作过于复杂如今已很少采用。不同的参数传送方法得到的结果不同，因此，如何选择参数传送的方法将影响言语的语义，这是编译程序在处置参数传送时应引起注重的问题。运转时存储器的划分目的代码静态数据栈堆管理过程的活动，过程调用时相关信息存入栈中存放动态数据图7-1静态存储分配假设在编译时就可以确定一个程序在运转时所需的存储空间大小，那么在编译时就可以安排好目的程序运转时的全部数据空间，并能确定每个数据项的单元地址，存储空间的这种分配方法叫做静态分配。FORTRAN言语的特点：不允许过程有递归性；每个数据名所需的存储空间大小都是常量(即不允许含可变体积的数据，如可变数组)；一切数据名的性质是完全确定的(不允许出如今运转时再动态确定其性质的名字)。这些特点确保整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进展分配。静态存储分配是一种最简单的存储管理。普通而言，适于静态存储分配的言语必需满足以下条件：(1)数组的上下界必需是常数；(2)过程调用不允许递归；(3)不允许采用动态的数据构造(即在程序运转过程中恳求和释放的数据构造)。在编译过程中，给程序中的变量或数组分配存储单元的普通做法是：为每一个变量(或数组)确定一个有序的整数对；其中，第一个整数用来指示数据区(部分数据区或公用区)的编号，第二个整数那么用来指明该变量(或数组)所对应的存储起始单元相对于其所在数据区起点的位移(即相对于数据区起点的地址)；并将这一对整数填入符号表相应登记项的信息栏中。至于各数据区的起始地址在编译时可暂不确定，待各程序段全部编译完成之后，再由衔接装配程序最终确定，并将各程序段的目的代码组装成一个完好的目的程序。一个FORTRAN程序段的部分数据区可由图7-2所示的工程组成。其中，隐参数是指过程调用时的衔接信息(不在源程序中明显出现)，如调用时的前往地址、调用时存放器的维护等；方式单元用来存放过程调用时形参与实参结合的实参地址或值。一个FORTRAN程序段的部分数据区保管调用此程序段时的前往地址保管调用段留在存放器中的相关信息存放实参的地址或值图7-2简单的栈式存储分配我们首先思索一种简单程序文语的实现，这种言语没有分程序构造，过程定义不允许嵌套，但允许过程的递归调用，允许过程含有可变数组。例如，C言语除不允许含有可变数组外，就是这样一种言语。C言语的程序构造如下：全局数听阐明main( ){main中的数听阐明}voidR( ){R中的数听阐明}voidQ(){Q中的数听阐明}例如，下面计算n！的C言语程序就是一个递归调用的程序，它的执行过程可以用栈来实现。#include“stdio.h〞longfactorial(intn){if(n>1)return(n*factorial(n−1));elsereturn(1);}main( ){intnum;do{scanf(“%d〞,&num);if(num>=0&&num<15)printf(“%d\n〞,factorial(num));elseprintf(“error!\n〞);}while(num>=0);}运用栈式存储分配法意味着程序运转时，每当进入一个过程(或函数)就有一个相应的活动记录累筑于栈顶，此记录含有衔接数据、方式单元、部分变量、部分数组的内情向量和暂时任务单元等；在进入过程和执行过程的可执行语句之前，再把部分数组所需空间累筑于栈顶，从而构成过程任务时的完好数据区。栈式存储分配与活动记录留意，每个过程的活动记录的体积在编译时可以静态地确定。但由于允许含有可变数组，所以数组的大小只需在运转时才干知道。因数组区的大小不能预先获知，为了扩展方便，所以只能将数组区累筑于活动记录之上的当前栈顶。当一个过程任务终了前往时，它在栈顶的数据区(包括活动记录和数组区)也随即不复存在。对C言语来说，由于其不含可变数组，因此它的活动记录本身包含了部分数组的空间。图7–3和图7–4分别给出了C言语和含可变数组的某简单言语程序运转时的数据空间构造，即显示了主程序在调用了过程Q，Q又调用了过程R，且在R投入运转后的存储构造。

图7–3C言语程序的存储组织SP指示器总是指向执行过程活动记录的起点，而TOP指示器那么一直指向(已占用)栈顶单元。当进入一个过程时，TOP指向为此过程创建的活动记录的顶端；在分配数组区之后(假设有的话)，TOP又改为指向数组区(从而是该过程整个数据区)的顶端。图7–4含可变数组程序的存储组织C的活动记录含有以下几个区段(如图7–5所示)：(1)衔接数据(两项)：老SP值(即前一活动记录的起始地址)和前往地址；(2)参数个数；(3)方式单元(存放真实参数的值或地址)；(4)过程的部分变量(简单变量)、数组的内情向量和暂时任务单元。图7–5C过程的活动记录C言语不允许过程(函数)嵌套，也即不允许一个过程的定义出如今另一个过程的定义之内。因此，C言语的非部分变量仅能出如今源程序头，非部分变量可采用静态存储分配并在编译时确定它们的地址。由图7–5可知，过程的每一部分变量或形参在活动记录中的位置都是确定的；也就是说，这些变量或形参所分配的存储单元其地址都是相对于活动记录的基址SP的。因此，变量和形参运转时在栈上的绝对地址是：绝对地址=活动记录基址(SP)+相对地址对当前正在执行(即活动)的过程，其任何部分变量或形参X的援用均可表示为变址访问X[SP]。此处X代表X相对于活动记录基址的偏移量，这个偏移量(即相对数)在编译时可完全确定下来。过程的部分数组的内情向量的相对地址在编译时也同样可完全确定下来，一旦数据空间在过程里获得分配后，对数组元素的援用也就容易用变址的方式进展访问。过程的执行1．过程调用过程调用的中间代码序列为：parT1parT2

parTncallP,n由于此时TOP是指向被调用过程P之前的栈顶，而P的方式单元和活动记录起点之间的间隔是确定的(等于3，参见图7–5)，因此由调用过程给将要调用的过程P的活动记录(正在构成中)的方式单元传送实参值或实参地址，即每个parTi(i=1,2,…,n)可直接翻译成如下指令：(i+3)[TOP]=Ti /*传送参数值*/或(i+3)[TOP]=addr[Ti]/*传送参数地址*/而四元式callP,n那么翻译成：1[TOP]=SP/*维护现行SP*/3[TOP]=n /*传送参数个数*/JSRP /*转子指令，转向P过程的第一条指令*/过程P调用之前，先构造出P的活动记录部分内容，见图7–6所示。图7–6过程P调用前先构造P的活动记录部分内容2．过程进入转入过程P后，首先要做的任务是定义新活动记录的SP，维护前往地址和定义新活动记录的TOP值，即执行下述指令：SP=TOP+1/*定义新SP*/1[SP]=前往地址/*维护前往地址*/TOP=TOP+L/*定义新TOP*/其中，L是过程P的活动记录所需的单元数，这个数在编译时可静态地计算出来。对含可变数组(非C言语)的情况来说，由于过程可含可变数组且一切数组都分配在活动记录的顶上，所以紧接上述指令之后应是对数组进展存储分配的指令(假设含有部分数组)，这些指令是在翻译数组阐明时产生的。对每个数组阐明，相应的目的指令组将做以下几件任务：(1)计算各维的上、下限；(2)调用数组空间分配子程序，其参数是各维的上、下限和内情向量单元首地址。数组空间分配子程序计算并填好内情向量的一切信息，然后在TOP所指的位置之上留出数组所需的空间，并将TOP调整为指向数组区的顶端。 进入过程P后所做的任务如图7–7所示。以后，在过程段执行语句的任务过程中，凡援用方式参数、部分变量或数组元素都将以SP为基址进展相对访问。图7–7进入过程P后所做的任务表示3．过程前往C言语以及其它一些类似的言语含有return(E)方式的前往语句，其中E为表达式。假定E值已计算出来并存放在某暂时单元T中，那么此时即可将T值传送到某个特定的存放器中(调用过程将从这个特定的存放器中获得被调用过程P的结果)。剩下的任务就是恢复SP和TOP为进入过程P之前的原值(即指向调用过程的活动记录及任务空间)，并按前往地址实行无条件转移，即执行下述指令序列：TOP=SP–1 /*恢复调用过程的TOP值*/SP=0[SP] /*恢复调用过程的SP值*/X=2[TOP] /*将前往地址送X*/UJ0[X] /*无条件转移，即按X的地址前往到调用过程*/过程P的前往表示如图7–8所示。图7–8过程P的前往表示嵌套过程言语的栈式实现在简单程序文语实现中是允许过程的递归调用的，并且过程中可含有可变数组。如今，我们再加上一种功能，即允许过程的嵌套性。在讨论中，经常要用到过程定义的“嵌套层次〞(简称层数)这个概念。我们一直假定主程序的层数为0，因此主程序称为第0层过程。假设过程Q是在层数为i的过程P内定义的，并且P是包围Q的最小过程，那么Q的层数就为i+1。当编译程序处置过程阐明时，过程的层数将作为过程名的一个重要属性登记在符号表中。嵌套层次显示表(DISPLAY)和活动记录由于过程定义是嵌套的，因此一个过程可以援用包围它的任一外层过程所定义的变量或数组。也就是说，运转时，一个过程Q能够援用它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运转时必需知道它的一切外层的最新活动记录的地址。由于允许递归和可变数组的存在，过程的活动记录位置(即使是相对位置)也往往是变化的，因此必需设法跟踪每个外层过程的最新活动记录的位置。采用嵌套层次显示表DISPLAY，其优点是访问非部分量的速度较快。每进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表DISPLAY。假定如今进入的过程层数为i，那么它的DISPLAY表含有i+1个单元。此表本身是一个小栈，自顶而下每个单元依次存放着现行层、直接外层……直至最外层(第0层，即主程序层)的每一层的最新活动记录的起始地址。例如，令过程R的外层为Q，Q的外层为主程序P，那么过程R运转时的DISPLAY表内容如表7-1所示。表7-1DISPLAY表2R的现行活动记录的始址(SP的现行值)1Q的最新活动记录的始址0P的活动记录的始址由于过程的层数可静态确定，因此每个过程的DISPLAY表的体积在编译时即可知道。为了便于组织存储区和简化处置手续，我们把DISPLAY作为活动记录的一部分置于方式单元的上端，如图7–9所示。由于每个过程的方式单元数目在编译时是知道的，因此DISPLAY的相对地址d(相对于活动记录的起点)在编译时也是完全确定的。被调用过程为了建立本人的DISPLAY，就必需知道它的直接外层过程的DISPLAY，这意味着必需把直接外层的DISPLAY地址作为衔接数据之一(称为“全局DISPLAY地址〞)传送给被调用过程。于是，此时的衔接数据包含老SP值、前往地址和全局DISPLAY地址这三项内容。整个活动记录的构造如图7–9所示。图7–9活动记录构造存取链(也称静态链)方法。存取链方法引入一个称为存取链的指针，该指针作为活动记录的一项指向直接外层的最新活动记录的地址，这就意味着在运转时栈中的每个数据区(活动记录)之间又拉出一条链，这个链称为存取链。留意，运转时栈中数据区之间原先就存在一条链，即每个活动记录中所保管的老SP值这一项，它是指向调用该过程(子过程)的那个过程(父过程)的最新活动记录的起点，由此向前构成了一条SP链。为了区别于存取链，称SP链为控制链(也称动态链)，它记录了在运转中过程之间相互调用的关系。留意，控制链是动态的，而存取链是静态的。控制链记录了当前时辰程序中各过程相互调用的情况；而存取链那么一直记录着程序静态定义时该过程一切的直接外层(嵌套过程规定，内层过程只允许调用其静态定义时的外层过程阐明的变量和数组)；因此，存取链指出了一个过程的当前活动记录指向其直接定义的外层过程直至最外层的最新活动记录的起点。具有存取链的活动记录构造如图7–10所示。图7–10具有存取链的活动记录构造假定过程的嵌套关系：程序中每个过程的静态构造(嵌套层次)是确定的，如嵌套深度为2的过程R援用了非部分量a和b，其嵌套深度分别为0和1。从R的活动记录开场，分别沿着2 − 0 = 2和2−1=1个存取链向前查找，那么可找到包含这两个非部分量的活动记录。上述过程P调用S以及S调用Q运转时栈的变化过程如图7–11(a)、(b)所示。由图7–11可以看出，指针SP总是指向当前正在执行过程的活动记录起点，控制链(老SP)那么指向调用运转过程的父过程的活动记录起点。因此，当运转过程调用终了前往时，利用控制链老SP值可以得到调用前原父过程活动记录的起点。从程序的静态构造来看，P是S和Q的静态直接外层，所以，S和Q活动记录中的存取链均指向其直接外层P的活动记录起点。图7–11过程调用时运转栈的变化例1:某程序的构造如图7–12所示，其中A、B、C为过程名，请分别画出过程C调用A前后的栈顶活动记录。图7–12例中的程序构造表示解：过程C调用A前后的栈顶活动记录表示如图7–13所示。由图7–13可知，当过程C执行时，它可运用主程序、A、B和C过程所阐明的变量，且其外层嵌套的过程活动记录始址由DISPLAY表指出。当C调用A而使过程A执行时，我们看到此时的DISPLAY表已变为两项，即主程序和A过程本身；也即此时A只可运用主程序和A过程所阐明的变量。图7–13例1的运转栈与活动记录表示例2：在下面的PASCAL程序中，曾经第二次(递归地)进入了f，请给出第三次进入f后的运转栈及DISPLAY的表示图PROGRAMtest(input,output);VARK:integer;FUNCTIONf(n:integer):integer;BEGINIFn<=0THENf:=1解：第三次进入f后的运转栈及DISPLAY的表示图如图7–14所示。由于静态嵌套层次只需两层，故每一次递归调用产生的DISPLAY表只需两项，一项为哪一项test的SP(即0)，另一项为哪一项当前活动记录的SPi(i=1,2,3)。图7–14例2的运转栈及DISPLAY表示图堆式动态存储分配假设一种程序文语允许数据对象可以自在地分配和释放，或者不仅有过程而且有进程(process)这样的程序构造，那么由于空间的运用不一定遵照“先恳求后释放〞的原那么，那么栈式存储分配就不适用了。在这种情况下，通常运用一种称之为堆的动态存储分配方案。假定程序运转时有一个大的存储空间，需求时就从这个空间中借用一块，不用时再退还给它。由于借、还的时间先后不一，因此经过一段时间的运转后，这个大空间就必然被分割成如图7–15所示的许多小块，这些块有些正在运用，有些那么是空闲的(未被运用)。图7–15堆式存储分配表示对于堆式存储分配来说，需求处理两个问题：一是堆空间的分配，即当运转程序需求一块空间时应分配哪一块给它；另一个问题是分配空间的回收，由于前往堆的不用空间是按恣意次序进展的，所以需求研讨专门的回收分配战略。在许多言语中都有显式的堆空间分配和回收语句或函数，如PASCAL言语中的new和dispose、C言语中的malloc和free以及C++言语中的new和delete。堆式存储管理的方法的简单讨论当运转程序要求一块体积为N的存储空间时应如何分配？从实际上讲，这时应从比N稍大一些的空闲块中取出N个单元予以分配，这种做法的目的是坚持较大的空闲块以备未来之需。但这种方法实现起来难度较大，实践中采用的方法是：扫描空闲块链并在初次遇到的比N大的空闲块中取出N个单元进展分配。假设找不到一块比N大的空闲块，但一切空闲块的总和却比N大，这时就需求用某种方法使这些空闲块拼接在一同，构成一个可分配的延续空间。假设一切空闲块的总和都不及N大，那么需求采用更复杂的方法，如废品回收技术(即寻觅那些运转程序已不运用但仍未释放的存储块或运转程序目前很少运用的存储块)，把这些存储块回收后再重新分配。

可以采用多种战略进展堆式动态存储管理。运用可利用空间表进展动态分配的方法可利用空间表是指将一切空闲块用一张表记录下来，表的构造可以是目录表，也可以是链表，其构造分别如图7–16(b)、(c)所示。图7–16内存形状和可利用空间表运用可利用空间表进展动态存储分配的方法又可分为如下两种：(1)定长块的管理。最简单的堆式存储管理方法是采用定长块的管理方法，即将堆存储空间在初始化时就划分成大小一样的假设干块，将各个块经过链表链接起来构成一个单向线性链表。由于各块大小一样，故分配时无需查找，只需将头指针所指的第