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

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

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

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

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

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

5、char c2; 1 char c2; 8 long i; 4 double f; 16 double f;8 a; b;,局部数据的安排,在X86/Linux机器的结果和SPARC/Solaris工作站不一样，是20和16。 typedef struct _a typedef struct _b char c1; 0 char c1; 0 long i; 4 char c2; 1 char c2; 8 long i; 4 double f; 12 double f;8 a; b;,程序块,本身含有局部变量声明的语句 可以嵌套 最近嵌套作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重

6、叠分配,程序块,main() / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / / end of B0 /,7.2 全局存储分配策略,介绍程序运行时所需的各个活动记录在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元 介绍三种分配策略 静态分配策略 栈式分配策略 堆式分配策略,7.2.1 运行时内存的划分

7、,7.2.2 静态存储分配策略,名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。 绑定的生存期是程序的整个运行时间。 控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。 每个活动记录的大小是固定的。 过程调用时保存信息的地址在编译时也是已知的。,例：某分段式程序运行时刻的内存划分,数组区 临时工作单元区 简单变量区 形式单元区 寄存器保护区 返回地址,某程序段,静态存储分配策略,顺序分配算法（基于调用图） 按照程序段出现的先后顺序逐段分配,程序段 区域 021 2236 3754 5571 7294 95104 共需要105个存储单元,程序段号/所需数据空间,能用更少的空间

8、么？,分层分配算法,允许程序段之间的覆盖（覆盖可能性分析）,程序段 区域 6 09 5 022 4 016 3 2340 2 1731 1 4162 共需要63个存储单元,思考：如何设计分配算法？,7/80,7.2.2 静态存储分配策略,静态分配给语言带来的限制 不允许递归过程 数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的 数据结构不能动态建立,7.2.2 静态存储分配策略,Fortran语言被设计成允许静态存储分配,7.2.2 静态存储分配策略,C语言程序的外部变量和程序中出现的常量都可以静态分配。 声明在函数外面 外部变量 静态外部变量 声明在函数里面 静态局部变量 自动

9、变量,7.2.3 栈式存储分配策略,如果过程允许递归 某一时刻过程A可能已被自己调用了若干次，但只有最近一次处于执行状态。其余各次等待返回被中断的那次调用 必须保存每次调用相应的数据区内容（活动记录） 引入一个运行栈 让过程的每次执行和过程的活动记录相对应。 每调用一次过程，就把该过程的活动记录压入栈中，返回时弹出。 假设寄存器top标记栈顶，局部名字x的相对地址为dx，则x的地址为top+dx 怎样刻画控制进入和离开活动的情况？,7.2.3 栈式存储分配策略,引入活动树 活动树:用树来描绘控制进入和离开活动的方式,7.2.3 栈式存储分配策略,活动树的特点 每个结点代表某过程的一个活动 根结

10、点代表主程序的活动 结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动 结点a处于结点b的左边，当且仅当a的生存期先于b的生存期,7.2.3 栈式全局存储分配策略,当前活跃着的过程活动保存在栈中 控制栈的内容：s, q (1, 9), q (1, 3), q (2, 3),7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,s,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记

11、录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等 过程调用序列 过程调用时执行的分配活动记录，把信息填入它的域中的代码 过程返回序列 过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码 调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中,7.2.3 栈式存储分配策略,即使是同一种语言，过程

12、调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异 设计这些序列和活动记录的一些原则是 以活动记录中间的某个位置作为基地址 长度能较早确定的域放在活动记录的中间 一般把临时数据域放在局部数据域的后面 把参数域和可能有的返回值域放在紧靠调用者活动记录的地方 用同样的代码来执行各个活动的保存和恢复,7.2.3 栈式存储分配策略,调用者和被调用者之间的任务划分,7.2.3 栈式存储分配策略,过程p调用过程q的调用序列 p在栈上留出放返回值的空间，并计算实参，依次放入栈顶，同时改变top_sp的值 p把返回地址和当前base_sp的值存入q的活动记录中，建立q的访问链，增加base_sp的值

13、 q保存寄存器的值和其它机器状态信息 q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体,7.2.3 栈式存储分配策略,过程p调用过程q的返回序列 q把返回值置入邻近p的活动记录的地方 q对应调用序列的步骤（4），减小top_sp的值 q恢复寄存器（包括base_sp）和机器状态，返回p p根据参数个数与类型和返回值类型调整top_sp，然后取出返回值,7.2.3 栈式存储分配策略,过程的参数个数可变的情况 函数返回值改成用寄存器传递 编译器产生将这些参数逆序进栈的代码 被调用函数能准确地知道第一个参数的位置 被调用函数根据第一个参数到栈中取第二、第三

14、个参数等等 如C语言的printf,7.2.3 栈式存储分配策略,活动记录的长度在编译时不能确定的情况 局部数组的大小要等到过程激活时才能确定 在活动记录中为这样的数组分别存放数组指针的单元 运行时，这些指针指向分配在栈顶的存储空间,7.2.3 栈式存储分配策略,悬空引用,悬空引用：引用某个已被释放的存储单元 main() | int dangle ( ) | int p; | int i = 23; p = dangle ( ); | return | ,7.2.4 堆式存储分配策略,栈式分配策略在下列情况下行不通： 过程活动停止后，局部名字的值还必须维持 被调用者的活动比调用者的活动的生存

