先介绍用于实现地址转换和加速这一过程的硬件，即存储管理部件与翻译快表。在了解了这两个硬件的作用后，我们将学习几种用于在翻译快表和内存中替换页面的算法，对比它们对于内存读取命中率的影响。

上一章中我们讲到了分页管理存储方法如何将逻辑地址转换为物理地址，但我们没有讲到进程在实际运行的过程中实现这一转换的细节。比如，页表是存储在哪里的？如何解决分页管理为了对一个地址进行操作至少要访问两次内存的问题？如果所寻页面现在不在物理内存中该怎么办？这一章中我们就来解决这些问题。

存储管理部件和翻译快表

• 存储管理部件

首先我们应该明确，处理器在运行时使用的是逻辑地址，与物理地址是有区别的，也就是说每一次处理器需要从内存中读取某一数据或向内存中写入某一数据时我们都必须通过某种方法将逻辑地址变为物理地址，实现这一功能的正是 存储管理部件（Memory Management Unit，MMU）。
存储管理器中含有一个硬件页表基址寄存器，其中存放了现在正在运行的进程的页表基址；当进程需要读取或写入一个地址时，存储管理部件都将其逻辑地址分解为页号和页内位移，然后用硬件页表基址寄存器中的页表基址进入页表中正确的项，获得其物理页框号。存储管理器也负责在进程使用一个页面时查看保护权限位、检查进程无越权操作，并改变页表中该页面对应的特征位（修改位、有效位、引用位等）。

• 翻译快表

你在看教材时有时可能会有这样的经历：当你第一次看某个章节的时候，你可能需要看目录才能找到章节对应的页数，但当你看了很多次这个章节以后，你不需要看目录也可以直接翻到书中对应的部分。同样地，在分页存储管理中，我们第一次使用一个页面时不可避免地需要从页表中找到它对应的页框号，需要访问两次内存，但如果我们能通过某种形式记住这个页框号，那之后我们再使用这个页面时就可以直接使用了。

当然，我们不能把页框号记在内存里的某个地方，因为这样我们仍然需要两次访问内存；我们需要的是一个比内存更快的硬件，这就是 翻译快表（Translation Lookaside Buffer，TLB）

翻译快表是独立于内存的 硬件，其读写速度远快于内存，一次读取可能只需要一个处理器时钟周期，但它的造价也更高，因此一般只能用来存放几十个页表项。每次进程使用一个页面时，我们先查看这个页号
对应的页框号是否已经存放于翻译快表中；如果没有，我们就将这个页面的号及其对应的页框号和特征位存入翻译快表，下次再使用这个页面时就可以直接看翻译快表找到页框号获得物理地址。每次我们使用一个页面时需要更新翻译快表中对应的特征位，如写入页面后就必须更新修改位（dirty bit） 为 1。

需要注意的是，我们不能允许一个进程通过翻译快表获得有关另一个进程的信息，因此我们需要以某种形式区分不同进程在快表中的项。一般我们有两种方法解决这个问题：

• 我们可以在每一个快表项中添加其对应进程的 进程标识符（PID），这样硬件就可以禁止进程标识符与快表项不同的进程获得这一项的内容；
• 我们也可以在每一次上下文切换时都将翻译快表清空或全部设为无效，强制下一个进程进入页表获取页框号。

翻译快表本质上就是一种特殊的 高速缓冲存储器（cache） ，其目的是减少将来访问数据时需要的时间。为了最大程度上减少访问页表产生的延迟，我们希望提高访问页面在翻译快表中出现的比率，即翻译快表的命中率，并缩短一次命中需要的时间。下面的章节中，我们就将讲到影响命中率和命中时间的因素、以及提高翻译快表命中率、缩短其命中时间的方法。

练习

失效和地址映像

为了提高命中率，我们先应该考虑翻译快表在哪些情况下无法命中一个页面。无法命中的情况被称为失效，在不考虑多处理器的情况下，失效主要分为以下三种：

