空闲内存管理目录
前言
在动态分配内存时，操作系统有两种方法跟踪内存使用情况:位图和空闲区链表。
一、使用位图的存储管理
使用位图方法时，内存可能被划分成小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位，0表示空闲，1表示占用(或者相反)。一块内存区和其对应的位图如图所示：
- a)一段有5个进程和3个空闲区的内存，刻度表示内存分配单元，阴影区域表示空闲（在位图中用0表示);
- b)对应的位图;
- c)用空闲区链表表示的同样的信息
分配单元的大小是一个重要的设计因素。分配单元越小，位图越大。然而即使只有4个字节大小的分配单元，32位的内存也只需要位图中的1位。32n位的内存需要n位的位图，所以位图只占用了1/32的内存。若选择比较大的分配单元，则位图更小。但若进程的大小不是分配单元的整数倍，那么在最后一个分配单元中就会有一定数量的内存被浪费了。
因为内存的大小和分配单元的大小决定了位图的大小，所以它提供了一种简单的利用一块固定大小的内存区就能对内存使用情况进行记录的方法。
这种方法的主要问题是:
在决定把一个占k个分配单元的进程调入内存时，存储管理器必须搜索位图，在位图中找出有k个连续0的串。查找位图中指定长度的连续0串是耗时的操作(因为在位图中该串可能跨越字的边界)，这是位图的缺点。
二、使用链表的存储管理
另一种记录内存使用情况的方法是，维护一个记录已分配内存段和空闲内存段的链表。其中链表中的一个结点或者包含一个进程，或者是两个进程间的一块空闲区。可用上图c段链表来表示上图a所示的内存布局。
链表中的每一个结点都包含以下域:
空闲区(H)或进程(P）的指示标志、起始地址、长度和指向下一结点的指针。
在本例中，段链表是按照地址排序的,其好处是当进程终止或被换出时链表的更新非常直接。一个要终止的进程一般有两个邻居(除非它是在内存的最底端或最顶端)，它们可能是进程也可能是空闲区,这就导致了下图所示的四种组合。在图a中更新链表需要把P替换为H;在图b和图c中两个结点被合并为一个，链表少了一个结点:在图d中三个结点被合并为一个，从链表中删除了两个结点。
进程表中表示终止进程的结点中通常含有指向对应于其段链表结点的指针，因此段链表使用双向链表可能要比上上图c所示的单向链表更方便。这样的结构更易于找到上一个结点，并检查是否可以合并。
当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以用来为创建的进程（或从磁盘换入的已存在的进程)分配内存。假设存储管理器知道要为进程分配多少内存。
1.首次适配算法
首次适配(first fit)算法是最简单的算法。存储管理器沿着段链表进行搜索，直到找到一个足够大的空闲区，除非空闲区大小和要分配的空间大小正好一样，否则将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。首次适配算法是一种速度很快的算法，因为它尽可能少地搜索链表结点。
2.下次适配算法
对首次适配算法进行很小的修改就可以得到下次适配(next fit)算法。它的工作方式和首次适配算法相同，不同点是每次找到合适的空闲区时都记录当时的位置，以便在下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次适配算法那样每次都从头开始。
3.最佳适配算法
另一个著名的并广泛应用的算法是最佳适配(best fit)算法。最佳适配算法搜索整个链表(从开始到结束)，找出能够容纳进程的最小的空闲区。最佳适配算法试图找出最接近实际需要的空闲区，以最好地匹配请求和可用空闲区，而不是先拆分一个以后可能会用到的大的空闲区。但是！生活总是那么不尽人意！它比首次适配算法或下次适配算法浪费更多的内存，因为它会产生大量无用的小空闲区。一般情况下，首次适配算法生成的空闲区更大一些。
4.最差适配算法
最佳适配的空闲区会分裂出很多非常小的空闲区，为了避免这一问题，可以考虑最差适配(worst fit)算法，即总是分配最大的可用空闲区，使新的空闲区比较大从而可以继续使用。但是！这也不是一个好主意！
5.快速适配算法
另一种分配算法称为快速适配(quick fit)算法，它为那些常用大小的空闲区维护单独的链表。例如,有一个n项的表，该表的第一项是指向大小为4KB的空闲区链表表头的指针，第二项是指向大小为8KB的空闲区链表表头的指针，第三项是指向大小为12KB的空闲区链表表头的指针，以此类推。像21KB这样的空闲区既可以放在20KB的链表中，也可以放在一个专门存放大小比较特别的空闲区的链表中。
快速适配算法寻找一个指定大小的空闲区是十分快速的，但它和所有将空闲区按大小排序的方案一样，都有一个共同的缺点，即在一个进程终止或被换出时，寻找它的相邻块并查看是否可以合并的过程是非常费时的。如果不进行合并，内存将会很快分裂出大量的进程无法利用的小空闲区。
