目标程序运行时存储组织

1、关于目标程序运行时的存储组织第一张，PPT共五十四页，创作于2022年6月 从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。 数据空间应包括：用户定义的各种类型的数据对象（变量和常数）所 需的存储空间；作为保留中间结果和传递参数的临时工作单元；调用过程时所需的连接单元；组织输入/输出所需的缓冲区。 目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。 第二张，PPT共五十四页，创作于2022年6月 因此运行时的存储区常常划分成：目标

2、代码区、静态数据区、栈区和堆区，如图10.1 。目标代码区code静态数据区static栈Stack堆heap图10.1 目标程序运行时存储区的典型划分数据空间第三张，PPT共五十四页，创作于2022年6月所谓数据空间的分配，本质上看，是将程序中的每个名字与一个存储位置关联起来，该存储位置用以保存名字的值。编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。第四张，PPT共五十四页，创作于2022年6月决定存储管理复杂程度的因素-源语言本身，比如源语言允许的数据类型有多少？语言中允许的数据项是静态确定还是动态确定？程序结构有什么特点，是段结

3、构还是分程序结构？过程定义是否允许嵌套？等等。源语言的结构特点、源语言的数据类型、源语言中决定名字作用域的规则等因素影响存储空间的管理和组织的复杂程度，决定数据空间分配的基本策略。 第五张，PPT共五十四页，创作于2022年6月10.1 数据空间的三种不同使用方法和管理方法数据空间的使用和管理方法: 简单的栈式分配方案 嵌套过程的栈式分配方案 分程序结构的存储分配方案静态存储分配、动态存储分配栈式堆式第六张，PPT共五十四页，创作于2022年6月10.1.1 静态存储分配如果在编译时能确定目标程序运行中所需的全部的数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储

4、位置，称这种分配策略为静态存储分配。如C中的静态变量，外部变量等。第七张，PPT共五十四页，创作于2022年6月10.1.2 动态存储分配如果一个程序设计语言允许递归过程、允许动态的申请建立和撤消存储空间、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定（静态）数组，否则称为可变（动态）数组。第八张，PPT共五十四页，创作于2022年6月10.1.2.1 栈式动态存储分配这种分配策略是将整个程序的数据

5、空间设计为一个栈。在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。过程所需的数据空间包括两部分： 生存期在本过程这次活动中的数据对象； 用以管理过程活动的记录信息 。栈式动态存储分配策略适用于PASCAL，C，ALGOL之类具有递归结构的语言的实现。 第九张，PPT共五十四页，创作于2022年6月10.1. 2.2 堆式动态存储分配如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制，或者不仅有过程而且有进程的程序结构，一般用堆式的动态存储分配方案。如+中的new，delete，PASCAL的new，等机制 。此时,空

6、间的使用未必服从“先申请后释放，后申请先释放”的原则，那么栈式的动态分配方案就不适用了。通常使用一种称为堆式的动态存储分配方案。 这种分配方式的存储管理技术甚为复杂，我们这里举出这种分配方法必须考虑的几个问题。 第十张，PPT共五十四页，创作于2022年6月堆式的动态存储分配策略:当运行程序要求一块体积为N的空间时，我们应该分配哪一块给它呢？理论上说，应从比N稍大一点的一个空闲块中取出N个单元，以便使大的空闲块派更大的用场。但这种做法较麻烦。因此，常常仍采用“先碰上哪块比N大就从其中分出N个单元”的原则。但不论采用什么原则，整个大存区在一定时间之后必然会变成零碎不堪。总有一个时候会出现异样的情

7、形：运行程序要求一块体积为N的空间，但发现没有比N大的空闲块了，然而所有空闲块的总和却要比N大得多！出现这种情形时怎么办呢？这是一个比前面的问题难得多的问题。解决办法似乎很简单，这就是，把所有空闲块连接在一起，形成一片可分配的连续空间。这里主要问题是，我们必须调整运行程序对各占用块的全部引用点。 第十一张，PPT共五十四页，创作于2022年6月堆式的动态存储分配策略:另外，如果运行程序要求一块体积为N的空间，但所有空闲块的总和也不够N，那又应怎么办呢？有的管理系统采用一种叫做废品回收的办法来对付这种局面。即寻找那些运行程序业己无用但尚未释放在占用块，或者那些行程序目前很少使用的占用块，把这此占

