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

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

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

3、如变量，与之结合的是一个存储单元； 也可以是操作对象，如过程，与之结合的是可执行的代码。我们的讨论仅限于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 of B2 / int a = 2; / end of

7、 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 /声 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1;

8、B1 B3 int a = 2;B2int b = 3; B3 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 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1

9、a2, b3重叠分配存储单元 6.2 全局存储分配战略引见程序运转时所需的各个活动记录在存储空间的分配战略6.2 全局存储分配战略引见程序运转时所需的各个活动记录在存储空间的分配战略描画过程的目的代码怎样访问绑定到部分名字的存储单元6.2 全局存储分配战略引见程序运转时所需的各个活动记录在存储空间的分配战略描画过程的目的代码怎样访问绑定到部分名字的存储单元引见三种分配战略静态分配战略6.2 全局存储分配战略引见程序运转时所需的各个活动记录在存储空间的分配战略描画过程的目的代码怎样访问绑定到部分名字的存储单元引见三种分配战略静态分配战略栈式分配战略6.2 全局存储分配战略引见程序运转时所需的各个

10、活动记录在存储空间的分配战略描画过程的目的代码怎样访问绑定到部分名字的存储单元引见三种分配战略静态分配战略栈式分配战略堆式分配战略 静态分配战略在编译是对一切对象分配固定的存储单元。且在运转是坚持不变。 栈式动态分配战略在运转时把存储器作为一个栈进展管理，运转时，每当调用一个过程，它所需求的存储空间就动态的分配于栈顶，一旦退出，它所占空间就予以释放。 堆式动态存储战略在运转时把存储器组织成堆构造，以便用户关于存储空间的恳求与归还回收，凡恳求者分给一块，凡释放者退回给堆。6.2.1 运转时内存的划分代 码静 态 数 据栈堆6.2.2 静态存储分配 假设在编译时就可以确定一个程序在运转时所需求的存

11、储空间的大小，那么在编译时就可以安排好目的程序运转时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种分配方法叫做静态分配。 特点：绑定是1对1的映射。名字在程序编译时与存储空间结合，每次过程活动时，它的名字映射到同一存储单元。程序运转时不再有对存储空间的分配。 静态分配的限制： 数据对象的大小和它在内存中位置的限制必需在编译时确定，如数组的大小不能是动态的； 不允许程序递归，由于一个过程的一切活动运用同样的名字绑定，即绑定是一对一的； 不能动态生成或吊销数据，由于运转时没有存储分配机制。完全采用静态分配的言语：早期的FORTRAN。允许分别编译的数据定义模块如全程援用的数据，也可以

12、采用静态分配，由于它们普通在整个程序运转的期间是被共享的。 6.2.3 栈式存储分配 存储空间被组织成栈，活动记录的推入和弹出分别对应于活动的开场和终了。 与静态分配不同的是，在每次活动中把部分名字和新的存储单元绑定，在活动终了时，活动记录从栈中弹出，因此部分名字的存储空间也随之消逝。6.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)活动树的特点：每个结点代表某过程的一个活动根结点代表主

13、程序的活动结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动结点a处于结点b的左边，当且仅当a的生存期先于b的生存期活动树上各节点之间具有下述关系：同一层次的活动生存期不交；任一时辰，处在生存期的活动构成一条从根到某节 点的途径；途径上各节点生存期是嵌套的后进先出。 当前活泼着的过程活动可以保管在一个栈中控制栈的内容：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)运转栈：把

14、控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 运转栈：把控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 sa : arrays运转栈：把控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 si: integerra : arraysr运转栈：把控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 sk: integerq (1, 9)a : arraysq(1,9)r运转栈：把控制栈中的信息拓广到包括过程活动所需的一切部分信息即活动记录 sk: integerq (1, 9)a : arrayq (1, 3)k: integersq(1,9)rp

