2. 伙伴系统：伙伴算法原理、内存碎片化问题、order与pageblock

2.1 伙伴算法核心原理

伙伴系统（Buddy System）是Linux内核管理物理内存分配与回收的基础算法。它将物理内存划分为2的幂次方大小的连续块，以order（阶）为单位进行管理。一个order为n的块包含2ⁿ个连续物理页框（page frame）。

2.2 order与pageblock

Linux内核使用order（0~10）来管理不同大小的连续内存块。每个order对应一个空闲链表，存储该大小的空闲块。pageblock是内存迁移和碎片管理的基本单元，通常大小为2^order页（典型值为order=3，即8页，共32KB）。

2.3 内存碎片化问题

内存碎片化分为内部碎片和外部碎片。伙伴系统主要面临外部碎片问题：虽然总空闲内存充足，但无法找到足够大的连续物理块。

• 外部碎片：空闲内存被分割成许多小碎片，无法满足高order分配请求。例如：总空闲内存100MB，但最大连续块只有64KB。
• 内部碎片：分配的内存块大于实际需求，造成浪费。伙伴系统通过2的幂次分配，内部碎片最多可达50%（平均25%）。

2.4 伙伴系统的数据结构

每个内存区域（zone）维护一个free_area数组，数组索引对应order。每个free_area包含一个空闲链表和nr_free计数。

// include/linux/mmzone.h
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};

struct zone {
    // ...
    struct free_area    free_area[MAX_ORDER];
    // ...
};

MAX_ORDER通常定义为11（order 0~10）。每个order的链表按迁移类型（MIGRATE_TYPES）进一步细分，以优化碎片管理。

2.5 迁移类型与碎片避免

Linux内核引入迁移类型（migrate type）来缓解碎片化。每个pageblock被标记为一种迁移类型，内核在分配时尽量将相同类型的页聚集在一起。

2.6 碎片化监控指标

通过/proc/buddyinfo可以查看各zone各order的空闲块数量，是诊断碎片化问题的第一手数据。

# cat /proc/buddyinfo
Node 0, zone      DMA      1      0      0      1      2      1      1      0      1      1      3
Node 0, zone    DMA32   1234    567     89     45     23     12      8      4      2      1      0
Node 0, zone   Normal   4567   2345    678    234     89     34     12      5      2      1      0

解读方法：从左到右依次为order 0~10的空闲块数量。如果高order（如order≥4）的数值长期为0或很小，说明碎片化严重。

2.7 伙伴系统与kswapd的协作

kswapd在回收内存时，不仅会扫描LRU链表回收页，还会触发内存压缩（compaction）来合并碎片。压缩过程将可移动页迁移到zone的一端，从而在另一端形成连续大块。

2.8 关键调优参数