15、期更长，此时活动树不能正确描绘程序的控制流 不遵守栈式规则的有Pascal语言和C语言的动态变量 Java禁止程序员自己释放空间,7.3 非局部名字的访问,本节内容 无过程嵌套的静态作用域（C语言） 有过程嵌套的静态作用域（Pascal语言） 动态作用域（Lisp语言）,7.3.1 无过程嵌套的静态作用域,过程体中的非局部引用可以直接使用静态确定的地址 局部变量在栈顶的活动记录中，可以通过base_sp指针来访问 无须深入栈中取数据，无须访问链 过程可以作为参数来传递，也可以作为结果来返回,7.3.2 有过程嵌套的静态作用域,sort readarray exchange quicksort

16、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 有过程嵌套的静态作用域,寻找非局部名字存储单元的访问链,s,a, x,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问

17、链,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的地址由下面的二元组

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

19、静态作用域,program param(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 c end.,过程作为参数传递时，怎样在该过程被激活时建立它的访问链 从b的访问链难以建立f的访问链,7.3.2 有过程嵌套的静态作用域

20、,program param(input, output);（过程作为参数） procedure 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 c end.,7.3.2 有过程嵌套的静态作用域,program ret (input, output);（过程作为返回值） var f: function (integer): integer; functio

21、n a: function (integer): integer; var m: integer; function addm (n: integer): 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语言的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况: 非静态局部变量

22、（包括形式参数），它们分配在活动记录栈顶的那个活动记录中 外部变量（包括定义在其它源文件中的外部变量）和静态的局部变量，它们都分配在静态数据区,通过使用Display表,SPn SPn-1 SP1 SP0,SP,SPn为第n层过程数据区首址,7.3.2 有过程嵌套的静态作用域,Display表 Display表是一个指针数组d，在运行过程中，若当前活动的过程的嵌套深度为i，则di中存放当前的活动记录地址，di-1,di-2, ,d1 中依次存放着当前活动的过程的直接外层， , 直至最外层（主程序）等每一层过程的最新活动地址。 这样，嵌套深度为j的变量a存放在由dj所指出的活动记录中。 在运行过

23、程中维持一个Display表实现非局部访问比存取链效率要高。,Display表的维护（过程不作为参数传递） 当嵌套深度为i的过程的活动记录筑在栈顶时： （1）在新的活动记录中保存di的值； （2）置di指向新的活动记录。 在一个活动结束前， di置成保存的旧值。 用Display表如何访问非局部量？ 1. Display表是一个数组，开始地址用通用 寄存器指出； 2. Display表由一组寄存器实现。,s,s a, 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 d

24、2 k, v,p(1,3),p(1,3) save d3 i, j,图 6.19,设p （嵌套深度为j）调用q（嵌套深度为i）,1. ji,P call q,q,d1 d2 dj di,P,q,2. ji,q,d1 d2 di-1 di,P,q,P call q,Save di,j=i,2. ji ji,q,d1 d2 di-1 di,P,q,p call q,Save di,P call q,q,dj,Save dj,7.3.3 动态作用域,程序运行时，一个名字a实施其影响，直到含a的声明的一个过程开始执行时暂停，此过程停止时，该影响恢复。 设有下面的的调用序列： A B C P 过程P中有

25、对x的非局部引用，沿动态链（红链）查找，最先找到的便是。,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.250 show; small; writeln; 0.250 0.250 show; small; writeln end.,7.3.3 动态作用域,program

26、 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.250 0.125 show; small; writeln end.,7.3.3 动态作用域,实现动态作用域的方法 深访问 用控制链搜索运行栈，寻找包含该非局部名字的第一个活动记录 浅访问 为每个名字在静

27、态分配的存储空间中保存它的当前值 当过程p的新活动出现时，p的局部名字n使用在静态数据区分配给n的存储单元。n的先前值可以保存在p的活动记录中，当p的活动结束时再恢复,7.4 参 数 传 递,本节内容 形参和实参相关联的几种方法 传值调用 引用调用 复制-恢复 传名调用,7.4.1 传值调用,实参的右值传给被调用过程 值调用可以如下实现 把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中。 调用过程计算实参，并把右值放入形参的存储单元中。,7.4.2 引用调用,实参的左值传给被调用过程 引用调用可以如下实现： 把实参的左值放入形参的存储单元。 在被调用过程的目标代码中，任何对形

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

29、 ai := temp end,子程序 P(X,Y,Z); Y:=Y+1; Z:=Z+X,传值调用： 2,传地址： X=T=5,Y=Z=A=2 A:=A+1=2+1 A:=A+T=3+5 8,换名 A:=A+1=3 A:=A+A+B=3+3+3 9,主程序 A:=2; B:=3; P(A+B, A, A); Print A,临时单元: T:A+B=5,符号表管理,符号表的内容 编译过程中需要不断地汇集和反复查证出现在源程序中各种名字的属性、特征、值等有关信息。他们通常被记录在一个或几个符号表中。 变量 类型、种属、长度、地址、形参标识、数组的内情向量 过程 外部过程、函数及类型、声明处理、形实

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

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

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

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

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

35、程 p 返回：对应return语句 a. p 在返回值域中保存返回值 b. 恢复原栈顶指针和其它寄存器 c. 按返回地址返回调用者,代码结构 E1.code a1:=E1.place En.code an:=En.place 动态存储分配相关工作 goto pc+n+1 param a1 param an call 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(c

36、all id.place,Elist.num) Elist E Elist.num := 1; Elist.code := E.code | t:=newtemp; gen(t:= E.place)；建立队列q，并将t 放入q Elist 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 + a goto pc+3 param t1 param 6 call f, 2,函数

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