操作系统9：存储管理之连续分配和对换

秒速五厘米 2024-03-17 14:34 95阅读 0赞

**目录**

1、连续分配存储管理方式

（1）单一连续分配

（2）固定分区分配

2.1 - 划分分区的方法

2.2 - 内存分配

（3）动态分区分配

3.1 - 动态分区分配中的数据结构

3.2 - 动态分区分配算法

3.3 - 分区分配操作

（4）基于顺序搜索的动态分区分配算法

4.1 - 首次适应（first fit，FF）算法

4.2 - 循环首次适应（next fit，NF）算法

4.3 - 最佳适应（best fit，BF）算法

4.4 - 最坏适应（worst fit，WF）算法

（5）基于引搜索的动态分区分配算法

5.2 - 伙伴系统（buddy system）

5.3 - 哈希算法

（6）动态可重定位区分配

6.1 - 紧凑

6.2 - 动态重定位

6.3 - 动态重定位分区分配算法

2、对换(Swapping)

（1）多道程序境下的对换技术

1.1 - 对换的引入

1.2 - 对换的类型

（2）对换空间的管理

2.1 - 对换空间管理的主要目标

2.2 - 对换区空闲盘块管理中的数据结构

2.3 - 对换空间的分配与回收

（3）进程的换出与换入

3.1 - 进程的换出

3.2 - 进程的换入

--------------------

### 1、连续分配存储管理方式 ###

为了能将用户程序装入内存，必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式，曾被广泛应用于上世纪 60~80 年代的 OS 中，该分配方式为一个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻。连续分配方式可分为四类：**单一连续分配**、**固定分区分配**、**动态分区分配**以及**动态可重定位分区分配**算法四种方式。

#### （1）单一连续分配 ####

在单道程序环境下，当时的存储器管理方式是把**内存**分为**系统区**和**用户区**两部分，系统区仅提供给 OS 使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。

![9d6aea61ffa2466da8b53891f9c62b31.png][]

虽然在早期的单用户、单任务操作系统中，有不少都配置了存储器保护机构，用于防止用户程序对操作系统的破坏，但在 20 世纪 80 年代所产生的几种常见的单用户操作系统中，如 CP/M、MS-DOS 及 RT11 等，并未采取存储器保护措施。这是因为，一方面可以节省硬件，另一方面在单用户环境下，机器由一用户独占，不可能存在其他用户干扰的问题，因此这是可行的。即使出现破坏行为，也仅仅会是用户程序自己破坏操作系统，其后果并不严重，只会影响该用户程序的运行，且操作系统也很容易通过系统的再启动而重新装入内存。

#### （2）固定分区分配 ####

为了能在内存中装入多道程序，且使这些程序之间又不会发生相互干扰，于是将整个用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样就形成了最早的、也是最简单的一种可运行多道程序的**分区式存储管理方式**。如果在内存中有四个用户分区，便允许四个程序并发运行。当有一空闲分区时，便可以再从外存的后备作业队列中选择一个适当大小的作业，装入该分区。当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。

![119df8e89046455fb2c2dcf6acec3c78.png][]

##### 2.1 - 划分分区的方法 #####

可用下述两种方法将内存的用户空间划分为若干个固定大小的分区：

*  **分区大小相等**（指所有的内存分区大小相等）。其缺点是缺乏灵活性，即当程序太小时，会造成内存空间的浪费。当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。尽管如此，对于利用一台计算机同时控制多个相同对象的场合，因为这些对象所需的内存空间大小往往相同，这种划分方式比较方便和实用，所以被广泛采用。例如，炉温群控系统就是利用一台计算机去控制多台相同的冶炼炉。
 *  **分区大小不等**。为了增加存储器分配的灵活性，应将存储器分区划分为若干个大小不等的分区。最好能对常在该系统中运行的作业大小进行调查，根据用户的需要来划分。通常，可把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区，这样，便可根据程序的大小，为之分配适当的分区。

##### 2.2 - 内存分配 #####

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

![7a8620ba0d5d49f69db4959f618e3fe3.png][]

