第8章-程序运行时的存储组织课件.ppt（39页）

1、第第8 8章章 程序运行时的存储组织程序运行时的存储组织及管理及管理 Constant dropping wears the stone.滴水穿石。滴水穿石。源 程 序目 标 程 序1.编 译编 译 程 序初 始 数 据系 统 子 程 序结 果2.运 行第第8 8章章 程序运行时的存储组织及管理程序运行时的存储组织及管理(P158)(P158)n8.1 程序运行时的存储组织程序运行时的存储组织n8.2 静态存储分配静态存储分配n8.3 栈式动态存储分配栈式动态存储分配n8.4 堆式动态存储分配堆式动态存储分配学学 习习 重重 点点n影响存储分配策略的语言特征影响存储分配策略的语言特征n静态存储

2、分配静态存储分配n动态存储分配动态存储分配n活动记录活动记录n堆式存储分配变长块的方法堆式存储分配变长块的方法n影响存储分配策略的语言特征影响存储分配策略的语言特征:过程能否递归过程能否递归 过程能否嵌套过程能否嵌套 过程调用时参数如何传递过程调用时参数如何传递 哪些实体可以作为参数和返回值哪些实体可以作为参数和返回值 是否允许动态的为对象分配和撤销存储空间是否允许动态的为对象分配和撤销存储空间 存储空间是否必须显式地释放存储空间是否必须显式地释放 第第8 8章章 程序运行时的存储组织及管理程序运行时的存储组织及管理n程序运行时，系统将为程序分配一块存储空间。这程序运行时，系统将为程序分配一块

3、存储空间。这块空间用来存储程序的目标代码以及目标代码运行时块空间用来存储程序的目标代码以及目标代码运行时需要或产生的各种数据。从用途上看，这块空间可分需要或产生的各种数据。从用途上看，这块空间可分为以下几个部分：为以下几个部分：1 1）目标程序区）目标程序区：用来存放目标代码。：用来存放目标代码。2 2）静态数据区）静态数据区：用来存放编译时就能确定存储空：用来存放编译时就能确定存储空间的数据。间的数据。3 3）运行栈区）运行栈区：用来存放运行时才能确定存储空间：用来存放运行时才能确定存储空间的数据。的数据。4 4）运行堆区）运行堆区：用来存放运行时用户动态申请存储：用来存放运行时用户动态申请

4、存储空间的数据。空间的数据。8.1 8.1 程序运行时的存储组织程序运行时的存储组织n静态存储分配方式：静态存储分配方式：对于源程序中出现的各种数据对于源程序中出现的各种数据项，如常量、简单变量、常界数组、非变体记录等项，如常量、简单变量、常界数组、非变体记录等,在编译时就给它们分配固定的存储空间，而且在目标在编译时就给它们分配固定的存储空间，而且在目标程序运行时，总是使用这些在编译时就分配好的存储程序运行时，总是使用这些在编译时就分配好的存储单元作为它们的数据空间。单元作为它们的数据空间。8.2 8.2 静态存储分配静态存储分配n采用静态存储分配的语言必须满足下列条件：采用静态存储分配的语言

5、必须满足下列条件：1 1）不允许过程有递归调用。）不允许过程有递归调用。2 2）不允许有可变大小的数据项，如可变数组或可变）不允许有可变大小的数据项，如可变数组或可变字符串。字符串。3 3）不允许用户动态建立数据实体。）不允许用户动态建立数据实体。nFORTRAN语言没有长度可变的串，也没有动态数组，语言没有长度可变的串，也没有动态数组，其子程序和函数也不允许递归调用，所以其子程序和函数也不允许递归调用，所以FORTRAN语语言言采用静态存储分配方式。采用静态存储分配方式。8.2 8.2 静态存储分配静态存储分配隐式参数隐式参数 形式参数形式参数 简单变量、简单变量、数组及其它数组及其它程序变

