8-第八章_存储空间组织-1-2节

1、CH8 运行时存储空间组织运行时存储空间组织编译程序总框编译程序总框 符符 号号 表表词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器代码优化代码优化出出 错错 处处 理理源程序源程序目标程序目标程序单词符号集单词符号集语法单位集语法单位集中间代码程序中间代码程序中间代码程序中间代码程序 目标代码生成目标代码生成 存储空间组织存储空间组织存储空间分配策略存储空间分配策略 1).1).静态分配静态分配 存储分配由编译程序在编译时进行；存储分配由编译程序在编译时进行； 2).2).动态分配动态分配 在编译时生成相应在编译时生成相应( (申请空间申请空间) )的目标的目标 程序，在目标程

2、序运行时，执行该代码，程序，在目标程序运行时，执行该代码， 进行存储分配。进行存储分配。 （有：栈式存储分配，堆式存储分配）（有：栈式存储分配，堆式存储分配）影响存储分配策略的源语言主要特征影响存储分配策略的源语言主要特征 1). 过程能否递归调用；过程能否递归调用；Program PP(input,output); var k: integer; Function F(n:integer):integer; begin if n=0 then F:=1 else F:=n*F(n-1); end; begin K:=F(10); end.执行顺序：执行顺序： P PPFPF1 1FF2 2

3、每一次调用每一次调用F F，需要一套数据区需要一套数据区影响存储分配策略的源语言主要特征影响存储分配策略的源语言主要特征 2).是否有可变数组（可变数组的大小创建时决定）；是否有可变数组（可变数组的大小创建时决定）；Pascal: Pascal: thepointthepoint : array of integer; : array of integer; setlength(thepoint,5); setlength(thepoint,5); 在在C99C99，实现了，实现了变长数组：变长数组：用用( (整型整型) )变量或表达式声明变量或表达式声明的数组。（在的数组。（在C90C90和

4、和C+C+，方括号内必须是常数值）。，方括号内必须是常数值）。例：例：intint f (void) ; f (void) ; intint main(voidmain(void) ) intint size = 4; size = 4; intint asizeasize; / ok in only C99; / ok in only C99 intint bsizebsize* *size; / ok in only C99size; / ok in only C99 intint c f() ; / ok in only C99 c f() ; / ok in only C99影响存储分

5、配策略的源语言主要特征影响存储分配策略的源语言主要特征 3). 过程能否访问非局部且非全局的变量过程能否访问非局部且非全局的变量 如：如：Pascal语言的过程嵌套声明语言的过程嵌套声明, ,内层可以访问内层可以访问 外层定义的名字外层定义的名字Program B1(input,output); const a=10; var b,c: integer; procedure B2(x:real); var f,g:real; procedure B3(y:real); const b=5; var j:real; begin j:=f * B3(a)+b; end; B3 begin ; be

6、gin ; end; B2 begin ; end; B1,主程序主程序其中其中： j,bj,b B3 B3 f B2f B2 a B1 a B1影响存储分配策略的源语言主要特征影响存储分配策略的源语言主要特征4). 是否有分程序结构（分程序中可以有是否有分程序结构（分程序中可以有变量声明变量声明）#include int test=5; void fun1( );void main( ) int test=10; fun1( ); printf(“2-%dn”,test); int test=15; printf(“3-%dn”,test); void fun1( ) printf(“1-%

7、dn”,test); 全局名：全局名：5main定义的定义的局部名：局部名：10分程序分程序定义的定义的局部名：局部名：15影响存储分配策略的源语言主要特征影响存储分配策略的源语言主要特征5). 名字的作用域名字的作用域 如，如， C语言的语言的staticstatic，externextern。动态局部变量（离开函数，值就消失）动态局部变量（离开函数，值就消失）静态局部变量（离开函数，值仍保留）静态局部变量（离开函数，值仍保留） 静态全局变量（只限本文件引用）静态全局变量（只限本文件引用）全局变量全局变量 （允许其它文件引用）（允许其它文件引用） 影响存储分配策略的源语言主要特征影响存储分配

8、策略的源语言主要特征6). 过程调用时如何传递参数；过程调用时如何传递参数； 如：传值，传地址，得结果，传名等。如：传值，传地址，得结果，传名等。7). 哪些实体可以作为参数和返回值；哪些实体可以作为参数和返回值； 如：简单变量，结构变量，标号，过程等，如：简单变量，结构变量，标号，过程等， 是否可以做为参数被传递和做为结果被返回？是否可以做为参数被传递和做为结果被返回？7). 是否允许动态的为对象分配存储空间；是否允许动态的为对象分配存储空间； 如：如：C C：mallocmalloc、calloccalloc； pascalpascal：NewNew、GetMemGetMem 8).8).