固定分区分配是最早出现的、可用于多道程序系统中的存储管理方式，由于每个分区的大小固定，必然会造成存储空间的浪费，因而现在已很少将它用于通用的 OS 中。但在某些用于控制多个相同对象的控制系统中，由于每个对象的控制程序大小相同，是事先已编好的，其所需的数据也是一定的，故仍采用固定分区式存储管理方式。//固定分区分配方式存在内存浪费问题

#### （3）动态分区分配 ####

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

##### 3.1 - 动态分区分配中的数据结构 #####

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

**空闲分区表。**在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项。

![83d24ba6b2fc457481e7345fb4797d69.png][]

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

![b01eaf0218984f46ad1143bafc47850e.png][]

##### 3.2 - 动态分区分配算法 #####

为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。// 内存分配算法对系统性能有很大的影响，后续将详细介绍

##### 3.3 - 分区分配操作 #####

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

**分配内存**

系统应利用某种分配算法，从空闲分区链（表）中找到所需大小的分区。

设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 **m.size - u.size <= size**（size 是事先规定的不再切割的剩余分区的大小），说明多余部分太小，可不再切割，将整个分区分配给请求者。//当分区不能再切割时，分配整个分区

否则（即多余部分超过 size），便从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链（表）中。然后，将分配区的首址返回给调用者。

**回收内存**

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

*  回收区与插入点的前一个空闲分区 F1 相接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 F1 的大小。
 *  回收分区与插入点的后一空闲分区 F2 相接。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
 *  回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并使用 F1 的表项和 F1 的首址，取消 F2 的表项，大小为三者之和。
 *  回收区既不与 F1 邻接，又不与 F2 接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

![8a3a51bfe7c04740a2ecbf8cee0e3f8e.png][]

#### （4）基于顺序搜索的动态分区分配算法 ####

为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。所谓顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。基于顺序搜索的动态分区分配算法有如下四种：**首次适应算法**、**循环首次适应算法**、**最佳适应算法**和**最坏适应算法**。//适用于分区不是很多的系统

##### 4.1 - 首次适应（first fit，FF）算法 #####

FF 算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败，返回。

![160c253a97ac45e9a02aa68dbf3ef843.png][]

该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销。

##### 4.2 - 循环首次适应（next fit，NF）算法 #####

为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。

![317f492dab9a4c3c898ff9de6ee1ee03.png][]

为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。

##### 4.3 - 最佳适应（best fit，BF）算法 #####

所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区必然是最佳的。

孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的碎片。

##### 4.4 - 最坏适应（worst fit，WF）算法 #####

由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。

实际上，这样的算法未必是最坏的，它的优点是可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。同时，最坏适应分配算法查找效率很高，该算法要求，将所有的空闲分区，按其容量以从大到小的顺序形成一空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。

#### （5）基于引搜索的动态分区分配算法 ####

基于顺序搜索的动态分区分配算法，比较适用于不太大的系统。当系统很大时，系统中的内存分区可能会很多，相应的空闲分区链就可能很长，这时采用顺序搜索分区方法可能会很慢。为了提高搜索空闲分区的速度，在大、中型系统中往往会采用基于索引搜索的动态分区分配算法，目前常用的有**快速适应算法**、**伙伴系统**和**哈希算法**。

**5.1 - 快速适应（quick fit）算法**

该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。//就像一张hash表

空闲分区的分类是根据进程常用的空间大小进行划分的，如 2KB、4KB、8KB 等，对于其它大小的分区，如 7KB 这样的空闲区既可以放在 8KB 的链表中，也可以放在一个特殊的空闲区链表中。

![97d34e627247480e94e092618ef97fff.png][]

该算法在搜索可分配的空闲分区时分为两步：

*  第一步是根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表；
 *  第二步是从链表中取下第一块进行分配即可。

另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。优点是查找效率高。

该算法的主要缺点在于为了有效合并分区，在分区归还主存时的算法复杂，系统开销较大。此外，该算法在分配空闲分区时，是以进程为单位的，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。这是典型的**以空间换时间**的做法。

##### 5.2 - 伙伴系统（buddy system） #####

该算法规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂（k 为整数）。假设系统的可利用空间容量为 2^m 个字，则系统开始运行时，整个内存区是一个大小为 2^m 的空闲分区。

