第10章目标程序运行时的组织

1、武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓第第10章章 目标程序目标程序运行时的存储组织运行时的存储组织 10.1 数据空间的三种不同使用方法和管理方法数据空间的三种不同使用方法和管理方法10.2 栈式存储分配的实现栈式存储分配的实现10.3 参数传递参数传递10.4 过程调用、过程进入和过程返回过程调用、过程进入和过程返回武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 从逻辑上看，在代码生成前，编译程序必须进行从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。目标程序运行环境的配置和数据空间的分配。 数据空间应包括：数据空间应包括：u用

2、户定义的各种类型的数据对象（变量和常数）所用户定义的各种类型的数据对象（变量和常数）所需的存储空间；需的存储空间；u作为保留中间结果和传递参数的临时工作单元；作为保留中间结果和传递参数的临时工作单元；u调用过程时所需的连接单元；调用过程时所需的连接单元；u组织输入组织输入/输出所需的缓冲区。输出所需的缓冲区。 目标代码所占用空间的大小在编译时能确定。有目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定，其地址些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。而有些数据对象具有可变体可以编译进目标代码中。而有些数据对象具有可变体积和待分配性质，无法

3、在编译时确定存储空间的位置。积和待分配性质，无法在编译时确定存储空间的位置。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 因此运行时的存储区常常划分成：目标区、静因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区，如图态数据区、栈区和堆区，如图10.1 。目标代码区目标代码区静态数据区静态数据区栈栈Stack堆堆heap图图10.1 目标程序运行时存储区的典型划分目标程序运行时存储区的典型划分武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓所谓数据空间的分配，本质上看，是将程序中的每个名所谓数据空间的分配，本质上看，是将程序中的每个名字与一个存储位置关联起来，该

4、存储位置用以容纳名字的值。字与一个存储位置关联起来，该存储位置用以容纳名字的值。编译程序分配目标程序运行时的数据空间的基本依据是编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的程序语言设计时对程序运行中存储空间的使用和管理办法的规定。规定。在程序设计语言语义学中，使用术语在程序设计语言语义学中，使用术语environment表示将表示将一个名字映射到一个存储位置的函数，术语一个名字映射到一个存储位置的函数，术语state表示存储位表示存储位置到值的映射，如图置到值的映射，如图10.2所示。所示。图图10.2 名字到存储位置、到值的映射名字到存

5、储位置、到值的映射 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓l 编译程序分配目标程序运行时的数据空间的基编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。间的使用和管理办法的规定。l 决定存储管理复杂程度的因素决定存储管理复杂程度的因素-源语言本身，源语言本身，比如源语言允许的数据类型有多少？语言中允比如源语言允许的数据类型有多少？语言中允许的数据项是静态确定还是动态确定？程序结许的数据项是静态确定还是动态确定？程序结构有什么特点，是段结构还是分程序结构？过构有什么特点，是段结构还是

6、分程序结构？过程定义是否允许嵌套？等等。程定义是否允许嵌套？等等。l 源语言的结构特点、源语言的数据类型、源语源语言的结构特点、源语言的数据类型、源语言中决定名字作用域的规则等因素影响存储空言中决定名字作用域的规则等因素影响存储空间的管理和组织的复杂程度，决定数据空间分间的管理和组织的复杂程度，决定数据空间分配的基本策略。配的基本策略。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.1 数据空间的三种不同使用方法和管理方法数据空间的三种不同使用方法和管理方法数据空间的使用和管理方法数据空间的使用和管理方法: 简单的栈式分配方案简单的栈式分配方案 嵌套过程的栈式分配方案嵌套过程的

7、栈式分配方案 分程序结构的存储分配方案分程序结构的存储分配方案静态存储分配、静态存储分配、动态存储分配动态存储分配栈式栈式堆式堆式武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.1.1 静态存储分配静态存储分配如果在编译时能确定目标程序运行中所需的如果在编译时能确定目标程序运行中所需的全部的数据空间的大小，编译时安排好目标程序全部的数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存运行时的全部数据空间，确定每个数据对象的存储位置，称这种分配策略为静态存储分配。储位置，称这种分配策略为静态存储分配。如如C中的静态变量，外部变量等。中的静态变量，外部变量等

