Storage Management PartⅢ

虚拟存储器 Virtual Memory

虚拟存储器的引入

问题的提出
一个程序要求的存储容量超过整个内存空间
有大量的作业需要装入内存运行而内存空间不足

解决方案
从物理上增加内存容量。但这会增加系统成本，并且增加是有限的
从逻辑上增加内存容量。这正是虚拟存储技术所要解决的主要问题。

常规存储器管理方式的特征
“一次性”: 要求将一个作业全部装入内存才能运行，
1）大作业无法运行。
2）限制作业并发执行的程度。
“驻留性”: 作业装入后一直驻留内存直到作业完成。
内存中存在一些已无用的、或暂时不用的程序或数据，浪费内存空间。
一次性和驻留性严重降低内存利用率，减少系统吞吐量。
内存的扩充方法

1. 物理扩充：
   增加硬件投入，受机器自身和成本的限制。
2. 逻辑扩充：

• 覆盖（overlay）应用程序手动把需要的指令和数据保存在内存中；解决了“一次性”问题。
• 对换（swapping）操作系统自动把暂时不能执行的程序保存到外存中;解决了“驻留性”问题。
• 虚拟存储 在有限容量的内存中，自动装入更多更大的程序

局部性原理 Principle of Locality

程序执行的局部性原理：程序的执行总是呈现局部性。即在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。
因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。

局限性又表现在下述两个方面：

1. 时间局限性
   如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。
   产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。
2. 空间局限性
   一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。
   程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

不同程序编写方法的局部性特征

页面大小为 4K，分配给每个进程的物理页框数为 1。在一个进程中，定义了如下的二维数组int A[1024][1024]，该数组按行存放在内存，每一行放在一个页面中。

// 程序编写方法1：for (j = 0; j < 1024; j++)for (i = 0; i < 1024; i++)    A[i][j] = 0;// 程序编写方法2：for (i=0; i<1024; i++)for (j=0; j<1024; j++)    A[i][j] = 0;

页号    页内数据0000    a0,0         a0,1        a0,2   ……………………        a0,10230001    a1,0         a1,1        a1,2   ……………………        a1,1023        ……………………………        ……………………………1023    a1023,0      a1023,1   ……………………....…......... a1023,1023

编写方式 1 发生了大量的缺页中断，因为程序按行存放，每次访问都会跨页，共计$1024 \times 1024 = ^{24}$次缺页中断。
编写方式 2 发生了较少的缺页中断，共计$2^{10}$次缺页中断。

缺页中断（Page Fault）是计算机操作系统中的一种中断或异常，当程序访问一个页面时，如果这个页面已经在物理内存中，那么就可以直接读取或者写入。但是，如果这个页面在虚拟内存中，而并没有加载到物理内存中，那么就会发生缺页中断。

虚拟存储器概述

定义

虚拟存储器（Virtual Memory）是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定
其运行速度接近于内存速度，而成本却又接近于外存。
虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。

• 当进程运行时，先将当前要运行的部分程序装入内存，其他部分暂留外存；
• 当要执行的指令不在内存时，处理器发生中断，通知操作系统将所缺部分从外存调入内存，保证程序继续执行；
• 当内存不足时，允许程序部分换入、换出。

虚拟存储器的基本工作情况

1. 基于局部性原理。一个作业运行前，仅将那些当前要运行的页面（段）装入内存启动运行，其余暂在外存。
2. 若运行所需页面（段）不在内存，则利用请求调页（段）功能将其调入内存。
3. 若此时内存满，则利用置换功能，将内存中暂时不用的部分页面（段）调至外存，再将所需页面（段）调入。
4. 这样，可实现大程序在小内存中运行，也可实现内存中同时装入更多的进程并发执行。

虚存容量

虚拟存储器虽然给用户提供了特大地址空间，但其容量不是无限大，主要受两个方面的限制：