6、量程序变量 n例例(P159)一个一个FORTRAN程序模块程序模块静态存储分配的典静态存储分配的典型数据区格局如右图所示，其中：型数据区格局如右图所示，其中：1)1)隐式参数隐式参数主要用于和主调模块的通讯，它可以是主调主要用于和主调模块的通讯，它可以是主调过程的返回地址，或是过程的返回地址，或是函数返回值。函数返回值。2)形式参数形式参数存放相应实在参数的地址存放相应实在参数的地址或值。或值。3)程序变量部分程序变量部分将作为简单变量、数将作为简单变量、数组、记录以及编译程序所产生的临时组、记录以及编译程序所产生的临时变量的存储空间。变量的存储空间。8.2 8.2 静态存储分配静态存储分配

7、n实现静态存储分配策略：实现静态存储分配策略：编译程序对源程序进编译程序对源程序进行处理时，对每个变量在符号表中创建一个记录，行处理时，对每个变量在符号表中创建一个记录，保存该变量的属性，其中包括为变量分配的存储保存该变量的属性，其中包括为变量分配的存储空间地址即目标地址。由于每个变量需要的空间空间地址即目标地址。由于每个变量需要的空间大小已知大小已知,可将数据区开始位置的地址可将数据区开始位置的地址A分配给第分配给第一个变量一个变量,设第一个变量占设第一个变量占n1个字节，则个字节，则A+n1分配分配给第二个变量，设第二个变量占给第二个变量，设第二个变量占n2个字节，同理，个字节，同理，A+

8、n1+n2分配给第三个变量等。分配给第三个变量等。n例例 char array16;int i,j;real a,b;假设假设:数据区开始位置的地址数据区开始位置的地址264字符型占字符型占2个存贮单元个存贮单元整型占整型占4个存贮单元个存贮单元实型占实型占8个存贮单元个存贮单元8.2 8.2 静态存储分配静态存储分配n目标地址可采用的地址形式：目标地址可采用的地址形式：绝对地址绝对地址 如果编写的编译程序是用于单任务环境，那如果编写的编译程序是用于单任务环境，那么，通常采用绝对地址作为目标地址。么，通常采用绝对地址作为目标地址。相对地址相对地址 如果编译程序是在多程序任务的环境中，那如果编译

9、程序是在多程序任务的环境中，那么目标地址可采用相对于程序数据区的基地址的么目标地址可采用相对于程序数据区的基地址的相对地址。相对地址。若使用相对地址方式，那么程序的每一次执若使用相对地址方式，那么程序的每一次执行，程序及其数据区可以处在不同的存储区内。行，程序及其数据区可以处在不同的存储区内。8.2 8.2 静态存储分配静态存储分配n动态存储分配方式：动态存储分配方式：有些语言允许有长度可变的串、有些语言允许有长度可变的串、动态数组，并允许过程递归调用，那么在编译时就无动态数组，并允许过程递归调用，那么在编译时就无法确定数据空间的具体大小，故其存储分配必须留到法确定数据空间的具体大小，故其存储

10、分配必须留到目标程序运行时动态地进行。目标程序运行时动态地进行。8.3 8.3 栈式动态存储分配栈式动态存储分配n动态存储分配方式的分类：动态存储分配方式的分类：栈式分配方式：栈式分配方式：主要采用一个栈作为动态存储分配主要采用一个栈作为动态存储分配的存储空间。当调用一个程序时，过程中各数据项所的存储空间。当调用一个程序时，过程中各数据项所需的存储空间动态地分配于栈顶，当过程结束时，就需的存储空间动态地分配于栈顶，当过程结束时，就释放这部分空间。释放这部分空间。C、PASCAL等语言即采用这种存等语言即采用这种存储分配方式。储分配方式。堆式分配方式：堆式分配方式：主要通过给运行程序分配一个大的

