专栏首页人人都是极客Linux内核内存管理算法Buddy和Slab

Linux内核内存管理算法Buddy和Slab

有了前两节的学习相信读者已经知道CPU所有的操作都是建立在虚拟地址上处理(这里的虚拟地址分为内核态虚拟地址和用户态虚拟地址),CPU看到的内存管理都是对page的管理,接下来我们看一下用来管理page的经典算法--Buddy。

Buddy分配算法

假设这是一段连续的页框,阴影部分表示已经被使用的页框,现在需要申请一个连续的5个页框。这个时候,在这段内存上不能找到连续的5个空闲的页框,就会去另一段内存上去寻找5个连续的页框,这样子,久而久之就形成了页框的浪费。为了避免出现这种情况,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个页框的链表查找,如果仍然没有,则返回错误。页框块在释放时,会主动将两个连续的页框块合并为一个较大的页框块。

从上面可以知道Buddy算法一直在对页框做拆开合并拆开合并的动作。Buddy算法牛逼就牛逼在运用了世界上任何正整数都可以由2^n的和组成。这也是Buddy算法管理空闲页表的本质。 空闲内存的信息我们可以通过以下命令获取:

也可以通过echo m > /proc/sysrq-trigger来观察buddy状态,与/proc/buddyinfo的信息是一致的:

CMA

细心的读者或许会发现当Buddy算法对内存拆拆合合的过程中会造成碎片化的现象,以至于内存后来没有了大块的连续内存,全是小块内存。当然这对应用程序是不影响的(前面我们讲过用页表可以把不连续的物理地址在虚拟地址上连续起来),但是内核态就没有办法获取大块连续的内存(比如DMA, Camera, GPU都需要大块物理地址连续的内存)。

在嵌入式设备中一般用CMA来解决上述的问题。CMA的全称是contiguous memory allocator, 其工作原理是:预留一段的内存给驱动使用,但当驱动不用的时候,CMA区域可以分配给用户进程用作匿名内存或者页缓存。而当驱动需要使用时,就将进程占用的内存通过回收或者迁移的方式将之前占用的预留内存腾出来,供驱动使用。

Slab

在Linux中,伙伴系统(buddy system)是以页为单位管理和分配内存。但是现实的需求却以字节为单位,假如我们需要申请20Bytes,总不能分配一页吧!那岂不是严重浪费内存。那么该如何分配呢?slab分配器就应运而生了,专为小内存分配而生。slab分配器分配内存以Byte为单位。但是slab分配器并没有脱离伙伴系统,而是基于伙伴系统分配的大内存进一步细分成小内存分配。我们先来看一张图:

kmem_cache是一个cache_chain的链表,描述了一个高速缓存,每个高速缓存包含了一个slabs的列表,这通常是一段连续的内存块。存在3种slab:

  • slabs_full(完全分配的slab)
  • slabs_partial(部分分配的slab)
  • slabs_empty(空slab,或者没有对象被分配)。

slab是slab分配器的最小单位,在实现上一个slab有一个货多个连续的物理页组成(通常只有一页)。单个slab可以在slab链表之间移动,例如如果一个半满slab被分配了对象后变满了,就要从slabs_partial中被删除,同时插入到slabs_full中去。

为了进一步解释,这里举个例子来说明,用struct kmem_cache结构描述的一段内存就称作一个slab缓存池。一个slab缓存池就像是一箱牛奶,一箱牛奶中有很多瓶牛奶,每瓶牛奶就是一个object。分配内存的时候,就相当于从牛奶箱中拿一瓶。总有拿完的一天。当箱子空的时候,你就需要去超市再买一箱回来。超市就相当于partial链表,超市存储着很多箱牛奶。如果超市也卖完了,自然就要从厂家进货,然后出售给你。厂家就相当于伙伴系统。

可以通过下面命令查看slab缓存的信息:

总结

从内存DDR分为不同的ZONE,到CPU访问的Page通过页表来映射ZONE,再到通过Buddy算法和Slab算法对这些Page进行管理,我们应该可以从感官的角度理解了下图:

文章分享自微信公众号:
人人都是极客

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • Linux内核内存管理算法Buddy和Slab

    有了前两节的学习相信读者已经知道CPU所有的操作都是建立在虚拟地址上处理(这里的虚拟地址分为内核态虚拟地址和用户态虚拟地址),CPU看到的内存管理都是对page...

    刘盼
  • 宋宝华:slab在内核内存管理和用户态Memcached的双重存在

    很多基础的概念,将跨越软件的层次而存在。比如slab,对于内核人员,我们都知道slab是buddy之上的一层。

    233333
  • Linux内核内存管理与漏洞利用

    网上已经有很多关于Linux内核内存管理的分析和介绍了,但是不影响我再写一篇:一方面是作为其他文章的补充,另一方面则是自己学习的记录、总结和沉淀。

    用户8639654
  • 伙伴系统和slab机制

    Linux内核中采用了一种同时适用于32位和64位系统的内存分页模型,对于32位系统来说,两级页表足够用了,而在x86_64系统中,用到了四级页表。四级页表分别...

    233333
  • SLUB的引入及举例说明

    我们都知道Buddy分配器是按照页的单位分配的(Buddy系统分配器实现),如果我们需要分配几十个字节,几百个字节的时候,就需要用到SLAB分配器。

    DragonKingZhu
  • [linux][memory] 物理内存管理

    前言: 书接上回《内存映射技术分析》,继续来分析一下linux的物理内存管理。 分析: 1,物理内存 PC上的内存条,或者手机上的内存芯片,物理上实实在在的...

    皮振伟
  • 五分钟彻底搞懂你一直没明白的Linux内存管理

    现在的服务器大部分都是运行在Linux上面的,所以,作为一个程序员有必要简单地了解一下系统是如何运行的。对于内存部分需要知道: 地址映射 内存管理的方式 缺页...

    小小科
  • 五分钟彻底搞懂你一直没明白的Linux内存管理

    现在的服务器大部分都是运行在Linux上面的,所以,作为一个程序员有必要简单地了解一下系统是如何运行的。对于内存部分需要知道:

    小小科
  • 倒计时:《Linux的任督二脉》之《内存管理》在线课程

    理解硬件访问内存的原理,MMU和页表;澄清Linux内核ZONE,buddy,slab管理;澄清用户空间malloc与内核关系,Lazy分配机制;澄清进程的内存...

    Linux阅码场
  • 优惠今天结束:《Linux的任督二脉》之《内存管理》在线课程

    理解硬件访问内存的原理,MMU和页表;澄清Linux内核ZONE,buddy,slab管理;澄清用户空间malloc与内核关系,Lazy分配机制;澄清进程的内存...

    Linux阅码场
  • Linux内存管理精华文章汇总

    Linux操作系统(包括Android)之所以可以运行丰富的应用程序,是因为背后有着内存管理和进程调度的支撑,个人觉得这两点也是所有OS的精华。掌握内存管理和进...

    刘盼
  • Linux内存管理 - slab分配器

    Linux内存管理是一个非常复杂的子系统,要完全说清的话估计要一本书的篇幅。但Linux内存管理可以划分成多个部分来阐述,这篇文章主要介绍slab算法。

    用户7686797
  • 万字整理,肝翻Linux内存管理所有知识点

    Linux的内存管理可谓是学好Linux的必经之路,也是Linux的关键知识点,有人说打通了内存管理的知识,也就打通了Linux的任督二脉,这一点不夸张。有人问...

    刘盼
  • 万字整理,肝翻Linux内存管理所有知识点

    Linux的内存管理可谓是学好Linux的必经之路,也是Linux的关键知识点,有人说打通了内存管理的知识,也就打通了Linux的任督二脉,这一点不夸张。有人问...

    用户6280468
  • Netty12# 池化内存框架流程

    本文简要梳理为什么使用池化内存?Netty使用池化内存从哪些方面提升了效率?梳理了池化内存的核心组件大体含义以及内存分配流程,勾勒池化内存的整体框架。后面文章会...

    瓜农老梁
  • ucoreOS_lab2 实验报告

    lab2 会依赖 lab1 ,我们需要把做的 lab1 的代码填到 lab2 中缺失的位置上面。练习 0 就是一个工具的利用。这里我使用的是 Linux 下的系...

    Angel_Kitty
  • 一文浅析内存管理机制

    众所周知,程序需要加载到物理内存才能运行,多核时代会出现多个进程同时操作同一物理地址的情况,进而造成混乱和程序崩溃。计算机当中很多问题的解决都是通过引入中间层,...

    范蠡
  • 万字长文,别再说你不懂Linux内存管理了,30 张图给你安排的明明白白

    之前写了两篇详细分析 Linux 内存管理的文章,读者好评如潮。但由于是分开两篇来写,而这两篇内容其实是有很强关联的,有读者反馈没有看到另一篇读起来不够不连贯,...

    程序IT圈

扫码关注云+社区

领取腾讯云代金券