8、用块收回来，重新分配。但是，我们如何知道哪些块运行时在使用或者目前很少使用呢？即便知道了，一经收回后运行程序在某个时候又要用它时又应该怎么办呢？要使用废品回收技术，除了在语言上要有明确的具体限制外，还需要有特别的硬件措施，否则回收几乎不能实现。第十二张，PPT共五十四页，创作于2022年6月堆式动态储分配的实现通常有如下两种途径：1）定长块管理 堆式动态储分配最简单的实现是按定长块进行。初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域，按照邻块的顺序把所有块链成一个链表，用指针available指向链表中的第一块。 分配时每次都分配指针available所指的块，然后availa

9、ble指向相邻的下一块。归还时，把所归还的块插入链表。考虑插入方便，可以把所归还的块插在available所指的块之前，然后available指向新归还的块。第十三张，PPT共五十四页，创作于2022年6月占用占用占用空闲空闲空闲available(a)占用占用空闲空闲空闲(b)空闲available图10.3 定长块管理第十四张，PPT共五十四页，创作于2022年6月2）变长块管理 除了按定长块进行分配之外，还可以根据需要分配长度不同的存储块，可以随要求而变。按这种方法，初始化时存储空间是一个整块。按照用户的需要，分配时先是从一个整块里分割出满足需要的一小块，以后，归还时，如果新归还的块能和

10、现有的空间能合并，则合并成一块；如果不能和任何空闲块合并，则可以把空闲块链成一个链表。再进行分配时，从空闲块链表中找出满足需要的一块，或者整块分配出去，或者从该块上分割一小块分配出去。若空闲块表中有若干个满足需要的空闲块时，该分配哪一块呢 ?通常有三种不同的分配策略： 第十五张，PPT共五十四页，创作于2022年6月变长块管理通常有三种不同的分配策略： 首次满足法（时间优先）;最优满足法（空间优先）;最差满足法（时间优先）。上述三种分配策略各有所长。 第十六张，PPT共五十四页，创作于2022年6月10.2 栈式存储分配的实现 前面提到，使用栈式存储分配策略意味着，运行时每当进入一个过程，就在

11、栈顶为该过程的临时工作单元，局部变量，机器状态及返回地址等信息分配所需的数据空间，当一个过程工作完毕返回时，它在栈顶的数据空间也即释放。 为讨论方便，首先引入一个术语-过程的活动记录AR(Activation Record)。过程的活动记录是一段连续的存储区，用以存放过程的一次执行所需要的动态信息，这些信息可以如图10.6所示。 图 10.6 过程的活动记录返回地址实参控制链存取链机器状态信息局部变量临时工作单元第十七张，PPT共五十四页，创作于2022年6月 临时工作单元：比如计算表达式过程中需存放中间结果用的临时值单元。 局部变量：一个过程的局部变量。 机器状态信息：保存该过程执行前关于机

12、器状态的信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。 存取链：用以存取非局部变量，这些变量存放于其它过程的活动记录中。并不是所有语言需要该信息。 控制链：指向调用该过程的那个过程的活动记录。 实参：也称形式单元，由调用过程向该被调过程提供实参的值（或地址）。当然在实际编译程序中，也常常使用机器寄存器传递实参。 返回地址：保存该被调过程返回后的地址。 图 10.6 过程的活动记录返回地址实参控制链存取链机器状态信息局部变量临时工作单元静态链，指向静态直接外层最新活动记录的起始地址，即指向定义本过程的直接外层过程 （或主程序）运行时最新活动记录的基地址。动态链，指向

13、调用该过程前正在运行过程的数据段基地址。第十八张，PPT共五十四页，创作于2022年6月10.2.1 简单的栈式分配的实现 程序结构特点:过程定义不嵌套，过程可递归调用，含可变数组；例： program main 全局变量的说明proc Rend R;proc Q end Q;主程序执行语句 end main图 10.7 过程定义不嵌套的程序结构 第十九张，PPT共五十四页，创作于2022年6月这种情况下，采用栈式动态分配策略，即，运行时，每当进入一个过程，则为该过程分配一段存储区，当一个过程工作完毕返回时，它所占用的存储区可释放。程序运行时的存储空间(栈)中在某一时刻可能会包含某个过程的几个

14、活动记录（某个过程递归调用的情况）；另外，同样的一个存储位置，在不同运行时刻可能分配给不同的数据对象。例如图10.7的程序结构中，若主程序调用了过程Q，Q又调用了R，在R进入运行后的存储结构如图10.8（a）所示。若主程序调用了过程Q，Q递归调用自己，在Q过程第二次进入运行后的存储结构如图10.8（b）所示。第二十张，PPT共五十四页，创作于2022年6月TOP 临时工作单元局部简单变量局部数组的内情向量 保存运行过程前的状态（返回地址，寄存器值）实参（形式单元）和参数个数 SP 存取链（静态链）控制链（动态链，老SP）图10.6 过程的活动记录Main Q R TOP R的活动记录 SP 主