11、主要通过给运行程序分配一个大的存储空间存储空间(称为堆称为堆)，每当运行需要时，就从这片空间，每当运行需要时，就从这片空间中借用一块，用过之后再退还给堆。中借用一块，用过之后再退还给堆。n栈式动态分配方式的实现：栈式动态分配方式的实现：1)1)申请：申请：在程序运行中，当程序模块被调用时，就在程序运行中，当程序模块被调用时，就从总的数据区中请求一个空间作为其数据区从总的数据区中请求一个空间作为其数据区(即加入运即加入运行栈中行栈中)，并保留该空间直到执行完整个模块为止。，并保留该空间直到执行完整个模块为止。2)2)释放：释放：当模块执行完毕，退出模块时，释放它所当模块执行完毕，退出模块时，释放

12、它所占有的数据空间占有的数据空间(即从运行栈中弹出即从运行栈中弹出)。3)3)嵌套调用：嵌套调用：从模块被调用到它运行结束之间，还从模块被调用到它运行结束之间，还可以通过过程调用或程序块入口进入其他的模块，此可以通过过程调用或程序块入口进入其他的模块，此时，也按上面所介绍的方法将这些模块的数据区压入时，也按上面所介绍的方法将这些模块的数据区压入或弹出运行栈。当嵌套的被调程序运行结束返回到主或弹出运行栈。当嵌套的被调程序运行结束返回到主调程序中的调用点时，运行栈中的格局和内容会恢复调程序中的调用点时，运行栈中的格局和内容会恢复到调用之前的情况。到调用之前的情况。8.3 8.3 栈式动态存储分配栈

13、式动态存储分配n例例(P160)设有如下设有如下C程序，其运行栈的变化情况如下图所示。程序，其运行栈的变化情况如下图所示。real x;块块1int 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);块块4数据区数据区 块块3数据区数据区 块块2数据区数据区 块块5数据区数据区 块块1数据区数据区 块块3数据区数据区 块块2数据区数据区 块块5数据区数据区 块块1数据区数据区 块块2数据区数据区 块块5数据区数据区 块块1

14、数据区数据区 块块5数据区数据区 块块1数据区数据区 块块1数据区数据区 (a)程序刚开始程序刚开始(b)运行运行main(c)运行运行m1(d)运行运行m2(e)运行块运行块4n对于对于C语言，函数是程序语言，函数是程序块，一对花括号内的程序即块，一对花括号内的程序即复合语句也可以看成是一个复合语句也可以看成是一个程序块。程序块。块块4数据区数据区 块块3数据区数据区 块块2数据区数据区 块块5数据区数据区 块块1数据区数据区 块块3数据区数据区 块块2数据区数据区 块块5数据区数据区 块块1数据区数据区 块块2数据区数据区 块块5数据区数据区 块块1数据区数据区 块块5数据区数据区 块块1

15、数据区数据区 块块1数据区数据区 (a)程序刚开始程序刚开始(b)运行运行main(c)运行运行m1(d)运行运行m2(e)运行块运行块4n活动记录活动记录：当程序运行进入一个程序模块时，就在：当程序运行进入一个程序模块时，就在运行栈的栈顶创建一个专用数据区，该数据区通常称运行栈的栈顶创建一个专用数据区，该数据区通常称为活动记录。为活动记录。8.3 8.3 栈式动态存储分配栈式动态存储分配n当程序模块执行结束时当程序模块执行结束时(即到达模块的出口即到达模块的出口)，其相，其相应的活动记录将从运行栈的栈顶删除。因此在该模块应的活动记录将从运行栈的栈顶删除。因此在该模块中所定义的变量在该模块的外

16、部是不存在的。中所定义的变量在该模块的外部是不存在的。活动记录活动记录n一个典型的活动记录结构如右图所示。一个典型的活动记录结构如右图所示。1 1、参数区参数区1)1)隐式参数：隐式参数：p返回地址返回地址：主调程序中调用语句的下一条可执行语句的地址。：主调程序中调用语句的下一条可执行语句的地址。p指向前一个活动记录起始位置的指针指向前一个活动记录起始位置的指针：该基地址指针存放该模：该基地址指针存放该模块的主调模块的活动记录的基地址，用于确保控制返回主调过程块的主调模块的活动记录的基地址，用于确保控制返回主调过程时，能使运行环境恢复到调用前的格局。时，能使运行环境恢复到调用前的格局。p函数返