• 1. 如果我们第一次使用某个页面，那么它不可能已经在翻译快表中。这种失效被称为 强制失效（compulsory miss）。
• 2. 如果我们之前曾经把某个页面放入翻译快表中，但一段时间后我们再用这个页面时它的位置已经被其它页面占用了，那我们就遭遇了 冲突失效（conflict miss）。
• 3. 如果我们在使用一个页面时，发现这个页面不在翻译快表中，且表中已经装满，那么我们就遭遇了** 容量失效（capacity miss）**。很多同学很难区分容量失效和冲突失效，这里我们介绍一种区分方法：
     如果你面临的失效通过增加快表的容量就可以被解决，那么这就是容量失效，否则就是冲突时效。

为了减少强制失效，我们可以根据用户会连续使用内存的假设（这被称作空间局部性，spatial locality） 在使用一个页面的时候把它后面的一个或几个页面也读取进来（这种技术叫做 预取，prefetching），但读取本身所占的时间也会带来延迟，而且读取太多反而可能造成容量失效，因此我们在这里先不做讨论。
减少容量失效的办法只有扩大容量，但这就要求我们提高计算机的制作成本，也不属于我们这节课的考虑范畴。因此，我们主要需要考虑的就是如何在不提高命中时间的基础上，减少冲突失效的比例。 冲突失效的数量主要取决于翻译快表是如何通过页号决定页面在快表中的位置的，即其使用的地址映像方法；与高速缓冲存储器相类似，翻译快表也可以从以下三种方式中选择一种：

• 直接映像（direct map）
• 组关联映射（set associative）
• 全关联映射（fully associative）

在直接映像中，我们可以根据快表的容量选取页号中固定的几位，与快表中的项一一对应。比如，如果快表中可以包含64项，那么我们就可以选择页号的后 6位（ 64 = 2 ）；假如后 6位是 010010 ，那么我们就将这个页面插入到快表的第18 项，如果这一项已经被另一个页面占据，我们就把这个页面移出快表，用新的页面取代它。这个失效的老页面面临的就是冲突失效，因为它们恰好都被映射到同一个快表项，即使扩大容量可能也并不能解决这一冲突。

直接映像显然会给我们带来很多冲突失效，因为每个对应的位置只能存放一个页面；我们希望一个区域可以容纳多个被映射到这个区域的页面而不导致失效，这就是组关联映射背后的思想。在组关联映射中，翻译快表被分为几个含有相同数量页面的组，当一个页面被映射到一个位置时，它可以进入这几组中任何一个组的对应位置，这就减少了冲突失效出现的概率。还以上面提到的可以容纳 64项的快表为例，如果我们把它分到 个4组中，那么 64/4 = 16 = 2^4，我们就只需要比较页号的后四位来给一个页面选择一个位置；如果这四组中任何一个组中的这一位置是空闲的，我们就可以把这个页面放入那个位置。

提高关联性（即增加组数）对于避免冲突失效是很有效的，因此我们可以把这一优势发挥到极致，将所有快表中存放的项都看做并列的组（如果快表中含有64 项，那么它就有 64个只含有一页的组）。这样，当一个页面进入快表时，就可以进入任何一个空闲的项；这就是全关联映射。
全关联映射没有任何冲突失效，在容量相同的前提下大大提高了命中率，但是它也有一个很大的弊端：它会延长一次命中需要的时间。这是因为我们在想要从快表获得一个页面的页框号时，必须同时将它与四个组的对应位置存放的页面作对比，然后将结果综合起来，看它实际被存放于哪一个组中，这一过程将会花费更长的时间。

翻译快表的地址映像与替换机制

由于翻译快表的一次失效意味着进入内存中的页表获取页表项，一次失效带来的时间代价远大于提高关联性导致的命中时间的延长。因此一般的翻译快表仍然采用全关联型。

当然，为了既享受关联型快表带来的高命中率，又不牺牲命中时间，翻译快表也可以由两层使用不同的映射方法的快表构成。

• 第一层快表容量小、使用直接映射、速度较快，但命中率较低；
• 一旦第一层不能命中，就进入全关联型的第二层快表寻找，这一层虽然命中时间长，但命中率高。

