[OS]Three Easy Pieces Chapter 17

Free-Space Management

对于页式内存来说，空闲页管理很简单，只需要用链表来管理空闲页即可；但是对于像段式内存这种空闲内存单元大小不固定的方式来说，空闲内存管理变得更复杂。对于后者，最大的挑战是外部碎片问题。

1 Low-level Mechanisms

Splitting and Coalescing

管理空闲内存空间的数据结构在需要时需要进行相应的拆分或者合并。

Tracking The Size Of Allocated Regions

像 free(void *ptr) 这样的接口无需大小参数。因此，给定一个指针，应该可以快速确定需要释放的内存的大小。

为此，很多实现会在内存中存储一个header，在header中存储一些额外的信息。

Embedding A Free List

将管理空闲内存的链表结点存储在空闲内存中。

当申请了一些内存后

当申请了一些内存，并释放了一些内存后。可以注意到，此时所有的空闲空间没有被合并，我们可以遍历一遍链表，将相邻的空间合并。

2 Basic Strategies

Best Fit

从最小的可行的空闲内存中分配。

Worst Fit

从最大的可行的空闲内存中分配。

First Fit

从第一个可行的空闲内存中分配。

一般将空闲内存按照地址排序。

Next Fit

类似First fit，但是每次从上一次分配的下一个可行的空闲内存中分配。

3 Other Approaches

Segregated Lists、Buddy Allocation等。