slab管理算法内存碎片

1. 伙伴算法和slab算法

内存碎片太小和管理内存碎片的效率问题

原因：分配内存时，不能将相邻内存合并

解决办法：

如果申请的内存大小为n，则向上取整为2的幂次数，定位到响应组，到组中(链表上)找空闲块分配出去；若没有空闲块，则到上一组找，直到找到为止，并将剩余的内存放到下面适当的组中。

用完内存需要归还，根据实际内存块大小向上取整为2的幂次数，归入链表。

注：伙伴算法使用位图标记内存块的使用情况

slab以内存池为思想，解决内部碎片问题，专门解决小内存问题。

2. linux 内存管理（buddy 和 slab）

Linux 在拿到一大块内存后（譬如是64MB内存），先将其看作是好多个连续排列的 4MB 内存。
那么如果程序请求1MB的内存，那么内存分配操作逻辑如下：

这个算法就是所谓的 binary buddy 分配算法。
在 Linux 中，这个二分法最小分割到 4096 字节，也就是一个页的大小。
因此总共有 11 种大小，分别为 4KB，8KB，……4MB。
其中 4KB 为 order 0，4MB 为 order 10.
我们称其 max order 为 12，有些资料会提到这个概念。

以上这些信息可以在 /proc/buddyinfo 上查看，其格式大概是这样：

buddy 在上面这种情况下，有些被分为小块内存，那么就会存在内存碎片的问题。
/proc/pagetypeinfo

以上 buddy 管理的是不小于4K 的内存分配，slab 则是管理小于4KB 的内存对象。

3. 外碎片与内碎片

内部碎片
是处于操作系统分配的用于装载某一进程的内存区域内部的存储块。占有这些区域或页面的进程并不使用这个存储块。而在进程占有这块存储块时，系统无法利用它。直到进程释放它，或进程结束时，系统才有可能利用这个存储块。
外部碎片
外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。
外部碎片是处于任何两个已分配区域或页面之间的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。

内部碎片的产生 ：因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。

外部碎片的产生 ： 频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，就会产生外部碎片。假设有一块一共有100个单位的连续空闲内存空间，范围是0 _{99。如果你从中申请一块内存，如10个单位，那么申请出来的内存块就为0} 9区间。这时候你继续申请一块内存，比如说5个单位大，第二块得到的内存块就应该为10 _{14区间。如果你把第一块内存块释放，然后再申请一块大于10个单位的内存块，比如说20个单位。因为刚被释放的内存块不能满足新的请求，所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是0} 9空闲，10 _{14被占用，15} 24被占用，25 _{99空闲。其中0} 9就是一个内存碎片了。如果10 _{14一直被占用，而以后申请的空间都大于10个单位，那么0} 9就永远用不上了，变成外部碎片。
 
伙伴算法(buddy)用来解决外碎片
slab算法用来解决内碎片

4. linux中使用了什么内存管理方法,为什么

“事实胜于雄辩”，我们用一个小例子（原形取自《User-Level Memory Management》）来展示上面所讲的各种内存区的差别与位置。

进程的地址空间对应的描述结构是“内存描述符结构”,它表示进程的全部地址空间，——包含了和进程地址空间有关的全部信息，其中当然包含进程的内存区域。

进程内存的分配与回收

创建进程fork()、程序载入execve()、映射文件mmap()、动态内存分配malloc()/brk()等进程相关操作都需要分配内存给进程。不过这时进程申请和获得的还不是实际内存，而是虚拟内存，准确的说是“内存区域”。进程对内存区域的分配最终都会归结到do_mmap（）函数上来（brk调用被单独以系统调用实现，不用do_mmap()），

内核使用do_mmap()函数创建一个新的线性地址区间。但是说该函数创建了一个新VMA并不非常准确，因为如果创建的地址区间和一个已经存在的地址区间相邻，并且它们具有相同的访问权限的话，那么两个区间将合并为一个。如果不能合并，那么就确实需要创建一个新的VMA了。但无论哪种情况，do_mmap()函数都会将一个地址区间加入到进程的地址空间中－－无论是扩展已存在的内存区域还是创建一个新的区域。

同样，释放一个内存区域应使用函数do_ummap()，它会销毁对应的内存区域。

如何由虚变实！

从上面已经看到进程所能直接操作的地址都为虚拟地址。当进程需要内存时，从内核获得的仅仅是虚拟的内存区域，而不是实际的物理地址，进程并没有获得物理内存（物理页面——页的概念请大家参考硬件基础一章），获得的仅仅是对一个新的线性地址区间的使用权。实际的物理内存只有当进程真的去访问新获取的虚拟地址时，才会由“请求页机制”产生“缺页”异常，从而进入分配实际页面的例程。

该异常是虚拟内存机制赖以存在的基本保证——它会告诉内核去真正为进程分配物理页，并建立对应的页表，这之后虚拟地址才实实在在地映射到了系统的物理内存上。（当然，如果页被换出到磁盘，也会产生缺页异常，不过这时不用再建立页表了）

这种请求页机制把页面的分配推迟到不能再推迟为止，并不急于把所有的事情都一次做完（这种思想有点像设计模式中的代理模式（proxy））。之所以能这么做是利用了内存访问的“局部性原理”，请求页带来的好处是节约了空闲内存，提高了系统的吞吐率。要想更清楚地了解请求页机制，可以看看《深入理解linux内核》一书。

