Massive Algorithms: 看数据结构写代码（50）伙伴系统 - fuming0210sc的专栏 - 博客频道

看数据结构写代码（50）伙伴系统 - fuming0210sc的专栏 - 博客频道 - CSDN.NET

看数据结构写代码（50）伙伴系统 - fuming0210sc的专栏 - 博客频道 - CSDN.NET
伙伴系统是一种 只可以分配 2的幂次方 个空间的，回收内存时 只合并 "伙伴空间" 的一种动态内存管理方式。
例如一个空间大小为 64 的内存，伙伴系统为这 64 的内存建立一组双向循环链表，分别管理着 2的 0 次方，2的1 次方幂，2的 2 次方幂。。。2的6次方幂的可用空间。
即使我们只想分配一个大小为3的空间，系统却只能返回一个内存大小为 4（2的2次方）的一个空间。
系统在初始化的时候 ，并不是为每一个链表都放入一些可用空间。而是在 2的 6次方幂插入一个空间节点，大小为64。
当我们想要分配内存的时候，会查找最近内存大小的链表，如果链表有可用空间，取第一个空间。否则顺次查找可用空间。
假设我们要在这个 64 的空间里，分配一个大小为 3 的内存，系统怎么分配呢？
系统会从第一个链表一直找，直到找到 2的 6次方的链表。系统会将前 4个空间分配给用户。可是其余的 60个空间，不能再插入到 2的 6次方的链表中了。只能插入到
比它小的链表中去。
具体的分配方式如下：4 4 8 16 32 。
前4个分给用户使用，后面的 4 8 16 32 依次插入到 2的 2次方幂，2的 3次方，4次方，5次方幂的链表中去。
这有一个规则：
1. 用户空间的邻接空间总是被拆分成一个跟用户空间大小一样的空间。这个空间就是上面所有的 "伙伴空间"。
2. 再下一个空间依次是用户空间的 2倍，4倍，8倍，。。。直到被拆分空间一半。例子的拆分空间为 64，它的一半为 32。
所以可以算出：64 是如何被拆分的： 4（用户空间） 4（伙伴空间） 8 16 32

当我们回收空间时，首先会查看这个空间的伙伴空间是否为空闲。如果空闲会合并，并从链表中删除伙伴空间。。然后会再次查看合并后的空间。直至无法合并。如果不空闲，插入到合适的链表中去。
伙伴空间就是上面所说的 "4" ，必须跟回收空间空间大小一样，而且是从同一个大块内存分配出去的，
有一个公式可以求出伙伴空间：

例如释放上面的空间，会查找伙伴空间，伙伴空间空闲，合并空间成为一个大小为8 的空间，并从 2 的 2 次方链表中删除伙伴空间，然后继续查找。继续删除。。最终会合并成一个在 2的 6次幂链表中的一个空间。和初始的情况一样。

#define MAX_SIZE 64//最大空间
#define LIST_LEN 7//表头数组长度
#define MAX_INDEX 6//表头数组最大下标
struct BuddyNode{
 BuddyNode * preLink;
 BuddyNode * nextLink;
 int k;//只能分配2 的k次幂
 int tag;//0 空闲, 1 占用
};

typedef struct BuddyHead{
 BuddyNode * head;
 int nodeSize;
}FreeList[LIST_LEN];

static BuddyNode * freeSpace = NULL;//为了释放内存
static BuddyNode * userSpace[MAX_SIZE] = {NULL};
static int userCount = 0;

void initFreeList(FreeList list){
 for (int i = 0; i < LIST_LEN; i++){
  list[i].head = NULL;
  list[i].nodeSize = (int)pow(2.0,i);
 }
 //分配最大空间
 BuddyNode * p = (BuddyNode*)malloc(sizeof(BuddyNode) * MAX_SIZE);
 if (p != NULL){
  p->k = MAX_INDEX;
  p->tag = 0;
  p->nextLink = p->preLink = p;//双向循环链表
 }
 freeSpace = list[MAX_INDEX].head = p;
}

void destoryFreeList(FreeList list){
 for (int i = 0; i < LIST_LEN; i++){
  list[i].head = NULL;
 }
 free(freeSpace);
}

BuddyNode * buddyAlloc(FreeList list,int size){
 bool isFirst = true;
 int k = -1;//分配空间的k值
 int needK = -1;//需要分配空间的k值.
 //查找第一个满足条件的空间.
 for (int i = 0; i < LIST_LEN; i++){
  BuddyHead head = list[i];
  if (head.nodeSize >= size){
   if (isFirst){
    needK = i;
    isFirst = false;
   }
   if (head.head != NULL){//找到可分配的空间了
    k = i;
    break;
   }
  }
 }
 BuddyNode * freeNode = NULL;
 if (k == -1){
  return NULL;//找不到满足条件的空间了..
 }
 else{
  //设置这个空间 被占用，并且 更换 表头元素..
  freeNode = list[k].head;
  freeNode->k = needK;
  freeNode->tag = 1;//设置 成 已占用..
  list[k].head = freeNode->nextLink;//重新设置表头..
  if (freeNode->preLink == freeNode->nextLink){//删除这个空间后，成为空表.
   list[k].head = NULL;
  }
  else{//删除这个节点.
   freeNode->preLink->nextLink = freeNode->nextLink;
   freeNode->nextLink->preLink = freeNode->preLink;
  }
  //剩余空间 依次 插在 needK 和 k-1 表里.
  for (int i = needK; i < k ; i++){//从高位开始分配..
   int index = (int)pow(2.0,i);
   BuddyNode * p = freeNode + index;
   p->k = i;
   p->tag = 0;
   BuddyNode * head = list[i].head;
   if (head != NULL){
    p->preLink = head->preLink;
    p->nextLink = head;
    p->preLink->nextLink = head->preLink = p;
   }
   else{
    p->preLink = p->nextLink = p;
   }
   list[i].head = p;//重新设置表头..
  }
 }
 userSpace[userCount++] = freeNode;
 return freeNode;
}

