参考: 中国科学院大学 2025年秋《高级操作系统教程》课件
引入虚拟内存后，物理内存分配主要在以下四个场景出现
- 用户态应用程序触发 on-demand paging（延迟映射）时
此时内核需要分配物理内存页，映射到对应的虚拟页 - 内核自己申请内存并使用时
如用于内核自身的数据结构，通常通过kmalloc()完成 - 内核申请用于设备的 DMA 缓存时
DMA 缓存通常需要连续的物理页 - 发生换页（swapping）时
通过磁盘来扩展物理内存的容量
物理页分配: alloc_page()
物理内存分配器的指标:
- 资源利用率
- 分配性能
简单实现: bitmap 位图
用位图记录物理页是否空闲: 每个 bit 记录一个物理页的空闲状态
- 分配时，通过 bitmap 查找空闲物理页，并在 bitmap 中标记非空闲
- 回收时，在 bitmap 中，把对应的物理页标记成空闲
问题：导致外部碎片问题
伙伴系统（buddy system）
当一个请求需要分配 $m$ 个物理页时，
- 伙伴系统将寻找一个大小合适的块，
该块包含 $2^n$ 个物理页，且满足 $2^n − 1 < m \le 2^n$ - 并将剩余的空闲块放到相应的链表中
合并过程
高效地找到伙伴块
- 互为伙伴的两个块的物理地址仅有一位不同
- 块的大小决定是哪一位
指标评估
- 资源利用率
- 外部碎片程度降低(但依旧存在)
- 内部碎片依然存在
- 分配性能
- 分配的时间复杂度: $O(list-num)$
- 合并的时间复杂度: $O(list-num)$