buddy memory allocation相关整理

概述

wiki上的定义:

The buddy memory allocation technique is a memory allocation algorithm that divides memory into partitions to try to satisfy a memory request as suitably as possible. This system makes use of splitting memory into halves to try to give a best fit.

伙伴内存分配技术是一种内存分配算法,它将内存划分为多个分区,以尝试尽可能适当地满足内存请求。 该系统利用将内存分成两半来尝试提供最佳匹配。

算法

伙伴系统有多种形式; 将每个块细分为两个较小块的块是最简单,最常见的一种。
选定块的大小要根据实际情况选取,太小则需要更多的内存记录跟踪内存分配, 太大又容易产生空间浪费,另外,就是如果选择2的次幂单位的话, 最大的块有可能不会覆盖整个内存.

例子

同样是wiki的例子,申请的内存调整了下

Step 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K
1 24
2.1 23 23
2.2 22 22 23
2.3 21 21 22 23
2.4 20 20 21 22 23
2.5 A:20 20 21 22 23
3 A:20 20 B: 21 22 23
4 A:20 C:20 B: 21 22 23
5.1 A:20 C:20 B: 21 21 21 23
5.2 A:20 C:20 B: 21 D: 21 21 23
6 A:20 C:20 21 D: 21 21 23
7.1 A:20 C:20 21 21 21 23
7.2 A:20 C:20 21 22 23
8 20 C:20 21 22 23
9.1 20 20 21 22 23
9.2 21 21 22 23
9.3 22 22 23
9.4 23 23
9.5 24
  1. 初始化状态,每块64K, 最大的块包含 24 个块, 一个4阶块.
  2. 程序A请求内存34K,0阶块,过程如下:
    1. 没有可用的0阶块,因此拆分了4阶块,创建了两个3阶块。
    2. 仍然没有可用的0阶块,因此拆分了第一个3阶块,创建了两个2阶块。
    3. 仍然没有可用的0阶块,因此拆分了第一个2阶块,创建了两个1阶块。
    4. 仍然没有可用的0阶块,因此拆分了第一个1阶块,创建了两个0阶块。
  3. 程序B请求内存66K,1阶块。1阶块可用,因此将其分配给B。
  4. 程序C请求内存35K,0阶块。0阶块可用,因此将其分配给C。
  5. 程序D请求内存67K,1阶块,过程如下:
    1. 没有可用的1阶块,因此拆分了2阶块,创建了两个1阶块。
    2. 有可用的1阶块,因此将其分配给D。
  6. 程序B释放其内存,释放一个1阶​​块。
  7. 程序D释放其内存。
    1. 释放一个1阶块。
    2. 由于新释放的块的伙伴块也是空闲的,因此将两者合并为一个2阶块。
  8. 程序A释放其内存, 释放一个0阶块。
  9. 程序C释放其内存, 释放一个0阶块。
    1. 释放一个0阶块。
    2. 由于新释放的0阶块的伙伴块也是空闲的,因此将两者合并为一个1阶块。
    3. 由于新形成的1阶块的伙伴块也是空闲的,因此将两者合并为一个2阶块。
    4. 由于新形成的2阶块的伙伴块也是空闲的,因此将两者合并为一个3阶块。
    5. 由于新形成的3阶块的伙伴块也是空闲的,因此将两者合并为一个4阶块。

过程整理为:

  • 分配内存
    1. 寻找合适大小的内存块(最小2k块,该块大于或等于请求的内存)
      1. 如果找到,它将分配给程序
      2. 如果没有,它将尝试创建合适的内存块。 系统通过尝试以下操作来做到这一点:
        1. 将大于请求的内存大小的可用内存块拆分为一半
        2. 如果达到下限,则分配该内存量
        3. 返回步骤1(寻找合适大小的内存块)
        4. 重复此过程,直到找到合适的内存块
  • 释放内存
    1. 释放内存块
    2. 看一下邻近的块-它是否释放
    3. 如果是这样,则将两者结合起来,然后返回到步骤2并重复此过程,直到达到上限(所有内存都已释放)或遇到非空闲邻居块为止

实现

Linux 物理内存管理

