【操作系统】内存空间的扩充、连续分配管理方式、动态分区分配算法

1. 内存空间的扩充

1. 覆盖技术

覆盖技术的思想：将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。

内存中分为一个“固定区”和若干个“覆盖区”。常驻内存的段放在“固定区”，调入后不在调出（除非运行结束）。不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。 必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点:对用户不透明，增加了用户编程负担。

覆盖技术只用于早期的操作系统中，现在已成为历史。

2. 交换技术

交换(对换)技术的设计思想:内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度) 中级调度(内存调度)，就是要决定将哪个处于挂起状态的进程重新调入内存。

暂时换出外存等待的进程状态为挂起状态(挂起态，suspend)

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态 1） 应该在外存(磁盘)的什么位置保存被换出的进程?

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式。总之，对换区的I/0速度比文件区的更快。

2）什么时候应该交换?

交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出。

3）应该换出哪些进程?

可优先换出阻塞进程;可换出优先级低的进程；为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间...

注意：PCB会常驻内存，不会被换出外存。

2. 内存空间的分配与回收

连续分配:指为用户进程分配的必须是一个连续的内存空间。

1. 单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点:实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护。

缺点:只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。

2. 固定分区分配

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。 分区大小相等:缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合。

分区大小不等:增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分。

操作系统需要建立一个数据结构—分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态(是否已分配) 当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”。

优点:实现简单，无外部碎片。

缺点: a. 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；b. 会产生内部碎片，内存利用率低。

3. 动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

1）系统要用什么样的数据结构记录内存的使用情况? 2）当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表(或空闲分区链)中选出一个分区分配给该作业。

3.如何进行分区的分配与回收操作?

原则：分配或回收前后多个相邻的空闲分区合并为一个。并修改相应空闲分区表的信息。

说明：

动态分区分配没有内部碎片，但是有外部碎片。

内部碎片，分配给某进程的内存区域中，有些部分没有用上。

外部碎片，是指内存中的某些空闲分区由于太小而难以利用。

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑(拼凑，Compaction)技术来解决外部碎片。

3. 动态分配算法

动态分区分配算法：在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?

1. 首次适应算法

算法思想:每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

2. 最佳适应算法

算法思想:由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。 缺点:每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

3. 最坏适应算法

又称最大适应算法(Largest Fit)

算法思想:为了解决最佳适应算法的问题---即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。 缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

4. 邻近适应算法

算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现:空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

4. 小结