内存管理算法--Buddy伙伴算法

2024-02-18 00:08
文章标签 算法 内存 管理 伙伴 buddy

本文主要是介绍内存管理算法--Buddy伙伴算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://blog.csdn.net/orange_os/article/details/7392986

采用buddy算法，解决了外碎片问题，这种方法适合大块内存请求，这是因为把页作为单位内存块，不适合小内存区请求。如：几十个或者几百个字节。

对于小内存的请求，slab算法可能更好的解决内碎片问题。

Buddy算法的优缺点：

1）尽管伙伴内存算法在内存碎片问题上已经做的相当出色，但是该算法中，一个很小的块往往会阻碍一个大块的合并，一个系统中，对内存块的分配，大小是随机的，一片内存中仅一个小的内存块没有释放，旁边两个大的就不能合并。

2）算法中有一定的浪费现象，伙伴算法是按2的幂次方大小进行分配内存块，当然这样做是有原因的，即为了避免把大的内存块拆的太碎，更重要的是使分配和释放过程迅速。但是他也带来了不利的一面，如果所需内存大小不是2的幂次方，就会有部分页面浪费。有时还很严重。比如原来是1024个块，申请了16个块，再申请600个块就申请不到了，因为已经被分割了。

3）另外拆分和合并涉及到 较多的链表和位图操作，开销还是比较大的。

Buddy（伙伴的定义）：

这里给出伙伴的概念，满足以下三个条件的称为伙伴：
1）两个块大小相同；
2）两个块地址连续；
3）两个块必须是同一个大块中分离出来的；

Buddy算法的分配原理：

假如系统需要4(2*2)个页面大小的内存块，该算法就到free_area[2]中查找，如果链表中有空闲块，就直接从中摘下并分配出去。如果没有，算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块，则将其从链表中摘下，分成等大小的两部分，前四个页面作为一个块插入free_area[2]，后4个页面分配出去，free_area[3]中也没有，就再向上查找，如果free_area[4]中有，就将这16(2*2*2*2)个页面等分成两份，前一半挂如free_area[3]的链表头部，后一半的8个页等分成两等分，前一半挂free_area[2]
的链表中，后一半分配出去。假如free_area[4]也没有，则重复上面的过程，知道到达free_area数组的最后，如果还没有则放弃分配。



Buddy算法的释放原理：

内存的释放是分配的逆过程，也可以看作是伙伴的合并过程。当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块，就直接把要释放的块挂入链表头；如果有，则从链表中摘下伙伴，合并成一个大块，然后继续考察合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块(2*2*2*2*2*2*2*2*2个页面)。


整个过程中，位图扮演了重要的角色，如图2所示，位图的某一位对应两个互为伙伴的块，为1表示其中一块已经分配出去了，为0表示两块都空闲。伙伴中无论是分配还是释放都只是相对的位图进行异或操作。分配内存时对位图的
是为释放过程服务，释放过程根据位图判断伙伴是否存在，如果对相应位的异或操作得1，则没有伙伴可以合并，如果异或操作得0，就进行合并，并且继续按这种方式合并伙伴，直到不能合并为止。


Buddy内存管理的实现：

提到buddy 就会想起linux 下的物理内存的管理 ,这里的memory pool 上实现的 buddy 系统

和linux 上按page 实现的buddy系统有所不同的是,他是按照字节的2的n次方来做block的size

实现的机制中主要的结构如下:

整个buddy 系统的结构:

struct mem_pool_table

{

#define MEM_POOL_TABLE_INIT_COOKIE (0x62756479)

uint32 initialized_cookie; /* Cookie 指示内存已经被初始化后的魔数,  如果已经初始化设置为0x62756479*/

uint8 *mem_pool_ptr;/* 指向内存池的地址*/

uint32 mem_pool_size; /* 整个pool 的size,下面是整个max block size 的大小*/

uint32 max_block_size; /* 必须是2的n次方,表示池中最大块的大小*/   
boolean assert_on_empty; /* 如果该值被设置成TRUE,内存分配请求没有完成就返回 并输出出错信息*/
 uint32 mem_remaining; /* 当前内存池中剩余内存字节数*/                                              
uint32 max_free_list_index; /* 最大freelist 的下标,*/
struct mem_free_hdr_type     *free_lists[MAX_LEVELS];/* 这个就是伙伴系统的level数组*/

#ifdef FEATURE_MEM_CHECK
uint32 max_block_requested;
  uint32 min_free_mem; /* 放mem_remaining */
#endif /* FEATURE_ONCRPC_MEM_CHECK*/
};

这个结构是包含在free node 或alloc node 中的结构:

其中check 和 fill 都被设置为某个pattern
用来检查该node 的合法性
#define MEM_HDR_CHECK_PATTERN ((uint16)0x3CA4)
#define MEM_HDR_FILL_PATTERN ((uint8)0x5C)


