本文共 8506 字，大约阅读时间需要 28 分钟。

一、基本概念

1、普通存储器管理方式的特征

• 普通存储器，也即传统存储器管理方式有如下两个特征：

1）一次性

• 作业必须一次性全部装入内存后，才能开始运行。这样一来极容易出现两种情况：
  ① 作业很大，超过内存的容量，无法装入内存，从而作业也就无法运行。
  ② 作业很多时，由于内存不足以装下所有作业，只有少数作业先运行，导致多道程序度下降。

2）驻留性

• 作业装入内存后，便会一直留在内存中，其任何部分都不会被换出，直到作业结束。尽管运行中的进程会因I/O而长期等待，或有的程序模块在运行过一次后就不再需要了，但它们都将继续占用宝贵的内存资源。

2、局部性原理

• 1968年，Denning.P 曾指出：程序执行时将呈现出局部性规律，即在一较短时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。他提出了以下几个论点：
  ① 程序执行时，除了少部分的转移和过程调用指令外，大多数情况下仍是顺序执行的。
  ② 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过 5.这就是说，程序将在一段时间内都局限在这些过程的范围内运行。
  ③程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将执行多次。
  ④ 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。
• 局部性原理体现在以下两个方面：

1）时间局部性

• 程序的某条指令一旦执行，不久后该指令可能再次执行；如果某数据被访问过，则不久后该数据可能再次被访问。产生时间局部性的典型原因是由于程序中存在大量的循环操作。

2）空间局部性

• 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问过的地址，可能集中在一定范围内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。
• 时间局部性通过将进来使用的指令和数据保存到高速缓冲存储器中，并使用高速缓存的层次结构实现。空间局部性通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。
• 虚拟内存技术实际上建立了“内存-外存”的两级存储器结构，利用局部性原理实现高速缓存。

3、虚存的定义

• 基于局部性原理，在程序装入时，将程序的一部分装入内存，而将其余部分留在外存，就可启动程序执行。在程序执行过程中，当所访问的信息不在内存中时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。如此，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟内存。

4、虚存的特征

• 之所以称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后，给用户一种比实际物理内存大得多的存储器。虚拟存储器的大小由计算机的地址结构决定，并不是内存和外存的简单相加。
• 虚拟存储器有多次行、对换性和虚拟性三大主要特征。

1）多次性

• 多次行是指无须在作业运行时一次性地全部装入内存，而允许被分成多次调入内存运行。

2）对换性

• 指无须在作业运行时一直常驻内存，而允许在作业运行过程中，进行换出和换入。

3）虚拟性

• 指从逻辑上扩充内存容量，使用户看到的内存容量远大于实际的内存容量。

5、虚拟内存技术的实现

• 虚拟内存技术允许将一个作业分多次调入内存。采用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的浪费，而且也无法从逻辑上扩大内存容量。因此虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。
• 虚拟内存的实现方式有请求分页存储管理、请求分段存储管理和请求段页式存储管理三种方式。不管哪种方式，都需要一定的硬件支持：
  § 请求分页的页表机制或段表机制，是在纯分页的页表机制或纯分段的段表机制上增加若干项而形成的，作为请求分页或请求分段的数据结构。
  § 缺页中断机构，即每当用户程序所要访问页面尚未调入内存时，便产生缺页中断，以请求 OS 将所缺的页调入内存。
  § 地址变换机构，同样是在纯分页或纯分段地址变换机构的基础上发展形成的。
  除了硬件，还需要一定的软件支持，如用于实现请求调页的软件和实现页面置换的软件。

二、请求分页管理方式

• 请求分页系统是建立在基本分页基础上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。在请求分页系统中，只需将当前需要的分页装入内存便启动运行；而执行过程如果要访问的页面不在内存中，则通过调页功能将其调入，同时置换功能将暂时不用的分页换出到外存中。请求分页是目前最常用的一种实现虚拟存储器的方法。

1、相关硬件支持

