目标程序运行时的存储组织.ppt

第10章目标程序运行时的组织,教学要求：本章介绍目标程序运行时的存储组织方式，包括静态存储分配和动态存储分配。要求掌握各种存储组织形式的基本方法。教学重点：静态分配策略和动态分配策略基本思想，嵌套过程语言栈式分配，活动记录、运行时栈的组织。,10.1概述,1、存储组织：编译程序对目标程序运行时的组织（运行环境和分配存储）。如通常存储区布局可为：,静态数据区用于存放一对一的绑定且编译时就可确定存储空间大小的数据,栈用于存放一对多的绑定且与活动同生存期的数据,堆用于存放与活动生存期不一致且可以动态生成和撤消的数据,三种数据区对应着下述三种不同的分配策略,2、存储分配策略：（1）静态存储分配在编译阶段对源程序中的量分配固定单元，运行时始终不变。注：1、程序结构特点：不允许递归调用，而且不含有可变数组。（如FORTRAN语言）。2、基本策略:在编译时，根据各类数据所需的存储空间大小以及存储方式规定，在符号表中建立“名字-地址”对应关系，然后根据这些对应关系进行变量名的地址分配。,（2）动态存储分配在运行阶段动态地为源程序中的量分配存储空间。（栈式、堆式）注：1)若某程序设计语言允许过程递归调用，而且允许使用可变数组，那么在编译时就不可能完全为其数据项目分配存储单元，必须采取动态存储分配策略。2)动态分配数据单元时一般使用栈，即栈式存储管理。栈式:简单的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储分配方案,3、过程活动：一个过程的活动指的是该过程的一次执行。4、活动记录：一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区（块）叫做一个活动记录。活动记录一般包含：（1）连接数据返回地址调用过程指令的下一条指令的地址。动态链（控制链）指向调用该过程活动记录地址的指针。用于当调用返回时，将当前栈顶正确切换到调用者的活动记录静态链（存取链）指向定义该过程的直接外过程（或主程序）运行时最新活动记录地址的指针.用来访问非局部数据(可选)。（2）形式单元存放相应实参的地址或值。（3）局部数据局部变量、内情向量、临时工作单元。,SP,TOP,连接数据(控制信息),SP为当前活动记录的起始位置。TOP为栈顶单元。分别放在两个寄存器中。,访问信息,10.2栈式存储分配的实现,一、简单的栈式存储分配的实现程序结构特点：没有分程序结构，过程定义不嵌套，过程可递归调用。简单栈式分配方案：把存储区组织成一个栈，运行时每进入一个过程，就把它的活动记录压入栈，形成过程工作时的临时数据区，该过程结束时取消该数据区。,例:main全局变量的说明；procR；endR;procQ；endQ;主程序执行语句endmain,mainQR,mainQQ,R的数组区R的活动记录Q的活动记录主程序全局数据区,分配了数组区之后的运行栈,TOP,SP,二、嵌套过程语言的栈式分配的实现1、程序结构特点：语言的定义允许嵌套，一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）（如PASCAL语言）。如何才能引用外层数据？2、关键：设法跟踪每个外层过程的最新活动记录AR的位置。跟踪办法：（1）用静态链。（2）用DISPLAY表。,（1）用静态链,在过程活动记录中增设静态链，指向包含该过程的直接外层过程的最新活动记录的起始位置。见P223-224,mainp1p2p3p4,main,过程定义的嵌套,执行顺序,p2,p4,p3,p3,2、用Display表,Display表-嵌套层次显示表当前激活过程的层次为K，它的Display表含有K+1个单元，依次存放着现行层，直接外层直至最外层的每一过程的最新活动记录的基地址。说明：1、由于过程的层数可以静态确定，因此每个过程的Display表的体积在编译时即可以确定。2、某过程p是在层次为i的过程q内定义的，并且q是包围p的直接外层，那么p的过程层数为i+1。,用Display表的方案,(1)主程序-(2)P-(3)Q-(4)R,用Display表的方案,(1)主程序-(2)P-(3)Q-(4)R,DISPLAY表的维护和建立,为便于组织存储区，将display作为活动记录的一部分，其相对地址在编译时是完全可以确定的。假设过程P1可调用P2，为了能在P2中建立P2的display，在P1调用P2时设法把P1的display地址作为连接数据之一（全局display地址）传送给P2，因此连接数据包括：老SP值（动态链）返回地址全局display地址,dDISPLAY4形式单元3参数个数2全局DISPLAY地址1返回地址0老SP,当过程的层次为n，它的display为n+1个值。一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。,10.3堆式存储分配,堆：通常是一片连续的足够大的存储区，当需要时，就从堆中分配一小块存储区；用完就及时退还给堆。注：在高级语言中有些数据存储空间的请求与释放不再遵循后进先出的原则，而且是全局性的。为此，需要让运行程序持有一块专用的全局存储空间来满足这些数据的存储要求。这种存储空间就是堆。,作业(1)对以下的Pascal程序画出过程C第二次被调用时的运行栈，控制链和存取链.(2)如果把存取链改成DISPLAY，重新做(1)programen