Buddy的分配算法假设这是一个连续的页框，阴影部分表示已经使用的页框，现在需要申请连续的5个页框。这时候，如果在这段内存中找不到5个连续的空闲页框，就会去另一段内存中寻找5个连续的页框。这样，随着时间的推移，页框就会被浪费掉。为了避免这种情况，Linux内核中引入了伙伴系统算法（Buddysystem）。将所有空闲页框分组为11个块链表，每个块链表包含大小为1、2、4、8、16、32、64、128、256、512和1024个连续页框的页框块。最多可申请1024个连续页框，对应4MB连续内存。每个页框块的第一个页框的物理地址是块大小的整数倍，如图：假设你要申请一个有256个页框的块，??首先从链接中搜索一个空闲块256个页框的链表，如果不是，则转到512个页框的链表。如果找到，则将该页框块分成两块256页框，一块分配给应用程序，另一块移到256页框的链表中。如果512页框的链表中仍然没有空闲块，则继续查找1024页框的链表，如果仍然没有空闲块，则返回错误。当一个页框块被释放时，它会主动将两个连续的页框块合并成一个更大的页框块。由上可知，Buddy算法一直在对页框进行拆解和合并。Buddy算法很棒，因为它使用世界上任何可以由2^n的和组成的正整数。这也是管理空闲页表的Buddy算法的精髓所在。我们可以通过以下命令获取freememory的信息：也可以通过echom>/proc/sysrq-trigger观察buddy的状态，与/proc/buddyinfo中的信息一致：细心的CMA读者可能会发现那就是当Buddy算法在对内存进行拆解和重组的过程中会造成碎片化，这样内存就不会再有大块的连续内存，而是全是小块的内存。当然，这对应用程序没有影响（前面我们提到，不连续的物理地址可以通过页表连接到虚拟地址），但是内核态是没有办法获取大块连续的内存（例如DMA、相机、GPU需要具有连续物理地址的大内存块）。CMA一般用于嵌入式设备来解决上述问题。CMA的全称是contiguousmemoryallocator。它的工作原理是：预留一段内存供驱动程序使用，但当驱动程序不使用时，可以将CMA区分配给用户进程用于匿名内存或页面缓存。当驱动程序需要使用它时，进程占用的内存将被回收或迁移，以腾出之前占用的预留内存供驱动程序使用。Slab在Linux中，伙伴系统以页为单位管理和分配内存。但实际需求是以字节为单位的。如果我们需要申请20Bytes，我们不能分配一个页面！岂不是严重浪费内存。那么怎么分配呢？slab分配器应运而生，专门为小内存分配设计的。slab分配器以Byte为单位分配内存。但是slab分配器并没有脱离伙伴系统，而是在伙伴系统分配的大内存的基础上进一步细分为小内存分配。我们先来看一张图。kmem_cache是??cache_chain的链表，描述了一个缓存。每个缓存都包含一个slab列表，通常是一个连续的内存块。有3种slab：slabs_full（完全分配的slab）slabs_partial（部分分配的slab）slabs_empty（空slab，或者没有分配对象）。slab是slab分配器的最小单位。在实现中，一个slab由一个或多个连续的物理页（通常只有一页）组成。单个slab可以在slab链表之间移动。例如，如果一个半满的slab在分配对象后变满了，它会从slabs_partial中删除，同时插入到slabs_full中。为了进一步说明，这里举例说明structkmem_cache结构体所描述的一段内存称为slabcachepool。slab缓存池就像一盒牛奶。一盒牛奶里有很多瓶牛奶，每瓶牛奶都是一个对象。分配内存时，就像从牛奶箱中取出一瓶。总会有结束的那一天。当盒子空了，你需要去超市再买一盒。超市相当于一个偏链表，超市里存放着很多箱子的牛奶。如果超市也卖完了，自然会从厂家进货卖给你。制造商相当于合作伙伴系统。可以使用如下命令查看slabcache的信息：总结一下，从内存DDR划分不同的ZONE，到CPU访问的Pages通过页表映射ZONEs，再到管理这些PagesBuddy算法和Slab算法，我们应该可以从感官的角度理解下图：