• 实现请求分页需要硬件上的支持，主要是页表机制、缺页中断机构以及地址变换机构。

1.1、页表机制

• 请求分页系统中主要数据结构就是页表。其基本作用仍是将用户地址空间中的逻辑地址变换为内存空间的物理地址。由于请求分页系统是调入进程的一部分分页，因此运行过程中必然出现要访问的页面不在内存中，如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此，在请求分页表项中增加了 4 个字段：
  
• 各个字段的含义说明如下：
  § 状态位 P：用于指示该页是否已经调入内存，供程序访问时参考。
  § 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时进行参考。
  § 修改位M：标识该页在调入内存后是否被修改过。
  § 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

1.2、缺页中断机构

• 发生缺页中断时，请求 OS 将所缺页调入内存。此时应将缺页的进程阻塞，待调页完成后再唤醒。若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应的页表项；若此时内存中没有空闲块，则淘汰某页，并且淘汰页若在内存期间被修改过，则要将其写回外存。
• 缺页中断作为中断，同样需要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序、恢复 CPU 环境等几个步骤。但与一般的中断相比，有以下两个明显的区别：
  • 在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部中断。
  • 一条指令在执行期间，可能产生多次缺页中断。

1.3、地址变换机构

• 请求分页系统中的地址变换机构，是在普通分页系统的地址变换机构的基础上，为实现虚拟内存，增加了一些功能而形成的。
  
• 如上图所示，进行地址变换时，先检索快表：
  · 如找到要访问的页，则修改页表项中的访问位，若是写指令还需要重置修改位，然后利用页表项中给出的物理块号和页内地址形成物理地址。
  · 若未找到该页的页表项，则应到内存中去查找页表，再比对页表项中的状态位 P，看该页是否已调入内存，未调入则产生缺页中断，请求把该页调入内存。

三、页面置换算法

• 选择调出页面的算法称为页面置换算法。好的页面置换算法应有较低的页面更换频率，即应将以后不会再访问或以后较长时间内不会再访问的页面先调出。
• 常用的页面置换算法有最佳置换算法、先进先出置换算法、最近最久未使用置换算法和时钟置换算法。

1、最佳置换算法

• 最佳（Optimal，OPT）置换算法选择的被淘汰页面是以后永久不使用的页面，或是在最长未来时间内不再被访问的页面，以保证获得最低的缺页率。但是该算法无法实现，因为目前的技术无法预知一个进程在内存的若干页面中，哪一个页面是未来最长时间内不再被访问的。
• 最佳置换算法通常被用来评价其他算法。
  
• 如上图，发生缺页中断的次数为 9 次，页面置换的次数为 6.

2、先进先出页面置换算法

• 先进先出（FIFO）算法优先淘汰最早进入内存的页面，也就是在内存中驻留时间最久的页面。
• 算法实现简单，只需要把调入内存的页面，根据先后次序链接成队列，设置一个替换指针总是指向最早的页面。但该算符与进程的实际运行规律不相适应，因为在进程中，有些页面经常被访问，比如含有全局变量、常用函数、例程等的页面，FIFO算法不能保证这些页面不被淘汰。
  
• FIFO算法还会产生所分配的物理块数增大而页故障数不减反增的异常现象，这由Belady于1969年发现，因此称为 Belady 异常。只有 FIFO 算法可能出现 Belady 异常，LRU 和 OPT 算法永远不会出现 Belady 异常。
  

3、最近最久未使用置换算法

3.1、最近最久未使用置换算法描述

• Least Recently Used， LRU 算法根据页面调入内存后的使用情况来进行决策的。由于无法预测各个页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此 LRU 算法选择最近最久未使用的页面予以淘汰。
• 该算法赋予每个页面一个访问字段，用来记录自上次访问以来所经历的时间 t，当必须淘汰一个页面时，选择现有页面中 t 值最大的页面进行淘汰。
  

3.2、LRU置换算法的硬件支持

