数据结构数据结构第八章第八章第八章第八章动态动态动态动态存存存存储储储储管理管理管理管理1本章内容本章内容8.1动态存储管理概述动态存储管理概述8.2 可利用空间表及分配方法可利用空间表及分配方法8.3 边界标识法边界标识法8.4 伙伴系统伙伴系统28.1 8.1 动态动态存存储储管理概述管理概述+存储管理每一种数据结构都必须研究该结构的存储结构，但它是借助于某一高级语言中的变量说明来加以描述的，并没有涉及到具体的存储分配。实际上，结构中的每个数据元素都占有一定的内存位置，在程序执行的过程中，数据元素的存取是通过对应的存储单元来进行的。研究数据存储与内存单元对应问题，就是存储管理问题。38.1 8.1 动态动态存存储储管理概述管理概述+动态存储管理的基本问题1.如何根据用户提出的“请求”来分配内存。2.如何收回被用户“释放”的内存，以备新的“请求”产生时重新进行分配。48.1 8.1 动态动态存存储储管理概述管理概述+存储原理计算机内存在刚工作时，空闲部分是一个整块的连续区域；不断运行程序，多次申请和释放内存以后，空闲内存不再连续，形成多个不连续的空闲区。动态存储管理：指系统随机地根据用户程序申请空间的大小，进行分配空间和回收不用空间所进行的内存管理。占用块：将系统已分配给用户使用的地址连续的内存区域为“占用块”；空闲块：称未曾分配的地址连续的内存区为“空闲块”。 内存的初始状态内存的初始状态U2U4 系统运行若干时后系统运行若干时后U1U2U3U4 系统运行初期系统运行初期58.1 8.1 动态动态存存储储管理概述管理概述+可利用空间表内存空间的所有可利用的空闲空间的情况记录表。有两种结构：1.目录表；2.链表：一个结点表示一个空闲块。av15000150000 010000800080000 031000 41000410000 059000链表链表目录表目录表空闲空闲空闲空闲41000410005900059000空闲空闲空闲空闲800080003100031000空闲空闲空闲空闲15000150001000010000内存状态内存状态010000250003100039000590009999968.2 8.2 可利用空可利用空间间表及分配方法表及分配方法本节主要讨论利用可利用空间表进行动态存储分配的方法。目录表法比较简单，在操作系统课程中已详细介绍。本节仅讨论链表方法分配内存。78.2 8.2 可利用空可利用空间间表及分配方法表及分配方法+三种结构形式：第一种情况：系统运行期间所有用户请求分配的存储量大小相同；具体作法是：开始运行时将内存区分割成若干大小相同的块，形成一可利用链表，分配和回收操作如同一般链表。第二种情况：系统运行期间用户请求分配的存储量有若干种大小的规格；具体作法是：先建立若干个可利用空间表，同一链表中的结点小相同，分配/回收情况：结点大小与请求分配量相同时；结点大小比请求量大时；结点大小比请求量小时。88.2 8.2 可利用空可利用空间间表及分配方法表及分配方法节点结构节点结构节点结构节点结构tagtagtypetypelinklinkValueValuetype = 0 节点大小为节点大小为2字节字节1 节点大小为节点大小为4字节字节2 节点大小为节点大小为8字节字节tag = 0 空闲块空闲块1 占用块占用块0 00 00 00 00 00 0av21 10 01 10 01 10 0av40 00 00 00 00 00 0av8可利用空间表可利用空间表98.2 8.2 可利用空可利用空间间表及分配方法表及分配方法第三种情况：系统在运行期间分配给用户的内存块的大小不固定，可以随请求而变。+工作情况：系统刚开始工作时，整个内存空间是一个空闲块，随时着分配和回收的进行，可利用空间表中的结点大小和个数也随之而变。108.2 8.2 可利用空可利用空间间表及分配方法表及分配方法+分配方法若某用户需大小为n的内存，而可利用空间仅有一块大小为 mn 的空闲块，则只需将其中大小为n 的一部分分配给申请的用户，同时将乘余的 m-n 的部分作为一个结点留在链表中即可。若可利用空间表有若干个不小于n的空闲块时，可有三种不同的分配方案：118.2 8.2 可利用空可利用空间间表及分配方法表及分配方法1.首次拟合法分配找到的第一个不小于n的空闲块的一部分。操作方便，查找快捷；2.最佳拟合法分配不小于n且最接近n的空闲块的一部分。尽可能将大的空闲块留给大程序使用；3.最坏拟合法分配不小于n且是最大的空闲块的一部分。尽可能减少分配后无用碎片；128.2 8.2 可利用空可利用空间间表及分配方法表及分配方法+内存的分配与回收分配根据申请内存大小利用相应分配策略分配给用户所需空间；若分配块大小与申请大小相差不多，则将此块全部分给用户；否则，将分配块分为两部分，一部分给用户使用，另一部分继续留在可利用空间表中。回收测试回收块前后相邻内存块是否空闲；若是则需将回收块与相邻空闲块合并成较大的空闲块，再链入可利用空间表中。138.3 8.3 边边界界标识标识法法+用以进行动态分区分配的一种管理方法+节点结构headheadllinkllinktagtagsizesizerlinkrlinkspacespacefootfootuplinkuplinktagtag可利用空间表中的节点结构图可利用空间表中的节点结构图p 可利用空间表中的节点结构定义可利用空间表中的节点结构定义type struct WORD /WORD,内存数据类型内存数据类型 union /head 和和 foot 分别是节点的第一个和最后一个字分别是节点的第一个和最后一个字 WORD *llink; /头部域，指向前趋节点头部域，指向前趋节点 WORD *rlink; /底部域，指向本节点头部底部域，指向本节点头部 ; int tag; /块标志块标志: 0空闲空闲,1占用占用.头部和尾部均有头部和尾部均有 int size; /头部域，块大小头部域，块大小 WORD *rlink; /头部域，指向后继节点头部域，指向后继节点 otherType other; /字的其他部分字的其他部分 WORD, head, foot, *Space; /*Space: 可利用空间指针类型可利用空间指针类型#define FootLoc(p) p+p-size-1 /指向指向p所指节点的底部所指节点的底部8.3 8.3 边边界界标识标识法法+分配算法：采取首次拟合法进行分配。有两个约定：1.假设待分配的内存空闲块容量为m 个字，若每次分配只从中分配n个字(nm)给用户，剩余m-n个字的节点仍留在表中，若干次分配后，链表中存在大量容量极小，总分配不出去的空闲块。解决的办法是：确定一个常量e，当m-nsizerlink!=pav; p=p-rlink;) /如果查找不小于如果查找不小于n的空闲块，找不到返回的空闲块，找不到返回NULL if (!p | p-sizerlink; /pav指向指向*p节点的后继节点的后继 if (p-size-n=e) /整块分配，不保留整块分配，不保留llink=p-llink;p-llink-rlink =pav; p-tg=f-tag=1; /修改分配节点的头部和底部标志修改分配节点的头部和底部标志 else /分配该块后的分配该块后的n个字个字 f-tag=1; /修改分配块的底部标志修改分配块的底部标志 p-size - =n; /修改剩余块大小修改剩余块大小 f=FootLoc(p); /指向剩余块底部指向剩余块底部 f-tag=0; f-uplink=p; /设置剩余块底部设置剩余块底部 p=f+1; /指向分配块头部指向分配块头部 p-tag=1; p-size=n; /设置分配块头部设置分配块头部 return p; /返回分配块的首地址返回分配块的首地址 168.3 8.3 边边界界标识标识法法+回收算法用户释放占用块后，系统需立即回收以备新的请求产生时进行再分配。为了使物理地址毗邻的空闲块结合成一个尽可能大的结点，则首先需要检查刚释放的占用块的左、右紧邻是否为空闲块。假设用户释放的内存区的头部地址为p，则p-1=与其低地址紧邻的内存区的底部地址，即左邻区；p+psize=与其高地址紧邻的内存区的头部地址,即右邻区。178.3 8.3 边边界界标识标识法法a)释放块的左、右邻区均为占用块此时只要作简单插入即可。由于边界标识法在按首次拟合进行分配时对可利用空间表的结构没有任何要求，则新的空闲块插入在表中任何位置均可。简单的做法就是插入在pav指针所指结点之前（之后），描述如下：ptag = 1= 0;FootLoc (p)uplink = p;FootLoc (p)tag = 0;if (!pav)pav = pllink = prlink = p;else q = pavllink;prlink = pav;pllink = q;qrlink = pavllink = p;pav = p; /令刚释放的结点为下次分配时的最先查询的结点令刚释放的结点为下次分配时的最先查询的结点188.3 8.3 边边界界标识标识法法b)释放块的左邻区为空闲块，而右邻区为占用块由于释放块的头部和左邻空闲块的底部毗邻，因此只要改变左邻空闲块的结点：增加结点的size域的值且重新设置结点的底部即可。描述如下n = psize; /释放块的大小释放块的大小s = (p1)uplink; /左邻空闲块的头部地址左邻空闲块的头部地址ssize + = n; /设置新的空闲块大小设置新的空闲块大小f = p + n1; /设置新的空闲块底部设置新的空闲块底部fuplink = s;ftag = 0;198.3 8.3 边边界界标识标识法法c)释放块的右邻区为空闲块，而左邻区为占用块由于释放块的底部和右邻区空闲块的头部毗邻，因此，当表中结点由原来的右邻空闲块变成合并后的大空闲块时，结点的底部位置不变,但头部要变,由此,链表中的指针也要变。描述如下：t = p + psize;/右邻空闲块的头部地址右邻空闲块的头部地址ptag = 0;/p为合并后的结点头部地址为合并后的结点头部地址q = tllink; /q为为*t结点在可利用空间表中的前驱结点的头部地址结点在可利用空间表中的前驱结点的头部地址pllink = q;/q指向指向*p的前驱的前驱qrlink = p;q1 = trlink; /q1为为*t结点在可利用空间表中的后继结点的头部地址结点在可利用空间表中的后继结点的头部地址prlink = q1;/q1指向指向*p的后继的后继q1llink = p;psize + = tsize;/新的空闲块的大小新的空闲块的大小FootLoc (t)uplink = p;/底部指针指向新结点的头部底部指针指向新结点的头部208.3 8.3 边边界界标识标识法法d)释放块的左、右邻区均为空闲块为使3个空闲块连接在一起成为一个大结点留在可利用空间表中，只要增加左邻空闲块的space容量，同时在链表中删去右邻空闲块结点即可。所作改变可描述如下：n = psize; /释放块的大小释放块的大小s = (p1)uplink; /指向左邻块指向左邻块t = p + psize; /指向右邻块指向右邻块ssize + = n + trlink; /设置新结点的大小设置新结点的大小q = tllink; /q != q1q1 = trlink;qrlink = q1; /删去右邻空闲块结点删去右邻空闲块结点q1llink = q;FootLoc (t)uplink = s; /新结点底部指针指向其头部新结点底部指针指向其头部218.3 8.3 边边界界标识标识法法例如，在上述情况下可利用空间表的变化如图例如，在上述情况下可利用空间表的变化如图8.6所示。所示。30 0001 20 000120 00000 30 000左邻区左邻区释放块释放块(a) 释放的存储块释放的存储块(b) 左邻区是空闲块的情况左邻区是空闲块的情况(c) 右邻区是空闲块的情况右邻区是空闲块的情况00 35 0000 15 000右邻区右邻区释放块释放块右邻区右邻区释放块释放块228.3 8.3 边边界界标识标识法法(d) 左、右邻区均是空闲块的情况左、右邻区均是空闲块的情况回收存储块后的可利用空间表回收存储块后的可利用空间表00 15 0000 45 000右邻区右邻区释放块释放块右邻区右邻区左邻区左邻区238.3 8.3 边边界界标识标识法法+边界表示法的问题查找适合需要的块，需要较多的时间查找适合需要的块的策略（最先/最佳/最坏），每种都有缺陷碎片问题248.48.4 伙伴系伙伴系统统+伙伴系统(buddy system)：是操作系统中用到的一种动态存储管理方法。它和边界标识法类似，在用户提出申请时，分配一块大小“恰当”的内存区给用户；反之，在用户释放内存区时即收回。+伙伴系统的特点：无论是占用块或空闲块，其大小均为2的k次幂（k为某个正整数）。258.48.4 伙伴系伙伴系统统+结点结构表头结点表头结点headllink tag kval rlinkspacenodesize firstn 结点：右头部结点：右头部head和和space域组成。域组成。 head：为结点头部，是一个由：为结点头部，是一个由4个域组成的记录。个域组成的记录。 llink： 链域，指向同一链表中的前驱结点。链域，指向同一链表中的前驱结点。 rlink： 链域，指向同一链表中的后继结点。链域，指向同一链表中的后继结点。 tag： 标志域，值为标志域，值为“0”表示空闲块，值为表示空闲块，值为“1”表示占用块。表示占用块。 kval： 其值为其值为2的幂次的幂次k。 space：数据域，是一个大小为：数据域，是一个大小为2k1个字的连续内存空间。个字的连续内存空间。n 表头结点：由两个域组成。表头结点：由两个域组成。 nodesize：表示该链表中空闲块的大小。：表示该链表中空闲块的大小。 first：该链表的表头指针。：该链表的表头指针。268.48.4 伙伴系伙伴系统统+可利用空间表的结构C语言描述#define m 16 /可利用空间总容量可利用空间总容量64k字的字的2的幂次，子表的个数为的幂次，子表的个数为m+1typedef struct WORD_b WORD_b *llink; /头部域，指向前驱结点头部域，指向前驱结点 int tag; /块标志，块标志，0：空闲，：空闲，1：占用。：占用。 int skval; /块大小，值为块大小，值为2的幂次的幂次k WORD_b *rlink; /头部域，指向后继结点头部域，指向后继结点 OtherType other; /字的其他部分字的其他部分 WORD_b, head; /WORD：内存字类型，结点的第一个字也称：内存字类型，结点的第一个字也称headtypedef struct HeadNode int nodesize; /该链表的空闲块的大小该链表的空闲块的大小 WORD_b *first; /该链表的表头指针该链表的表头指针 FreeListm + 1; /表头向量类型表头向量类型278.48.4 伙伴系伙伴系统统+示例：可利用空间表的初始状态如下图所示，其中m个子表都为空表，只有大小为2m的链表中有一个结点，即整个存储空间。(a) 表的初始状态表的初始状态nodesize first20212k2m0 m伙伴系统中的可利用空间表伙伴系统中的可利用空间表288.48.4 伙伴系伙伴系统统+分配算法当用户提出大小为n的内存请求时，首先在可利用表上寻找结点大小与n相匹配的子表，若此子表非空，则将子表中任意一个结点分配之即可；若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，则将其中一部分分配给用户，而将剩余部分插入相应的子表中298.48.4 伙伴系伙伴系统统+算法实现WORD_b AllocBuddy (FreList &avail, int n) /avail0.m为可利用空间表，为可利用空间表，n为申请分配量，若有不小于为申请分配量，若有不小于n的空的空 /闲闲/块，则分配相应的存储块，并返回其首地址；否则返回块，则分配相应的存储块，并返回其首地址；否则返回NULL for (k = 0; k = m & (availk.nodesize m) /分配失败返回分配失败返回NULL return NULL; else /进行分配进行分配 pa = availk.first; /指向可分配子表的第一个结点指向可分配子表的第一个结点 pre = pallink; /分别指向前驱和后继分别指向前驱和后继 suc = parlink; if (pa = = suc) /分配后该子表变成空表分配后该子表变成空表 availk.first = NULL; else /从子表中删去从子表中删去*pa结点结点 prerlink = suc; sucllink = pre; availk.first = suc; for (i=1; availk-i.nodesize=n+1; +i) pi = pa + 2k-i; pirlink = pi; pillink = pi; pitag = 0; pikval = ki; availk-i.first = pi; /将剩余块插入相应子表将剩余块插入相应子表 patag = 1; pakval = k(i); / else return pa; / AllocBuddy308.48.4 伙伴系伙伴系统统+例子：假设分配前的可利用空间表的状态如下图所示。若2k-1n2k-1，又第k1个子表不空，则只要删除此链表中第一个结点并分配给用户即可；分配前的表分配前的表202k-12m0 K2k0 K0 K318.48.4 伙伴系伙伴系统统若2k-2 n 2k-1-1，此时由于结点大小为2k-1的子表为空，则需从结点大小为2k的子表中取出一块，将其中一半分配给用户，剩余的一半作为一个新结点插入在结点大小为2k-1的子表中，如下图所示。(b) 分配后的表分配后的表202k-12m2k0 K0 K0 K-1328.48.4 伙伴系伙伴系统统若2k-i-1 n 2k-i1（i为小于k的整数），并且所有结点小于2k的子表均为空，则同样需从结点大小为2k的子表中取出一块，将其中2k-i的一部分分配给用户，剩余部分分割成若干个结点分别插入在结点大小为2k-i、2k-i+1、2k-1的子表中。338.48.4 伙伴系伙伴系统统+回收算法伙伴：是指由同一个大的空闲块分裂成的两个大小相等的存储区，这两个由同一大块分裂出来的小块就称之“互为伙伴”。起始地址为p，大小为2k的内存块，其伙伴的起始地址为： p + 2k (若若p MOD 2k+1 = 0)buddy (p, k) = p2k (若若p MOD 2k+1 = 2k)348.48.4 伙伴系伙伴系统统+算法思想回收空闲块时，首先判别其伙伴释放为空闲块，若否，则只要将释放的空闲块简单插入在相应子表中即可；若是，则需在相应子表中找到其伙伴并删除之，然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中去。+例子例如，假设整个可利用内存区大小为2101024（地址从0到1023），则大小为28，起始地址为512的伙伴块的起始地址为768；大小为27，起始地址为384的伙伴块的起始地址为256。35习题习题+本章习题参见教师网页：http:/staff.ustc.edu.cn/leeyi36