这里我们需要说明在内存区域结构上的nopage操作。当访问的进程虚拟内存并未真正分配页面时，该操作便被调用来分配实际的物理页，并为该页建立页表项。在最后的例子中我们会演示如何使用该方法。

系统物理内存管理

虽然应用程序操作的对象是映射到物理内存之上的虚拟内存，但是处理器直接操作的却是物理内存。所以当应用程序访问一个虚拟地址时，首先必须将虚拟地址转化成物理地址，然后处理器才能解析地址访问请求。地址的转换工作需要通过查询页表才能完成，概括地讲，地址转换需要将虚拟地址分段，使每段虚地址都作为一个索引指向页表，而页表项则指向下一级别的页表或者指向最终的物理页面。

每个进程都有自己的页表。进程描述符的pgd域指向的就是进程的页全局目录。下面我们借用《linux设备驱动程序》中的一幅图大致看看进程地址空间到物理页之间的转换关系。

上面的过程说起来简单，做起来难呀。因为在虚拟地址映射到页之前必须先分配物理页——也就是说必须先从内核中获取空闲页，并建立页表。下面我们介绍一下内核管理物理内存的机制。

物理内存管理（页管理）

Linux内核管理物理内存是通过分页机制实现的，它将整个内存划分成无数个4k（在i386体系结构中）大小的页，从而分配和回收内存的基本单位便是内存页了。利用分页管理有助于灵活分配内存地址，因为分配时不必要求必须有大块的连续内存[3]，系统可以东一页、西一页的凑出所需要的内存供进程使用。虽然如此，但是实际上系统使用内存时还是倾向于分配连续的内存块，因为分配连续内存时，页表不需要更改，因此能降低TLB的刷新率（频繁刷新会在很大程度上降低访问速度）。

鉴于上述需求，内核分配物理页面时为了尽量减少不连续情况，采用了“伙伴”关系来管理空闲页面。伙伴关系分配算法大家应该不陌生——几乎所有操作系统方面的书都会提到,我们不去详细说它了，如果不明白可以参看有关资料。这里只需要大家明白Linux中空闲页面的组织和管理利用了伙伴关系，因此空闲页面分配时也需要遵循伙伴关系，最小单位只能是2的幂倍页面大小。内核中分配空闲页面的基本函数是get_free_page/get_free_pages，它们或是分配单页或是分配指定的页面（2、4、8…512页）。

注意：get_free_page是在内核中分配内存，不同于malloc在用户空间中分配，malloc利用堆动态分配，实际上是调用brk()系统调用，该调用的作用是扩大或缩小进程堆空间（它会修改进程的brk域）。如果现有的内存区域不够容纳堆空间，则会以页面大小的倍数为单位，扩张或收缩对应的内存区域，但brk值并非以页面大小为倍数修改，而是按实际请求修改。因此Malloc在用户空间分配内存可以以字节为单位分配,但内核在内部仍然会是以页为单位分配的。

另外,需要提及的是，物理页在系统中由页结构structpage描述，系统中所有的页面都存储在数组mem_map[]中，可以通过该数组找到系统中的每一页（空闲或非空闲）。而其中的空闲页面则可由上述提到的以伙伴关系组织的空闲页链表（free_area[MAX_ORDER]）来索引。

内核内存使用

Slab

所谓尺有所长，寸有所短。以页为最小单位分配内存对于内核管理系统中的物理内存来说的确比较方便，但内核自身最常使用的内存却往往是很小（远远小于一页）的内存块——比如存放文件描述符、进程描述符、虚拟内存区域描述符等行为所需的内存都不足一页。这些用来存放描述符的内存相比页面而言，就好比是面包屑与面包。一个整页中可以聚集多个这些小块内存；而且这些小块内存块也和面包屑一样频繁地生成/销毁。

为了满足内核对这种小内存块的需要，Linux系统采用了一种被称为slab分配器的技术。Slab分配器的实现相当复杂，但原理不难，其核心思想就是“存储池[4]”的运用。内存片段（小块内存）被看作对象，当被使用完后，并不直接释放而是被缓存到“存储池”里，留做下次使用，这无疑避免了频繁创建与销毁对象所带来的额外负载。

Slab技术不但避免了内存内部分片（下文将解释）带来的不便（引入Slab分配器的主要目的是为了减少对伙伴系统分配算法的调用次数——频繁分配和回收必然会导致内存碎片——难以找到大块连续的可用内存），而且可以很好地利用硬件缓存提高访问速度。

Slab并非是脱离伙伴关系而独立存在的一种内存分配方式，slab仍然是建立在页面基础之上，换句话说，Slab将页面（来自于伙伴关系管理的空闲页面链表）撕碎成众多小内存块以供分配，slab中的对象分配和销毁使用kmem_cache_alloc与kmem_cache_free。

Kmalloc

Slab分配器不仅仅只用来存放内核专用的结构体，它还被用来处理内核对小块内存的请求。当然鉴于Slab分配器的特点，一般来说内核程序中对小于一页的小块内存的请求才通过Slab分配器提供的接口Kmalloc来完成（虽然它可分配32到131072字节的内存）。从内核内存分配的角度来讲，kmalloc可被看成是get_free_page（s）的一个有效补充，内存分配粒度更灵活了。

有兴趣的话，可以到/proc/slabinfo中找到内核执行现场使用的各种slab信息统计，其中你会看到系统中所有slab的使用信息。从信息中可以看到系统中除了专用结构体使用的slab外，还存在大量为Kmalloc而准备的Slab（其中有些为dma准备的）。

