第8章 存储空间的分配

1、第八章第八章 运行时的存储空间组织运行时的存储空间组织8.1 8.1 概述概述8 8.2 .2 静态存储分配静态存储分配8 8.3 .3 动态存储分配动态存储分配2编译程序的最终目的是将源程序翻译成等价的目标程序。因此，除了进行词法、语法、语义分析外，在生成目标代码前，需要把程序静态的正文与程序运行时的活动联系起来，弄清楚在代码运行时刻，程序中的各种变量、常量等是如何存放的，如何去访问它们。3编译程序必须分配目标程序运行时的存储空间。这些存储空间包括：用户定义的各类变量和常量所需存储单元；作为保留中间结果的参数传递用的临时工作单元；调用过程或函数时需要的形式单元；返回地址以及组织输入/输出所需

2、的缓冲区。4从本质上看，数据对象的空间分配是将程序中的每个对象名字与一个存储位置进行绑定。目标程序运行时的数据空间组织的基本依据是程序设计语言对程序运行中存储空间的使用和管理办法的规定。如：递归调用的过程，在运行时，其同一个局部名字应对应不同的运行空间位置。5过程是否允许递归？当控制从一个过程的活动返回时，对局部如何处理？过程是否允许引用非局部名？过程调用时如何传递参数；过程是否可以作为参数被传递和作为结果被返回？存储空间可否在程序控制下进行动态分配?存储空间是否必须显式地释放？6静态存储分配在编译阶段进行的存储分配。对程序中的简单变量和常量数组，由于它们所需的存储单元数在编译时就可以确定，因

3、此在编译时就可以给它们分配存储单元。动态存储分配在运行阶段才能确定数据的位置及大小的分配方法。7静态数据区由静态存储分配产生的数据区。这种数据区在整个程序运行过程中是固定不变的。动态数据区由动态存储分配产生的数据区。这种数据区不是固定不变的。随着相应程序单位的调用和返回，它也会进入和退出。8静态存储分配对程序设计语言的要求:不允许有递归调用；不允许有嵌套的子程序；不允许有可变数组。FORTRAN语言满足这些要求。9变量地址= 相对地址 + 起始地址返回地址返回地址寄存器保护区寄存器保护区形式单元形式单元简单变量简单变量数组数组临时变量临时变量10很多高级语言都支持嵌套分程序、嵌套或递归过程结构

4、及动态数组，这些需要运行时存储空间管理机制。栈式存储分配方法是适合于这类语言的一种存储管理方法。栈式存储分配方法是把整个程序的存储空间都安排在一个栈内。11进入主程序时，将主程序定义的各类全程量所需存储空间分配于栈顶；每当调用一个子程序（过程/函数）时，就将其所需的存储空间分配于栈的当前栈顶；每当从子程序运行结束时，就从栈中释放其所占空间；整个程序执行完后，释放它所占用的全部空间。12栈式存储分配适合于：层次嵌套结构允许过程递归调用含可变数组的程序设计语言。13数据区内容返回地址返回地址参数个数参数个数形式单元形式单元简单变量简单变量数组数组临时变量临时变量将这样一个数据区称为将这样一个数据区

5、称为一个一个活动记录活动记录。活动记录的大小在编译活动记录的大小在编译时可以静态地确定。时可以静态地确定。14活动数据区的内容与静态存储分配的数据区相同，所不同的是要允许递归，则每调用一次过程都要生成一个数据区，每次操作都是在新的数据区上进行，递归调用多少次就生成多少个数据区由于只有在运行时才知道调用多少次，因此只能在运行时确定分配多少空间。1516Program main; 全局变量 procedure R; end;(R) procedure Q; call R; end;(Q) 主程序; call Q; end.(main)设在主程序中调用设在主程序中调用Q Q，Q Q又调用了又调用了R

