对linux伙伴系统及其反碎片机制的研究1
需积分: 0 57 浏览量
2022-08-03
15:09:04
上传
评论
收藏 1.93MB PDF 举报
75
对linux伙伴系统及其反碎片机制的研究
雷方杰
（广东工业大学计算机学院，广东 广州 510006）
摘要：
首先介绍了linux伙伴系统的原理，然后提出了旧版本内核在解决碎片问题上的不足，并详细分析了内核对于该问题的
最新解决方法。
关键词：
内存管理；linux伙伴系统；外碎片
中图分类号：
TP316.81
文献标识码：
A
文章编号：
1673-1131（2011）06-0075-02
伙伴系统是一种经典的内存管理方法。Linux伙伴系统的
引入为内核提供了一种用于分配一组连续的页而建立的一种高
效的分配策略，并有效的解决了外碎片问题。
1 linux的内存组织
在linux中，内存被划分为多个结点，每个结点与系统中的
某个处理器对应。每个节点又被划分为最多三个内存域：ZONE_
DMA，ZONE_NOMAL，ZONE_HIGHMEM。ZONE_DMA是用于DMA操作
的内存区。ZONE_NOMAL是可以直接映射到内核段得普通内存
区。ZONE_HIGHMEM为高端内存区。每个内存域把该内存域中的
空闲块分组为MAX_ORDER个块链表，每个链表中包含着许多同
样大小的连续内存块。对于第order个链表，该链表管理着所有
大小为2
order
的空闲块，如图1所示。
2 伙伴系统的结构组织
系统的每个内存域描述结构如下：
struct zone {
……
struct free_area free_area[MAX_ORDER];
……
};
free_area数组定义如下：
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
nr_free指定了当前内存域中的空闲内存块的数目。每个空
闲内存块包含一个或多个连续页。阶是伙伴系统用来描述内存
分配的数量单位。数组free_area[MAX_ORDER]管理其所在内存
域的所有空闲块。如图1所示，数组free_area[MAX_ORDER]下标
解释为阶, 该数组的每一项free_area[order]都指向了一个双向
链表,该链表将所有大小为2
order
个页的连续空闲内存块链接在一
起。
图1 伙伴系统中相互链接的内存块
3 伙伴系统内存分配与释放
阶是伙伴系统用来描述内存分配的数量单位,所以伙
伴系统总是选择2
order
个连续页用来分配，order为0-MAX_
ORDER的整数。
3.1 内存的分配
如果需要分配1页的内存时，内核会从内存域zone的当前处
理器的每CPU高速缓存中申请。如果每CPU高速缓存结构热页链
表p cp[0].list中的页数pcp[0].cou nt不为零,则会从链表头部
选择一页用来配。如果p cp[0].cou nt等于零，则free_area[0]中
移除pcp[0].batch个页，并将这些页填充到每CPU高速缓存结构
热页链表pcp[0].list中,然后从链表头部选择一页用来分配。
如果需要分配多页，这里分两种情况说明。第一，当分配页
数满足2
n
形式时，可从伙伴系统的n阶空闲列表free_a rea[n]中
选择一块用来分配。如果free_area[n]中没有满足条件的空闲
块，则从较高的分配阶分配一块内存，将按照伙伴系统原理将
该内存块分裂成两块相等的内存块，将其中的一块用来分配，
以此类推。假设n=2，在free_area[2]和free_area[3]中没有找
到空闲的可用块，而从free_area[4]中找到了可用的空闲块,伙
伴系统拆分内存块的步骤如下：（1）将free_area[4]中选择的
空闲块从该链表中移除。（2）内核切换到低一个分配阶3，先将
步骤1中的空闲块拆分为两半，将后一半插入到阶为3的空闲列
表中。前一半用来分配，由于前一半内存块的大小为2
3
页，仍
然大于要分配的2
2
页。因此需要对该内存块进行进一步的拆
分。（3）将该内存块 拆分为两块大小为2
2
页的内存块，后一半
插入到阶为2的空闲列表中，前一半则用来分配。第二，当需
要分配的页数pages不满足2
n
形式但满足 ,内核
会分配2
i
个连续页而非pages页的内存块。分配原理和第一种
情况一样。
3.2 内存的释放
内核对单页和多页内存块的释放采用不同的方式。当释放
单页的内存时，内核将其置于每CPU高速缓存中，对很可能出现
在cache的页，则放到热页的列表中。内核先判断每CPU高速缓
存中的页数pcp->count是否大于或等于pcp->high,如果是，则
将数目为pcp->batch的一批内存页还给伙伴系统，然后将该页
添加到每CPU高速缓存中。
当释放多页的块时，内核首先计算出该内存块的伙伴的地
址。内核将满足以下条件的两个块称为伙伴：（1）两个块具有
相同的大小，记作b。（2）它们的物理地址是连续的。（3）第一
块的第一个页框的物理地址是2
×b×
2
12
的倍数。
如果找到了该内存块的伙伴，确保该伙伴的所有页都是空
闲的，以便进行合并。例如：两个大小为都为2页的伙伴合并成
一个2
2
页的内存块。内存继续查找该2
2
页内存块的伙伴并检查
2011 年第 6 期
（总第 116 期）
信 息 通 信
INFORMATION & COMMUNICATIONS
2011
（Sum. No 116）
柏傅美
- 粉丝: 19
- 资源: 325
最新资源
- STC15单片机串口2使用程序例子
- 读取日志的excel生成周报 用python3开发weekplan-master.zip
- python 读取excel数据导入dbimport-data-master.zip
- K折交叉验证BP神经网络，多输入多输出BP神经网络（代码完整，数据齐全）
- B07训练原图.zip
- python-对Excel数据处理做可视化分析.zip
- 人工智能大作业-无人机图像目标检测的python源代码+文档说明.zip
- 基于GoogLeNet实现Cifar-10图像分类项目python源码（高分项目）.zip
- 数据库 sql 面试题目及答案解析.docx
- 汽车常见 10 种传感器故障后的表现与解决措施.docx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0