连续存储空间管理–《计算机操作系统》

连续存储空间，是指为一个用户程序分配一个连续的内存空间。这种分配方式曾被广泛应用于20世纪60～70年代的OS中，它至今仍在内存分配方式中占有一席之地；最早出现的是单一连续分配方式，把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。这种方式只适用于单用户单任务操作系统，后期为支持多道程序并发执行，出现了分区分配管理方式，这种分配方式把用户区划分为若干个连续区域，每一个区域称为一个分区，每个分区可装入一个程序。根据分区划分方式的不同，分区分配方式又分为固定分区和可变分区分配两种管理方式。

5.2.1 固定分区管理方式

固定分区存储管理把内存中可分配的用户区域预先划分成若干个连续区，每一个连续区称为一个分区。一旦划分好后，内存中分区的个数就固定了。各个分区的大小可以相同，也可以不同，但每个分区的大小固定不变。在每个分区只装入一道作业，把用户空间分为几个分区，便允许有几道作业并发运行。图5-2是有三个分区的固定分区存储管理的示意图。当有一空闲分区时，便可以再从外存的后备作业队列中选择一个适当大小的作业装入该分区，当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。

1.划分分区的方法

固定分区分配虽然规定分区大小一经划分，不可更改，但并没有规定开始分区时不同分区的大小是否相等，可用下述两种方法将内存的用户空间划分为若干个固定大小的分区：

（1）分区等长。分区等长划分是指将内存划分为若干长度相等的分区。这种分区方式可简化相应的存储管理，但其缺点是缺乏灵活性，当程序太小时，会造成内存空间的浪费；当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。尽管如此，这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合，因为这些对象所需的内存空间是大小相等的。例如，炉温群控系统，就是利用一台计算机去控制多台相同的冶炼炉。

（2）分区不等长。分区不等长划分是将内存划分为若干长度不相等的分区，是为了克服分区大小相等而缺乏灵活性的这个缺点，其把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。这样，便可根据程序的大小为之分配适当的分区。

2.内存分配与回收

为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配），见表5-1所示。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。存储空间分配情况如图5-3所示。

表5-1 分区使用表

图5-3 存储空间分配情况

当一个作业运行完毕，系统回收内存资源，并修改分区使用表中对应分区的状态。

3.固定分区的缺点

由于每一个分区的大小是固定的，限制了可容纳程序的大小。在装入一个程序时，若找不到足够大的分区，则拒绝为该程序分配内存，这种分配方式的内存利用率仍然不够高，系统内存可容纳的进程数也受到一定的限制。

5.2.2 可变分区管理方式

可变分区存储管理不是预先把内存中的用户区域划成分区，而是在作业要求装入内存时，根据作业需要的内存空间大小和当时内存空间使用情况来决定是否为作业分配一个分区。因此分区的长度不是预先固定的，而是按作业的实际需求来划分的；分区的个数也不是预先确定的，而是由装入的作业数决定的。

在采用可变分区分配的操作系统中，可系统刚启动时，除了往操作系统区加载必要的系统程序外，其余空间为一个完整的大空闲区。当有程序需要装入时，则从该空闲区中分配一块大小与程序相同的区域，形成一个已分配区。随着系统的运行，不断地进行内存的分配与回收，原来的一整块大空闲区就形成了若干占用区和空闲区相间的布局。若有相邻的两块空闲区，系统可以将它们合并成一块连续的大空闲区。

可变分区分配根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这三个问题。

1.分区分配中的数据结构

为实现分区分配，系统必须配置相应的数据结构，用来描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式：

（1）空闲分区表。在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项，如表5-2所示。

表5-2 空闲分区表

图5-4 空闲链结构

（2）空闲分区链。为实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链，如图5-4所示。为了检索方便，在分区尾部重复设置状态位和分区大小表目。当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。

2.分区分配算法

为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。目前常用以下所述的五种分配算法。

1）首次适应算法（first fit）

以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。

2）循环首次适应算法（next fit）

该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。

3）最佳适应算法（best fit）

所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。

4）最坏适应算法（worst fit）

最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的概率最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。但是该算法的缺点也是明显的，它会使存储器中缺乏大的空闲分区。最坏适应算法与前面所述的首次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。

5）快速适应算法（quick fit）(www.xing528.com)

该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2 KB、4 KB、8 KB等，对于其他大小的分区，如7 KB这样的空闲区，既可以放在8 KB的链表中，也可以放在一个特殊的空闲区链表中。该算法的优点是查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。该算法的缺点是在分区归还主存时算法复杂，系统开销较大。此外，该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重，整体上会造成可观的存储空间浪费，这是典型的以空间换时间的做法。

图5-5 内存分配流程

3.分区分配操作

在动态分区存储管理方式中，主要的操作是分配内存和回收内存。

1）分配内存

系统利用某种分配算法，从空闲分区链（表）中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若m.size-u.size≤size（size是事先规定的不再切割的剩余分区的大小），说明多余部分太小，可不再切割，将整个分区分配给请求者；否则（即多余部分超过size），从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链（表）中。然后，将分配区的首址返回给调用者。图5-5示出了分配流程。

2）回收内存

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链（表）中找到相应的插入点，此时可能出现以下四种情况之一（黑色部分为空闲分区）：

①上邻空闲区，回收区与插入点的前一个空闲分区相邻接，见图5-6（a）。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区的大小。

