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

1、第第6章章 运行时存储空间组织运行时存储空间组织前面讨论了对源程序进行静态分析静态分析的编编译程序译程序的不同阶段, 这些分析仅取决于源程序本身源程序本身的特性, 与目标机目标机及目标机目标机的操作系统特性的操作系统特性无关无关。但编译程序的最终目的是把源程序翻译成能在目标机目标机上运行的目标程序目标程序, 这就要求编译程序不仅能生成目标代码, 还要在生成目标代码生成目标代码之前之前进行目标程序运运行环境的设计行环境的设计和数据空间的分配数据空间的分配。例如, 目标程序运行时运行时, 源程序中各种变量、常量变量、常量等如何在存储器中存放存放? 如何对它们进行访问访问? 源程序中各种变量、常量的

2、作用域作用域和生存期生存期如何确定? 递归过程递归过程的数据空间的数据空间如何在运行过程中实现动态的分配动态的分配? 这些问题对于编译程序是非常复杂又十分重要的。分配分配目标程序数据空间的基本策略数据空间的基本策略:1. 静态分配策略静态分配策略 若一个程序语言不允许有递归过程不允许有递归过程, 不允许含可变体积的不允许含可变体积的数据项数据项或待定待定性质的名字性质的名字, 则在编译时能完全确定完全确定其程序的每个数据项目的存储空间位置, 这种策略叫静态分配策略静态分配策略。例如, FORTRAN语言2. 栈式动态分配策略栈式动态分配策略若程序语言允许有递归过程允许有递归过程和可变数组可变数

3、组, 则程序数据空间的分配数据空间的分配需采用动态动态策略策略, 即在程序运行时进行数据空间的分配, 此时目标程序可用栈栈作为动态的数据空间。程序运行时运行时, 每当进入一个子程序, 其所需的数据空间就动态地分配于栈顶分配于栈顶, 一旦该子程序运行结束运行结束, 其所占用的空间就释释放放, 这种方法叫栈式动态分配策略栈式动态分配策略。3. 堆式动态分配策略堆式动态分配策略若程序语言允许用户动态地动态地申请和释申请和释放放存储空间, 并且申请和释放之间不一不一定定遵守“先申请后释放先申请后释放”的原则, 则必须让运行程序拥有一个大存储区(堆堆), 申请时从堆中分配一块, 释放时退还给堆, 这种方

4、法叫堆式动态分配策略堆式动态分配策略。6.1 静态静态存储分配存储分配 6.2 简单的简单的栈式栈式存储分配存储分配 6.3 嵌套过程语言的栈式实现嵌套过程语言的栈式实现 6.4 堆式堆式动态存储分配动态存储分配 6.5 参数传递补遗参数传递补遗6.1 静态存储分配静态存储分配若编译时编译时能确定程序运行时所需存储空间的大小, 则编译编译时时能安排好程序运行时的全部数据空间, 并能确定每个数据项的地址, 这种存储分配方法叫做静态分配静态分配。FORTRAN语言不允许不允许有递归递归过程,每个数据名所需存储空间的大小是常量(即不不允许允许含可变体积可变体积的数据), 且所有数据名的性质是完全确定

5、的(不允许不允许出现动态动态确定其性质的数据名)。故FORTRAN程序可静态分配存储空间。(1) 数组的上下界上下界必须是常数是常数;(2) 过程调用不允许递归不允许递归;(3)不允许不允许采用动态动态数据结构, 即程序运行过程中不允许申请和释放存储空间。适于静态静态存储分配存储分配的语言需满足的条件:满足条件的语言有FORTRAN, BASIC等。这些语言的编译程序可完全确定可完全确定程序中数据项所在地址数据项所在地址(通常为相应于各数据区起始地址的位移量)。由于过程调用不允许递归, 因此数据项的存储地址与过程相联系。过程调用所使用的过程调用所使用的局部数据区局部数据区直接安排在过程的目标代

6、码后过程的目标代码后, 并把各数据项的存储地址存储地址填入相关的目标代码, 以便在过程运行时访问访问这个局部数据区。采用静态存储分配时, 不存在对存储不存在对存储区的再利用问题区的再利用问题, 目标程序执行时不必进行运行时存储空间管理运行时存储空间管理, 因此, 过程进入和退出很简单。FORTRAN语言的静态存储管理特点使FORTRAN程序中各程序段可独立程序中各程序段可独立地进行编译地进行编译。在编译过程中, 给程序中变量变量或数数组组分配存储单元的一般方法为: 为每个变量变量(或数组数组)确定一个有序有序整数对整数对, 并把这一对整数这一对整数填入符号表相应登记项的信息栏中。其中第一个整数