8、。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.1.2 动态存储分配动态存储分配如果一个程序设计语言允许递归过程、允许如果一个程序设计语言允许递归过程、允许动态的申请建立和撤消存储空间、可变数组或允动态的申请建立和撤消存储空间、可变数组或允许用户自由申请和释放空间，那么，就需要采用许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。动态存储管理技术。因为对于这种程序在编译时无法知道它在运因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。的大小需待程序运行时动态地确定。

9、若一个数组所需的存储空间的大小在编译时若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定（静态）数组，否则称就已知道，则称它为确定（静态）数组，否则称为可变（动态）数组。为可变（动态）数组。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.1.2.1 栈式动态存储分配栈式动态存储分配分配策略是将整个程序的数据空间设计为一个分配策略是将整个程序的数据空间设计为一个栈。栈。在具有递归结构的语言程序中，每当调用一个在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。程工作结

10、束时就释放这部分空间。过程所需的数据空间包括两部分：过程所需的数据空间包括两部分： 生存期在本过程这次活动中的数据对象；生存期在本过程这次活动中的数据对象； 用以管理过程活动的记录信息用以管理过程活动的记录信息 。栈式动态存储分配策略适用于栈式动态存储分配策略适用于PASCAL，C，ALGOL之类具有递归结构的语言的实现。之类具有递归结构的语言的实现。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.1.2.2 堆式动态存储分配堆式动态存储分配如果一个程序语言提供用户自由地申请数据空如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制，或者不仅有过程而且有间和退还数据空

11、间的机制，或者不仅有过程而且有进程的程序结构，一般用堆式的动态存储分配方案。进程的程序结构，一般用堆式的动态存储分配方案。如如+中的中的new，delete，PASCAL的的new等机制等机制 。此时此时,空间的使用未必服从空间的使用未必服从“先申请后释放，后先申请后释放，后申请先释放申请先释放”的原则，那么栈式的动态分配方案就的原则，那么栈式的动态分配方案就不适用了。通常使用一种称为堆式的动态存储分配不适用了。通常使用一种称为堆式的动态存储分配方案。方案。 这种分配方式的存储管理技术甚为复杂，我们这种分配方式的存储管理技术甚为复杂，我们这里举出这种分配方法必须考虑的几个问题。这里举出这种分配

12、方法必须考虑的几个问题。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓堆式的动态存储分配策略堆式的动态存储分配策略:当运行程序要求一块体积为当运行程序要求一块体积为N的空同时，我们应该分配的空同时，我们应该分配哪一块给它呢？哪一块给它呢？理论上说，应从比理论上说，应从比N稍大一点的一个空闲块中取出稍大一点的一个空闲块中取出N个个单元，以便使大的空闲块派更大的用场。但这种做法较麻烦。单元，以便使大的空闲块派更大的用场。但这种做法较麻烦。因此，常常仍采用因此，常常仍采用“先碰上哪块比先碰上哪块比N大就从其中分出大就从其中分出N个单元个单元”的原则。但不论采用什么原则，整个大存区在一定的

13、原则。但不论采用什么原则，整个大存区在一定时间之后必然会变成零碎不堪。时间之后必然会变成零碎不堪。总有一个时候会出现异样的情形：运行程序要求一块体总有一个时候会出现异样的情形：运行程序要求一块体积为积为N的空间，但发现没有比的空间，但发现没有比N大的空闲块了，然而所有空闲大的空闲块了，然而所有空闲块的总和却要比块的总和却要比N大得多！出现这种情形时怎么办呢？这是大得多！出现这种情形时怎么办呢？这是一个比前面的问题难得多的问题。一个比前面的问题难得多的问题。解决办法似乎很简单，这就是，把所有空闲块连接在一解决办法似乎很简单，这就是，把所有空闲块连接在一起，形成一片可分配的连续空间。起，形成一片可

