第6章运行时存储空间的组织和管理ppt课件

1、第六章 运转时存储空间的组织和管理 术语过程的活动过程的一次执行称为过程的一次活动活动记录过程的活动需求可执行代码和存放所需信息的存储空间,后者称为活动记录本章内容讨论一个活动记录中的数据规划程序执行过程中，一切活动记录的组织方式 第六章 运转时存储空间的组织和管理 影响存储分配战略的言语特征 过程能否递归当控制从过程的活动前往时，部分变量的值能否要保管过程能否访问非部分变量过程调用的参数传送方式过程能否作为参数被传送过程能否作为结果值传送存储块能否在程序控制下动态地分配存储块能否必需显式地释放6.1 部分存储分配6.1.1 过程言语概念：过程定义、过程调用、方式参数、真实参数、活动的生存期6

2、.1 部分存储分配6.1.2 名字的作用域和绑定1、名字的作用域一个声明起作用的程序部分称为该声明的作用域即使一个名字在程序中只声明一次，该名字在程序运转时也能够表示不同的数据对象6.1 部分存储分配2、环境和形状环境把名字映射到左值，而形状把左值映射到右值即名字到值有两步映射赋值改动形状，但不改动环境 过程调用改动环境假设环境将名字x映射到存储单元s，那么说x被绑定到s名字存储单元形状值环境6.1 部分存储分配3、静态概念和动态概念的对应静 态 概 念 动 态 对 应 过程的定义 过程的活动 6.1 部分存储分配3、静态概念和动态概念的对应静 态 概 念 动 态 对 应 过程的定义 过程的活

3、动 名字的声明 名字的绑定 6.1 部分存储分配3、静态概念和动态概念的对应静 态 概 念 动 态 对 应 过程的定义 过程的活动 名字的声明 名字的绑定 声明的作用域 绑定的生存期 6.1 部分存储分配6.1.3 活动记录活动记录的常见规划返 回 值临 时 数 据参 数控 制 链访 问 链机 器 状 态局 部 数 据6.1 部分存储分配6.1.4 部分数据的规划字节是可编址内存的最小单位变量所需的存储空间可以根据其类型而静态确定一个过程所声明的部分变量，按这些变量声明时出现的次序，在部分数据域中依次分配空间部分数据的地址可以用相对于某个位置的地址来表示数据对象的存储规划还有一个对齐问题6.1

4、 部分存储分配例在SPARC/Solaris任务站上下面两个构造体的size分别是24和16，为什么不一样？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;charc2; long i;double f; double f;a; b;对齐：char : 1, long : 4, double : 86.1 部分存储分配例在SPARC/Solaris任务站上下面两个构造体的size分别是24和16，为什么不一样？typedef struct _atypedef struct _bchar c1;0 char c

5、1;0long i;4 char c2; 1charc2;8 long i; 4double f;16 double f; 8a; b;对齐：char : 1, long : 4, double : 86.1 部分存储分配例在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;对齐：char : 1, long : 4, doub

6、le : 46.1 部分存储分配6.1.5 程序块本身含有部分变量声明的语句可以嵌套最接近的嵌套作用域规那么并列程序块不会同时活泼并列程序块的变量可以重叠分配6.1 部分存储分配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 /声 明 作 用 域 int a = 0; B0 B2

7、 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1a2, b3重叠分配存储单元 6.2 全局栈式存储分配本节引见引见程序运转时所需的各个活动记录在存储空间的分配战略描画过程的目的代码怎样访问绑定到部分名字的存储单元引见三种分配战略静态分配战略栈式分配战略堆式分配战略6.2 全局栈式存储分配6.2.1 运转时内存的划分代 码静 态 数 据堆栈6.2 全局栈式存储分配1、静态分配名字在程序被编译时绑定到存储单元，不需求运转时的任何支持绑定的生存期是程序的整个运转期间6.2 全局栈式存储分配2、静态分配给言语带来限制

8、递归过程不被允许数据对象的长度和它在内存中位置的限制，必需是在编译时可以知道的数据构造不能动态建立6.2 全局栈式存储分配例C程序的外部变量、静态部分变量以及程序中出现的常量都可以静态分配声明在函数外面外部变量 静态分配静态外部变量 静态分配声明在函数里面静态部分变量 也是静态分配自动变量 不能静态分配6.2 全局栈式存储分配6.2.2 活动树和运转栈1、活动树用树来描画控制进入和分开活动的方式mq(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)6.2

