如何避免内存碎片

频繁地请求和释放不同大小的内存，必然导致内存碎片问题的产生，结果就是当再次要求分配连续的内存时，即使整体内存是足够的，也无法满足连续内存的需求。该问题也称之为外碎片(external fragmentation)。

解决方案：

避免外碎片的方法有两种:

1、利用分页单元把一组非连续的空闲页框映射到连续的线性地址

2、开发一种适当的技术来记录现存的空闲的连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲快

第一种方案的意思是，我们使用地址转换技术，把非连续的物理地址转换成连续的线性地址。

第二种方案的意思是，开发一种特有的分配技术来记录下来空闲内存的情况，从而解决内存碎片问题。

Linux采用了第二种方案，因为在某些情况下，系统的确需要连续的物理地址（DMA处理器可以直接访问总线）。

Linux采用著名的伙伴系统(buddy system)算法来解决外碎片问题。把所有的空闲页框分组为11个块链表，每个链表分别包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续的页框，对1024个页框的最大请求对应着4MB大小的连续RAM（每页大小为4KB），每个块的第一个页框的物理地址是该块大小的整数倍，例如，大小为16个页框的块，其起始地址是16*2^12的倍数。

我们通过一个例子来说明伙伴算法的工作原理，假设现在要请求一个256个页框的块（1MB），算法步骤如下：

• 在256个页框的链表中检查是否有一个空闲快，如果没有，查找下一个更大的块，如果有，请求满足。

• 在512个页框的链表中检查是否有一个空闲块，如果有，把512个页框的空闲块分为两份，第一份用于满足请求，第二份链接到256个页框的链表中。如果没有空闲块，继续寻找下一个更大的块。

以上过程的逆过程，就是页框块的释放过程，也是该算法名字的由来，内核试图把大小为B的一对空闲伙伴块合并为一个2B的单独块，满足以下条件的两个块称之为伙伴：

• 两个块具有相同的大小

• 他们的物理地址是连续的

第一块的第一个页框的物理地址是2 * B * 2^12

该算法是递归的，如果它成功合并了B，就会试图去合并2B，以再次试图形成更大的块。

由 *** 作系统或系统管理员预先将内存划分成若干个分区。在系统运行过程中，分区的边界不再改变。分配时，找一个空闲且足够大的分区。如没有合适的分区：①让申请者等待。②先换出某分区的内容，再将其分配出去。 为申请者分配指定的分区或任选一个分区。如果没有空闲分区，可将一个分区的内容换出。可能需要重定位。 会出现内部碎片，无法满足大内存的需求。 可减少内部碎片。减少对大内存需求的限制。 ①固定分配：只分配某种尺寸的特定分区，如分区已被使用，申请者必须等待。 可能出现不公平等待：虽有更大尺寸的空闲分区，却必须等待。 ②最佳适应分配：分配能满足需要的最小尺寸的空闲分区，只有当所有分区都已用完时，申请者才需要等待。灵活，但可能产生较大的内部碎片。 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所属队列。

---