内核非连续内存分配（Vmalloc）

伙伴关系也好、slab技术也好，从内存管理理论角度而言目的基本是一致的，它们都是为了防止“分片”，不过分片又分为外部分片和内部分片之说，所谓内部分片是说系统为了满足一小段内存区（连续）的需要，不得不分配了一大区域连续内存给它，从而造成了空间浪费；外部分片是指系统虽有足够的内存，但却是分散的碎片，无法满足对大块“连续内存”的需求。无论何种分片都是系统有效利用内存的障碍。slab分配器使得一个页面内包含的众多小块内存可独立被分配使用，避免了内部分片，节约了空闲内存。伙伴关系把内存块按大小分组管理，一定程度上减轻了外部分片的危害，因为页框分配不在盲目，而是按照大小依次有序进行，不过伙伴关系只是减轻了外部分片，但并未彻底消除。你自己比划一下多次分配页面后，空闲内存的剩余情况吧。

所以避免外部分片的最终思路还是落到了如何利用不连续的内存块组合成“看起来很大的内存块”——这里的情况很类似于用户空间分配虚拟内存，内存逻辑上连续，其实映射到并不一定连续的物理内存上。Linux内核借用了这个技术，允许内核程序在内核地址空间中分配虚拟地址，同样也利用页表（内核页表）将虚拟地址映射到分散的内存页上。以此完美地解决了内核内存使用中的外部分片问题。内核提供vmalloc函数分配内核虚拟内存，该函数不同于kmalloc，它可以分配较Kmalloc大得多的内存空间（可远大于128K，但必须是页大小的倍数），但相比Kmalloc来说,Vmalloc需要对内核虚拟地址进行重映射，必须更新内核页表，因此分配效率上要低一些（用空间换时间）

与用户进程相似,内核也有一个名为init_mm的mm_strcut结构来描述内核地址空间，其中页表项pdg=swapper_pg_dir包含了系统内核空间（3G-4G）的映射关系。因此vmalloc分配内核虚拟地址必须更新内核页表，而kmalloc或get_free_page由于分配的连续内存，所以不需要更新内核页表。

vmalloc分配的内核虚拟内存与kmalloc/get_free_page分配的内核虚拟内存位于不同的区间，不会重叠。因为内核虚拟空间被分区管理，各司其职。进程空间地址分布从0到3G(其实是到PAGE_OFFSET,在0x86中它等于0xC0000000)，从3G到vmalloc_start这段地址是物理内存映射区域（该区域中包含了内核镜像、物理页面表mem_map等等）比如我使用的系统内存是64M(可以用free看到)，那么(3G——3G+64M)这片内存就应该映射到物理内存，而vmalloc_start位置应在3G+64M附近（说"附近"因为是在物理内存映射区与vmalloc_start期间还会存在一个8M大小的gap来防止跃界）,vmalloc_end的位置接近4G(说"接近"是因为最后位置系统会保留一片128k大小的区域用于专用页面映射，还有可能会有高端内存映射区，这些都是细节，这里我们不做纠缠)。

上图是内存分布的模糊轮廓

由get_free_page或Kmalloc函数所分配的连续内存都陷于物理映射区域，所以它们返回的内核虚拟地址和实际物理地址仅仅是相差一个偏移量（PAGE_OFFSET），你可以很方便的将其转化为物理内存地址，同时内核也提供了virt_to_phys（）函数将内核虚拟空间中的物理映射区地址转化为物理地址。要知道，物理内存映射区中的地址与内核页表是有序对应的，系统中的每个物理页面都可以找到它对应的内核虚拟地址（在物理内存映射区中的）。

而vmalloc分配的地址则限于vmalloc_start与vmalloc_end之间。每一块vmalloc分配的内核虚拟内存都对应一个vm_struct结构体（可别和vm_area_struct搞混，那可是进程虚拟内存区域的结构），不同的内核虚拟地址被4k大小的空闲区间隔，以防止越界——见下图）。与进程虚拟地址的特性一样，这些虚拟地址与物理内存没有简单的位移关系，必须通过内核页表才可转换为物理地址或物理页。它们有可能尚未被映射，在发生缺页时才真正分配物理页面。

这里给出一个小程序帮助大家认清上面几种分配函数所对应的区域。

#include<linux/mole.h>

#include<linux/slab.h>

#include<linux/vmalloc.h>

unsignedchar*pagemem;

unsignedchar*kmallocmem;

unsignedchar*vmallocmem;

intinit_mole(void)

{

pagemem = get_free_page(0);

printk("<1>pagemem=%s",pagemem);

kmallocmem = kmalloc(100,0);

printk("<1>kmallocmem=%s",kmallocmem);

vmallocmem = vmalloc(1000000);

printk("<1>vmallocmem=%s",vmallocmem);

}

voidcleanup_mole(void)

{

free_page(pagemem);

kfree(kmallocmem);

vfree(vmallocmem);

}

实例

内存映射(mmap)是Linux操作系统的一个很大特色，它可以将系统内存映射到一个文件（设备）上，以便可以通过访问文件内容来达到访问内存的目的。这样做的最大好处是提高了内存访问速度，并且可以利用文件系统的接口编程（设备在Linux中作为特殊文件处理）访问内存，降低了开发难度。许多设备驱动程序便是利用内存映射功能将用户空间的一段地址关联到设备内存上，无论何时，只要内存在分配的地址范围内进行读写，实际上就是对设备内存的访问。同时对设备文件的访问也等同于对内存区域的访问，也就是说，通过文件操作接口可以访问内存。Linux中的X服务器就是一个利用内存映射达到直接高速访问视频卡内存的例子。

