运行时存储空间组织和

运行时存储空间的组织和管理.运行时的程序

过程的活动 过程的一次执行称为过程的一次活动活动记录 过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录.本章内容

影响存储分配策略的语言特征活动记录中各种数据域的安排(局部)各种存储分配策略（全局）静态分配、栈式分配、堆式分配非局部数据访问的实现方法各种参数传递方式及其实现符号表管理

.影响存储分配策略的语言特征过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块是否必须显式地释放.7.1局部存储分配策略7.1.1过程过程定义过程声明：过程名＋过程体过程调用执行被调用过程的过程体形式参数过程定义中用于在主调和被调间传递数据的标识符实在参数过程调用时用于在主调和被调间传递数据的变元活动的生存期程序执行期间的连续的步序列（过程执行的第一到最后一步）.名字的作用域和绑定名字的作用域一个声明起作用的那部分程序称为该声明的作用域。即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象（即保存值的存储单元）。符号表可用来寻找对一个名字的出现起作用的声明.名字的绑定从名字到值的两步映射。环境把名字映射到左值，而状态把左值映射到右值。赋值改变状态，但不改变环境。

如果环境将名字x映射到存储单元s，我们就说x被绑定到s。

名字存储单元状态值环境.名字的绑定

静态概念和动态概念的对应

静态概念

动态对应

过程的定义

过程的活动

名字的声明名字的绑定声明的作用域

绑定的生存期.活动记录过程一次执行所需的信息用一块连续的存储区来管理，称为活动记录。 一般的活动记录的布局：返回值临时数据实参可选的控制链可选的访问链保存的机器状态局部数据指向调用者的活动记录用来访问存于其它活动记录中的非局部数据.局部数据的安排字节是可编址内存的最小单位。变量所需的存储空间可以根据其类型而静态确定。一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间。局部数据的地址可以用相对于某个位置的地址来表示。数据对象的存储安排还有一个对齐问题。整数必须放在内存中特定的位置，如被2、4、8整除的地址.局部数据的安排在SPARC/Solaris工作站上下面两个结构的size分别是24和16，为什么不一样？typedefstruct_a{ typedefstruct_b{ char c1; charc1; long i; char c2; char c2; longi; doublef; doublef;}a; }b;.局部数据的安排在SPARC/Solaris工作站上下面两个结构的size分别是24和16，为什么不一样？typedefstruct_a{ typedefstruct_b{ char c1; 0 charc1; 0 long i; 4 char c2;1 char c2; 8 longi;4 doublef; 16 doublef;8}a; }b;.局部数据的安排在X86/Linux机器的结果和SPARC/Solaris工作站不一样，是20和16。typedefstruct_a{ typedefstruct_b{ char c1; 0 charc1; 0 long i; 4 char c2;1 char c2; 8 longi;4 doublef; 12 doublef;8}a; }b;.程序块本身含有局部变量声明的语句可以嵌套最近嵌套作用域规则并列程序块不会同时活跃并列程序块的变量可以重叠分配.程序块main(){/beginofB0

/ inta=0; intb=0; {/beginofB1

/ intb=1; {/beginofB2

/ inta=2; }/endofB2

/ {/beginofB3/ intb=3; }/endofB3

/ }/endofB1

/}/endofB0

/声明作用域inta=0;B0

B2

intb=0;B0

B1

intb=1;B1

B3

inta=2;B2intb=3;B3

