运行时存储空间组织和管理.ppt

《运行时存储空间组织和管理.ppt》由会员分享，可在线阅读，更多相关《运行时存储空间组织和管理.ppt（95页珍藏版）》请在三一办公上搜索。

1、运行时存储空间的组织和管理,运行时的程序,过程的活动过程的一次执行称为过程的一次活动活动记录过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录,本章内容,影响存储分配策略的语言特征活动记录中各种数据域的安排(局部)各种存储分配策略（全局）静态分配、栈式分配、堆式分配非局部数据访问的实现方法各种参数传递方式及其实现符号表管理,影响存储分配策略的语言特征,过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块是否必须显式地释放,7.1 局部存储分配策略

2、,7.1.1 过程过程定义过程声明：过程名过程体过程调用执行被调用过程的过程体形式参数过程定义中用于在主调和被调间传递数据的标识符实在参数过程调用时用于在主调和被调间传递数据的变元活动的生存期程序执行期间的连续的步序列（过程执行的第一到最后一步）,名字的作用域和绑定,名字的作用域一个声明起作用的那部分程序称为该声明的作用域。即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象（即保存值的存储单元）。符号表可用来寻找对一个名字的出现起作用的声明,名字的绑定,从名字到值的两步映射。环境把名字映射到左值，而状态把左值映射到右值。赋值改变状态，但不改变环境。如果环境将名字x映射到

3、存储单元s，我们就说x被绑定到s。,名字的绑定,静态概念和动态概念的对应,活动记录,过程一次执行所需的信息用一块连续的存储区来管理，称为活动记录。一般的活动记录的布局：,指向调用者的活动记录,用来访问存于其它活动记录中的非局部数据,局部数据的安排,字节是可编址内存的最小单位。变量所需的存储空间可以根据其类型而静态确定。一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间。局部数据的地址可以用相对于某个位置的地址来表示。数据对象的存储安排还有一个对齐问题。整数必须放在内存中特定的位置，如被2、4、8整除的地址,局部数据的安排,在SPARC/Solaris工作站上下面两

4、个结构的size分别是24和16，为什么不一样？typedef struct _atypedef struct _bchar c1;char c1;long i;char c2;charc2;long i;double f;double f;a;b;,局部数据的安排,在SPARC/Solaris工作站上下面两个结构的size分别是24和16，为什么不一样？typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2;1charc2;8 long i;4double f;16 double f;8a;b;,局部数据的安

5、排,在X86/Linux机器的结果和SPARC/Solaris工作站不一样，是20和16。typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2;1charc2;8 long i;4double f;12 double f;8a;b;,程序块,本身含有局部变量声明的语句可以嵌套最近嵌套作用域规则并列程序块不会同时活跃并列程序块的变量可以重叠分配,程序块,main()/begin of B0/int a=0;int b=0;/begin of B1/int b=1;/begin of B2/int a=2;/en

6、d of B2/begin of B3/int b=3;/end of B3/end of B1/end of B0/,7.2 全局存储分配策略,介绍程序运行时所需的各个活动记录在存储空间的分配策略描述过程的目标代码怎样访问绑定到局部名字的存储单元介绍三种分配策略静态分配策略栈式分配策略堆式分配策略,7.2.1 运行时内存的划分,7.2.2 静态存储分配策略,名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。每个活动记录的大小是固定的。过程调用时保存信息的地址在编译时也是已知的。,例：某分段式

7、程序运行时刻的内存划分,数组区临时工作单元区简单变量区形式单元区寄存器保护区返回地址,某程序段,静态存储分配策略,顺序分配算法（基于调用图）按照程序段出现的先后顺序逐段分配,程序段 区域 021 2236 3754 5571 7294 95104共需要105个存储单元,程序段号/所需数据空间,能用更少的空间么？,分层分配算法,允许程序段之间的覆盖（覆盖可能性分析）,程序段 区域6095022 4016323402173114162共需要63个存储单元,思考：如何设计分配算法？,7/80,7.2.2 静态存储分配策略,静态分配给语言带来的限制不允许递归过程数据对象的长度和它在内存中位置的限制，必