14、分配的连续空间。这里主要问题是，我们必须调整运行程序对各占用块的这里主要问题是，我们必须调整运行程序对各占用块的全部引用点。全部引用点。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓堆式的动态存储分配策略堆式的动态存储分配策略:另外，如果运行程序要求一块体积为另外，如果运行程序要求一块体积为N的空间，但的空间，但所有空闲块的总和也不够所有空闲块的总和也不够N，那又应怎么办呢？，那又应怎么办呢？有的管理系统采用一种叫做废品回收的办法来对付有的管理系统采用一种叫做废品回收的办法来对付这种局面。即寻找那些运行程序业己无用但尚未释放的这种局面。即寻找那些运行程序业己无用但尚未释放的占用块，

15、或者那些程序目前很少使用的占用块，把这些占用块，或者那些程序目前很少使用的占用块，把这些占用块收回来，重新分配。占用块收回来，重新分配。但是，我们如何知道哪些块运行时在使用或者目前但是，我们如何知道哪些块运行时在使用或者目前很少使用呢？即便知道了，一经收回后运行程序在某个很少使用呢？即便知道了，一经收回后运行程序在某个时候又要用它时又应该怎么办呢？时候又要用它时又应该怎么办呢？要使用废品回收技术，除了在语言上要有明确的具要使用废品回收技术，除了在语言上要有明确的具体限制外，还需要有特别的硬件措施，否则回收几乎不体限制外，还需要有特别的硬件措施，否则回收几乎不能实现。能实现。武汉理工大学计算机科

16、学系林泓武汉理工大学计算机科学系林泓堆式动态储分配的实现通常有如下两种途径：堆式动态储分配的实现通常有如下两种途径：1）定长块管理）定长块管理 堆式动态储分配最简单的实现是按定长块进行。堆式动态储分配最简单的实现是按定长块进行。初始化时，将堆存储空间分成长度相等的若干块，初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域，按照邻块的顺序把所有块链每块中指定一个链域，按照邻块的顺序把所有块链成一个链表，用指针成一个链表，用指针available指向链表中的第一块。指向链表中的第一块。 分配时每次都分配指针分配时每次都分配指针available所指的块，然所指的块，然后后availab

17、le指向相邻的下一块。归还时，把所归还指向相邻的下一块。归还时，把所归还的块插入链表。考虑插入方便，可以把所归还的块的块插入链表。考虑插入方便，可以把所归还的块插在插在available所指的块之前，然后所指的块之前，然后available指向新指向新归还的块。归还的块。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓占用占用占用占用占用占用空闲空闲空闲空闲空闲空闲available(a)占用占用占用占用空闲空闲空闲空闲空闲空闲(b)空闲空闲available图图10.3 定长块管理定长块管理武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓2）变长块管理）变长块管理 除了按定长

18、块进行分配之外，还可以根据需要除了按定长块进行分配之外，还可以根据需要分配长度不同的存储块，可以随要求而变。按这种分配长度不同的存储块，可以随要求而变。按这种方法，初始化时存储空间是一个整块。按照用户的方法，初始化时存储空间是一个整块。按照用户的需要，分配时先是从一个整块里分割出满足需要的需要，分配时先是从一个整块里分割出满足需要的一小块，以后，归还时，如果新归还的块能和现有一小块，以后，归还时，如果新归还的块能和现有的空间能合并，则合并成一块；如果不能和任何空的空间能合并，则合并成一块；如果不能和任何空闲块合并，则可以把空闲块链成一个链表。再进行闲块合并，则可以把空闲块链成一个链表。再进行分

19、配时，从空闲块链表中找出满足需要的一块，或分配时，从空闲块链表中找出满足需要的一块，或者整块分配出去，或者从该块上分割一小块分配出者整块分配出去，或者从该块上分割一小块分配出去。若空闲块表中有若干个满足需要的空闲块时，去。若空闲块表中有若干个满足需要的空闲块时，该分配哪一块呢该分配哪一块呢 ?通常有三种不同的分配策略：通常有三种不同的分配策略： 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓变长块管理通常有三种不同的分配策略：变长块管理通常有三种不同的分配策略： 首次满足法（时间优先）首次满足法（时间优先）; ;最优满足法（空间优先）最优满足法（空间优先）; ;最差满足法（时间优先）