7、第一个整数指示数据区的编号编号, 第二个整数第二个整数指明该变量(或数组)所对应的存储起始单元存储起始单元相应于其所在数据区起点的位移位移。各数据区的起始地址在编译时暂不确各数据区的起始地址在编译时暂不确定定, 待各程序段全部编译完后, 再由连连接装配程序接装配程序最终确定, 并将各程序段的目标代码组装成一个完整的目标程序。FORTRAN程序段的局部数据区局部数据区可由图6-1所示的项目组成: 临时变量临时变量数组数组简单变量简单变量形式单元形式单元寄存器保护区寄存器保护区隐隐参参数数 返回地址返回地址图图6-1 一个一个FORTRAN程序段的程序段的局部数据区局部数据区隐参数隐参数指过程调用

8、时的连接信息, 如返回地址、寄存器保护区等; 形式单元形式单元用来存放过程调用时与形参对应的实参地址或值。首先考虑一种简单程序语言: 没有没有分程序结构分程序结构, 过程定义不允许嵌套不允许嵌套, 但允许允许过程的递归调用递归调用, 允许允许过程含可变数组含可变数组。C语言除了不允许含可变数组外, 就是这样一种语言。6.2 简单的栈式存储分配简单的栈式存储分配C语言的程序结构语言的程序结构如下:全局数据说明全局数据说明main() main中的数据说明中的数据说明void R() R中的数据说明中的数据说明 void Q( ) Q中的数据说明中的数据说明 计算n!的C程序的执行过程可用栈栈实现

9、:# include “stdio.h”long factorial (int n) if (n1) return (n*factorial(n-1); else return (1); main () int num; do scanf (“%d” , &num); if (num=0 & num =0);6.2.1 栈式存储分配与活动记录栈式存储分配与活动记录使用栈式存储分配法意味着程序运行时, 每当进入一个过程每当进入一个过程(或函数或函数)就有一就有一个相应的活动记录累筑于栈顶个相应的活动记录累筑于栈顶, 此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时

10、工作单元等。在执行可执行语句执行可执行语句之前之前, 把把局部数组局部数组所需空间所需空间累筑于栈顶累筑于栈顶, 从而形成过程工作时的完整数据区。注意: (1)每个过程的活动记录的体积活动记录的体积在编译时可以静态地确定。(2)由于允许含有可变数组可变数组, 故数组的大数组的大小小在运行时运行时才能知道。(3)由于可变数组的大小不能预先获知, 为了扩充方便, 把数组区数组区累筑于活动记录之上的当前栈顶。(4)当一个过程执行完毕返回时, 它在栈顶的数据区(包括活动记录活动记录和数组区数组区)随即不复存在。由于C语言语言不含可变数组不含可变数组, 故故其活动活动记录记录本身包含了局部数组的空间本身

11、包含了局部数组的空间。图6-2和图6-3分别给出了C语言语言和含含可变数组的某简单语言可变数组的某简单语言程序运行时的数据空间结构, 即显示了主程序调用了过程Q, Q调用了过程R, R投入运行投入运行后后的存储结构。SPTOPR的活动记录的活动记录Q的活动记录的活动记录main的活动记录的活动记录全局数据区全局数据区图图6-2 C语言程序语言程序的的存储组织存储组织 SP总是指向执行过程活动记录的起点, TOP始终指向栈顶单元。当进入进入一个过程时, SP指向为此过程创建的活动记录的起点, TOP指向为此过程创建的活动记录的顶端。当进入进入一个过程时, SP指向为此过程创建的活动记录的起点,

12、TOP指向为此过程创建的活动记录的顶端; 若含有可变数组可变数组, 则分配数组区后, TOP又改为指向数组区的顶端。图6-3 含可变数组的程序含可变数组的程序的存储组织R的数组区的数组区R的活动记录的活动记录Q的数组区的数组区Q的活动记录的活动记录TOPSPmain的的数组区数组区main的的活动记录活动记录主程序全局数据区主程序全局数据区C的活动记录含以下几个区段的活动记录含以下几个区段:(1)连接数据连接数据(两项): 老老SP值值和返回地址返回地址, 其中老老SP为前一活动记录的起始地址;(2)参数个数参数个数;(3)形式单元形式单元(存放实参的值或地址);(4)过程的局部变量局部变量(

13、简单变量)、数组的数组的内情向量内情向量和临时工作单元临时工作单元。 1TOP临时工作单元临时工作单元内情向量内情向量简单变量简单变量形式单元形式单元参数个数参数个数返回地址返回地址老老SPSP20图6-4 C过程的活动记录过程的活动记录C语言不不允许函数嵌套允许函数嵌套, 即不允许一个过程的定义出现在另一过程的定义之内。因此, C语言的语言的非局部变量非局部变量仅能出仅能出现在源程序头现在源程序头, 非局部变量可采用静态静态存储存储并在编译时确定它们的地址。C语言中, 过程的每个局部变量或形参每个局部变量或形参在活动记录中的在活动记录中的位置是确定的位置是确定的。因此, 变量和形参运行时运行

