数据结构：第八章 动态存储管理.ppt

第八章 动态存储管理8.1 概述8.2 可利用空间表及分配方法8.3 边界标识法8.3.1 可利用空间表的结构8.3.2 分配算法8.4 伙伴系统8.4.1 可利用空间表的结构8.4.2 分配算法8.4.3 回收算法8.1 概述 动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何回收那些用户不再使用而“释放”的内存，以备新的“请求”产生时重新进行分配？占用块：已分配给用户使用的地址连续的内存区空闲块或可利用空间块：未曾分配的地址连续的内存区 在系统运行的初期，整个内存区基本上分隔成两大部分：低地址区包含若干占用块；高地址区（即分配后的剩余部分）是一个“空闲块”经过一段时间以后，有的用户运行结束,它占用的内存区变成空闲块，这就使整个内存区呈现出占用块和空闲块犬牙交错的状态如图8.1(b)所示U1 U2 U3 U4 U5 U6 U7 U8 (b) 系统运行若干时间之后图8.1动态存储分配过程中的内存状态(a) 系统运行初期U1 U2 U3 U4 U5 U6 U7 U8此时，若又有新的用户进入系统请求分配内存，那系统将： 策略一：系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区是否已空闲，直到分配无法进行（即剩余的空闲块不能满足分配的请求）时，系统才去回收所有用户不再使用的空闲块，并且重新组织内存，将所有空闲的内存区连接在一起成为一个大的空闲块。

策略二：用户一旦运行结束，便将它所占内存区释放成为空闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之在此策略下，系统需建立一张记录所有空闲块的“可利用空间表”，此表的结构可以是“目录表”，也可以是“链表”如图8.2所示 25 000 39 000 0 10 000 31 000 59 000 99 999 (a) 内存状态 (b) 目录表 起始地址 内存块大小 使用情况10 000 15 000空闲31 000 8 000空闲59 000 41 000空闲 (c) 链表图8.2 动态存储管理过程中的内存状态可利用空间表av10 000 31 000 59 0000 15 000 0 8 000 0 41 000 8.2 可利用空间表及分配方法 可利用空间表亦称作“存储池”根据系统运行的不同情况，可利用空间表可以有下列3种不同的结构形式：（1）系统运行期间所有用户请求分配的存储量大小相同 对此类系统，在系统开始运行时将归它使用的内存区按所需大小分割成若干大小相同的块，然后用指针链接成一个可利用空间表这种情况下的可利用空间表实质上是一个链栈。

内存分配：将可利用空间表中的第一个结点分配给用户 内存回收：将用户释放的空闲块插入可利用空间表的表头2）系统运行期间所有用户请求分配的存储量有若干种大小的规格 对此类系统，一般情况下是建立若干个可利用空间表，同一链表中的结点大小相同 例如，某动态存储管理系统中的用户请求分配2个字、4个字或8个字的内存块，则系统建立3个结点大小分别为3个字、5个字或9个字的链表，它们的表头指针分别为av2、av4和av8如图8.3所示 tag type linkvalue0结点大小为2个字type = 1结点大小为4个字2结点大小为8个字 0空闲块 tag = 1占用块 (a)结点结构(b) 可利用空间表图8.3有3种大小结点的可利用空间表 av20 0 0 0 0 0 av40 1 0 1 0 1 av80 2 0 2 0 2 内存分配和回收的方法在很大程度上与（1）类似只是当结点大小和请求分配的量相同的链表为空时，需查找结点较大的链表，并从中取出一个结点，将其中一部分内存分配给用户，而将剩余部分插入到相应大小的链表中回收时，也只要将释放的空闲块插入到相应大小的链表的表头中去即可然而，当结点与请求相符的链表和结点更大的链表均为空时，分配不能进行，而实际上内存空间并不一定不存在所需大小的连续空间，只是由于在系统运行过程中，频繁出现小块的分配和回收，使得大结点链表中的空闲块被分隔成小块后插入在小结点的链表中，此时若要使系统能继续运行，就必须重新组织内存，即执行“存储紧缩”的操作。

（3）系统运行期间分配给用户的内存块的大小不固定，可以随请求而变 因此，可利用空间表中的结点即空闲块的大小也是随意的通常，操作系统中的可利用空间表属这种类型此种可利用空间表栈结点的结构如图8.4所示tag：标志域，0表示空闲块，1表示占用块link：链域，指向链表中下一结点的指针size：结点大小域，指示空闲块的存储量space：数据域，是一个地址连续的内存空间tag size linkspace0空闲块tag =1占用块最佳拟合法 最佳拟合法：将可利用空间表中一个不小于n且最接近n的空闲块的一部分分配给用户 系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n且最接近n的空闲块进行分配为了避免每次分配都要扫视整个链表，通常，预先设定可利用空间表的结构按空间块的大小自小至大有序由此，只需找到第一块大于n的空闲块即可进行分配，但在回收时，必须将释放的空闲块插入到合适的位置上去首次拟合法 首次拟合法：从表头指针开始查找可利用空间表，将找到的第一个大小不小于n的空闲块的一部分分配给用户 可利用空间表本身既不按结点的初始地址有序，也不按结点的大小有序在回收时，只要将释放的空闲块插入在链表的表头即可。

