第六章运行时存储空间的组织和管理.ppt

1、第六章 运行时存储空间的 组织和管理,编译程序在完成词法、语法和语义分析后，在生成目标代码之前，需要把程序的静态正文和实现这个程序的运行时的活动联系起来弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定义的量是如何存放的，如何去访问它们。 在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。在程序语言中，程序使用的存储单元都是由标识符来表示的。它们对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。所以对于编译程序来说存储组织与管理是一个复杂而又十分重要的问题。,本章内容: 讨论一个活动记录中的数据安排 程序执行过程中，所有活动记录的组织方式 存储

2、器的组织与存储分配的策略 非局部名称的访问 参数传递,6.1 局部存储分配策略,过程的每一次运行称为一次活动（activation）。活动是一个动态的概念，它有有限的生存期。 活动的生存期是指从进入活动的第一条指令执行到离开此活动前的最后一条指令执行的这段时间，其中包括调用其它过程时其它活动的生存期。,6.1.2 名字的作用域和绑定,名字的作用域 一个声明起作用的程序部分称为该声明的作用域。 即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象。,名字的绑定 运行时为名字X分配存储空间S，这一过程称为绑定 （binding）。 换句话说，绑定是名字X与存储空间S的结合。,

3、X是一个对象： 既可以是数据对象，如变量，与之结合的是一个存储单元； 也可以是操作对象，如过程，与之结合的是可执行的代码。 我们的讨论仅限于X是一个数据对象。,名字的声明与名字的绑定均需要有对应的存储空间，而存储空间的对应方式，一个是静态的，一个是动态的。 声明时关心的是声明的作用域，即当一个名字被引用时，在不同的作用域中与该名字的不同声明结合； 绑定时关心的是绑定的生存期，即当一个名字在运行时被实际分配的存储单元，名字与存储单元结合的这段时间被称为绑定的生存期，显然此生存期应该和名字的生存期一致。,静 态动 态 过程的定义过程的活动 名字的声明名字的绑定 声明的作用域绑定的生存期 符号表活动

4、记录,静态与动态,变量与值的两步映射,环境改变存储，状态改变值。 例5.3 若有变量声明x: real和常量声明const pi=3.14，则赋值句中变量和常量的映射关系：,常量没有左值（存储空间），所以不能被赋值。,6.1.3 活动记录,为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，我们把这样的一个连续存储块称为活动纪录。,返回值,实在参数,控制链,访问链,保存机器状态,局部数据,临时变量,控制链:指向调用过程活动的活动记录。 访问链：指向本活动要访 问的非局部数据所在的活动记录。 保存机器状态：调用过程 活动在调用点的机器状态，包括计数器，各种寄存器的值。 局部数据：过程中定

5、义的 局部量。 临时变量：编译产生。,6.1.4 局部数据的安排 字节是可编址内存的最小单位。,6.1.4 局部数据的安排 字节是可编址内存的最小单位。 变量所需的存储空间可以根据其类型而静态确定。,6.1.4 局部数据的安排 字节是可编址内存的最小单位。 变量所需的存储空间可以根据其类型而静态确定。 一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间。,6.1.4 局部数据的安排 字节是可编址内存的最小单位。 变量所需的存储空间可以根据其类型而静态确定。 一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间。 局部数据的地址可以用相对

6、于某个位置的地址来表示。,6.1.4 局部数据的安排 字节是可编址内存的最小单位。 变量所需的存储空间可以根据其类型而静态确定。 一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间。 局部数据的地址可以用相对于某个位置的地址来表示。 数据对象的存储安排还有一个对齐问题。,6.1.5 程序块 本身含有局部变量声明的语句 可以嵌套 最接近的嵌套作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重叠分配,main() / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin o

7、f B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / / end of B0 /,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 /,main() / begin of

8、 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 /,6.2 全局存储分配策略,介绍程序运行时所需的各个活动记录在存储空间的分配策略,6.2 全局存储分配策略,介绍程序运行时所需的各个活动记录在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元,6.2 全局存储分配策略,介绍程序运行时所需的各个活动记录

9、在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元 介绍三种分配策略 静态分配策略,6.2 全局存储分配策略,介绍程序运行时所需的各个活动记录在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元 介绍三种分配策略 静态分配策略 栈式分配策略,6.2 全局存储分配策略,介绍程序运行时所需的各个活动记录在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元 介绍三种分配策略 静态分配策略 栈式分配策略 堆式分配策略,静态分配策略在编译是对所有对象分配固定的存储单元。且在运行是保持不变。 栈式动态分配策略在运行时把存储器作为一个栈进行管理，