a0b0b1a2,b3重叠分配存储单元.7.2全局存储分配策略介绍程序运行时所需的各个活动记录在存储空间的分配策略描述过程的目标代码怎样访问绑定到局部名字的存储单元介绍三种分配策略静态分配策略栈式分配策略堆式分配策略.7.2.1运行时内存的划分代码静态数据栈堆.7.2.2静态存储分配策略名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。每个活动记录的大小是固定的。过程调用时保存信息的地址在编译时也是已知的。.例：某分段式程序运行时刻的内存划分数组区临时工作单元区简单变量区形式单元区寄存器保护区返回地址某程序段指令代码常数区局部数据区程序段1程序段2……程序段n公用数据区.静态存储分配策略顺序分配算法（基于调用图）按照程序段出现的先后顺序逐段分配1/222/153/184/176/105/23程序段区域0~2122~3637~5455~7172~9495~104共需要105个存储单元程序段号/所需数据空间能用更少的空间么？.分层分配算法允许程序段之间的覆盖（覆盖可能性分析）程序段 区域6 0~95 0~224 0~163 23~402 17~311 41~62共需要63个存储单元1/222/153/184/176/105/23思考：如何设计分配算法？7/80.7.2.2静态存储分配策略静态分配给语言带来的限制不允许递归过程数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的数据结构不能动态建立.7.2.2静态存储分配策略Fortran语言被设计成允许静态存储分配cnsume的代码prduce的代码character50bufintegernextcharacterccharacter80bufferintegernextprduce的活动记录cnsume的活动记录静态数据代码.7.2.2静态存储分配策略C语言程序的外部变量和程序中出现的常量都可以静态分配。声明在函数外面外部变量静态外部变量声明在函数里面静态局部变量自动变量.7.2.3栈式存储分配策略如果过程允许递归某一时刻过程A可能已被自己调用了若干次，但只有最近一次处于执行状态。其余各次等待返回被中断的那次调用必须保存每次调用相应的数据区内容（活动记录）引入一个运行栈让过程的每次执行和过程的活动记录相对应。每调用一次过程，就把该过程的活动记录压入栈中，返回时弹出。假设寄存器top标记栈顶，局部名字x的相对地址为dx，则x的地址为top+dx怎样刻画控制进入和离开活动的情况？.7.2.3栈式存储分配策略引入活动树活动树:用树来描绘控制进入和离开活动的方式sq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9).7.2.3栈式存储分配策略活动树的特点每个结点代表某过程的一个活动根结点代表主程序的活动结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动结点a处于结点b的左边，当且仅当a的生存期先于b的生存期.7.2.3栈式全局存储分配策略当前活跃着的过程活动保存在栈中控制栈的内容：s,q(1,9),q(1,3),q(2,3)sq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9).7.2.3栈式存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）.7.2.3栈式存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）sa:arrays.7.2.3栈式存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）si:integerra:arraysr.7.2.3栈式存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）sk:integerq(1,9)a:arraysq(1,9)r.7.2.3栈式存储分配策略运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）sk:integerq(1,9)a:arrayq(1,3)k:integersq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3).7.2.3栈式存储分配策略过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等过程调用序列

过程调用时执行的分配活动记录，把信息填入它的域中的代码过程返回序列

过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中.7.2.3栈式存储分配策略即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原则是以活动记录中间的某个位置作为基地址长度能较早确定的域放在活动记录的中间一般把临时数据域放在局部数据域的后面把参数域和可能有的返回值域放在紧靠调用者活动记录的地方用同样的代码来执行各个活动的保存和恢复.7.2.3栈式存储分配策略调用者和被调用者之间的任务划分返回值和参数控制链访问链和机器状态局部数据临时数据返回值和参数局部数据临时数据

控制链访问链和机器状态top_sp

base_sp

被调用者的责任调用者的责任被调用者的活动记录调用者的活动记录栈.7.2.3栈式存储分配策略过程p调用过程q的调用序列p在栈上留出放返回值的空间，并计算实参，依次放入栈顶，同时改变top_sp的值p把返回地址和当前base_sp的值存入q的活动记录中，建立q的访问链，增加base_sp的值q保存寄存器的值和其它机器状态信息q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体.7.2.3栈式存储分配策略过程p调用过程q的返回序列q把返回值置入邻近p的活动记录的地方q对应调用序列的步骤（4），减小top_sp的值q恢复寄存器（包括base_sp）和机器状态，返回pp根据参数个数与类型和返回值类型调整top_sp，然后取出返回值.7.2.3栈式存储分配策略过程的参数个数可变的情况函数返回值改成用寄存器传递编译器产生将这些参数逆序进栈的代码被调用函数能准确地知道第一个参数的位置被调用函数根据第一个参数到栈中取第二、第三个参数等等如C语言的printf.7.2.3栈式存储分配策略活动记录的长度在编译时不能确定的情况局部数组的大小要等到过程激活时才能确定在活动记录中为这样的数组分别存放数组指针的单元运行时，这些指针指向分配在栈顶的存储空间.7.2.3栈式存储分配策略访问动态分配的数组q的数组q的活动记录p的数组控制链top_sp

