现
代计算机!总第二三五期"
ＭＯＤＥＲＮＣＯＭＰＵＴＥＲ２００６．５
实践与经验
１Ｌｉｎｕｘ内存管理体系
在Ｉｎｔｅｌ８０ｘ８６体系结构中，Ｌｉｎｕｘ内核的内存管
理采用了分页管理方式，真正实现了虚拟存储器管理，其虚拟内存管理的实现结构如图１所示。
图１
内存映射模块负责把磁盘文件的逻辑地址映射到虚拟地址，把虚拟地址映射到物理地址；交换模块负责控制内存内容的换入和换出；核心管理模块负责核心内存管理功能，即对页的分配、
回收、释放及请页处理等；结构特定的模块负责给各种硬件提供通用接口，这个模块通过执行命令来改变硬件ＭＭＵ的虚拟地址映射。
Ｌｉｎｕｘ虚拟内存的实现机制为：内存管理程序通过映射机制把用户程序的逻辑地址映射到物理地址，在用户程序运行时如果发现程序中要用到的虚地址没有对应的物理内存时，就发出了请页要求；如果有空闲的内存可供分配，就请求分配内存，并把正在使
用的物理页纪录在页缓存中。如果没有足够的内存可供分配，那么就调用交换机制，腾出一部分内存。另外，在地址映射中要通过ＴＬＢ来寻物理页，交换机制中也要用到交换缓存，并且把物理页内容交换到交换文件后也要修改页表来映射文件地址。
２Ｓｌａｂ分配机制概述
Ｓｌａｂ分配机制用来对内存区域中内核空间进行
分配和回收。Ｓｌａｂ使用对象来组织内存区域，对象就是指存放一组数据结构的内存区。Ｓｌａｂ根据内存区的使用频率对内存区域进行划分。对于预期频繁使用的内存区，Ｓｌａｂ创建一组特定大小的专用缓冲区进行处理，以避免内碎片的产生；对于较少使用的内存区，
Ｓｌａｂ创建一组通用缓冲区来处理，即使这种处理模式产生碎片，对整个系统的性能影响也不大。
Ｓｌａｂ分配模式把对象分组放进缓冲区，Ｓｌａｂ缓冲区并非由各个对象直接构成，而是由一连串的Ｓｌａｂ构成，而每个大块中则包括了若干个同种类型的对象。
高速缓存、Ｓｌａｂ及对象之间的关系如图２所示。
图２
Ｌｉｎｕｘ内存管理中的Ｓｌａｂ分配机制
赵鲲鹏１
，
苏葆光２
（１．长安大学，西安７１００６１；２．浙江万里学院，宁波３１５１０１）
摘
要：早期Ｌｉｎｕｘ的内存分配机制采用伙伴算法，当请求分配的内存大小为几十个字节或几百个
字节时会产生内存碎片，严重消耗系统资源。现今采用Ｓｌａｂ机制可以缓存物理空间的申请和回收，杜绝外部碎片的产生，降低内部碎片量。本文分析了Ｓｌａｂ内存分配机制及其数据结构和接口函数，然后给出了Ｓｌａｂ机制的实现。
关键词：Ｓｌａｂ；内存管理；Ｌｉｎｕｘ；分配机制
!
"
实践与经验
现代计算机!总第二三五期"
３Ｓｌａｂ数据结构和接口
（１）Ｓｌａｂ数据结构
Ｓｌａｂ是Ｓｌａｂ管理模式中最基本的结构。它是由
一组连续的物理页面组成，对象就被顺序放在这些页
面中。其数据结构定义如下：
ｔｙｐｅｄｅｆｓｔｒｕｃｔｓｌａｂ＿ｓ｛
ｓｔｒｕｃｔｌｉｓｔ＿ｈｅａｄｌｉｓｔ；
ｕｎｓｉｇｎｅｄｌｏｎｇｃｏｌｏｕｒｏｆｆ；
ｖｏｉｄ＊ｓ＿ｍｅｎ；
ｕｎｓｉｇｎｅｄｉｎｔｉｎｕｓｅ；
ｋｍｅｎ＿ｂｕｆｃｔ１＿ｔｆｒｅｅ；
｝ｓｌａｂ＿ｔ；
ｌｉｓｔ用来将前一个和后一个Ｓｌａｂ链接起来形成一
个双向链表；ｃｏｌｏｕｒｏｆｆ为该Ｓｌａｂ上着区大小，着
区的大小使Ｓｌａｂ中的每个对象的起始地址都按高速
缓存中的“缓存行”大小进行对齐；指针ｓ＿ｍｅｎ指向对
象区的起点；ｉｎｕｓｅ是Ｓｌａｂ中所分配对象的个数；ｆｒｅｅ
的值指明了空闲对象链中的第一个对象。对于小对
象，就把Ｓｌａｂ的描述结构ｓｌａｂ＿ｔ放在该Ｓｌａｂ中；对于
大对象，则把Ｓｌａｂ结构游离出来，集中存放。
（２）缓冲区数据结构
每个缓冲区管理着一个Ｓｌａｂ链表，Ｓｌａｂ按序分
为３组。第１组是全满的Ｓｌａｂ；第２组Ｓｌａｂ中只有部
分对象被分配；第３组Ｓｌａｂ中的对象全部空闲。每个
缓冲区还有一个轮转锁（Ｓｐｉｎｌｏｃｋ），在对链表进行修
改时用这个轮转锁进行同步。缓冲区类型
ｋｍｅｍ＿ｃａｃｈｅ＿ｓ定义及注释如下：
ｓｔｒｕｃｔｋｍｅｍ＿ｃａｃｈｅ＿ｓ｛
ｓｔｒｕｃｔｌｉｓｔ＿ｈｅａｄｓｌａｂｓ＿ｆｕｌｌ；／／全满Ｓｌａｂ链表
ｓｔｒｕｃｔｌｉｓｔ＿ｈｅａｄｓｌａｂｓ＿ｐａｒｔｉａｌ；
／／部分对象被分配的Ｓｌａｂ链表
ｓｔｒｕｃｔｌｉｓｔ＿ｈｅａｄｓｌａｂｓ＿ｆｒｅｅ；／／空闲Ｓｌａｂ链表
ｕｎｓｉｇｎｅｄｉｎｔｏｂｊｓｉｚｅ；／／对象的大小
ｕｎｓｉｇｎｅｄｉｎｔｆｌａｇｓ；／／属性标志
ｕｎｓｉｇｎｅｄｉｎｔｎｕｍ；／／ｓｌａｂ中对象的数目
ｓｐｉｎｌｏｃｋ＿ｔｓｐｉｎｌｏｃｋ；／／自旋锁
＃ｉｎｄｅｆＣＯＮＦＩＧ＿ＳＭＰ／／如果是对称多处理器
ｕｎｓｉｇｎｅｄｉｎｔｂａｔｃｈｃｏｕｎｔ；／／定义一个批处理计数
＃ｅｎｄｉｆ
／／以下是关于Ｓｌａｂ的增加和消除的
ｕｎｓｉｇｎｅｄｉｎｔｇｆｐｏｒｄｅｒ；／／Ｓｌａｂ中页面数目
ｕｎｓｉｇｎｅｄｉｎｔｇｆｐｆｌａｇｓ；／／申请页面的优先级
ｓｉｚｅ＿ｔｃｏｌｏｕｒ；／／着的范围
ｕｎｓｉｇｎｅｄｉｎｔｃｏｌｏｕｒ＿ｏｆｆ；／／着的偏移量
ｕｎｓｉｇｎｅｄｉｎｔｃｏｌｏｕｒ＿ｎｅｘｔ；／／下一个着的
ｋｍｅｍ＿ｃａｃｈｅ＿ｔ＊ｓｌａｂｐ＿ｃａｃｈｅ；
／／指向ｃａｃｈｅ＿ｓｌａｂｐ缓冲区的指针
ｕｎｓｉｇｎｅｄｉｎｔｇｒｏｗｉｎｇ；
／／对正在增长的Ｓｌａｂ设置的标志
ｕｎｓｉｇｎｅｄｉｎｔｄｆｌａｇｓ；
／／对动态作的标志
ｖｏｉｄ（＊ｃｔｏｒ）（ｖｏｉｄ＊，ｋｍｅｍ＿ｃａｃｈｅ＿ｔ＊，ｕｎｓｉｇｎｅｄ
ｌｏｎｇ）；／／构造函数
ｖｏｉｄ（＊ｄｔｏｒ）（ｖｏｉｄ＊，ｋｍｅｍ＿ｃａｃｈｅ＿ｔ＊，ｕｎｓｉｇｎｅｄ
ｌｏｎｇ）；／／析构函数
ｕｎｓｉｇｎｅｄｌｏｎｇｆａｉｌｕｒｅｓ；／／失败标记
／／以下是关于缓存的增加和消除的
ｃｈａｒｎａｍｅ［ＣＡＣＨＥ＿ＮＡＭＥＬＥＮ］；／／缓存区的名字
ｓｔｒｕｃｔｌｉｓｔ＿ｈｅａｄｎｅｘｔ；／／指向下一个缓存结构的指针
＃ｉｎｄｅｆＣＯＮＦＩＧ＿ＳＭＰ／／对称多处理器的编译预处理
ｃｐｕｃａｃｈｅ＿ｔ＊ｃｐｕｄａｔａ［ＮＲ＿ＣＰＵＳ］；
／／设置指向每一个ＣＰＵ运行的指针
＃ｅｎｄｉｆ
＃ｉｆＳＴＡＴＳ／／编译预处理，如果需要记录状态
ｕｎｓｉｇｎｅｄｌｏｎｇｎｕｍ＿ａｃｔｉｖｅ；／／活跃的数目
ｕｎｓｉｇｎｅｄｌｏｎｇｎｕｍ＿ａｌｌｏｃａｔｉｏｎｓ；／／分配的数目
ｕｎｓｉｇｎｅｄｌｏｎｇｈｉｇｈ＿ｍａｒｋ；／／最多活跃的标记
ｕｎｓｉｇｎｅｄｌｏｎｇｇｒｏｗｎ；／／增长标记
ｕｎｓｉｇｎｅｄｌｏｎｇｒｅａｐｅｄ；／／回收的标记
ｕｎｓｉｇｎｅｄｌｏｎｇｅｒｒｏｒｓ；／／出错的标记
＃ｉｆｄｅｆＣＯＮＦＩＧ＿ＳＭＰ编译预处理，如果定义了对称多处
理器
ａｔｏｍｉｃ＿ｔａｌｌｏｃｈｉｔ；／／原子计数器分配命中数
ａｔｏｍｉｃ＿ｔａｌｌｏｃｍｉｓｓ；／／原子计数器分配未命中数
ａｔｏｍｉｃ＿ｔｆｒｅｅｈｉｔ；／／原子计数器释放命中数
ａｔｏｍｉｃ＿ｔｆｒｅｅｍｉｓｓ；／／原子计数器释放未命中数
＃ｅｎｄｉｆ
＃ｅｎｄｉｆ
｝；
缓冲区结构头指针ｋｍｅｍ＿ｃａｃｈｅ＿ｔ定义及注释如下：
ｓｔａｔｉｃｋｍｅｍ＿ｃａｃｈｅ＿ｔｃａｃｈｅ＿ｃｈｃｈｅ＝｛
ｓｌａｂｓ＿ｆｕｌｌ；ＬＩＳＴ＿ＨＥＡＤ＿ＩＮＩＴ（ｃａｃｈｅ＿ｃａｃｈｅ，ｓｌａｂｓ＿
ｆｕｌｌ），／／全满Ｓｌａｂ链表
ｓｌａｂｓ＿ｐａｒｔｉａｌ；ＬＩＳＴ＿ＨＥＡＤ＿ＩＮＩＴ（ｃａｃｈｅ＿ｃａｃｈｅ，ｓｌａｂｓ＿
ｐａｒｔｉａｌ），／／部分对象被分配的Ｓｌａｂ链表
ｓｌａｂｓ＿ｆｒｅｅ；ＬＩＳＴ＿ＨＥＡＤ＿ＩＮＩＴ（ｃａｃｈｅ＿ｃａｃｈｅ，ｓｌａｂｓ＿
ｆｒｅｅ），／／空闲Ｓｌａｂ链表
ｏｂｊｓｉｚｅ；ｓｉｚｅｏｆ（ｋｍｅｍ＿ｃａｃｈｅ＿ｔ），／／对象的大小
ｆｌａｇｓ；ＳＬＡＢ＿ＮＯ＿ＲＥＡＰ，／／属性标志
ｓｐｉｎｌｏｃｋＳＰＩＮ＿ＬＯＣＫ＿ＵＮＬＯＣＫＥＤ，／／自旋锁
ｃｏｌｏｕｒ＿ｏｆｆ；Ｌ１＿ＣＡＣＨＥ＿ＢＹＴＥＳ，／／设定着范围
为１级缓存的大小
ｎａｍｅ；＂ｋｍｅｍ＿ｃａｃｈｅ＂，／／设置名称
｝；
（３）缓存接口
创建某类对象的缓存函数为：
!"
ＭＯＤＥＲＮＣＯＭＰＵＴＥＲ２００６．５
现
代计算机!总第二三五期"
ＭＯＤＥＲＮＣＯＭＰＵＴＥＲ２００６．５
实践与经验
ＳｌａｂＡｓｓｉｇｎｉｎｇＭｅｃｈａｎｉｓｍｉｎＭｅｍｏｒｙＭａｎａｇｅｍｅｎｔｏｆＬｉｎｕｘ
ＺＨＡＯＫｕｎ－ｐｅｎｇ１，
ＳＵＢａｏ－ｇｕａｎｇ２
（１．Ｃｈａｎｇ＇ａｎＵｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ７１００６１Ｃｈｉｎａ；２．ＺｈｅｊｉａｎｇＷａｎｌｉＵｎｉｖｅｒｓｉｔｙ，Ｎｉｎｇｂｏ３１５１０１Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：ＴｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓＳｌａｂＡｓｓｉｇｎｉｎｇｍｅｃｈａｎｉｓｍｉｎｍｅｍｏｒｙｍａｎａｇｅｍｅｎｔｉｎＬｉｎｕｘａｎｄｃｏｎｓｔｒｕｃｔｉｏｎｏｆ
ｄａｔａａｎｄｃｏｄｅｓｉｎｉｔ．ＴｈｉｓｐａｐｅｒａｌｓｏｉｎｔｒｏｄｕｃｅｓｈｏｗｔｏｕｓｅＳｌａｂＡｓｓｉｇｎｉｎｇｍａｃｈｉｎｅａｎｄｇｉｖｅｓａｎｅｘａｍｐｌｅ．
Ｋｅｙｗｏｒｄｓ：Ｓｌａｂ；ＭｅｍｏｒｙＭａｎａｇｅｍｅｎｔ；Ｌｉｎｕｘ；ＡｓｓｉｇｎｉｎｇＭｅｃｈａｎｉｓｍ
Ｋｍｅｍ＿ｃａｃｈｅ＿ｔ＊ｋｍｅｍ＿ｃａｃｈｅ＿ｃｒｅａｔｅ（ｃｏｎｓｔｃｈａｒ＊ｎａｍｅ，ｓｉｚｅ＿ｔｓｉｚｅ，ｓｉｚｅ＿ｔｏｆｆｓｅｔ，ｕｎｓｉｇｎｅｄｌｏｎｇｃ＿ｆｌａｇｓ，ｖｏｉｄ（＊ｃｔｏｒ）（ｖｏｉｄ＊ｏｂｊｐ，ｋｍｅｍ＿ｃａｃｈｅ＊ｃａｃｈｅｐ，ｕｎｓｉｇｎｅｄｌｏｎｇｆｌａｇｓ），ｖｏｉｄ（＊ｄｔｏｒ）（ｖｏｉｄ＊ｏｂｊｐ，ｋｍｅｍ＿ｃａｃｈｅ＿ｔ＊ｃａｃｈｅｐ，ｕｎｓｉｇｎｅｄｌｏｎｇｆｌａｇｓ））
从缓存中获得一个对象的函数为：
linux内核设计与实现 pdfｓｔａｔｉｃｉｎｌｉｎｅｖｏｉｄ＊＿ｋｍｅｍ＿ｃａｃｈｅ＿ａｌｌｏｃ（ｋｍｅｍ＿ｃａｃｈｅ＿ｔ＊ｃａｃｈｅｐ，ｉｎｔｆｌａｇｓ）
释放对象到缓存的函数为：
ｓｔａｔｉｃｉｎｌｉｎｅｖｏｉｄ＿ｋｍｅｍ＿ｃａｃｈｅ＿ｆｒｅｅ（ｋｍｅｍ＿ｃａｃｈｅ＿
ｔ＊ｃａｃｈｅｐ，ｃｏｎｓｔｖｏｉｄ＊ｏｂｊｐ）
当缓存为空或者没有多余的空闲对象满足申请时，向页面级分配器索要物理空间，并创建和初始化对象：
ｓｔａｔｉｃｉｎｔｋｍｅｍ＿ｃａｃｈｅ＿ｇｒｏｗ（ｋｍｅｍ＿ｃａｃｈｅ＿ｔ＊ｃａｃｈｅｐ，ｉｎｔｆｌａｇｓ）
当页面级分配器需要内存时，搜索所有缓存，析构缓存中的空闲对象，最后回收这些对象占用内存的函数为：
ｖｏｉｄｋｍｅｍ＿ｃａｃｈｅ＿ｒｅａｐ（ｉｎｔｇｆｐ＿ｍａｓｋ）
缓存销毁函数为：
ｉｎｔｋｍｅｍ＿ｃａｃｈｅ＿ｄｅｓｔｒｏｙ（ｔａｓｋ＿ｓｔｒｕｃｔ＿ｃａｃｈｅｐ）
４Ｓｌａｂ的使用
使用过程：
分配一个对象；
ｉｆ（该缓存中有空闲的对象）
直接使用对象；
ｅｌｓｅ｛
为该缓存分配空间；构造新的对象；
｝
使用后释放一个对象；
使用实例：
ｋｍｅｍ＿ｃａｃｈｅ＿ｔ＊ｔａｓｋ＿ｓｔｒｕｃｔ＿ｃａｃｈｅｐ；
ｔａｓｋ＿ｓｔｒｕｃｔ＿ｃａｃｈｅｐ＝ｋｍｅｍ＿ｃａｃｈｅ＿ｃｒｅａｔｅ（＂ｔａｓｋ＿ｓｔｒｕｃｔ＂，ｓｉｚｅｏｆ（ｓｔｒｕｃｔｔａｓｋ＿ｓｔｒｕｃｔ），０，ＳＬＡＢ＿ＭＵＳＴ＿ＨＷＣＡＣＨＥ＿ＡＬＩＧＮ，ＮＵＬＬ，ＮＵＬＬ）；
ｉｆ（！ｔａｓｋ＿ｓｔｒｕｃｔ＿ｃａｃｈｅｐ）
ｐａｎｉｃ（＂ｆｏｒｋ＿ｉｎｉｔ（）；ｃａｎｎｏｔｃｒｅａｔｅｔａｓｋ＿ｓｔｒｕｃｔＳＬＡＢ
ｃａｃｈｅ＂）；
ｓｔｒｕｃｔｔａｓｋ＿ｓｔｒｕｃｔ＊ｔｓｋ；
ｔｓｋ＝ｋｍｅｍ＿ｃａｃｈｅ＿ａｌｌｏｃ（ｔａｓｋ＿ｓｔｒｕｃｔ＿ｃａｃｈｅｐ，ＧＦＰ＿ＫＥＲ－ＮＥＬ）；
ｉｆ（！ｔｓｋ）｛
ｆｒｅｅ＿ｔｈｒｅａｄ＿ｉｎｆｏ（ｔｉ）；ｒｅｔｕｒｎＮＵＬＬ；｝
使用ｔａｓｋ＿ｓｔｒｕｃｔ＿ｃａｃｈｅｐ；
ｋｍｅｍ＿ｃａｃｈｅ＿ｆｒｅｅ（ｔａｓｋ＿ｓｔｒｕｃｔ＿ｃａｃｈｅｐ，ｔｓｋ）；
结语
Ｓｌａｂ分配器的概念首先在ＳＵＮＭｉｃｒｏｓｙｓｔｅｍ的ＳＵＮＯＳ５．４操作系统中实现。早期版本的Ｌｉｎｕｘ的内核区域分配算法采用伙伴算法，每次至少分配一个页面。当请求分配的内存大小为几十个字节或几百个字节时会产生内碎片，造成浪费。现今采用Ｓｌａｂ机制可以方便缓存物理空间的申请和回收，杜绝外部碎片的产生，使内部碎片量降低到最小。
参考文献
［１］ＭｉｃｈａｅｌＢｅｃｋ等．Ｌｉｎｕｘ内核编程指南．张瑜等译．北京：清华大学出版社，２００４
［２］陈莉君．深入分析Ｌｉｎｕｘ内核源代码．北京：人民邮电出版社，２００２
［３］ＲｏｂｅｒｔＬｏｖｅ等．Ｌｉｎｕｘ内核设计与实现．陈莉君等译．北京：机械工业出版社，２００５
［４］洪津津，石教英．Ｌｉｎｕｘ中的Ｓｌａｂ分配器．计算机应用研究，２０００（２９）
（收稿日期：２００６－０３－１０）
!
"

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。