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

武汉理工大学计算机科学系林泓第10章目标程序运行时的存储组织10.1数据空间的三种不同使用方法和管理方法10.2栈式存储分配的实现10.3参数传递10.4过程调用、过程进入和过程返回武汉理工大学计算机科学系林泓从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的配置和数据空间的分配。数据空间应包括：用户定义的各种类型的数据对象（变量和常数）所需的存储空间；作为保留中间结果和传递参数的临时工作单元；调用过程时所需的连接单元；以及组织输入/输出所需的缓冲区。目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。武汉理工大学计算机科学系林泓因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区，如图10.1。目标代码区静态数据区栈Stack堆heap图10.1目标程序运行时存储区的典型划分武汉理工大学计算机科学系林泓所谓数据空间的分配，本质上看，是将程序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。在程序设计语言语义学中，使用术语environment表示将一个名字映射到一个存储位置的函数，术语state表示存储位置到值的映射，如图10.2所示。图10.2名字到存储位置、到值的映射武汉理工大学计算机科学系林泓编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。决定存储管理复杂程度的因素--源语言本身，比如源语言允许的数据类型有多少？语言中允许的数据项是静态确定还是动态确定？程序结构有什么特点，是段结构还是分程序结构？过程定义是否允许嵌套？等等。源语言的结构特点、源语言的数据类型、源语言中决定名字作用域的规则等因素影响存储空间的管理和组织的复杂程度，决定数据空间分配的基本策略。武汉理工大学计算机科学系林泓10.1数据空间的三种不同使用方法和管理方法数据空间的使用和管理方法:简单的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储分配方案静态存储分配、动态存储分配——栈式堆式武汉理工大学计算机科学系林泓10.1.1静态存储分配如果在编译时能确定目标程序运行中所需的全部的数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，称这种分配策略为静态存储分配。如C中的静态变量，外部变量等。武汉理工大学计算机科学系林泓10.1.2动态存储分配如果一个程序设计语言允许递归过程、允许动态的申请建立和撤消存储空间、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定（静态）数组，否则称为可变（动态）数组。武汉理工大学计算机科学系林泓10.1.2.1栈式动态存储分配分配策略是将整个程序的数据空间设计为一个栈。在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。过程所需的数据空间包括两部分：①生存期在本过程这次活动中的数据对象；②用以管理过程活动的记录信息。栈式动态存储分配策略适用于PASCAL，C，ALGOL之类具有递归结构的语言的实现。武汉理工大学计算机科学系林泓10.1.2.2堆式动态存储分配如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制，或者不仅有过程而且有进程的程序结构，一般用堆式的动态存储分配方案。如Ｃ++中的new，delete，PASCAL的new等机制。此时,空间的使用未必服从“先申请后释放，后申请先释放”的原则，那么栈式的动态分配方案就不适用了。通常使用一种称为堆式的动态存储分配方案。这种分配方式的存储管理技术甚为复杂，我们这里举出这种分配方法必须考虑的几个问题。武汉理工大学计算机科学系林泓堆式的动态存储分配策略:当运行程序要求一块体积为N的空同时，我们应该分配哪一块给它呢？理论上说，应从比N稍大一点的一个空闲块中取出N个单元，以便使大的空闲块派更大的用场。但这种做法较麻烦。因此，常常仍采用“先碰上哪块比N大就从其中分出N个单元”的原则。但不论采用什么原则，整个大存区在一定时间之后必然会变成零碎不堪。总有一个时候会出现异样的情形：运行程序要求一块体积为N的空间，但发现没有比N大的空闲块了，然而所有空闲块的总和却要比N大得多！出现这种情形时怎么办呢？这是一个比前面的问题难得多的问题。解决办法似乎很简单，这就是，把所有空闲块连接在一起，形成一片可分配的连续空间。这里主要问题是，我们必须调整运行程序对各占用块的全部引用点。武汉理工大学计算机科学系林泓堆式的动态存储分配策略:另外，如果运行程序要求一块体积为N的空间，但所有空闲块的总和也不够N，那又应怎么办呢？有的管理系统采用一种叫做废品回收的办法来对付这种局面。即寻找那些运行程序业己无用但尚未释放的占用块，或者那些行程序目前很少使用的占用块，把这些占用块收回来，重新分配。但是，我们如何知道哪些块运行时在使用或者目前很少使用呢？即便知道了，一经收回后运行程序在某个时候又要用它时又应该怎么办呢？要使用废品回收技术，除了在语言上要有明确的具体限制外，还需要有特别的硬件措施，否则回收几乎不能实现。武汉理工大学计算机科学系林泓堆式动态储分配的实现通常有如下两种途径：1）定长块管理堆式动态储分配最简单的实现是按定长块进行。初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域，按照邻块的顺序把所有块链成一个链表，用指针available指向链表中的第一块。分配时每次都分配指针available所指的块，然后available指向相邻的下一块。归还时，把所归还的块插入链表。考虑插入方便，可以把所归还的块插在available所指的块之前，然后available指向新归还的块。武汉理工大学计算机科学系林泓占用占用占用空闲空闲空闲available(a)占用占用空闲空闲空闲(b)空闲available图10.3定长块管理武汉理工大学计算机科学系林泓2）变长块管理除了按定长块进行分配之外，还可以根据需要分配长度不同的存储块，可以随要求而变。按这种方法，初始化时存储空间是一个整块。按照用户的需要，分配时先是从一个整块里分割出满足需要的一小块，以后，归还时，如果新归还的块能和现有的空间能合并，则合并成一块；如果不能和任何空闲块合并，则可以把空闲块链成一个链表。再进行分配时，从空闲块链表中找出满足需要的一块，或者整块分配出去，或者从该块上分割一小块分配出去。若空闲块表中有若干个满足需要的空闲块时，该分配哪一块呢?通常有三种不同的分配策略：武汉理工大学计算机科学系林泓变长块管理通常有三种不同的分配策略：•首次满足法（时间优先）;•最优满足法（空间优先）;•最差满足法（时间优先）。上述三种分配策略各有所长。武汉理工大学计算机科学系林泓10.2栈式存储分配的实现前面提到，使用栈式存储分配策略意味着，运行时每当进入一个过程，就在栈顶为该过程的临时工作单元，局部变量，机器状态及返回地址等信息分配所需的数据空间，当一个过程工作完毕返回时，它在栈顶的数据空间也即释放。为讨论方便，首先引入一个术语--过程的活动记录AR(ActivationRecord)。过程的活动记录是一段连续的存储区，用以存放过程的一次执行所需要的动态信息，这些信息可以如图10.6所示。图10.6过程的活动记录返回地址实参控制链存取链机器状态信息局部变量临时工作单元武汉理工大学计算机科学系林泓①临时工作单元：比如计算表达式过程中需存放中间结果用的临时值单元。②局部变量：一个过程的局部变量。③机器状态信息：保存该过程执行前关于机器状态的信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。④存取链：用以存取非局部变量，这些变量存放于其它过程的活动记录中。并不是所有语言需要该信息。⑤控制链：指向调用该过程的那个过程的活动记录，这也不是所有语言都需要的。⑥实参：也称形式单元，由调用过程向该被调过程提供实参的值（或地址）。当然在实际编译程序中，也常常使用机器寄存器传递实参。⑦返回地址：保存该被调过程返回后的地址。图10.6过程的活动记录返回地址实参控制链存取链机器状态信息局部变量临时工作单元静态链，指向静态直接外层最新活动记录的起始地址，即指向定义本过程的直接外层过程（或主程序）运行时最新活动记录的基地址。动态链，指向调用该过程前正在运行过程的数据段基地址。武汉理工大学计算机科学系林泓10.2.1简单的栈式分配的实现程序结构特点:过程定义不嵌套，过程可递归调用，含可变数组；例：main全局变量的说明procR……endR;procQ……endQ;主程序执行语句endmain武汉理工大学计算机科学系林泓TOP临时工作单元局部简单变量局部数组的内情向量保存运行过程前的状态（返回地址，寄存器值…）实参（形式单元）和参数个数SP存取链（静态链）控制链（动态链，老SP）图10.3过程的活动记录指向调用该过程的那个过程的最新活动记录的起始地址用以存取非局部变量，这些变量存放于其他过程的活动记录中。MainQRTOPR的活动记录SP主程序全局数据区Q的活动记录MainQQQ的活动记录主程序全局数据区Q的活动记录图10.4栈式存储分配静态链，指向静态直接外层最新活动记录的起始地址，即指向定义本过程的直接外层过程（或主程序）运行时最新活动记录的基地址。动态链，指向调用该过程前正在运行过程的数据段基地址。武汉理工大学计算机科学系林泓TOPR的数组区SPR的活动记录Q的活动记录主程序全局数据区图10.6分配了数组区之后的运行栈TOP临时工作单元局部简单变量局部数组的内情向量返回地址实参（形式单元）SP参数个数控制链（老SP）图10.5无嵌套定义的过程活动记录内容武汉理工大学计算机科学系林泓10.2.2嵌套过程语言的栈式实现主要特点：•（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。•（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。武汉理工大学计算机科学系林泓(1)programsort(input,output);//sort的过程头(2)vara:array[0..10]ofinteger;(3)x:integer;(4)procedurereadarray;//sort内嵌套定义的readarray的过程头(5)vari:integer;(6)begin…a…end{readarray};//readarray的过程体(7)procedureexchange(i,j:integer);//sort内嵌套定义的exchange的过程头(8)begin(9)x∶=a[i];a[i]∶=a[j];a[j]∶=x;//exchange的过程体(10)end{exchange};(11)procedurequicksort(m,n:integer);//sort内嵌套定义的quicksort的过程头(12)vark,v:integer;(13)functionpartition(y,z:integer):integer;//quicksort内嵌套定义的partition的函数头(14)vari.j:integer;(15)begin…a…//partition的函数体(16)…v…(17)…exchange(i,j);…(18)end{partition};(19)begin…end{quicksort};//quicksort的过程体(20)begin…end{sort}.//sort的例程体图10.11具有嵌套过程的PASCAL程序武汉理工大学