9、存储空间是否必须显式地释放存储空间是否必须显式地释放 如：如：C C：free free pascalpascal： DisposeDispose、FreeMemFreeMem8.1 目标程序运行时的活动目标程序运行时的活动8.1.1 过程的活动过程的活动1). 1). 过程的活动过程的活动: : 该过程的一次执行该过程的一次执行( (调用调用) )。2). 2). 过程活动的生存期过程活动的生存期: : 从执行过程从执行过程 P P 的过程体的第一步操作到最后的过程体的第一步操作到最后 一步操作之间的操作序列；包括执行一步操作之间的操作序列；包括执行P P时调用时调用 其他过程其他过程 (

10、(如如Q) Q) 花费的时间。花费的时间。3). 3). 过程递归：过程递归： 若过程尚未退出当前活动，又开始其新的活动。若过程尚未退出当前活动，又开始其新的活动。 过程递归可以是间接达到的。如：过程递归可以是间接达到的。如：PQRPPQRPprogram main (input，output)； var A，B ： integer； procedure Q(X: X: integer); begin end; procedureP(X,Y,Z:X,Y,Z:integer); begin Y:=Y+1 Y:=Y+1；Z:=Z+XZ:=Z+X； if Z0 then Q(Z)if Z0 then

11、 Q(Z) else P(X,Y,Z); else P(X,Y,Z); end; begin A:=2; B:=3; A:=2; B:=3; P(A+B,A,A); P(A+B,A,A); writeln(A=，A） end. 过过程程定定义义过程调用过程调用1).1).过程的活动过程的活动2).2).过程活动过程活动 的生存期的生存期3).3).过程递归过程递归8.1.2 参数传递参数传递 过程过程( (函数函数) )： 结构化程序设计的主要手段；结构化程序设计的主要手段； 节省程序代码和扩充语言能力的主要途径；节省程序代码和扩充语言能力的主要途径；只要有过程定义，就可以在别的程序单位调用它

12、。只要有过程定义，就可以在别的程序单位调用它。调用者调用者( (程序单位程序单位) )与被调用者与被调用者( (过程过程) ) 之间的信息之间的信息传递主要通过传递主要通过“全局量全局量”和和“参数参数”来完成。来完成。如果把数据看成内容物的话，那么装载数据的容器如果把数据看成内容物的话，那么装载数据的容器就是变元。就是变元。主程序主程序/ /过程过程调用者调用者被调用者被调用者变元变元过程过程变元变元控制控制数据流数据流数据流数据流: : . .从从调用者调用者的变元的变元 = = 被调用过程被调用过程的变元；的变元； . .被调用过程被调用过程对数据进行计算处理；对数据进行计算处理； .

