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

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

概述为了使目标程序能够运行，编译程序要从操作系统中得到一块存储区，以使目标程序能够在其上运行。该存储区需容纳：（1）生成的目标代码（2）目标代码运行时的数据空间

数据空间应包括：用户定义的各种类型的数据对象所需的存储空间保留中间结果和传递参数的临时工作单调用过程时所需的连接单元组织输入/输出所需的缓冲区目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定。而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区运行时存储空间的划分代码空间数据空间目标代码空间静态数据空间栈自由空间

堆代码区用以存放目标代码，这是固定长度的，即编译时能确定的；静态数据区用以存放编译时能确定所占用空间的数据；栈区和堆区用于可变数据以及管理过程活动的控制信息。静态存储分配、栈式动态存储分配和堆式动态存储分配。

静态存储分配

这种存储分配非常简单，如果在编译时能确定目标程序运行中所需的全部数据空间的大小，称这种分配策略为静态存储分配。10.1数据空间的三种不同使用方法和管理方法

动态存储分配

如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时动态地确定。若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变数组。

例:

procedureA(m,n:integer);

beginrealz;

arrayB[m:n];

begin

··

·end;

end;

B[m:n]为可变数组，B的上下界是过程A的实参，A被调用时才能确定。动态存储管理技术有两种方式：栈式（stack）和堆式（heap）。下面主要介绍栈式动态存储分配

这种分配策略是将整个程序的数据空间设计为一个栈。在程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。为了讨论方便，我们引入一个术语：过程的活动记录。栈式动态存储分配过程的活动和活动记录一个过程的活动：该过程的一次执行。即每次执行一个过程体，就产生该过程的一个活动。活动记录：是一段连续的存储区，为了管理过程在一次执行中所需要的信息。源语言不同，实现的方法不同，组成活动记录的域也不同。栈式存储分配策略。在运行时，每个过程开始时就把它的活动记录压入栈，直到该活动结束，它的活动记录弹出栈。局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）形式单元：存放相应的实在参数的地址或值。连接数据返回地址动态链：指向调用该过程前正在运行过程的数据段基地址。即指向调用本过程的那个过程的活动记录的地址（老SP）静态链：指向静态直接外层最新活动记录地址的指针，用来访问非局部数据。sort

readarray

exchange

quicksort

partition

对于PL/0语言，每个过程的AR有3个联系单元：SL：静态链，指向定义该过程的直接外过程

（或主程序）运行时最新数据段的基地址。DL：动态链，指向调用该过程前正在运行过 程的数据段基地址。即指向调用本过程的那个过程的活动记录的地址（老SP）RA：返回地址，记录调用该过程时目标程序的断点，保存该过程返回后的地址。这种情况可以直接采用栈式存储分配策略。在运行时，每个过程开始时就把它的活动记录压入栈，直到该活动结束，它的活动记录弹出栈。10.2简单的栈式存储分配程序的特点:过程定义不嵌套,过程可递归调用,允许有可变数组.例如:C语言

全局数据说明

Main(){Main中的数据说明}VoidR(){R中的数据说明}VoidQ{Q中的数据说明}MainQR

嵌套过程语言的栈式分配方案前面我们讲的过程不允许语言嵌套定义，现在我们取消这个限制，即允许过程嵌套定义，一个过程可以引用包围它的任一外层过程所定义的标识（如变量，数组或过程等）。如：我们所熟悉的PASCAL语言程序结构就是这样一种语言。由于过程定义是嵌套的，一个过程可以引用包围它的任一外层过程所定义的标识（如变量，数组或过程等）。也就是说，运行时，一个过程Q可以引用它的的任意外层的最新活动记录的名字所对应的存储空间，过程Q运行时，必须知道它的所有外层的最新活动记录的地址。

办法：

1.用静态链（如PL/0的SL）。引入一个称为静态链的指针，该指针为活动记录的一个域，指向直接外层的最新活动记录的地址。

2.用DISPLAY表。例：(1)programsort(input,output);

(2)

vara:array[0..10]ofinteger;

(3)

x:integer;

(4)

procedurereadarray;

(5)

vari:integer;

(6)

begin…a…end{readarray};//readarray的过程体

(7)

procedureexchange(i,j:integer);

(8)

begin

(9)

x∶=a[i];a[i]∶=a[j];a[j]∶=x;//exchange的过程体

(10)

end{exchange};

(11)

procedurequicksort(m,n:integer);