1. 指令中表示地址的字长：这是由 CPU 的架构决定的。例如，如果 CPU 的有效地址长度为 32 位，那么它能够表示的地址空间最大为$2^{32}$，也就是 4GB。这意味着虚拟内存的最大容量为 4GB。这与物理内存的大小无关，即使物理内存小于 4GB，虚拟内存依然可以达到 4GB。但是，如果物理内存大于 4GB，那么超出 4GB 的部分将无法被 32 位的 CPU 编址。
2. 外存的容量（对换区）：虚拟内存的另一个部分存储在硬盘的交换区中。如果硬盘的空间有限，那么虚拟内存的容量也会受到限制。即使 CPU 可以支持更大的虚拟内存，如果硬盘空间不足，那么虚拟内存的实际可用空间也会受到限制。

虚拟存储器的特征

虚拟存储器具有以下主要特征：

1. 多次性 多次性是指一个作业被分成多次调入内存运行。
2. 对换性 对换性是指作业的运行过程中进行换进、换出。换进和换出能有效地提高内存利用率。
3. 虚拟性 虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

虚拟性是以多次性和对换性为基础的；而多次性和对换性又必须建立在离散分配的基础上。

虚拟存储管理与对换技术的区别

虚拟存储器的实现方法

请求分页系统

它是在纯分页系统的基础上增加了请求调页、页面置换两大功能所形成的页式虚拟存储系统。为了实现请求调页、页面置换两大功能，系统必须提供如下的硬件支持：

1. 请求分页的页表机制。
2. 缺页中断机构。
3. 地址变换机构。

此外，实现请求调页、页面置换两大功能还需得到 OS 的支持。

请求分段系统

它是在纯分段系统的基础上增加了请求调段、分段置换两大功能所形成的段式虚拟存储系统。为了实现请求调段、分段置换两大功能，系统必须提供如下的硬件支持：

1. 请求分段的段表机制。
2. 缺段中断机构。
3. 地址变换机构。

此外，实现请求调段、分段置换两大功能还需得到 OS 的支持。

段页式虚拟系统

目前，许多虚拟存储管理系统是建立在段页式系统的基础上的，通过增加了请求调页、页面置换两大功能所形成的段页式虚拟存储系统。
如：Intel 80386 处理机便支持段页式虚拟存储系统。

抖动 Thrashing

当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存。如果被交换出去的页面或段很快将被进程使用，则又需要将其换入内存。
如果系统花费大量的时间把程序和数据频繁地换入和换出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。
根本原因：选择的页面或段不恰当。

请求分页存储管理方式 Demand Paging

原理及实现

工作原理

作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由 OS 将其从辅存调入主存，如果内存无空块，则根据某种算法选择一个页淘汰以便装入新的页面。
利用这种方法，可使更多的作业处于就绪状态，且能支持比主存容量大的作业在系统中运行。从而提高存储空间利用率。
为了实现请求调页、页面置换两大功能，系统必须提供如下的硬件支持：

1. 请求分页的页表机制。
2. 缺页中断机构。
3. 地址变换机构。

页表机制 Page Table

在虚拟存储系统中的所有的页表，其页描述子有了新的扩充，这是进行地址变换机构所必须的，增加四个信息标识位。

1. 状态位/存在位D：用于说明该页是否已调入内存，供程序访问时参考；
   D=0，该页不在内存;D=1，该页在内存
2. 访问位A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。
   A=0，该页未被访问;A=1，该页被访问
3. 修改位M：用于表示该页在调入内存后是否被修改过，也是提供给置换算法在换出页面时是否将该页面写回外存作参考。
   M=0，该页在内存中未被修改;M=1，该页在内存中已经被修改
4. 外存地址：用于指出该页在外存上的地址，供调入该页时使用。

缺页中断机构 Page Fault Interrupt

由上述页表机制知道，状态位记录了访问页面是否在内存。在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断，也称为缺页故障。OS 接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。
缺页中断是一种特殊的中断，与一般中断相比，主要表现为：

