运行时的存储组织与分配.ppt

*1*1 编 译 原 理 * 第九章 运行时的存储组织与分配 1. 要求明确静态存储分配和动态存储分配的含义 2. 明确活动记录的含义及组成 3. 了解静态、动态存储分配的策略 教学目标 *2*2 编 译 原 理 * S.P O.P 语义分析、生成中间代码 生成目标程序 代码优化 语法分析程序 词法分析程序 错 误 处 理 符 号 表 管 理 编译程序在编译阶段要为源程序中出现的变量、常量等组 织好在运行阶段的存储空间 将这种组织形式通过生成的目标代码体现出来 为运行阶段实现存储奠定基础 *3*3 编 译 原 理 * 9.1 存储组织概述 9.2 静态存储分配 9.3 栈式动态存储分配 9.4 堆式动态存储分配 教学内容 *4*4 编 译 原 理 * 9.1 存储组织概述 运行时存储空间的划分 代码空间 数据空间 目标代码空间 静态数据空间 栈 自由空间 堆 *5*5 编 译 原 理 * 过程的活动和活动记录 一个过程的活动：该过程的一次执行。 即每次执行一个过程体，就产生该过程的 一个活动。 活动记录：为了管理过程在一次执行中所 需要的信息，使用一段连续的存储区 活动的生存期: 过程P一个活动的生存期，指的是从执行该过程 体第一步操作到最后一步操作之间的操作序，包 括执行P时调用其它过程花费的时间。 *6*6 编 译 原 理 * 活动记录的结构 *7*7 编 译 原 理 * 目标程序运行时的活动 传地址（call by reference） 把实在参数的地址传递给相应的形式参数。 传值（call by value） 把实在参数的值计算出来并存放在一个被调用 段可以拿得到的地方。被调用段开始工作时，首 先把这些值抄进自己的形式单元中，然后就好像 使用局部名一样使用这些形式单元。 传名（call by name）：也称为“换名” 过程调用的作用相当于把被调用段的过程体抄 到调用出现的位置，把其中任一出现的形式参数 都替换成相应的实在参数（文字替换）。 *8*8 编 译 原 理 * 9.2 静态存储分配 在编译阶段由编译程序实现对存储空间的 管理，为源程序中的变量分配存储单元。（如看电影） 条件 在编译时能够确定变量在运行时的数据空间大小 运行时不改变 *9*9 编 译 原 理 * FORTRAN程序的静态分配 *10*10 编 译 原 理 * 静态分配静态分配 名字在程序被编译时绑定到存储单元，不需名字在程序被编译时绑定到存储单元，不需 要运行时的任何支持。要运行时的任何支持。 绑定的生存期是程序的整个运行时间。绑定的生存期是程序的整个运行时间。 控制再次进入该过程时，局部变量的值和控控制再次进入该过程时，局部变量的值和控 制上一次离开时的一样。制上一次离开时的一样。 每个活动记录的大小是固定的。每个活动记录的大小是固定的。 过程调用时保存信息的地址在编译时也是已过程调用时保存信息的地址在编译时也是已 知的。知的。 *11*11 编 译 原 理 * 动态存储分配 在目标程序运行阶段由目标程序实现对存 储空间的组织与管理，为源程序中的变量分 配存储单元 特点 在目标程序运行时进行分配 编译时为运行阶段设计好存储组织形式，即为每个 数据项安排好它在数据区中的相对位置 C语言引用sizeof进行计算时，是在编译阶段完成 的，还是在运行阶段完成的？ （如开大会） *12*12 编 译 原 理 * 9.3 栈式动态存储分配 变量生存期具有嵌套特性，即后进先出的特性（如递归） 进入时：在栈顶为其分配一个数据区 退出时：撤消过程数据区 *13*13 编 译 原 理 * 9.4 堆式动态存储分配 变量生存期具有随机交叉特性，即非后进先出的特性（如程序 运行时动态申请存储空间） 给运行的程序划分一个大的存储区(称为堆) 每当需要时可从堆中分得一块 用完之后再退还给堆 *14*14 编 译 原 理 * 堆式的动态存储 如果一个程序语言允许用户自由地申请 数据空间和退还数据空间，或者不仅有 过程而且有进程（process）的程序结构 ，那么，由于空间的使用未必服从“先请 后还，后请先还”的原则，因此，栈式的 动态分配方案就不适用了。在这种情况 下通常使用一种称之为堆式的动态存储 分配方案。 *15*15 编 译 原 理 * 2.变长块管理 （1）首次满足法：只要在空闲块链表中找到 满足需要的一块，就进行分配。 （2）最优满足法：将空闲块链表中一个不小 于申请块且最接近于申请块的空闲块分配给用 户，则系统在分配前首先要对空闲块链表从头 至尾扫描一遍，然后从中找出一块不小于申请 块且最接近于申请块的空闲块分配。 （3）最差满足法：将空闲块表中不小于申请 块且是最大的空闲的一部分分配给用户。 *16*16 编 译 原 理 * 9.6.2 隐式存储回收 隐式存储回收要求用户程序和支持运行 的回收子程序并