内存管理

Posted on | In

学习《Linux内核设计与实现》笔记系列二

伙伴系统与slab机制.

伙伴系统(buddy 算法)主要解决的是外部碎片问题.

slab机制主要解决的是内部碎片问题.

内存管理

学习伙伴系统与slab机制.

伙伴系统(buddy 算法)主要解决的是外部碎片问题.

slab机制主要解决的是内部碎片问题.

外部碎片:外部碎片是指还没有被分配出去(不属于任何进程)的内存块,但是由于太小了无法分配给申请内存空间的新进程的内存空闲区域,即处于两个已分配区域或页面之间的空闲存储块.这些存储块的综合可以满足当前申请长度的要求,但是由于它们的地址不连续或其他原因,使得系统无法满足当前申请要求.

内部碎片:内部碎片是指已被分配出去的内存空间(能明确的指明出该碎片属于哪个进程)大于请求所需的内存空间,不能被利用的内存空间就是内部碎片.内部碎片是出于区域内部或页面内部的存储块.占有这些区域或页面的进程并不使用这个存储块.而在进程占用这块存储块时,系统无法利用它.直到进程释放它,或进程结束时,系统才有可能利用这个存储块.

简单的解释就是:当我们申请几十字节的时候,内核也是给我们分配一个页,这样每个页中就形成很大的浪费,称之为内部碎片.

伙伴算法(Buddy)

伙伴算法（Buddy system）把所有的空闲页框分为11个块链表，每块链表中分布包含特定的连续页框地址空间，第0个块链表包含大小为2 ^ 0个连续的页框，第1个块链表中，每个链表元素包含2 ^ 1个页框大小的连续地址空间，….，第10个块链表中，每个链表元素包含2 ^ 10个页框大小的连续地址空间。每个链表中元素的个数在系统初始化时决定，在执行过程中，动态变化。

伙伴算法每次只能分配2的幂次页的空间，比如一次分配1页，2页，4页，8页，…，1024页(2^10)等等，每页(pageSize)大小一般为4K(一般而言, 32位系统是4K ,64位系统是8K)，因此，伙伴算法最多一次能够分配4M的内存空间。

用一个简单的例子来说明该算法的工作原理.

例如我们需要一个256个(2^8)页框的块.算法首先会在第9个链表块中查找是否有这样一个空闲块.如果没有的话,就会去下一个更大的链表快中查找,也就是到512个页框大小的链表中找空闲块.如果存在这样的块,那么内核就会把512个页框大小的块分成两等分,一个用作满足申请的需求,另一个则插入到256个页框的链表中.若在512个页框中也没找到空闲块,就继续找更大的块–1024个页框的块.如果这样的块存在,内核就把1024的块分粉为2个256,一个512的页框,一个256的页框用作申请,另外两块分别插入到256页框的链表中和512页框的链表中.若1024个页框的链表也为空,算法就放弃并发出错误的信号.

当程序释放内存时,操作系统先将内存回收,然后检查与该内存相邻的内存是否是同样大小并且处于空闲状态,如果是,则将这两块内存合并,然后程序递归进行同样的检查.

下面通过一个例子来解释伙伴算法回收内存.