熟悉文件操作的朋友一定会知道file_operations结构中有mmap方法，在用户执行mmap系统调用时，便会调用该方法来通过文件访问内存——不过在调用文件系统mmap方法前，内核还需要处理分配内存区域（vma_struct）、建立页表等工作。对于具体映射细节不作介绍了，需要强调的是,建立页表可以采用remap_page_range方法一次建立起所有映射区的页表，或利用vma_struct的nopage方法在缺页时现场一页一页的建立页表。第一种方法相比第二种方法简单方便、速度快，但是灵活性不高。一次调用所有页表便定型了，不适用于那些需要现场建立页表的场合——比如映射区需要扩展或下面我们例子中的情况。

我们这里的实例希望利用内存映射，将系统内核中的一部分虚拟内存映射到用户空间，以供应用程序读取——你可利用它进行内核空间到用户空间的大规模信息传输。因此我们将试图写一个虚拟字符设备驱动程序，通过它将系统内核空间映射到用户空间——将内核虚拟内存映射到用户虚拟地址。从上一节已经看到Linux内核空间中包含两种虚拟地址：一种是物理和逻辑都连续的物理内存映射虚拟地址；另一种是逻辑连续但非物理连续的vmalloc分配的内存虚拟地址。我们的例子程序将演示把vmalloc分配的内核虚拟地址映射到用户地址空间的全过程。

程序里主要应解决两个问题：

第一是如何将vmalloc分配的内核虚拟内存正确地转化成物理地址？

因为内存映射先要获得被映射的物理地址，然后才能将其映射到要求的用户虚拟地址上。我们已经看到内核物理内存映射区域中的地址可以被内核函数virt_to_phys转换成实际的物理内存地址，但对于vmalloc分配的内核虚拟地址无法直接转化成物理地址，所以我们必须对这部分虚拟内存格外“照顾”——先将其转化成内核物理内存映射区域中的地址，然后在用virt_to_phys变为物理地址。

转化工作需要进行如下步骤：

如下图所示：

第二是当访问vmalloc分配区时，如果发现虚拟内存尚未被映射到物理页，则需要处理“缺页异常”。因此需要我们实现内存区域中的nopaga操作，以能返回被映射的物理页面指针，在我们的实例中就是返回上面过程中的内核物理内存映射区域中的地址。由于vmalloc分配的虚拟地址与物理地址的对应关系并非分配时就可确定，必须在缺页现场建立页表，因此这里不能使用remap_page_range方法，只能用vma的nopage方法一页一页的建立。

程序组成

map_driver.c，它是以模块形式加载的虚拟字符驱动程序。该驱动负责将一定长的内核虚拟地址(vmalloc分配的)映射到设备文件上。其中主要的函数有——vaddress_to_kaddress（）负责对vmalloc分配的地址进行页表解析,以找到对应的内核物理映射地址（kmalloc分配的地址）；map_nopage()负责在进程访问一个当前并不存在的VMA页时，寻找该地址对应的物理页，并返回该页的指针。

test.c它利用上述驱动模块对应的设备文件在用户空间读取读取内核内存。结果可以看到内核虚拟地址的内容（ok!），被显示在了屏幕上。

执行步骤

编译map_driver.c为map_driver.o模块,具体参数见Makefile

加载模块：insmodmap_driver.o

生成对应的设备文件

1在/proc/devices下找到map_driver对应的设备命和设备号：grepmapdrv/proc/devices

2建立设备文件mknodmapfilec 254 0（在我的系统里设备号为254）

利用maptest读取mapfile文件，将取自内核的信息打印到屏幕上。

5. 简述内存管理中buddy算法和slab机制的区别

1、Buddy算法
linux对空闲内存空间管理采取buddy算法，
Buddy算法：
把内存中所有页面按照2^n划分，其中n=0~5，每个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。划分后形成了大小不等的存储块，称为页面块，简称页块，包含一个页面的页块称为1页块，包含2个页面的称为2页块，依次类推。
每种页块按前后顺序两两结合成一对Buddy“伙伴”。系统按照Buddy关系把具有相同大小的空闲页面块组成页块组，即1页块组、2页块组……32页块组。 每个页块组用一个双向循环链表进行管理，共有6个链表，分别为1、2、4、8、16、32页块链表。分别挂到free_area[] 数组上。
位图数组
用于标记内存页面使用情况，第0组每一位表示单个页面使用情况，1表示使用，0表示空闲，第二组每一位表示比邻的两个页面使用情况，一次类推。默认为10个数组，当一对Buddy的两个页面中有一个事空闲的，而另一个全部或部分被占用时，该位置1.两个页面块都是空闲，对应位置0.
内存分配和释放过程
内存分配时，系统按照Buddy算法，根据请求的页面数在free_area[]对应的空闲页块组中搜索。 若请求页面数不是2的整数次幂，则按照稍大于请求数的2的整数次幂的值搜索相应的页面块组。
当相应页块组中没有可使用的空闲页面块时就查询更大一些的页块组，在找到可用的页块后分配所需要的页面。当某一空闲页面被分配后，若仍有剩余的空闲页面，则根据剩余页面的大小把他们加入到相应页面组中。
内存页面释放时，系统将其作为空闲页面看待，检查是否存在与这些页面相邻的其他空闲页块，若存在，则合为一个连续的空闲区按Buddy算法重新分组。