17、回值：函数返回值：有的隐式参数区包含此项，有的不包括，还有更有的隐式参数区包含此项，有的不包括，还有更好的处理返回值的方法好的处理返回值的方法 。2)2)显式参数：显式参数：显式参数区是形式参数的通讯区。显式参数区是形式参数的通讯区。形式参数的传递有传值、传地址、传名等方法。形式参数的传递有传值、传地址、传名等方法。局部数据局部数据区区参数区参数区display区区8.3 8.3 栈式动态存储分配栈式动态存储分配n一个典型的活动记录结构如右图所示。一个典型的活动记录结构如右图所示。1 1、参数区参数区2、display区区(嵌套层次显示表嵌套层次显示表)display区区用于保存对当前正在执行

18、的模块来说是全局的程序用于保存对当前正在执行的模块来说是全局的程序变量区的信息，它由一系列变量区的信息，它由一系列地址指针地址指针所组成，每一个指针指向一所组成，每一个指针指向一个程序块的活动记录的开始位置，而这个程序块对于当前正在执个程序块的活动记录的开始位置，而这个程序块对于当前正在执行的程序块来说是全局的。行的程序块来说是全局的。局部数据局部数据区区参数区参数区display区区8.3 8.3 栈式动态存储分配栈式动态存储分配real x;块块1int m1(int ind)块块2 int x;x=m2(ind+1);int m2(int j)块块3 int f10;块块4 bool t

19、est1;main()块块5 int x;x=2;printf(%dn,m1(x/5);j,1OS无前记录无前记录 xd1abp0 x,2d1return2abp1ind,0 xd1return3abp2d1d2abp3ftest1块块4活动记录活动记录abp4abp4 m2活动记录活动记录abp3 m1活动记录活动记录abp2 main活动记录活动记录abp1abp0display区区参数区参数区局部数据局部数据区区应是应是main,m2,m1,xu构造一个构造一个display区的算法区的算法(P162)：1)如果如果j=i+1(即进入一个程序块即进入一个程序块)，则复制则复制i层的层的d

20、isplay，然后增加一个，然后增加一个指向指向i层模块活动记录基地址的指针。层模块活动记录基地址的指针。2)如果如果ji(即调用对当前模块来说是即调用对当前模块来说是属于全程声明的过程模块属于全程声明的过程模块)，则来自，则来自i层模块活动记录中的层模块活动记录中的display区前面区前面j-1个入口将组成个入口将组成j层模块的层模块的display区。区。jOS无前记录无前记录 xd1abp0 x d1return2abp1indxd1return3abp2d1d2abp3ftest1块块4活动记录活动记录abp4abp4 m2活动记录活动记录abp3 m1活动记录活动记录abp2 ma

21、in活动记录活动记录abp1abp08.3 8.3 栈式动态存储分配栈式动态存储分配n根据变量的根据变量的二元地址二元地址(BL，ON)和和display区的结构可以计算出区的结构可以计算出变量在运行栈中的地址，从而找到变量的值。变量在运行栈中的地址，从而找到变量的值。n给定一个要访问的具有地址为给定一个要访问的具有地址为(BL，ON)的变量，设该变量在的变量，设该变量在LEV 层的一个模块中。该层的一个模块中。该变量的地址变量的地址ADDR可按如下方法计算可按如下方法计算(P163)：if BL=LEV then ADDR=abp+(BL-1)+nip+ON/局部变量局部变量 else if

22、 BLLEV then /全局变量全局变量 ADDR=displayBL+(BL-1)+nip+ON else write(“地址错，不合法的模块层次地址错，不合法的模块层次”)在上式中，在上式中，abp是当前活动记录基址指针值，是当前活动记录基址指针值，displayBL指当指当前活动记录中前活动记录中display区中第区中第BL个元素，个元素，nip是指隐式参数的数目。是指隐式参数的数目。注意：注意：表达式表达式(BL-1)+nip可解释为可解释为display区的大小加隐式参数区的大小加隐式参数区的大小。区的大小。display区区参数区参数区局部数据局部数据区区abp(BL-1)+n