(12)

vark,v:integer;

(13)

functionpartition(y,z:integer):integer;

(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}.见P236它的嵌套情况如下：sort

readarray

exchange

quicksort

partition

如果该程序的某次执行顺序为：

sort→quicksort→quicksort→partition→exchange…

即主程序(最外层过程)sort开始执行,继而进入过程quicksort，而又一次进入过程quicksort，接着进入过程partition，进入过程exchange…。

sort→quicksort→quicksort→partition→exchange…sort

readarray

exchange

quicksort

partition

解决对非局部量的引用（存取）

用Display表另外一种存取非局部变量的办法，也是常用的有效办法。即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display。Display表---嵌套层次显示表当前激活过程的层次为K，它的Display表含有K+1个单元，依次存放着现行层，直接外层…直至最外层的每一过程的最新活动记录的基地址令过程R的外层为Q，Q的外层为主程序为P，则过程R运行时的DISPLAY表内容为：问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？P0P1P2P0P2P1P0P1P2问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？P0P1P2

P1的最新活动记录的起始地址P0的最新活动记录的起始地址P1的display表P0的最新活动记录的起始地址

P2的最新活动记录的起始地址…………P2的display表问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？

P1的最新活动记录的起始地址P0的最新活动记录的起始地址P1的display表P0的最新活动记录的起始地址P1的最新活动记录的起始地址…………P2的display表P2的最新活动记录的起始地址P0P2P1问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的display表？P0P1P2P1的最新活动记录的起始地址P0的最新活动记录的起始地址P1的display表P0的最新活动记录的起始地址…………P2的display表P2的最新活动记录的起始地址P2的最新活动记录的起始地址例如：上例的程序，假定有如下四种调用情况：(a)sort→quicksort…;(b)sort→quicksort→quicksort…;(c)sort→quicksort→quicksort→partition…;(d)sort→quicksort→quicksort→partition→exchange…。则P239图10.16的（a），（b），（c），（d）分别说明了上述四种情形的运行栈和display。确实看出，display显示了存取链的信息。

sort

readarray

exchange

quicksort

partition

用Display表的方案(1)主程序--->(2)P--->(3)Q--->(4)R主程序的活动记录

d[0]spdisplaytop（1）

P的活动记录主程序的活动记录

d[1]d[0]displaysptop（2）用Display表的方案主程序--->P--->Q--->Rd[2]d[1]d[0]Q的活动记录

P的活动记录主程序的活动记录

displaysptop（3）topR的活动记录Q的活动记录

P的活动记录主程序的活动记录

d[1]d[0]

displaysp（4）display本身的体积在编译时可确定。至于display本身作为单独的表分配存储，还是作为活动记录的一部分，比如置于实参（形式单元）的上端（如图所示），则取决于编译程序的设计者。display作为活动记录的一部分Display表：当过程的层次为n，它的display为n+1个值。即第0层到第n层的SP的值。连接数据：有3个，即老SP，返回地址，全局Display。全局Display是调用该过程的那个过程的display表的地址。programP;vara,x:integer;procedureQ(b:integer); vari:integer; procedureR(u:integer;varv:integer); varc,d:integer; begin ifu=1thenR(u+1,v) ...... v:=(a+c)*(b-d); ...... end{R}begin ...... R(1,x); ......end{Q}procedureS; varc,i:integer; begin a:=1; Q(c); ...... end{S}begin a:=0; S; ......end.{P}0112PRQS00返回地址10(display)2a3x405返回地址62(全局display)70(形参个数)809510主程序过程

Sc11i12TOPSP动态链displayRQSP00返回地址10(display)2a3x405返回地址62(全局display)70(形参个数)809510主程序P过程

S

过程

Qc11i12动态链513返回地址149(全局display)151(形参个数)16b(形参)170181319i20TOPSPPRQSdisplaydisplay00返回地址10(display)2a3x405返回地址62(全局display)70(形参个数)809510主程序P过程

S

过程

Q

过程

Rc11i12动态链513返回地址149(全局display)151(形参个数)16b(形参)170181319i201321返回地址2218(全局display)232(形参个数)24u(形参)25v(形参)2602713282129c30d31TOPSPPRQS00返回地址10(display)2a3x405返回地址62(全局display)70(形参个数)809510主程序P

过程

S

过程

Q

过程

R

过程

