这节需要讨论一个话题，不仅仅限于内存虚拟化，而是任何内存分配库或者操作系统都会关心的 —— 如何管理空闲空间，当空间被划分为固定大小的 page 时是很好管理的，例如物理内存的 paging 机制，只需要维护一个列表记录下每块区间是否空闲、被谁使用等情况。
而当虚拟内存中划分为不同大小的区块后，管理空闲空间变得困难起来，因为会们之间会存在碎片（external fragmentation）。例如下图中总的空闲空间是 20，但是由于被分成了两个碎片，实际上没有足够的连续空闲空间。
我们知道基础的 library （下文统称分配器（allocator））提供了一些 API 例如 void malloc(size t size) 和 void free(void ptr) 分别用来申请和释放内存，前者返回一个指针，后者释放内存时不需要传入大小而是只需要传入地址，因此该分配器需要某种机制记录下这块地址申请了多大的空间。分配器管理分配内存的地方是 heap，通过名为 free list 的结构记录 heap 上空闲的区块，
Low-level Mechanisms
先叙述 splitting 和 coalescing，现代分配器都会有的概念。
假设有一个 30 bytes 大小的 heap，前半段和后半段都是空闲的，中间被使用，那么 free list 里的内容：列表存在两个元素，每个元素的内容是空闲块的起始地址和空闲块大小。
当这时某个程序请求大于 10 bytes 的空间时明显都会失败，如果它请求小于 10 bytes（例如请求 1 byte） 时会发生什么呢？这时分配器会通过 splitting 机制划分一个具体大小的块出来给它，并同时调整 free list 里的内容：可见分配器将第二个空闲块的起始地址后推一位，大小修改为 9。
如何中间的区块被释放了又如何呢，难道增加一个元素在 free list 中么？显然不能，因为这时三个元素对应的区块大小都是 10，如果程序请求 20 bytes 岂不是返回失败，但实际上 heap 空闲大小是 30，因此分配器通常会通过 coalescing 机制合并 free list 里的空闲块，原理就是当某块区间被释放时，检查下区间前后是不是可以合并。
Tracking The Size Of Allocated Regions
分配器如何记录被分配的区块大小呢，让用户可以在 free 时仅需要传递起始地址就好。答案是在分配区块的头部增加一小部分，记录区间的大小和 magic num 用来校验。
上图的例子中 ptr 是返回给用户的空闲区块的起始地址，而这块地址向前还有一个 hptr 指向记录区块信息的起始地址。因此分配器真正分配空间时，并不是程序请求 N 就分配 N，而是还会多分配一块给头部指针进行信息记录使用。
Basic Strategies
叙述一些简单的分配器分配策略
- best fit，遍历列表，找到满足条件的最小区块
- worst fit，遍历列表，分配最大的区块
- first fit，遍历列表，分配第一个合适的区块
- next fit，维护上次分配过的区块，从它开始找下一个
除了这些简单的策略，还有一些进阶的：
Segregated Lists
思想就是某些应用会经常请求一些大小的空闲，为这些 popular 的请求单独维护 free list，就存放固定大小，而其他偶尔的请求用一个通用 free list 维护。
Buddy Allocation
这种策略主要关注 coalescing，空闲大小要是 2 的 N 次方，然后通过组织树形结构，在释放内存时可以方便地检查邻近的节点是否也是空闲的，从而一层层向上合并
若有收获，就点个赞吧
0 人点赞
