数据结构(第8章)

数据结构（C语言版）目录第8章动态存储管理8.1概述8.2可利用空间表及分配方法8.3边界标识法8.4伙伴系统8.1概述动态存储管理研究的基本问题：系统如何按用户的要求分配内存；当用户使用完毕，系统如何回收内存。“占用块”：分配给用户使用的地址连续的内存区。“空闲块”：未曾分配的地址连续的内存区，也称“可利用空间块”。可利用空间表：把可利用空间表看作是一个“存储池”，它有以下三种不同的结构形式：(1)系统运行期间用户请求分配的存储量大小相同；(2)系统运行期间用户请求分配的存储量有几种大小的规格；(3)系统在运行期间分配给用户的内存块大小不固定。U1U2U3U4U5U6U7U8U1U3U4U6U8系统运行初期的内存状态系统运行若干时间之后的内存状态动态存储分配过程中的内存状态8.1概述系统继续从高地址空闲块进行分配，直至无法分配，再去回收用户释放的内存，重组内存，并分配。用户一旦运行结束，便将其占用的内存释放成空闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。由此，系统需建立一张记录所有空闲块的“可利用空间表”，此表的结构可以是“目录表”，也可以是“链表”。运行中如何分配内存8.1概述2500039000010000310005900099999内存状态起始地址内存块大小使用情况1000015000空闲310008000空闲5900041000空闲目录表8.1概述链表01500010000080003100004100059000av8.1概述8.2可利用空间表及分配方法1.可利用空间表的结点结构(1)结点大小相同(2)结点大小不同，但只有几种规格(3)结点大小不等2.可利用空间表的分配策略(1)首次拟合法(2)最佳拟合法(3)最差拟合法3.各种分配策略的比较用户所需内存量大小相同，可以把内存分为大小相同的若干块，将各块链接起来，由于表中结点大小相同，则分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户释放内存时，系统只要将用户释放的空闲块插入在表头即可，因此这种情况下的可利用空间表实质上是一个链栈。结点大小相同8.2可利用空间表及分配方法用户所需内存量不同，但只允许在几种规格间选取。在此情况下可建立若干个可利用空间表，同一链表中的结点大小相同。用加标记办法区分占用块或空闲块（tag=0,1）。分配时按类型分配，所需类型没有时，向较大块的类型中去找，取出所需，剩余插入合适链表中；回收时将释放的空闲块插入到相应大小的链表的表头中。结点只有几种规格结点结构tagtypelinkvalue8.2可利用空间表及分配方法内存块大小不固定，只有一个链表。开始整个内存是一个空闲块。以后每个空闲块或占用块均用4个字段标记：tag，size，space，link。结点大小不等结点结构tagsizelinkspace8.2可利用空间表及分配方法从表头指针开始查找可利用空间表，将找到的第一个大小不小于n的空闲块的一部分分配给用户。可利用空间表本身既不按结点的初始地址有序，也不按结点的大小有序。回收时只要将释放的空闲块插入在链表的表头即可。首次拟合法8.2可利用空间表及分配方法1700001500010000080003100004100059000av例如：在以下链表中用首次拟合法分配7K内存分配0150001000008000100008.2可利用空间表及分配方法将可利用空间表中一个不小于n且最接近n的空闲块的一部分分配给用户。系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n且最接近n的空闲块进行分配。最佳拟合法8.2可利用空间表及分配方法1700001500010000080003100004100059000av例如：在以下链表中用最佳拟合法分配7K内存分配01500010000310000800001000310008.2可利用空间表及分配方法将可利用空间表中不小于n且最是链表中最大的空闲块的一部分分配给用户。最差拟合法8.2可利用空间表及分配方法1700001500010000080003100004100059000av例如：在以下链表中用最差拟合法分配7K内存分配01500010000310000800004100059000034000590008.2可利用空间表及分配方法首次拟合适合事先不掌握请求分配和释放信息的情况，分配时查询，释放时插入表头。最佳拟合法分配与回收都需要查询。分配时容易产生存储量小而无法利用的内存小碎片。这种分配策略适合请求分配内存大小较广的系统。最差拟合法要求结点从大到小排序，适合请求分配内存大小范围较窄的系统。分配时不需查询，回收时查询，以便插入到适当位置。各种分配策略比较8.2可利用空间表及分配方法8.3边界标识法系统将所有的空闲块链接在一个双重循环链表结构的可利用空间表中；分配可按首次拟合进行，也可按最佳拟合进行。系统的特点在于：在每个内存区的头部和底部两个边界上分别设有标识，以标识该区域为占用块或空闲块，使得在回收用户释放的空闲块时易于判别在物理位置上与其相邻的内存区域是否为空闲块，以便将所有地址连续的空闲存储区组合成一个尽可能大的空闲块。1.可利用空间表的结构headllinktagsizerlinkspacefootuplinktag存储单元空间大小标志域前驱后继标志域自身8.3边界标识法typedefstructWORD{//WORD:内存字类型union{//head和foot分别是结点的第一个字和最后的字WORD*llink;//头部域，指向前驱结点WORD*uplink;//底部域，指向本结点头部}inttag;//块标志，0:空闲，1:占用，头部尾部均有intsize;//头部域，块大小WORD*rlink;//头部域，指向后继结点OtherTypeother;//字的其它部分}WORD,head,foot,*Space;//*Space:可利用空间指针类型#defineFootLoc(p)p+p-size-1//指向p所指结点的底部C语言的类型描述如下:8.3边界标识法2.分配算法从表头指针pav所指结点开始，在可利用空间表中查找第一个不小于n的空闲块m即可分配。规则如下：(1)若m-n≤e(e是适当常量)，则将m全部分配给用户，否则只分配大小为n的内存块。为避免修改指针，约定将结点中的高地址部分分配给用户。(2)每次分配后，令pav指向刚进行分配的结点的后继结点。8.3边界标识法SpaceAllocBoundTag(Space&pav,intn){//若有不小于n的空闲块，则分配相应的存储块，并返回其首地址；否则//返回NULL。若分配后可利用空间表不空，则pav指向表中刚分配过的结//点的后继结点for(p=pav;p&&p-sizen&&p-rlink!=pav;p=p-rlink);//查找空闲块if(!p||p-sizen)returnNULL;//找不到，返回空指针else{//p指向找到的空闲块f=FootLoc(p);//指向底部pav=p-rlink;//pav指向*p结点的后继结点……returnp;//返回分配块首地址}//else}//AllocBountTagC语言的类型描述如下:8.3边界标识法if(p-size-n=e){//整块分配，不保留=e的剩余量if(pav==p)pav=NULL;//可利用空间表变为空表else{//在表中删除分配的结点pav-llink=p-llink;p-llink-rlink=pav;}//elsep-tag=f-tag=1;//修改分配结点的头部和底部标志}//ifelse{//分配该块的后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;//设置分配块头部}//else8.3边界标识法3.回收算法用户释放占用块，系统要立即回收。为使相邻的空闲块成为较大的结点，要查看左右邻是否为空闲块。共分4种情况：(1)空闲块的左右邻均为“占用块”：只需将空闲块插入可利用空间表中即可。(2)空闲块的左邻为“占用块”，右邻为空闲块：将空闲块和右邻空闲块合并，修改循环链表前驱后继指针、空闲块的size以及uplink等。8.3边界标识法(3)空闲块的右邻为“占用块”，左邻为空闲块：将空闲块和右邻空闲块合并，修改空闲块的size以及uplink等。(4)空闲块的左右邻均为空闲块：将三块空闲块合并，修改循环链表前驱后继指针、空闲块的size以及uplink等。8.3边界标识法p-tag=0;FootLoc(p)-uplink=p;FootLoc(p)-tag=0;if(!pav)pav=p-llink=p-rlink=p;else{q=pav-llink;p-rlink=pav;p-llink=q;q-rlink=pav-llink=p;pav=p;//令刚释放的结点为下次分配时的最先查询的结点}情况1算法描述如下:8.3边界标识法n=p-size;//释放块的大小s=(p-1)-uplink;//左邻空闲块的头部地址s-size+=n;//设置新的空闲块大小f=p+n-1;f-uplink=s;f-tag=0;//设置新的空闲块底部情况2算法描述如下:8.3边界标识法t=p+p-size;//右邻空闲块的头部地址p-tag=0;//p为合并后的结点头部地址q=t-llink;//q为*t结点在可利用空间表中的前驱结点的头部地址p-llink=q;q-rlink=p;//q指向*p的前驱q1=t-rlink;//q1为*t结点在可利用空间表中的后继结点的头部地址p-rlink=q1;q1-llink=p;//q1指向*p的后继p-size+=t-size;//新的空闲块的大小FootLoc(t)-uplink=p;//底部指针指向新结点的头部情况3算法描述如下:8.3边界标识法n=p-size;//释放块的大小s=(p-1)-uplink;//指向左邻块t=p+p-size;//指向右邻块s-size+=n+t-size;//设置新结点的大小q=t-llink;q1=t-rlink;//q!=q1q-rlink=q1;q1-llink=q;//删去右邻空闲块结点FootLoc(t)-uplink=s;//新结点底部指针指向其头部情况4算法描述如下:8.3边界标识法8.4伙伴系统在用户提出空间申请时，分配一块大小“恰当”的内存区给用户；反之，在用户释放内存区时即回收。和边界标识法不同的是，在伙伴系统中，无论是占用块或空闲块，其大小均为2的k次幂(k为某个正整数)。1.可利用空间表的结构headerllinktagkvalrlinkspace存储单元2的幂次k标志域前驱后继8.4伙伴系统#definem16//可利用空间总容量64k字的2的幂次，子表的//个数为m+1typedefstructWORD_b{WORD_b*llink;//指向前驱结点inttag;//块标志，0:空闲，1:占用intkval;//块大小，值为2的幂次kWORD_b*rlink;//头部域，指向后继结点OtherTypeother;//字的其它部分}WORD_b,head;//WORD:内存字类型typedefstructHeadNode{intnodesize;//该链表的空闲块的大小WORD_b*first;//该链表的表头指针}FreeList[m+1];//表头向量类型C语言的类型描述如下:8.4伙伴系统2.分配算法取大于等于所申请空间的最小的2的幂次，若正好有这么大的空闲块，则从该循环链表头摘下即可。否则，应对大于该2的幂次的最小空闲