在全关联型翻译快表中，还有一个因素会影响命中率，那就是我们在快表已经装满时选用旧页面进行替换的机制。在直接映射型快表中，新的页面只能代替它映射位置的那个页面，因此我们不需要考虑替换机制；但在全关联型中，每一个页面都是相互等价的，我们必须用一种其它的标准来判断应该将哪个页面替换掉。如果我们的替换机制不好，那么很可能出现一个页面刚刚被替换出去，马上又需要被调入的情况；这种情况的持续被称为 “抖动”（thrashing），会大大拖慢运行速度。

我们可能会很自然的想到一个替换机制，即先进翻译快表的页面就先被替换。这一算法被称为 先进先出算法（First In First Out, FIFO） 。这一算法面临的主要问题是，先进的页面可能是包含程序代码的页面，而这种常用页面刚刚被替换出去马上就又将被需要，这会给我们造成很多时间上的浪费。我们想要一个不会把未来很快就会被需要的页面替换出去的替换机制。

• 一个较为合理的替换机制是选择自上一次使用后过去的时间最长的页面。
  这种标准基于一个假设，即用户在使用内存时短时间内会使用一段连续的区间的内存，因此一段时间内不被使用的内存短时间内应该也不会被使用。这种方法被称为 最近最少使用方法（Least Recently Used，LRU） 。我们在本章的后几节讲到请求分页的调度算法时也会讲到它，到时候我们再具体分析这种算法的实现方法和应用。

• 另一种替换机制是随机选择一个页面替换；你可能觉得这种方法听起来很不靠谱，但实际随着快表大小的增大，随机替换机制的命中率会逐渐逼近最近最少使用方法的命中率，而其实现难度又小于后者，因此在实际应用中往往被广泛使用。

讲完翻译快表后，让我们回顾一下我们讲翻译快表的理由：分页存储管理中，对一个地址的操作需要至少两次访问内存，因此我们想通过节省地址转换的时间来提高效率。

影响分页存储管理效率的因素除了地址转换所需的时间以外还有一点，就是每次我们转换地址后获得的页面地址实际存在于内存中的概率。如果一个页面在外存中，我们就需要花费大量的时间把它复制到内存中才能使用，因此我们希望尽可能多的页面在调用时都存在于内存中，这就涉及到我们在本章的后半部分要讲的内容：请求分页的虚拟存储方法。

练习

请求分页虚拟管理

在解决了分页存储地址转换所需时间过长的问题后，我们现在来解决所需页面不在内存中的问题。当一个进程所需的页面比物理内存大时，我们就只将运行所需的页面保留在内存中，将其它页面保留在读写速度较慢的外存中。因此当我们发现一个页面不在内存中（即页表中或翻译快表中该页面对应的有效位为 ）时，我们就触发了 缺页异常（Page Fault Exception）， 原 本 负 责 地 址 转 换 的 存储管理部件（MMU） 会将控制权交给内核，而内核会使进程进入等待态，选择一个空闲的页框或将一个内存中的页面移出至外存，将所缺页面从外存复制到该空闲页框中。

这一过程就被称为请求分页虚存管理，即只在需要页面时将页面从外存调入内存。请求分页与我们在第三节中提到过的预取技术相对应，是两种调入页面的方法。两者的不同就在于，请求分页在一个页面不被请求的时候不会调入这个页面，因此，我们接下来关于请求分页的讨论中都不会涉及提前调入的问题。

有心的同学马上会留意到，请求分页与使用翻译快表在本质上是相同的，都是对高速缓冲存储器这一概念的应用。高速缓冲存储器存在的目的就是要将可能马上被使用的数据存放在读写速度更快的存储器中；翻译快表可以被看做是针对页表的高速缓冲存储器，而内存则可以被看做是针对外存的全关联型高速缓冲存储器。
因此，在设计请求分页机制的过程中，我们所面临的问题与设计任何其它高速缓冲存储器时面临的问题是一样的——怎么样才能最大限度地利用存储在高速缓冲存储器中的数据提升运行的速度呢？

