四种常用的分区分配算法

 　　无论采用空闲分区表或空闲分区链记录内存使用情况，在为一个作业分配存储空间时都必须按照一定的分配算法。常用的分区分配算法有以下四种，小虫系统小编一一分别给大家介绍下。
 

　　(1)首次适应算法

　　首次适应算法把空闲区按地址从小到大排列在空闲分区表(链)中。每次分配时，总是从头顺序查找空闲分区表(链)，找到第一个能满足长度要求的空闲区为止。分割这个找到的空闲分区，一部分分配给作业，另一部分仍为空闲区。

　　这种分配算法优先利用主存低地址空闲分区，从而保留了高地址的大的空闲区，这为以后到达的大作业分配大的内存空间创造了条件。但由于低地址部分 不断被分割，势必造成低地址部分有较多难以使用的“碎片”，而每次查找又都从低地址部分开始，这就增加了查找可用空闲分区的开销。
 

　　(2)循环首次适应算法

　　循环首次适应算法每次分配时，总是从上次扫描结束处顺序查找空闲分区表(链)，找到第一个能满足长度要求的空闲区为止。分割这个找到的空闲分 区，一部分分配给作业，另一部分仍为空闲区。这一算法是最先适应分配算法的一个变种，能使得存储空间的利用率更加均衡，不会导致小的空闲区集中在存储器的 一端，但这会缺乏大的空闲分区。
 

　　(3)最佳适应算法

　　最佳适应算法要扫描整个空闲分区表(链)，从空闲区中挑选一个能满足作业要求的最小分区进行分配。这种算法可保证不去分割一个更大的区域，使装 入大作业时比较容易得到满足。采用这种分配算法时可把空闲区按长度以递增顺序排列，查找时总是从最小的一个区开始，直到找到一个满足要求的分区为止。按这 种方法，在冋收一个分区时也必须对空闲分区表或空闲分区链重新排列。最佳适应算法找出的分区如果正好满足要求则是最合适的了，但如果比所要求的略大则分割 后所剩下的空闲区就很小，以致无法使用。
 

　　(4)最坏适应算法

　　最坏适应算法要扫描整个空闲分区表(链)，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，对中、小作业有利， 但这会导致内存中缺乏大的空闲分区。采用这种分配算法时可把空闲区按长度以递减顺序排列，查找时只要看第一个分区能否满足作业要求即可，这样使最坏适应分 配算法查找效率很高。