②下邻空闲区，回收分区与插入点的后一空闲分区相邻接，见图5-6（b）。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。

③上下邻都是空闲区，回收区同时与插入点的上、下两个分区邻接，见图5-6（c）。此时将三个分区合并，使用上邻空闲区的首址，大小为上、下两个分区和回收区三者之和，删除下邻空闲区的表项。

④上下邻都不是空闲区，即回收区的上邻分区和下邻分区都不是空闲区，见图5-6（d），这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

图5-6 内存回收时的情况

5.2.3 覆盖与交换技术

1.覆盖

为了能让进程比它所分配到的内存空间大，可以使用覆盖（overlay）技术。覆盖的思想是在任何时候只在内存中保留所需的指令和数据。当需要其他指令时，将其装入到不再需要的指令所占用的内存空间。

例如，two-pass汇编程序，第一遍时，建立符号表；第二遍时，生成机器码。可将所占空间分成第一遍代码、第二遍代码、符号表及第一遍代码和第二遍代码的公共支持程序：

第一遍代码70 KB

第二遍代码80 KB

符号表20 KB

公共程序30 KB

若将所有代码一次性装入内存，要200 KB内存空间，若只有150 KB，则无法运行该进程。但该程序的第一遍代码和第二遍代码的运行时间不同，所以不必同时位于内存。可定义两个覆盖：覆盖A是符号表、公共程序和第一遍代码；覆盖B是符号表、公共程序和第二遍代码。需增加覆盖驱动程序（10 KB），并从内存中的覆盖A开始运行。当完成第一遍时，由覆盖驱动程序读入覆盖B，并重写覆盖A，接着转到第二遍。覆盖A需要120 KB，而覆盖B需要130 KB（图5-7），故可在150 KB的内存中执行该汇编程序。执行开始时需要装入的数据较少，装入较快，读入覆盖B替代A需要额外的I／O开销，运行稍慢。

覆盖A代码和覆盖B代码作为绝对内存映像存放在磁盘上，覆盖驱动程序根据需要分别将它们读入内存。为了构造覆盖，需要使用特殊的重定位和链接算法。

与动态加载一样，覆盖不需要操作系统提供特别支持。用户通过简单文件结构，将文件读入内存、转到内存，并执行所读指令就可以完全实现覆盖。

图5-7 一个two-pass汇编程序的覆盖

设计和编写覆盖结构需要完全了解程序结构、代码和数据结构。程序空间比较大时需使用覆盖，而小程序则无须使用覆盖，如何判别程序是否需要覆盖可能比较困难，因此，覆盖的使用通常局限于微处理机和只有有限物理内存且缺乏更先进硬件支持的系统。有的微处理机编译系统为程序员提供覆盖支持以简化编程，以在有限物理内存中运行较大程序。以交换回内存以继续执行。这种交换有时被称为滚出（roll out）、滚进（roll in）。

图5-8 使用磁盘作为备份存储空间的两个进程的交换

交换出的进程需要交换回它原来所占有的空间。这一限制是由地址捆绑方式决定的。如果捆绑是在汇编时或加载时决定，则不可移动到其他位置。如果捆绑在运行时确定，那么进程可以移到不同的地址空间。

交换需要备份存储，备份存储通常是足够大的快速磁盘，以容纳所有用户的内存映像拷贝，同时必须提供对这些内存映像的直接访问。系统有一就绪队列，包括在备份存储或在内存中准备运行的所有进程，当CPU需要切换进程时，调度程序检查队列中的下一进程是否已在内存中，如果不在，并且内存中没有空闲内存空间，调度程序会将内存中的进程交换出去，并换入即将执行的进程，然后重新装载寄存器，交换系统的关联转换时间比较长。

假设用户进程大小为1 MB且备份存储是传输速度为5 MB／s的标准硬盘，1 MB进程转入或转出内存的时间为假定无磁头寻址且平均延迟为8 ms，交换时间为208 ms。由于需要换出和换入，总的交换时间约为416 ms。为有效使用CPU，每个进程的执行时间必须大于交换时间。若是轮转法CPU调度算法，时间片应大于416 ms。

交换时间主要为转移时间，总的转移时间与所交换的内存空间直接成正比，如果内存空间为128 MB，操作系统占用5 MB，用户的最大空间为123 MB，如果一用户进程为1 MB，该进程的换出需要208 ms，而123 MB的交换需要24.6 s，所以需要了解用户进程真正需要的内存空间，而不是其可能需要的内存空间，交换时只需要交换出实际需要的内存，以便减少交换时间。操作时，用户需要提前告诉系统其内存需求情况，需要动态内存的进程通过系统调用来通知操作系统其需要内存变化情况。

2.交换

进程在执行中需要常驻内存。不过，进程在不需要执行时可从内存中交换（swap）到备份设备上，当需要再执行时再调回到内存中。例如，一个采用轮转调度算法的多道程序环境，时间片已到，内存管理器将刚刚执行过的进程换出，将另一进程换入（图5-8），同时CPU调度器可以将时间分配给新调入的进程，该进程时间片用完，再与另一进程交换。理想情况下，内存管理器可以以足够快的速度交换进程，以便当CPU调度器需要调度CPU时，总有进程在内存内可以执行。

改进后的交换策略被用在基于优先权的调度算法中，如果一个更高优先级进程进入系统，内存管理可以交换出最低优先级的进程，以装入和执行更高优先级的进程，当更高优先级进程执行完后，低优先级进程可