14、时在栈上的绝对地址绝对地址:绝对地址绝对地址=活动记录基址活动记录基址(SP)+相对地址相对地址对于当前正在执行的过程, 其任一局局部变量部变量或形参或形参A的引用均可表示为变址访问XSP, 其中X代表A相对于活动记录基址的偏移量偏移量, 这个偏移量在编译时可完全确定下来。过程的局部数组的内情向量局部数组的内情向量的相对地址在编译时同样可完全确定下来。当数据空间在过程中获得分配后, 对数组元素的引用易于用变址方式访问。6.2.2 过程的执行过程的执行1. 过程调用过程调用过程调用的四元式序列为: par T1 par T2 par Tn call P, n由于此时TOP指向被调过程P之前的栈顶

15、, 而P的形式单元形式单元与活动记录起点活动记录起点之间的距离是确定的(等于3), 因而由调用过程调用过程给被调过程被调过程P的活动记录活动记录(正在形成)的形式形式单元单元传递传递实参值实参值或或实参地址实参地址, 即每个par Ti(i=1, n)可直接翻译成如下指令: (i+3)TOP=Ti /传参数值 或 (i+3)TOP=addrTi /参数地址四元式 call P,n 翻译成: 1TOP=SP /保护现行SP 3TOP=n /传递参数个数 JSR P /转向P过程参数个数参数个数nTOP+3SPT2T1现行现行SP值值P的活动记录调用过程TOP43210图6-5 调用过程P之前先构

16、造P 的活动记录的部分内容2. 过程进入过程进入转入过程P后, 首先要做的是定义新活新活动记录的动记录的SP, 保护返回地址返回地址和定义新新活动记录的活动记录的TOP值值, 即执行下述指令:SP = TOP+1 /定义新SP1SP=返回地址 /保护返回地址TOP=TOP+L /定义新TOP其中L是过程P的活动记录所需的单元数, 该数在编译时可静态计算出。对含可变数组含可变数组的情况, 紧接上述指令之后是对数组进行存储分配的指令。对数组进行存储分配的指令对数组进行存储分配的指令是在翻译翻译数组说明数组说明时产生的, 对每个数组说明每个数组说明, 相应的目标指令组将做以下工作: (1)计算各维的

17、上下限; (2)调用数组空间分配子程序数组空间分配子程序。数组空间分配子程序数组空间分配子程序计算并填好内情计算并填好内情向量的所有信息向量的所有信息, 然后在TOP所指位置之上留出数组所需空间留出数组所需空间, 并将TOP调整为指向数组区顶端。P的数组区返回地址P的活动记录(长度为L)1调用过程SPTOP0此后, 在执行语句过程中, 凡引用引用形参、局部变量或数组元素都以SP为基址进行相对访问。进入过程P后所做工作如下图:3. 过程返回C语言及其它一些语言含return(E)形式的返回语句。假定E值值已计算出来并存放在某临时单元T中, 则此时可将T值传送到某个特定寄存器中(调用过程将从这个特

18、定寄存器中获得被调过程P的结果)。剩下的工作是恢复恢复SP和TOP, 并按返返回地址回地址实行无条件转移转移, 即执行下述指令序列:TOP= SP1 /恢复调用过程的TOP值SP=0SP /恢复调用过程的SP值X=2TOP /将返回地址返回地址送XUJ 0X /无条件转移到调用过程一个过程也可通过它的end语句(C语言为)自动返回。若此过程是一个函数函数, 则按上述办法传递结果值, 否则仅直接执行上述返回指令序列。SPTOP返回地址老SPP空间调用过程空间图6-7 过程P的返回示意图6.3 嵌套过程语言的栈式实现嵌套过程语言的栈式实现在简单程序语言实现中允许过程的递允许过程的递归调用归调用,

19、且过程中可含可变数组可含可变数组。现在再加上一种功能-允许过程的嵌套允许过程的嵌套性性, 如PASCAL。由于PASCAL含有文件和动态变量, 故它的存储分配不能简单地用栈式方法实现。考虑考虑PASCAL的一个子集的一个子集, 即去掉文件和动态变量文件和动态变量这两种数据类型, 则可用下述方法实现存储分配:6.3.1 嵌套层次显示表和活动记录嵌套层次显示表和活动记录假定主程序的层数为0。若过程Q是在层数为i的过程P内定义的, 且P是包围Q的最小过程, 则Q的层数为i+1。编译程序处理过程说明时, 过程的层过程的层数数作为过程名的一个重要属性登记在符号表中。由于过程定义是嵌套的, 因而一个过程可以引用引用包围它的任一外层过程所定义的变量或数组, 即运行时运行时过程Q可引用它的任一外层过程P的最新活动记录中的某些数据。因此, 过程Q运行时必须知道它的所有外层的最新活动记录的地址。由于允许递归和可变数组的存在, 过程的活动记录位置往往是变迁的, 因而必须设法跟踪每个外层过程的最新活动记录的位置。一种常用的跟踪每个外层过程最新活动记录位置的有效办法: 每进入进入一个过程后, 在建立它的活动记录区的同时建立一张建立