假设系统中有 1MB 大小的内存需要动态管理，按照伙伴算法的要求：需要将这1M大小的内存进行划分。这里，我们将这1M的内存分为 64K、64K、128K、256K、和512K 共五个部分，如下图所示

  1. 此时，如果有一个程序A想要申请一块45K大小的内存，则系统会将第一块64K的内存块分配给该程序（产生内部碎片为代价），如图b所示；
  2. 然后程序B向系统申请一块68K大小的内存，系统会将128K内存分配给该程序，如图c所示；
  3. 接下来，程序C要申请一块大小为35K的内存。系统将空闲的64K内存分配给该程序，如图d所示；
  4. 之后程序D需要一块大小为90K的内存。当程序提出申请时，系统本该分配给程序D一块128K大小的内存，但此时内存中已经没有空闲的128K内存块了，于是根据伙伴算法的原理，系统会将256K大小的内存块平分，将其中一块分配给程序D，另一块作为空闲内存块保留，等待以后使用，如图e所示；
  5. 紧接着，程序C释放了它申请的64K内存。在内存释放的同时，系统还负责检查与之相邻并且同样大小的内存是否也空闲，由于此时程序A并没有释放它的内存，所以系统只会将程序C的64K内存回收，如图f所示；
  6. 然后程序A也释放掉由它申请的64K内存，系统随机发现与之相邻且大小相同的一段内存块恰好也处于空闲状态。于是，将两者合并成128K内存，如图g所示；
  7. 之后程序B释放掉它的128k，系统也将这块内存与相邻的128K内存合并成256K的空闲内存，如图h所示；
  8. 最后程序D也释放掉它的内存，经过三次合并后，系统得到了一块1024K的完整内存，如图i所示。

slab分配器

灵魂一问，为什么要有slab?

因为在linux内核中的内存管理是使用的伙伴系统，但是这个系统有个问题就是它的最小单元一般为4KB。但是很多情况下，我们需要分配的单元大小是远小于4K的，如果使用伙伴系统的话，必定就会产生很大的浪费。所以，一个粒度更小的分配器就呼之欲出，slab就是为了解决这种小粒度内存分配的内问题。

slab分配器扮演的了通用数据结构缓存层的角色.

  • 频繁使用的数据结构也会频繁分配和释放,因此应当缓存它们
  • 分配和回收必然会导致内部碎片.为了避免这种现象,空闲链表的缓存会连续地存放.因为已释放的数据结构又会放回空闲链表,因此不会导致碎片.
  • 回收的对象可以立即投入下一次分配.

slab层通常需要满足这样两个条件

  1. 当某一个子系统频繁的申请和释放内存
  2. 利用slab申请的内存大小必须是固定的
1
2
3
4
5
6
7
8
# slab 描述符
struct slab{
  struct list_head list;		//	满、部分满或空链表
  unsigned long colouroff;		//	slab着色的偏移量
  void *s_mem;					//	在slab中的第一个对象
  unsigned int inuse;			//	slab中已分配的对象数
  kmem_bufctl_t free;			//  第一个空闲对象
};

slab 层把不同的对象划分为所谓高速缓存组，其中每个高速缓存组都存放不同类型的对象，每种对象类型对应一个高速缓存。例如，一个高速缓存用于存放进程描述符，而另一个高速缓存存放索引节点对象，然后这些高速缓存又被划分为 slab。slab 由一个或多个物理上连续的页组成。一般情况下，slab 也就是仅仅由一页组成，每个高速缓存可以由多个 slab 组成。

slab 分配器把每一个请求的内存称之为对象。每个 slab 都包含一些对象成员，这里的对象指的是被缓存的数据结构。每个 slab 处于三种状态之一：满、部分满或空。一个满的 slab 没有空闲的对象（slab 中的对象都已被分配）。一个空的 slab 没有分配出任何对象（slab 中所有对象都是空闲的）。一个部分满的 slab 有一些对象已分配出去，有些对象还空闲着。当内核的某一部分需要一个新的对象时，先从部分满的 slab 中进行分配，如果没有部分满的 slab，就从空的 slab 中进行分配。如果没有空的 slab，就要创建一个 slab 了。

slab分配器是基于对象管理的.相同对象归于一类,每当要申请一个对象时,slab分配器就从一个slab链表中分配一个这样大小的单元出去,而当要释放时,将其重新保留在该列表中,而不是直接返回给伙伴系统,从而避免内部碎片.slab分配器并不丢弃已分配的对象,而是释放并把它们保留在内存中.slab分配对象时,会使用最近释放的对象内存块,因此其驻留在CPU缓存中的概率会大大提高.

参考链接
【Linux 内核】内存管理（二）伙伴算法