搜索
第九章运行时存储空间组织编译程序的最终目的是将源程序翻译成等价的目标程序。为了达到此目的，除了进行词法、语法、语义分析外，在生成目标代码之前，需要把程序静态的正文和实现这个程序运行时的活动联系起来，以便弄清楚将来在代码运行时，源程序中的各个变量、常量等用户定义的量是如何存放的，如何去访问它。在程序的运行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。§9.1目标程序运行时的活动9.1.1过程的活动先讨论一个过程的静态源程序和它的目标程序在运行时的活动之间的关系。过程定义仅仅是一个说明；而过程调用是过程体的一次执行。过程的活动：是指该过程的一次执行。即每次执行一个过程体，就产生该过程体的一个活动。一个活动的生存期：指从执行该过程体的第一步操作到最后一步操作之间的这段时间。活动之间的关系一个过程是递归的：如果该过程在还没有退出当前的活动时，又开始了它的一次新的活动。即在某个时刻，可能有该过程的几个活动在活跃着。如果a和b是两个过程的活动，则它们的生存期或者是不重叠的，或者是嵌套的。9.1.2参数传递如何将实际参数传递给相应的形式参数？传地址（callbyreference）传值（callbyvalue）传名（callbyname）/宏复制-恢复（copy-restore）/得结果§9.2运行时存储器的划分9.2.1运行时存储器的划分目标代码静态数据栈……堆管理过程的活动存放动态数据9.2.2活动记录为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这个存储块就称为活动记录。用一个活动记录表示该活动的相关信息，并将其压入栈。临时单元内情向量局部变量形式单元静态链动态链返回地址SPTOP活动记录的大小在编译时可确定。9.2.3存储分配策略不同的编译程序关于数据空间的存储分配策略可能不同。常用的存储分配策略有：静态分配策略栈式动态分配策略堆式动态分配策略由关于名称的作用域和生成期的定义规则决定。§9.3静态存储分配如果在编译时就能确定一个程序在运行时所需的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种分配方法叫做“静态分配”。§9.4简单的栈式存储分配先考虑一种简单的程序语言的实现。假设该语言不允许过程嵌套，但允许过程递归调用。例如：C语言的程序结构intx,y;main(){inta,b;……}voidR(){charch;……}charQ(){floatx;……}这类语言，关于局部名称的存储分配，可以直接采用栈式存储分配策略。使用栈式存储分配，即：把存储组成一个栈，运行时，每当进入一个过程时，就把它的活动记录压入栈，从而形成过程工作时的数据区。一个过程的活动记录的大小在编译时是可静态确定的，当该活动结束时，则其活动记录也将出栈。例如：图9.13C语言程序的存储组织（P255）9.4.1C语言的活动记录C语言的活动记录有四项：连续数据（老SP值返回地址）参数个数形式参数过程的局部变量、数组内情向量、临时工作单元其结构形式见：图9.14（P256）§9.5嵌套过程语言的栈式实现例如：图9.15中PASCAL程序。(P258)0P1Q1S2R9.5.1非局部名字的访问的实现由于允许过程定义是嵌套的，则一个过程可以引用包围它的任一外层过程中所定义的变量或数组。为了在活动记录中查找非局部名字所对应的存储空间，就必须知道它的所有外层过程的最新活动记录的地址。一、静态链临时单元内情向量局部变量形式单元形参个数静态链返回地址动态链SPTOP直接外层的最新活动记录的基地址调用前的活动记录的基地址例如图.15程序运行时栈的变化过程。ic00返回地址0xa0返回地址0SPTOP①P调用S时S的活动记录P的活动记录109876543210ib10返回地址5…………SPTOP②S调用R时S的活动记录P的活动记录16151413121105R的活动记录二、嵌套层次形式表为了提高访问非局部量的速度，还可引用一个指针数组，即display表。临时单元内情向量局部变量display形式单元形参个数全局display返回地址动态链SPTOP调用前的活动记录的基地址§9.6堆式动态存储分配问题：如果一个程序语言允许用户自由的申请或退还数据空间（如new/delete），或者不仅有过程而且还有进程的程序结构，这种情况下，栈式的动态分配就不适用了，而通常使用堆式的动态存储分配方案。9.6.1堆式动态存储分配的实现定长块管理变长块管理分配回收首次满足法随机(查栈表)直接插入表头最优满足法请求内存范围较广(查找)最差满足法请求内存范围较窄(不查找)9.6.2隐式存储回收（用户程序和回收子程序并行工作）存储块格式：标记:对已分配的块跟踪程序中各指针的访问路径，如果某个块被访问过，就给这个块加一个标记。回收：所有未加标记的存储块回收到一起，并插入空闲块链表中，然后消除在存储块中所加的全部标记。优点：防止死块产生，缺点：开销大，：解决：当空闲块降到某值时开始回收。块长度访问计数标记指针用户使用空间