第九章 运行时存储空间组织bfex.pptx

《第九章 运行时存储空间组织bfex.pptx》由会员分享，可在线阅读，更多相关《第九章 运行时存储空间组织bfex.pptx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章 运行时存储空间组织 编译程序的最终目的是将源程序翻译成等价的目标程序。为了达到此目的，除了进行词法、语法、语义分析外，在生成目标代码之前，需要把程序静态的正文和实现这个程序运行时的活动联系起来，以便弄清楚将来在代码运行时，源程序中的各个变量、常量等用户定义的量是如何存放的，如何去访问它。在程序的运行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。9.1 目标程序运行时的活动9.1.1 过程的活动 先讨论一个过程的静态源程序和它的目标程序在运行时的活动之间的关系。过程定义仅仅是一个说明；而过程调用是过程体的一次执行。过程的活动：是指该过程的一次执行。即每次执行一个过程体，就产生

2、该过程体的一个活动。一个活动的生存期：指从执行该过程体的第一步操作到最后一步操作之间的这段时间。活动之间的关系一个过程是递归的：如果该过程在还没有退出当前的活动时，又开始了它的一次新的活动。即在某个时刻，可能有该过程的几个活动在活跃着。如果 a 和 b 是两个过程的活动，则它们的生存期或者是不重叠的，或者是嵌套的。9.1.2 参数传递如何将实际参数传递给相应的形式参数？传地址（call by reference）传值（call by value）传名（call by name）/宏 复制-恢复（copy-restore）/得结果9.2 运行时存储器的划分9.2.1 运行时存储器的划分 目标代码

3、 静态数据 栈 堆管理过程的活动存放动态数据9.2.2 活动记录 为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这个存储块就称为活动记录。用一个活动记录表示该活动的相关信息，并将其压入栈。临时单元 内情向量 局部变量 形式单元 静态链 动态链 返回地址SPTOP活动记录的大小在编译时可确定。9.2.3 存储分配策略 不同的编译程序关于数据空间的存储分配策略可能不同。常用的存储分配策略有：静态分配策略 栈式动态分配策略 堆式动态分配策略 由关于名称的作用域和生成期的定义规则决定。9.3 静态存储分配 如果在编译时就能确定一个程序在运行时所需的存储空间的大小，则在编译时就能够安排好目

4、标程序运行时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种分配方法叫做“静态分配”。9.4 简单的栈式存储分配 先考虑一种简单的程序语言的实现。假设该语言不允许过程嵌套，但允许过程递归调用。例如：C语言的程序结构 int x,y;main()int a,b;void R()char ch;char Q()float x;这类语言，关于局部名称的存储分配，可以直接采用栈式存储分配策略。使用栈式存储分配，即：把存储组成一个栈，运行时，每当进入一个过程时，就把它的活动记录压入栈，从而形成过程工作时的数据区。一个过程的活动记录的大小在编译时是可静态确定的，当该活动结束时，则其活动记录也将

5、出栈。例如：图9.13 C语言程序的存储组织 （P255）9.4.1 C语言的活动记录 C语言的活动记录有四项：连续数据（老SP值 返回地址）参数个数形式参数过程的局部变量、数组内情向量、临时工作单元 其结构形式见：图9.14 （P256）9.5 嵌套过程语言的栈式实现 例如：图9.15中PASCAL程序。(P258)0 P1 Q1 S2 R9.5.1 非局部名字的访问的实现 由于允许过程定义是嵌套的，则一个过程可以引用包围它的任一外层过程中所定义的 变量或数组。为了在活动记录中查找非局部名字所对应的存储空间，就必须知道它的所有外层过程的最新活动记录的地址。一、静态链临时单元 内情向量 局部变

6、量形式单元形参个数 静态链返回地址 动态链SPTOP直接外层的最新活动记录的基地址调用前的活动记录的基地址例如 图.15 程序运行时栈的变化过程。i c 0 0返回地址 0 x a 0返回地址 0SPTOPP 调用S 时S的活动记录P的活动记录10 9 8 7 6 54 3 2 1 0 i b 1 0返回地址 5 SPTOP S 调用R 时S的活动记录P的活动记录16 1514 13 12 11 0 5R的活动记录二、嵌套层次形式表 为了提高访问非局部量的速度，还可引用一个指针数组，即 display表。临时单元 内情向量 局部变量displaydisplay形式单元形参个数全局 displa

7、ydisplay返回地址 动态链SPTOP调用前的活动记录的基地址9.6 堆式动态存储分配问题：如果一个程序语言允许用户自由的申请或退还数据空间（如new/delete），或者不仅有过程而且还有进程的程序结构，这种情况下，栈式的动态分配就不适用了，而通常使用堆式的动态存储分配方案。9.6.1堆式动态存储分配的实现定长块管理定长块管理变长块管理变长块管理 分配回收分配回收 首次满足法首次满足法 随机随机(查栈表查栈表)直接插入表头直接插入表头 最优满足法最优满足法 请求内存范围较广请求内存范围较广(查找查找)最差满足法最差满足法 请求内存范围较窄请求内存范围较窄(不查找不查找)9.6.2隐式存储回收（用户程序和回收子程序并行工作）存储块格式：标记:对已分配的块跟踪程序中各指针的访问路径，如果某个块被访问过，就给这个块加一个标记。回收：所有未加标记的存储块回收到一起，并插入空闲块链表中，然后消除在存储块中所加的全部标记。优点：防止死块产生，缺点：开销大，：解决：当空闲块降到某值时开始回收。