15、程序全局数据区Q的活动记录MainQQQ的活动记录主程序全局数据区Q的活动记录图10.8 栈式存储分配静态链，指向静态直接外层最新活动记录的起始地址，即指向定义本过程的直接外层过程 （或主程序）运行时最新活动记录的基地址。动态链，指向调用该过程前正在运行过程的数据段基地址。指向调用该过程的那个过程的最新活动记录的起始地址用以存取非局部变量，这些变量存放于其他过程的活动记录中。第二十一张，PPT共五十四页，创作于2022年6月TOP 临时工作单元局部简单变量局部数组的内情向量 返回地址实参（形式单元） SP 参数个数控制链（老SP）图10.9 无嵌套定义的过程活动记录内容 常常使用两个指针指示栈

16、最顶端的数据区，一个称为SP，一个称为TOP。SP总是指向现行过程活动记录的起点，TOP则始终指向已占用的栈顶单元。 这种语言若含有可变数组，则其过程活动记录的内容可如图10.9所示。这里把控制链也称作老SP，即调用该过程的那个过程的最新活动记录的起点。 第二十二张，PPT共五十四页，创作于2022年6月 10.2.2 嵌套过程语言的栈式实现主要特点：（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。第二十三张，PPT共五十四页，创作于2022年6月(1) program sort(input

17、, output); /sort的过程头(2)var a: array 0.10 of integer;(3)x: integer;(4)procedure readarray; /sort内嵌套定义的readarray的过程头(5)var i: integer;(6)beginaendreadarray; /readarray的过程体(7)procedure exchange(i,j: integer);/sort内嵌套定义的exchange的过程头(8)begin(9) x=ai; ai=aj; aj=x; /exchange的过程体(10) endexchange;(11) proced

18、ure quicksort(m,n: integer);/sort内嵌套定义的quicksort的过程头(12) var k,v: integer; (13) function partition(y,z:integer):integer;/quicksort内嵌套定义的partition的函数头(14)var i.j:integer;(15)begin a /partition的函数体(16) v(17) exchange(i,j);(18) endpartition;(19) beginendquicksort; /quicksort的过程体(20) beginendsort. /sort

19、的例程体 图10.11 具有嵌套过程的PASCAL程序第二十四张，PPT共五十四页，创作于2022年6月图10.11的PASCAL程序中过程定义的嵌套情况如下：sortreadarrayexchangequicksortpartition 局部变量a,x局部变量k,v过程quicksort的活动记录过程sort的活动记录图10.12 存储栈布局记录下列信息： 可以引用过程 sort的局部变量第二十五张，PPT共五十四页，创作于2022年6月 关键技术：解决对非局部量的引用（存取）。设法跟踪每个外层过程的最新活动记录AR的位置。跟踪办法： 1. 用静态链（如PL/0的SL）。 2. 用DISPL

20、AY表。跟踪的办法很多，我们介绍两种，一种是在过程活动记录中增设存取链，指向包含该过程的直接外层过程的最新活动记录的起始位置。过程活动记录的内容如图10.13（a）所示。图10.12所提到的情况可用图10.13（b）说明。 第二十六张，PPT共五十四页，创作于2022年6月图 10.13 嵌套定义过程的活动记录和存储栈(a)局部变量存取链控制链TOPSP存取链控制链(老SP)TOPSP(b)quicksort的ARsort的AR第二十七张，PPT共五十四页，创作于2022年6月再回到图10.11的例子。如果该程序的某次执行顺序为：sortquicksortquicksortpartitione

21、xchange即主程序(最外层过程)sort开始执行,继而进入过程quicksort，而又一次进入过程quicksort，接着进入过程partition，进入过程exchange。图10.15给出了进入过程exchange之后运行栈的示意，我们仅把存取链和控制链的值标明。 可以看出，过程exchange由过程（函数）partition调用，但exchange的直接外层过程是sort，所以过程exchange的活动记录的存取链指向sort的活动记录的始址。 第二十八张，PPT共五十四页，创作于2022年6月图10.15 运行栈静态链，指向静态直接外层最新活动记录的起始地址，动态链，指向调用该过程

22、前正在运行过程的数据段基地址。exchange的活动记录partition的活动记录quicksort的活动记录quicksort的活动记录sort的活动记录第二十九张，PPT共五十四页，创作于2022年6月 解决对非局部量的引用（存取）的有效办法是用Display表。Display表-嵌套层次显示表，即每进入一个过程后，在建立它的活动记录的同时建立一张Display表。DISPLAY表是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，直至最外层（0层，主程序层）等每一层过程的最新活动记录的基地址（SP），当前激活过程的层次为K，则Display表就含有K+1个