Rc11i12动态链513返回地址149(全局display)151(形参个数)16b(形参)170181319i201321返回地址2218(全局display)232(形参个数)24u(形参)25v(形参)2602713282129c30d31TOPSP2132返回地址3327(全局display)342(形参个数)35u(形参)36v(形参)3703813393240c41d42分程序结构的存储管理例：main(){inta=0;intb=0;{intb=1;{inta=2;

B2Printf(“%d%d\n”,a,b);B0}

B1{intb=3;

B3Printf(“%d%d\n”,a,b);}Printf(“%d%d\n”,a,b);}Printf(“%d%d\n”,a,b);}图中，分程序有B0,B1,B2,B3。分程序的作用域遵循的是最近嵌套原则见P240:

声明

作用域inta=0;B0-B2intb=0;B0-B1intb=1;B1-B3inta=2;B2intb=3;B3分程序结构的特点：分程序内可以定义变量分程序允许嵌套定义变量，内层分程序可以引用包围它的任意一外层分程序定义的标识符分程序在哪里定义就在哪里被调用处理分程序结构存储分配方案的一种简单办法是:把分程序看成“无参过程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。一则：分程序不存在调用问题，在进入一个分程序时，没有必要将连接数据（如动态链，返回地址）和DISPLAY表都放在活动记录中；二则：当从内层分程序向外层转移时，可能同时要结束若干个分程序。1.过程的TOP值，它指向过程活动记录的栈顶位置。2.连接数据，共四项：（1)老SP值；（2)返回地址；

(3)全局DISPAY地址；（4)调用时的栈顶单元地址，老TOP。为了操作方便，对于分程序结构，每个过程的活动记录所含的内容有：3.参数个数和形式单元4.DISPAY表。5.过程所辖的各分程序的局部数据单元。对于每个分程序来说，它们包括：（1)分程序的TOP值。（2)分程序的局部变量，数组内情向量和临时工作单元。过程的TOP单元始终是指向活动记录的栈顶。而过程运行中的任何时刻的现行分程序的TOP则存放最新的栈顶地址。过程体中的并列分程序可享用同一存储空间,因为它们不会同时执行。分程序除数组外的所有数据的地址在编译时可以静态地确定。

参数传递参数传递的三种途径：传地址、传值、传名

(1)programreference(input,output);(2)vara,b:integer;(3)procedureswap({var}x,y:integer);(4)vartemp: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.PASCAL程序有关键字var时，PASCAL语言的参数传递使用的方式是传地址；去掉var，则使用的方式是传值。procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

调用swap(a,b)过程将不会影响a和b的值。其结果等价于执行下列运算：

x:=a；

y:=b；

temp:=x；

x:=y；

y:=temp

传地址（变量参数）例如：过程swap(varx,y:integer);swap(a,b）；（a,b为调用时的实参）调用结果a,b的值被改变。传值（值调用）特点是对形式参数的任何运算不影响实参的值。例如：过程swap(x,y:integer);swap(a,b）；其结果：a,b调用前的值不改变。

(1)swap(x,y)(2)int*x,*y;(3){inttemp;(4)temp=*x;*x=*y;*y=temp;(5)}(6)main()(7){inta=1,b=2;(8)swap(&a,&b);(9)printf(“aisnow%d,bisnow%d\n”,a,b);(10)}

在一个值调用过程中使用指针的C程序，在C程序中传地址，用指针实现。传地址：把实参的地址传递给形参。即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参。1、实在参数是一个变量，则直接传递它的地址。2、实在参数是表达式----计算值，放入一存储单元，传此存储单元地址3、过程对形参的引用或赋值都被处理成对形式单元的间接访问（指针操作）例:主程序A：＝2；B:=3;P(A+B,A,A)Print(A);子程序：P(X,Y,Z){Y:=Y+1;Z:=Z+X;}问传地址和传值Print（A）的结果是多少？传地址：T：＝A＋B＝5，X:=&T;Y:=&A;Z:=&A;（即X所指的变量为T，Y,Z所指的变量是A）Y↑:=Y↑+1=2+1=3（即A的值变为3）Z↑:=Z↑+X↑=A＋T＝3＋5＝8主程序A：＝2；B:=3;P(A+B,A,A)Print(A);子程序：P(X,Y,Z){Y:=Y+1;Z:=Z+X;}所以：传地址的结果为：8传值的结果为：2传名：将被调用的过程体复制到调用处，并将每个形参“文字地”替换成实参。主程序A：＝2；B:=3;P(A+B,A,A)Print(A)