《内蒙古大学《算法与数据结构》课件第9章动态存储管理》由会员分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》课件第9章动态存储管理（51页珍藏版）》请在金锄头文库上搜索。
1、计算机专业本科主干基础课计算机专业本科主干基础课第九章第九章 动态存储管理动态存储管理9.1 概述概述9.2 可利用空间表可利用空间表9.3 伙伴系统（伙伴系统（Buddy system）9.4 一个小型的动态存储管理系统一个小型的动态存储管理系统 9.1 概述概述 内存管理分别由操作系统、高级语言的编译内存管理分别由操作系统、高级语言的编译系统和程序员分工合作管理。通常编译系统系统和程序员分工合作管理。通常编译系统负责静态储存管理，操作系统负责整个内存负责静态储存管理，操作系统负责整个内存管理和动态储存管理。管理和动态储存管理。 用户程序中所用的储存结构可分为两类，静态用户程序中所用的储存结
2、构可分为两类，静态结构：空间量在编译后，即可确定；动态结构：结构：空间量在编译后，即可确定；动态结构：程序运行中申请空间，编译时无法确定。静态程序运行中申请空间，编译时无法确定。静态储存由编译系统管理；动态储存由程序员和操储存由编译系统管理；动态储存由程序员和操作系统管理，但程序员的管理非常简单。作系统管理，但程序员的管理非常简单。 程序员级的管理：程序员级的管理： 程序员的工作就是在需要的时候向系统申请空程序员的工作就是在需要的时候向系统申请空间，在不需要时释放占有的动态储存空间。间，在不需要时释放占有的动态储存空间。例例如：如： 在在C语言中语言中: malloc(size)：申请申请si
3、ze字节的内存；字节的内存； free(p)： 释放释放p，把空间归还给系，把空间归还给系.用户程序：用户程序：# include iostd.libInt main() *r=new int100; free (r);操作系统操作系统分配分配 OS_AllocMemory(r,size,flags)回收回收 OS_ReclaimMemory(r) FreeMem图图9.1 程序员管理内存程序员管理内存 在在C+中中: new objectType()：申请空间；申请空间； delete(p)： 释放释放p，把空间归还给系统；，把空间归还给系统； 在在Java语言中语言中: new objec
4、tType()：申请空间申请空间； 当用户在程序执行到空间申请语句时，操作系统执行分当用户在程序执行到空间申请语句时，操作系统执行分配操作，从空闲存储空间中取出所需空间，交给用户程配操作，从空闲存储空间中取出所需空间，交给用户程序使用。当执行到释放空间语句，操作系统执行回收操序使用。当执行到释放空间语句，操作系统执行回收操作，将被释放的空间回收到空闲存储空间中，如图作，将被释放的空间回收到空闲存储空间中，如图9.1所所示。示。 编译系统级管理：编译系统级管理： 在编译中，编译系统为程序设置了一个虚拟在编译中，编译系统为程序设置了一个虚拟空间。程序中所说明的数据在编译时根据其类型空间。程序中所说
5、明的数据在编译时根据其类型在虚拟存储空间中为它们分配存储空间，这样的在虚拟存储空间中为它们分配存储空间，这样的数据称为静态数据。程序执行时，首先将程序装数据称为静态数据。程序执行时，首先将程序装入内存，并将虚拟空间映射到内存。编译系统管入内存，并将虚拟空间映射到内存。编译系统管理的是虚拟存储空间。编译原理与技术中将做详理的是虚拟存储空间。编译原理与技术中将做详细介绍。细介绍。 程序：程序： int x,y; float r,s; char str10; x: 2bytesy: 2bytesr: 4bytess: 4bytes str: 10bytes内存内存程序装入时程序装入时,重定位重定位图
6、图9.2 数据说明、虚拟存储空间和内存的关系数据说明、虚拟存储空间和内存的关系虚拟存储空间：虚拟存储空间： 操作系统级管理：操作系统级管理：操作系统的存储管理操作系统的存储管理为程序代码和静态数据为程序代码和静态数据 分配空间，为程序动态分分配空间，为程序动态分 配空间配空间 回收不用的动态空间回收不用的动态空间 回收程序代码和所数据回收程序代码和所数据 占用的空间占用的空间 分分配配回回收收程序程序 New Otype()delete(p)执行完毕或撤消执行程执行完毕或撤消执行程 执行程序执行程序 9.2 可利用空间表可利用空间表 可利用空间表是动态存储管理的常用方法一。可利用空间表是动态存
7、储管理的常用方法一。系统在初始时，除了操作系统占用的空间外，其它系统在初始时，除了操作系统占用的空间外，其它空闲空间是连续的一大块，空闲空间是连续的一大块，如图如图8.4所示所示。经过一系。经过一系列的分配与回收之后，空闲块变的七零八乱，分布列的分配与回收之后，空闲块变的七零八乱，分布在存储空间的各处。可利用空间表就是将这些空闲在存储空间的各处。可利用空间表就是将这些空闲块链接成一个链表，分配时从可利用空间表中取一块链接成一个链表，分配时从可利用空间表中取一适当的块进行分配，回收时将被释放的块插入可利适当的块进行分配，回收时将被释放的块插入可利用空间表。可利用空间表是一个存储资源仓库，也用空间
8、表。可利用空间表是一个存储资源仓库，也称称“存储池存储池”或或“堆堆”，存储管，存储管 理系统是它的管理员，当需要存储空间时向它借用一块空理系统是它的管理员，当需要存储空间时向它借用一块空间，用完后归还。针对不同的用途和在不同的系统中，可间，用完后归还。针对不同的用途和在不同的系统中，可利用空间表的组织方法和实现方法有所不同。一般主要有利用空间表的组织方法和实现方法有所不同。一般主要有以下几种结构形式。以下几种结构形式。 第一种形式，将空闲空间分成大小相同的块，它们是不可第一种形式，将空闲空间分成大小相同的块，它们是不可分割和合并的，系统分配与回收存储空间都以块为单位。分割和合并的，系统分配与
9、回收存储空间都以块为单位。如如LISP语言，是一种符号处理语言，程序与数据均以广义语言，是一种符号处理语言，程序与数据均以广义表形式表示和存储，其存储单元是表形式表示和存储，其存储单元是Cell，即广义表存储结构，即广义表存储结构中的一个结点，所有中的一个结点，所有 Cell的大小是一样，把存储空间按的大小是一样，把存储空间按Cell的大小分割成块，构成可利用空间表。的大小分割成块，构成可利用空间表。 9.2.1 可利用空间表结构可利用空间表结构 一个连续的存储空间称为一个连续的存储空间称为“块块”（block），块由下列域组成：），块由下列域组成： Tag：标记空间是否分配；标记空间是否分配
10、； Size：空间大小；空间大小； Space：存储空间；存储空间； Link：指向下一个空闲块；指向下一个空闲块； 在初始，除了操作系统占用的空间外，其它空间形成一个闲在初始，除了操作系统占用的空间外，其它空间形成一个闲块。当空闲块多时，用块。当空闲块多时，用Link 链成一个链表，该链表就是可利链成一个链表，该链表就是可利用空间表。初始此表中只有一个空闲块。表指针是用空间表。初始此表中只有一个空闲块。表指针是free。初初始状态如图始状态如图9.4所示所示。 Free操作系统操作系统Tag=0Size Link图图9.4 可利用空间表的初始状态可利用空间表的初始状态经过多次分配、回收之后，
11、形成了多个空闲块，它们之间不连续，经过多次分配、回收之后，形成了多个空闲块，它们之间不连续，如图如图9.5和和9.6所示：所示：Free1 Used1 Free2 Used2 Free3 Used3 Free4 Used4 Free5图图9.5 多次分配回收后的内存状态多次分配回收后的内存状态Free1Free2Free3Free4Free5Free图9.6 多次分配回收后的可利用空间表的状态 可利用空间表的链接顺序有：可利用空间表的链接顺序有： （1）按块的首地址由低到高链接。）按块的首地址由低到高链接。 （2）按块的大小由小到大链接。）按块的大小由小到大链接。 （3）按块的大小由大到小链接
12、）按块的大小由大到小链接（4）随机链接）随机链接 9.2.2 分配分配分配一般有分配一般有3种策略，种策略，设申请空间的大小为设申请空间的大小为n。（1）首次拟合法：从表头开始搜索，遇到第一个大首次拟合法：从表头开始搜索，遇到第一个大 于等于于等于n的块进行分配。的块进行分配。（2）最佳拟合法：搜索整个表，将最小的大于等于最佳拟合法：搜索整个表，将最小的大于等于n的块进行分配。的块进行分配。（3）最差拟合法：搜索整个表，将大于等于最差拟合法：搜索整个表，将大于等于n的最大的最大块进行分配。块进行分配。 分配过程：分配过程：（1）按分配策略找到可分配的空闲块）按分配策略找到可分配的空闲块p；（2
13、）p-size等于等于n或比或比n大少许（一般设定一个量大少许（一般设定一个量s），则将），则将p从从表中删除，进行分配；表中删除，进行分配；（3）若）若p-size n+s，从，从p的下部切割的下部切割size为为n的一块进行分配，的一块进行分配，如图如图9.7所示所示，n=16k048k32k048k016k116k1(a) 分配前分配前 (b) 分配分配 (c) 分配后分配后 ppp 9.2.3 回收回收 回收过程：回收过程：设释放块是设释放块是p，大小为，大小为size。(1)设置设置p-tag=0；(2)判断判断p的下一相邻块的下一相邻块q是否空闲是否空闲 若空闲：从可利用空间表中摘
14、出若空闲：从可利用空间表中摘出q，置，置p-size=p-size + q-size（合并）；（合并）；(3)判断判断p的上一相邻块的上一相邻块r是否空闲是否空闲 若空闲：合并若空闲：合并r和和p，r-size=r-size + p-size 否则：将否则：将p插入可利用空间表。插入可利用空间表。 例如，图例如，图9.5中的中的Used1被释放，它的上端邻被释放，它的上端邻接块是接块是Free1，下端邻接块是，下端邻接块是Free2，因此，因此Free1、Used1和和Free2可以合并成一个块。可以合并成一个块。首先将首先将Free2从从Free中摘取下来，合并到中摘取下来，合并到Used1
15、上，在将上，在将Used1合并到合并到Free1上。上。如图如图9.8所示。所示。 图图 9.8 回收过程回收过程程序释放空间（程序释放空间（如如delete(p)）、程）、程序运行结束后将占序运行结束后将占用的块归还系统，用的块归还系统，如果收回的块的相如果收回的块的相邻块是空闲的，需邻块是空闲的，需要合并它们。要合并它们。0 32k0016k64kUsed1Used2Free1Used1Free2(a) 合并合并Used1和和Free2(b) 合并合并Free1和和Used1r 9.3 伙伴系统（Buddy system） 伙伴系统是一种精巧的内存动态管理的方法，伙伴系统是一种精巧的内存动
16、态管理的方法，具体的实现方法有多种。其特点是分配和回具体的实现方法有多种。其特点是分配和回收简单而有效，块按不同大小的等级分类。收简单而有效，块按不同大小的等级分类。下面详细介绍指数伙伴系统（下面详细介绍指数伙伴系统（Exponential Buddy System）。）。 在指数伙伴系统中，块的大小均是在指数伙伴系统中，块的大小均是2k（k=0,1,2,m）。任何）。任何一个块，若其大小为一个块，若其大小为2i (i0)，则该块可以分成两个大小为，则该块可以分成两个大小为2i-1 的块，这两个块是伙伴，任意一块的伙伴都是唯一的，伙伴的块，这两个块是伙伴，任意一块的伙伴都是唯一的，伙伴是相邻的。若两个伙伴都空闲，则可以合并成一个空闲块。是相邻的。若两个伙伴都空闲，则可以合并成一个空闲块。伙伴间存在一对一的关系，已知一个块的地址，很容易求得伙伴间存在一对一的关系，已知一个块的地址，很容易求得其伙伴的地址，因此合并十分容易实现其伙伴的地址，因此合并十分容易实现。 llink tagsize rlink 图图9.9 空闲块结构空闲块结构 9.3.1 指数伙伴系统的可利用空间表结构指数伙伴系统
