《操作系统》之内存篇(七)

分配内核内存

在用户模式下运行进程请求额外的内存时（new, malloc）时，从内核【操作系统】维护的空闲页帧列表上分配页面（书上的这句话，我理解为，new和malloc的时候，在虚拟空间会在堆空间进行申请内存，但是映射到物理内存，需要重新分配物理帧，而这个帧是由内核维护的空闲帧列表上来的）。
这个帧的列表是用来进行页面置换的，所以在它相邻的部分，不一定是来自于进程的同一个连续的虚拟内存，而是来自于物理内存的不同空闲页面。而且在用户申请单个字节的时候，他为了避免内存碎片，会分配整个帧给进程。

用于内核分配内存的空闲内存池列表，和内核给用户进程分配的页面的列表不一样的。

内核需要为不同大小的数据结构请求内存。有的小于一页，因此，在内核使用分配内存的时候，他应该尽量小的最小化碎片浪费。
用户模式进程分配的页面不必连续物理内存。

这部分是自己网上资料理解的（书上写的太烂了）：
Linux内核内存管理的一项重要工作就是如何在频繁申请释放内存的情况下，避免碎片的产生。Linux采用伙伴系统解决外部碎片的问题，采用slab解决内部碎片的问题。
在这里我们先讨论外部碎片问题。避免外部碎片的方法有两种：
（1）是利用分页单元把一组非连续的空闲页框映射到连续的线性地址区间；
（2）伙伴系统：是记录现存空闲连续页框块情况，以尽量避免为了满足对小块的请求而分割大的连续空闲块。

伙伴系统（解决外部碎片）
使用场景：内核中很多时候要求分配连续页，为快速检测内存中的连续区域，内核采用了一种技术：伙伴系统。
原理：系统中的空闲内存总是两两分组，每组中的两个内存块称作伙伴。伙伴的分配可以是彼此独立的。但如果两个小伙伴都是空闲的，内核将其合并为一个更大的内存块，作为下一层次上某个内存块的伙伴。
具体先看下一个例子：

这是一个最初由256KB的物理内存，内核需要请求21KB的内存。
那么最初他将256KB的内存进行分割，变成两个128KB的内存块，AL和AR，这两个内存块称为伙伴。随后他发现128KB也远大于21KB，于是他继续分割为两个64KB的内存块，发现64KB 也不是满足需求的最小的内存块，于是他继续分割为两个32KB的。32KB再往下就是16KB，就不满足需求了，所以32KB是它满足需求的最下的内存块了，所以他就分割出来的CL 或者CR 分配给需求方。
当需求方用完了，需要进行归还，然后他把32KB的内存还回来，它的另一个伙伴如果没被占用，那么他们地址连续，就合并成一个64KB的内存块，以此类推，进行合并。

注意这里的所有的分割都是进行二分来分割，所有内存块的大小都是2的幂次方。
他们的具体结构会保存在一个结构中。

#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
#define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

  struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];//空闲块双向链表
    unsigned long       nr_free;//空闲块的数目
  };
  struct zone{
       ....
       struct free_area    free_area[MAX_ORDER];  
       ....
  };

它的从上到下都是都保存一个链表，每一条链表的第一个页框的物理地址是该块大小的整数倍。例如，大小为 16个页框的块，其起始地址是 16 * 2^12 （2^12 = 4096，这是一个常规页的大小）的倍数。

Linux2.6为每个管理区使用不同的伙伴系统，内核空间分为三种区，DMA，NORMAL，HIGHMEM，对于每一种区，都有对应的伙伴算法。

伙伴系统的缺点：由于分配的都是2的幂次方的内存，会有内部碎片。

slab分配（分配小对象，小于一个页框）

slab有两种，一种是专用cache,如下分析：
它的基本思想是将内核中经常使用的对象放到高速缓存中，并且由系统保持为初始的可利用状态。将内核中经常使用的对象（比如进程描述符，文件描述符），他们也是需要内存的，所以一开始就直接分配好，按照所占用的内存大小分门别类放在下文讲的 kmem_cache (其实就和伙伴一摸一样)，下次用到直接拿去用，用完在放回原位置就行了。（简单的说就是带有结构体的内存池）。

需要注意的是slab分配器只管理内核的常规地址空间（直接被映射到内核地址空间的ZONE_NORMAL和ZONE_DMA）。

图 1 给出了 slab 结构的高层组织结构。在最高层是 cache_chain，这是一个 slab 缓存的链接列表。可以用来查找最适合所需要的分配大小的缓存（遍历列表）。cache_chain 的每个元素都是一个 kmem_cache 结构的引用（称为一个 cache）。它定义了一个要管理的给定大小的对象池（固定大小，即分门别类）。（kmem_cache == 对象池）

每个缓存都包含了一个 slabs 列表，这是一段连续的内存块（通常都是页面）。存在 3 种 slab：

slabs_full 完全分配的 slab
slabs_partial 部分分配的 slab
slabs_empty 空 slab，或者没有对象被分配

slab 列表中的每个 slab 都是一个连续的内存块（一个或多个连续页），它们被划分成一个个对象。这些对象是从特定缓存中进行分配和释放的基本元素。注意 slab 是 slob 分配器进行操作的最小分配单位，通常来说，每个 slab 被分配为多个对象。
由于对象是从 slab 中进行分配和释放的，因此单个 slab 可以在 slab 列表之间进行移动。例如，当一个 slab 中的所有对象都被使用完时，就从 slabs_partial 列表中移动到 slabs_full 列表中。

slab分配器分配的优点：

可以提供小块内存的分配支持
不必每次申请释放都和伙伴系统打交道，提供了分配释放效率
如果在slab缓存的话，其在CPU高速缓存的概率也会较高。
伙伴系统的操作对系统的数据和指令高速缓存有影响，slab分配器降低了这种副作用
伙伴系统分配的页地址都页的倍数，这对CPU的高速缓存的利用有负面影响，页首地址对齐在页面大小上使得如果每次都将数据存放到从伙伴系统分配的页开始的位置会使得高速缓存的有的行被过度使用，而有的行几乎从不被使用。slab分配器通过着色使得slab对象能够均匀的使用高速缓存，提高高速缓存的利用率

当然，slab分配器也存在缺点：

对于微型嵌入式系统，它显得比较复杂，这是可以使用经过优化的slab分配器，它使用内存块链表，并使用最先适配算法
对于具有大量内存的大型系统，仅仅建立slab分配器的数据结构就需要大量内存，这时候可以使用经过优化的slub分配器