目标程序运行进的存贮组织

1、第九章 目标程序运行时的存贮组织 从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配。 一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳 生成的目标代码和目标代码运行时的数据空间。数据空间应包括：用户定义的各种类型的数据对象 （变量和常数）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需 的连接单元，以及组织输入 /输出所需的缓冲区。目标代码所占用空间的大小，在编译时能确定，有 些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。但有些数据对象具有 可变体积和待编译性质，而无法在编译时确

2、定存储空间的位置。因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区，如图 9-1 就是一种典型 划分，代码（ code）区用以存放目标代码，这是固定长度的， 即编译时能确定的。 静态数据区（ static data）用以存放编译时能确定所占用空间的数据，堆栈区（stack and heap）用于可变数据以及管理过程活动的控制信息。图 9-1 目标程序运行时存储区的典型划分编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间 的使用和管理办法的规定。所谓数据空间的分配，本质上看，是将程序中的每个名字与一个存储位 置关联起来，该存储位置用以容纳名字的值。我

3、们知道，即便有些名字在程序中只声明了一次，但 该名字可能对应运行时不同的运行空间位置以容纳每次执行时的值。因此，源语言的结构特点、源 语言数据类型、源语言中决定名字作用域的规则等因素影响存储空间的管理和组织的复杂程序，决 定数据空间分配的基本策略。本章重点：存储空间的使用管理方法、栈式动态存储分配的实现第一节 数据空间的三种不同使用方法和管理方法数据空间的使用和管理方法分成三种： 静态存储分配、 栈式动态存储分配和堆式动态存储分配。1 、 静态存储分配 如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行 时的全部数据空间，确定每个数据对象的存储位置，那么则称这种

4、分配策略为静态存储分配。如像 FORTRAN 这样的语言，其程序是段结构的，如图 9-1-1 所示，即由主程序段和若干子程 序段组成。各程序段中定义的名字一般是彼此独立的（除公共块和等价语句说明的名字以外） ，也即 各段的数据对象名的作用域在各段中，同一个名字在不同的程序段表示不同的存储单元，不会在不 同段间互相引用、赋值。另外它的每个数据名所需的存储空间大小都是常量（即不许含可变体积的 数据，如可变数组） ，且所有数据名的性质是完全确定的。这样，整个程序所需数据空间的总量在编 译时完全确定，从而每个数据名的地址就可静态进行分配。换句话说，一旦存储空间的某个位置分 配给了某个数据名（关联起来）

5、之后，在目标程序的整个运行过程，此位置（地址）就属于该数据 名了。图 9-1-1 FORTRAN 程序构成特点2、动态存储分配如果一个程序设计语言允许递归过程，可变数组或可变数据结构，那么，就需要采用动态存储 管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据 空间的大小待程序运行时动态地确定。有两种动态存储分配方式：栈式（stack）和堆式（ heap）。3、栈式动态存储分配 这种分配策略是将整个程序的数据空间设计为一个栈。它适用于PASCAL ，C，ALGOL 之类语言的实现，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这

6、部分空间，过程所需的数据空间包括两部分，一部分是生存期在本过程这次活动中的数据对象，如 局部变量、参数单元、临时变量等等；另一部分则是用以管理过程活动的记录信息，即当一次过程 调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器（返 地址）、寄存器的值等，也都必须保留在栈中。当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动重新开始。至于 在这种分配策略下，如何实现动态地分配和释放一个过程的数据空间，如何实现对非局部变量的引 用、参数传递以及可变数据结构（如可变数组）的空间分配办法等等，将在后面给予讨论。4 、 堆式动态存储分配 如果一个程序语言

7、提供用户自由地申请数据空间和退还数据空间的机制 （如 C+中的 new, delete,PASCAL 的 new，便是这种机制）或者不仅有过程而且有进程的程序结构，即空间的使用未必服从 “先申请后释放，后申请先释放”的原则，那么栈式的状态分配方案就不适用了。这种情况下通常 使用一种称为堆式的动态存储分配方案。假设程序运行时有一个大的存储空间，每当需要时就从这 片空间中借用一块，不用时再退还，由于借还的时间先后不一，经一段运行之后，程序运行空间将 被分划成许多块块，有些占用，有些空闲。那么当运行程序要求一块体积为 N 的空间时，需要决定 应该从哪个空闲块得到这个空间。理论上讲，应该从比 N 稍大

