动态分区分配算法

这是一篇关于动态分区分配算法的思维导图，主要内容包括：首次适应算法，最佳适应算法，最坏适应算法，临近适应算法。

动态分区分配算法

• 首次适应算法
  • 思想
    • 每次都从低地址开始查找
    • 找到第一个满足大小的空闲分区。
  • 排列
    • 空闲分区以地址递增次序排列
  • 优点
    • 性能最好
    • 算法开销小
    • 回收分区后一般不需要对空闲分区队列重新排序
• 最佳适应算法
  • 思想
    • 为了保证大进程到来时能有连续的大片空间
    • 可以尽可能多地留下大片的空闲区
    • 优先使用更小的空闲区。
  • 顺序
    • 空间分区以容量递增次序排列
  • 优点
    • 会有更多的大分区被保留下来
      • 更能满足大进程需求
  • 缺点
    • 每次都选最小的分区进行分配
      • 会留下越来的内存块
        • 越多的
        • 很小的
        • 难以利用
        • 会产生很多的外部碎片
• 最坏适应算法
  • 思想
    • 每次分配时优先使用最大的连续空闲区
    • 这样分配后剩余的空闲区就不会太小
  • 排序
    • 空间分区以容量递减次序排列
  • 优点
    • 可以减少难以利用的小碎片
  • 缺点
    • 导致较大的连续空闲区被迅速用完
• 临近适应算法
  • 思想
    • 每次都从上次查找的位置开始检索
  • 排序
    • 空闲分区以地址递增次序排列
      • 可循环列成链表
  • 优点
    • 不用每次都从低地址的小分区开始检索
      • 算法的开销小
  • 缺点
    • 可能导致空闲分区都有相同的概率被使用
      • 无论
        • 低地址
        • 高地址
      • 也就导致了高地址高地址部分的大分区更可能被使用
        • 划分为小分区
        • 最后导致无大分区可用