5.2.4　分区存储管理

分区存储管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区，以连续存储各进程的程序和数据，使各进程得以并发执行。

1.单一连续区分配

单一连续区分配也称为单道连续分配，是一种早期最简单的存储管理方式。内存分配以作业为单位进行。适用于单用户、单任务的操作系统。

（1）基本思想

将主存空间分为两部分，一部分为操作系统（Operating System,OS）所占的系统区，通常在低地址部分；其余的部分为用户区，作为一个连续区域整体分配给一个作业使用。每次主存中只能存放一道作业。

（2）内存分配与回收

当作业要投入运行时，首先检查该作业要求的存储容量，若大于主存的可分配存储空间，则该作业不能在该系统中运行；否则，将其调入主存，使其运行。作业运行结束后，释放作业占用的区域。

（3）地址转换

·采用静态重定位方式。

·硬件支持：界地址寄存器（存放操作系统所在空间的下界）。

·绝对地址=逻辑地址+界地址寄存器值。

（4）存储保护

主要防止用户作业执行时访问系统区。通过界地址寄存器和越界检查机构实现存储保护。CPU对每条指令的绝对地址进行检查，若绝对地址大于等于界地址寄存器中的值，即产生“地址越界”中断事件，进入操作系统异常处理，这样就限定了作业只能在规定的内存区内执行，避免破坏操作系统的信息，达到“存储保护”的目的。

（5）单一连续区管理的优缺点

·优点：管理简单，只需要很少的软件和硬件支持。

·缺点：CPU的利用率不高，主存空间浪费严重。

2.固定分区存储管理

固定分区存储管理又称为定长分区或静态分区，适用于任务数固定、程序大小已知的情形。

（1）基本思想

将内存中可分配的用户区预先划分成若干个连续区。分区个数固定，每个分区的大小固定，但大小可以相同，也可以不同。每个分区中可装入一个作业或进程，作业或进程在执行过程中不会改变存放区域。

（2）内存空间的分配与回收

设置一张内存分配表，说明各分区的分配情况。内容通常包括：分区的起始地址、长度以及为每个分区设置的一个标志位。当标志位为“0”时，表示分区空闲；当标志位为非“0”时，表示分区已被占用。采用顺序分配算法分配内存空间，即顺序查找内存分配表，找标志位为“0”的分区，比较装入作业的逻辑地址空间的长度和分区长度。作业执行完成后，通过管理程序改写内存分配表中的分区状态标志位来回收内存空间。固定分区分配算法如图5-1所示。

图　5-1　固定分区分配算法

图5-2给出了固定分区存储管理中的内存分配表和对应的内存状态。图5-2中，假设系统拥有256KB主存，操作系统占用低地址部分的20K，其余空间被划分为4个分区。其中1、2、3号分区已分配，4号分区未分配。采用这种分配技术，虽然可以使多个作业共享主存空间，但仍不能充分利用它。因为一个作业的大小不可能刚好等于某个分区的大小，所以在每个分区中，总有一部分空间被浪费掉（图5-2中第1、2、3分区中的阴影部分称为内碎片）。

图　5-2　固定分区存储管理中的分区分配

（3）地址转换

·主要采用静态重定位方式。

·硬件支持：下界寄存器与上界寄存器。

（4）存储保护

装入程序对每条指令中的地址都要进行核对。如果绝对地址在上、下限地址范围内，则可按绝对地址访问内存；如果不等式不成立，则形成“地址越界”的中断事件，达到存储保护的目的。

（5）固定分区管理的优缺点

·优点：允许多个作业同时进驻内存，解决了单道程序运行时主存空间利用率低的问题。

·缺点：分区个数固定，限制了并发执行的程序数目；分区划分不合适，可能会使一些分区经常没有作业装入，反而使主存的利用率不高；另外，存在内碎片，造成内存浪费。

3.可变分区存储管理

为了克服固定分区的缺点，人们又引进了可变分区方式。可变分区存储管理又称为动态分区管理。分区的划分时间、大小和位置都是动态的。

（1）基本思想

内存不预先划分，当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分区域给该作业；否则，令其等待内存资源。

（2）主存空间的分配与回收

