第4章 存储管理 第4课时 可变分区存储管理《操作系统原理课件（第2版）》 同步教学（电子工业出版社）

操作系统原理(第2版） 4.3.3 可变分区存储管理 1. 实现原理 在程序装入内存之前并不建立分区，内存分区是在程序运行时根据程序对内存空间的需要而动态建立的。 分区的划分时间、大小及其位置都是动态的。 2. 数据结构 包括：已分配分区表、空闲分区表及空闲分区链。 已分配分区表用于登记内存空间中已经分配的分区，每个表项记录一个已分配分区，其内容包括分区号、起始地址、大小和状态。 空闲分区表则记录内存中所有空闲的分区，每个表项记录一个空闲分区，其内容包括分区号、起始地址、大小和状态。 空闲分区链以系统当前的空闲分区为结点，利用链指针将所有空闲分区结点链接成一个双向循环队列。 4.3 分区式存储管理 可变分区存储管理 已分配分区表 空闲分区表 分区号 起始地址 （KB） 大小（KB） 状态 分区号 起始地址（KB） 大小（KB） 状态 1 50 20 P1 1 70 20 0 2 90 15 P2 2 105 155 0 3 260 40 P3 3 300 100 0 … … … … … … … … 内存及空闲分区链示意 可变分区存储管理 3. 分配算法 （1）首次适应算法 要求空闲分区按内存地址递增的次序排列在空闲分区链上。每当一个程序申请装入内存时，管理程序从空闲分区链链首开始查找空闲分区（按内存地址递增的顺序查找），直到找到一个最先满足此程序需求的空闲分区，并按此程序的大小从该空闲分区中划出一块连续的内存区域给程序使用。而该分区剩余的部分，仍按地址递增的次序保留在空闲分区链中，但还需修改该空闲分区在空闲分区表中的起始地址和大小。若未能找到满足程序需求的空闲分区，则此次分配失败。 特点：每次都从内存的低地址部分开始查找满足要求的空闲分区。 首次适应算法中的空闲分区按地址递增排列，这使回收的内存区与相邻空闲分区的合并比较容易。 可变分区存储管理 （2）最佳适应算法 要求空闲分区按分区大小递增的次序排列在空闲分区链上。最佳适应算法在为用户程序分配内存空闲分区时，从空闲分区链链首的最小空闲分区开始查找，找到的第一个大小满足程序需求的空闲分区就是最佳空闲分区。该分区能满足程序的存储需求，并且在分配后剩余的空闲空间最小（因浪费最小故称为最佳）。剩余的小空闲分区仍按分区的大小插入空闲分区链上，同时修改该空闲分区在空闲分区表中的起始地址和大小。 优点：保留了内存中的大空闲区，当大程序到来时有足够大的空闲区可以为其分配。 在回收内存区时，为了将回收的内存区与相邻的空闲分区合并成一个空闲分区，可能要查遍整个空闲分区链。 可变分区存储管理 注意： 最佳适应算法的最佳仅仅是针对每次分配而言的。若从分配的整体情况来看，由于每次分配后所剩余的空闲空间总是最小，那么随着分配的不断进行，就会在内存留下越来越多无法再继续使用的小空闲分区。而且每次分配都是从空闲分区链链首的最小空闲分区开始查找，这必然增加了查找时间。此外在回收内存区时，首先考虑的是该回收内存区是否存在与之相邻的空闲分区，为了将回收的内存区与相邻的空闲分区合并成一个空闲分区，可能要查遍整个空闲分区链，因为空闲分区是按大小排列而不是按地址排列的。 可变分区存储管理 （3）最差适应算法 要求空闲分区按分区大小递减的次序排列在空闲分区链上，每一次总是把空闲分区链链首的最大的空闲分区分配给请求的用户程序；若该空闲分区小于程序要求的大小则分配失败；若能够满足程序的要求，则按程序要求的大小从该空闲分区中划出一块连续区域分配给它。 优点：总是选择内存中最大的空闲分区进行分配，因此分配后所剩余的部分也相对较大，这有利于以后再分配给其他程序使用。 在回收内存区时，为了将回收的内存区与相邻的空闲分区合并成一个空闲分区，可能要查遍整个空闲分区链，因为空闲分区是按大小排列而不是按地址排列的。 可变分区存储管理 例4.1 有一程序序列：程序A要求18KB，程序B要求25KB，程序C要求30KB，初始内存分配情况如图所示（其中阴影为分配区）。问首次适应算法、最佳适应算法和最差适应算法中哪种能满足该程序序列的分配？ 可变分区存储管理 【解答】 结合系统中初始内存的 分配情况，建立的首次适应算法、 最佳适应算法和最差适应算法的 空闲区链分别如图： 对于首次适应算法，程序A分配 30KB的空闲分区，程序B分配46KB的 空闲分区，此后就无法为程序C分配 合适的空闲分区了。 对于最佳适应算法，程序A分配 20KB的空闲分区，程序B分配30KB的空闲分区，程序C分配46KB的空闲分区。 对于最差适应算法，程序A分配46KB的空闲分区，程序B分配30KB的空闲分区， 此后就