8、一些的空闲块中取出 N 个单元，以便 使大的空闲块派更大的用场，但实际难度很大，实际中常常采用的办法是：先遇到哪块比 N 大就从 其中取出 N 个单元。 即使这样， 也会发生找不到一块比 N 大的空闲块， 但所有空闲块的总和比 N 大 得多的情况，这时，有的分配管理系统采用废品回收的办法来应付。第二节 栈式存储分配的实现就在栈顶为该过程分配前面提到，使用栈式存储分析策略意味着，运行时每当进入一个过程， 所需的数据空间，当一个过程工作完毕返回时，它的栈顶的数据 空间也即释放。下面讨论栈式存储分配的实现。为讨论方便，首先引入一个术语过程的活动记录（ Activation Record）。过程的活动

9、记录是一段连续的存储区，用 以存放过程的一次执行所需要的信息，这些信息可以如图 所示。 但并不是所有的语言， 所有的编译程序全部使用这些信息 对它的简单描述如下：1、临时工作单元， 比如计算表达式过程中需存放中间结果用 的临时值单元。2、局部变量，一个过程的局部变量。寄存器的值，这些值都需要在控制从该过程返3、保存机器状态，容纳该过程执行前关于机器状态的信息， 诸如程序计数器、 回时给予恢复。4、存取链，用以存取非局部变量，这些变量存放于其它过程活动记录中。并不是所有语言需要 该信息。5、控制链，指向调用该过程的那个过程的活动记录，这也不是所有语言都需要的。6、实参，也称形式单元，由调用过程向

10、该被调过程提供实参的值（或地址）。当然在实际编译程序中，也常常使用机器寄存器传递实参。7、返回地址，保存该被调过程返回后的地址。 这些域的大小在编译时是已知的，如果局部变量中包含有可变数组，那么则采用内情向量，将 内情向量置于过程活动记录中。另外，有些语言的编译程序还将参数个数存放于活动记录中，以便 进行参数个数人检查。一、 简单的栈式存储分配的实现 首先从一种最简单的程序设计语言结构讲起：没有分程序结构，过程定义不嵌套，但允许过程 递归调用。其程序结构如图 9-2-2 所示。这种情况下，program main ； 全局变量或数组的说明； proc R ；end（ R）；proc Q ；en

11、d（ Q）； 主程序执行语句 end. （main）图 9-2-2 过程定义不嵌套的程序结构采用栈式动态分配策略，即运行时，每当进入一个过程，则为该过程分配一段存储区，当一个 过程工作完毕返回时，它所占用的存储区则可释放。程序运行时的存储空间， （栈）中在某一时刻可 能会包含某个过程的几个活动记录（某个过程递归调用的情况） ；另外，同样一个存储位置，可能不 同运行时刻分配给不同的数据对象。例如，图 9-2-3 的程序结构中，若主程序调用了过程 Q，Q 又调 用了 R，在 R 进入运行后的存储结构如图 9-2-3（a）所示。若主程序调用了过程 Q， Q 递归调用自 己，在 Q 过程第二次进入运行

12、后的存储结构如图9-2-3（ b）所示。若主程序先调用过程 Q，然后主程序接着调用 R，且 Q 过程不调用 Q 和 R，这时 Q 和 R 进入运行后的存储结构分别如图 9-2-3（ c） 和 9-2-3 （d）所示。TOPR 的活动Q 的活动SP记录记录Q 的活动Q 的活动Q 的活动记录记录记录主程序全主程序全主程序全局数据区局数据区局数据区a）（ b）（c）R 的活动记录主程序全局数据区d）图 9-2-3 栈式存储分配图 9-2-4 无嵌套定义的过程活动记录分图配1了0.数6 组过区程之的后活的动运记行录栈图 9-2-5常常使用两个指针指示栈最顶端的数据区，一个称为 SP，一个称为 TOP。

