第6章运行时存储空间组织

第6章运行时存储空间组织第6章运行时存储空间组织6.1静态存储分配6.2简单的栈式存储分配6.3嵌套过程语言的栈式实现6.4堆式动态存储分配6.5参数传递补遗第6章运行时存储空间组织6.1静态存储分配如果在编译时就能够确定一个程序在运行时所需的存储空间大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址，存储空间的这种分配方法叫做静态分配。第6章运行时存储空间组织对FORTRAN语言来说，其特点是不允许过程有递归性，每个数据名所需的存储空间大小都是常量(即不允许含可变体积的数据，如可变数组)，并且所有数据名的性质是完全确定的(不允许出现在运行时再动态确定其性质的名字这种情况)。这些特点确保整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配。静态存储分配是一种最简单的存储管理。一般而言，适于静态存储分配的语言必须满足以下条件：第6章运行时存储空间组织(1)数组的上下界必须是常数；(2)过程调用不允许递归；(3)不允许采用动态的数据结构(即在程序运行过程中申请和释放的数据结构)。第6章运行时存储空间组织满足这些条件的语言除了FORTRAN之外，还有BASIC等语言。在这些语言中，编译程序可以完全确定程序中数据项所在的地址(通常为相对于各数据区起始地址的位移量)。由于过程调用不允许递归，因此数据项的存储地址就与过程相联系。过程调用所使用的局部数据区可以直接安排在过程的目标代码之后，并把各数据项的存储地址填入相关的目标代码中，以便在过程运行时访问这个局部数据区。在此，不存在对存储区的再利用问题；目标程序执行时不必进行运行时的存储空间管理，过程的进入和退出变得极为简单。第6章运行时存储空间组织FORTRAN语言的静态存储管理特点是FORTRAN程序中的各程序段均可独立地进行编译。在编译过程中，给程序中的变量或数组分配存储单元的一般做法是：为每一个变量(或数组)确定一个有序的整数对；其中，第一个整数用来指示数据区(局部数据区或公用区)的编号，第二个整数则用来指明该变量(或数组)所对应的存储起始单元相对于其所在数据区起点的位移(即相对于数据区起点的地址)；并将这一对整数填入符号表相应登记项的信息栏中。至于各数据区的起始地址在编译时可暂不确定，待各程序段全部编译完成之后，再由连接装配程序最终确定，并将各程序段的目标代码组装成一个完整的目标程序。第6章运行时存储空间组织一个FORTRAN程序段的局部数据区可由图6–1所示的项目组成。其中，隐参数是指过程调用时的连接信息(不在源程序中明显出现)，如调用时的返回地址、调用时寄存器的保护等；形式单元用来存放过程调用时形参与实参结合的实参地址或值。第6章运行时存储空间组织图6–1一个FORTRAN程序段的局部数据区临时变量数组简单变量形式单元寄存器保护区隐参数返回地址第6章运行时存储空间组织6.2简单的栈式存储分配我们首先考虑一种简单程序语言的实现，这种语言没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用，允许过程含有可变数组。例如，C语言除不允许含有可变数组外，就是这样一种语言。C语言的程序结构如下：第6章运行时存储空间组织全局数据说明main( ){main中的数据说明}voidR( ){R中的数据说明}第6章运行时存储空间组织voidQ(){Q中的数据说明}第6章运行时存储空间组织例如，下面计算n！的C语言程序就是一个递归调用的程序，它的执行过程可以用栈来实现。#include“stdio.h”longfactorial(intn){if(n1)return(n*factorial(n−1));elsereturn(1);}第6章运行时存储空间组织main( ){intnum;do{scanf(“%d”,&num);if(num=0&&num15)printf(“%d\n”,factorial(num));elseprintf(“error!\n”);}while(num=0);}第6章运行时存储空间组织6.2.1栈式存储分配与活动记录使用栈式存储分配法意味着程序运行时，每当进入一个过程(或函数)就有一个相应的活动记录累筑于栈顶，此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等；在进入过程和执行过程的可执行语句之前，再把局部数组所需空间累筑于栈顶，从而形成过程工作时的完整数据区。第6章运行时存储空间组织注意，每个过程的活动记录的体积在编译时可以静态地确定。但由于允许含有可变数组，所以数组的大小只有在运行时才能知道。因数组区的大小不能预先获知，为了扩充方便，所以只能将数组区累筑于活动记录之上的当前栈顶。当一个过程工作完毕返回时，它在栈顶的数据区(包括活动记录和数组区)也随即不复存在。第6章运行时存储空间组织对C语言来说，由于其不含可变数组，因而它的活动记录本身包含了局部数组的空间。图6–2和图6–3分别给出了C语言和含可变数组的某简单语言程序运行时的数据空间结构，即显示了主程序在调用了过程Q，Q又调用了过程R，且在R投入运行后的存储结构。SP指示器总是指向执行过程活动记录的起点，而TOP指示器则始终指向(已占用)栈顶单元。当进入一个过程时，TOP指向为此过程创建的活动记录的顶端；在分配数组区之后(如果有的话)，TOP又改为指向数组区(从而是该过程整个数据区)的顶端。第6章运行时存储空间组织SPTOPR的活动记录Q的活动记录main的活动记录全局数据区图6–2C语言程序的存储组织第6章运行时存储空间组织R的数组区R的活动记录Q的数组区Q的活动记录主程序全局数据区TOPSP图6–3含可变数组程序的存储组织第6章运行时存储空间组织C的活动记录含有以下几个区段(如图6–4所示)：(1)连接数据(两项)：老SP值(即前一活动记录的起始地址)和返回地址；(2)参数个数；(3)形式单元(存放实在参数的值或地址)；(4)过程的局部变量(简单变量)、数组的内情向量和临时工作单元。第6章运行时存储空间组织图6–4C过程的活动记录1TOP临时工作单元内情向量简单变量形式单元参数个数返回地址老SPSP20第6章运行时存储空间组织C语言不允许过程(函数)嵌套，也即不允许一个过程的定义出现在另一个过程的定义之内。因此，C语言的非局部变量仅能出现在源程序头，非局部变量可采用静态存储分配并在编译时确定它们的地址。由图6–4可知，过程的每一局部变量或形参在活动记录中的位置都是确定的；也就是说，这些变量或形参所分配的存储单元其地址都是相对于活动记录的基址SP的。因此，变量和形参运行时在栈上的绝对地址是：绝对地址=活动记录基址(SP)+相对地址第6章运行时存储空间组织于是，对当前正在执行(即活动)的过程，其任何局部变量或形参X的引用均可表示为变址访问X[SP]。此处X代表X相对于活动记录基址的偏移量，这个偏移量(即相对数)在编译时可完全确定下来。过程的局部数组的内情向量的相对地址在编译时也同样可完全确定下来，一旦数据空间在过程里获得分配后，对数组元素的引用也就容易用变址的方式进行访问。第6章运行时存储空间组织6.2.2过程的执行1．过程调用过程调用的四元式序列为：parT1parT2parTncallP,n第6章运行时存储空间组织由于此时TOP是指向被调用过程P之前的栈顶，而P的形式单元和活动记录起点之间的距离是确定的(等于3，参见图6–4)，因而由调用者过程给将要调用的过程P的活动记录(正在形成中)的形式单元传递实参值或实参地址，即每个parTi(i=1,2,…,n)可直接翻译成如下指令：(i+3)[TOP]=Ti/*传递参数值*/或(i+3)[TOP]=addr[Ti]/*传递参数地址*/第6章运行时存储空间组织而四元式callP,n则翻译成：1[TOP]=SP/*保护现行SP*/3[TOP]=n/*传递参数个数*/JSRP/*转子指令，转向P过程的第一条指令*/过程P调用之前，先构造出P的活动记录部分内容，见图6–5所示。第6章运行时存储空间组织参数个数nTOP＋3SPT2T1现行SP值P的活动记录调用过程TOP43210……图6–5过程P调用前先构造P的活动记录部分内容第6章运行时存储空间组织2．过程进入转入过程P后，首先要做的工作是定义新活动记录的SP，保护返回地址和定义新活动记录的TOP值，即执行下述指令：SP=TOP+1/*定义新SP*/1[SP]=返回地址/*保护返回地址*/TOP=TOP+L/*定义新TOP*/其中，L是过程P的活动记录所需的单元数，这个数在编译时可静态地计算出来。第6章运行时存储空间组织对含可变数组(非C语言)的情况来说，因为过程可含可变数组且所有数组都分配在活动记录的顶上，所以紧接上述指令之后应是对数组进行存储分配的指令(如果含有局部数组)，这些指令是在翻译数组说明时产生的。对每个数组说明，相应的目标指令组将做以下几件工作：(1)计算各维的上、下限；(2)调用数组空间分配子程序，其参数是各维的上、下限和内情向量单元首地址。第6章运行时存储空间组织数组空间分配子程序计算并填好内情向量的所有信息，然后在TOP所指的位置之上留出数组所需的空间，并将TOP调整为指向数组区的顶端。 进入过程P后所做的工作如图6–6所示。此后，在过程段执行语句的工作过程中，凡引用形式参数、局部变量或数组元素都将以SP为基址进行相对访问。第6章运行时存储空间组织P的数组区…返回地址P的活动记录(长度为L)1调用过程SPTOP0图6–6进入过程P后所做的工作示意第6章运行时存储空间组织3．过程返回C语言以及其它一些相似的语言含有return(E)形式的返回语句，其中E为表达式。假定E值已计算出来并存放在某临时单元T中，则此时即可将T值传送到某个特定的寄存器中(调用过程将从这个特定的寄存器中获得被调用过程P的结果)。剩下的工作就是恢复SP和TOP为进入过程P之前的原值(即指向调用过程的活动记录及工作空间)，并按返回地址实行无条件转移，即执行下述指令序列：第6章运行时存储空间组织TOP=SP–1/*恢复调用过程的TOP值*/SP=0[SP]/*恢复调用过程的SP值*/X=2[TOP]/*将返回地址送X*/UJ0[X]/*无条件转移，即按X的地址返回到调用过程*/一个过程也可通过它的end语句(对C语言则是该过程(函数)体结束时的“}”)自动返回。如果此过程是一个函数过程，则按上述办法传递结果值，否则仅直接执行上述返回指令序列。过程P的返回示意如图6–7所示。第6章运行时存储空间组织SPTOP…返回地址老SPP空间调用过程空间图6–7过程P的返回示意第6章运行时存储空间组织6.3嵌套过程语言的栈式实现在简单程序语言实现中是允许过程的递归调用的，并且过程中可含有可变数组。现在，我们再加上一种功能，即允许过程的嵌套性。从结构上看，PASCAL就是这样的一种语言；但由于PASCAL含有“文件”和“动态变量”，因此，它的存储分配不能简单地用栈式方法来实现。采用PASCAL的一个子集，例如去掉“文件”和“动态变量”这种数据类型，那就可以用我们下面将要讨论的方法实现存储分配。第6章运行时存储空间组织6.3.1嵌套层次显示表(DISPLAY)和活动记录在讨论中，常常要用到过程定义的“嵌套层次”(简称层数)这个概念。我们始终假定主程序的层数为0，因此主程序称为第0层过程。如果过程Q是在层数为i的过程P内定义的，并且P是包围Q的最小过程，则Q的层数就为i+1。当编译程序处理过程说明时，过程的层数将作为过程名的一个重要属性登记在符号表中。第6章运行时存储空间组织由于过程定义是嵌套的，因而一个过程可以引用包围它的任一外层过程所定义的变量或数组。也就是说，运行时，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运行时必须知道它的所有外层的最新活动记录的地址。由于允许递归和可变数组的存在，过程的活动记录位置(即使是相对位置)也往往是变迁的，因而必须设法跟踪每个外层过程的最新活动记录的位置。第6章运行时存储空