6、 R，则栈式，则栈式分配为：分配为：主程序的数据区主程序的数据区Q Q的数据区的数据区R R的数据区的数据区每调用一个过程就开辟一每调用一个过程就开辟一个数据区。当某个过程执个数据区。当某个过程执行完后，退出此过程的数行完后，退出此过程的数据区，进入下一个过程的据区，进入下一个过程的数据区。数据区。运行时，每当进入一个过程就将此过程的数据区（活动记录）置于栈顶。当过程执行完毕后，该过程所对应的数据区也不复存在，进入到下一个将要执行的过程的数据区中。因此，有必要用两个寄存器来记下数据区的大小。返回地址返回地址参数个数参数个数形式单元形式单元简单变量简单变量数组数组临时变量临时变量老老sp(sp(

7、控制链控制链) )topsp活动记录内容活动记录内容现行过程活动记录起点现行过程活动记录起点17全局变量全局变量Q Q的数据区的数据区R R的数据区的数据区Q Q的数据区的数据区sptoptopsp当当Q Q退出后，退出后，SPSP应指到什应指到什么地方不知道（因为么地方不知道（因为R R的的长度不知），因此在每个长度不知），因此在每个数据区设一老数据区设一老SPSP记下上一记下上一过程的过程的SPSP值。值。18设a为数据区中的相对地址，则asp为相对地址a+sp的地址；简单变量简单变量老老sp(sp(控制链控制链) )sp20则则20sp20sp：将：将2020单元单元的简单变量取出来。的

8、简单变量取出来。19过程调用四元式:(par,_,_,T1)(par,_,_,T2)(par,_,_,T3)(call,_,_,p) /地址调用地址调用 (i+3)top:=add(T (i+3)top:=add(Ti i) ) /值调用值调用 (i+3)top:=T (i+3)top:=Ti i 对应的目标动作：对应的目标动作：进入进入P P前的动作：前的动作： 1top:=sp;1top:=sp;/保存老保存老spsp3top:=3top:=参数个数参数个数 进入进入P P后，首先应定义新的活动记录的后，首先应定义新的活动记录的sp,sp,然后保存返回地址并定义新的然后保存返回地址并定义新

9、的toptop值值 sptop老老spsp参数个数参数个数:3:3Add(TAdd(T1 1) )Add(TAdd(T2 2) )Add(TAdd(T3 3) )20sp:=top+1; sp:=top+1; /定义新定义新spsp对应的目标动作：进入对应的目标动作：进入P P后的动作：后的动作： 过程过程P P的活动记录长的活动记录长度，在编译时可静度，在编译时可静态计算出来。态计算出来。sptopsptop老老spsp参数个数参数个数:3:3Add(TAdd(T1 1) )Add(TAdd(T2 2) )Add(TAdd(T3 3) )1sp:=1sp:=返回地址返回地址; ;/保存返回地

10、址保存返回地址top:=top:=top+Ltop+L; ; /定义新的定义新的toptop返回地址返回地址21对应的目标动作：从P返回时的动作: top:=sp-1;sptopsptop返回地址返回地址老老spsp参数个数参数个数:3:3Add(TAdd(T1 1) )Add(TAdd(T2 2) )Add(TAdd(T3 3) )sp:=0sp; sp:=0sp; /老老spsp 无条件转无条件转2top 2top /返回地址返回地址22动态存储分配比静态存储分配省空间。因为当某一过程执行完后就可以释放它所占的空间，只有当都不释放空间时才与静态分配所用空间相同。但动态分配省空间所付出的代价

11、是运行时分配，降低了执行效率。23某含递归调用的C语言程序： printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10 +0); /打印余数在主程序中调用：printd(-125)2425进入子过程体前： (1+3)top=Ti=n=-125 1top=sp=k /保留老sp 3top=参数个数=1sptopsptop参数个数参数个数:1:1返回地址返回地址形参形参:n=-125:n=-125简单变量简单变量: :i i=12=12老老spsp：K Kk1转入子过程体转入子过程体

12、 sp=top+1 sp=top+1 1 1spsp=返回地址返回地址 top= top=top+Ltop+L 进入子过程体内进入子过程体内，填简单变量，填简单变量i i 参数参数:n=-1250,:n=-1250,先打印先打印-,n=125-,n=125； i i=125/10=12!=0 : =125/10=12!=0 : printdprintd(12)(12) printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0); 形参形参:n=125:n=12526进入子过程

13、体前： (1+3)top=Ti=n=12 1top=sp=k1 3top=参数个数=1sptop简单变量简单变量: :i i=1=1转入子过程体转入子过程体 sp=top+1 sp=top+1 1 1spsp=返回地址返回地址 top= top=top+Ltop+L 进入子过程体内进入子过程体内, ,填简单变量填简单变量i i i i=12/10=1!=0 : =12/10=1!=0 : printdprintd(1)(1) printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%1