13、 SP 总是指向现行过程活动记录的起点，TOP 则始终指向已占用的栈顶单元。这种语言若含有可变数组，则其过程活动记录的内容可如图9-2-4 所示。 这里把控制链也称作老SP，即调用该过程的那个过程的最新活动记录的起点。假定图 9-2-4 所示为图 9-2-3（a）中现行过程 R 的活动记录， SP为此过程活动记录的起点， TOP 指向为此过程创设的活动记录的顶端， 并假定 R 含有可变数组， 则在分配了数组区之后 TOP 就指向 数组区（整个运行栈）的顶端。图 9-2-5 表明分配数组区之后的运行栈情况，可以与图9-2-3（ a）对照。在过程段中对任何局部变量 x 的引用可表示为变址访问 xs

14、p ，此处 x 代表变量 x 的相对数，也 就是相对于活动记录起点的地址。这个相对数在编译时可完全确定下来。过程的局部数组的内情向 量的相对地址在编译时也同样可确定下来。数组空间分配之后，对数组元素的引用也就容易用变址 访问的方式来实现。栈式存储分配就简单介绍这里。第三节 参数传递当一个过程调用其它过程时， 调用过程和被调过程之间的通信经由非局部量或者经由参数传递。 如图 9-3-1的过程 exchangel既使用了非局部量数组 a，又使用了形式参数（简称形参） i 和j，将ai 和 aj 的值进行交换。（1） procedure exchangel（i,j: integer） ；（ 2） v

15、ar x: integer ；（3）begin；（4）x： =ai ； ai ： =aj ；aj ：=x（ 5） end图 9-3-1 带有非局部变量和形参的 PASCAL 过程语句 exchangel（m, n） ；表示了对图 9-3-1 中过程 exchangel 的一次调用，其中 m,n 为实在参数， 简称实参。我们所讨论的问题是，为执行 exchangel（m,n） ，形参 i,j 应按何种方式同实参 m,n 相联， 换句话说， 如何把实在参数传递给相应的形式参数呢？有几种形实参对应的方法， 分别称作值调用， 地址（引用）调用，名字调用以及宏扩展。也就是说，参数传递的几种不同途径是传值

16、，传地址， 传名及宏扩展等。之所以存在有不同的方法，源于一个表达式的表示是如何给于不同的解释的。比 如，在一个赋值语句 ai：=aj 中，表达式 aj表示一个值，而 ai 表示一个存储位置，用于存放 aj 的值。通常术语左值（ 1 value ）指表达式代表的存储，右值（ r value）指该存储位置中含有的值。 “左”和“右”来自赋值语句的“左”端和“右”端。参数传递方法的不同主要基于实在参数是表 达一个右值，一个左值，还是实在参数本身的文本（字） 。知道一个语言使用的参数传递的方法非常重要，因为一个程序的结果依赖于所使用的方法。观 察图 9-3-2 的 PASCAL 程序。我们知道该程序的

17、输出是a=2，b=1 如果将第 3 行的关键字 var去掉，则该程序的输出是 a=1， b=2。有关键字 var 时， PASCAL 语言的参数传递使用的方式是传地址；去掉var，则使用的方式是传值。一、传值 现在讨论传值的实现。传值，即 call-by-value ，也称值调用。这是最简单的参数传递方法。即将 实参计算出它的值，然后把它传给被调过程。具体来讲是这样的：1、形式参数当作过程的局部变量处理， 即在被调过程的活动记录中开辟了形参的存储空间， 这 些存储位置即是我们所说的实参或形式单元。2、调用过程计算实参的值，并将它们的右值（r-value）放在形式单元开辟的空间中。3、被调用过程

