Free-Space Management
使用segmentation实现虚拟内存时，我们可能会遇到上图所示情况，总共未使用的空间是20字节，但是被分成了2个10字节的内存段，如果有个15字节的程序请求CPU给它分配内存，CPU只能拒绝这个请求。这一章就是为了解决这个问题。
1. Low-level Mechanisms
void *malloc(size t size)
void free(void *ptr)
1.1 Splitting and Coalescing
该heap包含两个free list，一个地址从0到9长度为10字节，一个地址从20到29长度为10字节。如下所示：
如上图所示，当大于10字节的程序请求CPU分配内存地址时，CPU拒绝这个请求。
假如一个小于10字节的程序请求CPU分配内存地址呢？
不妨假设1个字节的程序请求CPU分配内存地址并且CPU决定使用第二个空闲的内存segmentation。
则free list如下所示：
又如果我们为了返回中间的地址空间而使用free(10)呢？如果我们没有过多的考虑就只是简单地将这个segmentation加入到free list中，那么如下所示：
注意上面的图，整个地址空间都是空闲的，但是被分成了3个10字节的segmentaion，如果大于10字节的程序请求CPU给其分配内存地址，CPU还是会拒绝这个请求。
所以我们需要做的就是把连续的空闲的内存空间合并，如下所示：
1.2 Tracking The Size Of Allocated Regions
你可能已经注意到了free(void *ptr)，这个函数的参数没有给出一个大小参数而是一个指针，malloc库可以很迅速地决定多少内存大小的区域被释放进而被合并到free list中。
为了完成这个任务，allocators添加了额外的信息已经分配好的malloc库的header块中。可以看下图：
上图中ptr指向已经分配好的20字节的内存块，ptr = malloc(20)。
header至少包含分配区域的大小，它还包含其他指针以加快内存释放速度，和一个神奇数字提供其他完整性检查。代码如下：
typedef struct {
int size;
int magic;
} header_t;
图如下所示：
当用户调用free(ptr)，库使用简单的指针算法确认需要释放的内存地址：
void free(void *ptr) {
header_t *hptr = (header_t *) ptr - 1;
...
获得对应的地址后，库会检测神奇的数字(magic)是否匹配assert(hptr->magic == 1234567)，然后计算需要释放的内存大小(size的大小)。
1.3 Embedding A Free List
到目前为止，我们都是描述heap中的free list （external fragmentation），我们如何描述每个heap中的segmentation中的free list （internal fragmentation）呢？
假设我们要管理一个4096字节的内存块，为了将其看作一个free list，我们首先需要对其初始化，代码如下：
typedef struct __node_t {
int size;
struct __node_t *next;
} node_t;
我们假设堆是内置在通过调用系统调用mmap（）获得的一些空闲空间中，代码如下：
// mmap() returns a pointer to a chunk of free space
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;
运行此代码后，list的head指向地址4088。然后我们假设该范围的起始地址为16KB，如下图所示：
现在，让我们假设请求的块为100字节。为了满足这个请求，库需要查找空余内存块，由于只有一个空余内存块（4088字节），故选中此块。为了满足100字节进程的请求，库分配108字节。8字节包含size和magic，100字节满足该进程的需求。
如果有3个100字节的进程发出该请求，那么如下图所示：
head指向地址3764（在3个分段之后），如果现在调用free()会发生什么呢？
应用程序返回中间块通过调用free(16500)，值16500由存储区的开始地址16KB（16384）加上第一个108字节的分段和中间段的头8字节，最后结果由上图sptr指向表示。库立即就能根据头8个字节中的size释放相应大小的内存空间，然后把释放的内存空间加入到free list中。如下图所示：
跟着灰色箭头：从head指针开始看，然后head->next
把另外两个进程也释放后如下图所示：
对于上图，很混乱有木有？因为我们还没有将其合并，尽管整个都是空余内存，但是被分成了几个段。解决这种情况的方法就是：遍历free list，然后把相邻的空余内存合并，这样就变成了一个整体。
1.4 Growing The Heap
heap分配的整个内存地址空间不是无限大的，总有用完的时候，如果heap分配的内存用尽了，我们应该怎么办呢？最简单的办法就是当heap内存空间用完后，新的进程发出请求的时候，直接拒绝就行了。当然这也是一种方法，但是有一种更好的办法就是刚开始分配的heap非常小，当越来越多的进程发出内存请求后，heap也会相应的增加内容空间大小。
2. Basic Strategies
接下来让我们了解一下管理空余地址内存的基本策略。
2.1 Best Fit
遍历free list，在free list中找到内存空间不小于新来的进程请求的内存空间大小的块，然后返回候选的最小的那个可用内存块。
2.2 Worst Fit
遍历free list，在free list中找到内存空间不小于新来的进程请求的内存空间大小的块，然后返回候选的最大的那个可用内存块。
2.3 First Fit
不需要遍历free list，找到第一个内存空间不小于新来的进程请求的内存空间大小的块就可以直接使用。
2.4 Next Fit
不会总是在列表的开头开始首次搜索，而是会保留一个额外的指针，以指向列表中最后查找的位置。 这样做的想法是将对可用空间的搜索更加均匀地分布在整个列表中，从而避免分散列表的开头。 这种方法的性能与First Fit非常相似，因为再次避免了详尽的搜索。
3. Other Approaches
Segregated Lists
Buddy Allocation
etc
4. Homework (Simulation)
The program, malloc.py, lets you explore the behavior of a simple
free-space allocator as described in the chapter. See the README for
details of its basic operation.
Question & Answer
1. 
2. 
3. 
4. 
5. 
6. 
7. 
改变选项的事就自己慢慢做啦~