《【新编】运行时存储空间组织教材》由会员分享，可在线阅读，更多相关《【新编】运行时存储空间组织教材（94页珍藏版）》请在金锄头文库上搜索。
1、第6章 运行时存储空间组织 第6章 运行时存储空间组织 6 1 静态存储分配 6 2 简单的栈式存储分配 6 3 嵌套过程语言的栈式实现 6 4 堆式动态存储分配 6 5 参数传递补遗 第6章 运行时存储空间组织 6 1 静态存储分配 如果在编译时就能够确定一个程序在运行时所需的 存储空间大小 则在编译时就能够安排好目标程序运 行时的全部数据空间 并能确定每个数据项的单元地 址 存储空间的这种分配方法叫做静态分配 第6章 运行时存储空间组织 对FORTRAN语言来说 其特点是不允许过程有递 归性 每个数据名所需的存储空间大小都是常量 即不 允许含可变体积的数据 如可变数组 并且所有数据 名的性
2、质是完全确定的 不允许出现在运行时再动态确 定其性质的名字这种情况 这些特点确保整个程序所 需数据空间的总量在编译时是完全确定的 从而每个 数据名的地址就可静态地进行分配 静态存储分配是一种最简单的存储管理 一般而言 适于静态存储分配的语言必须满足以下条件 第6章 运行时存储空间组织 1 数组的上下界必须是常数 2 过程调用不允许递归 3 不允许采用动态的数据结构 即在程序运行过程中申请 和释放的数据结构 第6章 运行时存储空间组织 满足这些条件的语言除了FORTRAN之外 还有 BASIC等语言 在这些语言中 编译程序可以完全确 定程序中数据项所在的地址 通常为相对于各数据区起 始地址的位移
3、量 由于过程调用不允许递归 因此数 据项的存储地址就与过程相联系 过程调用所使用的 局部数据区可以直接安排在过程的目标代码之后 并 把各数据项的存储地址填入相关的目标代码中 以便 在过程运行时访问这个局部数据区 在此 不存在对 存储区的再利用问题 目标程序执行时不必进行运行 时的存储空间管理 过程的进入和退出变得极为简单 第6章 运行时存储空间组织 FORTRAN语言的静态存储管理特点是FORTRAN程 序中的各程序段均可独立地进行编译 在编译过程中 给程序中的变量或数组分配存储单元的一般做法是 为每一个变量 或数组 确定一个有序的整数对 其中 第一个整数用来指示数据区 局部数据区或公用区 的
4、 编号 第二个整数则用来指明该变量 或数组 所对应的 存储起始单元相对于其所在数据区起点的位移 即相对 于数据区起点的地址 并将这一对整数填入符号表相 应登记项的信息栏中 至于各数据区的起始地址在编 译时可暂不确定 待各程序段全部编译完成之后 再 由连接装配程序最终确定 并将各程序段的目标代码 组装成一个完整的目标程序 第6章 运行时存储空间组织 一个FORTRAN程序段的局部数据区可由图6 1所示 的项目组成 其中 隐参数是指过程调用时的连接信 息 不在源程序中明显出现 如调用时的返回地址 调 用时寄存器的保护等 形式单元用来存放过程调用时 形参与实参结合的实参地址或值 第6章 运行时存储空
5、间组织 图6 1 一个FORTRAN程序段 的局部数据区 第6章 运行时存储空间组织 6 2 简单的栈式存储分配 我们首先考虑一种简单程序语言的实现 这种语言 没有分程序结构 过程定义不允许嵌套 但允许过程 的递归调用 允许过程含有可变数组 例如 C语言除 不允许含有可变数组外 就是这样一种语言 C语言的 程序结构如下 第6章 运行时存储空间组织 全局数据说明 main main中的数据说明 void R R中的数据说明 第6章 运行时存储空间组织 void Q Q中的数据说明 第6章 运行时存储空间组织 例如 下面计算n 的C语言程序就是一个递归调用的程 序 它的执行过程可以用栈来实现 in
6、clude stdio h long factorial int n if n 1 return n factorial n 1 else return 1 第6章 运行时存储空间组织 main int num do scanf d if num 0 第6章 运行时存储空间组织 6 2 1 栈式存储分配与活动记录 使用栈式存储分配法意味着程序运行时 每当进入 一个过程 或函数 就有一个相应的活动记录累筑于栈顶 此记录含有连接数据 形式单元 局部变量 局部 数组的内情向量和临时工作单元等 在进入过程和执 行过程的可执行语句之前 再把局部数组所需空间累 筑于栈顶 从而形成过程工作时的完整数据区 第
7、6章 运行时存储空间组织 注意 每个过程的活动记录的体积在编译时可以静 态地确定 但由于允许含有可变数组 所以数组的大 小只有在运行时才能知道 因数组区的大小不能预先 获知 为了扩充方便 所以只能将数组区累筑于活动 记录之上的当前栈顶 当一个过程工作完毕返回时 它在栈顶的数据区 包括活动记录和数组区 也随即不复 存在 第6章 运行时存储空间组织 对C语言来说 由于其不含可变数组 因而它的活 动记录本身包含了局部数组的空间 图6 2和图6 3分 别给出了C语言和含可变数组的某简单语言程序运行时 的数据空间结构 即显示了主程序在调用了过程Q Q 又调用了过程R 且在R投入运行后的存储结构 SP指示
8、器总是指向执行过程活动记录的起点 而 TOP指示器则始终指向 已占用 栈顶单元 当进入一个 过程时 TOP指向为此过程创建的活动记录的顶端 在分配数组区之后 如果有的话 TOP又改为指向数组 区 从而是该过程整个数据区 的顶端 第6章 运行时存储空间组织 图6 2 C语言程序的存储组织 第6章 运行时存储空间组织 图6 3 含可变数组程序的存储组织 第6章 运行时存储空间组织 C的活动记录含有以下几个区段 如图6 4所示 1 连接数据 两项 老SP值 即前一活动记录的起始 地址 和返回地址 2 参数个数 3 形式单元 存放实在参数的值或地址 4 过程的局部变量 简单变量 数组的内情向量和 临时
9、工作单元 第6章 运行时存储空间组织 图6 4 C过程的活动记录 第6章 运行时存储空间组织 C语言不允许过程 函数 嵌套 也即不允许一个过程 的定义出现在另一个过程的定义之内 因此 C语言的 非局部变量仅能出现在源程序头 非局部变量可采用静 态存储分配并在编译时确定它们的地址 由图6 4可知 过程的每一局部变量或形参在活动记 录中的位置都是确定的 也就是说 这些变量或形参所 分配的存储单元其地址都是相对于活动记录的基址SP的 因此 变量和形参运行时在栈上的绝对地址是 绝对地址 活动记录基址 SP 相对地址 第6章 运行时存储空间组织 于是 对当前正在执行 即活动 的过程 其任何局 部变量或形
10、参X的引用均可表示为变址访问X SP 此 处X代表X相对于活动记录基址的偏移量 这个偏移量 即相对数 在编译时可完全确定下来 过程的局部数组 的内情向量的相对地址在编译时也同样可完全确定下 来 一旦数据空间在过程里获得分配后 对数组元素 的引用也就容易用变址的方式进行访问 第6章 运行时存储空间组织 6 2 2 过程的执行 1 过程调用 过程调用的四元式序列为 par T1 par T2 par Tn call P n 第6章 运行时存储空间组织 由于此时TOP是指向被调用过程P之前的栈顶 而P 的形式单元和活动记录起点之间的距离是确定的 等于 3 参见图6 4 因而由调用者过程给将要调用的过
11、程 P的活动记录 正在形成中 的形式单元传递实参值或实 参地址 即每个par Ti i 1 2 n 可直接翻译成如下指 令 i 3 TOP Ti 传递参数值 或 i 3 TOP addr Ti 传递参数地址 第6章 运行时存储空间组织 而四元式call P n则翻译成 1 TOP SP 保护现行SP 3 TOP n 传递参数个数 JSR P 转子指令 转向P过程的第 一条指令 过程P调用之前 先构造出P的活动记录部分内容 见图6 5所示 第6章 运行时存储空间组织 图6 5 过程P调用前先构造P的活动记录部分内容 第6章 运行时存储空间组织 2 过程进入 转入过程P后 首先要做的工作是定义新活
12、动记录的 SP 保护返回地址和定义新活动记录的TOP值 即执 行下述指令 SP TOP 1 定义新SP 1 SP 返回地址 保护返回地址 TOP TOP L 定义新TOP 其中 L是过程P的活动记录所需的单元数 这个 数在编译时可静态地计算出来 第6章 运行时存储空间组织 对含可变数组 非C语言 的情况来说 因为过程可含 可变数组且所有数组都分配在活动记录的顶上 所以 紧接上述指令之后应是对数组进行存储分配的指令 如 果含有局部数组 这些指令是在翻译数组说明时产生 的 对每个数组说明 相应的目标指令组将做以下几 件工作 1 计算各维的上 下限 2 调用数组空间分配子程序 其参数是各维的上 下限
13、和内情向量单元首地址 第6章 运行时存储空间组织 数组空间分配子程序计算并填好内情向量的所有信 息 然后在TOP所指的位置之上留出数组所需的空间 并将TOP调整为指向数组区的顶端 进入过程P后所 做的工作如图6 6所示 此后 在过程段执行语句的工作过程中 凡引用形 式参数 局部变量或数组元素都将以SP为基址进行相 对访问 第6章 运行时存储空间组织 图6 6 进入过程P后所做的工作示意 第6章 运行时存储空间组织 3 过程返回 C语言以及其它一些相似的语言含有return E 形式 的返回语句 其中E为表达式 假定E值已计算出来并 存放在某临时单元T中 则此时即可将T值传送到某个 特定的寄存器
14、中 调用过程将从这个特定的寄存器中获 得被调用过程P的结果 剩下的工作就是恢复SP和 TOP为进入过程P之前的原值 即指向调用过程的活动 记录及工作空间 并按返回地址实行无条件转移 即 执行下述指令序列 第6章 运行时存储空间组织 TOP SP 1 恢复调用过程的TOP值 SP 0 SP 恢复调用过程的SP值 X 2 TOP 将返回地址送X UJ 0 X 无条件转移 即按X的地址 返回到调用过程 一个过程也可通过它的end语句 对C语言则是该过 程 函数 体结束时的 自动返回 如果此过程是一个 函数过程 则按上述办法传递结果值 否则仅直接执 行上述返回指令序列 过程P的返回示意如图6 7所示
15、第6章 运行时存储空间组织 图6 7 过程P的返回示意 第6章 运行时存储空间组织 6 3 嵌套过程语言的栈式实现 在简单程序语言实现中是允许过程的递归调用的 并且过程中可含有可变数组 现在 我们再加上一种 功能 即允许过程的嵌套性 从结构上看 PASCAL 就是这样的一种语言 但由于PASCAL含有 文件 和 动态变量 因此 它的存储分配不能简单地用栈式方 法来实现 采用PASCAL的一个子集 例如去掉 文件 和 动态变量 这种数据类型 那就可以用我们下面将 要讨论的方法实现存储分配 第6章 运行时存储空间组织 6 3 1 嵌套层次显示表 DISPLAY 和活动记录 在讨论中 常常要用到过程
16、定义的 嵌套层次 简称 层数 这个概念 我们始终假定主程序的层数为0 因 此主程序称为第0层过程 如果过程Q是在层数为i的过 程P内定义的 并且P是包围Q的最小过程 则Q的层数 就为i 1 当编译程序处理过程说明时 过程的层数将 作为过程名的一个重要属性登记在符号表中 第6章 运行时存储空间组织 由于过程定义是嵌套的 因而一个过程可以引用包 围它的任一外层过程所定义的变量或数组 也就是说 运行时 一个过程Q可能引用它的任一外层过程P的 最新活动记录中的某些数据 因此 过程Q运行时必须 知道它的所有外层的最新活动记录的地址 由于允许 递归和可变数组的存在 过程的活动记录位置 即使是 相对位置 也往往是变迁的 因而必须设法跟踪每个外 层过程的最新活动记录的位置 第6章 运行时存储空间组织 一种常用的跟踪每个外层过程最新活动记录位置 的有效办法是 每进入一个过程后 在建立它的活动 记录区的同时建立一张嵌套层次显示表DISPLAY 假 定现在进入的过程层数为i 则它的DISPLAY表含有 i 1个单元 此表本身是一个小栈 自顶而下每个单元 依次存放着现行层 直接外层 直至最外层 第0层 即主程
