数据结构C语言08.pptx

内容和要求可利用空间表及分配方法边界标识法伙伴系统无用单元收集存储紧缩第1页内容和要求 可利用空间表、边界标识法、伙伴系统和无用单元收集。要求掌握可利用空间表及分配办法。重点 可利用空间表及分配。第1页/共53页动态存储管理的基本问题及方法 存储管理是一个既复杂而又重要的问题。在后续课程操作系统和编译技术（或方法、原理）中，将对其作较深入的研究。在数据库技术中，也涉及大量有关存储管理的问题。本章仅就动态存储管理方面一些基本技术进行讨论。第2页 在以往的算法描述中，有关存储分配请求、存储回收等项工作往往一带而过，好比是存储“自动满足”又 “自动回收”。偶尔亦考虑某一数据结构下判断是否溢出或者是否释放内存空间等问题。这是必要的，主要是为了把当时的重点和核心放在研究数据的逻辑特性、物理表示、算法描述与分析上，而对有关存储管理的问题作了一定的简化。第2页/共53页动态存储管理的基本问题(1)如何按用户提出的“请示”分配内存？(2)如何回收那些用户不再使用而“释放”的内存，以备新的“请示”产生时重新进行分配？第3页(1)由用户来解决；(2)由系统来解决；(3)由系统和用户共同解决。存储管理问题的解决途径存储管理问题的解决途径动态存储管理的基本问题及方法第3页/共53页在计算机系统中，存储管理的分级 (1)操作系统为进程分配所需要的存储空间，以便能在机器上运行。一旦运行结束从系统撤离时，操作系统就回收进程所使用的空间。此类存储管理问题将在操作系统课程中讨论。第4页动态存储管理的基本问题及方法 (2)进程对数据结构分配及回收存储空间，例如编译进程为变量、数组以及各种表格分配、回收空间。此类存储管理问题将在编译方法课程中讨论。(3)数据结构中，对某结构中的元素或子结构分配、回收存储空间。此类存储管理问题将是数据结构课程研究的范畴。下面仅限于在数据结构一级上研究存储管理的方法。但其基本思想和方法亦完全适用于其他两个级别。第4页/共53页一些有关存储管理的重要问题 (1)由谁来负责存储空间的分配与回收？是用户自身，还是由系统的一个专门子系统为用户分配并发现不再使用的空间而加以回收？第5页 (2)分配和释放存储空间的单位是相同还是有大有小？(3)系统何时回收空闲的空间？是及时回收还是定期回收或当存储空间用完时才去回收？(4)是否考虑存储碎片的紧凑问题？(5)当请示存储空间时，满足该请示的最好分配策略是什么？是寻找容量大致相当的存储块给予，还是不加选择地依次给一块至少能满足的空间？(6)怎样安排空闲存储块的次序？随机排列或按地址排列或按容量大小排列？动态存储管理的基本问题及方法第5页/共53页两个术语占用块 称已分配给用户使用的地址连续的内存区为占用块。在不同的动态存储管理系统中，请求分配的内存量大小不同，可能小到几个字节，多至若干k字节。但系统每次分配给用户的都是一个地址连续的内存区。第6页u1u2u3u4u5u6u7u8u1u3u4u6u8(b)(b)系统运行若干时间之后系统运行若干时间之后(a)(a)系统运行初期；系统运行初期；图图8.1 8.1 动态存储分配过程中的内存状态动态存储分配过程中的内存状态示例1 系统运行期间，动态存储分配过程的初期及系统运行一段时间后的状态示意如下l空闲块 称未曾分配的、地址连续的内存区为空闲块或可利用空间块。不管怎么样的动态存储管理系统，在刚开始工作时，整个内存区是一个空闲块（在编译系统中称之为堆，即堆区域）。动态存储管理的基本问题及方法空闲块占用块此时用户再次请求分配内存，系统将怎样分配？第6页/共53页第7页两种分配策略：两种分配策略：(1)(1)系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区是否已空闲，直到分配无法进行，才回收所有空闲块，并重新组织内存，将所区是否已空闲，直到分配无法进行，才回收所有空闲块，并重新组织内存，将所有空闲的内存区联接成一个大的空闲块；有空闲的内存区联接成一个大的空闲块；10,00015,000空 闲31,0008,000空 闲59,00041,000空 闲起始地址起始地址内存块大小内存块大小使用情况使用情况目录表目录表 (b)(b)动态存储管理的基本问题及方法 (2)用户一旦运行结束，便将它所占内存区释放成为空闲块，每当新用户请求分配内存时，系统巡视整个内存区中所有空闲块，从中找出一个合适者分配之。此时，系统需建立一张记录所有空闲块的可利用空间表（目录表或链表）。10,00010,00025,00025,00031,00031,00039,00039,00059,00059,00099,99999,999内存状态内存状态 (a)(a)示例1 可利用空间表的图示形式链链 表表 (c)(c)15,00008,000041,000 031,00031,00059,00059,00010,00010,000avav图图8.2 8.2 动态存储管理过程中的内存状态和可利用空间表动态存储管理过程中的内存状态和可利用空间表第7页/共53页可利用空间表及分配方法可利用空间表中包含所有可分配的空闲块，每一块是链表中的一个结点。当用户请示分配时，系统从可利用空间表中删除一个结点分配之；当用户释放其所占内存时，系统即回收该内存区并将它插入到可利用空间表中。第8页可利用空间表的结构形式结构形式一：结点均含大小相同的空闲块。可利用空间表可以有下列三和不同的结构形式：若系统运行期间所有用户请求分配的存储量大小相同，则系统开始运行时，将归它使用的内存区按所需大小分割成若干大小相同的块，并用指针链接成一个可利用空间表。分配时取表头结点，回收时按插表头形式。这种情况下的可利用空间表实际是一个链栈。是一种最简单的动态存储管理的方式。第8页/共53页第9页示例示例22 有三种大小结点（设结点大小分别为有三种大小结点（设结点大小分别为2,4,82,4,8个字）的可利用空间表的结点结构及个字）的可利用空间表的结点结构及其可利用空间表。其可利用空间表。结构形式二：结构形式二：建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结点大小，一般成倍数关系。点大小，一般成倍数关系。可利用空间表及分配方法tagtagtypetypelinklinkspacespace0 0 空闲块空闲块1 1 占用块占用块0 0 结点大小的结点大小的22个字个字1 1 结点大小的结点大小的44个字个字2 2 结点大小的结点大小的88个字个字tag=tag=type=type=(a)结点结构；图图8.3 8.3 有三种大小结点的可利用空间表有三种大小结点的可利用空间表000000000000 001100110011 002200220022 av2av2av4av4av8av8(b)可利用空间表分配过程？第9页/共53页第10页结构形式二：结构形式二：建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结点大小，一般成倍数关系。点大小，一般成倍数关系。可利用空间表及分配方法分配过程？根据用户请求空间的大小，到相应的空闲表中取结点。若该空闲表为空，则到较大结点的链表中取一结点，把它一分为二，一部分分配给用户，另部分插入到结点较小的空闲表中。产生什么结果？结点较大链表中的结点，不断一分为二，很容结点较大链表中的结点，不断一分为二，很容易用完，所以回收时，必须有易用完，所以回收时，必须有“紧缩聚合紧缩聚合”的的过程。过程。第10页/共53页第11页如何分配？结构形式三：结构形式三：结点所包含空闲块的大小可随请求而变。通常，操作系统中结点所包含空闲块的大小可随请求而变。通常，操作系统中的可利用空间表属于这种类型。的可利用空间表属于这种类型。其中其中 tagtag：标志位，标志位，tag=0tag=0表示空闲块，表示空闲块，tag=1tag=1表示占用块表示占用块 sizesize：空闲块的存储容量：空闲块的存储容量 linklink：链接下一个结点的指针域、链接下一个结点的指针域、spackspack：一片地址连续的内存区域一片地址连续的内存区域可利用空间表及分配方法tagtagsizesizelinklinkspacespace 结点结构的一般形式图8.4 空闲块的大小随意的结点结构若用户需求量为n，链表中仅有一块其容量mn，则分割出大小为n的部分分配给用户，剩余大小为m-n的部分作为一个结点留在链表中（只要把size改小就行）。问题：若空闲块链表中有若干个大小不小于n的结点，该分配哪一个？分配策略？三种分配策略：首次拟合法；最佳拟合法；最差拟合法。第11页/共53页分配策略一：首次拟合法从空闲块链表的表头指针开始查找，找出首先能满足请求容量的存储块，将其中一部分分配给用户。可利用空间表本身既不按结点的初始地址有序，也不按结点的大小有序。在回收时，只要将释放的空闲块插入在链表的表头即可。第12页分配给用户的占用块分配给用户的占用块7,0007,0001118,00018,000这种方法需对空闲块链表的结点检测的平均次数从1n不等。所以，首次拟合法为了满足一次请示其平均检测次数小于n/2。示例3 就示例1的可利用空间表（链表），设有用户U9进入系统并申请7千字内存，则按首次拟合法，有15,00015,000008,0008,0000041,00041,000 0031,00031,00059,00059,00010,00010,000avav 图图8.5 8.5 结点大小随意的可利用空间表结点大小随意的可利用空间表(a)(a)按首次拟合原则进行分配按首次拟合原则进行分配从高位开始分8,000第12页/共53页分配策略二：最佳拟合法从空闲块链表中找出能满足用户请求容 量的最小空闲块。显然这是一种较好的方法，但为了满足某个请示分配，需要对空闲块链表从头至尾扫描，时间开销大。第13页分配给用户的占用块分配给用户的占用块7,0007,0001132,00032,000图图8.5 8.5 结点大小随意的可利用空间表结点大小随意的可利用空间表(b)(b)按最佳拟合原则进行分配按最佳拟合原则进行分配15,00015,000008,0008,0000041,00041,000 0031,00031,00059,00059,00010,00010,000avav示例5 上例，若采用最佳拟合法，则可得最佳空闲块从高位开始分1,000优点：尽可能保证较大的空闲块不被细分。以满足较大的空间请求。缺点：有可能使剩余的空闲块容 量变得太小，以至于不能满足任何请求。第13页/共53页第14页 为了避免每次分配都要扫视整个链表，可以改造空闲块链表的结点排为了避免每次分配都要扫视整个链表，可以改造空闲块链表的结点排列顺序，列顺序，即以结点的容量由小到大排列即以结点的容量由小到大排列。这样为了满足某个请求分配，则。这样为了满足某个请求分配，则平均检测结点的数目只是链表结点个数一半即可。然而在这种情况下，将平均检测结点的数目只是链表结点个数一半即可。然而在这种情况下，将任一空闲块插入至空闲块链表的一半位置也需要平均检测链表的一半结点。任一空闲块插入至空闲块链表的一半位置也需要平均检测链表的一半结点。而不按块容量大小排列的空闲块链表，回收算法中不需要做检测工作。而不按块容量大小排列的空闲块链表，回收算法中不需要做检测工作。分配策略二：最佳拟合法第14页/共53页分配策略三最差拟合法其指导思想是每次都用空闲块链表中最大的空闲块去满足请求分配，所以若链表中诸结点不是按容量大小排列的话，则每次分配都扫描整个链表，即检测n次。但是，如果将链表结点按空闲块容 量的不增次序排列，则满足一次请求分配仅需检测一次即可。而回收一个空闲块将其插入空闲块链表时，同样需平均检测n/2次。第15页若按结点容量自大至小有序链接诸空闲块，则分配时仅需删除第一个结点，并将其中一部分分配给用户，剩余部分作为一个新的结点插入到链表适当位置。三种方法分配、回收平均检测次数列列表如下第15页/共53页边 界 标 识 法 边界标识法(Boundary Tag Method)是操作系统中用以在运行期间对用户所请求的随意内存块大小进行动态分区分配的一种存储管理方法。空闲块链表是个双向循环链表结构。分配策略或采用首次拟合法，或采用最佳拟合法。第16页系统特点：在每个内存区的头部和底部两个边界上分别设有标志域，以标识该内存区域为占用块或空闲块。在回收时，对物理上相邻的空闲块进行全并，组合成一个尽可能大的、地址连续的空闲块。第16页/共53页可利用空间表的结构 边界标识法中的结点结构其中 head：结点的头部地址 foot：结点的底部地址 space：一组地址连续的待分配存储单元 tag：标志域，tag=0表示空闲块，tag=1表示占用块 size：整个结点的大小，包括头部header和底部footer所占空间（设各占1个字），但在分配时忽略不计 llink：指向双向循环链表中本结点的前趋结点的指针 rlink：指向双向循环链表中本结点的后继结点的指针 uplink：指向本结点的指针，其值即为该内存块的首地址第17页边 界 标 识 法spacellinktagsizerlinkuplinktaghead：foot：第17页/共53页第18页typedef struct WORDtypedef struct WORD union union WORD*llink,WORD*llink,/头部域，指向前驱头部域，指向前驱 WORD*uplink;WORD*uplink;/底部域，指向本结点头部底部域，指向本结点头部 int tag;int tag;/块标志块标志 int size;int size;/块大小块大小 WORD*rlink;WORD*rlink;/后继结点后继结点 OtherType other;OtherType other;/其它部分其它部分 WORD,head,foot,*Space;WORD,head,foot,*Space;#define FootLoc(p)(p+p-size-1)#define FootLoc(p)(p+p-size-1)在此双向循环链表中在此双向循环链表中不设表头结点不设表头结点，表头指针表头指针pavpav可以指向可以指向任一个任一个结点。结点。0000100000100000pavpav示例6 一个占有100k内存空间的系统在运行开始时的可利用空间表的初始状态如下所示边界标识法 数据结构第18页/共53页边界标识法分配算法 设采用首次拟合法进行分配，并约定第19页(1)选定一个适当的常量e，当mne（用户请求分配容量为n的空闲块，而找到的待分配空闲块的容量mn）时，就将容量为m的空闲块整块地分配给用户；否则，若有mne，则仅分配其中n个字的内存块；以免产生“空闲碎屑”(2)在每次分配之后，令指针指向刚进行过分配的结点的后继结点；(3)将Space型的变量视作其值为存储块的头部地址的简单变量，允许作加、减运算，即假定可按地址来作加、减运算以求得新地址来表示所指向的时针。故有 p：存储块首地址 p-size：地址为p的存储块头部中的结点大小域，其值约等于同一存储块中spack空间的容量 p-tag：该存储块头部的标志域 (p+p-size-1)-tag：同一存储块底部的标志域第19页/共53页第20页Space AllocBoundTag(Space&pav,int n)Space AllocBoundTag(Space&pav,int n)/*n/*n为请求分配的存储量，若系统中尚有足够大的空间可分配，则返回为请求分配的存储量，若系统中尚有足够大的空间可分配，则返回pp值指示值指示分配给用户的存储块的地址，否则返回分配给用户的存储块的地址，否则返回NULLNULL，若进行分配后的可利用空间表不若进行分配后的可利用空间表不空，则空，则pavpav指向表中刚进行过分配的结点的后继结点指向表中刚进行过分配的结点的后继结点*/for(p=pav;p&p-size rlink!=pav)for(p=pav;p&p-size rlink!=pav)p=p-rlink;p=p-rlink;/查找空闲块查找空闲块 if(!p|p-size size rlink;f=FootLoc(p);pav=p-rlink;/pav/pav指向指向pp的后继的后继 if(p-size n e)if(p-size n e)/分配整结点分配整结点 if(pav=p)pav=NULL;if(pav=p)pav=NULL;else else pav-llink=p-llink;pav-llink=p-llink;p-llink-rlink=pav;p-llink-rlink=pav;/删除已分配的结点删除已分配的结点 p-tag=f-tag=1;p-tag=f-tag=1;/修改分配结点的标志修改分配结点的标志 else else f-tag=1;p-size-=n;f=FootLoc(p);f-tag=1;p-size-=n;f=FootLoc(p);f-tag=0;f-uplink=p;f-tag=0;f-uplink=p;p=f+1;p=f+1;p-tag=1;p-size=n;p-tag=1;p-size=n;return p;return p;边界标识法分配算法描述第20页/共53页第21页 边界标识法分配算法描述示例7 某系统的可利用空间表从初始状态到运行若干时间后的状态以及进行再分配（7000字）后的状态，可用图示形式表示如下0000100000100000pavpav(a)(a)初始状态初始状态第21页/共53页第22页000015,00015,000pavpav00008,0008,000000041,00041,00010,00010,00031,00031,00059,00059,000(b)(b)运行若干时间后的状态运行若干时间后的状态图图8.6 8.6 某系统的可某系统的可利用空间表利用空间表11117,0007,000pp(c)(c)进行再分配进行再分配后的状态后的状态分配：分配：00008,0008,000pavpav00008,0008,000000041,00041,00010,00010,00031,00031,00059,00059,000第22页/共53页回收算法 一旦用户释放占用块，系统应立即回收以备新的请求产生时进行再分配。为了使物理地址相紧邻的空间闲块能结合成一个尽可能大的结点，需检查刚释放的占用块的左、右紧邻是否空闲块，若是则合并。第23页算法思想：设p指向用户释放的内存区的头部，则与其低地址紧邻的内存区的底部地址为 p-1，与其高地址紧邻的内存区的头部地址为 p+p-size。分四种情况：(1)释放块的左、右邻区均为占用块，即有(p-1)-tag=1&(p+p-size)-tag=1(2)释放块的左邻区为空闲块，右邻区为占用块，即有(p-1)-tag=0&(p+p-size)-tag=1(3)释放块的左邻区为占用块，右邻区为空闲块，即有(p-1)-tag=1&(p+p-size)-tag=0(4)释放块的左、右邻区均为空闲块，即有(p-1)-tag=0&(p+p-size)-tag=0第23页/共53页第24页则只需将该内存块简单地插入到则只需将该内存块简单地插入到pavpav所指向的结点之前（或之后）即可。所指向的结点之前（或之后）即可。000000001111qqpppavpav(1)释放块的左、右邻区均为占用块，即有(p-1)-tag=1&(p+p-size)-tag=100第24页/共53页第25页此时应将释放块与其紧邻的左邻区合并，即需要改变左邻空闲块的结点，增加结点的此时应将释放块与其紧邻的左邻区合并，即需要改变左邻空闲块的结点，增加结点的sizesize域的值且重新设置结点的底部。域的值且重新设置结点的底部。n=p-size;n=p-size;s=(p-1)-uplink;s=(p-1)-uplink;/s/s为左邻空闲块的头部地址为左邻空闲块的头部地址s-size+=n;s-size+=n;/设置新的空闲块大小设置新的空闲块大小f=p+n+1;f-uplink=s;f-tag=0;f=p+n+1;f-uplink=s;f-tag=0;/设置新的空闲块底部设置新的空闲块底部00ss11001111ss2211pp释放块释放块左邻块左邻块右邻块右邻块p+p-sizep+p-sizes1+s2P-1P-1(2)释放块的左邻区为空闲块，右邻区为占用块，即有(p-1)-tag=0&(p+p-size)-tag=10第25页/共53页第26页1111000000ss11ppp+p-sizep+p-size释放块释放块左邻块左邻块右邻块右邻块P-1P-1t=p+p-size;t=p+p-size;/t/t为右邻空闲块的头部地址为右邻空闲块的头部地址p-tag=0;p-tag=0;/p/p为合并后的结点的头部地址为合并后的结点的头部地址q=t-llink;q=t-llink;/q/q为为tt结点在可用空间链表中的前驱结点的头部地址结点在可用空间链表中的前驱结点的头部地址p-llink=q;q-rlink=p;p-llink=q;q-rlink=p;/q/q为为pp的前驱的前驱q1=t-rlink;q1=t-rlink;/q1/q1为为tt结点在链表中的后继结点的头部地址结点在链表中的后继结点的头部地址p-rlink=q1;q1-llink=p;p-rlink=q1;q1-llink=p;/q1/q1为为pp的后继的后继p-size+=t-size;p-size+=t-size;/新的空闲块大小新的空闲块大小FootLoc(t)-uplink=p;FootLoc(t)-uplink=p;/底部指针指向新结点的头部底部指针指向新结点的头部(3)释放块的左邻区为占用块，右邻区为空闲块，即有(p-1)-tag=1&(p+p-size)-tag=0由原来的右邻空闲块变成合并后的大空闲块时，结点的底部位置不变，但头部要变，由此，链表中的指针也要变。ttqqq1q1第26页/共53页第27页为使三个空闲块连接在一起成为一个大结点留在可利用空间表中，只要增加左邻空闲块为使三个空闲块连接在一起成为一个大结点留在可利用空间表中，只要增加左邻空闲块的的spacespace容量，同时在链表中删去右邻空闲块结点即可。容量，同时在链表中删去右邻空闲块结点即可。n=p-size;n=p-size;/n/n为释放块大小，设为为释放块大小，设为ss22s=(p-1)-uplink;t=p+p-size;s=(p-1)-uplink;t=p+p-size;/s/s指示左邻块，指示左邻块，tt指示右邻块指示右邻块q=t-llink;q1=t-rlink;q=t-llink;q1=t-rlink;/qq1/qq1s-size+=n+t-size;s-size+=n+t-size;/设置新结点中设置新结点中spactspact空间大小空间大小q-rlink=q1;q1-llink=q;q-rlink=q1;q1-llink=q;/删去右邻空闲块结点删去右邻空闲块结点FootLoc(t)-uplink=s;FootLoc(t)-uplink=s;/使新结点底部指针指向新结点的头部使新结点底部指针指向新结点的头部00ss110000ss3300ss22qqpp释放块释放块左邻块左邻块右邻块右邻块ssP-1P-1tts1+s2+s3(4)释放块的左、右邻区均为空闲块，即有(p-1)-tag=0&(p+p-size)-tag=0q1q1第27页/共53页第28页 边界标识法由于在每个结点的头部和底部设立了边界标识法由于在每个结点的头部和底部设立了标识域，使得在回收用户释放的内存块时，很容易判标识域，使得在回收用户释放的内存块时，很容易判别与它毗邻的内存区是否为空闲块，且不需要查询整别与它毗邻的内存区是否为空闲块，且不需要查询整个可利用空间表便能找到毗邻的空闲块与其合并之；个可利用空间表便能找到毗邻的空闲块与其合并之；边 界 标 识 法再者，由于可利用空间表上结点既不需依结点大小再者，由于可利用空间表上结点既不需依结点大小有序，也不需依结点地址有序，则释放块插入时也不需有序，也不需依结点地址有序，则释放块插入时也不需查找链表。查找链表。由此，不管是哪一种情况，回收空闲块的时间都是由此，不管是哪一种情况，回收空闲块的时间都是个常量，和可利用空间表的大小无关。唯一的缺点是增个常量，和可利用空间表的大小无关。唯一的缺点是增加了结点底部所占的存储量。加了结点底部所占的存储量。第28页/共53页 伙伴系统(Buddy System)是操作系统中用到的另一种动态存储管理方法。所谓伙伴系统是指存储区中有一定地址关系且容量相等的一对存储块所谓伙伴系统是指存储区中有一定地址关系且容量相等的一对存储块。伙伴系统中为避免出现许多明显的链域，使用了隐含的寻址规则，它是伙伴系统可用性的基础。如果知道某存储块的地址和容量，也就能够确定它的伙伴存储块。这就要求并约定存储区中的所有存储块容量都必须是2的幂。在伙伴系统中，无论是占用块或空闲块，其大小均为2的幂次。当用户申请n个字的存储区，则分配的占用块为2k个字，这里k满足2k-1n2k.第29页伙伙 伴伴 系系 统统第29页/共53页可利用空间表的结构 伙伴系统中的可利用空间表由若干个子表组成，每个子表是一个双向循环链表。对于总内存空间为2m字的一个系统，可以有m+1个这样的子表，它们以向量形式连接在一起。双向循环链表的结点形式第30页header：结点头部（设仅占1个字）llink,rlink：指针域，分别指向同一链表中该结点的前驱、后继结点tag：标志域，tag=0表示空闲块，tag=1表示占用块kval：k值域，满足存储块大小为2k字space：地址连续的内存空间，其大小为2k1字llinkllinktag=0tag=0kvalkvalrlinkrlinkspacespaceheaderheader图图8.8 8.8 伙伴系统中的伙伴系统中的可利用空间表可利用空间表(a)(a)空闲块的结点结构空闲块的结点结构伙伙 伴伴 系系 统统第30页/共53页第31页示例示例11 伙伴系统中可利用空间表（设整个内存区是一个大小为伙伴系统中可利用空间表（设整个内存区是一个大小为22mm的空闲块）的结构及的空闲块）的结构及初始状态示意如下初始状态示意如下2200 2211 22kk 22mmfreelistfreelist0011kkmmnodesize firstnodesize firstmm00llinkllinktagtagkvalkvalrlinkrlink图图8.8 8.8 伙伴系统中的可利用空间表伙伴系统中的可利用空间表 (b)(b)表的初始状态表的初始状态伙伙 伴伴 系系 统统第31页/共53页第32页 伙伴系统中可利用空间表的数据结构类型定义如下伙伴系统中可利用空间表的数据结构类型定义如下#define M 16 /#define M 16 /可利用空间总容量可利用空间总容量typedef struct WORDtypedef struct WORD WORD*llink;WORD*llink;int tag;int tag;int kval;int kval;WORD*rlink;WORD*rlink;OtherType other;OtherType other;WORD,Head;WORD,Head;typedef struct HeadNodetypedef struct HeadNode int nodesize;int nodesize;WORD*first;WORD*first;FreeListM+1;FreeListM+1;伙伙 伴伴 系系 统统第32页/共53页分配算法 伙伴系统分配算法的基本约定：(1)分配存储块时其容量一律按照2的幂给予满足。如果用户请求分配n字，则伙伴系统将给予容量为2k的一块存储空间，它满足关系2k-1 n 2k。而已经分配的 2kn这个余数称为内部碎片（设n不是2的幂），它是个小小的浪费；第33页伙伙 伴伴 系系 统统(2)所有容量为2k的空闲存储块都链接在一个链表中，因此，对于总容量为2m的伙伴系统，将所有m+1个链表；(3)假定存储区初始状态是容量为2m的一个单一空闲块，其内存地址是0 2m1。伙伴系统的分配过程：伙伴系统的分配过程：伙伴系统的分配过程：伙伴系统的分配过程：设用户提出大小为设用户提出大小为nn的内存请求，则在可利用表上寻找的内存请求，则在可利用表上寻找结点大小与结点大小与nn相匹配的子表，相匹配的子表，(1)(1)若此子表非空，则将该子表中任意一个结点（可取第一个若此子表非空，则将该子表中任意一个结点（可取第一个结点）分配之；结点）分配之；(2)(2)若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，将其中一部分分配给用户，而将剩余部分插入至相应的子表中空闲块，将其中一部分分配给用户，而将剩余部分插入至相应的子表中第33页/共53页第34页示例示例22 伙伴系统可利用空间表在进行分伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配配用户请求内存时的状态变化（设分配容量为容量为22k-1k-1）。）。初始状态如右图所示初始状态如右图所示伙伙 伴伴 系系 统统需要分配大小为n的内存。22k-1k-1 22kk 22mmkk00kk00kk0020(1)如果2k-1 n=2k-1 且k+1个子表不为空，直接在k+1链表中分配。22k-1k-1 22kk 22mmkk00kk0020第34页/共53页第35页示例示例22 伙伴系统可利用空间表在进行分伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配配用户请求内存时的状态变化（设分配容量为容量为22k-1k-1）。）。初始状态如右图所示初始状态如右图所示伙伙 伴伴 系系 统统需要分配大小为n的内存。22k-1k-1 22kk 22mmkk00kk00kk0020(2)如果2k-2 n=2k-1-1且k(即2k-1)个子表为空，则需要从结点大小为2k取出一般分配，另一半作为新结点插入到结点大小为2k-1的子表中。kk2200 22k-1k-122kk22mm00K-1K-100kk00第35页/共53页第36页伙伙 伴伴 系系 统统一般情况：假如对于用户需求n，有 2k-i-1n2k-i-1 其中i为小于k的一个整数，并且所有结点小于2k的子表均为空，此时如何进行分配？同样地，需从结点大小为2k的子表中取出一块，将其中2k-i的一小部分分配给用户，剩余部分分割成若干个结点分别插入在结点大小为2k-i,2k-i+1,2k-1的子表中。kk2200 22k-1k-122kk22mm00K-1K-100kk00第36页/共53页第37页示例示例3 3 对于需要内存容量为对于需要内存容量为n=7n=7的用户，假定所有容量为的用户，假定所有容量为2233=8,2=8,244=16,2=16,255=32=32的链的链表均为空表均为空，而，而2266=64=64的链表为非空，则将该表中的一个结点进行分配与分割，设其的链表为非空，则将该表中的一个结点进行分配与分割，设其起始地址为起始地址为pp，则，则 占用块（始地占用块（始地pp）：分配给用户）：分配给用户；空闲块空闲块11（始地（始地p+8p+8）：插入至）：插入至2233=8=8的子表；的子表；空闲块空闲块22（始地（始地p+16)p+16)：插入至：插入至2244=16=16的子表；的子表；空闲块空闲块33（始地（始地p+32)p+32)：插入至：插入至2255=32=32的子表；的子表；2k=64P+8P+16P+32占用块空闲块1空闲块2空闲块3p伙伙 伴伴 系系 统统大小7，碎片为1第37页/共53页第38页伙伴系统分配算法描述伙伴系统分配算法描述Space alloc_buddy(FreeList&avail,int n)Space alloc_buddy(FreeList&avail,int n)/*avail0.m/*avail0.m为可利用空间表；为可利用空间表；nn为用户请求分配的存储量，设系统尚有空间可分为用户请求分配的存储量，设系统尚有空间可分配时，返回配时，返回papa值指示分配给用户的占用块的初始地址，否则返回值指示分配给用户的占用块的初始地址，否则返回NULL*/NULL*/for(k=0;k=m&(availk.nodesizen+1|!availk.first)for(k=0;k=m&(availk.nodesize m)return NULL;if(k m)return NULL;/没有满足，返回没有满足，返回 elseelse pa=availk.first;pa=availk.first;pre=pa-llink;suc=pa-rlink;pre=pa-llink;suc=pa-rlink;/指向前驱和后继指向前驱和后继 if(pa=suc)availk.first=NULL;/if(pa=suc)availk.first=NULL;/分配后为空表分配后为空表 elseelse /删除删除papa结点结点 pre-rlink=suc;suc-llink=pre;availk.first=suc;pre-rlink=suc;suc-llink=pre;availk.first=suc;for(i=1;availk-i.nodesize=n+1;i+)for(i=1;availk-i.nodesize=n+1;i+)pi=pa+2 pi=pa+2(k-i)(k-i);pi-rlink=pi;pi-llink=pi;pi-rlink=pi;pi-llink=pi;pi-tag=0;pi-kval=k i;availk-i.first=pi pi-tag=0;pi-kval=k i;availk-i.first=pi /剩余块插入子表剩余块插入子表 pa-tag=1;pa-kval=k (i-);pa-tag=1;pa-kval=k (i-);return pa;return pa;/算法算法8.28.2伙伙 伴伴 系系 统统第38页/共53页回收算法 回收过程：当用户释放不再使用的空闲块时，系统需将新的空闲块插入到可利用空间表中去。可能要对地址相邻的空闲块进行合并以构成较大块。但在伙伴系统中，仅考虑互为伙伴的两个空闲块的合并。对于起始地址为p，大小为2k的内存块，欲求其伙伴内存块的起始地址，有 p+2k，若p MOD 2k+1=0 buddy(p,k)=(*)p-2k，若p MOD 2k+1=2k 第39页示例4 设整个可利用内存区大小为210=1024（地址从0到1023）。则由下图计算 大小为28，起始地址为29(=512)的内存块，其伙伴块的起始地址为 ，而大小为27，起始地址为384(=28+27)的内存块，其伙伴块的起始地址为 。22772288 0025625638438451251276876810231023伙伙 伴伴 系系 统统768(29+28)256(=28)伙伴块伙伴块伙伴块伙伴块第39页/共53页 伙伴系统方法的算法分析：存储动态分配和回收的伙伴系统方法的效率是很高的，它是存储管理中最快捷的一种分配和回收存储块的方法。然而这种速度快捷的优点是以增加存储碎片（内部碎片）为代价的。由于请求容量不足2k时，只能分配2k这样大的存储块，就产生了多余的存储空间。第40页伙伙 伴伴 系系 统统2k第40页/共53页无用单元收集 无用单元是指那些用户不再使用而系统没有回收的结构和变量。第41页