`
cloudtech
  • 浏览: 4578156 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

linux内存管理伙伴算法(一:基本概念介绍)

 
阅读更多

在系统初始化进行到伙伴系统分配器能够承担内存管理的责任后,必须停用bootmem分配器,毕竟不能同时用两个分配器管理内存。在UMA和NUMA系统上,停用分别由free_all_bootmem和free_all_bootmem_node完成(前面的博客已经详细讨论过)。伙伴系统基于一种相对简单而令人吃惊的强大算法,它结合了优秀内存分配器的两个关键特性:速度和效率。Linux内核中采用了一种同时适用于32位和64位系统的内存分页模型,对于32位系统来说,两级页表足够用了,而在x86_64系统中,用到了四级页表,四级页表分别为:

页全局目录(Page Global Directory)

页上级目录(Page Upper Directory)

页中间目录(Page Middle Directory)

页表(Page Table)

页全局目录包含若干页上级目录的地址,页上级目录又依次包含若干页中间目录的地址,而页中间目录又包含若干页表的地址,每一个页表项指向一个页框。Linux中采用4KB

大小的页框作为标准的内存分配单元。


在实际应用中,经常需要分配一组连续的页框,而频繁地申请和释放不同大小的连续页框,必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样,即使这些页框
是空闲的,其他需要分配连续页框的应用也很难得到满足。为了避免出现这种情况,Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请1024个连续页框,对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。假设要申请一个256个页框的块,先从256个页框的链表中查找空闲块,如果没有,就去512个页框的链表中找,找到了则将页框块分为2个256个页框的块,一个分配给应用,另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块,继续向1024个页框的链表查找,如果仍然没有,则返回错误。
页框块在释放时,会主动将两个连续的页框块合并为一个较大的页框块。

为清楚了解其分配制度,先给个伙伴系统数据的存储框图如下:

也就是每个order对应一个free_area结构,free_area以不同的类型以链表的方式存储这些内存块。

主要的数据域结构分析:

struct zone
{
      ...
      ...
      struct free_area free_area[MAX_ORDER];
      ...
};
struct free_area {
	struct list_head	free_list[MIGRATE_TYPES];
	unsigned long		nr_free;
};
nr_free指定了当前内存区中空闲页块的数目(对0阶内存区逐页计算,对1阶内存区计算页对的数目,对2阶内存区计算4页集合的数目,依此类推)。free_list是用于连接空闲页的链表。order(阶)是伙伴系统中一个非常重要的概念,它描述了内存分配的数量单位,内存块的长度是2的order次方,其中order的范围从0到MAX_ORDER,而MAX_ORDER的值通常设置为11,这意味着一次分配可以请求的页数最大是2048(2的11次方)。但如果特定于体系结构的代码设置了FORCE_MAX_ZONEORDER配置选项,该值也可以手工改变。MIGRATE_TYPES指定了迁移类型的种类数。

#define MIGRATE_UNMOVABLE     0   //不可移动页:在内存中有固定位置,不能移动到其他地方
#define MIGRATE_RECLAIMABLE   1   //可回收页:不能直接移动,但可以删除,其内容可以从某些源重新生成
#define MIGRATE_MOVABLE       2   //可移动页:可以随意的移动
#define MIGRATE_RESERVE       3   //如果向具有特定可移动性地列表请求分配内存失败,这种紧急情况下可以从MIGRATE_RESERVE分配内存
#define MIGRATE_ISOLATE       4  //是一个特殊的虚拟区域,用于跨域NUMA结点移动物理内存页,在大型系统上,它有益于将物理内存页移动到接近于是用该页最频繁的CPU
#define MIGRATE_TYPES         5  //只是表示迁移类型的数目,不代表具体的区域
在伙伴系统中,每种迁移类型都对应于一个空闲列表。

注:我只是一个内核的初学者,如果有哪些地方说的不对或是不准确,请指正;如果你有什么问题希望能提出来,一起分析讨论一下,以求共同进步。谢谢


分享到:
评论

相关推荐

    疯狂内核之——Linux虚拟内存

    1.4 Linux内存布局 21 1.5 内核空间和用户空间 23 1.5.1 初始化临时内核页表 24 1.5.2 永久内核页表的初始化 32 1.5.3 第一次进入用户空间 41 1.5.4 内核映射机制实例 44 1.6 固定映射的线性地址 48 1.7 高端内存...

    深入分析Linux内核源码

    6.3.1 伙伴算法 6.3.2 物理页面的分配和释放 6.3.3 Slab分配机制 6.4 地址映射机制 6.4.1 描述虚拟空间的数据结构 6.4.2 进程的虚拟空间 6.4.3 内存映射 6.5 请页机制 6.5.1 页故障的产生 6.5.2 页错误的...

    Linux2.6内核标准教程(共计8-- 第1个)

    然后对Linux内核的3大核心模块——内存管理、进程管理、中断和异常处理进行了深入的分析; 在此基础上,对时间度量、系统调用进行了分析和讨论;最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU...

    Linux2.6内核标准教程(共计8--第6个)

    然后对Linux内核的3大核心模块——内存管理、进程管理、中断和异常处理进行了深入的分析; 在此基础上,对时间度量、系统调用进行了分析和讨论;最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU...

    Linux2.6内核标准教程(共计8--第8个)

    然后对Linux内核的3大核心模块——内存管理、进程管理、中断和异常处理进行了深入的分析; 在此基础上,对时间度量、系统调用进行了分析和讨论;最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU...

    Linux2.6内核标准教程(共计8--第3个)

    然后对Linux内核的3大核心模块——内存管理、进程管理、中断和异常处理进行了深入的分析; 在此基础上,对时间度量、系统调用进行了分析和讨论;最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU...

    Linux2.6内核标准教程(共计8--第7个)

    然后对Linux内核的3大核心模块——内存管理、进程管理、中断和异常处理进行了深入的分析; 在此基础上,对时间度量、系统调用进行了分析和讨论;最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU...

    Linux2.6内核标准教程(共计8--第4个)

    然后对Linux内核的3大核心模块——内存管理、进程管理、中断和异常处理进行了深入的分析; 在此基础上,对时间度量、系统调用进行了分析和讨论;最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU...

    Linux2.6内核标准教程(共计8--第2个)

    然后对Linux内核的3大核心模块——内存管理、进程管理、中断和异常处理进行了深入的分析; 在此基础上,对时间度量、系统调用进行了分析和讨论;最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU...

    Linux2.6内核标准教程(共计8--第5个)

    然后对Linux内核的3大核心模块——内存管理、进程管理、中断和异常处理进行了深入的分析; 在此基础上,对时间度量、系统调用进行了分析和讨论;最后讲解了Linux内核中常见的同步机制,使读者掌握每处理器变量和RCU...

    代码之美(中文完整版).pdf

    第26章 节省劳动的架构:一个面向对象的网络化软件框架 26.1 示例程序:日志服务 26.2 日志服务器框架的面向对象设计 26.3 实现串行化日志服务器 26.4 实现并行日志服务器 26.5 结论 第27章 以REST方式集成业务伙伴 ...

    圣天诺加密锁虚拟程序

    圣天狗是一个强大的软件保护设备,它实现了 163 位椭圆曲线非对称算法和 AES 对称 算法,提供了很多具有创新性的功能 , 并且首次把安全通道的概念引入到基于硬件的软件保护中,彻底解决了被保护软件和安全硬件的安全...

Global site tag (gtag.js) - Google Analytics