20、。最差满足法（时间优先）。上述三种分配策略各有所长。上述三种分配策略各有所长。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.2 栈式存储分配的实现栈式存储分配的实现 前面提到，使用栈式存储分配策略意味着，运前面提到，使用栈式存储分配策略意味着，运行时每当进入一个过程，就在栈顶为该过程的临时行时每当进入一个过程，就在栈顶为该过程的临时工作单元，局部变量，机器状态及返回地址等信息工作单元，局部变量，机器状态及返回地址等信息分配所需的数据空间，当一个过程工作完毕返回时，分配所需的数据空间，当一个过程工作完毕返回时，它在栈顶的数据空间也即释放。它在栈顶的数据空间也即释放。 为讨论方便

21、，首先引入为讨论方便，首先引入一个术语一个术语-过程的活动记录过程的活动记录AR(Activation Record)。过。过程的活动记录是一段连续的程的活动记录是一段连续的存储区，用以存放过程的一存储区，用以存放过程的一次执行所需要的动态信息，次执行所需要的动态信息，这些信息可以如图这些信息可以如图10.6所示。所示。 图图 10.6 过程的活动记录过程的活动记录返回地址返回地址实参实参控制链控制链存取链存取链机器状态信息机器状态信息局部变量局部变量临时工作单元临时工作单元武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 临时工作单元临时工作单元：比如计算表达式过程中：比如计算表达式

22、过程中需存放中间结果用的临时值单元。需存放中间结果用的临时值单元。 局部变量局部变量：一个过程的局部变量。：一个过程的局部变量。 机器状态信息：机器状态信息：保存该过程执行前关于保存该过程执行前关于机器状态的信息，诸如程序计数器、寄机器状态的信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过存器的值，这些值都需要在控制从该过程返回时给予恢复。程返回时给予恢复。 存取链存取链：用以存取非局部变量，这些变：用以存取非局部变量，这些变量存放于其它过程的活动记录中。并不量存放于其它过程的活动记录中。并不是所有语言需要该信息。是所有语言需要该信息。 控制链控制链：指向调用该过程的那个过程的：指向

23、调用该过程的那个过程的活动记录，这也不是所有语言都需要的。活动记录，这也不是所有语言都需要的。 实参实参：也称形式单元，由调用过程向该：也称形式单元，由调用过程向该被调过程提供实参的值（或地址）。当被调过程提供实参的值（或地址）。当然在实际编译程序中，也常常使用机器然在实际编译程序中，也常常使用机器寄存器传递实参。寄存器传递实参。 返回地址返回地址：保存该被调过程返回后的地：保存该被调过程返回后的地址。址。 图图 10.6 过程的活动记录过程的活动记录返回地址返回地址实参实参控制链控制链存取链存取链机器状态信息机器状态信息局部变量局部变量临时工作单元临时工作单元静态链，指向静态直接外层最新活动

24、静态链，指向静态直接外层最新活动记录的起始地址，记录的起始地址，即指向即指向定义定义本过程本过程的的直接外层过程直接外层过程 （或主程序）运行时（或主程序）运行时最新最新活动记录的基地址活动记录的基地址。动态链动态链，指向，指向调用调用该过程前正该过程前正在运行过程的数据段基地址。在运行过程的数据段基地址。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.2.1 简单的栈式分配的实现简单的栈式分配的实现 程序结构特点程序结构特点:过程定义不嵌套，过程可递归过程定义不嵌套，过程可递归调用，含可变数组；例：调用，含可变数组；例： main 全局变量的说明全局变量的说明proc Rend

25、 R;proc Q end Q;主程序执行语句主程序执行语句 end main武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓TOP 临时工作单元临时工作单元局部简单变量局部简单变量局部数组的内情向量局部数组的内情向量 保存运保存运行过程前的状态行过程前的状态（返回地址，寄存器值（返回地址，寄存器值）实参实参（形式单元）和参数个数（形式单元）和参数个数 SP 存取链（存取链（静态链静态链）控制链控制链（动态链，动态链，老老SP）图图10.3 过程的活动记录过程的活动记录指向调用该过程的那个过程指向调用该过程的那个过程的最新活动记录的起始地址的最新活动记录的起始地址用以存取非局部变量，用