15、(1,9)q(1,3)q(1,0)p(1,3)过程调用和过程前往都需求执行一些代码来管理活动记录栈，保管或恢复机器形状等过程调用和过程前往都需求执行一些代码来管理活动记录栈，保管或恢复机器形状等过程调用序列过程调用时执行的分配活动记录，把信息填入它的域中的代码过程调用和过程前往都需求执行一些代码来管理活动记录栈，保管或恢复机器形状等过程调用序列过程调用时执行的分配活动记录，把信息填入它的域中的代码过程前往序列过程前往时执行的恢复机器形状，释放活动记录，使调用过程可以继续执行的代码过程调用和过程前往都需求执行一些代码来管理活动记录栈，保管或恢复机器形状等过程调用序列过程调用时执行的分配活动记录，

16、把信息填入它的域中的代码过程前往序列过程前往时执行的恢复机器形状，释放活动记录，使调用过程可以继续执行的代码调用序列和前往序列经常都分成两部分，分处于调用过程和被调用过程中调用者和被调用者之间的义务划分前往值和参数控制链访问链和机器形状部分数据暂时数据前往值和参数部分数据暂时数据 控制链访问链和机器形状top_sp base_sp 被调用者的责任调用者的责任被调用者的活动记录调用者的活动记录栈过程p调用过程q的调用序列p计算实参，依次放入栈顶，并在栈顶留出放前往值的空间。top_sp的值在此过程中被改动p把前往地址和当前base_sp的值存入q的活动记录中，建立q的访问链，添加base_sp的

17、值q保管存放器的值和其它机器形状信息q根据部分数据域和暂时数据域的大小添加top_sp的值，初始化它的部分数据，并开场执行过程体调用者和被调用者之间的义务划分前往值和参数控制链访问链和机器形状部分数据暂时数据前往值和参数部分数据暂时数据 控制链访问链和机器形状top_sp base_sp 被调用者的责任调用者的责任被调用者的活动记录调用者的活动记录栈过程p调用过程q的前往序列q把前往值置入临近p的活动记录的地方q对应调用序列的步骤4，减小top_sp的值 q恢复存放器包括base_sp和机器形状，前往pp根据参数个数与类型和前往值类型调整top_sp，然后取出前往值调用者和被调用者之间的义务划

18、分前往值和参数控制链访问链和机器形状部分数据暂时数据前往值和参数部分数据暂时数据 控制链访问链和机器形状top_sp base_sp 被调用者的责任调用者的责任被调用者的活动记录调用者的活动记录栈过程的参数个数可变的情况函数前往值改成用存放器传送编译器产生将这些参数逆序进栈的代码被调用函数能准确地知道第一个参数的位置被调用函数根据第一个参数到栈中取第二、第三个参数等等调用者和被调用者之间的义务划分前往值和参数控制链访问链和机器形状部分数据暂时数据前往值和参数部分数据暂时数据 控制链访问链和机器形状top_sp base_sp 被调用者的责任调用者的责任被调用者的活动记录调用者的活动记录栈活动记

19、录的长度在编译时不能确定的情况部分数组的大小要等到过程激活时才干确定在活动记录中为这样的数组分别存放数组指针的单元运转时，这些指针指向分配在栈顶的存储空间访问动态分配的数组q的数组q的活动记录p的数组控制链top_sp base_sp p的活动记录数组A的指针数组B的指针数组A数组B控制链悬空援用：援用某个已被释放的存储单元悬空援用：援用某个已被释放的存储单元main()|int dangle ( ) |int q;|int j = 20; q = dangle ( );|return &j;|6.3.3 堆式存储分配 1部分名的值在活动终了时必需被保管。 2. 被调用者的活动生存期超越调用者

20、。 用活动树不可以正确描画这种言语的过 程之间的控制流。 new(p); dispose(p);6.3 非部分名字的访问本节引见无过程嵌套的静态作用域C言语有过程嵌套的静态作用域Pascal言语动态作用域Lisp言语6.3.1 无过程嵌套的静态作用域过程体中的非部分援用可以直接运用静态确定的地址部分变量在栈顶的活动记录中，可以经过base_sp指针来访问无须深化栈中取数据，无须访问链过程可以作为参数来传送，也可以作为结果来前往6.3.2 有过程嵌套的静态作用域过程嵌套深度sort1readarray2exchange2quicksort2partition36.3.2 有过程嵌套的静态作用域过

