动态分区分配计算

动态分区分配

内存连续分配管理分为：

• 单一连续分配
• 固定分区分配
• 动态分区分配（本篇所讲）

首次适应算法（First Fit，FF）

该算法又称最先适应算法，要求空闲分区按照首地址递增的顺序排列。

优点：优先使用低地址部分空闲分区，保留了高地址部分的大量空闲分区，有利于大程序或作业的装入。
缺点：内存的低地址区留下了许多难以利用的很小空闲分区，即内存“碎片”；算法每次都从低地址部分开始查找，这增加了查找可用空闲分区的开销。

注：外碎片是指由于空闲空间太小，以致于无法分配给程序或作业的内存空闲区域，如动态分区分配中存在外碎片； 内碎片是指已经被分配出去，却不能被充分利用的内存空间区域，如固定分区分配中存在内碎片。

循环首次适应算法（Next Fit，NF）

空闲分区按照首地址递增的顺序排列。每次内存分配时，不再从表头（或链首）开始查找，而是从上次分配的空闲分区的下一个空闲分区开始顺序查找。

优点：内存的空闲分区分布较均匀，减少查找空闲分区的开销。
缺点：经多次分配后，内存缺少较大的空闲分区，以分配给较大的程序或作业。

最佳适应算法（Best Fit，BF）

或称最优适应算法，该算法要求将空闲分区按从小到大的顺序排列。

优点：较大的空闲分区被尽量的保留下来，有利于大程序或作业的分配。
缺点：容易产生内存碎片；每次分配后需要更新空闲分区表（链），增加了系统开销；分割后小的空闲分区处于分区表（链）首，增加了查找空闲分区的时间。

最坏适应算法（Worst Fit，WF）

又称最差适应算法，该算法空闲分区按从大到小的顺序排列的。

优点：不会产生过多的碎片，有利于中、小程序或作业，且查找效率高。
缺点：影响大程序或作业的分配。此外，每次分配后需要更新空闲分区表（链），增加了系统开销。

四种算法比较

从搜索速度上看，FF具有最佳性能。

首次适应算法具有最佳性能；空间利用方面，首次适应算法比最佳适应算法好，最坏适应算法最差。

最佳适应算法找到的空闲分区是最佳的，但内存利用率不一定最优；

首次适应算法尽可能利用低地址空间，保证了高地址有较大空闲分区，以分配给较大的程序或作业；

最坏适应算法总是分割大的空闲分区，这有利于中、小程序或作业，但不利于较大的程序或作业。在实际系统中，首次适应算法使用较广泛。

例题

1.在可变分区存储管理下，按地址排列的内存空闲区为：10KB、4KB、20KB、18KB、7KB、9KB、12KB 和 15KB。对于下列连续存储区的请求：12KB、10KB、15KB、18KB，试问：使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法，哪个空闲区将被使用？

首次适应算法：

循环首次适应算法：

最佳适应算法：

最坏适应算法：

2.某操作系统采用可变分区分配存储管理方法，用户区为512K且始址为0。若分配采用分配空闲区低地址部分的方案，对下述申请序列:
申请310K，申请100K，释放310K，申请150K，申请40K，申请30K。
分别采用首次适应算法、最佳适应算法，回答下列问题:
(1)给出每一步的已分配空间、空闲分区(给出始址，大小)?
(2)若再申请120K，还能分配这120K存储空间吗?