26、以存取非局部变量，这些变量存放于其他过这些变量存放于其他过程的活动记录中。程的活动记录中。Main Q R TOP R的活动记录的活动记录 SP 主程序全局主程序全局数据区数据区Q的活动记录的活动记录MainQQQ的活动记录的活动记录主程序全局主程序全局数据区数据区Q的活动记录的活动记录图图10.4 栈式存储分配栈式存储分配静态链，指向静态直接外层最新活静态链，指向静态直接外层最新活动记录的起始地址，动记录的起始地址，即指向即指向定义定义本本过程的过程的直接外层过程直接外层过程 （或主程序）（或主程序）运行时运行时最新最新活动记录的基地址活动记录的基地址。动态链动态链，指向，指向调用调用该过程

27、前正该过程前正在运行过程的数据段基地址。在运行过程的数据段基地址。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓TOPR R的数组区的数组区 SPR R的活动记录的活动记录Q Q的活动记录的活动记录主程序全局主程序全局数据区数据区图图10.6 10.6 分配了数组区之后的运行栈分配了数组区之后的运行栈TOP 临时工作单元临时工作单元局部简单变量局部简单变量局部数组的内情向量局部数组的内情向量 返回地址返回地址实参实参（形式单元）（形式单元） SP 参数个数参数个数控制链控制链（老（老SP）图图10.5 10.5 无嵌套定义无嵌套定义的过程活动记录内容的过程活动记录内容武汉理工大学计算

28、机科学系林泓武汉理工大学计算机科学系林泓 10.2.2 嵌套过程语言的栈式实现嵌套过程语言的栈式实现主要特点：主要特点： （语言）一个过程可以引用包围它的任一外层（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程过程所定义的标识符（如变量，数组或过程等）。等）。 （实现）一个过程可以引用它的任一外层过程（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。的最新活动记录中的某些数据。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓(1) program (1) program sortsort(input, output); /sort(inp

29、ut, output); /sort的过程头的过程头(2)(2)var a: array 0.10 of integer;var a: array 0.10 of integer;(3)(3)x: integer;x: integer;(4)(4)procedure procedure readarrayreadarray; /sort; /sort内嵌套定义的内嵌套定义的readarrayreadarray的过程头的过程头(5)(5)var i: integer;var i: integer;(6)(6)beginaendreadarray; /readarraybeginaendreada

30、rray; /readarray的过程体的过程体(7)(7)procedure procedure exchangeexchange(i,j: integer);(i,j: integer);/sort/sort内嵌套定义的内嵌套定义的exchangeexchange的过程头的过程头(8)(8)beginbegin(9) (9) x=ai; ai=aj; aj=x; /exchangex=ai; ai=aj; aj=x; /exchange的过程体的过程体(10)(10) endexchange;endexchange;(11)(11) procedure procedure quicksor

31、tquicksort(m,n: integer);(m,n: integer);/sort/sort内嵌套定义的内嵌套定义的quicksortquicksort的过程头的过程头(12) (12) var k,v: integer; var k,v: integer; (13)(13) function function partitionpartition(y,z:integer):integer;(y,z:integer):integer;/quicksort/quicksort内嵌套定义的内嵌套定义的partitionpartition的函数头的函数头(14)(14)var i.j:int

32、eger;var i.j:integer;(15)(15)begin a /partitionbegin a /partition的函数体的函数体(16)(16) vv(17) (17) exchangeexchange(i,j);(i,j);(18) (18) endpartition;endpartition;(19) (19) beginendquicksort; /quicksortbeginendquicksort; /quicksort的过程体的过程体(20) beginendsort. /sort(20) beginendsort. /sort的例程体的例程体 图图10.11 具

33、有嵌套过程的具有嵌套过程的PASCAL程序程序武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓图图10.11的的PASCAL程序中过程定义的嵌套情况如下：程序中过程定义的嵌套情况如下：sortreadarrayexchangequicksortpartition 局部变量局部变量a,x局部变量局部变量k,v过程过程quicksort的活动记的活动记录录过程过程sort的活动记录的活动记录图图10.12 存储栈布存储栈布局局记录下列信息：记录下列信息： 可以引用过程可以引用过程 sort的局部变量的局部变量武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 关键技术：解决对非局部量