typedef struct  tagBuddyMemBlockHeadType

{

    mem_pool_type pool; /*回指向内存池*/

    uint16 check; 

    uint8 state; /* bits 0-3 放该node 属于那1级 bit 7 如果置1,表示已经分配(not free)

    uint8 fill;

} BUDDY_MEM_BLOCK_HEAD_TYPE;



这个结构就是包含node 类型结构的 free header 的结构:

typedef struct  tagBuddyMemHeadType

{

    mem_node_hdr_type hdr;

    struct mem_free_hdr_type * pNext;   /* next,prev,用于连接free header的双向 list*/

    struct mem_free_hdr_type * pPrev;

} mem_free_hdr_type;

这个结构就是包含node 类型结构的 alloc header 的结构:
已分配的mem 的node 在内存中就是这样表示的
  1. typedef struct mem_alloc_hdr_type
  2. {
  3.    mem_node_hdr_type hdr;

  5. #ifdef FEATURE_MEM_CHECK_OVERWRITE
  6.    uint32     in_use_size;
  7. #endif

  9. } mem_alloc_hdr_type;
其中用in_use_size 来表示如果请求分配的size 所属的level上实际用了多少
比如申请size=2000bytes, 按size to level 应该是2048,实际in_use_size
为2000,剩下48byte 全部填充为某一数值,然后在以后free 是可以check 
是否有overwite 到着48byte 中的数值,一般为了速度,只 检查8到16byte

另外为什么不把这剩下的48byte 放到freelist 中其他level 中呢,这个可能
因为本来buddy 系统的缺点就是容易产生碎片,这样的话就更碎了

关于free or alloc node 的示意图:

假设

最小块为2^4=16,着是由mem_alloc_hdr_type (12byte)决定的, 实际可分配4byte

如果假定最大max_block_size =1024,

如果pool 有mem_free_hdr_type[0]上挂了两个1024的block node

上图是free node, 下图紫色为alloc node


接下来主要是buddy 系统的操作主要包括pool init , mem alloc ,mem free

pool init :
 1. 将实际pool 的大小去掉mem_pool_table 结构大小后的size 放到
     mem_pool_size, 并且修改实际mem_pool_ptr指向前进mem_pool_table
     结构大小的地址
 2.  接下来主要将mem_pool_size 大小的内存,按最大块挂到free_lists 上
    level 为0的list 上,然后小于该level block size 部分,继续挂大下一
    级,循环到全部处理完成  (感觉实际用于pool的size ,应该为减去
    mem_pool_table 的大小,然后和最大块的size 对齐,这样比较好,
    但没有实际测试过)
    
    
mem alloc:
    这部分相当简单,先根据请求mem的size ,实际分配时需要加上mem_alloc_hdr_type
这12byte ,然后根据调整后的size,计算实际应该在那个 level上分配,如果有相应级
很简单,直接返回,如果没有,一级一级循环查找,找到后,把省下的部分,在往下一级
一级插入到对应级的freelist 上

mem free:
     其中free 的地址,减去12 就可以获得mem_alloc_hdr_type 结构
     然后确定buddy 在该被free block 前,还是后面, 然后合并buddy,
     循环寻找上一级的buddy ,有就再合并,只到最大block size 那级



关于这个算法,在<<The Art  of Computer Programming>> vol 1,的

动态存储分配中有描述,对于那些只有OSAL 的小系统,该算法相当有用


网上有很简单的buddy算法的实现，但是只是toy，总内存大小不能动态调整

http://coolshell.cn/articles/10427.html

buddy2_new只是申请了一块小内存，用于管理大内存的分配,设这块大内存的起始地址是realstart.对于buddy2而言，是按照page管理大内存的。

对于buddy2_alloc返回的偏移是offset, 而实际的内存偏移应该是 realstart+offset*pageSize


这篇关于内存管理算法--Buddy伙伴算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/719413。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
NameNode内存生产配置

NameNode内存生产配置

Hadoop2.x 系列，配置 NameNode 内存 NameNode 内存默认 2000m ，如果服务器内存 4G ， NameNode 内存可以配置 3g 。在 hadoop-env.sh 文件中配置如下。 HADOOP_NAMENODE_OPTS=-Xmx3072m Hadoop3.x 系列，配置 Nam
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...
安全管理体系化的智慧油站开源了。

安全管理体系化的智慧油站开源了。

AI视频监控平台简介 AI视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒，省去繁琐重复的适配流程，实现芯片、算法、应用的全流程组合，从而大大减少企业级应用约95%的开发成本。用户只需在界面上进行简单的操作，就可以实现全视频的接入及布控。摄像头管理模块用于多种终端设备、智能设备的接入及管理。平台支持包括摄像头等终端感知设备接入，为整个平台提
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2