23、ip8.3 8.3 栈式动态存储分配栈式动态存储分配n对于具有递归块程序结构的语言来说，对于具有递归块程序结构的语言来说，一个程序模块可以和一个程序模块可以和多个活动记录相关多个活动记录相关。当程序运行时，随着递归函数的每一次调。当程序运行时，随着递归函数的每一次调用，在运行栈栈顶将设置一个新的活动记录，返回地址也与每用，在运行栈栈顶将设置一个新的活动记录，返回地址也与每个活动记录相联系。个活动记录相联系。块块2数据区数据区 块块2数据区数据区 块块2数据区数据区 块块3数据区数据区 块块1数据区数据区 块块2数据区数据区 块块2数据区数据区 块块3数据区数据区 块块1数据区数据区 块块2数据

24、区数据区 块块3数据区数据区 块块1数据区数据区 块块3数据区数据区 块块1数据区数据区 块块1数据区数据区 (a)程序刚开始程序刚开始(b)运行运行main(c)第一次第一次运行函数运行函数f(d)第二次第二次运行函数运行函数f(e)第三次第三次运行函数运行函数fint f(int n)j=f(n-1);main()i=f(4);递归函数递归函数地址地址 内容内容说明说明 abp4n,2第第3次调次调fact函数函数n=2，返回，返回2给全给全局变量区的局变量区的fact单元单元abp3ret2abp0 abp3n,3第第2次调次调fact函数函数n=3，返回，返回6给全给全局变量区的局变量

25、区的fact单元单元abp2ret2abp0 abp2n,4第第1次调次调fact函数函数n=4。返回。返回24给给全局变量区的全局变量区的fact单元单元abp1ret1abp0 abp1m,4主函数运行，主函数运行，m=4，调，调fact函数。函数。ret0是运行完是运行完main后返回的地址后返回的地址,可以是可以是OS或留空或留空abp0ret0abp0 abp0mainfact用于保存用于保存fact函数的返回值，函数的返回值，开始时无值，最后开始时无值，最后fact函数返回函数返回后为后为24。fact,2,6,24无前记录无前记录OSn例例(P163)C程序在程序执行期间程序在程

26、序执行期间其运行栈的变化情况如右图所示。其运行栈的变化情况如右图所示。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函数内部的调用点之后。函数内部的调用点之后。ret2ret18.3 8.3 栈式动态存储分配栈式动态

27、存储分配n栈式存储分配适合那些栈式存储分配适合那些过程允许嵌套定义过程允许嵌套定义、递归调递归调用用的语言，其过程的进入和退出具有的语言，其过程的进入和退出具有“后进先出后进先出”的特点。的特点。n如果语言如果语言允许动态申请和释放存储空间允许动态申请和释放存储空间，那么，栈，那么，栈式存储分配就不适合了，这时，可以采用式存储分配就不适合了，这时，可以采用堆式动态堆式动态存储分配策略存储分配策略。n堆式分配策略的基本思路堆式分配策略的基本思路：假设程序运行时有一个大的连续的：假设程序运行时有一个大的连续的存储空间（堆），当存储管理程序接收到运行程序的存储空间请存储空间（堆），当存储管理程序接收

28、到运行程序的存储空间请求时，就从堆中分配一块空间给运行程序。当运行程序用完后再求时，就从堆中分配一块空间给运行程序。当运行程序用完后再退还给堆（即释放）。管理程序回收其存储空间以备后面使用。退还给堆（即释放）。管理程序回收其存储空间以备后面使用。由于每块空间可以按任意顺序释放，这样，程序经过一段运行后，由于每块空间可以按任意顺序释放，这样，程序经过一段运行后，堆将被划分成若干已用块和空闲块。堆将被划分成若干已用块和空闲块。8.4 8.4 堆式动态存储分配堆式动态存储分配u1u3 u4u7 u8程序运行一段时间后程序运行一段时间后 程序运行初期程序运行初期 8.4 8.4 堆式动态存储分配堆式动

