第8章+运行时存储管理

1、1第第8章章 运行时的运行时的存储管理存储管理2开设本章的目的开设本章的目的n一个用高级语言编写的程序要投入运行，一个用高级语言编写的程序要投入运行， 一组可运行的代一组可运行的代码，这组代码应与高码，这组代码应与高级语言的程序等价；级语言的程序等价；程序语言的编译系统程序语言的编译系统涉及涉及 一个运行环境，一个运行环境，对程序中的变量做存对程序中的变量做存储分配，提供各种运储分配，提供各种运行信息。行信息。 变量以及变量的变量以及变量的存储分配和存储管理存储分配和存储管理的问题。的问题。涉及涉及3 8.1 存储组织存储组织4运行时内存的划分运行时内存的划分v编译程序从操作系统中得到一块存储

2、区以编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳使目标程序在其上运行，该存储区需容纳1. 生成的目标生成的目标代码空间代码空间；2. 目标代码运行时的目标代码运行时的数据空间数据空间。5代码空间代码空间 这是经翻译后的目标代码的存储区域，这是经翻译后的目标代码的存储区域，线性存放着目标指令序列。这是线性存放着目标指令序列。这是固定长度固定长度的，即在编译时能确定的。的，即在编译时能确定的。6数据空间数据空间 每个程序都定义一定数量的各种类型每个程序都定义一定数量的各种类型的变量和常量，必须为之分配相应的存储的变量和常量，必须为之分配相应的存储空间。空间。l 用户定义

3、的各种类型的数据对象；用户定义的各种类型的数据对象；l 保留中间结果和传递参数的临时工作单元；保留中间结果和传递参数的临时工作单元；l 调用过程时所需的连接单元；调用过程时所需的连接单元；l 组织输入、输出所需的缓冲区。组织输入、输出所需的缓冲区。7 有些数据对象所有些数据对象所占用的空间，在编译占用的空间，在编译时能确定，其地址可时能确定，其地址可以编译进目标代码；以编译进目标代码；有些数据对象具有可有些数据对象具有可变体积和待编译性质，变体积和待编译性质，无法再编译时确定存无法再编译时确定存储空间的位置。储空间的位置。静态存储分配静态存储分配动态存储分配动态存储分配8 对数据空间来说，对数

4、据空间来说，程序实体的属程序实体的属性性(变量类型决定存储长度，作用域决变量类型决定存储长度，作用域决定了变量在存储区的空间范围等定了变量在存储区的空间范围等)和和语语言的运行特性言的运行特性都决定了数据空间的分配都决定了数据空间的分配和管理应采用的方法和策略。和管理应采用的方法和策略。数据空间的分配数据空间的分配名字名字 存储位置存储位置 值值9 静态数据区静态数据区用以用以存放编译时能确定所占存放编译时能确定所占用空间的数据。用空间的数据。 堆栈区堆栈区用于存放用于存放可变数据以及管理过程可变数据以及管理过程活动的控制信息。活动的控制信息。代代代代码码码码段段段段静静静静态态态态数数数数据

5、据据据段段段段运运运运行行行行栈栈栈栈 堆堆堆堆10 v静态存储分配静态存储分配v动态存储分配动态存储分配 1. 栈式动态存储分配栈式动态存储分配 2. 堆式动态存储分配堆式动态存储分配11过程活动记录过程活动记录(AR)(AR) 源程序由一组过程按某种规则组成。源程序由一组过程按某种规则组成。过程的一次执行称作一次活动。一个过程过程的一次执行称作一次活动。一个过程的一次执行所需要的信息使用一个连续的的一次执行所需要的信息使用一个连续的存储区来管理，这个区叫做一个活动记录。存储区来管理，这个区叫做一个活动记录。12 临时值，如计算表达式时的中间工作单元。临时值，如计算表达式时的中间工作单元。

6、局部变量局部变量 （数据）（数据） 保存运行过程前的状态保存运行过程前的状态 存取链存取链（可选可选） 对于非局部量的引用。对于非局部量的引用。 控制链控制链（可选可选） 指向调用者的活动记录，释放栈。指向调用者的活动记录，释放栈。 实参实参 （形式单元）（形式单元）返回值返回值 （对函数）（对函数）（有时可使用寄存器存放返回值）（有时可使用寄存器存放返回值）13 8.2 静态静态存储分配存储分配14静态存储分配静态存储分配v对于某些变量，在编译时刻就可以由编译对于某些变量，在编译时刻就可以由编译程序为它们分配存储区。在运行时刻，这程序为它们分配存储区。在运行时刻，这些变量和存储区的结合（些变