8、须是在编译时可以知道的数据结构不能动态建立,7.2.2 静态存储分配策略,Fortran语言被设计成允许静态存储分配,7.2.2 静态存储分配策略,C语言程序的外部变量和程序中出现的常量都可以静态分配。声明在函数外面外部变量静态外部变量声明在函数里面静态局部变量自动变量,7.2.3 栈式存储分配策略,如果过程允许递归某一时刻过程A可能已被自己调用了若干次，但只有最近一次处于执行状态。其余各次等待返回被中断的那次调用必须保存每次调用相应的数据区内容（活动记录）引入一个运行栈让过程的每次执行和过程的活动记录相对应。每调用一次过程，就把该过程的活动记录压入栈中，返回时弹出。假设寄存器top标记栈顶，

9、局部名字x的相对地址为dx，则x的地址为top+dx怎样刻画控制进入和离开活动的情况？,7.2.3 栈式存储分配策略,引入活动树活动树:用树来描绘控制进入和离开活动的方式,7.2.3 栈式存储分配策略,活动树的特点每个结点代表某过程的一个活动根结点代表主程序的活动结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动结点a处于结点b的左边，当且仅当a的生存期先于b的生存期,7.2.3 栈式全局存储分配策略,当前活跃着的过程活动保存在栈中控制栈的内容：s,q(1,9),q(1,3),q(2,3),7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即

10、活动记录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,s,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等过程调用序列过程调用时执行的分配活动记录，把信息填入它的

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

12、程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 栈式

13、存储分配策略,过程的参数个数可变的情况函数返回值改成用寄存器传递编译器产生将这些参数逆序进栈的代码被调用函数能准确地知道第一个参数的位置被调用函数根据第一个参数到栈中取第二、第三个参数等等如C语言的printf,7.2.3 栈式存储分配策略,活动记录的长度在编译时不能确定的情况局部数组的大小要等到过程激活时才能确定在活动记录中为这样的数组分别存放数组指针的单元运行时，这些指针指向分配在栈顶的存储空间,7.2.3 栈式存储分配策略,悬空引用,悬空引用：引用某个已被释放的存储单元main()|int dangle()|int p;|int i=23;p=dangle();|return|,7.2.

14、4 堆式存储分配策略,栈式分配策略在下列情况下行不通：过程活动停止后，局部名字的值还必须维持被调用者的活动比调用者的活动的生存期更长，此时活动树不能正确描绘程序的控制流不遵守栈式规则的有Pascal语言和C语言的动态变量Java禁止程序员自己释放空间,7.3 非局部名字的访问,本节内容无过程嵌套的静态作用域（C语言）有过程嵌套的静态作用域（Pascal语言）动态作用域（Lisp语言）,7.3.1 无过程嵌套的静态作用域,过程体中的非局部引用可以直接使用静态确定的地址局部变量在栈顶的活动记录中，可以通过base_sp指针来访问无须深入栈中取数据，无须访问链过程可以作为参数来传递，也可以作为结果来

15、返回,7.3.2 有过程嵌套的静态作用域,sortreadarrayexchangequicksortpartition,7.3.2 有过程嵌套的静态作用域,过程嵌套深度sort1readarray2exchange2quicksort2partition3,7.3.2 有过程嵌套的静态作用域,过程嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度,7.3.2 有过程嵌套的静态作用域,寻找非局部名字存储单元的访问链,s,a,x,q(1,9),k,v,访问链,s,a,x,q(1,3),k,