在系统运行过程中，由于不断地划分，将会形成若干个不连续的空闲分区，将这些空闲分区按分区的大小进行分类。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，这样，不同大小的空闲分区形成了 k 个空闲分区链表。// 一次分配要进行多次分割

![c7a2be8a0b874e13b714af3026d3e697.png][]

当需要为进程分配一个长度为 n 的存储空间时，首先计算一个i值，使 2^(i-1) < n <= 2^i，然后在空闲分区大小为 2^i 的空闲分区链表中查找。

若找到，即把该空闲分区分配给进程。否则，表明长度为 2^i 的空闲分区已经耗尽，则在分区大小为 2^(i+1) 的空闲分区链表中寻找。若存在 2^(i+1) 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。

若大小为 2^(i+1) 的空闲分区也不存在，则需要查找大小为 2^(i+2) 的空闲分区，若找到则也对其进行两次分割：第一次，将其分割为大小为 2^(i+1) 的两个分区，一个用于分配，一个加入到大小为 2^(i+1) 的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为 2^i 的两个分区，一个用于分配，一个加入到大小为 2^i 的空闲分区链表中。

若仍然找不到，则继续查找大小为 2^(i+3) 的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对 2^k 的空闲分区进行 k 次分割才能得到所需分区。

![674e28901f8c4381b67494f31180ae52.png][]

与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为 2^i 的空闲分区时，若事先已存在 2i 的空闲分区，则应将其与伙伴分区合并为大小为 2^(i+1) 的空闲分区，若事先已存在 2^(i+1) 的空闲分区，又应继续与其伙伴分区合并为大小为 2^(i+2) 的空闲分区，依此类推。//如果有成对的相同空闲分区，那么进行合并

在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比快速适应算法差，但由于它采用了索引搜索算法，比顺序搜索算法好。而其空间性能，由于对空闲分区进行合并，减少了小的空闲分区，提高了空闲分区的可使用率，故优于快速适应算法，比顺序搜索法略差。

##### 5.3 - 哈希算法 #####

在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过查找得到一个空闲分区。如果对空闲分区分类较细，则相应索引表的表项也就较多，因此会显著地增加搜索索引表的表项的时间开销。

哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。//减少搜索索引表的表项的时间开销

当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。

#### （6）动态可重定位区分配 ####

##### 6.1 - 紧凑 #####

连续分配方式的一个重要特点是，一个系统或用户程序必须被装入一片连续的内存空间中。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲空间。即使这些分散的许多小分区的容量总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。//因为碎片过多，且无法连续，导致内存浪费

例如，在内存中现有四个互不邻接的小分区，它们的容量分别为 10 KB、30 KB、14 KB 和 26 KB，其总容量是 80 KB，但如果现在有一个作业到达，要求获得 40 KB 的内存空间，由于必须为它分配一个连续空间，故此作业无法装入。这种不能被利用的小分区即是前已提及的 **“碎片”**，或称为 **“零头”**。

![f8ff3682055e45eabf896222536106bd.png][]

若想把大作业装入，可采用的一种方法是：将内存中的所有作业进行移动，使它们全都相邻接。这样，即可把原来分散的多个空闲小分区拼接成一个大分区，可将一个作业装入该区。这种通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。

虽然“紧凑”能获得大的空闲空间，但也带来了新的问题，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。为了提高内存的利用率，系统在运行过程中是经常需要进行“紧凑”的，每“紧凑”一次，就要对移动了的程序或数据的地址进行修改，这不仅是一件相当麻烦的事情，而且还大大地影响到系统的效率。那么，使用**动态重定位方法将能很好地解决此问题**。

##### 6.2 - 动态重定位 #####

使用动态运行时装入的方式中，作业装入内存后的所有地址仍然都是相对(逻辑)地址。而将相对地址转换为绝对(物理)地址的工作被推迟到程序指令要真正执行时进行。

为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个**重定位寄存器**，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。//相对地址+重定位寄存器地址

地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”，而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可。//动态重定位的实现原理

![5a21ad3f4c184a25925f276812381363.png][]

##### 6.3 - 动态重定位分区分配算法 #####

动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。

通常，当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这时便须对内存进行“紧凑”，将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求，则返回分配失败信息。//如果内存不够，触发一次紧凑，Java虚拟机的内存回收就是这一原理

