Linux系统---简易伙伴系统

顾得泉：个人主页

个人专栏：《Linux操作系统》《C/C++》《LeedCode刷题》

键盘敲烂，年薪百万！

一、题目要求

1.采用C语言实现

2.伙伴系统采用free_area[11]数组来组织。要求伙伴内存最小为一个页面，页面大小为4KB，最大为4MB，即1024个页面。描述一个空闲伙伴内存块的数据结构为

struct chunk
{unsigned int power;  //内存块大小的2次幂指数，如12，13，...，22unsigned int start;   //内存块的起始地址struct chunk* next;  //后向指针Struct chunk* prev;  //前向指针}

3.如何辨识两个内存块c1和c2互为伙伴（buddy）？

条件1：c1.power=c2.power，即两个块的大小相同；

条件2：c1和c2的地址start（二进制）的第power位不同，其他位完全相同。比如，大小为256KB的两个伙伴，一个地址为0x0000,0000，另一个为0x0004,0000，这两个地址的第18位（二进制位，从0开始起位）一个为0，一个为1，其余位完全相同，因此它们互为buddy。

再如，大小为256KB的两个伙伴，一个地址为0x0008,0000，另一个为0x000C,0000，它们的第power位，即第18位一个为0，一个为1，其余位完全相同。

而地址为0x4,0000和0x8,0000的chunk不是伙伴，尽管它们是相邻的。

因此可以设计判断两个chunk是否是伙伴的函数：

int isBuddy(struct chunk* c1, struct chunk* c2){if(c1->power!=c2->power)return 0;if((c1->start^c2->start)>>c1->power!=1) //先异或，再移位return 0;return 1;}

二、模块描述

本文实现了一个内存管理程序，用于分配和释放内存块。它使用了内存池技术，通过将内存块划分为大小为2^n的块来提高内存分配的效率。

程序中定义了一个结构体chunk，表示内存块，包含以下成员变量：

power：表示内存块的大小，即2^n。
start：表示内存块的起始地址。
next：指向下一个内存块的指针。
prev：指向上一个内存块的指针。

程序还定义了一个全局数组free_area，用于存储空闲的内存块。数组的索引表示内存块的大小，数组的元素是指向对应大小的内存块链表的头指针。

程序提供了以下函数：

is_buddy(struct chunk *c1 , struct chunk *c2)：判断两个内存块是否为“伙伴”关系，即它们的power相同且它们的起始地址相邻。
init()：初始化内存池，将最大内存块分配给free_area[8]。
pick(unsigned int k)：从free_area中选择一个大小为2^k的内存块，并将其分割成两个大小为2^(k-1)的内存块。
allocate(unsigned int req)：请求分配一个大小为req字节的内存块，如果无法满足请求，则返回NULL。
release(struct chunk *c)：释放一个内存块，将其与相邻的伙伴内存块合并，并更新free_area。
check()：打印当前内存池的状态，包括每个大小的内存块链表。

在main()函数中，首先调用init()函数初始化内存池，然后依次请求分配100KB、256KB和500KB的内存块，并打印分配前后的内存池状态。最后，释放这些内存块，并再次打印内存池状态。

三、代码实现

#include <stdio.h>
#include <stdlib.h>struct chunk{unsigned int power;unsigned int start;struct chunk *next;struct chunk *prev;
};struct chunk* free_area[11];int is_buddy(struct chunk *c1 , struct chunk *c2)
{if(c1 -> power != c2 -> power) return 0;if((c1 -> start ^ c2 -> start) >> c1 -> power != 1) return 0;return 1;
}void init()
{for(int i = 0 ; i < 11 ; i ++)free_area[i] = NULL;struct chunk *max_chunk = (struct chunk*) malloc(sizeof(struct chunk));max_chunk -> power = 20;max_chunk -> start= 0;max_chunk -> next = NULL;max_chunk -> prev = NULL;free_area[8] = max_chunk;
}struct chunk *pick(unsigned int k)
{struct chunk *c = NULL;struct chunk *left = NULL;struct chunk *right = NULL;int i;for(i = k ; i <= 10 ; i ++){if(free_area[i] != NULL){c = free_area[i];free_area[i] = c -> next;break;}}if(i > 10){printf("Failed to pick up a trunk\n");return NULL;}for(int j = i - 1 ; j >= k ; j --){left = (struct chunk*)malloc(sizeof(struct chunk));left -> power = c -> power - 1;left -> start = c -> start;left -> next = free_area[j];left -> prev = NULL;if(free_area[j] != NULL){free_area[j] -> prev = left;}free_area[j] = left;right = (struct chunk *) malloc(sizeof (struct chunk));right -> power = c -> power - 1;right -> start = c -> start + (1 << right -> power);right -> next = NULL;right -> prev = NULL;free(c);c = right;}return c;
}struct chunk * allocate(unsigned int req){unsigned int power = 0;while((1 << power) < req)power ++;return pick(power - 12);}void release(struct chunk *c)
{unsigned int k = c -> power - 12;struct chunk * buddy = NULL;int merged = 1;while(merged){merged = 0;buddy = free_area[k];while(buddy != NULL){if(is_buddy(c , buddy)){c -> power ++;if(buddy -> prev == NULL)free_area[k] = buddy -> next;else buddy -> prev -> next = buddy -> next;if(buddy -> next != NULL)buddy -> next -> prev = buddy -> prev;if(c -> start > buddy -> start) c -> start = buddy -> start;free(buddy);merged = 1;k ++;break;}buddy = buddy -> next;}}c -> next = free_area[k];if(free_area[k] != NULL)free_area[k] -> prev = c;free_area[k] = c;
}void check()
{for(int i = 0 ; i < 11 ; i ++){printf("free_area[%d]: " , i);struct chunk * chunk = free_area[i];while(chunk != NULL){printf("(%u  , %x) ->" , chunk -> power , chunk -> start);chunk = chunk -> next;}printf("NULL\n");}printf("\n");
}int main()
{init();printf("inintal state\n");check();struct chunk *c100 = allocate(100 * 1024);printf("ask for 100kb allocate\n");check();struct chunk *c256 = allocate(256 * 1024);printf("ask for 256kb allocate\n");check();struct chunk *c500 = allocate(500 * 1024);printf("ask for 500kb allocate\n");check();release(c100);printf("release c100\n");check();release(c256);printf("release c256\n");check();release(c500);printf("release c500\n");check();
}