26考研——内存管理_虚拟内存管理（3）

408答疑

二、虚拟内存管理

1、虚拟内存的基本概念

• 传统存储管理方式的特征
  • 上一节讨论的各种内存管理策略都是为了同时将多个进程保存在内存中，以便允许进行多道程序设计。它们都具有以下两个共同的特征：
    1. 一次性。作业必须一次性全部装入内存后，才能开始运行。这会导致两个问题：① 当作业很大而不能全部被装入内存时，将使该作业无法运行；② 当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序并发度的下降。
    2. 驻留性。作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中的进程会因等待 I/O 而被阻塞，可能处于长期等待状态。
  • 由以上分析可知，许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。
• 局部性原理
  • 要真正理解虚拟内存技术的思想，首先必须了解著名的局部性原理。从广义上讲，快表、页高速缓存及虚拟内存技术都属于高速缓存技术，这个技术所依赖的原理就是局部性原理。局部性原理既适用于程序结构，又适用于数据结构。局部性原理表现在以下两个方面：
    1. 时间局部性。程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。产生的原因是程序中存在着大量的循环操作。
    2. 空间局部性。一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。
  • 时间局部性通过将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构实现。空间局部性通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上建立了 $“内存-外存”$ 的两级存储器结构，利用局部性原理实现高速缓存。
• 虚拟存储器的定义和特征
  • 基于局部性原理，在程序装入时，仅需将程序当前运行要用到的少数页面（或段）装入内存而将其余部分暂留在外存，便可启动程序执行。
  • 在程执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序，这个过程就是请求调页（或请求调段）功能。
    • 当内存空间不够时，由操作系统负责将内存中暂时用不到的信息换出到外存，从而腾出空间存放将要调入内存的信息，这个过程就是页面置换（或段置换）功能。
    • 这样，系统好像为用户提供了一个比实际内存容量大得多的存储器，称为虚拟存储器。
  • 之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入、请求调入和置换功能后（均对用户透明），给用户的感觉是好像存在一个比实际物理内存大得多的存储器。但容量大只是一种错觉，是虚的。
  • 虚拟存储器有以下三个主要特征：
    1. 多次性。无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。以后每当要运行到尚未调入的那部分程序或数据时，再将它们调入。多次性是虚拟存储器最重要的特征。
    2. 对换性。在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将那些暂不使用的程序和数据从内存调至外存的对换区（换出），待以后需要时再将它们从外存调至内存（换进）。正是由于对换性，才使得虚拟存储器得以正常运行。
    3. 虚拟性。从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际容量。这是虚拟存储器所表现出的最重要特征，也是实现虚拟存储器的最重要目标。
• 虚拟内存技术的实现
  • 虚拟内存技术允许将一个作业分多次调入内存。采用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。
  • 虚拟内存的实现有三种方式：① 请求分页存储管理。② 请求分段存储管理。③ 请求段页式存储管理。
  • 不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：
    • 一定容量的内存和外存。
    • 页表机制（或段表机制），作为主要的数据结构。
    • 中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。
    • 地址变换机构，逻辑地址到物理地址的变换。

2、请求分页管理方式

2.1、相关概念

• 请求分页系统建立在基本分页系统的基础之上，为支持虚拟存储器功能而增加了请求调页和页面置换功能。在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可启动作业运行。
  • 在作业执行过程中，当所访问的页面不在内存时，再通过请求调页功能将其从外存调入内存；
  • 当内存空间不够时，通过页面置换功能将内存中暂时用不到的页面换出到外存。
• 为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。

2.2、页表机制

• 相比于基本分页系统，在请求分页系统中，为了实现请求调页功能，操作系统需要知道每个页面是否已调入内存；若未调入，则还需要知道该页在外存中的存放地址。

• 为了实现页面置换功能，操作系统需要通过某些指标来决定换出哪个页面；对于要换出的页面，还要知道其是否被修改过，以决定是否写回外存。为此，在请求页表项中增加了 4 个字段，如下图所示。