2、Slab算法
采用buddy算法，解决了外碎片问题，这种方法适合大块内存请求，不适合小内存区请求。如：几十个或者几百个字节。Linux2.0采用传统内存分区算法，按几何分布提供内存区大小，内存区以2的幂次方为单位。虽然减少了内碎片，但没有显着提高系统效率。
Linux2.4采用了slab分配器算法，该算法比传统的分配器算法有更好性能和内存利用率，最早在solaris2.4上使用。
Slab分配器思想
1）小对象的申请和释放通过slab分配器来管理。
2）slab分配器有一组高速缓存，每个高速缓存保存同一种对象类型，如i节点缓存、PCB缓存等。
3）内核从它们各自的缓存种分配和释放对象。
4）每种对象的缓存区由一连串slab构成，每个slab由一个或者多个连续的物理页面组成。这些页面种包含了已分配的缓存对象，也包含了空闲对象。

6. 怎样设计一个内存池，减少内存碎片

一般工程里不推荐你写，因为你费力写一个出来99%可能性没有内置的好，且内存出bug难调试
一定要设计的话，你也可以当个玩具写写玩玩：

1. 实现教科书上的内存分配器：
做一个链表指向空闲内存，分配就是取出一块来，改写链表，返回，释放就是放回到链表里面，并做好归并。注意做好标记和保护，避免二次释放，还可以花点力气在如何查找最适合大小的内存快的搜索上，减少内存碎片，有空你了还可以把链表换成伙伴算法，写着玩嘛。

2. 实现固定内存分配器：
即实现一个 FreeList，每个 FreeList 用于分配固定大小的内存块，比如用于分配 32字节对象的固定内存分配器，之类的。每个固定内存分配器里面有两个链表，OpenList 用于存储未分配的空闲对象，CloseList用于存储已分配的内存对象，那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户，释放又是从 CloseList 移回到 OpenList。分配时如果不够，那么就需要增长 OpenList：申请一个大一点的内存块，切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候，统一把先前向系统申请的内存块全部还给系统。

3. 实现 FreeList 池：
在你实现了 FreeList的基础上，按照不同对象大小（8字节，16字节，32，64，128，256，512，1K。。。64K），构造十多个固定内存分配器，分配内存时根据内存大小查表，决定到底由哪个分配器负责，分配后要在头部的 header 处（ptr[-sizeof(char*)]处）写上 cookie，表示又哪个分配器分配的，这样释放时候你才能正确归还。如果大于64K，则直接用系统的 malloc作为分配，如此以浪费内存为代价你得到了一个分配时间近似O（1）的内存分配器，差不多实现了一个 memcached 的 slab 内存管理器了，但是先别得意。此 slab 非彼 slab（sunos/solaris/linux kernel 的 slab）。这说白了还是一个弱智的 freelist 无法归还内存给操作系统，某个 FreeList 如果高峰期占用了大量内存即使后面不用，也无法支援到其他内存不够的 FreeList，所以我们做的这个和 memcached 类似的分配器其实是比较残缺的，你还需要往下继续优化。

4. 实现正统的 slab （非memcached的伪 slab）代替 FreeList：
这时候你需要阅读一下论文了，现代内存分配技术的基础，如何管理 slab 上的对象，如何进行地址管理，如何管理不同 slab 的生命周期，如何将内存回收给系统。然后开始实现一个类似的东西，文章上传统的 slab 的各种基础概念虽然今天没有改变，但是所用到的数据结构和控制方法其实已经有很多更好的方法了，你可以边实现边思考下，实在不行还可以参考 kernel 源码嘛。但是有很多事情应用程序做不了，有很多实现你是不能照搬的，比如页面提供器，可以提供连续线性地址的页面，再比如说 kernel 本身记录着每个页面对应的 slab，你查找 slab 时，系统其实是根据线性地址移位得到页面编号，然后查表得到的，而你应用程序不可能这么干，你还得做一些额外的体系来解决这些问题，还需要写一些额外的 cookie 来做标记。做好内存收缩工作，内存不够时先收缩所有分配器的 slab，再尝试重新分配。再做好内存回收工作，多余的内存，一段时间不使用可以还给操作系统。

5. 实现混合分配策略：
你实现了上面很多常见的算法后，该具体阅读各种内存分配器的代码了，这些都是经过实践检验的，比如 libc 的内存分配器，或者参考有自带内存管理的各种开源项目，比如 python 源码，做点实验对比他们的优劣，然后根据分配对象的大小采用不同的分配策略，区别对待各种情况。试验的差不多了就得引入多线程支持了，将你的锁改小。注意很多系统层的线程安全策略你是没法弄的，比如操作系统可以关中断，短时间内禁止本cpu发生任务切换，这点应用程序就很麻烦了，还得用更小的锁来代替。当锁已经小到不能再小，也可以选择引入 STM 来代替各种链表的锁。