29、态存储分配n堆式存储分配需要解决的问题：堆式存储分配需要解决的问题：一是堆空间的分配一是堆空间的分配 当运行程序需要一块空间时，应该分配哪一块当运行程序需要一块空间时，应该分配哪一块给它。给它。二是分配空间的释放二是分配空间的释放 由于返回给堆的不用空间是按任意次序进行的，由于返回给堆的不用空间是按任意次序进行的，所以需要专门研究释放的策略。所以需要专门研究释放的策略。n 新用户请求分配内存时，新用户请求分配内存时，系统分配空间策略系统分配空间策略：系统继续系统继续从高地址的空闲块中进行分配从高地址的空闲块中进行分配，而不查看已分配，而不查看已分配给用户的内存区是否已空闲，直到给用户的内存区是

30、否已空闲，直到分配无法进行分配无法进行(即剩余的即剩余的空闲块不能满足分配的请求空闲块不能满足分配的请求)时，系统时，系统才去回收才去回收所有用户不所有用户不再使用的空闲块。再使用的空闲块。用户使用一旦结束，便将所占内存区释放成空闲块。同时，用户使用一旦结束，便将所占内存区释放成空闲块。同时，每当新的用户请求分配内存时，系统需要巡视整个内存中每当新的用户请求分配内存时，系统需要巡视整个内存中所有空闲块，并从中所有空闲块，并从中找出一个找出一个“合适合适”的空闲块加以分配的空闲块加以分配。由此，系统需建立一张记录所有空闲块的由此，系统需建立一张记录所有空闲块的“可利用空间可利用空间表表”，表的结

31、构可以采用目录表或链表。，表的结构可以采用目录表或链表。8.4 8.4 堆式动态存储分配堆式动态存储分配0 10000 20000 30000(a)内存状态内存状态 起始地址起始地址内存大小内存大小 使用情况使用情况 100005000空闲空闲200003000空闲空闲300008000空闲空闲(b)可利用空间目录表可利用空间目录表0500020000030003000008000#10000HEAD 10000 20000 30000(c)可利用空间链表可利用空间链表堆式存储管理的可利用空间表堆式存储管理的可利用空间表 TAGSIZELINKSPACE8.4 8.4 堆式动态存储分配堆式动态

32、存储分配n“可利用空间链表可利用空间链表”中结点的数据结构如下中结点的数据结构如下 TAG：标记，：标记，0表示空闲，表示空闲，1表示占用。表示占用。SIZE：记录结点大小，指示空闲块的存储量。：记录结点大小，指示空闲块的存储量。LINK:指向下一个结点。指向下一个结点。SPACE：地址连续的内存空间。：地址连续的内存空间。一个链表结点一个链表结点n堆式存储管理方法：堆式存储管理方法：1、定长块的管理、定长块的管理 将总的可被利用的堆存储区划分成大小适当的一系列块。将总的可被利用的堆存储区划分成大小适当的一系列块。这些块通过每块中的这些块通过每块中的LINK域连接起来形成单向线性链表（即域连接

33、起来形成单向线性链表（即可利用空间链表）。然后由一个分配程序来处理可利用空间链表）。然后由一个分配程序来处理。8.4 8.4 堆式动态存储分配堆式动态存储分配0800200000800300000800#10000HEAD 10000 20000 30000n对一个存储块的请求，其定长块分配程序算法如下：对一个存储块的请求，其定长块分配程序算法如下：Function GET_BLOCK(HEAD)/H E A D 为 指 向 可 用 存 储 块 链 表 上 第 一 个 块 的 指 针，为 指 向 可 用 存 储 块 链 表 上 第 一 个 块 的 指 针，GET_BLOCK返回一个可用块的地址