base_sp

p的活动记录数组A的指针数组B的指针数组A数组B控制链.悬空引用悬空引用：引用某个已被释放的存储单元main() | intdangle(){ | { intp; | inti=23; p=dangle(); | return&i;} | }.7.2.4堆式存储分配策略栈式分配策略在下列情况下行不通：过程活动停止后，局部名字的值还必须维持被调用者的活动比调用者的活动的生存期更长，此时活动树不能正确描绘程序的控制流不遵守栈式规则的有Pascal语言和C语言的动态变量Java禁止程序员自己释放空间.7.3非局部名字的访问本节内容无过程嵌套的静态作用域（C语言）有过程嵌套的静态作用域（Pascal语言）动态作用域（Lisp语言）.7.3.1无过程嵌套的静态作用域过程体中的非局部引用可以直接使用静态确定的地址局部变量在栈顶的活动记录中，可以通过base_sp指针来访问无须深入栈中取数据，无须访问链过程可以作为参数来传递，也可以作为结果来返回.7.3.2有过程嵌套的静态作用域sort readarray exchange quicksort partition .7.3.2有过程嵌套的静态作用域过程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 3.7.3.2有过程嵌套的静态作用域过程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 3变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度.7.3.2有过程嵌套的静态作用域寻找非局部名字存储单元的访问链

sa,xq(1,9)k,v访问链sa,xq(1,3)k,v访问链q(1,9)k,v访问链sa,xq(1,3)k,v访问链q(1,9)k,v访问链p(1,3)i,j访问链e(1,3)访问链sa,xq(1,3)k,v访问链q(1,9)k,v访问链p(1,3)i,j访问链.7.3.2有过程嵌套的静态作用域假定过程p的嵌套深度为np，它引用嵌套深度为na的变量a，na

np。如何访问a的存储单元？从栈顶的活动记录开始，追踪访问链np

na次。到达a的声明所在过程的活动记录。访问链的追踪用间接操作就可完成。.7.3.2有过程嵌套的静态作用域过程p对变量a访问时，a的地址由下面的二元组表示：（np

na，a在活动记录中的偏移）.7.3.2有过程嵌套的静态作用域建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp<nx的情况x肯定就声明在p中被调用过程的访问链必须指向调用过程的活动记录的访问链.7.3.2有过程嵌套的静态作用域建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp

nx的情况p和x的嵌套深度分别为1，2，…，nx1的外围过程肯定相同追踪访问链np

nx+1次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录所到达的访问链就是x的活动记录中的访问链应该指向的那个访问链.7.3.2有过程嵌套的静态作用域programparam(input,output);（过程作为参数） procedureb(functionh(n:integer):integer); beginwriteln(h(2))end{b}; procedurec; varm:integer; functionf(n:integer):integer; beginf:=m+nend{f}; beginm:=0;b(f)end{c};begin c end.过程作为参数传递时，怎样在该过程被激活时建立它的访问链从b的访问链难以建立f的访问链.7.3.2有过程嵌套的静态作用域programparam(input,output);（过程作为参数） procedureb(functionh(… beginwriteln(h(2))end; procedurec; varm:integer; functionf(n:integer)… beginf:=m+nend{f}; beginm:=0;b(f)end{c};begin c end.访问链访问链paramcmb<f,>.7.3.2有过程嵌套的静态作用域programret(input,output);（过程作为返回值）varf:function(integer):integer; functiona:function(integer):integer; varm:integer;functionaddm(n:integer):integer;beginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2))end;beginf:=a;b(f)end.retabaddm.7.3.2有过程嵌套的静态作用域 C语言的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况:非静态局部变量（包括形式参数），它们分配在活动记录栈顶的那个活动记录中外部变量（包括定义在其它源文件中的外部变量）和静态的局部变量，它们都分配在静态数据区.通过使用Display表SPnSPn-1……SP1SP0数组存储区本过程……所辖分第临时工作单元程一序层局部数组说明存分储程局部变量区序分程序TOP本过程Display形式单元（m+1个）连主调分程序TOP接全局Display地址数返回地址据主调过程SP本过程TOPSPSPn为第n层过程数据区首址7.3.2有过程嵌套的静态作用域.Display表