9、 全局栈式存储分配活动树的特点每个结点代表某过程的一个活动根结点代表主程序的活动结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动结点a处于结点b的左边，当且仅当a的生存期先于b的生存期6.2 全局栈式存储分配当前活泼着的过程活动可以保管在一个栈中例 控制栈的内容：m, q (1, 9), q (1, 3), q (2, 3) mq(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)6.2 全局栈式存储分配2、运转栈：把控制栈中的信息拓广到包括过

10、程活动所需的一切部分信息即活动记录 6.2 全局栈式存储分配2、运转栈：把控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 ma : arraym6.2 全局栈式存储分配2、运转栈：把控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 mi: integerra : arraymr6.2 全局栈式存储分配2、运转栈：把控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 mk: integerq (1, 9)a : arraymq(1,9)r6.2 全局栈式存储分配2、运转栈：把控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 mk: integerq

11、 (1, 9)a : arrayq (1, 3)k: integermq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)6.2 全局栈式存储分配6.2.3 调用序列过程调用和过程前往都需求执行一些代码来管理活动记录栈，保管或恢复机器形状等过程调用序列过程调用时执行的分配活动记录，把信息填入它的域中的代码过程前往序列过程前往时执行的恢复机器形状，释放活动记录，使调用过程可以继续执行的代码调用序列和前往序列经常都分成两部分，分处于调用过程和被调用过程中6.2 全局栈式存储分配即使是同一种言语，过程调用序列、前往序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原

12、那么以活动记录中间的某个位置作为基地址长度能较早确定的域放在活动记录的中间返 回 值临 时 数 据参 数控 制 链访 问 链机 器 状 态局 部 数 据6.2 全局栈式存储分配即使是同一种言语，过程调用序列、前往序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原那么普通把暂时数据域放在部分数据域的后面把参数域和能够有的前往值域放在紧靠调用者活动记录的地方返 回 值临 时 数 据参 数控 制 链访 问 链机 器 状 态局 部 数 据6.2 全局栈式存储分配即使是同一种言语，过程调用序列、前往序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原那么

13、用同样的代码来执行各个活动的保管和恢复返 回 值临 时 数 据参 数控 制 链访 问 链机 器 状 态局 部 数 据6.2 全局栈式存储分配1、过程p调用过程q的调用序列前往值和参数top_sp base_sp 暂时数据部分数据控制链 和保管的机器形状 6.2 全局栈式存储分配1、过程p调用过程q的调用序列(1) p计算实参，依次放入栈顶，并在栈顶留出放前往值的空间。top_sp的值在此过程中被改动前往值和参数top_sp base_sp 暂时数据部分数据控制链 和保管的机器形状 前往值和参数6.2 全局栈式存储分配1、过程p调用过程q的调用序列(2) p把前往地址和当前base_sp的值存入

14、q的活动记录中，建立q的访问链，添加base_sp的值前往值和参数top_sp base_sp 暂时数据部分数据控制链 和保管的机器形状 前往值和参数控制链和前往地址6.2 全局栈式存储分配1、过程p调用过程q的调用序列(3) q保管存放器的值和其它机器形状信息前往值和参数top_sp base_sp 暂时数据部分数据控制链 和保管的机器形状 前往值和参数控制链 和保管的机器形状6.2 全局栈式存储分配1、过程p调用过程q的调用序列(4) q根据部分数据域和暂时数据域的大小添加top_sp的值，初始化它的部分数据，并开场执行过程体暂时数据部分数据前往值和参数前往值和参数 控制链 和保管的机器形

15、状top_sp base_sp 暂时数据部分数据控制链 和保管的机器形状 6.2 全局栈式存储分配调用者p和被调用者q之间的义务划分被调用者q的责任调用者p的责任调用者p的活动记录被调用者q的活动记录暂时数据部分数据前往值和参数前往值和参数 控制链 和保管的机器形状top_sp base_sp 栈增长方向暂时数据部分数据控制链 和保管的机器形状 6.2 全局栈式存储分配2、过程p调用过程q的前往序列暂时数据部分数据前往值和参数前往值和参数 控制链 和保管的机器形状top_sp base_sp 栈增长方向暂时数据部分数据控制链 和保管的机器形状 6.2 全局栈式存储分配2、过程p调用过程q的前往