34、的引用（存取）。关键技术：解决对非局部量的引用（存取）。设法跟踪每个外层过程的最新活动记录设法跟踪每个外层过程的最新活动记录AR的的位置。位置。跟踪办法：跟踪办法： 1. 用静态链（如用静态链（如PL/0的的SL）。）。 2. 用用DISPLAY表。表。跟踪的办法很多，我们介绍两种，一种是在过跟踪的办法很多，我们介绍两种，一种是在过程活动记录中增设存取链，指向包含该过程的直接程活动记录中增设存取链，指向包含该过程的直接外层过程的最新活动记录的起始位置。过程活动记外层过程的最新活动记录的起始位置。过程活动记录的内容如图录的内容如图10.13（a）所示。图）所示。图10.12所提到的情所提到的情况

35、可用图况可用图10.13（b）说明。）说明。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓图图 10.13 嵌套定义过程的活动记录和存储栈嵌套定义过程的活动记录和存储栈(a)局部变量局部变量存取链存取链控制链控制链TOPSP存取链存取链控制链控制链(老老SP)TOPSP(b)quicksort的的ARsort的的AR武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓再回到图再回到图10.11的例子。如果该程序的某次执行顺的例子。如果该程序的某次执行顺序为：序为：sortquicksortquicksortpartitionexchange即主程序即主程序(最外层过程最外层过程

36、)sort开始执行开始执行,继而进入过继而进入过程程quicksort，而又一次进入过程，而又一次进入过程quicksort，接着进入，接着进入过程过程partition，进入过程，进入过程exchange。图图10.15给出了进入过程给出了进入过程exchange之后运行栈的示之后运行栈的示意，我们仅把存取链和控制链的值标明。意，我们仅把存取链和控制链的值标明。 可以看出，过程可以看出，过程exchange由过程（函数）由过程（函数）partition调用，但调用，但exchange的直接外层过程是的直接外层过程是sort，所以过程所以过程exchange的活动记录的存取链指向的活动记录的存

37、取链指向sort的活的活动记录的始址。动记录的始址。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓图图10.15 运行栈运行栈静态链，指向静态直接外层最新静态链，指向静态直接外层最新活动记录的起始地址，活动记录的起始地址，动态链动态链，指向，指向调用调用该过程前正该过程前正在运行过程的数据段基地址。在运行过程的数据段基地址。exchange的活动记录的活动记录partition的活动记录的活动记录quicksort的活动记录的活动记录quicksort的活动记录的活动记录sort的活动记录的活动记录武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 解决对非局部量的引用（存取

38、）的有效办解决对非局部量的引用（存取）的有效办法是用法是用Display表。表。Display表表-嵌套层次显示表嵌套层次显示表，即每进入一个过，即每进入一个过程后，在建立它的活动记录的同时建立一张程后，在建立它的活动记录的同时建立一张Display表。表。当前激活过程的层次为当前激活过程的层次为K，它的，它的Display表含有表含有K+1个单元，依次存放着现行层，直接外层个单元，依次存放着现行层，直接外层直至直至最外层的每一过程的最新活动记录的基地址。最外层的每一过程的最新活动记录的基地址。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓例：例：program main(i,0);

39、程序结构图程序结构图proc R(c,d);Rend /*R*/proc P (a); 主主 proc Q (b);P Q call R R(x,y);end /*Q*/ call QQ(z); call Pend /*P*/call RP（W）；）；R（U，V）；）；end /*main*/武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R主程序的主程序的活动记录活动记录 d0spdisplaytop（1）d1d0 P 的的活动记录活动记录主程序的主程序的活动记录活动记录 displaysptop（2）武

40、汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓用用Display表的方案表的方案 主程序主程序-P-Q-Rd2d1d0Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录 displaysptop（3）R 的的活动记录活动记录 Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录 d1d0 displaytopsp（4）武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓DISPLAY表的维护和建立表的维护和建立 DISPLAY表表d 运行栈运行栈 0 主程活动记录地址主程活动记录地址 1 R活动记录地址活动记录地址 .