• LRU置换算法虽然是一个比较好的算法，但是要求系统有较多的硬件支持。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用地页面，须有两类硬件地支持：寄存器和栈。

3.2.1、寄存器

• 为每个在内存中地页面配置一个移位寄存器，用于记录某进程在内存中各页地使用情况，可表示为：
  
• 当进程访问某物理块时，要将相应寄存器的 Rn-1 位置成 1.此时，定时信号将每隔一段时间将寄存器右移一位。如果我们将 n 位寄存器的数看作一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
  
• 如上图，某进程在内存中有 8 个页面，为每个页面配置一个 8 位寄存器时的 LRU 访问情况，这里将 8 个页面的序号分别定为 1~8.从图中的表格可以看出，第三个内存页面的 R 值最小，当发生缺页时，首先将它置换出去。

3.2.2、栈

• 利用一个特殊的栈保存当前使用的各个页面的页面号。每当进程访问某页时，便将该页的页面号从栈中移出，将他压入栈顶。因此栈顶始终是最新访问的页面编号，而栈底始终是最近最久未使用的页面号。
• 假设现有一进程所访问的页面号序列为：
  4，7，0，1，0，1，2，1，2，6
• 随着进程的访问，栈中页面号的变换情况如下图：
  
• 在访问页面 6 时发生了缺页，此时页面 4 是最近最久未使用的页面，应将它置换出去。
• LRU 之所以不会出现 Belady 异常，是因为 LRU 算法属于堆栈类算法，而堆栈类算法不可能出现 Belady 异常。FIFO 算法是基于队列实现的，因此会出现 Belady 异常。

4、时钟置换算法

• LRU 算法虽然性能接近于 OPT 算法，但实现起来困难且开销大；FIFO 算法实现简单，但性能差。因此操作系统设计者尝试了很多算法，试图用较小的开销接近 LRU 算法的性能，这类算法都是 CLOCK 算法的变体。因为算法要循环扫描缓冲区，像时钟的指针一样转动，所以称为 CLOCK 算法。

4.1、简单 CLOCK 算法

• 简单 CLOCK 算法给每帧关联一个附加位，称为使用位。当某页首次装入主存时，将该帧的使用位设置为 1；当该页随后再被访问到时，其使用位也被置 1.对于页替换算法，用于替换的候选帧集合可视为一个循环缓冲区，并有一个指针与之关联。当某一页被替换时，该指针被设置成指向缓冲区的下一帧。当需要替换某一页时，操作系统扫描缓冲区，以便查找使用位置为 0 的一帧。每当遇到一个使用位为 1 的帧时，操作系统就将该位置重新置为 0；若这个过程开始时，缓冲区中所有帧的使用位都为 0，则选择遇到的第一个帧替换；若所有帧的使用位都为 1，这指针在缓冲区中完整的循环一周，把所有使用位都置 0，并停留在最初的位置上，替换该帧中的页。由于该算法循环检查各页面的情况，因此称 CLOCK 算法，又称最近未用（Not Recently Use，NRU）算法。

4.2、改进型 CLOCK 算法

• CLOCK 算法的性能比较接近 LRU 算法，而通过增加使用的位数目，可以使得 CLOCK 算法更高效。在使用位的基础上再增加一个修改位，则得到改进型 CLOCK 算法。如此，每帧都处于以下 4 种情况之一：

  ① 最近未被访问，也未被修改（u=0，m=0）
  ② 最近被访问，但未被修改（u=1，m=0）
  ③ 最近未被访问，但被修改过（u=0，m=1）
  ④ 最近被访问，被修改（u=1，m=1）

• 算法执行如下操作步骤：

• 1）从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧（u=0，m=0）用于替换。

• 2）若第1）步失败，则重新扫描，查找（u=0，m=1）的帧，选择第一个这样的帧用于替换。在这个扫描过程种，对每个跳过的帧，把它的使用位置 0.

• 3）若第2）步失败，则指针将回到最初位置，且集合中所有帧的使用位都为 0.重复第1）步，并且若有必要，重复第2）步，以便找到可以替换的帧。