7、量和存储区的结合（绑定绑定）不变。）不变。v局部名字的值在过程活动停止后仍保留下局部名字的值在过程活动停止后仍保留下来。来。 v不能不能处理的情况：处理的情况：在编译时刻不能确定大小的变量。在编译时刻不能确定大小的变量。要支持递归过程实现。要支持递归过程实现。动态建立的数据结构。动态建立的数据结构。15动态存储分配动态存储分配v凡不满足静态分配条件的语言，自然归入凡不满足静态分配条件的语言，自然归入了动态分配类。了动态分配类。v如果一个程序语言允许递归过程、可变数如果一个程序语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么组或允许用户自由申请和释放空间，那么就采用动态存储分配管理技

8、术。就采用动态存储分配管理技术。v有两种动态存储分配方式：有两种动态存储分配方式： 1. 栈式栈式(stack)动态存储分配动态存储分配 2. 堆式堆式(heap)动态存储分配动态存储分配16 8.3 栈式栈式存储分配存储分配17v基于控制栈的原理：基于控制栈的原理： 存储空间被组织成栈，存储空间被组织成栈，活动记录的推入和弹出分别对应于活动的活动记录的推入和弹出分别对应于活动的开始和结束。开始和结束。v 与静态分配不同的是，在每次活动中把局与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字时，活动记

9、录从栈中弹出，因而局部名字的存储空间也随之消失。的存储空间也随之消失。 18简单的栈式存储分配简单的栈式存储分配v程序结构特点程序结构特点：没有分程序结构，过程定没有分程序结构，过程定义不嵌套，过程可递归调用，含可变数组；义不嵌套，过程可递归调用，含可变数组； v采用栈式动态分配策略，运行时，每当进采用栈式动态分配策略，运行时，每当进入一个过程，则为该过程分配一段存储区，入一个过程，则为该过程分配一段存储区，当一个过程工作完毕返回时，它所占用的当一个过程工作完毕返回时，它所占用的存储区则可释放。存储区则可释放。19 main 全局变量的说明或数组的说明；全局变量的说明或数组的说明； proc

10、R end R; proc Q end Q; 主程序执行语句主程序执行语句 end mainMain-Q-TOP- R 的活动记录的活动记录 SP-的活动记录的活动记录主程序全局主程序全局数据区数据区RQSP指向现行过程活动记录的起点指向现行过程活动记录的起点TOP始终指向已占用的栈顶单元始终指向已占用的栈顶单元20 嵌套过程语言的栈式分配嵌套过程语言的栈式分配v（语言）一个过程可以引用包围它的任（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，一外层过程所定义的标识符（如变量，数组或过程等）。数组或过程等）。v（实现）一个过程可以引用它的任一外（实现）一个过程可以引用它的任

11、一外层过程的最新活动记录中的某些数据。层过程的最新活动记录中的某些数据。21带有嵌套过程的一个带有嵌套过程的一个Pascal程序程序 sort readarray exchange quicksort partition22 v关键技术：解决对非局部量的引用（存关键技术：解决对非局部量的引用（存取）。取）。v设法跟踪每个外层过程的最新活动记录设法跟踪每个外层过程的最新活动记录AR的位置。的位置。v跟踪办法：跟踪办法： 1. 用存取链。用存取链。 2. 用用DISPLAY表。表。23存取链存取链 栈中的活动记录应反映源程序中过程栈中的活动记录应反映源程序中过程之间的嵌套关系。之间的嵌套关系。 为

12、每一个活动记录增设一个称为存取为每一个活动记录增设一个称为存取链的指针，如果在源程序中过程链的指针，如果在源程序中过程p直接嵌入直接嵌入在过程在过程q中，那么中，那么p的一个活动记录中的存的一个活动记录中的存取链指向取链指向q的最近的活动记录中的存取链。的最近的活动记录中的存取链。从当前活动记录开始，沿着这条链，能找从当前活动记录开始，沿着这条链，能找到访问的非局部名字。到访问的非局部名字。 程序运行过程中应维持这条链。程序运行过程中应维持这条链。24嵌套层次显示表嵌套层次显示表displayv“嵌套层次嵌套层次”是指过程定义的层数。主程是指过程定义的层数。主程序的层数为序的层数为0。向外逐层加。向外逐层加1。v每进入一个过程后，在建立它的活动记录每进入一个过程后，在建立它的活动记录的同时建立一张的同时建立一张display表。表。v当前激活过程的层次为当前激活过程的层次为K，它的，它的Display表表含有含有K+1个单元，个单元，自顶向下自顶向下依次存放着现依次存放着现行层，直接外层行层，直接外层直至最外层的每一过程直至最外层的每一过程的最新活动记录的地址。的最新活动记录的地址。25 8.4 堆式堆式存储分配存储分配26堆式存储分配堆式存储分配v堆式分配的适合范围：堆式分配的适合范