Linux学习笔记-伙伴算法

淩亂°似流年 2023-07-05 14:49 37阅读 0赞

**一.为什么要有伙伴算法？**  
伙伴算法是Linux系统一种管理内存的分配器，为了减少内存碎片而设计。伙伴算法拥有两个关键特征:速率和效率。  
**二.伙伴算法是什么?**

*  伙伴算法把所有的空闲页框分为11块链表,每块链表分别包含大小为1,2,4,8,16,32,64,128,256,512,和1024个连续页框的页框块。
 *  我们可以通过查看<mmzone.h>文件，获取相应的信息

#define MAX_ORDER 11
    #define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER -1 ))

伙伴系统在内存中的布局  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70]

*  不同的大小的块在不同的链表之间，是不会有重叠的。当一个需求为4个连续页面时候，检查每个结点大小为4页面的块的链表如果其中有空闲的块，分配给用户，不然向下一个级别的链表中查找。若下一级别存在空闲块，将该页面块分裂，一块分配出去，另外一块交给4页面的链表进行合并

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 1]

*  在分配内存时，首先从空闲的内存中搜索比申请的内存大的最小的内存。如果内存块存在，则进行标记为“已用”。同时将内存分配给应用程序。如果不存在，往下一级链表寻找，平分为两部分，一部分给程序使用，另一部分合并
 *  当程序释放内存，操作系统会将内存回收，然后检查与该内存相邻的内存是不是同样大小并且没有被使用，如果存在，则进行合并。
 *  我们可以通过查看<mmzone.h>

struct free_area{
        
       		struct list_head free_list[MIGRATE_TYPES];
       		unsigned long nr_free;	
       }

*  nr\_free 指定了当前内存区中的空闲页面的数目,free\_list用于连接空闲页的链表
 *  不论申请还是回收内存，算法都会来查找当前链表有没有空闲页存在。

**三.伙伴算法的优缺点**

优点:

*  较好的解决外部碎片问题
 *  针对大内存来进行分配
 *  只要请求的块不超过512页面，内核就分配连续的页面

缺点：

*  合并要求太过严格，符合伙伴关系的块才可以合并
 *  减少外部碎片的代价是以产生内部碎片为代价
 *  内存块的一个页面被占用，导致整块的内存区都不具备合并的条件

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200215212940184.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200215213023417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f,size_16,color_FFFFFF,t_70