二、存储的动态分配和回收

动态分配就是要在可利用空间表中找到一个合适的空闲块以满足存储请求。即为了分配一个N字节大小的空间，就要利用某种策略从可利用空间表中搜索到一个长度大于等于N字节的空闲块进行分配；如果可利用空间表中不存在这样的结点，就不能进行分配。
    为避免可利用空间表中空闲块长度固定所带来的存储共享问题，可以把各种不同长度的空闲块组织在一个可利用空间表中。这样在分配时并不是可利用空间表中的任一结点都能满足，而需要按照申请的长度在可利用空间表中进行检索，找到其长度大于等于申请长度的结点，从中截取合适的长度。常用的分配方法是顺序适配，包括：首先适配、最佳适配和最差适配。
    首先适配从可利用空间表的表头开始，顺次在可利用空间表这进行搜索，一旦找到第一个长度大于等于请求块长度的空闲块，就进行分配。其优点是速度快，缺点是可能把较大块拆分成较小的块，导致后来对大块的申请难以满足。
    最佳适配在所有长度大于等于请求块长度的空闲块中找出最小的一块进行分配。其优点是使无法满足大请求块的可能性降到最低，但可能导致严重的外部碎片问题。
    最差适配则采用与最佳适配相反的策略，在所有长度大于等于请求块长度的空闲块中找出最大的一块进行分配。 最差适配方法将使得空闲块长度趋于一致，适合于存储分配长度请求比较均匀的情况。
    顺序适配方法的缺点是易产生碎片问题，也即在系统长期动态运行的过程中可能使整个空间被分割成许多大小不等的碎块，而某些碎块由于太小而长期得不到使用。
    为解决碎片问题，存储回收时需要考虑与相邻空闲块的合并，以形成大的空闲块来满足将来尽可能大的存储要求。
    利用链表方式进行存储管理不可避免的问题是用于保存链表和块本身的信息所产生的额外开销。
    例：假设可利用空间表中包含3个可利用块，其大小分别是1200，1000和3000，现有如下一串存储分配的请求：600，500，900，2200。下图显示了分别采用最佳适配法和首先适配法时，空闲块的变化情况。采用最差适配策略的情况请同学们自己画出。在这个例子里，首先适配策略比最佳适配策略更好。当然，也可以找出反例。