为方便主存空间的分配和去配，主存分配表可由两张表格组成，一张称为“已分配区表”，另一张称为“空闲区表”。已分配区表记录已装入的作业在内存中占用分区的始址和长度，用标志位指出占用分区的作业名。空闲区表记录内存中可供分配的空闲区的始址和长度，用标志位指出该分区是未分配的空闲区。由于已占分区和空闲区的个数不定，因此两张表格中都应设置适当的空栏目，分别用以登记新内存分配表。

主存空间分配时，依据作业大小，在空闲区队列中查找满足要求的可用空闲区。若空闲区大小正好与作业大小相等，则分配该空闲区并将其从空闲区队列中删除；若空闲区大于作业大小，则将空闲区分割，一部分为已分配区，剩余部分为空闲区。因此，只要找到满足要求的可用空闲区，就需要对已分配区表和空闲区表的相关表项进行修改。

主存去配时，主要检查所回收的分区在主存中的邻接情况，如果其上、下有邻接的空闲区，则需要合并成一个连续的空闲区。如果没有邻接空闲区，则增加一个新的空闲区并加入到空闲区队列中。因此，主存空间回收后，都需要对空闲区表的相关表项进行修改。

（3）可变分区分配算法

1）首次/最先/最早适应分配算法（First Fit,FF）：顺序查找空闲区表（空闲区按地址递增顺序登记），找到第一个能满足作业长度要求的空闲区，分割这个找到的空闲区，一部分分配给作业，另一部分仍为空闲区。该算法实现简单，利于大作业的装入，但会造成内存负载不均衡，较大的空闲区保留在内存高端。随着低端分区不断划分，会产生较多的小分区，每次分配查找的时间开销也会增大，随着内碎片增多，主存利用率会降低，此外，也给回收分区带来了麻烦。

2）循环首次/下次适应分配算法（Circle First Fit,CFF）：每次分配总是从上次分配的下一个位置开始，向空闲区表尾部查找。查到第一个可满足的空闲区，立即分配。若查到尾部仍没有可满足的空闲区，则转到空闲区表头部重新开始查找。该算法不会导致小空闲区集中在主存的一端，解决了内存中负载不均衡问题。此外，缩短了平均查找时间。

3）最佳适应分配算法（Best Fit,BF）：挑选一个能满足作业要求的最小空闲区进行分配。这样保证不去分割一个更大的区域，较大的空闲区可以保留下来，使装入大作业时比较容易得到满足。该算法从整体上看，会产生较多的外碎片，通常无法分配，影响了内存空间的利用率。此外，每次分配都要对整个空闲区表从头到尾查找，系统开销较大，效率较低。一种提高查找效率的方法是在空闲区表中按照空闲区长度的递增顺序登记。

4）最坏适应分配算法（Worst Fit,WF）：总是挑选一个最大的空闲区分割一部分给作业使用，剩余部分的空闲空间不至于太小，仍可供分配使用，基本不留下小空闲区，不易形成外碎片。由于较大的空闲区不被保留，因此当有较大作业需要装入时，其要求不易满足；对中小型作业是有利。每次分配都要对整个空闲区表从头到尾搜索。可将空闲区长度以递减顺序排列，以提高查找效率。

（4）地址转换与存储保护

·采用动态重定位方式，有硬件地址转换机构提供支持。

·硬件支持：设置两个专用控制寄存器，基址寄存器用来存放作业或进程所占分区的起始地址；限长寄存器用来存放作业或进程所占连续存储空间的长度。当进程占用CPU运行后，操作系统将分区的起始地址和长度送入基址寄存器和限长寄存器。

作业执行过程中，处理器每执行一条指令，都要取出该指令中的逻辑地址。当逻辑地址小于限长寄存器中的限长值时，则逻辑地址加基址寄存器值就可得到绝对地址。

当逻辑地址大于等于限长寄存器中的限长值时，表示欲访问的内存地址超出了所分配的分区范围。这时就不允许访问，形成一个“地址越界”的程序性中断事件，达到存储保护的目的，如图5-3所示。

图　5-3　可变分区存储管理地址转换示意图

（5）可变分区管理的优缺点

·优点：解决了固定分区方式中存在的内碎片问题。

·缺点：因为必须将作业装入一个连续的主存储区域中，所以随着作业的装入和撤销，导致严重的外碎片问题，使得内存的利用率不高。可以通过移动技术解决外碎片问题。