• 增加的4个字段说明如下：

  • 状态位 P。标记该页是否已调入内存，供程序访问时参考。
  • 访问字段 A。记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考。
  • 修改位 M。标记该页在调入内存后是否被修改过，以决定换出时是否写回外存。
  • 外存地址。记录该页在外存的存放地址，通常是物理块号，供调入该页时参考。

2.3、缺页中断机构

• 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，请求操作系统的缺页中断处理程序处理。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
• 若内存中有空闲页框，则为进程分配一个页框，将所缺页面从外存装入该页框，并修改页表中的相应表项，若内存中没有空闲页框，则由页面置换算法选择一个页面淘汰，若该页在内存期间被修改过，则还要将其写回外存；未被修改过的页面不用写回外存。
• 缺页中断作为中断，同样要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序、恢复 CPU 环境等几个步骤。但与一般的中断相比，它有以下两个明显的区别：
  • 在指令执行期间而非一条指令执行完后产生和处理中断，属于内部异常。
  • 一条指令在执行期间，可能产生多次缺页中断。

2.4、地址变换机构

• 在基本分页系统地址变换机构的基础上，为实现虚拟内存，增加了产生和处理缺页中断，及从内存中换出一页的功能，请求分页系统中的地址变换过程如下图所示。

• 请求分页系统的地址变换过程如下：

  1. 先检索快表，若命中，则从相应表项中取出该页的物理块号，并修改页表项中的访问位，以供置换算法换出页面时参考。对于写指令，还需要将修改位置为 1。
  2. 若快表未命中，则要到页表中査找，若找到，则从相应表项中取出物理块号，并将该页表项写入快表，若快表已满，则需采用某种算法替换。
  3. 若在页表中未找到，则需要进行缺页中断处理，请求系统将该页从外存换入内存，页面被调入内存后，由操作系统负责更新页表和快表，并获得物理块号。
  4. 利用得到的物理块号和页内地址拼接形成物理地址，用该地址去访存。

3、页框分配

• 驻留集大小
  • 对于分页式的虚拟内存，在进程准备执行时，不需要也不可能将一个进程的所有页都读入主存。因此，操作系统必须决定读取多少页，即决定给特定的进程分配几个页框。
  • 给一个进程分配的页框的集合就是这个进程的驻留集。需要考虑以下两点：
    1. 驻留集越小，驻留在内存中的进程就越多，可以提高多道程序的并发度，但分配给每个进程的页框太少，会导致缺页率较高，CPU需耗费大量时间来处理缺页。
    2. 驻留集越大，当分配给进程的页框超过某个数目时，再为进程增加页框对缺页率的改善是不明显的，反而只能是浪费内存空间，还会导致多道程序并发度的下降。
• 内存分配策略
  • 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。
  • 在进行置换时，也可采取两种策略，即全局和局部置换。
  • 于是可组合出下面三种适用的策略：
    1. 固定分配局部置换
       • 为每个进程分配固定数目的物理块，在进程运行期间都不改变。
       • 所谓局部置换，是指若进程在运行中发生缺页，则只能从分配给该进程在内存的页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。
       • 实现这种策略时，难以确定应为每个进程分配的物理块数目，太少会频繁出现缺页中断，太多又会降低 CPU 和其他资源的利用率。
    2. 可变分配全局置换
       • 先为每个进程分配一定数目的物理块，在进程运行期间可根据情况适当地增加或减少。
       • 所谓全局置换，是指若进程在运行中发生缺页，则系统从空闲物理块队列中取出一块分配给该进程，并将所缺页调入。这种方法比固定分配局部置换更加灵活，可以动态增加进程的物理块，但也存在弊端，如它会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降。
    3. 可变分配局部置换
       • 为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，因此不会影响其他进程的运行。
       • 若进程在运行中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直至该进程的缺页率趋于适当程度；反之，若进程在运行中的缺页率特别低，则可适当减少分配给该进程的物理块，但不能引起其缺页率的明显增加。
       • 这种方法在保证进程不会过多地调页的同时，也保持了系统的多道程序并发能力。当然它需要更复杂的实现，也需要更大的开销，但对比频繁地换入/换出所浪费的计算机资源，这种牺牲是值得的。

全局置换意味着一个进程拥有的物理块数量必然会变，因此不可能与固定分配组合。

