tls现代的应用程序都运行在一个内存空间里，在32位的系统里(4)

Q：malloc申请的空间是不是连续的？

A: 在分析这个问题之前，我们首先要分清楚“空间”这个词所指的意思。如果“空间”是指虚拟空间的话，那么答案是连续的，即每一次malloc分配后返回的空 间都可以看做是一块连续的地址；如果空间是指“物理空间”的话，则答案是不一定连续，因为一块连续的虚拟地址空间有可能是若干个不连续的物理页拼接凑成 的。

1.3.3 堆分配算法

前面已经介绍了堆在进程中的地址空间是如何分布的，对于程序来说，堆空间只是程序向操作系统申请划分出来的一大块地址空间（通过brk和mmap申请）。 而程序在通过malloc在堆空间申请内存时的大小却是不一定的，从数个字节到数个GB都是有可能的。于是我们必须将堆空间管理起来，将它分块地按照用户 要求出售给最终的程序，并且还可以按照一定的方式收回内存。其实这个问题可以归结为：如何管理一大块连续的内存空间，能够按照要求分配、释放其中的空间， 这就是堆分配的算法。

1）空闲链表

空闲链表的方法实际上是把堆上各个空闲的块按照链表的方式链接起来，当用户调用malloc请求一块空间时，可以遍历整个列表，直到找到合适的小的块并且将它拆分；当用户释放空间时将它合并到空闲链表中。

首先需要一个数据结构来登记堆空间里所有的空闲空间，这样才能知道程序请求空间的时候分配给它哪一块内存。

空闲链表就是在堆里的每一个空闲空间的开头（或结尾）有一个头（header），头结构里记录了上一个（prev）和下一个（next）空闲块的地址，也就是说，所有的空闲块形成了一个链表。如果所示：

在这样的结构如何分配空间呢？

首先在空闲链表里查找足够 容纳请求大小的一个空闲块，然后将这个块分为两部分，一部分为程序请求的空间，另一部分为剩下来的空闲空间，然后原来空闲空间的结构更新为新的剩下的空闲 块，如果剩下的空间为0，则直接将这个结构从链表中删除。下图演示了用户请求一块和空闲块2恰好相等的内存空间后堆的状态。

这样的空闲链表实现尽管简 单，但在释放空间的时候，给定一个已分配块的指针，堆无法确定这个块的大小。一个简单的解决方法是当用户请求k个字节空间的时候，我们实际分配k+4个字 节，这4个字节用于存储该分配的大小，即k+4.这样释放该内存的时候只要看看这4个字节的值，就能知道该内存块的大小，然后将其插入到空闲链表里就可以 了。

当然这仅仅是最简单的一种分配策略，这样的思路存在很多问题。例如，一旦链表被破坏，或者记录长度的那4字节被破坏，整个堆就无法正常工作，而这些数据恰恰很容易被越界读写接触到。

2 位图

针对空闲链表的弊端，另一 种分配方式显得更为稳健。这种方式称为位图，其核心思想是将整个堆划分为大量的块，每个块的大小相同。当用户请求内存的时候，总是分配整数个块的空间给用 户，第一个块我们称为已分配区域的头（Head），其余的称为已分配区域的主体（Body）。而我们可以使用一个整数数组来记录块的使用情况，由于每个块 只有头/主体/空闲三种状态，因此仅仅需要两位即可表示一个块，因此称为位图。

例如：

这样的实现有几个优点：

1）速度快：由于整个堆的空闲信息存储在一个数组内，因此访问该数组时cache容易命中。

2）稳定性好：为了避免用户越界读写破坏数据，我们只需简单地备份一个位图即可。而且即使部分数据被破坏，也不会导致整个堆无法工作。

3）块不需要额外信息，易于管理。

当然缺点也是显而易见的：

1）分配内存的时候容易产生碎片

2）如果堆很大，或者设定的块很小（可以减少内部碎片），那么位图将会很大，可能失去cache命中率高的优势，而且也会浪费一定的空间。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-76057-4.html