《深入理解计算机系统》Dynamic Memory Allocation-Basic Concepts

calloc：malloc后，内存清零。

realloc：alloc后，改变分配的大小。

sbrk：内存分配内部使用，用来增长和缩小堆

 碎片：

内部碎片：

外部碎片：

需要分配N字节内存时，内存中空间足够，但是没有N字节的块可供分配

内存分配需要考虑的问题：

1. 如何知道free的指针，包含多大的空间；

2. 如何组织空闲块

3. 分配一个小块内存时，如何处理原本这个空闲块的剩余部分；

4. 如何在许多空闲块中选择一个用来分配内存；

5. 如何合并释放的块

问题1解法：

在每次释放内存时，多申请一小块，在该字节上写分配了多少空间

问题2解法：

使用空闲链表；使用多个空闲链表，每个链表包含大小在一定范围内的空闲块；使用红黑树等结构，形成已排序的空闲块。

ps：这里传递一个思想，如果有无限多种类大小的空闲块，则可以满足任意的内存分配需求，理论上就不会有内存碎片；实际上，如果实现上越靠近这点，内存碎片就越少。

简单的堆块的格式：

每个内存块，必须是8byte（32位cpu）或16byte（64位cpu）的整数倍

最低的几位，代表当前块是否被分配；假设分配的最小单元是16byte，则最后4bit代表当前块是否被分配；前面的块代表大小；当需要获取当前块大小时，直接将最后4bit屏蔽为0，然后读取第一个16byte即可。精妙！！！！

问题4解决：

方法1：遍历所有空闲块，找到第一个符合条件的，分配；---会导致大量的内存碎片；

方法2：找到最适合分配的空闲块；---消耗太大；

问题3解决：

方法1：直接把一大块内存返回给应用程序；

方法2：分配应用程序想要的大小，剩下的形成一个新的空闲块；

所有分配器的一大特征：

永远不会有相连的两个空闲块,一个空闲块后面，跟着的一定是已分配的块。

因此，在释放内存时，需要检查前后的块，是否空闲，如果空闲，需要合并。

因此，内存分配块中增加了如下结构（为了快速找到前一块和后一块的位置）：

内存释放的四种情况：

可以在调用free时，就进行空闲块的合并，也可以，周期性扫描空闲块，进行合并。

对方案的优化：

1. 只有空闲块才需要footer，已分配的块因为不涉及合并，因此不需要footer；

2. 如果已分配的块没有footer，如何确定前一块有没有被分配：

header中最后3或4位代表该块是否是被分配，可以拿出一个bit，来表示前一个块是否被分配。因为，两个块一定是相连的，上一个块的结束和后一个块的header相连，分配时，可以手动改后一个块的header的那一位，来指示后面的块在释放时是否需要与前一个内存块合并。