34、返回一个可用块的地址p。(1)溢出吗溢出吗?if HEAD=NULL then 转错误处理程序；转错误处理程序；(2)分配存储块分配存储块 p=HEAD HEAD=p.LINK return(p)由于由于各块大小相同，故在分各块大小相同，故在分配函数中不用查找，只需配函数中不用查找，只需将头指将头指针所指的第一块分配给申请空间针所指的第一块分配给申请空间的程序的程序，然后头指针指向下一个，然后头指针指向下一个空闲块。同样，当用户释放内存空闲块。同样，当用户释放内存时，系统只要将用户释放的时，系统只要将用户释放的空间空间块插入到表头块插入到表头即可。即可。08002000008003000008

35、00#10000HEAD 10000 20000 30000n堆式存储管理方法：堆式存储管理方法：2、变长块的管理、变长块的管理（常用）（常用）系统在运行期间分配给用户的内存块的大小不固定，可以系统在运行期间分配给用户的内存块的大小不固定，可以随请求而变。随请求而变。8.4 8.4 堆式动态存储分配堆式动态存储分配n变长块的分配策略：变长块的分配策略：假设用户请求一个大小为假设用户请求一个大小为n的存储块，而的存储块，而“可利用空间链表可利用空间链表”中仅有一块大小为中仅有一块大小为m(mn)的空闲块，则分配时只需将大小为的空闲块，则分配时只需将大小为n的部分分配给申请的用户，同时将剩余的的部

36、分分配给申请的用户，同时将剩余的m-n部分作为一个结部分作为一个结点留在链表中即可。点留在链表中即可。若可利用空间表中有若干个大于若可利用空间表中有若干个大于n的空闲块时，可采用的空闲块时，可采用首次满首次满足法、最优满足法或最差满足法足法、最优满足法或最差满足法来分配块。来分配块。p首次满足法：首次满足法：从表头指针开始查找可利用空间表，将找到的从表头指针开始查找可利用空间表，将找到的第一个大小不小于第一个大小不小于n的空闲块的一部分分配给用户。可利用空的空闲块的一部分分配给用户。可利用空间表本身既不按结点的初始地址排序，也不按结点的大小排序。间表本身既不按结点的初始地址排序，也不按结点的大

37、小排序。在回收时，只要将释放的空闲块插入在链表的表头即可。在回收时，只要将释放的空闲块插入在链表的表头即可。8.4 8.4 堆式动态存储分配堆式动态存储分配08002000001200300000600#10000HEAD 10000 20000 30000 50000070050000010004000040000n问题：假如要申请的空间大小为问题：假如要申请的空间大小为900，分配哪一块呢？分配哪一块呢？8.4 8.4 堆式动态存储分配堆式动态存储分配06002000007003000001200#10000HEAD 10000 20000 30000 500000800500000100

38、04000040000n问题：假如要申请的空间大小为问题：假如要申请的空间大小为900，分配哪一块呢？分配哪一块呢？p最优满足法：最优满足法：系统在分配前首先要对可利用空间表从头至尾系统在分配前首先要对可利用空间表从头至尾扫描一遍，然后从中找出一块不小于扫描一遍，然后从中找出一块不小于n且最接近且最接近n空闲块进行分空闲块进行分配给用户。为了提高效率，通常预先将配给用户。为了提高效率，通常预先将“可利用空间表可利用空间表”按空按空间的大小间的大小从小到大进行排序从小到大进行排序。在回收时，必须将释放的空闲块。在回收时，必须将释放的空闲块插入到合适的位置上去。插入到合适的位置上去。8.4 8.4

39、 堆式动态存储分配堆式动态存储分配012002000001000300000600#10000HEAD 10000 20000 30000 5000008005000007004000040000n问题：假如要申请的空间大小为问题：假如要申请的空间大小为900，分配哪一块呢？分配哪一块呢？p最差满足法：最差满足法：将可利用空间表中不小于将可利用空间表中不小于n且是链表中最大的空且是链表中最大的空闲块的一部分分配给用户。闲块的一部分分配给用户。为了减少查找时间，应该对为了减少查找时间，应该对“可利可利用空间表用空间表”按空闲块的大小从大到小排序。每次按空闲块的大小从大到小排序。每次分配时无需查分