18、执行时，就像使用局部变量一样使用这些形式单元。 传值或值调用的重要特点是对形式参数的任何运算来不影响调用过程的活动记录中实参的值。也即在图 9-3-2 程序中， 如果第 3 行的关键字 var 去掉以后， PASCAL 将以传值方式将 x 和 y 传递给 过程 swap。第 12行 swap（a,b）调用过程将不会影响 a和 b 的值。其结果等价于执行下列运算：x ： = ay ： = btemp： = xx ： = y y ： =temp 这里， x,y 和 temp 局部于 swap，虽然赋值改变了局部量 x,y 和 temp 的值， 但当控制从该调用返回而 swap 的该活动记录释放后，

19、这些改变即消失，这种调用方式不影响调用过程的活动记录。（ 1） program reference （input, output） ； （2）var a, b： integer ；（ 3） procedure swap （var x, y ：integer）；（4）var temp ： integer ；（ 5）begin（ 6）temp： =x；（ 7）x：=y；（ 8）y： =temp（ 9）end；（10） begin（ 11）a：=1 ； b：=2 ；（ 12）swap （a, b）；（13）writeln （ a=， a） ； writeln （ b=，b）（14） end.图 9-

20、3-2 带有过程 swap 的 PASCAL 程序通过值调用的过程可以由非局部量（参见图9-3-1 的 exchangel）或由指针而对调用过程发生影响。比如图 9-3-3的C程序中， x和y声明为整型指针（在第 2行），第 8行调用 swap（&a, &b）中 的&操作符号导致将指向 a和 b 的指针传给过程 swap。该程序的输出为：a is now 2, b is now 1该例中指针的使用恰好提示了一个编译程序怎样实现引用调用。（ 1）swap（x, y）（ 2 ） int * x, *y ；（ 3 ） int temp ；（ 4 ）temp=*x ； *x= * y ； * y=te

21、mp ；（5）（ 6 ） main （ ）（7） int a=1，b=2；（ 8 ）swap （&a, &b）（ 9 ）printf （ a is now %d, b is now %dn , a, b）；（10）图 9-3-3 在一个值调用过程中使用指针的 C 程序、 传地址当参数通过引用传递时，也称作传地址，或引用调用。调用过程传给被调过程的是指针，指向 实参存储位置的指针。1、如实参是一个名字或具有左值的表达式，则左值本身传递过去。2、如实参是一表达式，比方 a+b 或 2，而没有左值，则表达式先求值，并存入某一位置，然后 该位置的地址传递过去。3、被调过程中对形式参数的任何引用和赋值都

22、通过传递到被调过程的指针被处理成间接访问。 例如，在图 9-3-2的程序中，若用实参 i 和 ai对过程 swap 进行调用，即 swap（i, ai） ，其效果 如下步骤所述：1、将 i 和 ai的地址（左值）拷贝到被调过程的活动记录中，比如说分别对应形参x 和 y 的单元 arg1 和 arg2 。2、将局部变量 temp 设为由 arg1 所指单元的内容（即令 temp 等于 I0，其中 I0 是 i 的初值），这 一步对应于 swap 定义中的第 6 行语句： temp： =x。3、将 arg1 所指单元的内容设为 arg2所指单元的值，即 i：=aI0，这一步对应 swap中第 7

23、行 的 x：=y 。4、将 arg2 所指单元的内容设为等于 temp 的值，即，设 aI0=i ，这一步对应 y： =temp。 除了传值和传地址两种参数传递方法之外，还有“得结果”（ value-result ），传名 call-by-name第四节 习题一、单项选择题1、程序所需的数据空间在程序运行前可确定，称为管理技术。a. 动态存储 b. 栈式存储2、堆式动态分配申请和释放存储空间遵守c. 静态存储 原则。c. 后请先放d. 堆式存储d. 任意a. 先请先放 b.3、静态分配允许程序出现先请后放。a. 递归过程 b. 可变体积的数据项目 c. 静态变量d. 待定性质的名字4、在编译方法中，动态存储分配的含义是。a. 在运行阶段对源程序中的数组、变量、参数等进行分配b. 在编译阶段对源程序中的数组、变量、参数进行分配c. 在编译阶段对源程序中的数组、变量、参数等进行分配，在运行时这些数组、变量、参 数的地址可根据需要改变d. 以上都不正确5、在