操作系统——虚拟内存和页面置换算法（一文详解操作系统的虚拟内存和页面置换算法）

1、虚拟内存

答： 这个在我们平时使用电脑特别是 Windows 系统的时候太常见了。很多时候我们使用点开了很多占内存的软件，这些软件占用的内存可能已经远远超出了我们电脑本身具有的物理内存。为什么可以这样呢？ 正是因为虚拟内存的存在，通过虚拟内存可以让程序可以拥有超过系统物理内存大小的可用内存空间。另外，虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。这样会更加有效地管理内存并减少出错。

虚拟内存是计算机系统内存管理的一种技术，我们可以手动设置自己电脑的虚拟内存。不要单纯认为虚拟内存只是“使用硬盘空间来扩展内存“的技术。虚拟内存的重要意义是它定义了一个连续的虚拟地址空间，并且 把内存扩展到硬盘空间。

2、内存管理的目的

答： 最主要的就是提高内存的利用率，所谓的提高内存利用率，就是尽可能的在内存中多存储进程，这就涉及到为进程分配内存空间了。分配的方式主要是有两种——连续分配和离散分配。

3、局部性原理

答：局部性原理是虚拟内存技术的基础，正是因为程序运行具有局部性原理，才可以只装入部分程序到内存就开始运行。

局部性原理表现在以下两个方面：

• 时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
• 空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

4、虚拟存储器

答：基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其他部分留在外存，就可以启动程序执行。由于外存往往比内存大很多，所以我们运行的软件的内存大小实际上是可以比计算机系统实际的内存大小大的。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换到外存上，从而腾出空间存放将要调入内存的信息。这样，计算机好像为用户提供了一个比实际内存大的多的存储器——虚拟存储器。

我觉得虚拟内存同样是一种时间换空间的策略，你用 CPU 的计算时间，页的调入调出花费的时间，换来了一个虚拟的更大的空间来支持程序的运行。不得不感叹，程序世界几乎不是时间换空间就是空间换时间。

5、虚拟内存的技术实现

答：虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。 虚拟内存的实现有以下三种方式：

• 请求分页存储管理：建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。
• 请求分段存储管理：建立在分段存储管理之上，增加了请求调段功能、分段置换功能。请求分段储存管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。
• 请求段页式存储管理

请求分页与分页存储管理，两者有何不同呢？

• 请求分页存储管理建立在分页管理之上。他们的根本区别是是否将程序全部所需的全部地址空间都装入主存，这也是请求分页存储管理可以提供虚拟内存的原因，我们在上面已经分析过了。
• 它们之间的根本区别在于是否将一作业的全部地址空间同时装入主存。请求分页存储管理不要求将作业全部地址空间同时装入主存。基于这一点，请求分页存储管理可以提供虚存，而分页存储管理却不能提供虚存。

6、什么是页面置换算法

答：进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区，其中选择调出页面的算法就称为页面置换算法。

好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。

7、为什么要使用页面置换算法

答：当进程运行时，要访问的页面不在内存，则出现缺页中断，需要把该页面调入内存，如果内存中没有空闲物理块，则需要进行页面置换．页面置换算法依据一定策略，把物理块中的某个页面置换出去，送到磁盘交换区，在空出的一个物理块中装入导致缺页中断的页面。

8、最佳置换算法

答：FIFO算法是基于队列实现的，不是堆栈类算法，即未来永远不会再使用的页面 or 未来最长时间不再被访问的页面。该算法保证了可以获得最低缺页率，但无法预知未来页面的使用情况，因此目前无法实现，但通常用来评价其他算法。

• 优点：可保证最低缺页率。
• 缺点
  • 置换的页面可以是很久以前使用过但现已不再使用的初始化模块；所置换的页面可能包含一个被大量使用的变量，它早就初始化了，但仍在不断使用。
  • 对页面的访问时间无法预知，故该算法无法实现。

9、先进先出（FIFO）页面置换算法

答：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。这种页面置换算法确保对于给定数量的帧会产生最低的可能的缺页错误率。

FIFO 和 OPT 算法的区别： 在于除了在时间上向后或向前看之外，FIFO算法使用的是页面调入内存的时间，OPT算法使用的是页面将来使用的时间。

• 优点： 实现简单
• 缺点：往往与进程实际运行的规律不相符。有些页面，如存放全局变量、常用函数的页面，在整个进程的运行过程中将会被频繁访问。如果频繁将其换进换出，则会产生“抖动”现象，因此，这种算法在实际中应用很少。

10、最近最久未使用（LRU）算法

答：LRU 是堆栈类的算法，堆栈类算法不可能出现Belay异常。该算法以过去预测未来，选择之前最长时间未使用的页面置换。但是由于利用“过去”作为“未来”的近似这一做法并非完全可靠，因此有时会造成缺页率非常高，导致效率会非常低。

Belady现象的描述： 一个进程P要访问M个页，OS分配N(N<M)个内存页面给进程P；对一个访问序列S，发生缺页次数为PE(S,N)。当N增大(且N小于M)时，PE(S, N)时而增大，时而减小。FIFO是最早出现的页置换算法之一。Belady现象的原因是FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的，因而FIFO并不是一个好的置换算法。

• 优点： 由于考虑程序访问的时间局部性，一般能有较好的性能。实际应用多。
• 缺点： 实现需要较多的硬件支持，会增加硬件成本。

11、Clock 置换算法

答：Clock置换算法是一种LRU的近似算法。由于LRU算法需要较多的硬件支持，采用Clock算法只需相对较少的硬件支持。Clock也称之为最近未用算法NRU。

• 优点： 可减少磁盘的I/O操作数
• 缺点： 实现该算法本身的开销将有所增加

11.1、执行过程

答：只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。在选择页面淘汰时，只需检查页的访问位，如果是0，就选择该页换出；若为1，则重新将它置为0，暂时不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。由于该算法是循环地检查各页面的使用情况，故称为Clock算法。

11.2、改进型Clock置换算法：

答：由访问位A和修改位M可以组合成下面四种类型的页面：

• 1类（A=0, M=0）： 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。
• 2类（A=0, M=1）： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。
• 3类（A=1, M=0）： 最近已被访问， 但未被修改， 该页有可能再被访问。
• 4类（A=1, M=1）： 最近已被访问且被修改， 该页可能再被访问。

12、最少使用置换算法

答：为每个页面配置一个计数器，一旦某页被访问，则将其计数器的值加1，在需要选择一页置换时，则将选择其计数器值最小的页面，即内存中访问次数最少的页面进行淘汰。

13、页面缓冲算法

答：规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中；否则，便放入已经修改页面的链表中的一个。须注意的是，这时页面在内存中并不做物理上的移动，而只是将页表中的表项移到上述两个链表之一中。