内存换出的重要性及与换入的关系

现在我们讲第25讲，主题是内存的换出（swipe out）。实际上，上一讲我们讲的是内存的换入，而这一节聚焦于内存的换出。
换入和换出必须合在一起工作，不能只有换入而没有换出。上节课也提到，换入换出合在一起的目的是实现虚拟内存。我们有一个0 - 4g的完整虚拟内存空间，但物理内存可能只有1g。这就好比仓库很大，而门店空间有限。当我们访问虚拟地址、需要虚拟页时，就要从磁盘上把这一页换到内存中。然而，如果只进行换入，不断地将内容从磁盘换到内存，迟早内存会满。所以，有换入就必须有换出，这样才能空出物理内存，让新的内容换入，保证系统合理工作。

内存换出算法的引出

换出操作涉及到选择哪一页淘汰的算法，这个算法与get free page相关。
get free page用于获取物理空闲页，它出现在页面中断处理程序do no page（14号中断的处理程序）中。在这个程序里，首先会申请一个空闲页，然后从磁盘上读入。但内存有限，并非总有新的空闲页，所以在申请空闲页时，如果空闲页不够，就需要找一页换出去，再进行申请，这部分代码就应该放在这里。接下来我们就来探讨有哪些算法可以用于选择换出的页面。

常见的页面置换算法

1. 先来先出（FIFO）算法

   • 最开始能想到的页面置换算法就是先来先出。这种调度方法本质上和资源分配、剥夺相关，和最大化、最小化问题没有本质区别。我们通常从最简单的先来先服务问题开始思考调度算法，然后分析其问题，逐步提出更好的算法。
   • 例如，我们分配了三个页框，页面访问序列为A、B、C、A、B、D。A来了放入1号页框，B来了放入，C来了也放入。此时A又来，由于页框已满，按照先来先出原则，把最先进入的A换出。接着D来了，再把B换出。但这里存在问题，D刚把A换出去，A马上又来，导致频繁换入换出，增加了磁盘读写操作，降低了指令执行速度。这说明先来先服务算法存在缺点，我们需要改进。

2. 最优（OPT）算法

   • 为了改进FIFO算法的不足，我们引出了最优算法（OPT）。还是以上面的例子，当D要换入时，我们往后看，发现A和B马上会被使用，而C是未来才会使用，所以换出C是最合适的。这样操作后，产生缺页的次数从原来的7次减少到5次，效果变优。
   • 然而，最优算法存在一个严重问题，它需要知道将来会访问哪一页，但在实际执行过程中，我们无法预知程序将来会执行哪一页，所以这个算法理论上很完美，但在实际中无法使用。

3. 最近最少使用（LRU）算法

   • 由于无法预知未来，人们想到用过去的历史去预测未来，这就是LRU算法的核心思想。程序往往具有局部性，在一段时间内会在一定范围内不断访问某些页面。例如在while循环中，会反复访问相关页面。所以，历史上最近一段时间老使用的页面，待会儿也很可能会使用；而最近一段时间没有使用的页面，我们可以预测未来也不太可能使用，就将其淘汰。
   • 同样以A、B、C、A、B、D的访问序列为例，当D要换入时，最近最少使用的是C，所以把C换出。后续操作中，LRU算法的缺页次数也是5次，效果不错。在实际系统中通过实验验证，LRU算法确实是公认的很好的页面置换算法。

4. LRU算法的实现及问题

   • 时间戳实现：最常想到的LRU算法实现方式是使用时间戳。为每个页面维护一个时间戳，记录页面的使用时刻。每次访问页面时，更新其时间戳。当需要换出页面时，选择时间戳最小的页面。但这种方法在实际操作系统中代价太大，因为每执行一条指令，都要访问逻辑页，查页表进行地址翻译，此时都需要针对当前在内存中的页面维护时间戳，不仅要修改时间戳，还可能面临时间戳溢出的问题，会极大地降低计算机运行速度，不可行。

   • 页面栈实现：另一种实现方式是使用页面栈。栈的顶部始终保留最近使用的页面，其他页面按照使用顺序排列。每次访问页面时，将该页面移动到栈顶。当需要换出页面时，选择栈底的页面。但这种方式同样存在问题，每次访问页面都需要调整栈中页面的位置，即使使用指针实现，也需要修改多次指针，实现代价也很大，在实际系统中也不实用。

   • 因此，LRU算法虽然理论上优秀，但准确实现困难，需要进行近似实现。

