内存分配

最近看了一些关于内存分配的分享，发现操作系统相关的知识都忘光了，于是打算借助Linux内核的内存分配机制，简单复习一下内存分配相关的理论知识

程序运行时不断进行内存的申请与释放，高效的分配方式不仅能提高内存的利用率，还能提高性能。

Linux内存分配原理

地址

程序需要装入内存才能运行，程序开始的位置相较于内存0地址会有一段偏移，这个偏移被称为物理地址。

在程序内部，以程序开头为0地址，向后偏移得到的地址称为逻辑地址。

分配

内存分配最大的问题是内存碎片问题，大的数据间总是残余一些小的空间，这些空间整体数量较多，但是单个空间较小，无法满足存入新的大数据，于是尽管我们还有大量空间没有被使用，但是无法分配给新的数据。

• 连续分配（将程序放在一起）
  • 单一连续分配
    • 系统区
    • 用户区
  • 固定分区分配
  • 可变分区分配
    • 首次适应
    • 最后适应
    • 最佳适应
    • 最坏适应
• 不连续分配（将程序分散放置）
  • 页式管理
  • 段式管理

Intel CPU硬件支持段式管理和二层页式管理，Liunx主要使用二层页式管理。

页式管理

一本书有很多页，每一页都有页码，页码可以唯一标识一本书中的某一页，页式管理就是将数据分成一个个大小相等的页，每一页都有一个唯一的页码，通过页码可以找到对应的数据

页式管理是一种不连续分配技术，将数据的逻辑地址拆成一个个大小相等的页面。将内存也拆成一个个大小相等的页框（物理块），并为每个页框分配一个唯一的页框号。

程序被装入内存时，被拆成多个页，这些页会被放入内存中不连续的位置，通常只有最后一页会写不满，因此只会产生一个页内碎片。

上图中间的是页表，存储着页号和物理块的对应关系，以实现页间寻址。
页内的数据通过虚地址（页号+页内偏移量）来实现页内寻址。

为了提速，页表含有一个缓存机制。

我们上面的页表是连续分配的，而对于一个32位系统，他拥有一个大小为$2^{32}$的逻辑空间，会形成一个巨大的页表。为此我们将页表也进行拆分，离散存储在内存中，使用一个外层目录表来存储页表的地址。当我们需要某一个页数据时，通过外层目录找到对应页表的地址，将该部分页表装入内存，再通过页表找到对应的页数据。这个方案叫做二级页表。

常见内存分配器

Linux内核为不同场景设计了不同的分配器，比如Slab、TLSF、Buddy，内存分配器需要在分配性能和空间利用率间做出权衡。

我感觉这三个分配器并不是平级的关系，Buddy像是一个硬件级、操作系统级的分配器，进行页面级别的内存分配，他解决了程序要怎么分散放置在内存中。TLSF解决了如何具体分配一块指定大小的内存。Slab则为内存分配提供了缓存优化。

Buddy

以内存页（4kb）为单位分配内存，本质还是一种空闲链表法

Buddy系统将内存拆分为多个物理块，这些块的大小均为2的幂次方

Buddy分配器维护了一个空闲位图（也有用二叉树维护的），这个位图是一个数组，数组的每个元素是一个链表。链表中每一个元素均为$2^n$大小的空闲物理块，其中$n$为order的值。

当分配一个大小为k的内存时，分配器会找到比k大且order值最小的空闲块，如果这个最小的空闲块比k的两倍还大，那么将这个空闲块拆分为二，再次进行分配。

当释放一块内存时，将新的内存块放入对应链表中，若该链表中内存块过多，会进行合并操作

TLSF

用于分配介于512b和512kb的数据，实现可以参考tlsf

TLSF（Two-Level Segregated Fit）的核心是使用两级链表。

第一级链表（下图f1）将空闲内存块大小根据二的幂次方进行分类（注意，这里表示的是内存的粗细粒度，而非要求内存块大小必须为二的幂次方），该行的内存块大小范围为$[2^i, 2^{i+1})$

第二级链表（下图s1）按照间隔，将索引$[2^i, 2^{i+1})$进行分段，以加速查找。二级链表的值是一个链表，链表中的每个元素是一个空闲内存块，大小和索引值相同。

FL_bitmap和SL_bitmaps[]的每一个bit表示是否被使用。

当我们需要分配一个大小为89Bytes的内存时，这个数据范围在$[64, 128)$，我们通过FL_bitmap判断出第6行是有空闲块的。然后通过SL_bitmaps[6]判断出$[88, 96)$这个范围中有空闲块，最后分配出89Bytes大小的内存块

TLSF分配、释放、再分配复杂度均为稳定的O(1)，且适用于高负载和多线程环境。不过尽管操作复杂度都是常数级，但位图操作比较复杂，速度并不一定快

Slab

用于小于512b、频繁被销毁创建的数据，

上面的Buddy算法以页为单位进行分配，对于几字节的小文件，这十分浪费。Slab分配器用于在一个页框内分配小存储区，是对Buddy分配在小文件的补充。

Slab分配器是一种基于缓存的内存分配方法，对于一些高频使用的对象（比如进程描述符），将其放入Slab缓存中。

当需要创建一个对象时直接从缓存中拿去一份（所有权转移？）。当进程结束后，并不将对象所在的页框释放，而是重新放回Slab分配器中。

一个对象可以同时有着多个副本缓存，我们将同一个对象的所有缓存存入一个双向循环链表中，这个链表被称为“缓存链”。

通过着色技术提高缓存利用率。

缓存着色技术

缓存着色技术适用于组相联映射缓存

缓存的组织组织方式：

• 直接映射
• 组相连映射（set associative cache）
• 全相连映射（full associative cache）

直接映射：内存地址到缓存地址的映射是唯一的，通常为取模运算。这会导致相邻的内存会被映射到同一缓存地址，导致缓存冲突（conflict miss）

全相联映射：允许内存地址映射到任何缓存地址。但是为了检查特定地址是否在缓存中，需要整个便利。通常要实现一套LRU（最近最少使用）系统。全相联缓存硬件复杂，而且极其昂贵，一般都极其小。

组相联映射是对两者的折中，将整个缓存分成n个组，每个组中有m块。将内存做拆分，每个内存块有n行数据。内存中第i行的数据可以存在第i组缓存中，内存块和块之间共享m块缓存。当内存数据存入缓存时，通过取模运算得到组号，再便利组内数据，判断该数据是否已经在缓存中了。

然后我们发现，如果同时多个数据他们的组号相同，他们还是会被映射到同一个组内，一旦数量超过了m条，就会引发缓存冲突。

缓存着色技术将内存、程序、缓存进行分行并标色，对于一段程序，操作系统会尽量将程序的某一行放到对应颜色的内存行、缓存行中（红色的程序行放在红色的缓存行中）。

参考

《操作系统原理及应用（Linux）》王红

Building Night City: The Technology of ‘Cyberpunk 2077’ - GDC 2021

TLSF内存分配器

TLSF内存分配原理

组相联缓存机制