10、运行时，每当调用一个过程，它所需要的存储空间就动态的分配于栈顶，一旦退出，它所占空间就予以释放。 堆式动态存储策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者分给一块，凡释放者退回给堆。,6.2.1 运行时内存的划分,6.2.2 静态存储分配 如果在编译时就能够确定一个程序在运行时所需要的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种分配方法叫做静态分配。 特点：绑定是1对1的映射。名字在程序编译时与存储空间结合，每次过程活动时，它的名字映射到同一存储单元。程序运行时不再有对存储空间的分配。,

11、静态分配的限制： 数据对象的大小和它在内存中位置的限制必须在编译时确定，如数组的大小不能是动态的； 不允许程序递归，因为一个过程的所有活动使用同样的名字绑定，即绑定是一对一的； 不能动态生成或撤消数据，因为运行时没有存储分配机制。 完全采用静态分配的语言：早期的FORTRAN。 允许分别编译的数据定义模块（如全程引用的数据），也可以采用静态分配，因为它们一般在整个程序运行的期间是被共享的。,6.2.3 栈式存储分配 存储空间被组织成栈，活动记录的推入和弹出分别对应于活动的开始和结束。 与静态分配不同的是，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的

12、存储空间也随之消失。,6.2.3 栈式分配 活动树:用树来描绘控制进入和离开活动的方式,活动树的特点： 每个结点代表某过程的一个活动 根结点代表主程序的活动 结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动 结点a处于结点b的左边，当且仅当a的生存期先于b的生存期 活动树上各节点之间具有下述关系： 同一层次的活动生存期不交； 任一时刻，处在生存期的活动构成一条从根到某节 点的路径； 路径上各节点生存期是嵌套的（后进先出）。,当前活跃着的过程活动可以保存在一个栈中 控制栈的内容：s, q (1, 9), q (1, 3), q (2, 3),运行栈：把控制栈中的信息拓广到包括过程活动

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

14、来管理活动记录栈，保存或恢复机器状态等 过程调用序列 过程调用时执行的分配活动记录，把信息填入它的域中的代码 过程返回序列 过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码,过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等 过程调用序列 过程调用时执行的分配活动记录，把信息填入它的域中的代码 过程返回序列 过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码 调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中,调用者和被调用者之间的任务划分,过程p调用过程q的调用序列 p计算实参，依次放入栈顶，并在栈顶留出放返

15、回值的空间。top_sp的值在此过程中被改变 p把返回地址和当前base_sp的值存入q的活动记录中，建立q的访问链，增加base_sp的值 q保存寄存器的值和其它机器状态信息 q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体,调用者和被调用者之间的任务划分,过程p调用过程q的返回序列 q把返回值置入邻近p的活动记录的地方 q对应调用序列的步骤（4），减小top_sp的值 q恢复寄存器（包括base_sp）和机器状态，返回p p根据参数个数与类型和返回值类型调整top_sp，然后取出返回值,调用者和被调用者之间的任务划分,过程的参数个数可变的情况 函

16、数返回值改成用寄存器传递 编译器产生将这些参数逆序进栈的代码 被调用函数能准确地知道第一个参数的位置 被调用函数根据第一个参数到栈中取第二、第三个参数等等,调用者和被调用者之间的任务划分,活动记录的长度在编译时不能确定的情况 局部数组的大小要等到过程激活时才能确定 在活动记录中为这样的数组分别存放数组指针的单元 运行时，这些指针指向分配在栈顶的存储空间,悬空引用：引用某个已被释放的存储单元,悬空引用：引用某个已被释放的存储单元 main()|int dangle ( ) | int q;|int j = 20; q = dangle ( );|return |,6.3.3 堆式存储分配 1局部

17、名的值在活动结束时必须被保存。 2. 被调用者的活动生存期超过调用者。 用活动树不能够正确描绘这种语言的过 程之间的控制流。 new(p); dispose(p);,6.3 非局部名字的访问,本节介绍 无过程嵌套的静态作用域（C语言） 有过程嵌套的静态作用域（Pascal语言） 动态作用域（Lisp语言）,6.3.1 无过程嵌套的静态作用域 过程体中的非局部引用可以直接使用静态确定的地址 局部变量在栈顶的活动记录中，可以通过base_sp指针来访问 无须深入栈中取数据，无须访问链 过程可以作为参数来传递，也可以作为结果来返回,6.3.2 有过程嵌套的静态作用域 过程嵌套深度 sort1 rea

18、darray2 exchange2 quicksort2 partition3,6.3.2 有过程嵌套的静态作用域 过程嵌套深度 sort1 readarray2 exchange2 quicksort2 partition3 变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度,6.3 非局部名字的访问,寻找非局部名字存储单元的访问链,6.3 非局部名字的访问,假定过程p的嵌套深度为np，它引用嵌套深度为na的变量a，na np。如何访问a的存储单元？ sort1 readarray2 exchange2 quicksort2 partition3,6.3 非局部名字的访问,假定过