• 在指令执行期间产生和处理中断信号。通常，CPU 只能在指令之间接受中断；然而，一个缺页中断要求在指令执行中间得到服务，即发现所要访问的指令或数据不在内存时产生缺页中断并处理。
• 再则，一条指令可能引起多次不同的页面故障。
  例如COPY A,B,指令本身跨了两个页面,数据 A 和 B 各自跨了两个页面,这条指令的执行需要访问六个不同的页面，对它们的访问都可能引起缺页中断,最多可能引起 6 次缺页中断(每个页面都不在内存中)

由于缺页中断的独特性，系统中需要提供硬件寄存器或其它机构，在出现页面故障时，保存部分完成的指令的状态。此外，还需要使用一条特殊的返回指令，确保在出现缺页中断处恢复该指令的处理。

缺页中断处理过程

1. 操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；
2. 操作系统通知处理机从外存读取指定的页面；
3. 处理机激活 I/O 设备；
4. 检查内存有无足够的空闲空间装入该页面？若有，转（6），否则，执行（5）；
5. 利用页面置换算法，选择内存中的某个页面，换出内存；
6. 将指定页面从外存装入内存；
7. 更新该进程的页表；
8. 更新快表；
9. 计算物理地址。

地址变换机构 Address Translation

内存分配策略和分配算法

在为进程分配物理块时，又将涉及到这样三个问题：

• 确定进程能正常运行所需的最少物理块数；
• 为每个进程分配的物理块，其数目是固定的还是可变的；
• 对各进程所分配的物理块数，是采取平均分配算法还是根据进程的大小按比例予以分配等。

最小物理块数的确定
显然，给每个进程所分配物理块数目越少，则进程执行中的缺页率越高，进程的执行速度也减慢。为使进程能有效地工作，应为它分配一定数目的物理块。
最小物理块数：是指能保证进程正常运行所需的最少物理块数。若系统为某进程所分配的物理块数少于此值时，进程将无法运行。
进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。

例：对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为 2。如果该机器允许间接寻址时，则至少要求有物理块数为 3。对于前面所介绍的在缺页中断机构中要发生 6 次中断的情况，至少要为每个进程分配 6 个物理块，以装入 6 个页面。

物理块的分配策略

1. 固定分配局部置换 Fixed Allocation，Local Replacement
2. 可变分配全局置换 Variable Allocation，Global Replacement
3. 可变分配局部置换 Variable Allocation， Local Replacement

1. 固定分配局部置换
   为每个进程分配一定数目的物理块，在整个运行期间都不再改变。
   实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。
   若太少，会频繁地出现缺页中断，降低了系统的吞吐量；
   若太多，又必然使内存中驻留的进程数目减少，进而可能造成 CPU 空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。
2. 可变分配全局置换 （常用方式）
   在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而 OS 自身也保持一个空闲物理块队列。
   当某进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中。
   这样，凡产生缺页（中断）的进程，都将获得新的物理块；
   仅当空闲物理块队列中的物理块用完时，OS 才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。
3. 可变分配局部置换
   为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。
   在进程运行过程中统计进程的缺页率，如果缺页率高，则为其增加一定的内存页，否则适当减少其内存的页面数。
   当需要置换时只从本进程的内存页中选择，但此方式实现复杂，对进程的缺页情况的统计需要额外的开销。

物理块的分配算法

在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个进程，可采取下述几种方法。

1. 平均分配算法
   将系统中所有可供分配的物理块，平均分配给各个进程。
   例：当系统中有 100 个物理块，有 5 个进程在运行时，每个进程可分得 20 个物理块。如有一个进程其大小为 200 页，只分配给它 20 个块，这样，它必然会有很高的缺页率；而另一个进程只有 10 页，却有 10 个物理块闲置未用。
   这种方式貌似公平，但实际上是不公平的。因为，它并未考虑到各进程本身的大小。