Display表是一个指针数组d，在运行过程中，若当前活动的过程的嵌套深度为i，则d[i]中存放当前的活动记录地址，d[i-1],d[i-2],…,d[1]中依次存放着当前活动的过程的直接外层，…,

直至最外层（主程序）等每一层过程的最新活动地址。 这样，嵌套深度为j的变量a存放在由d[j]所指出的活动记录中。 在运行过程中维持一个Display表实现非局部访问比存取链效率要高。.Display表的维护（过程不作为参数传递）当嵌套深度为i的过程的活动记录筑在栈顶时：（1）在新的活动记录中保存d[i]的值；（2）置d[i]指向新的活动记录。在一个活动结束前，d[i]置成保存的旧值。用Display表如何访问非局部量？1.Display表是一个数组，开始地址用通用寄存器指出；2.Display表由一组寄存器实现。.ssa,xdisplayrrq(1,9)q(1,9)k,vp(1,9)p(1,9)e(1,9)

e(1,9)saved[2]

q(1,3)

q(1,3)saved[2]k,vp(1,3)

p(1,3)saved[3]i,j图6.19.设p（嵌套深度为j）调用q（嵌套深度为i）1.j<iP

callqqd[1]d[2]d[j]d[i]Pq.2.ji

qd[1]d[2]d[i-1]d[i]PqPcallqSaved[i]j=i.2.jij>i

qd[1]d[2]d[i-1]d[i]PqpcallqSaved[i]Pcallqqd[j]Saved[j].7.3.3动态作用域 程序运行时，一个名字a实施其影响，直到含a的声明的一个过程开始执行时暂停，此过程停止时，该影响恢复。设有下面的的调用序列：

ABCP

过程P中有对x的非局部引用，沿动态链（红链）查找，最先找到的便是。.7.3.3动态作用域programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin 静态作用域r:=0.25; 0.250 0.250show;small;writeln; 0.250 0.250show;small;writelnend.dynamicshowsmallsmallshowshowshow.7.3.3动态作用域programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin 动态作用域r:=0.25; 0.250 0.125show;small;writeln; 0.250 0.125show;small;writelnend.dynamicshowsmallsmallshowshowshow.7.3.3动态作用域实现动态作用域的方法深访问 用控制链搜索运行栈，寻找包含该非局部名字的第一个活动记录浅访问为每个名字在静态分配的存储空间中保存它的当前值当过程p的新活动出现时，p的局部名字n使用在静态数据区分配给n的存储单元。n的先前值可以保存在p的活动记录中，当p的活动结束时再恢复.7.4参数传递本节内容形参和实参相关联的几种方法

传值调用引用调用复制-恢复传名调用.7.4.1传值调用实参的右值传给被调用过程值调用可以如下实现把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中。调用过程计算实参，并把右值放入形参的存储单元中。调用者被调用者直接使用A实际参数A形式参数XA的值单向传值.7.4.2引用调用实参的左值传给被调用过程引用调用可以如下实现：把实参的左值放入形参的存储单元。在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参的。调用者被调用者间址访问A实际参数A形式参数XA的地址传地址.7.4.3复制-恢复调用值调用和引用调用的混合复制-恢复调用可以如下实现： 实参的右值和左值同时传给被调用过程。 在被调用过程中，像值调用那样使用实参的右值。 当控制返回调用过程时，根据传递来的实参的左值，将形参当前的值复写到实参存储单元。调用者被调用者A实际参数A形式参数XA的值传值/传地址A的地址.7.4.4换名调用用实参表达式对形参进行正文替换。procedureswap(varx,y:integer); vartemp:integer; begin 调用swap(i,a[i])