16、v,访问链,q(1,9),k,v,访问链,s,a,x,q(1,3),k,v,访问链,q(1,9),k,v,访问链,p(1,3),i,j,访问链,e(1,3),访问链,s,a,x,q(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

17、 na，a在活动记录中的偏移）,7.3.2 有过程嵌套的静态作用域,建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp nx的情况x肯定就声明在p中被调用过程的访问链必须指向调用过程的活动记录的访问链,7.3.2 有过程嵌套的静态作用域,建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp nx的情况p和x的嵌套深度分别为1，2，nx 1的外围过程肯定相同追踪访问链np nx+1次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录所到达的访问链就是x的活动记录中的访问链应该指向的那个访问链,7.3.2 有过程嵌套的静态作用域,program param(

18、input,output);（过程作为参数）procedure b(function h(n:integer):integer);begin writeln(h(2)end b;procedure c;var m:integer;function f(n:integer):integer;begin f:=m+n end f;begin m:=0;b(f)end c;begin cend.,过程作为参数传递时，怎样在该过程被激活时建立它的访问链 从b的访问链难以建立f的访问链,7.3.2 有过程嵌套的静态作用域,program param(input,output);（过程作为参数）proce

19、dure b(function h(begin writeln(h(2)end;procedure c;var m:integer;function f(n:integer)begin f:=m+n end f;begin m:=0;b(f)end c;begin cend.,7.3.2 有过程嵌套的静态作用域,program ret(input,output);（过程作为返回值）var f:function(integer):integer;function a:function(integer):integer;var m:integer;function addm(n:integer):

20、integer;begin return m+n end;begin m:=0;return addm end;procedure b(g:function(integer):integer);begin writeln(g(2)end;begin f:=a;b(f)end.,7.3.2 有过程嵌套的静态作用域,C语言的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况:非静态局部变量（包括形式参数），它们分配在活动记录栈顶的那个活动记录中外部变量（包括定义在其它源文件中的外部变量）和静态的局部变量，它们都分配在静态数据区,通过使用Display表,SPnSPn-1SP1SP

21、0,SP,SPn为第n层过程数据区首址,7.3.2 有过程嵌套的静态作用域,Display表Display表是一个指针数组d，在运行过程中，若当前活动的过程的嵌套深度为i，则di中存放当前的活动记录地址，di-1,di-2,d1 中依次存放着当前活动的过程的直接外层，,直至最外层（主程序）等每一层过程的最新活动地址。这样，嵌套深度为j的变量a存放在由dj所指出的活动记录中。在运行过程中维持一个Display表实现非局部访问比存取链效率要高。,Display表的维护（过程不作为参数传递）当嵌套深度为i的过程的活动记录筑在栈顶时：（1）在新的活动记录中保存di的值；（2）置di指向新的活动记录。在

22、一个活动结束前，di置成保存的旧值。用Display表如何访问非局部量？1.Display表是一个数组，开始地址用通用 寄存器指出；2.Display表由一组寄存器实现。,s,sa,x,display,r,r,q(1,9),q(1,9)k,v,p(1,9),p(1,9),e(1,9),e(1,9)save d2,q(1,3),q(1,3)save d2k,v,p(1,3),p(1,3)save d3i,j,图 6.19,设p（嵌套深度为j）调用q（嵌套深度为i）,1.ji,P call q,q,d1d2djdi,P,q,2.ji,q,d1d2di-1di,P,q,Pcall q,Save di

23、,j=i,2.ji ji,q,d1d2di-1di,P,q,pcall q,Save di,Pcall q,q,dj,Save dj,7.3.3 动态作用域,程序运行时，一个名字a实施其影响，直到含a的声明的一个过程开始执行时暂停，此过程停止时，该影响恢复。设有下面的的调用序列：A B C P过程P中有对x的非局部引用，沿动态链（红链）查找，最先找到的便是。,7.3.3 动态作用域,program dynamic(input,output);var r:real;procedure show;begin write(r:5:3)end;procedure small;var r:real;be

24、gin r:=0.125;show end;begin静态作用域 r:=0.25;0.2500.250 show;small;writeln;0.2500.250 show;small;writeln end.,7.3.3 动态作用域,program dynamic(input,output);var r:real;procedure show;begin write(r:5:3)end;procedure small;var r:real;begin r:=0.125;show end;begin动态作用域 r:=0.25;0.250 0.125 show;small;writeln;0.2

25、50 0.125 show;small;writeln end.,7.3.3 动态作用域,实现动态作用域的方法深访问用控制链搜索运行栈，寻找包含该非局部名字的第一个活动记录浅访问为每个名字在静态分配的存储空间中保存它的当前值当过程p的新活动出现时，p的局部名字n使用在静态数据区分配给n的存储单元。n的先前值可以保存在p的活动记录中，当p的活动结束时再恢复,7.4 参 数 传 递,本节内容形参和实参相关联的几种方法 传值调用引用调用复制-恢复传名调用,7.4.1 传值调用,实参的右值传给被调用过程 值调用可以如下实现把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中。调用过程计算

26、实参，并把右值放入形参的存储单元中。,7.4.2 引用调用,实参的左值传给被调用过程 引用调用可以如下实现：把实参的左值放入形参的存储单元。在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参的。,7.4.3 复制-恢复调用,值调用和引用调用的混合复制-恢复调用可以如下实现：实参的右值和左值同时传给被调用过程。在被调用过程中，像值调用那样使用实参的右值。当控制返回调用过程时，根据传递来的实参的左值，将形参当前的值复写到实参存储单元。,7.4.4 换名调用,用实参表达式对形参进行正文替换。procedure swap(var x,y:integer);var temp

27、:integer;begin 调用swap(i,ai)temp:=x;temp:=i;x:=y;i:=ai;y:=tempai:=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,换名A:=A+1=3A:=A+A+B=3+3+39,主程序A:=2;B:=3;P(A+B,A,A);Print A,临时单元:T:A+B=5,符号表管理,符号表的内容编译过程中需要不断地汇集和反复查证出现在源程序中各种名字的属性、特征、值等有关信息。他们通常被记录在一个或几个符号表中。变量类型、种属、长度、

28、地址、形参标识、数组的内情向量过程外部过程、函数及类型、声明处理、形实结合信息、入口地址常数类型、地址、值,符号表管理_组织方式与查填技术,组织方式分类符号表：变量表、过程表、常数表统一符号表,一般形式,符号表管理_组织方式与查填技术,查填表的主要方式线性表对半查与二叉树Hash法对符号的名字或内码（key）进行简单的算术或逻辑运算后得到入口，要求均匀散列。,带嵌套程序（过程）的符号表管理,如果允许过程的嵌套，对符号表有何特殊要求？程序具有如下性质标识符必须先定义后引用遵循最小作用域原则同一程序块（无嵌套）中，标识符不允许重名,带嵌套程序（过程）的符号表管理,对符号表的要求属于哪一个层次的符号

29、表当前处理的层次是什么外层符号表的内容对内层程序的处理有效内层符号表的内容对外层程序的处理无用定义以最内层优先能识别重定义/无定义和重说明/无说明问题,带嵌套程序（过程）的符号表管理,层次划分的标志分程序：beginend过程：过程名后首字符end循环语句：forend,带嵌套程序（过程）的符号表管理,标识符的基本处理方法（1）当在某一层的说明中识别出一个标识符（id的定义性出现），以此标识符查相应于本层的符号表。If查到then出重复说明错else在符号表中加入新登记项，将标识符及有关信息填入（2）当在语句部分扫视到标识符时（id的应用性出现）首先在该层符号表中查找该id，if找不到then

30、到直接外层符号表中去查，如此等等，一旦找到，则在表中取出有关信息并作相应处理If查遍所有外层符号表均未找到该id，则表明该id未经说明，出错,带嵌套程序（过程）的符号表管理,实现（1）分层组织符号表登记项每层符号表的登记项连续地排列在一起（2）建立一个层次表_记录每层的信息扫视嵌套结构的源程序时，总是按先进后出的顺序为使每层符号表登记项连续地排列在一起，设置一个临时工作栈，按先进后出预构造符号表于栈中，造好后移入正式表算法基本步骤自左向右扫描源程序，遇到层开始，在层次表中加一项，记下临时工作栈栈顶遇到id定义，在栈顶添一项，并将层次表本层登记项数加1遇到层结束，将栈中内容正式记录入符号表，记下

31、pointer,过程说明语句的翻译,分析参数的类型、分配地址统计参数和返回值的空间需求与调用语句配合完成形/实参数的结合符号表处理完成过程名的属性登记,说明语句：Procedure id(X1,X2,Xn),过程说明语句代码结构,说明语句：Procedure id(X1,X2,Xn),代码结构X1.code 按参数传递要求实现参数X1的传递，或者完成传递准备；X2.code 按参数传递要求实现参数X2的传递，或者完成传递准备；Xn.code 按参数传递要求实现参数Xn的传递，或者完成传递准备；完成动态存储分配相关的工作；进入过程体。,过程调用语句的代码结构,过程调用语句id(E1,E2,En)

32、,代码结构E1.codea1:=E1.placeEn.codean:=En.place动态存储分配相关工作goto pc+n+1param a1param ancall id.place，n,需要一个队列存放a1,a2,an，以生成,过程调用的实现,1)在过程 f 中调用过程 p 时a.f 对实在参数求值，将结果存入 p 的活动记录参数域b.在 p 的活动记录中存放返回地址和当前栈顶指针c.按照活动记录的大小，上移栈顶指针d.控制转到 p 的入口（过程体）,e.p 存放寄存器值和其它状态信息f.执行过程体2.从过程 p 返回：对应return语句a.p 在返回值域中保存返回值b.恢复原栈顶指针

33、和其它寄存器c.按返回地址返回调用者,代码结构E1.codea1:=E1.placeEn.codean:=En.place动态存储分配相关工作goto pc+n+1param a1param ancall id.place，n,过程调用语句的制导翻译定义,产生式语义规则S call id(Elist)S.code:=Elist.code|gen(goto pc+Elist.num+1)|for 队列q中的每一项 t do gen(param t)|gen(call id.place,Elist.num)Elist E Elist.num:=1;Elist.code:=E.code|t:=new

34、temp;gen(t:=E.place)；建立队列q，并将t 放入qElist Elist1,E Elist.num:=Elist 1.num+1;Elist.code:=Elist 1.code|E.code|t:=newtemp;gen(t:=E.place);将t 放入队列q,3+a,6,生成的目标代码t1:=3+agoto pc+3param t1param 6call f,2,函数调用 f(3+a,6)的翻译,函数调用 f(b*c-1,x+y,x,y)的翻译,t1:=b*ct2:=t1-1t3:=x+ygoto pc+5param t2param t3param xparam yca

35、ll f,4,赋值语句x:=a+b+f(b*c-1,x+y,x,y)的翻译,t1:=a+bt2:=b*ct3:=t1-1t4:=x+ygoto pc+5,param t3param t4param xparam ycall f.place,4 t5:=t1+f.valx:=t5,本 章 要 点,影响存储分配策略的语言特征各种存储分配策略，主要了解静态分配和动态栈式分配活动记录中各种数据域的作用和安排非局部数据访问的实现方法各种参数传递方式及其实现符号表管理,习 题,P295:7.6,思考题,1 试分别给出下列语句的三地址码，并希望你能讲清楚是如何转换出来的。call sub(a+5,b*a,c)a+fun(a+5,b*a,c)2 什么叫静态绑定？什么叫动态绑定？变量的绑定和过程的绑定有什么区别？3 程序的执行过程中如何进行存储分配？何时为哪些数据目标分配存储空间？,