2. 按比例分配算法
   根据进程的大小按比例分配物理块的算法。
   例：系统中共有 n 个进程，每个进程的页面数为$S_i$，则系统中各进程页面数的总和为：
   $S = \sum_{i=1}^{n} S_i$
   又假定系统中可用的物理块总数为 m，则每个进程所能分到的物理块数为$b_i$，将有：
   $b_i = \frac{S_i}{S} \times m$
   b 应该向上取整，它必须大于最小物理块数。
3. 考虑优先权的分配算法
   通常采取的方法是把内存中可供分配的所有物理块分成两部分：
   一部分按比例地分配给各进程；
   另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。
   在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配物理块。

调页策略

解决的问题：

• 系统应当在何时把一个页面装入内存？
• 从何处调入页面？
• 页面调入过程？
• 页面置换算法？

装入时机

系统应当在何时把一个页面装入内存？

• 预调页 (Prepaging)
• 请求调页 (Demand Paging)

可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。
处理过程：

• 当进程创建时，预先为进程装入多个页面。
• 缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。
• 若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率。预调页的成功率仅约 50％。

请求调页：仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。
当进程刚开始执行时，由于预先未装入进程的页面，故需要频繁地申请装入页面。执行一段时间以后，进程的缺页率将下降。
采用请求调页方式，磁盘 I/O 的启动频率较高，系统的开销较大。

从何处调入页面

在请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。
通常，由于对换区是采用连续分配方式，而文件区是采用离散分配方式，故对换区的磁盘 I/O 速度比文件区的高。
这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况。

1. 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页的速度。
2. 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；
   • 而当换出这些页面时，由于它们未被修改而不必再将它们换出到对换区，以后再调入时，仍从文件区直接调入。
   • 但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。
3. UNIX 方式。由于与进程有关的文件都放在文件区，应从文件区调入。故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。

页面调入过程

1. 每当程序所要访问的页面未在内存时，便向 CPU 发出一缺页中断。
2. 中断处理程序首先保留 CPU 环境，分析中断原因后，转入缺页中断处理程序。
3. 如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果此页已被修改，则必须将它写回磁盘。
4. 然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。
5. 形成所要访问数据的物理地址，再去访问内存数据。

整个页面的调入过程对用户是透明的。

页面置换算法

页面置换算法的选择，是虚拟存储器管理系统的核心问题。
它的实质是，为系统提供一种方法，当从主存中需要换出页面时，应避免选择那些不久将再次要求访问的页面。
置换算法的选择在一定程度上取决于可用的硬件设施。

最优置换算法 Optimal Replacement Algorithm

最理想的页面置换策略是：从主存中移出永远不再需要的页面；如无这样的页面存在，则应选择最长时间不需要访问的页面。
最佳置换策略首先是由 Belady 于 1966 年提出的。
最佳置换策略本身不是一种实际的方法，因为页面访问的未来顺序是不知道的，但是，可将其它的实用方法与之比较来评价这些方法的优劣。所以，这种最佳策略具有理论上的意义。

例 设页面请求次序 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
存储块为 3(驻留集为 3)，假定最初存储块为空，采用 OPT。

第一行为要请求访问的页面，第二行为存储块(内存)中存储的页，第三行为被移出内存的页。
从上面的演示知，利用 OPT，发生了 6 次页面置换,发生了 9 次缺页中断(前 3 次没有置换,但内存中未装入页面,发生中断)
缺页率=缺页次数/访问次数=9/20=0.45

先进先出页面置换算法 FIFO

该算法的实质是：总是选择作业中驻留时间最长的一页淘汰。即先进入主存的页面先退出主存。
算法实现比较容易，如分配给一个作业的存储块数为 m，只需建立一个 m 个元素的队列表 Q(0)、Q(1)、…、Q(m-1)和一个替换指针。该队列是按页面调入主存的先后顺序排列的，而指针始终指向最早调入主存的一页。

发生了12次页面置换,发生了15次缺页中断，缺页率=缺页次数/访问次数=15/20=0.75

二次机会页面置换算法 SCR，Second Chance Replacement Policy

二次机会算法是 FIFO 算法的升级版，而 clock 算法可以认为是二次机会算法的升级版本
该算法仍然使用标准的 FIFO 队列。