### 2、对换(Swapping) ###

对换技术也称为交换技术，最早用于麻省理工学院的单用户分时系统 CTSS 中。由于当时计算机的内存都非常小，为了使该系统能分时运行多个用户程序而引入了对换技术。系统把所有的用户作业存放在磁盘上，每次只能调入一个作业进入内存，当该作业的一个时间片用完时，将它调至外存的后备队列上等待，再从后备队列上将另一个作业调入内存。这就是最早出现的分时系统中所用的对换技术。现在已经很少使用。

由上所述可知，要实现内、外存之间的对换，系统中必须有一台 I/O 速度较高的外存，而且其容量也必须足够大，能容纳正在分时运行的所有用户作业，目前最常使用的是大容量磁盘存储器。

#### （1）多道程序境下的对换技术 ####

##### 1.1 - 对换的引入 #####

在多道程序环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞，而无可运行之进程，迫使 CPU 停止下来等待的情况；另一方面，却又有着许多作业，因内存空间不足，一直驻留在外存上，而不能进入内存运行。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。

为了解决这一问题，在系统中又增设了对换(也称交换)设施。所谓 **“对换”**，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据换入内存。对换是改善内存利用率的有效措施，它可以直接提高处理机的利用率和系统的吞吐量。//增加资源利用率

##### 1.2 - 对换的类型 #####

在每次对换时，都是将一定数量的程序或数据换入或换出内存。根据每次对换时所对换的数量，可将对换分为如下两类：

*  **整体对换**。处理机中级调度实际上就是存储器的对换功能，其目的是用来解决内存紧张问题，并可进一步提高内存的利用率和系统的吞吐量。由于在中级调度中对换是以整个进程为单位的，故称之为“进程对换”或“整体对换”。这种对换被广泛地应用于多道程序系统中，并作为处理机中级调度。
 *  **页面(分段)对换**。如果对换是以进程的一个“页面”或“分段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又统称为“部分对换”。这种对换方法是请求分页和请求分段式存储管理的基础，其目的是为了支持虚拟存储系统。//页面对换，在分页和分段中介绍

为了实现进程对换，系统必须能实现三方面的功能：对**对换空间的管理**、**进程的换出**和**进程的换入**。

#### （2）对换空间的管理 ####

##### 2.1 - 对换空间管理的主要目标 #####

在具有对换功能的OS中，通常把磁盘空间分为**文件区**和**对换区**两部分。

**文件区管理的主要目标**

文件区占用磁盘空间的大部分，用于存放各类文件。由于通常的文件都是较长时间地驻留在外存上，对它访问的频率是较低的，故对文件区管理的主要目标是提高文件存储空间的利用率，然后才是提高对文件的访问速度。因此，对文件区空间的管理**采取离散分配**方式。//优先考虑空间，其次才是速度

**对换空间管理的主要目标**

对换空间只占用磁盘空间的小部分，用于存放从内存换出的进程。由于这些进程在对换区中驻留的时间是短暂的，而对换操作的频率却较高，故对对换空间管理的主要目标，是提高进程换入和换出的速度，然后才是提高文件存储空间的利用率。为此，对对换区空间的管理**采取连续分配**方式，较少考虑外存中的碎片问题。//优先考虑速度，其次才是空间

##### 2.2 - 对换区空闲盘块管理中的数据结构 #####

为了实现对对换区中的空闲盘块的管理，在系统中应配置相应的数据结构，用于记录外存对换区中的空闲盘块的使用情况。其数据结构的形式与内存在动态分区分配方式中所用数据结构相似，即**同样可以用空闲分区表或空闲分区链**。在空闲分区表的每个表目中，应包含两项：对换区的**首址**及其**大小**，分别用盘块号和盘块数表示。

##### 2.3 - 对换空间的分配与回收 #####

由于对换分区的分配采用的是连续分配方式，因而对换空间的分配与回收与动态分区方式时的内存分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法等。

#### （3）进程的换出与换入 ####

当内核因执行某操作而发现内存不足时，例如，当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，便调用对换进程，它的主要任务是实现进程的换出和换入。//对换操作是由特定的进程实现的

