一、静态分区法

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

1、等尺寸分区

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

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

2、不等尺寸分区（固定分配、最佳适应分配）

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

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

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

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

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

二、动态分区法

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

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

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

3、解决外部碎片 --> 紧缩：

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

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

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

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

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

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

4、动态分配算法：

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

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

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

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

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

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

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

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

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

三、伙伴算法 Buddy

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

1、

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

记录大小不同的空闲页：

示意图：

2、

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

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

3、限定伙伴的尺寸

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

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

4、每个页有一个管理结构

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

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

5、

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

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

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

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

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

6、分配算法

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）回收物理内存：

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

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

四、Slab 算法

1、

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

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

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

2、

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

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

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