内存分配与回收

无论什么进程，想要运行的就需要申请内存的空间，操作系统把我们的内存空间分割成化成一个个页表，现在的一般一个页表的大小是 4kb，而每个进程申请的空间都是以页为单位的。

比如我们写了一个 Java 应用程序，这时候这个程序可能被分成若干个段，代码段，数据段，堆栈段等。如果每个段需要内存比较大，每个段表又会申请多个页。这是在动态地址变化时采取的段页式存储管理方式，那么操作系统是如何对内存分配和回收的呢？

现在主体的内存分配方式有四种，分别为：位示图法、链式分配法、伙伴分配法和 cache(页缓存)分配内存。

位示图法

分配

这种方式分配内存采取的数据结构可以是二维数组。如下图所示，其中的每一块代表一个页。其中的数字为 1 代表这块内存被分配出去了。没有标识为 1 代表可以被分配。当我们需要一块 4 页大小的内存的时候，就会从头找是否标识为 1，是 1 跳过，不是 1 则看看后面在同一行是否可以找到连续的 4 块位置。否则去下一行遍历。

回收

我们在每个进程申请内存的时候都会有进程控制块。这个进程控制块(PCB)都会有指向这个内存的指针。当要回收内存的视乎就会给操作系统发信号，这时候操作系统就会记录下要结束进程指针所指向的地址，当进程结束的时候就会把内存回收。将对应的标识为清空位 0。其他几种回收内存的方式和这种相似，后面将不再赘述。

链式分配法

分配

上面的一个个查询过于繁琐，每次都要从开始位置向后面一个个遍历，而且也不能判断有空闲的页是否能分配给要申请的内存，这时候操作系统来利用链表这种数据结构来分配和回收内存，结构如下图。

其中第一位代表标识位，p(process) 代表被进程占用。F(free) 代表空闲。进程控制块中会有信息指向这个标记位。以便于回收内存。这第二位代表其实地址，第三位代表长度。最后一位代表指向下一个结点的指针。

第一个节点的信息就代表起始地址是 0 号的页，后面的连续四个页(包括 0 页)被进程占用。当需要申请内存的时候就从链表头部开始遍历，找到符合要求的地址，拆分这个结点的信息，分出来一部分地址。比如要申请一块三个页的内存，就把第二个节点拆成两个节点。其中分出来三个页给进程使用。

回收

当要回收内存的时候。就会把这个标识位清空，删掉这个结点。然后重新把两边连接起来。改变空闲区的长度和起始地址。

伙伴分配法

分配

我们知道内存是很大的，每个页的内存是 4k，而对于我们 4g 的计算机来说，上面那种链式的结构虽然有些改进，但是对于我们查询链表然后分配内存还是不够乐观。这时候出现了伙伴分配的方式。这时候的分配方式如下图。

我们以 16 个页为例子。加入我们想分配 4 个页，这时候这连续的 16 个页就会被分成 1 个 4 页，和一个 8 页。如下图：我们可以看到分配内存的时候总是从开始位置分配，而且如果分配的内存总是2的整数次方倍，你想分配 3 个页的内存，只会给你分配4个页大小的内存。这种查找效率是迅速的，先确定你需要多大的内存，通过下标直接定位到你要的内存，然后直接从后面分配内存，这层没有的话分裂下一层的内存。

回收

内存的回收时候除了回收之外还需要查看是否能合并内存，这时候需要右三个合并内存的条件：

1. 伙伴申请内存的大小相同假设都为 n 个页。

2. 物理块相连，只有挨在一起的才是伙伴。

3. 位置居前的页块的首地址是 2n 的倍数，这样才能确定他们是由同一块分割的。

cache(页缓存)分配内存

分配

我们知道计算机是有硬件的极限的，那就是利用 cpu 内部的告诉缓冲，我们比较常用的并且占用内存较少的进程可能只占用 64b 或者 128b 的空间，甚至不需要我们分配一个页大小的空间。这时候我们可以利用完全利用告诉缓冲区的较小且处理速度巨快的告诉缓冲区来分配内存。这样便达到了最好的效果。比如 linux 系统中的 slab 分配器就是基于这样的理念所制作的。

回收

回收的时候便按照一般的回收机制回收高速缓冲区的内存。

总结

我们分配内存的基本就是这样，这四种方式在生活中都会用到，当我们的计算机内存较小的时候不需要处理较大的内存时，可能采用前两种比较简单的方式，例如嵌入式操作系统。而要在服务器上时，对内存就需要后面两种管理的方式。还有最后需要注意的一点：我们在总线上传输的都是物理地址。

当内存分配好了之后我们需要把 EA (逻辑地址)变成 PA (物理地址)。这个功能是由硬件实现的。当操作系统计算出并分配好逻辑地址之后，由一种叫 MMU(虚拟存储管理单元)的硬件来实现地址的对应转化。对于现在的计算机来说，这个硬件现在一般都内嵌在 cpu 内部。所以这个内存转换的问题不是操作系统所需要考虑的。