分配策略： 最差拟合法 最差拟合法：将可利用空间表中一个不小于n且是链表中最大的空闲块的一部分分配给用户 为了节省时间，此时的可利用空间表的结构应按空闲块的大小自大至小有序分配时，无需查找，只需从链表中删除第一个结点，并将其中一部分分配给用户，而剩余部分作为一个新的结点插入到可利用空间表的适当位置回收时，亦需将释放的空闲块插入到链表的适当位置上去8.3 边界标识法 边界标识法（boundary tag method）是操作系统中用以进行动态分区分配的一种存储管理方法系统将所有的空闲块链接在一个双重循环链表结构的可利用空间表中；分配可按首次拟合进行，也可按最佳拟合进行 采用边界标识法系统的特点：在每个内存区的头部和底部两个边界上分别设有标识，以标识该区域为占用块或空闲块，使得在回收用户释放的空闲块时易于判别在物理位置上与其相邻的内存区域是否为空闲块，以便将所有地址连续的空闲存储区组合成一个尽可能大的空闲块8.3.1 可利用空间表的结构（1）结点结构uplink tagheadllink tag size rlinkspacefoot结点由3部分组成：头部head域、space域和底部foot域。

space：为一组地址连续的存储单元，是可以分配给用户使用的 内存区域其大小有head中的size域指示,并以头部head 和底部foot作为它的两个边界 tag：标志域,在head和foot中都设有该域,值为“0”表示空闲块, 值为“1”表示占用块 size：整个结点的大小，包括头部head和底部foot所占空间llink：链域，位于头部head域，指向前驱结点rlink：链域，位于头部head域，指向后继结点foot:位于结点底部,它的地址是随结点中space空间的大小而变的.uplink:链域，位于尾部foot域，指向本结点头部，其值即为该空 闲块的首地址2）C语言描述 typedef struct WORD /WORD：内存字类型union /head和foot分别是结点的第一个字和最后的字 WORD*llink;/头部域，指向前驱结点 WORD*uplink; /底部域，指向本结点头部;inttag;/块标志,0:空闲,1:占用,头部和尾部均有intsize;/头部域，块大小WORD*rlink;/头部域，指向后继结点OtherTypeother;/字的其他部分 WORD, head, foot, *Space;/*Space:可利用空间指针类型 #define FootLoc (p) p + psize-1/指向p所指结点的底部（3）例子 例如，图8.5(a)是一个占有100KB内存空间的系统在程序开始时的可利用空间表。

a) 初始状态pav0 1000000(b)运行若干时间后的状态pav10 000 31 000 59 0000 15 000 0 8 000 0 41 00000010 000 31 000 59 0000 8 000 0 8 000 0 41 000000pav (c)进行再分配后的状态图8.5 某系统的可利用空间表8.3.2 分配算法（1）算法描述 假设采用首次拟合法进行分配，则只要从表头指针pav所指结点起，在可利用空间表中进行查找，找到第一个容量不小于请求分配的存储量(n)的空闲块时，即可进行分配为了使整个系统更有效地运行，在边界标识法中还作了如下两条约定： 假设找到的此块待分配的空闲块的容量为m个字（包括头部和底部）,若每次分配只是从中分配n个字给用户,剩余m-n个字大小的结点任留在链表中，则在若干次分配之后，链表中会出现一些容量极小总也分配不出去的空闲块，这就大大减慢了分配（查找）的速度弥补的办法是：选定一个适当的常量e，当mne时，就将容量为m的空闲块整块分配给用户；反之，只分配其中n个字的内存块同时，为了避免修改指针,约定将该结点中的高地址部分分配给用户 如果每次分配都从同一个结点开始查找的话，势必造成存储量小的结点密集在头指针pav所指结点附近，这同样会增加查询较大空闲块的时间。

反之，如果每次分配从不同的结点开始进行查找，使分配后剩余的小块均匀的分布在链表中，则可避免上述弊病实现的方法是，在每次分配之后，令指针pav指向刚进行过分配的结点的后继结点 （2）算法实现 Space AllocBoundTag (Space &pav, int n) /若有不小于n的空闲块，则分配相应的存储块，并返回/其首地址；否则返回NULL若分配后可利用空间表不/空，则pav指向表中刚分配过的结点的后继结点for (p = pav; p & psize rlink != pav; p = prlink);/查找不小于n的空闲块if (!p | | psize rlink;/pav指向*p结点的后继结点if (psizen = e) /整块分配，不保留llink = pllink;pllinkrlink = pav; / else ptag = ftag = 1;/修改分配结点的头部和底部标志 / if（3）例子 例如，图8.5(b)所示可利用空间表在进行分配之后的状态如图8.5(c)所示 (ppt15和16页) else /分配该块的后n个字 ftag = 1;/修改分配块的底部标志 psize = n;/置剩余块大小 f = FootLoc (p);/指向剩余块底部 ftag = 0;fuplink = p;/设置剩余块底部 p = f + 1;/指向分配块头部 ptag = 1; psize = n;/甚至分配块头部return p; / else / AllocBoundTag8.3.3 回收算法 用户释放占用块后，系统需立即回收以备新的请求产生时进行再分配。

为了使物理地址毗邻的空闲块结合成一个尽可能大的结点，则首先需要检查刚释放的占用块的左、右紧邻是否为空闲块假设用户释放的内存区的头部地址为p，则 p-1=与其低地址紧邻的内存区的底部地址，即左邻区； p+psize=与其高地址紧邻的内存区的头部地址,即右邻区 （1）释放块的左、右邻区均为占用块 此时只要作简单插入即可由于边界标识法在按首次拟合进行分配时对可利用空间表的结构没有任何要求，则新的空闲块插入在表中任何位置均可简单的做法就是插入在pav指针所指结点之前（之后），描述如下：ptag = 0;FootLoc (p)uplink = p;FootLoc (p)tag = 。