13、.过程结束返回时，把数据结果过程结束返回时，把数据结果 = 调用者调用者的变元；的变元；在完成对过程中代码段的调用执行的同时，在完成对过程中代码段的调用执行的同时，也完成了与过程的数据交换也完成了与过程的数据交换信息传递中，涉及到两类参数信息传递中，涉及到两类参数: : 属于属于被调用过程被调用过程： 用于表示相应数据在过程执行当中的含义用于表示相应数据在过程执行当中的含义 形式参数（形参，或哑元）形式参数（形参，或哑元）program main（input,output）；）； var A，B ： integer； procedure P(X X, ,Y Y, ,Z Z: : integer

14、); begin Y:=Y+1 Y:=Y+1； Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P( P(A+BA+B, ,A A, ,A A); ); writeln(A=，A） end. 形式参数形式参数信息传递中，涉及到两类参数信息传递中，涉及到两类参数: : 属于属于调用者调用者： 用于装载调用者对被调过程的输入用于装载调用者对被调过程的输入/ /输出数据；输出数据； 实在参数实在参数 （实参（实参 ）program main（input,output）；）； var A，B ： integer； procedure P(X X, ,Y

15、 Y, ,Z Z: : integer); begin Y:=Y+1 Y:=Y+1； Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P( P(A+BA+B, ,A A, ,A A); ); writeln(A=，A） end. 实在参数实在参数形参与实参之间按照从左到右的顺序一一对应。形参与实参之间按照从左到右的顺序一一对应。即：处于两个列表的相同位置的变元，意味着它们即：处于两个列表的相同位置的变元，意味着它们 是相互关联的。是相互关联的。 形形- -实对应的主要方式：传值，传地址，得结果，传名实对应的主要方式：传值，传地址，得结果，传名p

16、rogram main（input,output）；）； var A，B ： integer； procedure P(X X, ,Y Y, ,Z Z: : integer); begin Y:=Y+1 Y:=Y+1； Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P( P(A+BA+B, ,A A, ,A A); ); writeln(A=，A） end. 实在参数实在参数形式参数形式参数传值调用（传值调用（Call by value）调用者计算出实在参数的值，并将其传送给过程的调用者计算出实在参数的值，并将其传送给过程的形式参数。形式参数

17、。 调用者计算实参的值，放在过程可以取到的地方；调用者计算实参的值，放在过程可以取到的地方； 过程取出实参的值，放在过程内对应的形式单元中过程取出实参的值，放在过程内对应的形式单元中 ( (过程的活动记录中开辟的存储空间过程的活动记录中开辟的存储空间) )； 过程执行时，像局部名一样使用这些形式单元。过程执行时，像局部名一样使用这些形式单元。C参数为普通变量参数为普通变量void sub (void sub (intint x,intx,int y) y)pascal值参值参procedure procedure P(x,y:integerP(x,y:integer) )program mai

18、n(input，output); var A，B ： integer； procedure P(X,Y,Z:X,Y,Z:integer); begin Y:=Y+1 Y:=Y+1；Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P(A+B,A,A); P(A+B,A,A); writeln(A=，A） end. 主程序主程序子程序子程序T5X 5 A2Y2 3B3Z2 7此种参数传递方法，此种参数传递方法，过程内对参数的变动过程内对参数的变动不会影响到不会影响到“调用者调用者”输出结果：输出结果：A=2传地址传地址 (引用调用引用调用) ( C

19、all-by-address ) 调用者把一个指向实参的存储地址的指针，传递给调用者把一个指向实参的存储地址的指针，传递给过程的形参。过程的形参。 实参是名字：传递其地址；实参是名字：传递其地址； 实参是表达式：计算表达式值且存放在某一实参是表达式：计算表达式值且存放在某一 存储单元，将该存储单元地址传递过去。存储单元，将该存储单元地址传递过去。 过程中对形参的引用和赋值，都变成对传递过程中对形参的引用和赋值，都变成对传递 来的指针的间接引用访问。来的指针的间接引用访问。C C参数为指针变量参数为指针变量 void void sub(intsub(int * *sum)sum)数组作为参数数组

20、作为参数void void Func(intFunc(int arr5) arr5)pascalpascal变参变参procedure procedure P(VarP(Var x,y:integerx,y:integer) ) program main(input，output); var A，B ： integer； procedure P(X,Y,Z:X,Y,Z:integer); begin Y:=Y+1 Y:=Y+1；Z:=Z+XZ:=Z+X； end; begin A:=2; B:=3; A:=2; B:=3; P(A+B,A,A); P(A+B,A,A); writeln(A=，

21、A） end. 主程序主程序T 5A 2 3 8B 3子程序子程序XTTYAAZAA输出结果：输出结果：A=8C C语言参数例语言参数例# include # include void sub (void sub (intint x,intx,int y,inty,int * *sum)sum) * *sum=sum=x+yx+y;main ( )main ( ) intint x=9,y=10,s=1; x=9,y=10,s=1; sub(x,y,&ssub(x,y,&s);); printf(%dprintf(%d n,sn,s);); 答案答案: 19: 19其中：其中：

22、x,yx,y 传值传值 sum sum 传地址传地址其中：其中：x x 传值传值 y y 传地址传地址#include #include intint x,y,zx,y,z; ; void void p(intp(int * *x,intx,int y) y) + +* *x; y- -; z=x; y- -; z=* *x+yx+y; ; printf(%d,%d,%dnprintf(%d,%d,%dn,* *x,y,zx,y,z); ); void main() void main() x=2; y=3; z=4; x=2; y=3; z=4; p(&x,yp(&x,y);

23、); printf(%d,%d,%dn,x,y,zprintf(%d,%d,%dn,x,y,z);); p(&y,xp(&y,x);); printf(%d,%d,%dn,x,y,zprintf(%d,%d,%dn,x,y,z);); 3, 2, 53, 2, 53, 3, 53, 3, 54, 2, 64, 2, 63, 4, 63, 4, 6得结果得结果 ( Call by result ) 或或 复制恢复复制恢复 ( Copy-Restore ) 被调用过程为每个形参设置两个形式单元；被调用过程为每个形参设置两个形式单元； 分别存地址、值。分别存地址、值。 调用者把实在参

24、数的调用者把实在参数的地址和值地址和值同时传递到被调用同时传递到被调用 过程中；过程中； 被调用过程直接使用被调用过程直接使用实参的值实参的值； 过程过程返回时，把形参的现行值复制到相应的实在返回时，把形参的现行值复制到相应的实在 参数的地址中参数的地址中, ,将计算结果返回给调用者。将计算结果返回给调用者。（ AdaAda，pascalpascal ) )program main(input，output); var A，B ： integer； procedure P(X,Y,Z:X,Y,Z:integer); begin Y:=Y+1 Y:=Y+1；Z:=Z+XZ:=Z+X； end;

25、begin A:=2; B:=3; A:=2; B:=3; P(A+B,A,A); P(A+B,A,A); writeln(A=，A） end. 主程序主程序T 5A 2 3 7B 3子程序子程序XTT5 5YAA2 2 3 3ZAA2 2 7 7或或: 主程序主程序T 5A 2 7 3B 3结果：结果：A=7 (左左右右) 或：或：A=3 (右右左左)传名调用传名调用 或：换名调用或：换名调用 ( Call-by-Name ) 调用者调用者将实在参数的名字传给将实在参数的名字传给被调用被调用过程中过程中 相应的形式参数；相应的形式参数； 被调用被调用过程的过程体中，所有的形式参数都过程的过程

26、体中，所有的形式参数都 用相应实在参数的名字进行替换；用相应实在参数的名字进行替换；ALGOL ALGOL 使用的一种参数传递方式使用的一种参数传递方式program main(input,output); var A，B ： integer； procedure P(X,Y,Z:integer); begin Y:=Y+1；Z:=Z+X； end; begin A:=2; B:=3; P(A+B,A,A); writeln(A=，A） end. program main(input,output); var A，B ： integer； procedure P(X,Y,Z:integer);

27、 begin A:=A+1；A:=A+(A+B)； end; begin A:=2; B:=3; P(A+B,A,A); writeln(A=，A） end. 主程序主程序TAB52 3 93输出结果：输出结果：A=98.2 8.2 运行时存储器的划分运行时存储器的划分8.2.1 8.2.1 运行时存储器的划分运行时存储器的划分一个目标程序运行所需的存储空间包括一个目标程序运行所需的存储空间包括: : 存放目标代码的空间存放目标代码的空间 存放数据项目的空间存放数据项目的空间 存放程序运行的控制或连接数据所需单元存放程序运行的控制或连接数据所需单元 ( (控制栈控制栈) )一个程序在运行时刻的

28、内存划分一个程序在运行时刻的内存划分:代码代码(Code)静态数据静态数据(Static Data)栈栈(Stack) 堆堆(Heap) 绝大多数高级语言，执行时不绝大多数高级语言，执行时不能改变代码，所以在编译时，能改变代码，所以在编译时，所有代码所有代码( (包括每个过程的入包括每个过程的入口点口点) )地址都是可计算的。地址都是可计算的。过程过程1 1的代码的代码过程过程2 2的代码的代码. . . .过程过程n n的代码的代码过程过程1 1入口入口过程过程2 2入口入口过程过程n n入口入口代代码码区区内容内容代码区代码区大小大小静态确定静态确定位置位置静态确定静态确定静态数据：静态数

29、据：编译时就可以确定存储位置的数据。编译时就可以确定存储位置的数据。如：如：* *) FORTRAN77 ) FORTRAN77 ：所有的数据；：所有的数据； * *) Pascal ) Pascal ： 全局变量；全局变量； * *) C ) C ： 外部变量，静态变量外部变量，静态变量；对常量，常数：对常量，常数： 编译时已知其内容，且编译时已知其内容，且值不变。通常由编译程值不变。通常由编译程序直接插入到代码中，序直接插入到代码中，不分配数据空间。不分配数据空间。内容内容 数据段数据段 静态数据区静态数据区大小大小静态确定静态确定位置位置静态确定静态确定目标代码目标代码静态数据静态数据栈