• 物理块调入算法：采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述几种算法。
  1. 平均分配算法，将系统中所有可供分配的物理块平均分配给各个进程。
  2. 按比例分配算法，根据进程的大小按比例分配物理块。
  3. 优先权分配算法，为重要和紧迫的进程分配较多的物理块。通常采取的方法是将所有可分配的物理块分成两部分：一部分按比例分配给各个进程；一部分则根据优先权分配。
• 调入页面的时机：为确定系统将进程运行时所缺的页面调入内存的时机，可采用以下两种调页策略：
  1. 预调页策略。根据局部性原理，一次调入若干个相邻的页面会比一次调入一页更高效。但若提前调入的页面中大多数都未被访问，则又是低效的。因此，可以预测不久之后可能被访问的页面，将它们预先调入内存，但目前预测成功率仅约 $50\%$。因此这种策略主要用于进程的首次调入，由程序员指出应先调入哪些页。
  2. 请求调页策略。进程在运行中需要访问的页面不在内存，便提出请求，由系统将其所需页面调入内存。由这种策略调入的页一定会被访问，且比较易于实现，因此目前的虚拟存储器大多采用此策略。其缺点是每次仅调入一页，增加了磁盘 I/O 开销。

预调页实际上就是运行前的调入，请求调页实际上就是运行期间的调入。

• 从何处调入页面
  • 请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区，也称交换区。
  • 对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘 I/O 速度比文件区的更快。这样，当发生缺页请求时，系统从何处将缺页调入内存就分为三种情况：
    1. 系统拥有足够的对换区空间。可以全部从对换区调入所需页面，以提高调页速度。为此在进程运行前，需将与该进程有关的文件从文件区复制到对换区。
    2. 系统缺少足够的对换区空间。凡是不会被修改的文件都直接从文件区调入；当换出这些页面时，由于它们不会被修改而不必再换出。但对于那些可能被修改的部分，在将它们换出时必须放在对换区，以后需要时再从对换区调入（因为读比写的速度快）。
    3. UNIX 方式。与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入。曾经运行过但又被换出的页面，由于是放在对换区，因此在下次调入时应从对换区调入进程请求的共享页面若被其他进程调入内存，则不需要再从对换区调入。
• 如何调入页面
  • 当进程所访问的页面不在内存中时（存在位为 0），便向 CPU 发出缺页中断，中断响应后便转入缺页中断处理程序。
  • 该程序通过查找页表得到该页的物理块，此时，若内存未满，则启动盘 I/O，将所缺页调入内存，并修改页表；若内存已满，则先按某种置换算法从内存中选出一页准备换出。
  • 若该页未被修改过（修改位为 0），则不需要将该页写回磁盘；但是，若该页已被修改（修改位为 1），则必须将该页写回磁盘，然后将所缺页调入内存，并修改页表中的相应表项，置其存在位为 1。调入完成后，进程就可利用修改后的页表形成所要访问数据的内存地址。

4、页面置换算法

4.1、相关概念

• 进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页，换出到外存。选择调出哪个页面的算法就称为页面置换算法。
• 页面的换入、换出需要磁盘 I/O，开销较大，因此好的页面置换算法应该追求更低的缺页率。
• 常见的页面置换算法有以下四种。

4.2、最佳（OPT）置换算法

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

4.4、最近最久未使用（LRU）置换算法

4.5、时钟（CLOCK）置换算法

5、抖动和工作集

• 抖动
  • 在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出内存，这种频繁的页面调度行为称为抖动或颠簸。
  • 系统发生抖动的根本原因是，分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页，必须请求系统将所缺页面调入内存。显然，对磁盘的访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，进而导致发生 CPU 利用率急剧下降并趋于零的情况。
  • 抖动是进程运行时出现的严重问题，必须采取相应的措施解决它。由于抖动的发生与系统为进程分配物理块的多少（即驻留集）有关，于是又提出了关于进程工作集的概念。
