《目标程序运行时的存储组织》由会员分享，可在线阅读，更多相关《目标程序运行时的存储组织（20页珍藏版）》请在金锄头文库上搜索。
1、第10章 目标程序运行时的组织n教学要求：本章介绍目标程序运行时的 存储组织方式，包括静态存储分配和动 态存储分配。 要求掌握各种存储组织形 式的基本方法。n教学重点：静态分配策略和动态分配策 略基本思想，嵌套过程语言栈式分配， 活动记录、运行时栈的组织。 10.1 概述目标代码区静态数据区Stackheap1 1、存储组织：编译程序对目标程序运行时的组织、存储组织：编译程序对目标程序运行时的组织 （运行环境和分配存储）。如通常存储区布局可为（运行环境和分配存储）。如通常存储区布局可为 ： 静态数据区用于存放一对一的绑定且 编译时就可确定存储空间大小的数据栈用于存放一对多的绑定且与活动同 生存
2、期的数据堆用于存放与活动生存期不一致且可 以动态生成和撤消的数据三种数据区对应着下述三种不同的分配策略2 2、存储分配策略：、存储分配策略：（1 1）静态存储分配）静态存储分配在编译阶段对源程序中在编译阶段对源程序中 的量分配固定单元，运行时始终不变。的量分配固定单元，运行时始终不变。注：注：1 1、程序结构特点：不允许递归调用，而且、程序结构特点：不允许递归调用，而且 不含有可变数组。（如不含有可变数组。（如FORTRANFORTRAN语言）。语言）。2 2、基本策略、基本策略: :在编译时，根据各类数据所需在编译时，根据各类数据所需 的存储空间大小以及存储方式规定，在符号表的存储空间大小以
3、及存储方式规定，在符号表 中建立中建立“名字名字- -地址地址”对应关系，然后根据这对应关系，然后根据这 些对应关系进行变量名的地址分配。些对应关系进行变量名的地址分配。（2 2）动态存储分配）动态存储分配在运行阶段动态地为源程在运行阶段动态地为源程 序中的量分配存储空间。（栈式、堆式）序中的量分配存储空间。（栈式、堆式）注：注：1)1)若某程序设计语言允许过程递归调用，而且若某程序设计语言允许过程递归调用，而且 允许使用可变数组，那么在编译时就不可能完全为允许使用可变数组，那么在编译时就不可能完全为 其数据项目分配存储单元，必须采取动态存储分配其数据项目分配存储单元，必须采取动态存储分配 策
4、略。策略。2)2)动态分配数据单元时一般使用栈，即栈式存动态分配数据单元时一般使用栈，即栈式存 储管理。储管理。栈式栈式: : 简单的栈式分配方案简单的栈式分配方案嵌套过程的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储分配方案分程序结构的存储分配方案3 3、过程活动：一个过程的活动指的是该过程的一次执行。、过程活动：一个过程的活动指的是该过程的一次执行。4 4、活动记录：一个过程的一次执行所需要的信息使用一个连、活动记录：一个过程的一次执行所需要的信息使用一个连 续的存储区来管理，这个区（块）叫做一个活动记录。续的存储区来管理，这个区（块）叫做一个活动记录。活动记录一般包含：活动记录一般
5、包含：（1 1）连接数据）连接数据返回地址返回地址调用过程指令的下一条指令的地址。调用过程指令的下一条指令的地址。动态链（控制链）动态链（控制链）指向指向调用调用该过程活动记录地址的指针。该过程活动记录地址的指针。用用 于当调用返回时，将当前栈顶正确切换到调用者的活动记录于当调用返回时，将当前栈顶正确切换到调用者的活动记录静态链（存取链）静态链（存取链）指向指向定义定义该过程的直接外过程（或主程序该过程的直接外过程（或主程序 ）运行时最新活动记录地址的指针）运行时最新活动记录地址的指针. .用来访问非局部数据用来访问非局部数据( (可选可选 ) )。（2 2）形式单元）形式单元存放相应实参的地
6、址或值。存放相应实参的地址或值。（3 3）局部数据）局部数据局部变量、内情向量、临时工作单元。局部变量、内情向量、临时工作单元。临时单元临时单元内情向量内情向量局部变量局部变量形式单元形式单元静态链静态链动态链动态链返回地址返回地址SPSPTOPTOP连接数据连接数据( (控制信息控制信息) )SPSP为为当前活动记录的起始位置。当前活动记录的起始位置。 TOPTOP为栈顶单元。为栈顶单元。分别放在两个寄分别放在两个寄 存器中。存器中。访问信息访问信息10.2 10.2 栈式存储分配的实现栈式存储分配的实现一、简单的栈式存储分配的实现一、简单的栈式存储分配的实现n n程序结构特点：没有分程序结
7、构，过程定义不程序结构特点：没有分程序结构，过程定义不 嵌套，过程可递归调用。嵌套，过程可递归调用。n n简单栈式分配方案：把存储区组织成一个栈，简单栈式分配方案：把存储区组织成一个栈， 运行时每进入一个过程，就把它的活动记录压运行时每进入一个过程，就把它的活动记录压 入栈，形成过程工作时的临时数据区，该过程入栈，形成过程工作时的临时数据区，该过程 结束时取消该数据区。结束时取消该数据区。 例: main全局变量的说明；proc R；end R;proc Q； end Q;主程序执行语句 end mainmainQRQ的活动记录 主程序全局 数据区 Q的活动记录TOPR的活动记录SPQ的活动记
8、录主程序全局 数据区mainQQR的数组区R的活动记录Q的活动记录主程序全局数据区分配了数组区之后的运行栈TOPSP二、嵌套过程语言的栈式分配的实现二、嵌套过程语言的栈式分配的实现 1 1、程序结构特点：语言的定义允许嵌套，一个、程序结构特点：语言的定义允许嵌套，一个 过程可以引用包围它的任一外层过程所定义过程可以引用包围它的任一外层过程所定义 的标识符（如变量，数组或过程等）（如的标识符（如变量，数组或过程等）（如 PASCALPASCAL语言）语言） 。n n如何才能引用外层数据？如何才能引用外层数据？2 2、关键：设法跟踪每个外层过程的最新活动记、关键：设法跟踪每个外层过程的最新活动记
9、录录ARAR的位置。的位置。n n跟踪办法：跟踪办法：（1 1） 用静态链。用静态链。（2 2） 用用DISPLAYDISPLAY表。表。（1 1） 用静态链用静态链n n在在过程活动记录中增设静态链，指向包含该过过程活动记录中增设静态链，指向包含该过 程的程的直接外层直接外层过程的最新活动记录的起始位置过程的最新活动记录的起始位置 。见。见P223-224P223-224mainp1p2p3p4 main过 程 定 义 的 嵌 套执 行 顺 序 p2p4p3p3 main活动记录p3活动记录 存取链（静态链） 控制链（动态链）p3活动记录 存取链（静态链） 控制链（动态链）p4活动记录 存取
10、链（静态链） 控制链（动态链）p2活动记录 存取链（静态链） 控制链（动态链）2 2、用、用DisplayDisplay表表DisplayDisplay表表-嵌套层次显示表嵌套层次显示表当前激活过程的层次为当前激活过程的层次为K K，它的它的DisplayDisplay表含有表含有K+1K+1个单元，依次存放着现行层，直接外层个单元，依次存放着现行层，直接外层直至最外层直至最外层的每一过程的最新活动记录的基地址。的每一过程的最新活动记录的基地址。说明：说明：1 1、由于过程的层数可以静态确定，因此每个过程、由于过程的层数可以静态确定，因此每个过程的的DisplayDisplay表的体积在编译时
11、即可以确定。表的体积在编译时即可以确定。2 2、某过程、某过程p p是在层次为是在层次为i i的过程的过程q q内内定义定义的，并且的，并且q q是包围是包围p p的直接外层，那么的直接外层，那么p p的过程层数为的过程层数为i+1i+1。例： program main(i,0); 程序结构图proc R(c,d); Rend /*R*/proc P (a); 主proc Q (b); P Q call RR(x,y);end /*Q*/ call QQ(z); call Pend /*P*/ call RP（W）；R（U，V）； end /*main*/用Display表的方案(1)主程序-
12、(2)P-(3)Q-(4)R主程序的 活动记录d0spdisplaytop（1）P的 活动记录 主程序的 活动记录d1d0displaysptop（2）用Display表的方案(1)主程序-(2)P-(3)Q- (4)RQ的 活动记录P的 活动记录 主程序的 活动记录display d2 d1 d0sptop（3）R的 活动记录 Q的 活动记录P的 活动记录 主程序的 活动记录d1 d0displaytopsp（4）DISPLAYDISPLAY表的维护和建立表的维护和建立n n为便于组织存储区，将为便于组织存储区，将displaydisplay作为活动记录的作为活动记录的 一部分，其相对地址在
13、编译时是完全可以确定的一部分，其相对地址在编译时是完全可以确定的 。n n假设过程假设过程P1P1可调用可调用P2P2，为了能在，为了能在P2P2中建立中建立P2P2的的 displaydisplay，在在P1P1调用调用P2P2时设法把时设法把P1P1的的displaydisplay地址地址 作为连接数据之一（全局作为连接数据之一（全局displaydisplay地址）传送给地址）传送给 P2P2，因此连接数据包括：，因此连接数据包括：老老SPSP值（动态链）值（动态链）返回地址返回地址全局全局displaydisplay地址地址n d DISPLAY4 形式单元3 参数个数2 全局DISP
14、LAY地址1 返回地址0 老SP 当过程的层次为当过程的层次为n n， 它的它的displaydisplay为为n+1n+1个值个值 。 一个过程被调用时，一个过程被调用时， 从调用过程的从调用过程的DISPLAYDISPLAY 表中自下向上抄录表中自下向上抄录n n个个 SPSP值，再加上本层的值，再加上本层的SPSP 值。值。10.3 10.3 堆式存储分配堆式存储分配堆：通常是一片连续的足够大的存储区，当需要 时，就从堆中分配一小块存储区；用完就及时退 还给堆。注：在高级语言中有些数据存储空间的请求与释 放不再遵循后进先出的原则，而且是全局性的。 为此，需要让运行程序持有一块专用的全局存储 空间来满足这些数据的存储要求。这种存储空间 就是堆。作业 (1)对以下的Pascal程序画出过程C第二次被调用时的运 行栈，控制链和存取链. (2)如果把存取链改成DISPLAY，重新做(1) program env;procedure A;var x :integer;procedure B;procedure C;begin x:=2; B end; (c过程)begin C end; (B过程)begin B end ; (A过程)begin A end; (main)