14、0+0); 老老sp:k1sp:k1返回地址返回地址形参形参:n=12:n=12k2参数个数参数个数:1:1k1参数个数参数个数:1:1返回地址返回地址形参形参:n=125:n=125老老sp:Ksp:K简单变量简单变量: :i i=12=12sptop27 进入过程体内：进入过程体内： 参数参数n=1n=1 i i=1/10=0;=1/10=0; putcharputchar打印：打印：1%10+0=1; printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0); spt

15、op简单变量简单变量: :i i=1=1老老sp:k2sp:k2老老sp:k1sp:k1返回地址返回地址形参形参:n=12:n=12k2参数个数参数个数:1:1k1参数个数参数个数:1:1返回地址返回地址形参形参:n=125:n=125老老sp:Ksp:K简单变量简单变量: :i i=12=12返回地址返回地址参数个数参数个数:1:1形参形参:n=1:n=1k3简单变量简单变量: :i i=0=028返回到第返回到第2 2次调用处次调用处( (包括返回数包括返回数据区据区):): n=12, n=12,打印：打印：12%10+0=2 printd(int n) int i; if(n0) pu

16、tchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0); sptop简单变量简单变量: :i i=1=1老老sp:k1sp:k1返回地址返回地址形参形参:n=12:n=12k2参数个数参数个数:1:1k1参数个数参数个数:1:1返回地址返回地址形参形参:n=125:n=125老老sp:ksp:k简单变量简单变量: :i i=12=12老老sp:k2sp:k2返回地址返回地址参数个数参数个数:1:1形参形参:n=1:n=1k3简单变量简单变量: :i i=0=0topsp29返回到第返回到第1 1次调用处次调用处( (包括返回数包括

17、返回数据区据区):): n=125, n=125, 打印：打印：125%10+0=5 总的打印结果为：总的打印结果为：-125-125 printd(int n) int i; if(n0) putchar(-); n=-n; if(i=n/10)!=0) printd(i); L:putchar(n%10+0); 简单变量简单变量: :i i=1=1老老sp:k1sp:k1返回地址返回地址形参形参:n=12:n=12k2参数个数参数个数:1:1k1参数个数参数个数:1:1返回地址返回地址形参形参:n=125:n=125老老sp:ksp:k简单变量简单变量: :i i=12=12topspsp

18、top原来的活动记录简单变量简单变量数组数组临时变量临时变量若数组长度可若数组长度可变，则不能确变，则不能确定活动记录的定活动记录的大小，但要求大小，但要求在编译时一定在编译时一定要能确定活动要能确定活动记录的长度，记录的长度，为此，将活动为此，将活动记录改为：记录改为：简单变量简单变量数组数组临时变量临时变量数组内情向量数组内情向量新的活动记录新的活动记录活活动动记记录录30对数组建立内情向量，记录已知信息。如：数组起始地址数组起始地址a a维数维数n n数组常量数组常量C Cd d1 1d d2 2d dn n数组起始地址数组起始地址a a维数维数n n数组常量数组常量C CL L1 1N

19、 N1 1d d1 1L L2 2N N2 2d d2 2L Ln nN Nn nd dn n这样便于计算数组越界这样便于计算数组越界31Void p() int A1.m; int B1.n; P P的活动记录的活动记录数组数组B B数组数组A Asptop32计算各维的长度（或上、下限）调用数组空间分配子程序，其参数为各维的长度（或上、下限）及内情向量的起始地址。33填写内情向量中的信息 （数组起址:=top+1 )调整top：top:=top+v v为数组体积P P的活动记录的活动记录数组数组topsptop34例： procedure P procedure Q procedure R

20、 end end end这种过程嵌套结构所附这种过程嵌套结构所附带的语义检查：带的语义检查：过程调用的合理性过程调用的合理性变量使用的合法性变量使用的合法性35由于过程定义是嵌套的，任一个过程都可以引用其外层过程中定义的变量。因此，子过程必须要知道其全部外层过程的最新活动记录的地址。由于允许递归调用和包含可变数组，因此过程的活动记录位置往往是变化的，因此应跟踪每个外层过程的最新活动记录的位置。36静态链指向其直接外层过程的最新活动记录的基地址。Display表每当进入一个子过程时，在建立它的活动记录区的同时建立一张嵌套的层次显示表display。37Program P; Var a,x: in

