操作系统的空闲内存管理

动态分配内存时，操作系统必须对空闲内存进行管理。

1. 使用位图的存储管理

使用位图时，内存可能被划分为很多个分配单元，每个分配单元对应位图中的一位，0 表示空闲，1 表示占用。

使用位图时，关键问题在于分配单元大小的设计。

分配单元越小，越可以精细分配内存。但这也意味着位图越大，消耗的空间越大。

2. 使用链表的存储管理

使用链表时，链表中的一个节点包括一个进程或者两个进程间的一块空闲区域。

如上图，链表中每个节点都包含以下域：

• 空闲区 H 或进程 P 的指示标志
• 起始地址
• 长度
• 指向下一节点的指针

段链表可以使用双向链表，在设计时显然会更加方便。

有几种算法可以为创建的线程分配内存：

• 首次适配算法：沿着链表搜索，使用第一个足够大的空闲区，每次都重头开始。
• 下次适配算法：沿着链表搜索，使用第一个足够大的空闲区，每次都从上一次结束的位置开始。
• 最佳适配算法：搜索整个链表，找到大小最合适的空闲区。
• 快速适配算法：为常用大小的空闲区维护单独的链表。例如有一个 n 项的表，第一项指向大小为 4KB 的空闲区链表表头的指针，第二项为指向大小为 8KB 的空闲区链表表头的指针，以此类推。