每个帧(frame)有一个 second chance 位，也叫做引用位。
当一个 frame 被引用到，它的 second chance 位设置为 1。这表示该 frame 后面还有可能会被引用到，所以下次置换先跳过这个 frame，也就是再给它一次机会留在内存中。这样可以减少 frame 置换，提高页面操作效率。
当一个新的页面被读到内存中时，它的 second chance 被设置为 0。
当你需要替换内存中的一个页面时，使用轮询的方式来查找可以被替换的页面：

• 如果页面的 second chance 是 1，那么置为 0，继续查找；
• 如果页面的 second chance 是 0，那么将这个页面置换出去。

最近最久未使用置换算法 LRU

LRU(least Recently Used)算法的基本思想是，利用局部性原理，根据一个作业在执行过程中过去的页面访问踪迹来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。
算法的实质是：当需要置换一页面时，选择在最近一段时间内最久未使用的页面予以淘汰。
实现这种技术，是通过周期性地对“页面访问”位进行检查，并利用它来记录一个页面自上次访问以来所经历的时间 t，并选择 t 为最大的页予以淘汰。

发生了9次页面置换,发生了12次缺页中断，缺页率=缺页次数/访问次数=12/20=0.60

LRU 算法的硬件支持
LRU 算法作为页面置换算法是比较好的，因为它适用于各种类型的程序。但是，实现起来比较困难，因为要对先前的访问历史时时加以记录和更新。如果这种连续的修改完全由软件来做，系统开销太大；如由硬件执行，则需要解决：

• 一个进程在内存中的各个页面各有多久未被进程访问？
• 如何快速地知道哪一页是最近最久未使用的页面？

为此，需要以下两类硬件的支持：

• 寄存器。用于记录某进程在内存中各页使用情况。
• 栈。用于保存当前进程使用的各个页面的页面号。

移位寄存器：
为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器可表示为：
$R = R_{n-1}R_{n-2}R_{n-3}…R_2R_1R_0$

当进程访问某物理块时，要将相应寄存器的最高位$R_{n-1}$位置成 1。表示这个页面最近被访问过。系统每隔一定时间（例如 100 ms）将寄存器右移一位，这意味着如果一个页面在一段时间内没有被访问，它的寄存器值将逐渐变小。
如果我们把 n 位寄存器的数看作是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
例如，假设我们有三个页面，其寄存器值分别为 100（4）、010（2）和 001（1）。在这种情况下，第三个页面的寄存器值最小，因此它是最近最久未使用的页面，应该被换出。
栈
操作系统维护一个栈，其中每个元素代表一个页面。栈顶的元素代表最近被访问的页面，而栈底的元素代表最近最久未使用的页面。

最少使用置换算法 LFU

最少使用置换算法(Least Frequently Used)选择到当前时间为止被访问次数最少的页面被置换。
1、基本方法：
记录每个页面的访问次数，最少访问的页面首先考虑淘汰
2、实际采取方法
为页面设置移位寄存器。统计 1 的个数,1 的个数越少，表示访问次数越少，越容易被淘汰。
与 LRU 的区别：
R1=10000000
R2=01110100
LRU----------淘汰 R2
LFU----------淘汰 R1

Clock 置换算法

简单的 Clock 置换算法（NRU）当采用简单 clock 算法时，为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。

• 某页被访问时，其访问位被置 1。
• 置换程序从上次停止位置开始检查页面的访问位。
  • 如果是 0，就选择该页换出；
  • 若为 1，则重新将它置 0，暂不换出，而给该页第二次驻留内存的机会。
• 由于该算法是循环地检查各页面的使用情况，故称为 clock 算法。置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法 NRU。

改进型 Clock 置换算法

系统把一个页面移出内存时，如果该页面驻留内存期间没有被修改过，那么不必把它写回辅存，否则系统必须把它写回辅存。这表明，换出未修改过的页面比换出被修改过的页面开销小。
显然，我们可以依据上述结论改进 CLOCK 算法。改进后的 CLOCK 算法将在置换范围内首选符合下面条件的作为被置换页面