• 改进型的 CLOCK 算法优于简单 CLOCK 算法的地方就在于替换时首选没有变化的页。由于修改过的页在替换之前必须写回，因而这样做会节省时间。

• 操作系统中任何经过优化而有效的页面置换算法都有一个原则：

• 尽可能保留曾经使用过的页面，而淘汰未使用的页面，认为这样可以在总体上减少换页次数。

• CLOCK 算法只考虑是否被访问过，因此被访问过的当然尽可能留下，未使用过的就被淘汰；而改进型 CLOCK 算法对使用过的页面又进行了细分：修改过和未修改，因此，若有未使用过的页面，则当然首先将它换出去，但是若没有未使用过的，则优先将未修改过的置换出去。

• 注意：现假设，系统准备用页面a替换页面b，而页面b原先占有的 x 号页框（物理块），那么页面a换入内存后也放在 x 号物理块中。

四、页面分配策略

1、驻留集大小

• 对分页式虚拟内存，由于不需要将进程的所有页调入主存，因此操作系统需要决定读取多少页，即决定给特定的进程分配几个页框。
• 给进程分配的物理页框的集合就是这个进程的驻留集。驻留集需要考虑以下几点：
  ① 分配给一个进程的存储量越小，任何时候驻留在主存中的进程数就越多，从而可以提高处理机的时间利用效率。
  ② 若一个进程在主存中的页数过少，则尽管有局部性原理，页错误率仍然会相对较高。
  ③ 若页数过多，则由于局部性原理，给特定的进程分配更多的主存空间对该进程的错误率没有明显的影响。

2、分配策略

• 基于上面提到的驻留集的考虑因素，现代操作系统通常采用固定分配局部置换策略、可变分配全局置换策略和可变分配局部置换三种策略。

1）固定分配局部置换策略

• Fixed Allocation，Local Replacement。
• 指基于进程的类型—交互型或批处理型等，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个进程运行期间都不改变。若运行中进程发生缺页，则只能从该进程在内存中的 n 个页面中选出一个页换出，然后调入需要的页面。
• 实现该策略的难点在于：该给每个进程分配多少个物理块？太少时，会频繁出现缺页中断，降低系统吞吐量；太多时，又必然使内存中驻留的进程数目减少，进而造成 CPU 空闲或其他资源空闲，而且实现进程对换时，会花费更多的时间。

2）可变分配全局置换

• Variable Allocation，Global Replacement。
• 是一种先对容易实现的物理块分配和置换策略。采用该策略时，先为系统中的每个进程分配一定数目的物理块，操作系统自身也保持一个空闲物理块队列。当某进程发生缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的页装入其中。如此，凡是产生缺页的进程，都将获得新的物理块；仅当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一页调出，该页可能是系统中任一进程的页，自然使得那个进程的物理块减少，进而缺页率增加。
• 此策略比固定分配局部置换灵活，可以动态增加进程的物理块，但也存在弊端：盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降。

3）可变分配局部置换

• Variable Allocation，Local Replacement。
• 该策略为每个进程分配一定数目的物理块，但当进程发生缺页时，只允许从该进程在内存中的页面中挑选出一页换出，故而不影响其他进程的运行。若进程运行中频繁发生缺页中断，则系统须再为该进程分配若干附加的物理块，直到该进程的缺页率减少到适当程度为止；反之，若进程运行中缺页率特别低，则可以适当减少分配该进程的物理块，但不应引起其缺页率明显增加。
• 该策略不仅能动态增加进程的物理块数量，还可动态减少进程的物理块数量，在保证进程不会过多地调页的同时，也保证了系统多道程序并发能力，当然也需要更复杂的实现和更大的开销，但对比频繁地换入/换出所浪费地计算机资源，这种牺牲是值得的。

3、调页时机

• 为确定系统将进程运行时所缺的页面调入内存的时机，可采取预调页策略或请求调页策略。

1）预调页策略