41、武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 当过程的层次为当过程的层次为n，它的它的 display为为n+1个个值。值。 一个过程被调用时，一个过程被调用时，从调用过程的从调用过程的DISPLAY表中自下向表中自下向上抄录上抄录n个个SP值，再加值，再加上本层的上本层的SP值。值。全局全局DISPLAY地址地址 0 老老 SP 1 返回地址返回地址 2 全局全局 DISPLAY地址地址 3 参数个数参数个数 4形式单元形式单元 . . . d DISPLAY . . . 简单变量简单变量 数组内情向量数组内情向量 临时变量临时变量 武汉理工大学计算机科学系林泓武汉理工大学计算机

42、科学系林泓 分程序结构分程序结构Procedure A(m,n); integer m,n; B1:begin real z; array Bm:n; B2:begin real d, e; L3: 2 end; B4:begin array C1:m; 1 B5:begin real e; L6: 5 4 end; end; L8:end; 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 分程序结构的存储分配方案分程序结构的存储分配方案 处理分程序结构存储分配方案的一种简单办处理分程序结构存储分配方案的一种简单办法是，把分程序看成法是，把分程序看成 “无名无参过无名无参过 程程”，

43、它在，它在哪里定义就在哪里被调用。因此，可以把处理过哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法程的存储办法应用到处理分程序中。但这种做法是极为低效的。是极为低效的。 一则，每逢进入一则，每逢进入 一个分程序，就照样建立一个分程序，就照样建立连接数据和连接数据和DISPLAY表表,这是不必要的。这是不必要的。 二则二则 ，当从内层分程序向外层转移时，可，当从内层分程序向外层转移时，可能同时要结束若干个分程序。能同时要结束若干个分程序。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓按照过程处理办法，意味着必须一层一层地按照过程处理办法，意味着必须

44、一层一层地通过通过“返回返回” 来恢复所要到达的那个分程序的来恢复所要到达的那个分程序的数据区，但不能直接到达。数据区，但不能直接到达。例如：如果有一个从第例如：如果有一个从第5层分程序转出到达层分程序转出到达第第1层分程序的标号层分程序的标号L，虽然在第，虽然在第5层分程序工作层分程序工作时知道时知道L所属的层数，我们极易从所属的层数，我们极易从DISPLAY中获中获得第得第1层分程序的活动记录基址（层分程序的活动记录基址（SP），但是怎），但是怎么知道第么知道第1层分程序进入时的层分程序进入时的TOP呢？唯一的办呢？唯一的办法是从法是从 5,4,3和和2各层顺序退出。但这种办法是很各层顺序

45、退出。但这种办法是很浪费时间的。浪费时间的。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 为了解决上述问题，可采取两种措施。第一，为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己的栈顶指示器对每个过程或分程序都建立有自己的栈顶指示器TOP，代替原来仅有过程的栈顶指示器，代替原来仅有过程的栈顶指示器, 每个每个TOP的值保存在各自活动记录中。这样，上述的的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作第二个问题便可解决。第二，不把分程序看作“无参过程无参过程”，每个分程序享用包围它的那个最，每个分程序享用包围它的那个最近过程的近过程

46、的DISPLAY。每个分程序都隶属于某个。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。个过程进行编号的。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓： 每个过程被当作是每个过程被当作是0层分程序。而过程体分程层分程序。而过程体分程序（假定是一个分程序）当作是它所管辖的第序（假定是一个分程序）当作是它所管辖的第1层层分程序。分程序。 这样，每个过程的活动记录所含的内容有：这样，每个过程的活动记录所含的内容有：1.过程的过程的TOP值，它指向过程活动记录的栈顶位置。值，它指向过程活动记录的栈顶位置。2.连接

47、数据，共四项：连接数据，共四项： (1)老老SP值；值；(2)返回地址；返回地址；(3)全局全局DISPAY地址；地址；(4)调用时的栈顶单元地址，老调用时的栈顶单元地址，老TOP。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 3. 参数个数和形式单元参数个数和形式单元 4. DISPAY表。表。5. 过程所辖的各分程序的局部数据单元。过程所辖的各分程序的局部数据单元。 对于对于每个分程序来说，它们包括：每个分程序来说，它们包括：（1)分程序的分程序的TOP值。当进入分程序时它含现行值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的新高度（分程栈顶地址，以后，用来定义栈的新高度