temp:=x; temp:=i;

x:=y; i:=a[i];

y:=temp a[i]:=temp end.子程序P(X,Y,Z);{Y:=Y+1;Z:=Z+X}传值调用：2传地址：X=T=5,Y=Z=A=2A:=A+1=2+1A:=A+T=3+58复制恢复：X=T=5,Y=Z=A=2Y:=Y+1=3Z:=Z+X=5+2=7Y A=3Z A=77换名A:=A+1=3A:=A+A+B=3+3+39主程序A:=2;B:=3;P(A+B,A,A);PrintA临时单元:T:A+B=5.符号表管理符号表的内容编译过程中需要不断地汇集和反复查证出现在源程序中各种名字的属性、特征、值等有关信息。他们通常被记录在一个或几个符号表中。变量类型、种属、长度、地址、形参标识、数组的内情向量过程外部过程、函数及类型、声明处理、形实结合信息、入口地址常数类型、地址、值.符号表管理_组织方式与查填技术组织方式分类符号表：变量表、过程表、常数表…统一符号表名字信息1……信息nsum1real定义……一般形式.符号表管理_组织方式与查填技术查填表的主要方式线性表对半查与二叉树Hash法对符号的名字或内码（key）进行简单的算术或逻辑运算后得到入口，要求均匀散列。.带嵌套程序（过程）的符号表管理如果允许过程的嵌套，对符号表有何特殊要求？程序具有如下性质标识符必须先定义后引用遵循最小作用域原则同一程序块（无嵌套）中，标识符不允许重名.带嵌套程序（过程）的符号表管理对符号表的要求属于哪一个层次的符号表当前处理的层次是什么外层符号表的内容对内层程序的处理有效内层符号表的内容对外层程序的处理无用定义以最内层优先能识别重定义/无定义和重说明/无说明问题.带嵌套程序（过程）的符号表管理层次划分的标志分程序：begin－end过程：过程名后首字符－end循环语句：for－end.带嵌套程序（过程）的符号表管理标识符的基本处理方法（1）当在某一层的说明中识别出一个标识符（id的定义性出现），以此标识符查相应于本层的符号表。If查到then出重复说明错else在符号表中加入新登记项，将标识符及有关信息填入（2）当在语句部分扫视到标识符时（id的应用性出现）首先在该层符号表中查找该id，if找不到then到直接外层符号表中去查，如此等等，一旦找到，则在表中取出有关信息并作相应处理If查遍所有外层符号表均未找到该id，则表明该id未经说明，出错.带嵌套程序（过程）的符号表管理实现（1）分层组织符号表登记项每层符号表的登记项连续地排列在一起（2）建立一个层次表_记录每层的信息扫视嵌套结构的源程序时，总是按先进后出的顺序为使每层符号表登记项连续地排列在一起，设置一个临时工作栈，按先进后出预构造符号表于栈中，造好后移入正式表算法基本步骤自左向右扫描源程序，遇到层开始，在层次表中加一项，记下临时工作栈栈顶遇到id定义，在栈顶添一项，并将层次表本层登记项数加1遇到层结束，将栈中内容正式记录入符号表，记下pointerouternecountpointer直接外层登记项数开始地址.过程说明语句的翻译分析参数的类型、分配地址统计参数和返回值的空间需求与调用语句配合完成形/实参数的结合符号表处理完成过程名的属性登记说明语句：

Procedureid(X1,X2,…,Xn).过程说明语句代码结构说明语句：

Procedureid(X1,X2,…,Xn)代码结构X1.code按参数传递要求实现参数X1的传递，或者完成传递准备；X2.code按参数传递要求实现参数X2的传递，或者完成传递准备；……Xn.code按参数传递要求实现参数Xn的传递，或者完成传递准备；完成动态存储分配相关的工作；进入过程体。.过程调用语句的代码结构过程调用语句id(E1,E2,…,En)代码结构E1.codea1:=E1.place…En.codean:=En.place动态存储分配相关工作gotopc+n+1parama1…parama