• 工作集
  • 工作集是指在某段时间间隔内，进程要访问的页面集合。一般来说，工作集 W 可由时间 t 和工作集窗口尺寸 $\Delta$ 来确定。
    • 例如，某个进程对页面的访问次序如上图所示。
    • 假设工作集窗口尺寸 $\Delta$ 设置为 5，则在 $t_1$ 时刻，进程的工作集为 { 2 , 3 , 5 } \{2,3,5\} {2,3,5}，$t_2$时刻，进程的工作集为 { 1 , 2 , 3 , 4 } \{1,2,3,4\} {1,2,3,4} 。
  • 实际应用中，工作集窗口会设置得很大，对于局部性好的程序，工作集大小般会比工作集窗口 $\Delta$ 小很多。工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，因此驻留集大小不能小于工作集，否则进程在运行过程中会频繁缺页。

6、页框回收

7、内存映射文件

• 内存映射文件（Memory-Mapped Filcs）是操作系统向应用程序提供的一个系统调用，它与虚拟内存有些相似，在磁盘文件与进程的虚拟地址空间之间建立映射关系。

• 进程通过该系统调用，将一个文件映射到其虚拟地址空间的某个区域，之后就用访问内存的方式读写文件。这种功能将一个文件当作内存中的一个大字符数组来访问，而不通过文件 I/O 操作来访问，显然这更便利。磁盘文件的读出/写入由操作系统负责完成，对进程而言是透明的。当映射进程的页面时，不会实际读入文件的内容，而只在访问页面时才被每次一页地读入。当进程退出或关闭文件映射时，所有被改动的页面才被写回磁盘文件。

• 进程可通过共享内存来通信，实际上，很多时候，共享内存是通过映射相同文件到通信进程的虚拟地址空间来实现的。当多个进程映射到同一个文件时，各进程的虚拟地址空间都是相互独立的，但操作系统将对应的这些虚拟地址空间映射到相同的物理内存（用页表实现），如下图所示。

• 一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时，就能立刻看到上一个进程写操作的结果。

• 由此可见，内存映射文件带来的好处主要是：① 使程序员的编程更简单，已建立映射的文件，只需按访问内存的方式进行读写；② 方便多个进程共享同一个磁盘文件。

8、虚拟存储器性能影响因素

• 缺页率是影响虚拟存储器性能的主要因素，而缺页率又受到页面大小、分配给进程的物理块数页面置换算法以及程序的编制方法的影响。
• 根据局部性原理，页面较大则缺页率较低，页面较小则缺页率较高。页面较小时，一方面减少了内存碎片，有利于提高内存利用率；另一方面，也会使每个进程要求较多的页面，导致页表过长，占用大量内存。页面较大时，虽然可以减少页表长度，但会使页内碎片增大。
• 分配给进程的物理块数越多，缺页率就越低，但是当物理块超过某个数目时，再为进程增加一个物理块对缺页率的改善是不明显的。可见，此时已没有必要再为它分配更多的物理块，否则也只能是浪费内存空间。只要保证活跃页面在内存中，保持缺页率在一个很低的范围即可。
• 好的页面置换算法可使进程在运行过程中具有较低的缺页率。选择 LRU、CLOCK 等置换算法，将未来有可能访问的页面尽量保留在内存中，从而提高页面的访问速度。
• 写回磁盘的频率。换出已修改过的页面时，应当写回磁盘，如果每当一个页面被换出就将它写回磁盘，那么每换出一个页面就需要启动一次磁盘，效率极低。为此在系统中建立一个已修改换出页面的链表，对每个要被换出的页面（已修改），可以暂不将它们写回磁盘，而将它们挂在该链表上，仅当被换出页面数达到给定值时，才将它们一起写回磁盘，这样就可显著减少磁盘 I/O 的次数，即减少已修改页面换出的开销。此外，若有进程在这批数据还未写回磁盘时需要再次访问这些页面，则不需从外存调入，而直接从已修改换出页面链表上获取，这样也可以减少页面从磁盘读入内存的频率，减少页面换进的开销。
• 编写程序的局部化程度越高，执行时的缺页率就越低。若存储采用的是按行存储，则访问时就要尽量采用相同的访问方式，避免按列访问造成缺页率过高的现象。

三、参考资料

鲍鱼科技课件

b站免费王道课后题讲解:

网课全程班:

26王道考研书