Linux物理内存管理:初始化时期,使用简单的内存分配方式bootmem,memblock来管理内存,完成初始化工作后,再转交给伙伴系统来管理物理页。

  1. 是针对页进行分配的算法,也就是分配的最小单位是一个页;
  2. 根据使用用途,以链表的形式存放在不同的ZONE类型的数组里。
  3. ZONE又被分配到不同节点pglist_data上,主要是针对NUMA内存模型设计, SMP内存模型的架构只有一个节点。
  • 数据结构 :
typedef struct pglist_data {
    struct zone node_zones[MAX_NR_ZONES];
    struct zonelist node_zonelists[MAX_ZONELISTS];
    int nr_zones;
  ...
};

struct zone {
    struct free_area    free_area[MAX_ORDER];
    unsigned long       flags;
    spinlock_t      lock;
    ...
}

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

再具体管理物理内存页的过程中,Linux内核设计上考虑到了实际的的应用场景: 对内存进行分类MIGRATE_* , 进行内存迁移,这个类型内存不够了可以从其他备选类型中再申请; 设置缓存分配页面per_cpu_pageset等等。

用linux的改一个

下面参考Linux 伙伴系统简化一个版本演示一下wiki上的伙伴系统的例子。

  1. 使用alloc_pages分配

alloc_pages -> alloc_pages_current->__alloc_pages_nodemask ->rmqueue->__rmqueue_smallest->expand

  1. 使用free_pages释放内存

free_pages-> __free_pages -> free_the_page -> __free_pages_ok -> free_one_page->__free_one_page

  1. 伙伴系统初始化, 涉及到初始的内存从哪里来

mem_init -> memblock_free_all -> free_low_memory_core_early-> __free_memory_core -> memblock_free_pages -> __free_pages_core -> __free_pages

代码有些长, 放到github上了 https://github.com/weida/buddytest

输出结果:


[root@centosgpt buddylinux]# ./buddytest |2^4 step| 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 1 |2^4 2 |2^4 |2^3 |2^3 |2^2 |2^2 |2^3 |2^1 |2^1 |2^2 |2^3 |2^0 |2^0 |2^1 |2^2 |2^3 2 |A:2^0|2^0 |2^1 |2^2 |2^3 3 |A:2^0|2^0 |2^1 |2^2 |2^3 3 |A:2^0|2^0 |B:2^1 |2^2 |2^3 4 |A:2^0|2^0 |B:2^1 |2^2 |2^3 4 |A:2^0|C:2^0|B:2^1 |2^2 |2^3 5 |A:2^0|C:2^0|B:2^1 |2^2 |2^3 |A:2^0|C:2^0|B:2^1 |2^1 |2^1 |2^3 5 |A:2^0|C:2^0|B:2^1 |D:2^1 |2^1 |2^3 6 |A:2^0|C:2^0|B:2^1 |D:2^1 |2^1 |2^3 |A:2^0|C:2^0|B:2^1 |D:2^1 |2^1 |2^3 6 |A:2^0|C:2^0|2^1 |D:2^1 |2^1 |2^3 7 |A:2^0|C:2^0|2^1 |D:2^1 |2^1 |2^3 |A:2^0|C:2^0|2^1 |2^1 |2^1 |2^3 |A:2^0|C:2^0|2^1 |2^2 |2^3 7 |A:2^0|C:2^0|2^1 |2^2 |2^3 8 |A:2^0|C:2^0|2^1 |2^2 |2^3 |2^0 |C:2^0|2^1 |2^2 |2^3 8 |2^0 |C:2^0|2^1 |2^2 |2^3 9 |2^0 |C:2^0|2^1 |2^2 |2^3 |2^0 |2^0 |2^1 |2^2 |2^3 |2^1 |2^1 |2^2 |2^3 |2^2 |2^2 |2^3 |2^3 |2^3 |2^4 9 |2^4

参考及引用

Buddy memory allocation
How to add the mathematical symbol for ‘power’ (like X ^ 2) to a question?
buddy-system-内核物理页管理的实现
godspeed1989/buddy_allocator

Be First to Comment

发表回复