6. 实现 Per-CPU Cache：
现代内存分配器，在多核下的一个重要优化就是给多核增加 cache，为了进一步避免多线程锁竞争，需要引入 Per-CPU Cache 了。分配内存先找到对应线程所在的cpu，从该cpu上对应的 cache 里分配，cache 不够了就一次性从你底层的内存分配器里多分配几个对象进来填充 cache，释放时也是先放回 cache，cache里面如果对象太多，就做一次收缩，把内存换个底层分配器，让其他 cpu 的cache有机会利用。这样针对很多短生命周期的频繁的分配、释放，其实都是在 cache 里完成的，没有锁竞争，同时cache分配逻辑简单，速度更快。操作系统里面的代码经常是直接读取当前的cpu是哪个，而应用层实现你可以用 thread local storage 来代替，目前这些东西在 crt的 malloc 里还暂时支持不到位（不排除未来版本会增加），可以更多参考 tc/jemalloc。

7. 实现地址着色:
现代内存分配器必须多考虑总线压力，在很多机型上，如果内存访问集中在某条 cache line相同的偏移上，会给总线带来额外的负担和压力。比如你经常要分配一个 FILE 对象，而每个 FILE对象使用时会比较集中的访问 int FILE::flag; 这个成员变量，如果你的页面提供器提供的页面地址是按照 4K对齐的，那么很可能多个 FILE对象的 flag 成员所处的 cache line 偏移地址是相同的，大量访问这些相同的偏移地址会给总线带来很大负担，这时候你需要给每个对象额外增加一些偏移，让他们能够均匀的分布在线性地址对应的cache line 偏移上，消减总线冲突的开销。

8. 优化缓存竞争：
多核时代，很多单核时代的代码都需要针对性的优化改写，最基本的一条就是 cache 竞争，这是比前面锁竞争更恶劣的情况：如果两个cpu同时访问相同的 cache-line 或者物理页面，那么 cpu 之间为了保证内存一致性会做很多的通信工作，比如那个cpu0需要用到这段内存，发现cpu1也在用，那么需要通知cpu1，将cpu1 L1-L2缓存里面的数据写回该物理内存，并且释放控制权，这时cpu0取得了控制权才能继续操作，期间cpu0-cpu1之间的通信协议是比较复杂的，代价也是比较大的，cache竞争比锁竞争恶劣不少。为了避免 cache 竞争，需要比先前Per-CPU cache 更彻底的 Per-CPU Page 机制来解决，直接让不同的cpu使用不同的页面进行二次分配，彻底避免 cache 竞争。具体应用层的做法也是利用线性地址来判断所属页面（因为物理页面映射到进程地址也是4k对齐的），同时继续使用 thread local storage 或者用系统提供的 api 读取当前属于哪个 cpu 来实现。为了避免核太多每个核占据大量的页面带来的不必要的浪费，你可以参考下 Linux 最新的 slub 内存分配算法，但是 slub 也有未尽之处，好几个 linux 发行版在实践中发现 slub 还是存在一些问题的（非bug，而是机制），所以大部分发行版默认都是关闭 slub 的，虽然，你还是可以借鉴测试一下。

9. 调试和折腾：
继续参考各种现代内存分配器，取长补短，然后给你的分配器添加一些便于调试的机制，方便诊断各种问题。在你借鉴了很多开源项目，自己也做了一些所谓的优化，折腾了那么久以后，你或许以为你的分配器可以同各种开源分配器一战了，测试效果好像也挺好的，先别急，继续观察内存利用率，向操作系统申请/归还内存的频率等一系列容易被人忽视的指标是否相同。同时更换你的测试用例，看看更多的情况下，是否结果还和先前一样？这些都差不多的时候，你发现没有个一两年的大规模持续使用，你很难发现一些潜在的隐患和bug，可能你觉得没问题的代码，跑了两年后都会继续报bug，这很正常，多点耐心，兴许第三年以后就比较稳定了呢？

7. linux内核物理内存管理有哪些常用算法 lru slab