1. 在最近没有被使用过；
2. 在驻留内存期间没有被修改过的页面

由访问位 A(Access)和修改位 M(Modify)可以组合成下面四种类型的页面,淘汰优先级依次下降：
1 类（A=0，M=0）：表示该页最近既未彼访问，又未被修改，是最佳淘汰页。
2 类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
3 类（A=1，M=0）：最近已被访问，但未被修改：该页有可能再被访问。
4 类（A=1，M=1）：最近已被访问且被修改，该页可能再被访问。

执行过程可分成以下三步：
（1）从指针所指示的当前位置开始，扫描循环队列，寻找 A=0 且 M=0 的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
（2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找 A=0 且 M ＝ 1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位 A 都置 0。
（3）如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复 0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页 .

FAQ

Q：存储块越多，缺页中断率越小吗？
A:
一般来说，对于任何一个页的访问顺序(或序列)和任何一种换页算法，如果分给的物理块数增加，则缺页(所访问页不在主存)的频率应该减少。但这个结论并不普遍成立，对于某些页面访问序列，FIFO 有随着分给的页架数增加，缺页频率也增加的异常现象。
例如某程序在内存中分配 m 页初始为空，页面走向为
1，2，3，4，1，2，5，1，2，3，4，5
当 m=3，m=4 时缺页中断分别为多少？用 FIFO 算法
m=3 时，缺页中断 9 次
m=4 时，缺页中断 10 次

抖动与工作集 Thrashing and Working Set

缺页率对有效访问时间的影响

有效访问时间是指访问存储器所需时间的平均值。
假设使用了快表，则 CPU 访问内存时有以下三种情况(设内存读写周期为 t，查找快表时间为 λ，缺页中断处理时间为 ɛ)：

• 页面在内存且页表项在快表中：只需一次访问内存
  EAT= λ + t
• 页面在内存但页表项不在快表中：需两次访问内存，一次读取页表，一次读取数据，另外还需更新快表。
  EAT= λ + t + t + λ=2(λ + t)
• 页面不在内存：考虑查找快表时间、查找页表时间、缺页中断处理时间、更新快表时间、访问实际物理地址时间
  EAT= λ + t +ɛ + λ + t = 2(λ + t) + ɛ

引入快表命中率为 α，缺页中断率为 f，则有效访问内存时间为：
EAT= α(λ + t) + [1-α](2(λ + t) + f(2(λ + t) + ɛ))

抖动

系统内进程增多–>每个进程的缺页率增大–>缺页率增大到一定程度，进程总等待调页完成–>CPU 利用率降低–>进程进一步增多，缺页率更大 …
此时: 进程调入一页，需将一页淘汰出去，刚淘汰出去的页马上要需要调入;称这一现象为抖动或颠簸(thrashing)显然，防止的根本手段给进程分配足够多的帧

抖动：如果运行进程的大部分时间都用于页面的换入/换出，而几乎不能完成任何有效的工作，则称此进程处于抖动状态。抖动又称为颠簸。

抖动分为：

• 局部抖动
• 全局抖动

抖动产生的原因有：

• 进程分配的物理块太少
• 置换算法选择不当
• 全局置换使抖动传播

工作集模型

在工作集模型中，工作集的定义是在最近的一段连续执行时间（称为工作集窗口，通常用 T 表示）内，进程实际引用过的页面集合。换句话说，工作集是进程当前正在使用或可能马上就要使用的页面的集合。

抖动的预防

• 抖动发生前会出现一些征兆，可利用这些征兆发现抖动并加以防范。这些技术有：
• 采取局部置换策略
• 引入工作集的算法
• L=S 准则
  • L 缺页之间的平均时间，S 平均缺页服务时间
• 选择暂停的进程

请求分段存储管理方式 Demand Segmentation