决定请求分页机制的效率的因素与翻译快表相似，就是用选择用来替换的旧页面的算法；我们需要选择一个能够降低缺页异常比率的算法。这种替换算法可以根据替换范围分为两大类，一类是全局替换算法，一类是局部替换算法，前者从物理内存的 全部页面中 选取一个页面进行替换，而后者只从 需要调入页面的进程 本身的页面里选取一个替换。

我们将先讲解全局替换方法，因为它和我们前面学到的翻译快表的替换算法较为相似。在翻译快表中用到的

• FIFO（先进先出算法）
• LRU（最近最少用到算法）
• Random （随机算法）

依然适用于全局替换算法。不过在复习这三种算法以前，我们将先带你认识 最佳页面替换算法（OPT），以便于我们将其它全局替换算法的表现与最佳页面替换算法的表现作比较、评价其利弊。

预知未来

在介绍其它全局页面替换算法以前,我们想要先给你介绍Beay在1966年提岀的最佳页面替换算法( Optimal，简称OPT)。

最佳页面替换算法要求系统在需要从外存调入一个新页面时选择内存中未来最长的一段时间内不会被用到的页面来替换。比如,如果一个內存中有4个页面,分别会在10,7,8,15分钟会会被用到,那我们就把15分钟后会用到的页面调出內存,用新页面加以替换。

这一算法显然是不能够实现的，因为它需要我们能够完全地预知未来。之所以要讲这个算法，是因为这个算法可以被证明是最好的页面替换算法，我们接下来讲其它可实现的算法时都要与这个最佳算法作比较来衡量其优劣程度。凭借直觉你应该能够认同这个算法可以实现最佳的页面调度，但实际的证明还是有一点复杂的，接下来我们就来讲一讲这个证明。

我们将用反证法来证明PT的最佳性。假设OPT不是最佳算法,而最佳算法是ALT,即 Alternative。当我们用两种调度算法来运行同一组进程时(即,页面请求的顺序、数量对于两种算法完全相同)我们可以设页面请求为OPT与ALT第一次产生
分歧的点。为了调入页面i,OPT从内存中移出了页面j,而ALT从内存中移出了页面k。由OPT的定义我们可以知道,页面j一定会在页面k之后被调用(我们假设不会有两个页面同时被调用)。

现在我们要稍微修改一下ALT算法,然后通过证明修改后的算法与修改前的算法至少一样好来推翻我们之前的假设。上文我们提到页面i是使OPT与ALT第一次产生分歧的调入页面,为了推翻这个假设,我们现在修改ALT使其在处理页面请求时不再与OPT产生分歧——修改后的算法为了调入页面i,也会从內存中移出了页面了,这之后所有请求新算法都与ALT的处理方式完全相同。设这个新算法为NEW,现在我们就要来证明NEW与ALT都是最佳算法。

由于ALT在调入页面i时从内存中移出了页面k,根据请求分页的定义,在下一次需要调用页面k以前,页面k都不会被调入内存。因此在下一次调用k时,ALT一定会产生缺页异常,需要将页面k从外存调入,假设这一步骤中被调出内存的页面为m。由于NEW没有调出k,NEW在这里不会产生缺页异常。

• 如果m=j,那么现在NEW和ALT的内存中就含有完全相同的内容,而NEW比ALT少产生了一个缺页异常,证明ALT不是最佳算法,矛盾。
• 如果m≠j,那么接下来如果m在j之前就被调用,那么ALT就会产生更多缺页异常,直到我们ALT从内存中移出j(这种情况下就会与前面的情况产生相同的矛盾)或最终需要调用j。在调用j时,NEW会产生一个缺页异常,但这与之前ALT调用k时的缺页异常相抵消,因此NEW至少和ALT一样好。
  上面我们所证明的正是数学归纳法的基础步骤，接下来我们就可以用递推证明，OPT 至少与 ALT 一样好，因此 OPT 就是最佳算法。递推步骤的证明与上面的证明相类似这里就不一一写出了。

练习

image.png