8.4伙伴系统(1) 8.4伙伴系统(2) 伙伴系统(buddy system) ·可利用空间表的结构 ·与边界标识法类似 年define m16 typedef struet WORD!内存字类型 。不同点是：在伙伴系统中，无论是占用块或空闲块，其大小均为 2的k次幂(k为某个正蓝数) head llink tag kval rlink VORD *link:∥指向前狐结森 int tag:刀0空闲：占用】 。可利用空问表 细tka止∥块大小，值为2的罩次k space WORD*rink:指向后整蜂戒 ·若可利用内存喜量为2个字，则空闲换的大小只能是2、 OtherType other:∥字的其它年分 21、…、2m WORD.head: ·所有大小相同的空闲块建于一张子表中，每个子表是一个双重精 typedef struct HeadNode 环城表，可能有m+1个子表 2k-1 t nodesize;∥被链表的空闲块的大小 ·将m+1个表头指针用向量结构组织成一个表 2 WORD*s出城能表的表头糯针 3 FreeList[m+H:录头向量类型 2m 19/35 回 20/35 回 8.4伙伴系统(3) 8.4伙伴系统(4) ■分配算法（算法8.2P205) ·回收算法(P205,206) 银设用请求分配的存铺量为n, 假设用户释放的内存区的起始地址为，块的大小为2 ,若21<n<2北1，且第k+1个子表不空，则只要除此蛙表中第 一个结点并分配给用户即可 ·伙伴系统仅考虑互为“伙伴”的两个空闲块的归并 若22<n≤21-1，结点大小为21的子表为空，则从结点大小 为2必的子表中取出一块，将其中一半分配给用户，剩余的一半作为 伙伴：两个由同一大块分裂出来的小块就称为“互为 一个新结点插入在结点大小为21的子表中 伙伴”。假设即为大小为2k的空闲块的初始地址，且 ,若2+1<n<2L1(为小于k的整款)，并且所有结点小于2的子 pMOD2k+1=0,则初始地址为P和p+2的两个空 表均为空，则周样福从结点大小为2*的子表中取出一块，将其中 2~分配给用户，剩余部分分剂成若干个轴点分别插入在结点大小 闲块互为伙伴。 为2、21、、21的子表中。 21/35 图 22/35 图 8.4伙伴系统(5) 8.5无用单元收集(1) ,判别其伙伴是否为空闲块 ■8.2~8.4节讨论的存储管理系统中，用户必须明确给出 ·若是，则在相应子表中找到其伙伴并除之，然后再兴别合并 “请求”和“释放”的信息 后的空闲块的伙伴是否是空用块 →因为用户的硫漏或结构本身的原因致使系统在不恰当的 。若否，则只要将释放的空用块葡单插入在相应子表中即可 时候或没有进行回收而产生“无用单元”或“悬挂访问”的问 ,伙伴块的起始地址 题。 「p+2(若pMOD2=0) 。无用单元：那些用户不再使用而系统没有回收的结构和变量。 buddy(p,k)= p-2(若pMOD2=2) :p=malloc(size);..P=NULL; 。悬挂访问：访问已经被得放的结点 ▣对伙伴系统的评价 例：p=malloc(size);…q=p;free(pjia=*q 。优点：算法简单、速度快 因结构本身的特性，也会产生上述问夏 例如广义表的结构：共事子表（图8.9P207) ·峡点：由于只归并伙伴而容易产生醉片 图 24/35 图 44 19/35 8.4 伙伴系统(1) „ 伙伴系统(buddy system) „ 与边界标识法类似 „ 不同点是：在伙伴系统中，无论是占用块或空闲块，其大小均为 2的k次幂(k为某个正整数) „ 可利用空间表 „ 若可利用内存容量为2m个字，则空闲块的大小只能是20、 21、…、 2m „ 所有大小相同的空闲块建于一张子表中，每个子表是一个双重循 环链表，可能有m+1个子表 „ 将m+1个表头指针用向量结构组织成一个表 20/35 8.4 伙伴系统(2) „ 可利用空间表的结构 llink tag kval rlink space head #define m 16 typedef struct WORD{ // 内存字类型 WORD *llink; // 指向前驱结点 int tag; // 0-空闲; 1-占用 int kval; // 块大小,值为2的幂次k WORD *rlink; //指向后继结点 OtherType other; //字的其它部分 }WORD, head; typedef struct HeadNode{ int nodesize; // 该链表的空闲块的大小 WORD *first; //该链表的表头指针 } FreeList[m+1]; //表头向量类型 20 … 2k-1 2k … 2m … 21/35 8.4 伙伴系统(3) „ 分配算法 (算法8.2 P205) 假设用请求分配的存储量为n 。 „ 若2k-1<n ≤ 2k-1，且第k+1个子表不空，则只要删除此链表中第 一个结点并分配给用户即可 „ 若2k-2<n ≤ 2k-1-1，结点大小为2k-1的子表为空，则从结点大小 为2k的子表中取出一块，将其中一半分配给用户，剩余的一半作为 一个新结点插入在结点大小为2k-1的子表中 „ 若2k-i-1<n ≤ 2k-i-1(i为小于k的整数)，并且所有结点小于2k的子 表均为空，则同样需从结点大小为2k的子表中取出一块，将其中 2k-i分配给用户，剩余部分分割成若干个结点分别插入在结点大小 为2k-i、 2k-i+1、…、 2k-1的子表中。 22/35 8.4 伙伴系统(4) „ 回收算法(P205，206) 假设用户释放的内存区的起始地址为p，块的大小为2k „ 伙伴系统仅考虑互为“伙伴”的两个空闲块的归并 伙伴：两个由同一大块分裂出来的小块就称为“互为 伙伴”。假设p为大小为2k的空闲块的初始地址，且 p MOD 2k+1=0，则初始地址为p和p+2k的两个空 闲块互为伙伴。 23/35 8.4 伙伴系统(5) „ 判别其伙伴是否为空闲块 „ 若是，则在相应子表中找到其伙伴并删除之，然后再判别合并 后的空闲块的伙伴是否是空闲块 „ 若否，则只要将释放的空闲块简单插入在相应子表中即可 „ 伙伴块的起始地址 „ 对伙伴系统的评价 „ 优点：算法简单、速度快 „ 缺点：由于只归并伙伴而容易产生碎片 1 1 2 ( MOD 2 0 ) buddy( , ) 2 ( MOD 2 2 ) k k k kk p p p k p p + + ⎧ + = = ⎨ ⎩ − = 若 若 24/35 8.5 无用单元收集(1) „ 8.2~8.4节讨论的存储管理系统中，用户必须明确给出 “请求”和“释放”的信息 Î因为用户的疏漏或结构本身的原因致使系统在不恰当的 时候或没有进行回收而产生“无用单元”或“悬挂访问”的问 题。 „ 无用单元：那些用户不再使用而系统没有回收的结构和变量。 例： p = malloc(size); …. p=NULL; „ 悬挂访问：访问已经被释放的结点 例： p = malloc(size); …. q=p; free(p); a = *q; „ 因结构本身的特性，也会产生上述问题 例如广义表的结构: 共享子表(图8.9 P207)