5. Clock算法（二次机会算法）

   • 基本思想：为了近似实现LRU算法，我们引入引用位（reference bit）。每访问一页，就将其引用位置为1，表示该页被访问过。当需要淘汰页面时，如果引用位为1，就将其置为0，不淘汰该页，再给它一次机会；如果引用位为0，说明该页最近没有被访问过，就将其淘汰。这是对LRU算法的一种近似，它不是严格的最近最少使用，而是基于最近是否使用来决定是否淘汰页面。

   • 效率与问题：这种算法的效率相对较高，因为每访问一页，只需要修改一位引用位，而且MMU查页表时可以自动将访问页面的引用位置为1。然而，它对LRU的近似效果不好。由于程序具有局部性，缺页通常很少发生。当缺页很少时，页面会被频繁访问，引用位会一直保持为1，导致指针扫描时，所有页面的引用位都为1。一旦缺页，指针扫描会将所有引用位都置为0，然后按顺序换出页面，这样就退化成了FIFO算法，失去了LRU算法的思想，页面置换效果变差。

6. 改进的Clock算法

   • 问题分析与解决：为了解决上述Clock算法的问题，我们需要分析原因。二次机会算法退化成FIFO的原因是引用位记录了太长的历史信息，指针扫描速度太慢，无法体现“最近”的概念。所以，解决的核心在于定时清除引用位，缩短其记录信息的时间。我们可以使用一个扫描指针定时将引用位置为0，这样就能体现最近一段时间内页面是否被使用。当淘汰页面的指针扫描时，如果发现页面引用位为0，就将其淘汰，这样更符合LRU算法的思想。
   • 命名由来：这种改进后的算法，一个指针快速清除引用位，一个指针慢速扫描淘汰页面，就像时钟的指针转动，所以被称为Clock算法。在实际系统中，将定时清除引用位的操作放在时钟中断中，淘汰页面的操作放在缺页时get free page前面，通过这些程序的相互配合，实现了对LRU算法的近似，完成页面换出操作。

进程页面分配数量问题

在解决了页面换出算法后，还需要考虑一个附带问题，即应该给一个进程分配多少个页框。分配的页框数量过多，会浪费系统内存；分配过少，会产生颠簸问题。

1. 颠簸现象：当进程数量过多时，给每个进程分配的页框就会减少，导致每个进程的缺页率增加。例如，一个进程本需要4页内存，但只分配了3页。在执行过程中，刚把第4页换出，马上又需要使用，再换入第4页时，又会导致其他某一页被换出，如此反复，不停缺页。每次缺页都要启动磁盘进行页面换入换出，CPU需要等待磁盘操作完成，导致CPU利用率急剧下降，这种现象就是系统颠簸。系统一旦出现颠簸，效率会变得很低，用户程序无法正常推进，用户体验变差。
2. 合理分配数量：为了避免颠簸，分配给进程的页框个数应该能够覆盖住程序访问内存的局部。但这个局部的大小很难确定，因为程序的执行情况复杂，包含循环、条件语句等多种结构。虽然有一些算法可以计算工作集来确定局部大小，进而确定合理的页框分配数量，但在一些基本的操作系统中，也可以采用近似算法，根据缺页情况动态调整页框分配数量。例如，如果缺页较多，就多分配几个页框；如果缺页较少，就少分配几个页框。总之，要合理调整给进程分配的页框数量，避免颠簸现象的发生。

换入换出与操作系统整体架构

当我们确定好给进程分配的页框数量后，就可以形成一个Clock的环形数组，应用Clock算法进行页面淘汰和内存换出操作。结合之前讲的内存换入（当访问地址缺页时，进行缺页中断，从磁盘读入一页，若页框不足，使用Clock算法换出一页，再将新页换入），这就构成了完整的内存换入换出过程，也就是著名的swap分区的工作原理。在安装Linux时，通常会让用户安装swap分区，它的工作就是进行内存的换入换出。
实现换入换出是为了实现虚拟内存，而虚拟内存又是为了实现分页，分页是操作系统管理内存的重要思想，目的是让程序能够载入并执行起来，最终落实到进程的运行。内存管理和进程管理是操作系统的核心部分，再加上外围的设备驱动、文件系统、系统接口以及系统初始化和引导等模块，就构成了一个完整的操作系统。如果能够深入理解这些内容，将其融会贯通，就能对操作系统有更深刻的认识，甚至有可能自己设计和实现一个操作系统，或者在实际操作系统中进行模块设计和修改 。