• 根据局部性原理，一次调入若干相邻的页可能比一次调入一页更高效。但如果调入的一批页面中的大多数都未被访问，则又是低效的。因此需要采用一种以预测为基础的预调页策略，将预计在接下来便会访问到的页面预先调入内存，但目前预调页的成功率仅为 50%。
• 因此该策略主要用于进程的首次调入，由程序员指出应先调入哪些页。

2）请求调页策略

• 进程运行过程中需要访问的进程不在内存而提出请求，由系统将所需的页面调入内存。由这种策略调入的页一定会被访问，且这种策略易于实现，因此目前大多数的虚拟存储器都采用此策略。
• 此策略的缺点是：每次调入一页，故须花费较大的系统开销，增加了磁盘的I/O 的启动频率。
• 预调入实际是运行前的调入，请求调入是运行期间的调入。故而一般情况下，两种策略可以同时使用。

4、自何处调页

• 请求分页系统中，外存分为存放文件的文件区和存放对换页面的对换区。对换区通常是连续分配方式，而文件区则是离散分配方式；因此对换区的磁盘 I/O 速度比文件区的快。故而进行调页时可能发生如下三种情况：
• ① 系统拥有足够的对换空间：
  可以全部从对换区调入所需的页面，以提高换页速度；不过，需要事先即进程运行前，需要将与进程有关的文件从文件区复制到对换区。
• ② 系统缺少足够的对换空间：
  凡不会被修改的文件都直接从文件区调入；而换出这些页面时，由于未被修改而不必再将它们换出。但对于那些可能被修改的部分，在将它们换出时须调到对换区，以后需要时再从对换区调入，这是由于读的速度比写的速度快。
• ③ UNIX 方式
  与进程相关的文件都放在文件区，因此凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被存放对换区，因此在下次调入时，应从对换区调入。由于 UNIX 系统允许页面共享，因此，某进程所请求的页面若已经被其他进程调入内存，则无须再从对换区调入。

五、抖动和工作集

1、何为抖动

• 页面置换过程中，若发生刚刚换出的页面马上又要换入主存，刚刚换入主存的页面马上又要移出主存，这种频繁的页面调度行为称为抖动或颠簸，这是一种很糟糕的情况。若一个进程再换页上用的时间多于执行时间，则这个进程就在颠簸。

2、发生抖动的原因

• 发生抖动的主要原因是：某个进程频繁访问的页面数目高于可用的物理页帧数目。虚拟内存技术可在内存中保留更多的进程以提高系统效率，在稳定状态，几乎所有主存空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程。然而，如果管理不当，那么处理机大部分时间都将用于交换块，因此会大大降低系统效率。

3、工作集

• 工作集是指在某段时间间隔内，进程要访问的页面集合。基于局部性原理，可以用最近访问过的页面来确定工作集。
• 一般来说，工作集可由时间和工作集窗口大小来确定。例如：
• 某进程对页面的访问次序：
  
• 假设系统为该进程设定的工作集窗口大小为 5，则在t1 时刻，进程工作集为{2，3，5}，t2 时刻则是 {1，2，3，4}。
• 实际应用中，工作集窗口会设置得很大，即对于局部性好的程序，工作集大小一般会比工作集窗口小的很多。

4、工作集的用处

• 工作集反映了进程接下来一段时间内很有可能会频繁访问的页面集合，因此若分配给进程的物理块大小小于工作集大小，则该进程就很有可能频繁换页，为防止这种抖动现象，分配给进程的物理块数—驻留集要大于工作集大小。

5、工作集模型原理

• 让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的驻留集。落在工作集内的页面需要调入驻留集，而落在工作集外的页面可从驻留集中换出。若还有空闲物理块，则可以再调入一个进程到内存以增加多道程序数。若所有进程的工作集之和超过了可用物理块数，则操作系统会暂停一个进程，将其页面调出并分配其物理块给其他进程，防止出现抖动现象。

转载地址：http://kqqgn.baihongyu.com/