采用伙伴算法分配内存时，每次至少分配一个页面。但当请求分配的内存大小为几十个字节或几百个字节时应该如何处理？如何在一个页面中分配小的内存区，小内存区的分配所产生的内碎片又如何解决？
Linux2.0采用的解决办法是建立了13个空闲区链表，它们的大小从32字节到132056字节。从Linux2.2开始，MM的开发者采用了一种叫做slab的分配模式，该模式早在1994年就被开发出来，用于Sun Microsystem Solaris 2.4操作系统中。Slab的提出主要是基于以下考虑：
· 内核对内存区的分配取决于所存放数据的类型。例如，当给用户态进程分配页面时，内核调用get_free_page()函数，并用0填充这个页面。 而给内核的数据结构分配页面时，事情没有这么简单，例如，要对数据结构所在的内存进行初始化、在不用时要收回它们所占用的内存。因此，Slab中引入了对象这个概念，所谓对象就是存放一组数据结构的内存区，其方法就是构造或析构函数，构造函数用于初始化数据结构所在的内存区，而析构函数收回相应的内存区。但为了便于理解，你也可以把对象直接看作内核的数据结构。为了避免重复初始化对象，Slab分配模式并不丢弃已分配的对象，而是释放但把它们依然保留在内存中。当以后又要请求分配同一对象时，就可以从内存获取而不用进行初始化，这是在Solaris 中引入Slab的基本思想。
实际上，Linux中对Slab分配模式有所改进，它对内存区的处理并不需要进行初始化或回收。出于效率的考虑，Linux并不调用对象的构造或析构函数，而是把指向这两个函数的指针都置为空。Linux中引入Slab的主要目的是为了减少对伙伴算法的调用次数。
· 实际上，内核经常反复使用某一内存区。例如，只要内核创建一个新的进程，就要为该进程相关的数据结构（task_struct、打开文件对象等）分配内存区。当进程结束时，收回这些内存区。因为进程的创建和撤销非常频繁，因此，Linux的早期版本把大量的时间花费在反复分配或回收这些内存区上。从Linux2.2开始，把那些频繁使用的页面保存在高速缓存中并重新使用。
· 可以根据对内存区的使用频率来对它分类。对于预期频繁使用的内存区，可以创建一组特定大小的专用缓冲区进行处理，以避免内碎片的产生。对于较少使用的内存区，可以创建一组通用缓冲区（如Linux2.0中所使用的2的幂次方）来处理，即使这种处理模式产生碎片，也对整个系统的性能影响不大。
· 硬件高速缓存的使用，又为尽量减少对伙伴算法的调用提供了另一个理由，因为对伙伴算法的每次调用都会“弄脏”硬件高速缓存，因此，这就增加了对内存的平均访问次数。
Slab分配模式把对象分组放进缓冲区（尽管英文中使用了Cache这个词，但实际上指的是内存中的区域，而不是指硬件高速缓存）。因为缓冲区的组织和管理与硬件高速缓存的命中率密切相关，因此，Slab缓冲区并非由各个对象直接构成，而是由一连串的“大块（Slab）”构成，而每个大块中则包含了若干个同种类型的对象，这些对象或已被分配，或空闲，如图6.12所示。一般而言，对象分两种，一种是大对象，一种是小对象。所谓小对象，是指在一个页面中可以容纳下好几个对象的那种。例如，一个inode结构大约占300多个字节，因此，一个页面中可以容纳8个以上的inode结构，因此，inode结构就为小对象。Linux内核中把小于512字节的对象叫做小对象。

8. 【我的笔记】内存管理（二）分区方法（静态、动态、伙伴、Slab）

由操作系统或系统管理员预先将内存划分成若干个分区。在系统运行过程中，分区的边界不再改变。分配时，找一个空闲且足够大的分区。如没有合适的分区：①让申请者等待。②先换出某分区的内容，再将其分配出去。

为申请者分配指定的分区或任选一个分区。如果没有空闲分区，可将一个分区的内容换出。可能需要重定位。

会出现内部碎片，无法满足大内存的需求。

可减少内部碎片。减少对大内存需求的限制。

①固定分配：只分配某种尺寸的特定分区，如分区已被使用，申请者必须等待。

可能出现不公平等待：虽有更大尺寸的空闲分区，却必须等待。

②最佳适应分配：分配能满足需要的最小尺寸的空闲分区，只有当所有分区都已用完时，申请者才需要等待。灵活，但可能产生较大的内部碎片。

3、静态分区：内存利用率低，产生内部碎片；尺寸和分区数量难以确定。

1、不预先确定分区的大小和数量，将分区工作推迟到实际分配内存时进行。  Lazy

初始情况下，把所有的空闲内存看成一个大分区。分配时，按申请的尺寸，找一块足够大的空闲内存分区，临时从中划出一块构成新分区。新分区的尺寸与申请的大小相等，不会出现内部碎片。回收时，尽可能与邻近的空闲分区合并。在内存紧缺时，可将某个选定的分区换出。

2、会产生外部碎片，如下图（内部碎片是指 eg：要 1M，分了 8M，产生 7M 的碎片）：

移动内存中的进程，将碎片集中起来，重新构成大的内存块。需要运行时的动态重定位，费时。

（1）紧缩方向：向一头紧缩，向两头紧缩。

（2）紧缩时机：①在释放分区时，如果不能与空闲分区合并，则立刻进行紧缩。

好处是不存在外部碎片，坏处是费时。

②在内存分配时，如果剩余的空闲空间总量能满足要求但没有一个独立的空闲块能满足要求，则进行紧缩。

好处是减少紧缩次数。Lazy。

①最先适应算法（First fit）：从头开始，在满足要求的第一个空闲块中分配。

分区集中在内存的前部，大内存留在后面，便于释放后的合并。

②最佳适应算法（Best fit）：遍历空闲块，在满足要求的最小空闲块中分配。

留下的碎片最小，基本无法再用，需要更频繁地紧缩。

③下一个适应算法（Next fit）：从上次分配的位置开始，在满足要求的下一个空闲块中分配。

对内存的使用较平均，不容易留下大的空闲块。

④最差适应算法（Worst Fit）：遍历空闲块，在满足要求的最大空闲块中分配。

留下的碎片较大，但不会剩余大内存。

最先适应算法较优，最佳适应算法较差。

伙伴算法：将动态分区的大小限定为 2^k  字节，分割方式限定为平分，分区就会变得较为规整，分割与合并会更容易，可以减少一些外部碎片。平分后的两块互称伙伴。

1、

分配时可能要多次平分，释放时可能要多次合并。举例：

记录大小不同的空闲页：

示意图：

2、

伙伴算法是静态分区和动态分区法的折中，比静态分区法灵活，不受分区尺寸及个数的限制；比动态分区法规范，不易出现外部碎片。会产生内部碎片，但比静态分区的小。

Linux、Windows、Ucore等都采用伙伴算法管理物理内存。

一般情况下，将最小尺寸定为 2^12 字节（1页，4K=4096B），最大尺寸定为1024页，11个队列。