工作原理：请求分段系统中，程序运行之前，只需先调入若干个分段（不必调入所有的分段），便可启动运行。当所访问的段不在内存中时，可请求 OS 将所缺的段调入内存。

为了实现请求调段、分段置换两大功能，系统必须提供如下的硬件支持：

• 请求分段的段表机制
• 缺段中断机构
• 地址变换机构

原理及实现

请求分段的段表机制

在虚拟存储系统中的所有段表，其段描述子增加五个信息标识位。

1. 状态位(存在位)P：用于说明该段是否已调入内存，供程序访问时参考；P=0，该段不在内存;P=1，该段在内存
2. 访问位 A：用于记录本段在一段时间内被访问的次数，提供给置换算法选择换出段时参考。A=0，该段未被访问;A=1，该段被访问
3. 修改位 M：用于表示该段在调入内存后是否被修改过，也是提供给置换算法在换出段时是否将该段写回外存作参考。M=0，该段在内存中未被修改;M=1，该段在内存中已经被修改
4. 外存地址：用于指出该段在外存上的地址，供调入该页时使用。
5. 增补位：说明该分段是否允许扩展，此外如该段已被增补，则在写回辅存时，需另选择辅存空间；

缺段中断机构 Demand Segment Fault

由上述段表机制知道，状态位记录了访问段是否在内存。在地址映射过程中，在段表中发现所要访问的段不在内存，则产生缺段中断。OS 接到此中断信号后，就调出缺段中断处理程序，根据段表中给出的外存地址，将该段调入内存，使作业继续运行下去。缺段中断与缺页中断类似，主要表现为：
① 一个缺段中断要求在指令执行中间得到服务，即发现所要访问的指令或数据不在内存时产生缺段中断并处理。
② 一条指令可能引起多次不同的缺段中断。

地址变换机构 Address Translation

分段的共享与保护

共享段表

为了实现分段共享，可在系统中配置一张共享段表，所有共享段都在共享段表中占有一个表项。

• 共享进程计数：记录有多少进程共享该段。
• 存取控制字段：对同一共享段，不同进程有不同的操作权限。
• 段号：共享段在不同进程中有不同的段号。

共享段的分配与回收

共享段的分配

在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把 count 置为 1；

之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段表中，填上调用进程的进程名、存取控制等，再执行count+=1操作，以表明有两个进程共享该段。

共享段的回收
当共享此段的某进程不再需要该段时，应将该段释放， 包括撤消该进程段表中共享段所对应的表项，以及执行 count-=1 操作。
若 count 结果为 0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则，则只是取消调用者进程在共享段表中的有关记录。

分段的保护

1. 越界检查 Bounds Check
   寄存器中放有段表长度信息，将逻辑地址空间的段号与段表长度进行比较 ，如果段号等于或大于段表长度，将发出地址越界中断信号。保证每个进程只能在自己的地址空间内运行。
2. 存取控制检查 Access Control Check
   Read-Only、Read-Write、Execute-Only、Execute-Read-Write etc
3. 环保护机构 Ring Protection
   低编号的环具有高优先权。OS 核心处于 0 环内；某些重要的实用程序和操作系统服务，占居中间环；而一般的应用程序在外环上。

环保护的基本原则是：
一个程序可以访问驻留在相同环或较低特权环中的数据；
一个程序可以调用驻留在相同环或较高特权环中的服务。

环保护的基本思想是将操作系统内的操作和资源划分为不同的"环"，每个环都有其特定的权限。通常，环的编号越小，权限越高。例如，在一个典型的四环模型中：

• 环 0（Ring 0）：拥有全部权限，通常用于运行操作系统内核，可以访问所有硬件和内存资源。
• 环 1（Ring 1）和环 2（Ring 2）：通常用于运行操作系统服务，有一些特定的硬件和内存访问权限，但不如环 0 全面。
• 环 3（Ring 3）：权限最低，通常用于运行用户级的应用程序，只能访问有限的硬件和内存资源，对系统资源的访问需要通过系统调用。
  

Ref

Clock 置换算法