40、配时无需查找，只需从链表中删除第一个结点找，只需从链表中删除第一个结点，并将其中一部分分配给用，并将其中一部分分配给用户，而将户，而将剩余部分剩余部分作为一个新的结点作为一个新的结点插入插入到可利用空间表的到可利用空间表的适适当位置当位置上。回收时也将释放的空闲块插入到链表的适当位置上。上。回收时也将释放的空闲块插入到链表的适当位置上。n在选择变长块的分配策略时需考虑的因素在选择变长块的分配策略时需考虑的因素u用户的逻辑要求用户的逻辑要求u请求的内存空间的大小分布请求的内存空间的大小分布u分配和释放的频率分配和释放的频率u效率对系统的重要性效率对系统的重要性8.4 8.4 堆式动态存储分配堆式

41、动态存储分配p最优满足法最优满足法比较适合于请求分配的内存大小范围较广的系比较适合于请求分配的内存大小范围较广的系统，但最费时间统，但最费时间p最差满足法最差满足法比较适合于请求分配的内存大小范围较窄的系比较适合于请求分配的内存大小范围较窄的系统统p首次满足法首次满足法介于前两者之间。介于前两者之间。n变长块的三种分配策略之比较变长块的三种分配策略之比较n堆式存储管理方法：堆式存储管理方法：3、释放方法、释放方法p最简单的释放方法是作为一个新的空闲块插入到无序的可利最简单的释放方法是作为一个新的空闲块插入到无序的可利用空间表中。但会导致可用空间表中会含有大量的小块。处理用空间表中。但会导致可用

42、空间表中会含有大量的小块。处理办法是将两个连续的办法是将两个连续的块合并块合并成一个块，需要对可利用空间链表成一个块，需要对可利用空间链表按块的地址顺序进行组织，同时为了要确定当前释放块的插入按块的地址顺序进行组织，同时为了要确定当前释放块的插入位置，还需要位置，还需要搜索可利用空间链表搜索可利用空间链表。p有的程序设计语言有的程序设计语言干脆不做释放的工作，直到内存空间用完干脆不做释放的工作，直到内存空间用完为止为止。这样做的缺点是浪费空间，但如果系统的内存很大，这。这样做的缺点是浪费空间，但如果系统的内存很大，这种方法也是可行的。种方法也是可行的。8.4 8.4 堆式动态存储分配堆式动态存

43、储分配小小 结结 n 影响存储分配策略的语言特征：递归、可变数影响存储分配策略的语言特征：递归、可变数据项据项/数据实体等数据实体等n 静态存储分配：编译时安排所有数据对象的存静态存储分配：编译时安排所有数据对象的存储储n 动态存储分配：动态存储分配：栈分配策略：按栈的方式管理运行时的数据存栈分配策略：按栈的方式管理运行时的数据存储空间；储空间；堆分配策略：在运行时根据要求从堆数据区动堆分配策略：在运行时根据要求从堆数据区动态地分配和释放数据存储空间。态地分配和释放数据存储空间。n 活动记录：局部数据区、参数区和活动记录：局部数据区、参数区和display区区n 堆式存储分配变长块的方法：首次

44、满足法、最堆式存储分配变长块的方法：首次满足法、最优满足法、最差满足法。优满足法、最差满足法。习习 题题(P168)(P168)1.什么是静态存储分配？什么是动态存储分配？它什么是静态存储分配？什么是动态存储分配？它们有什么不同？们有什么不同？2.活动记录哪几部分组成？活动记录哪几部分组成？display的作用是什么？的作用是什么？3.静态存储分配对语言有何要求？静态存储分配对语言有何要求？4.只有采用动态存储分配的程序设计语言允许有过只有采用动态存储分配的程序设计语言允许有过程递归调用，为什么？程递归调用，为什么？习习 题题5.画出下段程序运行到画出下段程序运行到a点和点和b点时的运行栈内容。点时的运行栈内容。int f(int b)int c;c=10;int d;d=10;b=c+d;b return(b);main()int a;a a=f(5);printf(“%dn”,a);