数据结构第8章

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