30、栈堆堆栈区：栈区：用于用于符合符合后进先出使用风格的数据；后进先出使用风格的数据； * *) ) 过程运行的控制及连接数据；过程运行的控制及连接数据； * *) ) 过程的局部变量、形式参数等；过程的局部变量、形式参数等；目标代码目标代码静态数据静态数据栈栈堆堆堆区：堆区：用于用于不符合不符合后进先出使用风格的数据；后进先出使用风格的数据； * *) ) 动态申请地址空间的变量。动态申请地址空间的变量。 其中：其中：“栈区栈区”和和“堆区堆区”的大小是随着程序的运的大小是随着程序的运行而行而 改变的，因此两者采用对开式使用。改变的，因此两者采用对开式使用。8.2.2 8.2.2 活动记录活动记录过程在一次活动过程在一次活动( (执行执行) )中所需要的信息，存放在一片中所需要的信息，存放在一片连续的存储区中，称为一个活动记录。过程调用产生连续的存储区中，称为一个活动记录。过程调用产生新的活动记录。新的活动记录。活动记录中至少应该存放两类信息：活动记录中至少应该存放两类信息： 1. 1. 控制信息：控制信息： * *）控制活动的正确调用与返回；）控制活动的正确调用与返回；( (如：返回地址如：返回地址) ) * *）控制活动记录的正确切换；）控制活动记录的正确切换；( (如：动态链如：动态链) ) 2. 2