23、单元 。第三十张，PPT共五十四页，创作于2022年6月例：见P238-239第三十一张，PPT共五十四页，创作于2022年6月 分程序结构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; 第三十二张，PPT共五十四页，创作于2022年6月 分程序结构的存储分配方案 处理分程序结构存储分配方案的一种简单办法是，把分程序看成 “无名无参

24、过 程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。 一则，每逢进入 一个分程序，就照样建立连接数据和DISPLAY表,这是不必要的。 二则 ，当从内层分程序向外层转移时，可能同时要结束若干个分程序。第三十三张，PPT共五十四页，创作于2022年6月按照过程处理办法，意味着必须一层一层地通过“返回” 来恢复所要到达的那个分程序的数据区，但不能直接到达。例如：如果有一个从第5层分程序转出到达第1层分程序的标号L，虽然在第5层分程序工作时知道L所属的层数，我们极易从DISPLAY中获得第1层分程序的活动记录基址（SP），但是怎么知道第1层

25、分程序进入时的TOP呢？唯一的办法是从 5,4,3和2各层顺序退出。但这种办法是很浪费时间的。第三十四张，PPT共五十四页，创作于2022年6月 为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己的栈顶指示器TOP，代替原来仅有过程的栈顶指示器, 每个TOP的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作“无参过程”，每个分程序享用包围它的那个最近过程的DISPLAY。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。第三十五张，PPT共五十四页，创作于2022年6月： 每个过程被当作是0层分程序。而过程体分程序

26、（假定是一个分程序）当作是它所管辖的第1层分程序。 这样，每个过程的活动记录所含的内容有：1.过程的TOP值，它指向过程活动记录的栈顶位置。2.连接数据，共四项： (1)老SP值；(2)返回地址；(3)全局DISPAY地址；(4)调用时的栈顶单元地址，老TOP。第三十六张，PPT共五十四页，创作于2022年6月 3. 参数个数和形式单元 4. DISPAY表。5. 过程所辖的各分程序的局部数据单元。 对于每个分程序来说，它们包括：（1)分程序的TOP值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的新高度（分程序的TOP值）；（2)分程序的局部变量， 数组内情向量和临时工作单元。第三十七张

27、，PPT共五十四页，创作于2022年6月过程的活动记录B的 数组B的内情向量变量 z kdD I S P L A Y6形式单元m,n5参数个数：4调用时的栈顶地址（老）3全局D I S P L A Y 地址2返回地址1老S P0过程的，指向活动记录之顶SP数组的内情向量B的B的B的变量 e变量 d和e第三十八张，PPT共五十四页，创作于2022年6月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

28、处A的T O P第三十九张，PPT共五十四页，创作于2022年6月 （d）进入分程序B2 数 组B e dB22的T O PB 的 信 息 向 量 zB1的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）数组分配之后第四十张，PPT共五十四页，创作于2022年6月(e)进入分程序B4分配数组C之后 数 组C 数 组BC的 向 量 内 情B4的T O PB的 内 情 向 量 ZB1 的T O PD I S P L A Y 形式单元

29、 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 第四十一张，PPT共五十四页，创作于2022年6月10.3 参数传递(1)procedure exchangel(i,j:integer);(2) var x:integer;(3) begin;(4) x:=ai; ai:=aj; aj:=x(5) end; 带有非局部变量和形参的PASCAL过程非局变量ai和aj的值进行交换，i,j为形

30、参（在这里是传值）第四十二张，PPT共五十四页，创作于2022年6月 (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. 带有过程swap的PASCAL程序第四十三张，P

31、PT共五十四页，创作于2022年6月 10.3.1 传值（值调用call-by-value）特点是对形式参数的任何运算不影响实参的值。 例如：过程 swap(x,y:integer); swap(a,b）； 其结果： a,b调用前的值不改变。第四十四张，PPT共五十四页，创作于2022年6月传值的实现（1）形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。（2）调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。（3）被调用过程执行时，就像使用局部变量一样使用这些形式单元。第四十五张，PPT共五十四页，创作于

32、2022年6月procedure swap( 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第四十六张，PPT共五十四页，创作于2022年6月10.3.2 传地址（变量参数call-by-address 、 call-by-location 、 call- by- reference ） 例如：过程 swap(var x,y:integer); swap(a,b）； （ a,b为调用时的实参 ） 调用结果a,b的值被改变。第四十七张，PPT共五十四页，创作于2022年6月传地址的实现把实在参数的地址传递给相应的形参，即 调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：（1）实