《第10章目标程序运行时的组织》由会员分享，可在线阅读，更多相关《第10章目标程序运行时的组织（50页珍藏版）》请在金锄头文库上搜索。
1、第第10章章 目标程序运行时的组织目标程序运行时的组织概概 述述为了使目标程序能够运行，编译程序要从操作系统中得为了使目标程序能够运行，编译程序要从操作系统中得到一块存储区，以使目标程序能够在其上运行。到一块存储区，以使目标程序能够在其上运行。该存储区需容纳该存储区需容纳 ： （1 1）生成的目标代码生成的目标代码（2 2）目标代码运行时的数据空间）目标代码运行时的数据空间数据空间应包括：数据空间应包括：(1)(1)用户定义的各种类型的数据对象所需的存储空间用户定义的各种类型的数据对象所需的存储空间(2)(2)保留中间结果和传递参数的临时工作单元保留中间结果和传递参数的临时工作单元(3)(3)
2、调用过程时所需的连接单元调用过程时所需的连接单元(4)(4)组织输入组织输入/ /输出所需的缓冲区输出所需的缓冲区目标代码所占用空间的大小在编译时能确定。目标代码所占用空间的大小在编译时能确定。有些数据对象所占用的空间也能在编译时确定。有些数据对象所占用的空间也能在编译时确定。而有些数据对象具有可变体积和待分配性质，无法在编译而有些数据对象具有可变体积和待分配性质，无法在编译时确定存储空间的位置。时确定存储空间的位置。因此运行时的存储区常常划分成：目标区、静态数据区、因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区栈区和堆区目标程序运行时存储区的典型划分目标程序运行时存储区的典型划
3、分codestatic datastack heap代码代码( (code)code)区用以存区用以存放目标代码，这是固放目标代码，这是固定长度的，即编译时定长度的，即编译时能确定的；静态数据能确定的；静态数据区区( (static data)static data)用以用以存放编译时能确定所存放编译时能确定所占用空间的数据；栈占用空间的数据；栈区和堆区区和堆区( (stack and stack and heap)heap)用于可变数据以用于可变数据以及管理过程活动的控及管理过程活动的控制信息。制信息。所谓数据空间的分配，本质上看，是将程所谓数据空间的分配，本质上看，是将程序中的每个名字与一
4、个存储位置关联起来，序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。该存储位置用以容纳名字的值。 关联（关联（Binding）将源程序的文本将源程序的文本 程序运行动作的实现程序运行动作的实现 即源程序文本要做哪些功能，目标程序要实现它即源程序文本要做哪些功能，目标程序要实现它的功能。的功能。 源文件中的名字源文件中的名字N 运行时的存储运行时的存储S S (N (N到到S S的映射的映射) )10.1 10.1 数据空间的三种不同使用方法和管理方法数据空间的三种不同使用方法和管理方法 数据空间的三种不同使用方法和管理方法数据空间的三种不同使用方法和管理方法: : 静态存储分
5、配静态存储分配、栈式动态存储分配栈式动态存储分配和和堆式动态存储分配。堆式动态存储分配。 1 1、 静态存储分配静态存储分配这种存储分配非常简单，如果在编译时能确定目这种存储分配非常简单，如果在编译时能确定目标程序运行中所需的全部数据空间的大小，称这种分标程序运行中所需的全部数据空间的大小，称这种分配策略为静态存储分配。配策略为静态存储分配。像像FORTRANFORTRAN这样的语言，其程序是段结构的，即由主程序这样的语言，其程序是段结构的，即由主程序段和若干子程序段组成。段和若干子程序段组成。各程序段中定义的名字一般是彼此独立的，也即各段的各程序段中定义的名字一般是彼此独立的，也即各段的数据
6、对象名的作用域在各段中，数据对象名的作用域在各段中，同一个名字在不同的程同一个名字在不同的程序段表示不同的存储单元，不会在不同段间互相引用、序段表示不同的存储单元，不会在不同段间互相引用、赋值。赋值。另外它的每个数据名所需的存储空间大小都是常量另外它的每个数据名所需的存储空间大小都是常量（即（即不许含可变体积的数据，如可变数组）不许含可变体积的数据，如可变数组），且所有数据名，且所有数据名的性质是完全确定的。的性质是完全确定的。这样，整个程序所需数据空间的总量在编译时完全确定，这样，整个程序所需数据空间的总量在编译时完全确定，换句话说，一旦存储空间的某个位置分配给了某个数据换句话说，一旦存储空
7、间的某个位置分配给了某个数据名（关联起来）之后，在目标程序的整个运行过程中，名（关联起来）之后，在目标程序的整个运行过程中，此位置（地址）就属于该数据名了。此位置（地址）就属于该数据名了。 2 2 动态存储分配动态存储分配如果一个程序设计语言允许递归过程、可变数组或允如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储许用户自由申请和释放空间，那么，就需要采用动态存储管理管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数据空间的大小需待程序运行时的存储空间，它所需要的
8、数据空间的大小需待程序运行时动态地确定动态地确定。若一个数组所需的存储空间的大小在编译时就已知道，则若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变数组。称它为确定数组，否则称为可变数组。例 : procedure A(m,n:integer);begin real z;array Bm:n;begin end;end;Bm:n 为可变数组，为可变数组，B的上下界是过程的上下界是过程A的实参，的实参，A被被调用时才能确定。调用时才能确定。动态存储管理技术有两种方式：栈式（动态存储管理技术有两种方式：栈式（stack）和堆式和堆式（heap）。）。下面简述这两种方式
9、的原则。下面简述这两种方式的原则。1 1、栈式动态存储分配、栈式动态存储分配这种分配策略是将整个程序的数据空间设计为一个栈。这种分配策略是将整个程序的数据空间设计为一个栈。例：在具有递归结构的语言程序中，每当调用一个过程时，例：在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。放这部分空间。过程所需的数据空间包括两部分：过程所需的数据空间包括两部分：一部分是生存期在本过程这次活动中的数据对象，如局部变一部分是生存期在本过程这次活动中的数据对象，如局部变量、参数单元、临时变量等等；
10、量、参数单元、临时变量等等；另一部分则是用以管理过程活动的记录信息另一部分则是用以管理过程活动的记录信息( (连接数据连接数据) )。即即当一次过程调用出现时，调用该过程的那个过程的活动即被当一次过程调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如返回地址、寄存器的值等中断，当前机器的状态信息，诸如返回地址、寄存器的值等等，也都必须保留在栈中。当控制从调用返回时，便根据栈等，也都必须保留在栈中。当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动继续进行。中记录的信息恢复机器状态，使该过程的活动继续进行。2 2、堆式动态存储分配、堆式动态存储分配如果一个
11、程序语言提供用户自由地申请数据空间和如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制，通常使用一种称为堆式的动态存退还数据空间的机制，通常使用一种称为堆式的动态存储分配方案。储分配方案。过程活动记录过程活动记录: :AR为说明方便，假定程序是由过程组成，过程运行时称作过为说明方便，假定程序是由过程组成，过程运行时称作过程的激活。程的激活。 一个过程的一次执行所需要的信息使用一个连续的存储区来一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区管理，这个区（块）叫做一个活动记录（块）叫做一个活动记录 lllllll一般这个段要记录：一般这个段要记录：临时值，如计算表达式
12、时的中间工作单元。临时值，如计算表达式时的中间工作单元。局部变量局部变量（数据）（数据）保存运行过程前的状态保存运行过程前的状态（寄存器值（寄存器值）存取链存取链（可选）（可选） 对于非局部量的引用。对于非局部量的引用。控制链控制链（可选）（可选） 指向调用者的活动记录。指向调用者的活动记录。实参实参（形式单元）（形式单元）返回地址返回地址术语：术语：每个过程的每个过程的ARAR有有3 3个联系单元：个联系单元：SLSL： 静态链静态链，指向，指向定义定义该过程的该过程的直接外过程直接外过程 （或主程序）运行时（或主程序）运行时最新最新数据段的基地址数据段的基地址。DLDL： 动态链动态链，指
13、向，指向调用调用该过程前正在运行过该过程前正在运行过 程的数据段基地址。即指向调用本过程的那程的数据段基地址。即指向调用本过程的那个过程的活动记录的地址（老个过程的活动记录的地址（老SPSP）RARA： 返回地址返回地址，记录调用该过程时，记录调用该过程时目标程序目标程序的的断点断点，保存该过程返回后的地址。，保存该过程返回后的地址。这种情况可以直接采用栈式这种情况可以直接采用栈式存储分配策略。存储分配策略。在运行时，每个过程开始时在运行时，每个过程开始时就把它的活动记录压入栈，就把它的活动记录压入栈，直到该活动结束，它的活动直到该活动结束，它的活动记录弹出栈。记录弹出栈。10.2 简单的栈式
14、存储分配简单的栈式存储分配程序的特点程序的特点: 过程定义过程定义不嵌套不嵌套,过程过程可递归调用可递归调用,允许有可变数组允许有可变数组. 例如例如:C语言语言 全局数据说明全局数据说明 Main ( ) Main 中的数据说明中的数据说明 Void R( ) R 中的数据说明中的数据说明 Void Q Q中的数据说明中的数据说明 Main Q R 嵌套过程语言的栈式分配方案嵌套过程语言的栈式分配方案n前面我们讲的过程不允许语言嵌套定义，现在前面我们讲的过程不允许语言嵌套定义，现在我们取消这个限制，我们取消这个限制，即允许过程嵌套定义，一即允许过程嵌套定义，一个过程可以引用包围它的任一外层过
15、程所定义个过程可以引用包围它的任一外层过程所定义的标识（如变量，数组或过程等）的标识（如变量，数组或过程等）。如：我们如：我们所熟悉的所熟悉的PASCALPASCAL语言程序结构就是这样一种语语言程序结构就是这样一种语言。言。n由于过程定义是嵌套的，一个过程可以引用包围它的任一外层过程所定义的标识（如变量，数组或过程等）。也就是说，运行时，一个过也就是说，运行时，一个过程程Q Q可以引用它的的任意外层的最新活动记录的可以引用它的的任意外层的最新活动记录的名字所对应的存储空间，名字所对应的存储空间，过程过程Q Q运行时，必须知运行时，必须知道它的所有外层的最新活动记录的地址。道它的所有外层的最新
16、活动记录的地址。 办法：办法： 1. 1. 用静态链（如用静态链（如PL/0PL/0的的SLSL）。）。 引入一个称为静态链的指针，该指针引入一个称为静态链的指针，该指针 为活动为活动 记录的一个域，指向直接外层记录的一个域，指向直接外层 的最新活动记录的地址。的最新活动记录的地址。 2. 2. 用用DISPLAYDISPLAY表。表。例：(1) program sort(input, output); (2)var a: array 0.10 of integer; (3)x: integer; (4)procedure readarray; (5)var i: integer; (6)be
17、ginaendreadarray; /readarray的过程体的过程体 (7)procedure exchange(i,j: integer); (8)begin (9) x =ai; ai =aj; aj =x; /exchange的过程体的过程体 (10) endexchange; (11) procedure quicksort(m,n: integer); (12) var k,v: integer; (13) function partition(y,z:integer):integer; (14)var i.j:integer; (15)begin a /partition的函数
18、体的函数体 (16)v (17) exchange(i,j); (18) endpartition; (19) beginendquicksort; /quicksort的过程体的过程体 (20) beginendsort. 它的嵌套情况如下：sortreadarrayexchangequicksort partition如果该程序的某次执行顺序为：sortquicksortquicksortpartitionexchange即主程序即主程序( (最外层过程最外层过程) )sortsort开始执行开始执行, ,继而进入过程继而进入过程quicksortquicksort，而又一次进入过程而又一
19、次进入过程quicksortquicksort，接着进入过程接着进入过程partitionpartition，进入过程进入过程exchangeexchange。 sortquicksortquicksortpartitionexchange解决对非局部量的引用（存取）解决对非局部量的引用（存取）用用DisplayDisplay表表另外一种存取非局部变量的办法，也是常用的有效另外一种存取非局部变量的办法，也是常用的有效办法。即每进入一个过程后，在建立它的活动记办法。即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表录的同时建立一张嵌套层次显示表displaydisplay。Dis
20、playDisplay表表-嵌套层次显示表嵌套层次显示表当前激活过程的层次为当前激活过程的层次为K K，它的它的DisplayDisplay表含有表含有K+1K+1个单元，依次存放着现行层，直接外层个单元，依次存放着现行层，直接外层直至最直至最外层的每一过程的最新活动记录的基地址外层的每一过程的最新活动记录的基地址例如：上例的程序，假定有如下四种调用情况：例如：上例的程序，假定有如下四种调用情况：(a)sortquicksort;(b)sortquicksortquicksort;(c)sortquicksortquicksortpartition;(d)sortquicksortquicks
21、ortpartitionexchange。则则P225 图图10.16的（的（a），（），（b），（），（c），（），（d）分别说明分别说明了上述四种情形的运行栈和了上述四种情形的运行栈和display。确实看出，确实看出，display显显示了存取链的信息。示了存取链的信息。用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R P 的的活动记录活动记录主程序的主程序的活动记录活动记录 d1d0displaysptop主程序的主程序的活动记录活动记录 d0spdisplaytop（1）（2）用用Display表的方案表的方案n主程序主程序-P-Q-RR 的的活动记
22、录活动记录 Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录 displayd2d1d0 d1d0 displaysptoptopsp（3）（4）displaydisplay本身的体积在编译时可确定。至于本身的体积在编译时可确定。至于displaydisplay本身本身作为单独的表分配存储，还是作为活动记录的一部分，作为单独的表分配存储，还是作为活动记录的一部分，比如置于实参（形式单元）的上端（如图所示），则取比如置于实参（形式单元）的上端（如图所示），则取决于编译程序的设计者。
23、决于编译程序的设计者。display作为活动记录的一部分Display表：当过程的层表：当过程的层次为次为n，它的它的 display为为n+1个值。即第个值。即第0层到第层到第n层的层的SP的的值。值。全局全局Display表：直接外表：直接外层的层的Display 地址。地址。连接数据：有连接数据：有3个，个，即老即老SP，返回地址，返回地址，全局全局Display。例：例：P227 图图10.19的程序中，分程序有的程序中，分程序有B0,B1,B2,B3。 分程序的作用域遵循的是最近嵌套原则分程序的作用域遵循的是最近嵌套原则: P226过程的过程的TOPTOP单元始终是指向活动记录的栈顶
24、。单元始终是指向活动记录的栈顶。而过程运行中的任何时刻的现行分程序的而过程运行中的任何时刻的现行分程序的TOPTOP则存放最新的栈则存放最新的栈顶地址。顶地址。过程体中的并列分程序可享用同一存储空间过程体中的并列分程序可享用同一存储空间, ,因为它们不会同因为它们不会同时执行。时执行。分程序除数组外的所有数据的地址在编译时可以静态地确定。分程序除数组外的所有数据的地址在编译时可以静态地确定。 参数传递参数传递参数参数 传递的三种途径：传递的三种途径：传地址、传值、传名传地址、传值、传名传地址传地址：把实参的地址传递给形参。即调用过程把把实参的地址传递给形参。即调用过程把一个指向实参的存储地址的
25、指针传递给被调用过程一个指向实参的存储地址的指针传递给被调用过程相应的形参。相应的形参。1 1、实在参数是一个变量，则直接传递它的地址。、实在参数是一个变量，则直接传递它的地址。2 2、实在参数是表达式、实在参数是表达式-计算值，放入一存储单计算值，放入一存储单元，传此存储单元地址元，传此存储单元地址3 3、过程对形参的引用或赋值都被处理成对形式单、过程对形参的引用或赋值都被处理成对形式单元的间接访问（指针操作）元的间接访问（指针操作） (1)program reference(input,output);(2)var a,b:integer;(3)procedure swap(var x,y
26、: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.PASCAL程序有关键字程序有关键字var时，时，PASCAL语言的参数传语言的参数传递递使用的方式是传地址；去掉使用的方式是传地址；去掉var，则使用的方式是传值。则使用的方式是传值。传传值：值： 在被调过程的活动记录中开辟形参的存储空间，这些在被调过程的活动记录中开辟形参的
27、存储空间，这些存储位置即是我们所说的形参或形式单元。存储位置即是我们所说的形参或形式单元。 调用过程计算实参的值，并将它们的右值放在为形式调用过程计算实参的值，并将它们的右值放在为形式单元开辟的空间中。单元开辟的空间中。 被调用过程执行时，就像使用局部变量一样使用这被调用过程执行时，就像使用局部变量一样使用这些形式单元。些形式单元。procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 调用swap(a,b) 过程将不会影响a和b的值。 其结果等价于执行下列运算： x :=a； y :=
28、b； temp :=x； x :=y； y :=temp n传地址传地址（变量参数）（变量参数） 例如：过程例如：过程 swap(swap(varvar x,y:integer); x,y:integer); swap(a,b swap(a,b）；（）；（ a,b a,b为为调用时的调用时的实参实参 ） 调用结果调用结果a,ba,b的值被改变。的值被改变。n传值传值（值调用）（值调用）特点是对形式参数的任何运算不影响实参的值。特点是对形式参数的任何运算不影响实参的值。 例如：过程例如：过程 swap(x,y:integer);swap(x,y:integer); swap(a,b swap(a
29、,b）；）；其结果：其结果： a,ba,b调用前的值不改调用前的值不改变。变。 (1)swap(x,y)(2)int *x,*y;(3) int temp;(4) temp=*x; *x=*y; *y=temp;(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) 在一个值调用过程中使用指针的在一个值调用过程中使用指针的C程序程序在在C程序中传地址，用指针实现。程序中传地址，用指针实现。例例:主程序主程序A：2；B:=3;P(A+B, A, A)Print(A);
30、子程序：子程序：P(X, Y ,Z ) Y:=Y+1; Z:=Z+X; 问传地址和传值问传地址和传值Print（A）的的结果是多少？结果是多少？传传地址：地址：T：AB5，X := &T ;Y := &A ;Z := &A ;（即即X 所指的变量为所指的变量为T，Y ,Z所指的所指的变量是变量是A）Y:=Y +1=2+1=3 （即即A的值变为的值变为3）Z :=Z +X =AT358主程序主程序A：2；B:=3;P(A+B, A, A)Print(A);子程序：子程序：P(X, Y ,Z ) Y:=Y+1; Z:=Z+X; 所以：传地址的结果为所以：传地址的结果为 ： 8传值的结果为：传值的结
31、果为：2传传名：名：将被调用的过程体复制到调用处，并将每个将被调用的过程体复制到调用处，并将每个形参形参“文字地文字地”替换成实参。替换成实参。主程序主程序A：2；B:=3;P(A+B, A, A)Print(A);子程序：子程序：P(X, Y ,Z ) Y:=Y+1; Z:=Z+X; 例：传名时传名时Print(A)的结果是多少？的结果是多少？主程序主程序A：2；B:=3;P(A+B, A, A)Print(A);子程序：子程序：P(X, Y ,Z ) Y:=Y+1; Z:=Z+X; 传名： 经过P(A+B, A, A)P(A+B, A, A)函数调用，将实参的名传函数调用，将实参的名传过去
32、，过去，X X就是就是A AB B，Y Y就是就是A A，Z Z也是也是A A Y:=Y+1; Y:=Y+1; 变为：变为： A :=A+1A :=A+13 3Z:=Z+X; Z:=Z+X; 变为：变为： A :=A+AA :=A+AB B3 33 33 39 9所以传名的结果：所以传名的结果：9 9过程调用、过程进入和过程返回过程调用、过程进入和过程返回n经过上述讨论之后，我们归纳一下，对于过程调用的四元式序列：par T1par T2par Tncall P,n在运行时是如何执行的。或者说，对于par和call应产生什么相应的目标代码？对于对于par Tpar Ti i(i=1,2,n)(
33、i=1,2,n)的处理是：的处理是：根据根据par Tpar Ti i(i=1,2,n)(i=1,2,n)中中T Ti i的种别而生成传送指令，的种别而生成传送指令，或将参数的值或将参数的地址传送至新的过程的活动记或将参数的值或将参数的地址传送至新的过程的活动记录的形式单元中。录的形式单元中。对于对于call p,ncall p,n：则应生成传送参数个数则应生成传送参数个数n n的指令；保护现行的指令；保护现行SPSP至新过程至新过程的活动记录（老的活动记录（老SPSP）；）；转子，转向转子，转向P P的第一条指令；定的第一条指令；定义新义新SPSP；保护返回地址；定义新值；填写保护返回地址；
34、定义新值；填写displaydisplay或存或存取链内容等指令。取链内容等指令。例：例：假定在过程假定在过程Q Q调用了过程调用了过程P P，过程过程Q Q执行过程调用语句执行过程调用语句 call p, m call p, m 的基本步骤的基本步骤是：是：每个每个Par Ti 可翻译为：可翻译为：(i+4)Top:=Ti转指令前，建立连接数据：转指令前，建立连接数据：1TOP:= SP; 3TOP:= SP+d;/全局全局display4TOP:= n;实现转指令：实现转指令：JSR P;一旦转子，进入一旦转子，进入P过程，立即执行：过程，立即执行：SP:=TOP+1/建立新的建立新的sp1SP:= 返回地址返回地址TOP:=TOP+L /定义新定义新TOP过程返回时：过程返回时：TOP:=SP-1;/返回地址送返回地址送XSP:=0sp;X:=2TOP; UJ:=0x; 形式单元 参数个数 全局Display返回地址老SP Display表1 SP 234d过过程程P过过程程Q SPTOPTOP