16、序列暂时数据部分数据前往值和参数前往值和参数 控制链 和保管的机器形状top_sp base_sp 栈增长方向暂时数据部分数据控制链 和保管的机器形状 (1) q把前往值置入临近p的活动记录的地方 参数个数可变场所难以确定存放前往值的位置，因此通常用存放器传送前往值6.2 全局栈式存储分配2、过程p调用过程q的前往序列(2) q对应调用序列的步骤(4)，减小top_sp的值前往值和参数top_sp base_sp 暂时数据部分数据控制链 和保管的机器形状 前往值和参数控制链 和保管的机器形状6.2 全局栈式存储分配2、过程p调用过程q的前往序列(3) q恢复存放器(包括base_sp)和机器形

17、状，前往p前往值和参数top_sp base_sp 暂时数据部分数据控制链 和保管的机器形状 前往值和参数6.2 全局栈式存储分配2、过程p调用过程q的前往序列前往值和参数top_sp base_sp 暂时数据部分数据控制链 和保管的机器形状 (4) p根据参数个数与类型和前往值类型调整top_sp，然后取出前往值6.2 全局栈式存储分配3、过程的参数个数可变的情况暂时数据部分数据参 数参 数 控制链 和保管的机器形状top_sp base_sp 栈增长方向暂时数据部分数据控制链 和保管的机器形状 (1) 函数前往值改成用存放器传送6.2 全局栈式存储分配3、过程的参数个数可变的情况暂时数据部

18、分数据参数1, , 参数n参数1, ,参数m 控制链 和保管的机器形状top_sp base_sp 栈增长方向暂时数据部分数据控制链 和保管的机器形状 (2) 编译器产生将实参表达式逆序计算并将结果进栈的代码 自上而下依次是参数1, , 参数n6.2 全局栈式存储分配3、过程的参数个数可变的情况暂时数据部分数据参数1, , 参数n参数1, ,参数m 控制链 和保管的机器形状top_sp base_sp 栈增长方向暂时数据部分数据控制链 和保管的机器形状 (3) 被调用函数能准确地知道第一个参数的位置6.2 全局栈式存储分配3、过程的参数个数可变的情况暂时数据部分数据参数1, , 参数n参数1,

19、 ,参数m 控制链 和保管的机器形状top_sp base_sp 栈增长方向暂时数据部分数据控制链 和保管的机器形状 (4) 被调用函数根据第一个参数到栈中取第二、第三个参数等等6.2 全局栈式存储分配6.2.4 栈上可变长数据活动记录的长度在编译时不能确定的情况例：部分数组的大小要等到过程激活时才干确定备注： Java言语的实现是将它们分配在堆上6.2 全局栈式存储分配访问动态分配的数组控制链数组A的指针数组B的指针top_sp base_sp . . . . . . .栈(1) 编译时，在活动记录中为这样的数组分别存放数组指针的单元6.2 全局栈式存储分配访问动态分配的数组(2) 运转时，

20、这些指针指向分配在栈顶的存储空间控制链数组A的指针数组B的指针top_sp base_sp . . . . . . .栈数组A数组B6.2 全局栈式存储分配访问动态分配的数组(3) 运转时，对数组A和B的访问都要经过相应指针来间接访问控制链数组A的指针数组B的指针top_sp base_sp . . . . . . .栈数组A数组B6.2 全局栈式存储分配访问动态分配的数组q的数组q的活动记录p的数组p的活动记录控制链top_sp base_sp 数组A的指针数组B的指针数组A数组B控制链. . . . . . .栈6.2 全局栈式存储分配6.2.5 悬空援用悬空援用：援用某个已被释放的存储单

21、元6.2 全局栈式存储分配6.2.5 悬空援用悬空援用：援用某个已被释放的存储单元main()|int dangle ( ) |int q;|int j = 20; q = dangle ( );|return &j;|6.3 非部分名字的访问本节引见无过程嵌套的静态作用域C言语有过程嵌套的静态作用域Pascal言语动态作用域Lisp言语6.3 非部分名字的访问6.3.1 无过程嵌套的静态作用域过程体中的非部分援用可以直接运用静态确定的地址部分变量在栈顶的活动记录中，可以经过base_sp指针来访问无须深化栈中取数据，无须访问链过程可以作为参数来传送，也可以作为结果来前往6.3 非部分名字的访

22、问6.3.2 有过程嵌套的静态作用域sortreadarrayexchangequicksortpartition6.3 非部分名字的访问6.3.2 有过程嵌套的静态作用域过程嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度6.3 非部分名字的访问访问链用来寻觅非部分名字的存储单元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访问

