诚信网站 互联网建站,深圳软件开发有限公司,wordpress网站的彻底清理,河南省工程招标信息网顾得泉#xff1a;个人主页
个人专栏#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂#xff0c;年薪百万#xff01; 一、题目要求
1.采用C语言实现
2.伙伴系统采用free_area[11]数组来组织。要求伙伴内存最小为一个页面#xff0c;页面大小为4KB…
顾得泉个人主页
个人专栏《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂年薪百万 一、题目要求
1.采用C语言实现
2.伙伴系统采用free_area[11]数组来组织。要求伙伴内存最小为一个页面页面大小为4KB最大为4MB即1024个页面。描述一个空闲伙伴内存块的数据结构为
struct chunk
{unsigned int power; //内存块大小的2次幂指数如1213...22unsigned int start; //内存块的起始地址struct chunk* next; //后向指针Struct chunk* prev; //前向指针}
3.如何辨识两个内存块c1和c2互为伙伴buddy 条件1c1.powerc2.power即两个块的大小相同 条件2c1和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.hstruct 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();
}四、结果展示 首先开辟了一块1M大小的空间 请求分配100KB的内存块 请求分配256KB的内存块 请求分配500KB的内存块 释放100KB的内存块 释放256KB的内存块 释放500KB的内存块 到此所有操作就结束了。 结语Linux系统中实现简易的伙伴系统的分享到这里就结束了希望本篇文章的分享会对大家的学习带来些许帮助如果大家有什么问题欢迎大家在评论区留言~~~