##### 3.1 - 进程的换出 #####

对换进程在实现进程换出时，是将内存中的某些进程调出至对换区，以便腾出内存空间。换出过程可分为以下两步：

（1）选择被换出的进程。对换进程在选择被换出的进程时，将检查所有驻留在内存中的进程，首先**选择处于阻塞状态或睡眠状态的进程**，当有多个这样的进程时，应当**选择优先级最低的**进程作为换出进程。在有的系统中，为了防止低优先级进程在被调入内存后很快又被换出，还需考虑进程在内存的驻留时间。如果系统中已无阻塞进程，而现在的内存空间仍不足以满足需要，便选择优先级最低的就绪进程换出。

![6cac9006af4e4d50b6f65260d72369af.png][]

（2）进程换出过程。应当注意，在选择换出进程后，在对进程换出时，只能换出非共享的程序和数据段，而对于那些共享的程序和数据段，只要还有进程需要它，就不能被换出。在进行换出时，应**先申请对换空间**，若申请成功，就启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块和内存分配表等数据结构做相应的修改。若此时内存中还有可换出的进程，则继续执行换出过程，直到内存中再无阻塞进程为止。

##### 3.2 - 进程的换入 #####

对换进程将定时执行换入操作，它首先查看 PCB 集合中所有进程的状态，从中**找出“就绪”状态但已换出的进程**。当有许多这样的进程时，它将**选择其中已换出到磁盘上时间最久的进程**（必须大于规定时间，如 2s）作为换入进程，为它申请内存。如果申请成功，可直接将进程从外存调入内存；如果失败，则需先将内存中的某些进程换出，腾出足够的内存空间后，再将进程调入。

在对换进程成功地换入一个进程后，若还有可换入的进程，则再继续执行换入换出过程，将其余处于**“就绪且换出”**状态的进程陆续换入，直到内存中再无“就绪且换出”状态的进程为止，或者已无足够的内存来换入进程，此时对换进程才停止换入。

由于要交换一个进程需要很多的时间，因此，对于提高处理机的利用率而言，它并不是一个非常有效的解决方法。目前用得较多的对换方案是，在处理机正常运行时，并不启动对换程序。但如果发现有许多进程在运行时经常发生缺页且显现出内存紧张的情况，才启动对换程序，将一部分进程调至外存。如果发现所有进程的缺页率都已明显减少，而系统的吞吐量已下降时，则可暂停运行对换程序。// 进程的换入和换出要考虑进程的缺页率和系统的吞吐量

[9d6aea61ffa2466da8b53891f9c62b31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/086c9b21e92047569b76daa103ce9155.png
[119df8e89046455fb2c2dcf6acec3c78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f3c0e6da70cd42c6b4616b7baf9b6022.png
[7a8620ba0d5d49f69db4959f618e3fe3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e250cd4f759b4afa942e83535ac9e5ae.png
[83d24ba6b2fc457481e7345fb4797d69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a7eb3d1447c9421e8016723627b0e005.png
[b01eaf0218984f46ad1143bafc47850e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0d6b9654805143b2a568bc56ef4d4dec.png
[8a3a51bfe7c04740a2ecbf8cee0e3f8e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e5c7440e23bb4a04a92f48627716d78f.png
[160c253a97ac45e9a02aa68dbf3ef843.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9b12e4260c7f40e9b49e92df36f6b8e7.png
[317f492dab9a4c3c898ff9de6ee1ee03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f8d16ba3db154b7b90da19d251032cf8.png
[97d34e627247480e94e092618ef97fff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b06a3c3f5b3449068a95e88412f68c01.png
[c7a2be8a0b874e13b714af3026d3e697.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/17d82fbcd4aa46a5b90542e3a4589407.png
[674e28901f8c4381b67494f31180ae52.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6ac9c74c41e04fbdb8ae03cc40606ebf.png
[f8ff3682055e45eabf896222536106bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/87516300a7ce4b19b17f44f9107719d3.png
[5a21ad3f4c184a25925f276812381363.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/01c72cc67dc44191b5371e73d6981148.png
[6cac9006af4e4d50b6f65260d72369af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/244f5d42d3d448bd998489547e3ea355.png