数据结构》课件C语言08.ppt

第*页 边界标识法由于在每个结点的头部和底部设立了标识域，使得在回收用户释放的内存块时，很容易判别与它毗邻的内存区是否为空闲块，且不需要查询整个可利用空间表便能找到毗邻的空闲块与其合并之； 边 界 标 识 法 再者，由于可利用空间表上结点既不需依结点大小有序，也不需依结点地址有序，则释放块插入时也不需查找链表。 由此，不管是哪一种情况，回收空闲块的时间都是个常量，和可利用空间表的大小无关。唯一的缺点是增加了结点底部所占的存储量。 伙伴系统(Buddy System)是操作系统中用到的另一种动态存储管理方法。所谓伙伴系统是指存储区中有一定地址关系且容量相等的一对存储块。伙伴系统中为避免出现许多明显的链域，使用了隐含的寻址规则，它是伙伴系统可用性的基础。如果知道某存储块的地址和容量，也就能够确定它的伙伴存储块。这就要求并约定存储区中的所有存储块容量都必须是2的幂。 在伙伴系统中，无论是占用块或空闲块，其大小均为2的幂次。当用户申请n个字的存储区，则分配的占用块为2k个字，这里k满足2k-1＜n≤2k. 第*页 伙 伴 系 统 可利用空间表的结构 伙伴系统中的可利用空间表由若干个子表组成，每个子表是一个双向循环链表。对于总内存空间为2m字的一个系统，可以有m+1个这样的子表，它们以向量形式连接在一起。 双向循环链表的结点形式 第*页 header：结点头部（设仅占1个字） llink,rlink：指针域，分别指向同一链表中该结点的前驱、后继结点 tag：标志域，tag=0表示空闲块，tag=1表示占用块 kval：k值域，满足存储块大小为2k字 space：地址连续的内存空间，其大小为2k－1字 llink tag=0 kval rlink space header 图8.8 伙伴系统中的 可利用空间表 (a) 空闲块的结点结构 伙 伴 系 统 第*页 示例1 伙伴系统中可利用空间表（设整个内存区是一个大小为2m的空闲块）的结构及初始状态示意如下 20 ∧ 21 ∧ · · · · · · 2k ∧ · · · · · · 2m freelist 0 1 k m nodesize first m 0 llink tag kval rlink 图8.8 伙伴系统中的可利用空间表 (b) 表的初始状态 伙 伴 系 统 第*页 伙伴系统中可利用空间表的数据结构类型定义如下 #define M 16 //可利用空间总容量 typedef struct WORD{ WORD *llink; int tag; int kval; WORD *rlink; OtherType other; }WORD, Head; typedef struct HeadNode{ int nodesize; WORD *first; } FreeList[M+1]; 伙 伴 系 统 分配算法 伙伴系统分配算法的基本约定： (1) 分配存储块时其容量一律按照2的幂给予满足。如果用户请求分配n字，则伙伴系统将给予容量为2k的一块存储空间，它满足关系2k-1 n ≤2k。而已经分配的 2k－n这个余数称为内部碎片（设n不是2的幂），它是个小小的浪费； 第*页 伙 伴 系 统 (2) 所有容量为2k的空闲存储块都链接在一个链表中，因此，对于总容量为2m的伙伴系统，将所有m+1个链表； (3) 假定存储区初始状态是容量为2m的一个单一空闲块，其内存地址是0 ~ 2m－1。 伙伴系统的分配过程：设用户提出大小为n的内存请求，则在可利用表上寻找结点大小与n相匹配的子表，(1)若此子表非空，则将该子表中任意一个结点（可取第一个结点）分配之；(2)若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，将其中一部分分配给用户，而将剩余部分插入至相应的子表中 第*页 示例2 伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配容量为2k-1）。初始状态如右图所示 伙 伴 系 统 需要分配大小为n的内存。 2k-1 ∧ 2k · · · · · · 2m k 0 k 0 k 0 … 20 (1)如果2k-1 n = 2k-1 且k+1个子表不为空，直接在k+1链表中分配。 2k-1 ∧ 2k · · · · · · 2m k 0 k 0 … 20 第*页 示例2 伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配容量为2k-1）。初始状态如右图所示 伙 伴 系 统 需要分配大小为n的内存。 2k-1 ∧ 2k · · · · · · 2m k 0