Linux、Windows、Ucore 等都将伙伴的最小尺寸限定为1页。

ucore 用 page，在内存初始化函数 page_init 中为系统中的每个物理页建立一个 page 结构。

页块（pageblock）是一组连续的物理页。

5、

（1）判断伙伴关系/寻找伙伴

最后两行是指，B1和B2只有第i位相反。

（2）判断伙伴是否空闲：

ucore 用 free_area[ ]数组定义空闲页块队列。

（3）确定伙伴是否在 order 队列中：

7、

（1）解决内部碎片过大问题（eg：申请5页，分配8页，浪费3页）：

ucore 在前部留下需要的页数，释放掉尾部各页。每次释放1页，先划分成页块，再逐个释放。

（2） 解决切分与合并过于频繁的问题：

用得较多的是单个页。位于处理器Cache中页称为热页（hot page），其余页称为冷页（cold page）。处理器对热页的访问速度要快于冷页。

可建一个热页队列（per_cpu_page），暂存刚释放的单个物理页，将合并工作向后推迟 Lazy。总是试图从热页队列中分配单个物理页。分配与释放都在热页队列的队头进行。

（3）解决内存碎化(有足够多的空闲页，但是没有大页块)问题：①将页块从一个物理位置移动到另一个物理位置，并保持移动前后逻辑地址不变（拷贝页块内容）；②逻辑内存管理器。

（4）满足大内存的需求：

（5）物理内存空间都耗尽的情况：

在任何情况下，都应该预留一部分空闲的物理内存以备急需。定义两条基准线low和high，当空闲内存量小于low时，应立刻开始回收物理内存，直到空闲内存量大于high。

（6）回收物理内存：

法一：启动一个守护进程，专门用于回收物理内存。周期性启动，也可被唤醒。

法二：申请者自己去回收内存。实际是由内存分配程序回收。回收的方法很多，如释放缓冲区、页面淘汰等。

1、

伙伴算法最小分配内存为页，对于更小的内存的管理 --> Slab 算法

内和运行过程中经常使用小内存（小于1页）eg：建立数据结构、缓冲区

内核对小内存的使用极为频繁、种类繁多、时机和数量难以预估。所以难以预先分配，只能动态地创建和撤销

2、

Slab 向伙伴算法申请大页块（批发），将其划分成小对象分配出去（零售）；将回收的小对象组合成大页块后还给伙伴算法。

Slab 采用等尺寸静态分区法，将页块预先划分成一组大小相等的小块，称为内存对象。

具有相同属性的多个Slab构成一个Cache，一个Cache管理一种类型（一类应该是指一个大小）的内存对象。当需要小内存时，从预建的Cache中申请内存对象，用完之后再将其还给Cache。当Cache中缺少对象时，追加新的Slab；当物理内存紧缺时，回收完全空闲的Slab。

Slab 算法的管理结构：

① Cache 管理结构：管理Slab，包括Slab的创建和销毁。

② Slab 管理结构：管理内存对象，包括小对象的分配与释放。

（Cache结构和Slab结构合作，共同实现内存对象的管理）

3、

（1）描述各个内存对象的使用情况

可以用位图标识空闲的内存对象。也可以将一个Slab中的空闲内存对象组织成队列，并在slab结构中记录队列的队头。

早期的Linux在每个内存对象的尾部都加入一个指针，用该指针将空闲的内存对象串联成一个真正的队列。（对象变长、不规范，空间浪费）

改进：将指针集中在一个数组中，用数组内部的链表模拟内存对象队列。

再改进：将数组中的指针换成对象序号，利用序号将空闲的内存对象串成队列。序号数组是动态创建的。

序号数组可以位于 Slab 内部，也可以位于 Slab 外部

（2）一个Cache会管理多个Slab，可以将所有Slab放在一个队列中。

Ucore为每个Cache准备了两个slab结构队列：全满的和不满的。Linux为每个Cache准备了三个slab结构队列：部分满的、完全满的和完全空闲的。

Linux允许动态创建Cache，Ucore不许。Ucore预定了对象大小，分别是32、64、128、256、512、1K、2K（4K、8K、16K、32K、64K、128K）。为每一种大小的对象预建了Cache。

（3）Slab是动态创建的，当Cache中没有空闲的内存对象时，即为其创建一个新的Slab。

Slab所需要的内存来自伙伴算法，大小是  2^page_order 个连续页。

4、小对象的尺寸

如按处理器一级缓存中缓存行（Cache Line）的大小（16、32字节）取齐，可使对象的开始位置都位于缓存行的边界处。

在将页块划分成内存对象的过程中，通常会剩余一小部分空间，位于所有内存对象之外，称为外部碎片。

Slab算法选用碎片最小的实现方案。

5、

（1）对象分配 kmalloc

① 根据size确定一个Cache。

② 如果Cache的slabs_notfull为空，则为其创建一个新的Slab。

③ 选中slabs_notfull中第一个Slab，将队头的小对象分配出去，并调整队列。

④ 对象的开始地址是：objp = slabp->s_mem + slabp->free * cachep->objsize;

（2）对象释放 kfree

① 算出对象所在的页号，找到它的 Page 结构。

② 根据 Page 找到所属的 Cache 和 Slab。

③ 算出对象序号：objnr = (objp - slabp->s_mem) / cachep->objsize;

④将序号插入Slab的free队列。

⑤整Slab所属队列。