void userSpaceFree(BuddyNode * node){
 for (int i = 0; i < userCount; i++){
  if (userSpace[i] == node){
   userSpace[i] = NULL;
  }
 }
}

//伙伴算法 回收...
void buddyReclaim(FreeList list,BuddyNode * node){
 userSpaceFree(node);
 while (node->k < MAX_INDEX){//循环查找伙伴，k值达到 MAX_INDEX 不需要 寻找...
  int sub = node - freeSpace;//计算出 具体坐标位置
  BuddyNode * buddy = NULL;
  int i = (int)pow(2.0,node->k + 1);
  bool isNext = true;//伙伴是不是在后
  if(sub % i == 0){//伙伴在后
   buddy = node + i/2;
  }
  else{//伙伴在前.
   buddy = node - i/2;
   isNext = false;
  }
  if (buddy->tag == 0 ){//伙伴空闲，合并
   //首先从列表里释放 buddy
   if (buddy->preLink == buddy->nextLink){//表中 只有一个节点，释放后，成为空表
    list[buddy->k].head = NULL;
   }
   else{//删除节点
    buddy->preLink->nextLink = buddy->nextLink;
    buddy->nextLink->preLink = buddy->preLink;
    list[buddy->k].head = buddy->nextLink;
   }
   if (isNext == false){
    node = buddy;
   }
   node->k ++;
  }
  else{//伙伴空间被占用..
   break;
  }
 }
 BuddyNode * head = list[node->k].head;
 node->tag = 0;
 if (head == NULL){//表头为空
   node->preLink = node->nextLink = node;
 }
 else{
  node->nextLink = head;
  node->preLink = head->preLink;
  node->preLink->nextLink = head->preLink = node;
 }
 list[node->k].head = node;
}

void printList(FreeList list){
 printf("------------------------打印伙伴列表-------------------\n");
 for (int i = 0; i < LIST_LEN; i++){
  BuddyNode * head = list[i].head;
  if (head){
   printf("首地址空间为：%0x,表的前驱：%0x,后继：%0x,表空间大小是2的%d次方\n",head,head->preLink,head->nextLink,head->k);
  }
 }
 printf("------------------------用户空间-------------------\n");
 for (int i = 0; i < userCount; i++){
  BuddyNode * us = userSpace[i];
  if (us != NULL){
   printf("首地址空间为：%0x,表空间大小是2的%d次方\n",us,us->k);
  }
 }
 printf("\n");
}



int _tmain(int argc, _TCHAR* argv[])
{
 FreeList list;
 initFreeList(list);
 printList(list);
 printf("---------------分配一个1空间之后--------------\n");
 BuddyNode * s1_1 = buddyAlloc(list,1);
 printList(list);
 printf("---------------分配一个1空间之后--------------\n");
 BuddyNode * s1_2 = buddyAlloc(list,1);
 printList(list);
 printf("---------------分配一个29空间之后--------------\n");
 BuddyNode * s29 = buddyAlloc(list,29);
 printList(list);
 printf("---------------释放一个1空间之后--------------\n");
 buddyReclaim(list,s1_2);
 printList(list);
 printf("---------------释放一个1空间之后--------------\n");
 buddyReclaim(list,s1_1);
 printList(list);
 destoryFreeList(list);
 return 0;
}

http://www.cnblogs.com/xudong-bupt/archive/2013/03/22/2976289.html

　1.伙伴系统概念

　　伙伴系统是一种经典的内存管理方法。Linux伙伴系统的引入为内核提供了一种用于分配一组连续的页而建立的一种高效的分配策略，并有效的解决了外碎片问题。

　2.伙伴系统的组织结构

　　Linux中的内存管理的“页”大小为4KB。把所有的空闲页分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页块。最大可以申请1024个连续页，对应4MB大小的连续内存。每个页块的第一个页的物理地址是该块大小的整数倍。

　　结构如图所示：第i个块链表中，num表示大小为(2^i)页块的数目，address表示大小为(2^i)页块的首地址。

　3.伙伴系统的内存分配及释放

　　当向内核请求分配(2^(i-1)，2^i]数目的页块时，按照2^i页块请求处理。如果对应的块链表中没有空闲页块，则在更大的页块链表中找。当分配的页块中有多余的页时，伙伴系统根据多余的页框大小插入到对应的空闲页块链表中。

　　当释放单页的内存时，内核将其置于CPU高速缓存中，对很可能出现在cache的页，则放到“快表”的列表中。在此过程中，内核先判断CPU高速缓存中的页数是否超过一定“阈值”，如果是，则将一批内存页还给伙伴系统，然后将该页添加到CPU高速缓存中。

　　当释放多页的块时，内核首先计算出该内存块的伙伴的地址。内核将满足以下条件的三个块称为伙伴：(1)两个块具有相同的大小，记作b。(2)它们的物理地址是连续的。(3)第一块的第一个页的物理地址是2*(2^b)的倍数。如果找到了该内存块的伙伴，确保该伙伴的所有页都是空闲的，以便进行合并。内存继续检查合并后页块的“伙伴”并检查是否可以合并，依次类推。