操作系统：可变分区管理

1. 有作业序列：作业A要求42K；作业B要求27K，作业C要求22K，作业和空闲内存区如下图所示，请画出最佳适应算法空闲队列图，并分析最佳适应算法是否适合该作业系列。

答：最佳适应算法是按照空闲块由小到大的顺序排序的，其空闲块队列图如下图所示：

最佳适应算法对该作业系列适应性分析如下：

步骤1，作业A请求分配内存42K，遍历最佳适应算法空闲队列，作业A将从首地址210的内存块45K中分得42K内存（假设从空闲块尾部分割），剩余首地址210的3K空闲内存（210，3）将作为新的空闲块在最佳适应算法空闲队列中重新排序并得到如下排序序列｛（210，3），（160，9），（110，24），（31，33）｝。

步骤2，作业B请求分配内存27K，遍历分配完作业A之后的最佳适应算法空闲队列｛（210，3），（160，9），（110，24），（31，33）｝，作业B将从首地址31的内存块33K中分得27K内存（假设从空闲块尾部分割），剩余首地址31的6K空闲内存（31，6）将作为新的空闲块在最佳适应算法空闲队列中重新排序并得到如下排序序列｛（210，3），（31，6），（160，9），（110，24）｝。

步骤3，作业C请求分配内存22K，遍历分配完作业AB之后的最佳适应算法空闲队列｛（210，3），（31，6），（160，9），（110，24）｝，作业C将从首地址110的内存块24K中分得22K内存（假设从空闲块尾部分割），剩余首地址110的2K空闲内存（110，2）将作为新的空闲块在最佳适应算法空闲队列中重新排序并得到如下排序序列｛（110，2）,（210，3），（31，6），（160，9）｝。

至此，作业ABC按照最佳适应算法均获得了所需要的内存分配，因此，最佳适应算法适合作业系列ABC的内存分配请求。

2.动态分区存储管理算法。某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲)，采用首次适配(FirstFit)算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分区的大小是多少？请解释首次适应算法，用图形分析上述情况的内存分配过程。

答：此时内存空间中最大的空闲分区大小是10M。

首次适应算法是按内存物理地址由小到大排序，每一个作业进来，都从低地址开始查找大于或等于作业大小的空闲块，如果满足条件，则分配，否则不分配。

其内存空间的分配过程如下所示：

经过以上分配与释放过程，此时内存空间中最大的空闲分区大小是10M。

3.动态分区存储管理算法。某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲)，采用最佳适配(BestFit)算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分区的大小是多少？请解释最佳适应算法，用图形分析上述情况的内存分配过程。

答：此时内存空间中最大的空闲分区大小是9M。

最佳适应算法要求空闲分区按容量大小递增的次序排列。当用户作业申请一个空闲区时，存储管理程序从空闲分区表(链)首开始顺序查找，当找到第一个满足要求的空闲区时，停止查找。

其内存空间的分配过程如下所示：

经过以上分配与释放过程，此时内存空间中最大的空闲分区大小是9M。

4.采用可变分区方式管理主存空间时，若主存中按地址顺序依次有5个大小分别为15KB、28KB、10KB、226KB和110KB的空闲区。现在有5个作业JA、JB、JC、JD和JE，它们所需的主存依次为10KB、15KB、102KB、26KB和180KB。请问：

（1）如果采用首次适应算法能把这5个作业按JA~JE的次序全部装入主存吗？

（2）用什么分配算法装入这5个作业可使主存的利用率最高？

（1）不能。

对于首次适应算法，即按照存储地址从小到大的顺序分配内存。

装入JA后内存空闲区变为：5KB、28KB、10KB、226KB和110KB

装入JB后内存空闲区变为：5KB、13KB、10KB、226KB和110KB

装入JC后内存空闲区变为：5KB、13KB、10KB、124KB和110KB

装入JD后内存空闲区变为：5KB、13KB、10KB、98KB和110KB

因为JE需要180KB的内存区，所以不能满足

（2）用最佳适应算法，即按照空闲块由大到小动态排序的顺序分配内存。能使主存的利用率最高，此时五个内存块依次装入五个作业为：JA（10KB）、JB（15KB）、JC（110KB）、JD（28KB）、JE（110KB）

5.有作业序列：作业A要求18KB，作业B要求25KB，作业C要求30KB，初始内存分配情况如下图所示，问首次适应算法、最佳适应算法和最坏适应算法中哪些能够满足该作业序列的分配？并写出判断过程。

1. 对于首次适应算法，即按照存储地址从小到大的顺序分配内存。作业A分配30KB的空闲分区，作业B分配45KB的空闲分区，此时无法为作业C分配合适的空闲分区了。
2. 对于最佳适应算法，即按照空闲块由小到大动态排序的顺序分配内存。作业A分配20KB的空闲分区，作业B分配30KB的空闲分区，作业C分配45KB的空闲分区。
3. 对于最坏适应算法，即按照空闲块由大到小动态排序的顺序分配内存。作业A分配45KB的空闲分区，作业B分配30KB的空闲分区，作业C无法分配到合适的空闲分区。

因此，最佳适应算法能够满足该作业序列的需求。