23、链e (1, 3)访问链sa, xq (1, 3)k, v访问链q (1, 9)k, v访问链p (1, 3)i, j访问链6.3 非部分名字的访问访问非部分名字的存储单元 假定过程p的嵌套深度为np，它援用嵌套深度为na的变量a，na np。如何访问a的存储单元sort1readarray2exchange2quicksort2partition36.3 非部分名字的访问访问非部分名字的存储单元 假定过程p的嵌套深度为np，它援用嵌套深度为na的变量a，na np。如何访问a的存储单元从栈顶的活动记录开场，追踪访问链np na次到达a的声明所在过程的活动记录访问链的追踪用间接操作就可完成so

24、rt1readarray2exchange2quicksort2partition36.3 非部分名字的访问访问非部分名字的存储单元 sort readarray exchange quicksort partitionsa, 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访问链6.3 非部分名字的访问过程p对变量a访问时，a

25、的地址由下面的二元组表示：np na，a在活动记录中的偏移6.3 非部分名字的访问建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程x(1) np nx的情况sort1readarray2exchange2quicksort2partition3 这时x一定就声明在p中6.3 非部分名字的访问建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程x(1) np nx的情况被调用过程的访问链必需指向调用过程的活动记录的访问链6.3 非部分名字的访问访问非部分名字的存储单元 sort readarray exchange quicksort partitionsa, xq (1,

26、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访问链6.3 非部分名字的访问建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程x(2) np nx的情况sort1readarray2exchange2quicksort2partition3 这时p和x的嵌套深度分别为1，2，nx 1的外围过程一定一样6.3 非部分名字的访问建立访

27、问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程x(2) np nx的情况追踪访问链np nx + 1次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录所到达的活动记录就是x的活动记录中的访问链应该指向的那个活动记录6.3 非部分名字的访问访问非部分名字的存储单元 sort readarray exchange quicksort partitionsa, 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)访问

28、链sa, xq (1, 3)k, v访问链q (1, 9)k, v访问链p (1, 3)i, j访问链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 cend.过程作为参数传送时，

29、怎样在该过程被激活时建立它的访问链 从b的访问链难以建立f的访问链6.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 cend.访 问 链访 问 链paramcmb f的起始地址连同它的访问链一同传送6.3 非部分名字的访问program ret (

30、input, output);过程作为前往值 var f: function (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.ar

31、etbaddm 执行addm时，a的活动记录已不存在，取不到m的值6.3 非部分名字的访问C言语的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况非静态部分变量包括方式参数，它们分配在活动记录栈顶的那个活动记录中外部变量包括定义在其它源文件之中的外部变量和静态的部分变量，它们都分配在静态数据区6.3 非部分名字的访问6.3.3 动态作用域被调用过程的非部分名字a和它在调用过程中援用的是同样的存储单元新的绑定仅为被调用过程的部分名字建立，这些名字在被调用过程的活动记录中占用的存储单元6.3 非部分名字的访问program dynamic(input, output); var

32、 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.dynamicshowsmallsmallshowshowshow6.3 非部分名字的访问program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3)

33、 end; procedure small; var r: real; begin r := 0.125; show end; begin静态作用域 r := 0.25;0.2500.250 show; small; writeln;0.2500.250 show; small; writeln end.dynamicshowsmallsmallshowshowshow6.3 非部分名字的访问program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small

34、; 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.dynamicshowsmallsmallshowshowshow6.3 非部分名字的访问实现动态作用域的方法深访问用控制链搜索运转栈，寻觅包含该非部分名字的第一个活动记录浅访问为每个名字在静态分配的存储空间中保管它的当前值当过程p的新活动出现时，p的部分名字n运用在静态数据区分配给n的存储单元。n的先前值保管在p的活动记录中，当

35、p的活动终了时再恢复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; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow?r 静态区运用值的地方 栈区暂存值的地方dyn

36、amicr?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; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr? 静态区运用值的地方 栈区暂

37、存值的地方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; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr?show 静态区运用值的地方

38、栈区暂存值的地方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; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr?smallr0.25 静

39、态区运用值的地方 栈区暂存值的地方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; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.125rdynamicr?smallr0.25 静态区运用值的地方 栈区暂存值的地方6.3 非部分名字的访问program dynamic(input, out