,第8章 程序运行时的存储组织及管理(P158),8.1 程序运行时的存储组织 8.2 静态存储分配 8.3 栈式动态存储分配 8.4 堆式动态存储分配,学 习 重 点,影响存储分配策略的语言特征 静态存储分配 动态存储分配 活动记录 堆式存储分配变长块的方法,影响存储分配策略的语言特征: 过程能否递归 过程能否嵌套 过程调用时参数如何传递 哪些实体可以作为参数和返回值 是否允许动态的为对象分配和撤销存储空间 存储空间是否必须显式地释放 ,第8章 程序运行时的存储组织及管理,程序运行时，系统将为程序分配一块存储空间。这块空间用来存储程序的目标代码以及目标代码运行时需要或产生的各种数据。从用途上看，这块空间可分为以下几个部分： 1）目标程序区：用来存放目标代码。 2）静态数据区：用来存放编译时就能确定存储空间的数据。 3）运行栈区：用来存放运行时才能确定存储空间的数据。 4）运行堆区：用来存放运行时用户动态申请存储空间的数据。,8.1 程序运行时的存储组织,静态存储分配方式：对于源程序中出现的各种数据项，如常量、简单变量、常界数组、非变体记录等, 在编译时就给它们分配固定的存储空间，而且在目标程序运行时，总是使用这些在编译时就分配好的存储单元作为它们的数据空间。,8.2 静态存储分配,采用静态存储分配的语言必须满足下列条件： 1）不允许过程有递归调用。 2）不允许有可变大小的数据项，如可变数组或可变字符串。 3）不允许用户动态建立数据实体。,FORTRAN语言没有长度可变的串，也没有动态数组，其子程序和函数也不允许递归调用，所以FORTRAN语言采用静态存储分配方式。,8.2 静态存储分配,例(P159) 一个FORTRAN程序模块静态存储分配的典型数据区格局如右图所示，其中： 1)隐式参数主要用于和主调模块的通讯，它可以是主调过程的返回地址，或是函数返回值。,2)形式参数存放相应实在参数的地址或值。 3)程序变量部分将作为简单变量、数组、记录以及编译程序所产生的临时变量的存储空间。,8.2 静态存储分配,实现静态存储分配策略：编译程序对源程序进行处理时，对每个变量在符号表中创建一个记录，保存该变量的属性，其中包括为变量分配的存储空间地址即目标地址。由于每个变量需要的空间大小已知,可将数据区开始位置的地址A分配给第一个变量,设第一个变量占n1个字节，则A+n1分配给第二个变量，设第二个变量占n2个字节，同理， A+n1+n2分配给第三个变量等。,例 char array16; int i, j ; real a, b; 假设: 数据区开始位置的地址264 字符型占2个存贮单元 整型占4个存贮单元 实型占8个存贮单元,8.2 静态存储分配,目标地址可采用的地址形式： 绝对地址 如果编写的编译程序是用于单任务环境，那么，通常采用绝对地址作为目标地址。 相对地址 如果编译程序是在多程序任务的环境中，那么目标地址可采用相对于程序数据区的基地址的相对地址。 若使用相对地址方式，那么程序的每一次执行，程序及其数据区可以处在不同的存储区内。,8.2 静态存储分配,动态存储分配方式：有些语言允许有长度可变的串、动态数组，并允许过程递归调用，那么在编译时就无法确定数据空间的具体大小，故其存储分配必须留到目标程序运行时动态地进行。,8.3 栈式动态存储分配,动态存储分配方式的分类： 栈式分配方式：主要采用一个栈作为动态存储分配的存储空间。当调用一个程序时，过程中各数据项所需的存储空间动态地分配于栈顶，当过程结束时，就释放这部分空间。C、PASCAL等语言即采用这种存储分配方式。 堆式分配方式：主要通过给运行程序分配一个大的存储空间(称为堆)，每当运行需要时，就从这片空间中借用一块，用过之后再退还给堆。,栈式动态分配方式的实现： 1)申请：在程序运行中，当程序模块被调用时，就从总的数据区中请求一个空间作为其数据区(即加入运行栈中)，并保留该空间直到执行完整个模块为止。 2)释放：当模块执行完毕，退出模块时，释放它所占有的数据空间(即从运行栈中弹出)。 3)嵌套调用：从模块被调用到它运行结束之间，还可以通过过程调用或程序块入口进入其他的模块，此时，也按上面所介绍的方法将这些模块的数据区压入或弹出运行栈。当嵌套的被调程序运行结束返回到主调程序中的调用点时，运行栈中的格局和内容会恢复到调用之前的情况。,8.3 栈式动态存储分配,例(P160)设有如下C程序，其运行栈的变化情况如下图所示。 real x; 块1 int m1(int ind) 块2 int x; x=m2(ind+1); int m2(int j) 块3 int f10; 块4 bool test1; main()块5 int x; x=2; printf(%dn,m1(x/5); ,(a)程序刚开始,(b)运行main,(c)运行m1,(d)运行m2,(e)运行块4,对于C语言，函数是程序块，一对花括号内的程序即复合语句也可以看成是一个程序块。,上例说明：当这段程序刚开始运行时，其存储分配为图(a)所示，接下来主函数main运行，则为主函数main分配数据区，运行栈为图 (b)，在main中调用了函数m1，当函数m1运行时，运行栈为图 (c)，在函数m1中又调用了函数m2，当函数m2运行时的运行栈如图 (d)所示，由于函数m2中嵌套着块4，当运行块4时，运行栈为图 (e)所示。当块4运行完后，块4数据区出栈，运行栈恢复到图 (d)所示。当函数m2运行完后，运行栈恢复到图 (c)所示。当函数m1运行完后，运行栈恢复到图 (b)所示。当所有程序运行后，运行栈为空。,8.3 栈式动态存储分配,活动记录：当程序运行进入一个程序模块时，就在运行栈的栈顶创建一个专用数据区，该数据区通常称为活动记录。,8.3 栈式动态存储分配,当程序模块执行结束时(即到达模块的出口)，其相应的活动记录将从运行栈的栈顶删除。因此在该模块中所定义的变量在该模块的外部是不存在的。,一个典型的活动记录结构如右图所示。 1、 参数区 1) 隐式参数： 返回地址：主调程序中调用语句的下一条可执行语句的地址。 指向前一个活动记录起始位置的指针：该基地址指针存放该模块的主调模块的活动记录的基地址，用于确保控制返回主调过程时，能使运行环境恢复到调用前的格局。 函数返回值：有的隐式参数区包含此项，有的不包括，还有更好的处理返回值的方法 。 2) 显式参数：显式参数区是形式参数的通讯区。 形式参数的传递有传值、传地址、传名等方法。,8.3 栈式动态存储分配,2、display区(嵌套层次显示表) display区用于保存对当前正在执行的模块来说是全局的程序变量区的信息，它由一系列地址指针所组成，每一个指针指向一个程序块的活动记录的开始位置，而这个程序块对于当前正在执行的程序块来说是全局的。,8.3 栈式动态存储分配,real x; 块1 int m1(int ind) 块2 int x; x=m2(ind+1); int m2(int j) 块3 int f10; 块4 bool test1; main()块5 int x; x=2; printf(%dn,m1(x/5); ,j,OS,无前记录,x,d1,abp0,x ,2,d1,return2,abp1,ind,x,0,d1,return3,abp2,d1,d2,abp3,f,test1,块4活动记录abp4,m2活动记录abp3,m1活动记录abp2,main活动记录abp1,abp0,display区,参数区,局部数据区,应是main,m2,m1,x,构造一个display区的算法(P162)： 如果j=i+1(即进入一个程序块)，则复制i层的display，然后增加一个指向i层模块活动记录基地址的指针。 如果ji(即调用对当前模块来说是属于全程声明的过程模块)，则来自i层模块活动记录中的display区前面j-1个入口将组成j层模块的display区。,8.3 栈式动态存储分配,根据变量的二元地址(BL，ON)和display区的结构可以计算出变量在运行栈中的地址，从而找到变量的值。如果所引用的变量是一个外层模块的局部变量，则它的层次号BL值必须小于当前正在执行的模块的层次号。对这种情况而言，包含该变量单元的活动记录能够间接通过当前活动记录中display区中的相应指针来获取。,给定一个要访问的具有地址为(BL，ON)的变量，设该变量在LEV 层的一个模块中。该变量的地址ADDR可按如下方法计算(P163)： if BL=LEV then ADDR=abp+(BL-1)+nip+ON/局部变量 else if BLLEV then /全局变量 ADDR=displayBL+(BL-1)+nip+ON else write(“地址错，不合法的模块层次”) 在上式中，abp是当前活动记录基址指针值，displayBL指当前活动记录中display区中第BL个元素，nip是指隐式参数的数目。 注意：表达式(BL-1)+nip可解释为display区的大小加隐式参数区的大小。,8.3 栈式动态存储分配,8.3 栈式动态存储分配,对于具有递归块程序结构的语言来说，一个程序模块可以和多个活动记录相关。当程序运行时，随着递归函数的每一次调用，在运行栈栈顶将设置一个新的活动记录，返回地址也与每个活动记录相联系。,例(P163) C程序在程序执行期间其运行栈的变化情况如右图所示。 int fact(int n) if (n3) return(n) else return(n*fact(n-1); main() int m; m=4; printf(%d!=%dn,m,fact(m); 备注：返回地址ret1指示从fact函数的特定动作返回到main函数内部的调用点之后。返回地址ret2指示从fact函数的特定动作返回到fact函数内部的调用点之后。,ret2,ret1,8.3 栈式动态存储分配,栈式存储分配适合那些过程允许嵌套定义、递归调用的语言，其过程的进入和退出具有“后进先出”的特点。如果语言允许动态申请和释放存储空间，那么，栈式存储分配就不适合了，这时，可以采用堆式动态存储分配策略。,堆式分配策略的基本思路：假设程序运行时有一个大的连续的存储空间（堆），当存储管理程序接收到运行程序的存储空间请求时，就从堆中分配一块空间给运行程序。当运行程序用完后再退还给堆（即释放）。管理程序回收其存储空间以备后面使用。由于每块空间可以按任意顺序释放，这样，程序经过一段运行后，堆将被划分成若干已用块和空闲块。,8.4 堆式动态存储分配,程序运行一段时间后,程序运行初期,8.4 堆式动态存储分配,堆式存储分配需要解决的问题： 一是堆空间的分配 当运行程序需要一块空间时，应该分配哪一块给它。 二是分配空间的释放 由于返回给堆的不用空间是按任意次序进行的，所以需要专门研究释放的策略。,新用户请求分配内存时，系统分配空间策略： 系统继续从高地址的空闲块中进行分配，而不查看已分配给用户的内存区是否已空闲，直到分配无法进行(即剩余的空闲块不能满足分配的请求)时，系统才去回收所有用户不再使用的空闲块。 用户使用一旦结束，便将所占内存区释放成空闲块。同时，每当新的用户请求分配内存时，系统需要巡视整个内存中所有空闲块，并从中找出一个“合适”的空闲块加以分配。由此，系统需建立一张记录所有空闲块的“可利用空间表”，表的结构可以采用目录表或链表。,8.4 堆式动态存储分配,0 10000 20000 30000,(a)内存状态,(b)可利用空间目录表,10000,HEAD 10000 20000