19、程p的嵌套深度为np，它引用嵌套深度为na的变量a，na np。如何访问a的存储单元？ 从栈顶的活动记录开始，追踪访问链np na次。,6.3 非局部名字的访问,假定过程p的嵌套深度为np，它引用嵌套深度为na的变量a，na np。如何访问a的存储单元？ 从栈顶的活动记录开始，追踪访问链np na次。 到达a的声明所在过程的活动记录。,6.3 非局部名字的访问,假定过程p的嵌套深度为np，它引用嵌套深度为na的变量a，na np。如何访问a的存储单元？ 从栈顶的活动记录开始，追踪访问链np na次。 到达a的声明所在过程的活动记录。 访问链的追踪用间接操作就可完成。,6.3 非局部名字的访问,

20、访问非局部名字的存储单元,sort readarray exchange quicksort partition,6.3 非局部名字的访问,过程p对变量a访问时，a的地址由下面的二元组表示： （np na，a在活动记录中的偏移）,6.3 非局部名字的访问,建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的 过程x np nx的情况 sort1 readarray2 exchange2 quicksort2 partition3,6.3 非局部名字的访问,建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的 过程x np nx的情况 x肯定就声明在p中,6.3 非局部名字的访问,建

21、立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的 过程x np nx的情况 x肯定就声明在p中 被调用过程的访问链必须指向调用过程的活动记录的访问链,6.3 非局部名字的访问,建立访问链,sort readarray exchange quicksort partition,6.3 非局部名字的访问,建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的 过程x np nx的情况 sort1 readarray2 exchange2 quicksort2 partition3,6.3 非局部名字的访问,建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的 过程x np nx的

22、情况 p和x的嵌套深度分别为1，2，nx 1的外围过程肯定相同,6.3 非局部名字的访问,建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的 过程x np nx的情况 p和x的嵌套深度分别为1，2，nx 1的外围过程肯定相同 追踪访问链np nx + 1次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录,6.3 非局部名字的访问,建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的 过程x np nx的情况 p和x的嵌套深度分别为1，2，nx 1的外围过程肯定相同 追踪访问链np nx + 1次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录 所到达的访问

23、链就是x的活动记录中的访问链应该指向的那个访问链,6.3 非局部名字的访问,建立访问链,sort readarray exchange quicksort partition,6.3 非局部名字的访问,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

24、 m := 0; b(f) end c; begin c end.,6.3 非局部名字的访问,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.,过程作为参数传递时，怎样在该过程被激活时

25、建立它的访问链。,6.3 非局部名字的访问,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的访问链,6

26、.3 非局部名字的访问,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.,6.3 非局部名字的访问,program ret (input, output);（过程作为返回值） var f: function (integer): integer; f

27、unction 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.,6.3 非局部名字的访问,program ret (input, output);（过程作为返回值） var f: f

28、unction (integer): integer; function 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.,6.3 非局部名字的访问,C语言的函数声明不能嵌套，函数不论

29、在什么情况下激活，要访问的数据分成两种情况: 非静态局部变量（包括形式参数），它们分配在活动记录栈顶的那个活动记录中 外部变量（包括定义在其它源文件中的外部变量）和静态的局部变量，它们都分配在静态数据区,6.3 非局部名字的访问,6.3.3 动态作用域 被调用过程的非局部名字a和它在调用过程中引用的是同样的存储单元。,6.3 非局部名字的访问,6.3.3 动态作用域 被调用过程的非局部名字a和它在调用过程中引用的是同样的存储单元。 新的绑定仅为被调用过程的局部名字建立，这些名字在被调用过程的活动记录中占用的存储单元。,6.3 非局部名字的访问,program dynamic(input, ou

30、tput); 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; show; small; writeln; show; small; writeln end.,6.3 非局部名字的访问,program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small

31、; var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.,6.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.2500.250 sh

32、ow; small; writeln;0.2500.250 show; small; writeln end.,6.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.250 0.125 show; small; writeln end.,6.3 非局部名字的访问,实现动态作用域的方法 深访问 用控制链搜索运行栈，寻找包含该非局部名字的第一个活动记录 浅访问 为每个名字在静态分配的存储空间中保存它的当前值 当过程p的新活动出现时，p的局部名字n使用在静态数据区分配给n的存储单元。n的先前值可以保存在p的活动记录中，当p的活动结束时再恢复,6.4 参 数 传 递,6.4.1 值调用 实参的右值传给被调用过程 值调用可以如下实现 把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中。,6.4 参 数 传 递,6.4.1 值调用 实参的右值传给被