项目事故和安全语言

举个例子，程序刚开始运行的时候，连续五次向Heap申请内存，每次1k，然后释放了第二个，第四个，然后再申请4k内存，这4k内存不是连续的，而是分成了三片，在原来的第二块，第四块和第五块后面。这样在这4k里面读写数据就会在内存里跳来跳去，影响性能。

char * p = ( char * ) malloc( 8092 );
for( int i = 0; i < 8092; i++ ) {
  *p = 'a';
  printf( "%p\n", p++ );
}

在 c/c++ 的内存分配中，内存分配一定是连续的。

char * p = ( char * ) malloc( 8092 );
for( int i = 0; i < 8092; i++ ) {
  *p = 'a';
  printf( "%p\n", p++ );
}

无论如何，上面的代码输出的地址总应该是连续的。而且这些输出的地址就应该是这次 malloc 分配的结果。malloc 分配的内存是连续的，这是 c/c++ 依赖的一个基本假设。上面的这段代码在 c/c++ 中是非常常见的。

上面写的这一段代码中用户进程操作的内存地址都是虚拟地址，操作系统会把这些虚拟地址映射到物理地址上（需要CPU的协作）。操作系统为了简化用户程序员的工作量，作了大量的工作，隐藏了很多细节，虚拟内存是连续的，未必物理内存也是连续的。

经典的内存分配过程是这样进行的：
1. 内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
2. 运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内（即T时刻开始，T+P时刻结束），这M个被占用的内存单元不能再被其他进程使用。
3、假设在T时刻有一个进程申请M个单元，且运行时间为P，则：
1. 若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
2. 如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为M的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。
现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

标准C库函数malloc()和free()可在任意的时间段中，为应用分配任意大小的内存块。随着内存块的使用和释放，在整个内存区域中，分配给堆栈的存储区将混杂着许多正在使用或已经释放的存储块，而未被使用的任何小块内存区将变得无法使用。例如，某个应用要求堆栈分配30字节，如果堆栈中只有20个长度为3字节的小存储块(总共为60字节)，那么堆栈仍然无法为该应用分配内存，因为所需的30字节必须是连续的。

　　内存分配程序浪费内存的基本方式有三种：即额外开销、内部碎片以及外部碎片（图 1）。
　　内存分配程序需要存储一些描述其分配状态的数据。这些存储的信息包括任何一个空闲内存块的位置、大小和所有权，以及其它内部状态详情。一般来说，一个运行时间分配程序存放这些额外信息最好的地方是它管理的内存。
　　内存分配程序需要遵循一些基本的内存分配规则。例如，所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址。内存分配程序把仅仅预定大小的内存块分配给客户，可能还有其它原因。当某个客户请求一个 43 字节的内存块时，它可能会获得 44字节、48字节 甚至更多的字节。由所需大小四舍五入而产生的多余空间就叫内部碎片。
　　外部碎片的产生是当已分配内存块之间出现未被使用的差额时，就会产生外部碎片。例如，一个应用程序分配三个连续的内存块，然后使中间的一个内存块空闲。内存分配程序可以重新使用中间内存块供将来进行分配，但不太可能分配的块正好与全部空闲内存一样大。倘若在运行期间，内存分配程序不改变其实现法与四舍五入策略，则额外开销和内部碎片在整个系统寿命期间保持不变。虽然额外开销和内部碎片会浪费内存，因此是不可取的，但外部碎片才是嵌入系统开发人员真正的敌人，造成系统失效的正是分配问题。

内存碎片和硬盘碎片原理差不多。

举个例子，程序刚开始运行的时候，连续五次向Heap申请内存，每次1k，然后释放了第二个，第四个，然后再申请4k内存，这4k内存不是连续的，而是分成了三片，在原来的第二块，第四块和第五块后面。这样在这4k里面读写数据就会在内存里跳来跳去，影响性能。

实际上，内存碎片并没有想象的那么厉害。内存管理技术的发展已经让碎片的几率大大下降。譬如linux的malloc和free采用的是DougLea的内存分配器。

关于这一点，对垃圾收集感兴趣的人一般都会读过几片相关的论文。Paul R. Wilson 有两篇论文专门研究这个问题。调查和讨论了几乎所有现在的所有内存分配策略。

早期很多人都认为内存碎片会是一个大问题，但是经过对很多现实程序内存管理行为的跟踪、统计和分析，近年来越来越形成共识的是，如果采用比较现代的分配器，实际上内存碎片是很少的。缩并式的垃圾收集算法也因为这一点显得越来越没有优势。

The memory fragmentation problem: solved?