21、teger; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 层次层次0 01 12 21 1变量作用域变量作用域a,xa,xb,ib,iu,vu,vc,dc,dc,ic,i38为了在子过程的活动记

22、录中引用包围它的某一外层过程的数据，在子过程的活动记录中添加静态链，静态链指向其直接外层过程的最新活动记录基地址。返回地址返回地址参数个数参数个数形式单元形式单元静态链静态链内情向量内情向量临时变量临时变量老老spsp简单变量简单变量sptop39Program P; Var a,x: integer; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x);

23、endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1静态链示例静态链示例1 1P P调用调用S S时时返回地址返回地址简单变量简单变量:a:a简单变量简单变量: x: x老老sp:0sp:0静态链静态链:0:0参数个数参数个数:0:0老老sp:0sp:0返回地址返回地址参数个数参数个数:0:0简单变量简单变量: :i i简单变量简单变量:c:c1 13 34 45 57 78 80 06 62 210109 9P的活的活动记录动记录S的活的活动记录动记录SPTOP40

24、Program P; Var a,x: integer; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1静态链示例静态链示例2 2过程过程S S中中调用调用Q Q时时返回地

25、址返回地址简单变量简单变量:a:a简单变量简单变量: x: x老老sp:0sp:0静态链静态链:0:0参数个数参数个数:0:0老老sp:0sp:0返回地址返回地址参数个数参数个数:0:0简单变量简单变量: :i i返回地址返回地址静态链静态链:0:0简单变量简单变量:c:c老老sp:5sp:5参数个数参数个数:1:1形参形参:b:b简单变量简单变量: :i i1 13 34 45 57 78 80 06 62 21010121213139 91111151516161414P的活的活动记录动记录S的活的活动记录动记录Q的活的活动记录动记录SPTOP41Program P; Var a,x: i

26、nteger; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1静态链示例静态链示例3 3过程过程Q Q中中调用调用R R时时PSPTOP返回地址返回地址简单变量简单变量:a

27、:a简单变量简单变量: x: x老老sp:0sp:0静态链静态链:0:0参数个数参数个数:0:0老老sp:0sp:0返回地址返回地址参数个数参数个数:0:0简单变量简单变量: :i i返回地址返回地址静态链静态链:0:0简单变量简单变量:c:c老老sp:5sp:5形参形参:b:b参数个数参数个数:1:1简单变量简单变量: :i i返回地址返回地址静态链静态链:11:11老老sp:11sp:11形参形参:u:u参数个数参数个数:2:2形参形参:v:v简单变量简单变量:c:c简单变量简单变量:d:d1 13 34 45 57 78 80 06 62 21010121213139 911111515

28、1414161618181919171721212020222223232424SQR42在本过程的活动记录中添加display表（栈式）用来存放各外层最新活动记录的基地址。43Program Main; 0 A:integer; procedure R;1 B,C:integer; A:=B+C; end; procedure P;1 procedure Q;2 R; end; Q; end; P;End.topspP PQ QMainMainR RR的的displayQ的的display过程层次过程层次Q Q的活动记录起址的活动记录起址MainMain的活动记录起址的活动记录起址P P的活

29、动记录起址的活动记录起址0 01 12 2R R的活动记录起址的活动记录起址MainMain的活动记录起址的活动记录起址0 01 144由于每个过程的display表的大小可在编译阶段知道，因此为便于组织存储区域和简化处理过程，可把display作为活动记录的一部分放在形式单元的上边。现在的活动记录为：返回地址返回地址参数个数参数个数形式单元形式单元displaydisplay内情向量内情向量临时变量临时变量老老spsp简单变量简单变量45全局display: 调用段display表地址,用来建 立 被 调 用 段 的display表：从调用段P1的display表中自底向上抄录L2个单元(L

30、2为被调用段P2的层数)。返回地址返回地址参数个数参数个数形式单元形式单元新新displaydisplay内情向量内情向量临时变量临时变量老老spsp简单变量简单变量老老displaydisplay地址地址d在编译时可确定在编译时可确定46当P1调用P2,进入P2后,P2如何建立自己的 display表?从P1的display表中自底向上抄录L2个单元(L2为P2的层数),再添加p2自己的sp,就构成p2的 display表。47P1P1的的displaydisplay有有 项项: :P2P2的的displaydisplay表有表有 项项: :P1P1的的displaydisplay有有 项项