48、（分程序的序的TOP值）；值）；（2)分程序的局部变量，分程序的局部变量， 数组内情向量和临时工数组内情向量和临时工作单元。作单元。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓过程的活动记录过程的活动记录B的的 数数组组B的内情向量的内情向量变量变量 z z kdD I S P L A Y6 形式单元形式单元m,nm,n5 参数个数：参数个数：4调用时的栈顶地址（老）调用时的栈顶地址（老）3 全局全局D I S P L A Y 地址地址2返回地址返回地址1老老 S P0 过程的，指向活动记录之顶过程的，指向活动记录之顶SP数数组的内情向量组的内情向量B的的B的的B的的变量变量 e

49、e变量变量 d d和和e e武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓B B1T OB的的 信信 息息 向向 量量 ZB1的的 PD I S P L A Y 形式单元形式单元 m , n 2连连 接接数数 据据A的的T O P (b)进进 入入 分分 程程 序序 B1D I S P L A Y 形式单元形式单元 m , n 2连连 接接数数 据据 (a) 到到 达达 标标 号号 B1处处A的的T O P武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 （d d）进入分程序）进入分程序B2 数数 组组 B e dB22的的 T O PB 的的 信信 息息 向向 量量 zB1

50、的的 T O PD I S P L A Y 形式单元形式单元 m,n2连接连接 数数 据据A 的的 T O P 数数 组组 BB 的的 信信 息息 向向 量量 zB1 的的 T O PD I S P L A Y 形式单元形式单元 m,n2连连 接接 数数 据据A 的的 T O P （c c）数组分配之后）数组分配之后武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓(e) 进入分程序进入分程序B4分配数组分配数组C之后之后 数数 组组C 数数 组组BC的的 向向 量量 内内 情情B4的的T O PB的的 内内 情情 向向 量量 ZB1 的的T O PD I S P L A Y 形式单元形

51、式单元 m,n 2连连 接接 数数 据据A的的T O P (f) 进入分程序进入分程序B5 数数 组组 C 数数 组组 B eB5的的T O PC 的的 内内 情情 向向 量量B4的的T O PB 的的 内内 情情 向向 量量 zB1的的T O PD I S P L A Y 形式单元形式单元 m,n 2连接数据连接数据A的的T O P 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.3 参数传递参数传递(1)procedure exchangel(i,j:integer);(2) var x:integer;(3) begin;(4) x:=ai; ai:=aj; aj:=x(5

52、) end; 带有非局部变量和形参的带有非局部变量和形参的PASCAL过程过程非局变量非局变量ai和和aj的的值进行交换，值进行交换，i,j为形参（在为形参（在这里是传值）这里是传值）武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 (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;

53、 b:=2;(12) swap(a,b);(13) writeln(a=,a);writeln(b=,b)(14)end. 带有过程带有过程swap的的PASCAL程序程序武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 10.3.1 传值（值调用传值（值调用call-by-value）特点是对形式参数的任何运算不影响实参特点是对形式参数的任何运算不影响实参的值。的值。 例如：过程例如：过程 swap(x,y:integer); swap(a,b）；）； 其结果：其结果： a,b调用前的值不改变。调用前的值不改变。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓传值的实现传值的

54、实现（1）形式参数当作过程的局部变量处理，即在）形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以这些存储位置即是我们所说的形式单元（用以存放实参）。存放实参）。（2）调用过程计算实参的值，并将其放在对应）调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。形式单元开辟的空间中。（3）被调用过程执行时，就像使用局部变量一）被调用过程执行时，就像使用局部变量一样使用这些形式单元。样使用这些形式单元。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓procedure swap

55、( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 调用调用swap(a,b) 过程将不会影响过程将不会影响a和和b的值。的值。 其结果等价于执行下列运算：其结果等价于执行下列运算： x :=a； y :=b； temp :=x； x :=y； y :=temp武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓10.3.2 传地址（变量参数传地址（变量参数call-by-address 、 call-by-location 、 call- by- reference ） 例如：过程例如：过程 swap(var x,y:integer); swap(a,b）；）； （ a,b为为调用时的实参调用时的实参 ） 调用结果调用结果a,b的值被改变。的值被改变。武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓传地址的实现传地址的实现把实在参数的地址传递给相应的形参，即把实在参数的地址传递给相应的形参，