一、首次适应算法(First Fit)

• 算法思想
  • 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
  • 空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
• 优缺
  • 保留了高地址空间，为大作业分配创造了条件。
  • 低地址不断被划分，留下了大量的外部碎片
  • 每次不必修改整张表

二、(循环)邻近适应算法(Next Fit)

• 算法思想

  • 首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销
  • 如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
  • 设置寻址指针，空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
  

• 优缺

  • 使内存中的空闲分区发布更加均匀，减少了查找开销
  • 缺乏大的空闲分区
  • 每次不必修改整张表

三、最佳适应算法(Best Fit)

• 算法思想
  • 为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
  • 空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
• 优缺
  • 避免了“大材小用”
  • 每次留下的难以利用的空间是最小的，产生了大量的外部碎片。

四、最坏适应算法(Worse Fit)

• 算法思想
  • 为了解决最佳适应算法的问题--留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
  • 空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
• 优缺
  • 可使剩余的空闲区不至于太小，产生碎片的可能性最小;对中、小作业有利；查找效率高，每次只需看第一个分区是否满足。
  • 对大作业不利，大空间很快被用光