31、: :P2P2的的displaydisplay表有表有 项项: : P0 P0 -0 -0层层 P2 P2 -1-1层层 P1 P1 -1-1层层 call P2 call P2 (p0,p1)(p0,p1)2 2(p0,p1,p2)(p0,p1,p2)3 3 P0 P0 -0 -0层层 P1 P1 -1-1层层 P2 P2 -2-2层层 call P2 call P2 2 22 2(p0,p1)(p0,p1)(p0,p2)(p0,p2)48 P0 P0 -0 -0层层 P2 P2 -1-1层层 P3 P3 -1-1层层 P1 P1 -2-2层层 call P2 call P2 P1P1的的d

32、isplaydisplay有有 项项: :P2P2的的displaydisplay表有表有 项项: :3 32 2(p0,p3,p1)(p0,p3,p1)(p0,p2)(p0,p2)49( (par,_,_,Tipar,_,_,Ti) )的目标动作的目标动作: :(i+4)top:=T(i+4)top:=Ti( (Call,_,_PCall,_,_P) )的目标动作的目标动作: :1top:=sp; 1top:=sp; /保存老保存老spsp3top:=3top:=sp+dsp+d; ; /现行现行displaydisplay地址地址4top:=n; 4top:=n; /保存参数个数保存参数个

33、数sptop返回地址返回地址参数个数参数个数形式单元形式单元新新displaydisplay内情向量内情向量临时变量临时变量老老spsp简单变量简单变量老老displaydisplay地址地址50进入过程进入过程P P后的目标动作后的目标动作( (确定新确定新spsp、toptop位置位置) ) sp:=top+1; sp:=top+1; top:= top:=top+Ltop+L; ; /L /L：活动记录长度：活动记录长度 top:= top:=top+Vtop+V; ; /V/V：数组体积：数组体积 建立新的建立新的displaydisplay R:=2sp; R:=2sp; /取出老取

34、出老displaydisplay的地址的地址 dsp:=0R;dsp:=0R; d+1sp:=1R; d+1sp:=1R; (d+i-1)sp:=(i-1)R; (d+i-1)sp:=(i-1)R; ( (d+id+i)sp:=sp; )sp:=sp; /新加入的新加入的displaydisplay项项抄老抄老displaydisplaydsptop返回地址返回地址参数个数参数个数形式单元形式单元新新displaydisplay内情向量内情向量临时变量临时变量老老spsp简单变量简单变量老老displaydisplay地址地址511sp:=1sp:=返回地址返回地址; ;/保存返回地址保存返回

35、地址从过程返回: top:=sp-1; sp:=0sp; /取老sp 无条件转2top返回地址返回地址参数个数参数个数形式单元形式单元新新displaydisplay内情向量内情向量临时变量临时变量老老spsp简单变量简单变量老老displaydisplay地址地址52Program P; Var a,x: integer; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R beg

36、in R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1DisplayDisplay表示例表示例1 1P P调用调用S S时时P的活的活动记录动记录S的活的活动记录动记录SPTOP返回地址返回地址简单变量简单变量:a:a简单变量简单变量: x: x老老sp:0sp:0老老display:2display:2参数个数参数个数:0:0老老sp:0sp:0返回地址返回地址display:0display:0简单变量简单变量: :i i简单变量简单变量:c:

37、c5 50 09 91 13 34 45 57 78 80 06 62 2111110101212display0 0层（主程序）过程的层（主程序）过程的displaydisplay只含只含1 1项，项，这一项就是主程序开始工作时所建立的这一项就是主程序开始工作时所建立的第第1 1个个SPSP值。值。53Program P; Var a,x: integer; Procedure Q(b:int ) Var i:integer; Procedure R( u:int; Var v:int); Var c,d: integer begin if u=1 then R(u+1,v) V:=(a+c)*(b-d); end R begin R(1,x); endQ procedure S; var c,i: integer; begin a:=1; Q(c); end Sbegin a:=0; S; end 0 01 12 21 1DisplayDisplay表示例表示例2 2过程过程S S中中调用调用Q Q时时P的活的活动记录动记录S的活的活动记录动记录SPTOPdisplaydisplay返回地址返回地址简单变量简单变量:a:a简单变量