21、程嵌套深度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访问链e (1, 3)访问链sa, xq (1, 3)k, v访问链q (1, 9)k, v访问链p (1, 3)i, j访问链6.3 非部分名字的访问假定过程p的嵌套深度为np，

22、它援用嵌套深度为na的变量a，na np。如何访问a的存储单元？sort1readarray2exchange2quicksort2partition36.3 非部分名字的访问假定过程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

23、。如何访问a的存储单元？从栈顶的活动记录开场，追踪访问链np na次。到达a的声明所在过程的活动记录。访问链的追踪用间接操作就可完成。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访问链e (1, 3)访问链sa, xq (1, 3)k, v访问链q (1, 9)k, v访问链p (1, 3)i, j访问链sort readarray exchange quicksort partitio

24、n6.3 非部分名字的访问过程p对变量a访问时，a的地址由下面的二元组表示：np na，a在活动记录中的偏移6.3 非部分名字的访问建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp nx的情况sort1readarray2exchange2quicksort2partition36.3 非部分名字的访问建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp nx的情况x一定就声明在p中6.3 非部分名字的访问建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp nx的情况x一定就声明在p中被调用过程的访问链必需指向调用过程的活动记录的访问链6.3 非

25、部分名字的访问建立访问链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访问链sort readarray exchange quicksort partition6.3 非部分名字的访问建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp nx的情况sort1readarray2exchange2quic

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

27、访问链np nx + 1次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录所到达的访问链就是x的活动记录中的访问链应该指向的那个访问链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访问链e (1, 3)访问链sa, xq (1, 3)k, v访问链q (1, 9)k, v访问链p (1, 3)i, j访问链sort readarray exchange quicksort partition6

28、.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.6.3 非部分名字的访问program param(input, output);过程作为参数procedure b(fun

29、ction 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.过程作为参数传送时，怎样在该过程被激活时建立它的访问链。6.3 非部分名字的访问program param(input, output);过程作为参数procedure b(function h(n: integer): integer); be

30、gin 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的访问链6.3 非部分名字的访问program param(input, output);过程作为参数procedure b(function h( begin writeln(h(2) end ;procedure c; var m

31、: integer; function f(n: integer) begin f := m+n end f; begin m := 0; b(f) end c; begin cend.访 问 链访 问 链paramcmb 6.3 非部分名字的访问program ret (input, output);过程作为前往值 var f: function (integer): integer;function a: function (integer): integer; var m: integer; function addm (n: integer): integer; begin retur

32、n 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: function (integer): integer;function a: function (integer): integer; var m: integer; function addm (n: intege

33、r): 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.retabaddm6.3 非部分名字的访问C言语的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况:非静态部分变量包括方式参数，它们分配在活动记录栈顶的那个活动记录中外部变量包括定义在其它源文件中的外部变量和静态的部分变量，它们都分配在静态数据区 6.3 非部

34、分名字的访问6.3.3 动态作用域被调用过程的非部分名字a和它在调用过程中援用的是同样的存储单元。6.3 非部分名字的访问6.3.3 动态作用域被调用过程的非部分名字a和它在调用过程中援用的是同样的存储单元。新的绑定仅为被调用过程的部分名字建立，这些名字在被调用过程的活动记录中占用的存储单元。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 e

35、nd; 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; show; small; writeln; show; small; writeln end.dynamicshow

36、smallsmallshowshowshow6.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 show; small; writeln;0.2500.250 show; small; writeln end.dynamicshowsmallsmallshowshowsho

37、w6.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.dynamicshowsmallsmallshowshowshow6.3 非部分名字的访问实现动态作用域的方法深访问用控制链搜索运转栈，寻觅包含该非部分名字的第一个活动记录浅访问为每个