第5章 存储系统

1. 存储器的分类和主要特点
2. Cache的三种映像关系：全相联、直接映像、组相联
3. 主存地址Tag、Index、块内偏移三个字段的计算
4. Cache块的替换策略
5. Cache的读写过程
6. 平均访存时间和CPU时间的计算
7. Cache失效率的类别，以及每种失效率的解决方法有哪些
8. 虚拟地址到物理地址的转换过程，TLB表的原理和作用，与Cache的关系，访存时间的最好情况和最坏情况的判断

5.1 引言

5.1.1 基本术语及概念

存储器的分类

半导体存储器

1. 静态随机存储器 — SRAM

2. 动态随机存储器 — DRAM

3. 闪存 - Flash Memory

性能指标：容量、存储周期（例：2GB 60ns）

磁表面存储器

性能指标：容量、转速（例： 200GB 7200转/分）

光盘存储器

1. CD-ROM：只读性光盘

2. WORM：写入式（只能写一次）

3. CD-RW：可擦/写光盘

例如：

• DVD - Digital Versatile Disc 4.7GB
• VCD - Video Compact Disc 700MB

存储器存取方式

随机存取存储器(RAM)

可按地址随机地访问任一存储单元

访问时间与访问地址无关

顺序存取存储器(SAM)

必须按顺序访问,例如：磁带。

存储器的主要性能指标

存储容量

单位：Byte、KB、MB、GB

存取周期

CPU连续访存中平均一次存取操作所需的时间。

5.1.2 加快存储器的速度

问题

处理器-存储器之间的性能差距

• 处理器：容量小 速度快
• 存储器：容量大 速度慢

硬件的部件特征

• 更小的硬件更快也更贵
• 更大的存储器级别更低也更便宜

目标

• 具有最小存储器的速度和最大存储器的容量
• 价格接近最便宜级别的存储器

解决方法

局部性原理：多数程序不会一下访问所有的代码或数据

• 时间局部性： 如果一项被访问，则该项趋向于近期又被访问

  使最近访问过的多数数据项靠近处理器

• 空间局部性：如果一项被访问，附近的项趋向于近期被访问

  把最近访问过的连续字（块）移向处理器

利用局部性原理，以最便宜技术提供尽可能多的存储空间，以最快的技术提供访问

方法：基于存储器的各层（级）具有不同的速度与大小

• 靠CPU越近的级，速度越快
• 靠CPU越近的级，容量越小
• 靠CPU越近的级，价格越贵

使用的存储器

Static RAM(SRAM)静态存储器

用于制造寄存器、L1/L2 Cache

存取速度快：0.5～25ns(集成的更快)

集成度低、价格贵

功耗大

Dynamic RAM(DRAM)动态存储器

用于计算机主存的制造

存取速度慢：50～70ns

需周期性刷新

集成度高，价格便宜

功耗小

5.2 Cache的基本原理

5.2.1 Cache概述

DRAM的发展趋势

容量：4倍/3年

速度：2倍/10年

寻址的速度差异

寻址延时与制造材料的物理特性有关

带宽的增加

• 并行传输：多位同时传输
• 突发传输（Burst transfers）：在一个读写周期内实现多次传输

利用带宽支持存储器的分层结构

• 使用Cache支持访问的局部性
• 分层设计存储器，实现内存中大块数据的传输

当前计算机的存储器结构

Cache的原理

插入到CPU与主存间

由快速SRAM实现

存储程序的部分：指令、数据

操作：

• 命中 (在Cache中)
• 未命中 (不在Cache中)

实现Cache的4个关键问题

1：数据块放在Cache的什么地方？

2：如何在Cache中找到所需的数据块？

3：Cache未命中时如何调入数据块？

4：写数据时如何写？

• A. 只写Cache？
• B. 只写Memory？
• C. 同时时写Cache和Memory？
• D. 其它？

5.2.2 数据块放在Cache的什么地方

通常，主存容量远大于Cache的容量。因此，当要把一个块从主存调入Cache时，就存在如何放置的问题。这就是映象规则（地址映像）所要解决的。映象规则有以下3种：

• 全相联映像
• 直接映像
• 组相联映像

全相联映象 (fully associative)

全相联是指主存中的任一块可以被放置到Cache中的任意一个位置的方法。

假设， Cache大小为8块、主存大小为16块的情况。实际的Cache常包含几百个块，而主存则一般包含上百万个块。

如图所示，主存的第9块可以放人Cache中的任意一个位置（带阴影）。

直接映象 (direct mapped)

直接映象是指主存中的每一个块只能被放置到Cache中唯一的一个位置，主存的第9块只能放人Cache的第1块（9 mod 8）的位置。一般地，对于主存的第i块（即块地址为i），设它映象到Cache的第j块（i mod M，M为Cache的块数） 。

可以直接用主存块地址低m位去选择直接映象Cache中的相应块。

例如：$m=3$，$9=(1001{)}_2$ ，主存第9块只能放入cache的001块

组相联映象 (set associative)

Cache被等分为若干组，每组由若干个块构成。组相联是指主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。

这显然是直接映象和全相联的一种折中：一个主存块首先是映象到唯一的一个组上（直接映象的特征），然后这个块可以被放人这个组中的任何一个位置（全相联的特征）。

组的选择常采用位选择算法，即若主存第i块映象到Cache的第k组，则

$$k=imodG$$

其中，G为Cache的组数。例如图（c）中 9 mod 4 = 1。

设G = 2^g，则当表示为二进制数时，k实际上就是i的低g位。

因此，可以直接用主存块地址的低g位去选择组相联Cache中的相应组。这里的低g位以及上述直接映象中的低m位通常称为索引（index）。

图（c）中，$g=2$， $9=(1001{)}_2$ ，主存第9块只能在cache的01组。

如果每组中有n个块（n=M/G），则称该映象规则为n路组相联（n-way set associative）。前图（c）为两路组相联映象的示意图。

n的不同取值构成了一系列不同相联度（associativity）的组相联。直接映象和全相联实际上是组相联的两种极端情况。下表列出了各种情况下，路数n和组数G的取值。表中M为Cache的块数。

例子

数据Cache容量为8KB，块大小为32B，共有256个块，采用两路组相联映像方式。最小寻址单位1B。256块的Cache有128组，每组两块。

设主存的物理地址为34位。这个地址被分为两部分：块地址（29位）和块内偏移量（5位）。两路组相联映象，相联度为2，按下式来计算索引所需的位数为7位。

因此，标识为 29-7 = 22位。

或者说，Cache有128组，需要7位索引。

5.2.3 如何在Cache中找到所需的数据块

当CPU访问Cache时，如何确定Cache中是否有所要访问的块（主存的块是否在cache中，命中）？若有的话，如何确定其位置？这是通过查找目录表来实现的。

Cache中每个cache块有一个表项，用于指出当前该块中存放的信息是哪个主存块的（可能有多个主存块映象到该Cache块）。它实际上是记录了该主存块的块地址的高位部分，称为标识（tag）。每个主存块能唯一地由其tag来确定。

为了指出Cache中的块是否包含有效信息，一般是对每一表项设置一个有效位。例如，当该位为“1”时表示该表项有效，Cache中相应块所包含的信息有效。当一个主存块被调入Cache中某一个块位置时，它的标识就被填入目标表中与该Cache块相对应的项中，并且该项的有效位被置“1”。

根据映象规则不同，一个主存块可能映象到Cache中的一个或多个Cache块位置。为便于讨论，把它们称为候选位置。

当CPU访问该主存块时，必须且只需查找它的候选位置所对应的标识。如果有与所访问的主存块相同的标识，且其有效位“1”，则它所对应的Cach块即是所要找的块。为了保证速度，对各候选位置的标识的检查比较是同时并行地进行。

每个cache块的内容

主存地址的构成

直接映象Cache的候选位置最少，只有一个；全相联Cache的候选位置最多，为M个；而n路组相联则介于两者之间，为n个。

并行查找的硬件实现方法有两种：

（1）用组相联存储器实现；

（2）用单体多字存储器和比较器来实现。

图中画出了用第二种方法来实现4路组相联（每组4个块）的情况。这时需要4个比较器。CPU访存时，用本次访存地址中的索引找到对应的分组，并从该组中读出4个tag，然后将它们与本次访存地址中的tag进行并行比较。根据比较结果确定是否命中，以及该组中哪一个块是要访问的块（若命中）。

无论是直接映象还是组相联，查找时只需比较标识，索引无需参加比较。这是因为索引已被用来选择要查找的组（或块），而所有索引相同（且只有索引相同）的块都被映象到该组（块）中。所以，该组中存放的块的索引一定与本次访存的索引相同。

如果Cache的容量不变，提高相联度会减少组数、增加每一组中的块数，从而会减少索引的位数和增加标识的位数。当采用类似于前图的并行比较方案时，不仅所需比较器的个数随之增加，而且比较器的位数也随之增多。在全相联的情况下，索引的位数为0，块地址全都作为标识。

例（第三次课后练习）

假设一个计算机系统有64K字节的高速缓存。它采用4路组相联映射，每块有32B 。物理地址大小是34位，最小可寻址单位是1 B。给出34位物理地址哪些位分别对应于Cache索引、标识及块内偏移量。

答案：
高20位（第33-14）为标识字段，
中间9位（第13-5）为索引字段，
最低5位（第4-0位）为块内偏移

每块有32B = 2⁵ * 最小可寻址单位1B，所以块内偏移为5位；

每块有32B，4路组相联映射，所以每组2⁷B，
64KB的高速缓存 = 2¹⁶B，2¹⁶ / 2⁷ = 2⁹ 组，所以索引字段为9位；

物理地址大小是34位，剩下的20位为标识字段。

5.2.4 如何调入数据块

考点：LRU

FIFO（大概率不考）

由于主存中的块比Cache中的块多，所以当要从主存调入一个块到Cache中时，会出现该块所映象到的一组（或一个）Cache块已全被占用的情况。这时，需强迫腾出其中的某一块，以接纳新调入的块。那么应该替换哪一块呢？这就是替换算法所要解决的问题。

直接映象Cache中的替换很简单，因为只有一个块，别无选择。而在组相联和全相联Cache中，则有多个块供选择，希望应尽可能避免替换掉马上就要用到的信息。主要的替换算法有以下3种。

1．随机法

为了均匀使用一组中的各块，这种方法随机地选择被替换的块。有些系统采用伪随机数法产生块号，以使行为可再现。这对于调试硬件是很有用的。

优点：简单、易于用硬件实现

缺点：没有考虑Cache块过去被使用的情况，反映不了程序的局部性，所以其失效率比最近最少使用法高。

2．先进先出法(First-In-First-Out，FIFO)

选择最早调入的块作为被替换的块。

优点：易于实现，利用了同一组中各块进入Cache的顺序这一“历史”信息

缺点：不能正确地反映程序的局部性。因为最先进入的块，很可能是经常要用到的块。

3．最近最少使用法（Least Recently Used，LRU）

选择近期最少被访问的块作为被替换的块。但由于实现比较困难，现在实际上实现的LRU都只是选择最久没有被访问过的块作为被替换的块。方法的依据是局部性原理的一个推论：如果最近刚用过的块很可能就是马上要再用到的块，则最久没用过的块就是最佳的被替换者。

优点：较好地反映程序的局部性原理，因而其失效率在上述3种方法中是最低的。

缺点：LRU较复杂，硬件实现比较困难，特别是当组的大小增加时，LRU的实现代价会越来越高，而且经常只是近似地实现。

例

已知一个Cache存储器，主存有0～7共8块，Cache共有4个块，各个块号为C0、C1、C2和C3，采用组相联映像，分为两组。

初始时Cache为空，当程序执行过程中访存的块地址序列为：

1，2，4，1，3，7，0，1，2，5时，试给出采用LRU、FIFO替换算法时的实际装入和替换过程；并计算各自的命中率。

（1）采用LRU替换算法时，程序执行时块地址流情况。

命中率＝1/10

（2）采用FIFO替换算法时，程序执行时块地址流情况。

命中率＝1/10

例（第三次课后练习）

Cache-主存存储层次中，主存有0-15共16块，Cache为8块，块号为C0-C7，采用2路组相联映像。设Cache初始为空，现访存块地址流为1、 1、 2、 4、 13、 3、 9、 7、 3、 13时：

（1）画出用LRU替换算法，Cache内各块的实际替换过程图，并标出命中时刻。
（2）计算命中率。

命中率 = 3/10

LRU与随机法在失效率方面的比较

下表给出了LRU与随机法在失效率方面的比较。表中的数据是对于一个VAX地址流（既包括用户程序，也包括操作系统程序）在块大小为16 B的情况下统计的。

表中，对于大容量Cache，LRU和随机法的失效率几乎没什么差别。

5.2.5 写数据

设计Cache要对最经常发生的“读”进行优化。 “读”也是最容易提高速度的。访问Cache时，在读出标识进行比较的同时，可以把相应的Cache块也读出。如果命中，则把该块中所请求的数据立即送给CPU；若为失效，则所读出的块没什么用处，置之不理就是了。

“写”与“读”的区别：只有在读出标识并进行比较，确认是命中后，才可对Cache块进行写入：

• “写” 比“读”花费更多的时间。由于检查标识不能与写入Cache块并行进行。
• 要写入的数据的宽度不是定长的（通常为1～8 B）。写入时，只能修改Cache块中相应的部分，而“读”则可以多读出几个字节也没关系。

更重要的是，“写”访问可能导致主存与Cache副本内容不一致。在写Cache时，主存的内容也必须更新。至于何时更新，正是写策略所要解决的问题。

写命中时

写命中时，策略主要有两种：

1. 写直达法（write through）：也称为存直达法（store through），它是指在执行“写”操作时，不仅把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。
2. 写回法（write back）：也称为拷回法（copy back），它只把信息写入Cache中相应的块。该块只有在被替换时，才被写回主存。

为了减少在替换时块的写回，常采用“污染位”标志，即为Cache中的每一块设置一个“污染位”（设在与该块相应的目录表项中），用于指出该块被修改过还是没被修改过。替换时，若被替换的块是干净的，则不必写回下一级存储器，因为这时下一级存储器中相应块的内容与Cache中的一致。

写回法的优点：速度快，不需要经常访存，这使得写回法对于多处理机很有吸引力。
写直达法的优点：易于实现，而且下一级存储器中的数据总是最新的。后一个优点对于I／O和多处理机来说是重要的。
I／O和多处理机经常难以在这两种方法之间选择：它们既想用写回法来减少访存的次数，又想用写直达法来保持Cache与下一级存储器的一致性。

采用写直达法时，如果处理器的操作必须等待写操作完成才能进行时，则处理器称为是写停顿（write stall）。

通常用来减少写停顿的优化策略是采用写缓存技术（write buffer）。它允许处理器把数据写入到缓存后立刻继续工作，从而使存储器的更新和处理器执行重叠起来。

写失效时

当写失效时该如何处理呢，有两种选择：

• 按写分配法（write allocate）：写失效时，先把所写单元所在的块调入Cache，然后再进行写入。这与读失效类似。这种方法也称为写时取（fetch on write）方法。
• 不按写分配法（no-write allocate）：写失效时，直接写入下一级存储器而不将相应的块调入Cache。这种方法也称为绕写法（write around）。

写回法Cache一般与按写分配法结合使用。这样，以后对那个块的“写”就能被Cache捕获。

而写直达法一般与不按写分配法结合使用，因为以后对那个块的“写”仍然还要到达下一级存储器。

例

假设有一个全相联映射的Cache，采用写回策略，刚开始时Cache为空。有下面5个存储器操作：
1 write Mem[100];
2 write Mem[100];
3 Read Mem[200];
4 write Mem[200];
5 write Mem[100];

解：

for no-write allocate 不按写分配法

• misses: 1,2,3,5 缺失
• hit: 4 命中

for write allocate 按写分配法

• misses: 1,3 缺失
• hit: 2,4,5 命中

例（第三次课后练习）

假设有一个全相联映射的Cache，采用写回策略，刚开始时Cache为空。有下面5个存储器操作：
（1）write Mem[150];
（2）write Mem[150];
（3）Read Mem[70];
（4）write Mem[70];
（5）write Mem[150];

解：

如果采用按写分配情况下，命中操作的编号序列为：2，4，5

如果采用不按写分配情况下的命中操作的编号为：4

5.3 Cache 性能分析

统一 Cache 和分离 Cache

• 单一的指令数据混合Cache（称为统一Cache或混合Cache），但它有可能会成为瓶颈。例如，当按流水方式工作的处理器执行LOAD或STORE指令时，可能会同时请求一个数据字和一个指令字。所以对于LOAD或STORE操作，单一的Cache会出现结构冲突，导致CPU等待。
• 两个分离Cache：一个专门存放指令，另一个专门存放数据。大多数最近生产的处理器都采用了分离的Cache。Alpha AXP 21064就是如此，它有一个8KB的指令Cache，其结构和图5.9中8KB数据Cache几乎一样。

失效率

下表列出了不同容量的指令Cache、数据Cache以及混合Cache在相同条件下的失效率。这些数据是在块大小为32 B、直接映象的条件下，针对SPEC92典型程序，在DECstation5000上测出的平均值。

对指令的访问约占所有访问的75%。

从表看出，指令Cache的失效率比数据Cache的低。

例

根据表5.4所列的失效率，试问指令Cache和数据Cache容量均为16 KB的分离Cache和容量为32 KB的混合Cache相比，哪种Cache的失效率更低？

解 ： 如前所述，约75%的访存为取指令，则剩下25%的访存是取数据。因此，16KB分离Cache的总体失效率为

$$(75\%\times 0.64\%)+(25\%\times 6.47\%)=2.10\%$$

根据表5.4，容量为32KB的混合Cache的失效率略低一些，只有1.99%。 根据如上计算，容量为32KB的混合Cache的失效率略低一些，是不是说明混合Cache比分离Cache更好呢？

平均访存时间

失效率与硬件速度无关，是一个常用的评价存储系统的性能的指标。但是它不够完善，一种更好的的指标是平均访存时间：

$$\text{平均访存时间}AMAT=\text{命中时间}+\text{失效率}\times \text{失效开销}$$

其中，命中时间（hit-time）是指访问Cache命中时所用的时间，平均访存时间的两个组成部分既可以用绝对时间（如命中时间为2 ns），也可以用时钟周期数（如失效开销为50个时钟周期）来衡量。

平均访存时间仍然是衡量性能的一个间接指标，尽管它是一个比失效率更好的指标，但并不能代替程序执行时间。

平均访存时间公式可以分为指令访问和数据访问两部分：

\text{平均访存时间} = & \text{访问指令所占的百分比}×(\text{指令命中时间}+\text{指令失效率}×\text{失效开销})\\ &+\text{访问数据所占的百分比}×(\text{数据命中时间}+\text{数据失效率}×\text{失效开销})

可以用这个公式比较分离Cache和混合Cache的性能。

尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构冒险。

例

假设Cache的命中时间为一个时钟周期，失效开销为50个时钟周期，在混合Cache中一次LOAD或STORE操作访问Cache的命中时间都要增加一个时钟周期（因为混合Cache只有一个端口，无法同时满足两个请求，会导致结构冲突）。又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？

解 ： 如前所计算，16KB分离Cache的总体失效率为

$$(75\%\times 0.64\%)+(25\%\times 6.47\%)=2.10\%$$

查表所得容量为32KB的混合Cache的失效率为 $1.99\%$。

所以，两种结构的平均访存时间分别为

CPU时间

对于一段程序的CPU时间，可由下式计算得出：

$$\begin{gathered} CPU时间=IC\times \left(CP{I}_{\text{exexution}}\times 时钟周期时间+\frac{访存次数}{指令数}\times 失效率\times 失效开销时钟周期数\times 时钟周期时间\right) \\ =IC\times \left(CP{I}_{\text{exexution}}\times 时钟周期时间+\frac{访存次数}{指令数}\times 失效率\times 失效开销时间\right) \end{gathered}$$

例

我们用一个和AlphaAXP类似的机器作为第一个例子。假设Cache失效开销为50个时钟周期，当不考虑存储器停顿时（意思是不考虑cache的失效开销），所有指令的执行时间都是2.0个时钟周期，访问Cache失效率为2%，平均每条指令访存1.33次。试分析Cache对性能的影响。

解 ：

因此，当考虑了Cache的失效影响后，CPI就会增大，本例中CPI从理想计算机的2.0增加到3.33，是原来的1.67倍，所以CPU的时间也将增加到原来的1.67倍。然而，若不采用Cache，CPI将增加为2.0+50×1.33=68.5，即超过原来的30倍!

上面例子说明，Cache的行为可能会对系统性能产生巨大的影响。尽可能地减少平均访问时间是一个合理的目标，但是最终目标是减少CPU的执行时间。下面的例子就说明了二者的区别。

例

考虑两种不同组织结构的Cache：直接映象Cache和两路组相联Cache，试问它们对CPU的性能有何影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设：

• ① 理想Cache（命中率为100%）情况下的CPI为2.0，时钟周期为2 ns，平均每条指令访存1.3次。
• ② 两种Cache容量均为64KB，块大小都是32B，命中时间均为1个时钟周期。
• ③ 图5.10说明，在组相联Cache中，必须增加一个多路选择器，用于根据标识匹配结果从相应组的块中选择所需的数据。因为CPU的速度直接与Cache命中的速度紧密相关，所以对于组相联Cache，由于多路选择器的存在而使CPU的时钟周期增加到原来的1.10倍。
• ④ 这两种结构Cache的失效开销都是70 ns。（在实际应用中，应取整为整数个时钟周期）
• ⑤ 命中时间为一个时钟周期，64KB直接映象Cache的失效率为1.4%，相同容量的两路组相联Cache的失效率为1.0%。

解 : 平均访存时间=命中时间+失效率×失效开销，因此，两种结构的平均访存时间分别是

两路组相联Cache的平均访存时间比较低。

CPU性能为

用70 ns代替“失效开销×时钟周期时间”，两种结构的性能分别为

CPU时间_1路=IC × ( 2 × 2 + 1.3 ×0.014 ×70 ) = IC × 5.274

CPU时间_2路=IC × ( 2 × 2 × 1.1 + 1.3 ×0.01 ×70 ) = IC × 5.31

与平均访存时间的比较结果相反，直接映象Cache的平均性能稍好一些，这是因为在两路组相联的情况下，虽然失效次数减少了，但所有指令的时钟周期时间都增加了10%。由于CPU时间是进行评价的基准，而且直接映象Cache的实现更简单，所以本例中直接映象Cache是较好的选择。

例（第三次课后练习）

给定以下的假设，试计算直接映象Cache和两路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？
（1）理想Cache情况下的CPI为2.0，时钟周期为2 ns，平均每条指令访存1.2次。
（2）两者Cache容量均为64KB，块大小都是32B。
（3）两路组相联Cache中的多路选择器使CPU的时钟周期增加了12%。
（4）这两种Cache的失效开销都是80 ns。
（5）命中时间为1个时钟周期。
（6）直接映象Cache的失效率为1.4%，两路组相联Cache的失效率为1.0%。

怎样改善 Cache 性能

$$\text{平均访存时间}AMAT=\text{命中时间}+\text{失效率}\times \text{失效开销}$$

因此，12种cache优化措施分为3类：

1.减少缺失率

• 增加块容量

• 增大 cache 容量

• 更高相联度

• 编译优化

2.减少缺失代价

• 两级 caches

• 关键字优先和提前重启动

• 读缺失优于写缺失

• 牺牲缓冲

• 非阻塞 caches

• 预取技术

3. 减少cache的命中时间

• 小和简单的 caches

• 写操作流水化

5.7 虚拟存储器

虚拟存储器的概念

虚拟存储器：又称虚拟内存，将主存的用作辅助存储器(磁盘)高速缓存的技术。即将磁盘的一部分当作内存使用。

采用虚拟存储器的目的：

• 更有效地共享处理器和主存
• 可以运行超过主存容量的程序

虚拟存储器中，处理器产生了一个虚拟地址，再转换成一个物理地址，然后就可以访问主存了。

• 虚拟地址 (virtual address)：用户编程的地址空间，又称逻辑地址。

• 物理地址(physical address)：物理内存的地址空间。

虚拟存储器和Cache的工作原理是一样的，但不同的历史决定他们使用不同的术语。

虚拟存储器中，块被称为页，访问缺失被称为缺页。

虚存还提供重定位来简化执行时的程序加载过程。在用地址访存前，重定位将程序所用的虚拟地址映射到不同的物理地址。重定位允许我们将程序加载到主存中的任何位置。

虚拟地址到物理地址的转换

虚地址空间

大小：4GB = 2^32
页大小：4KB = 2^12

物理内存空间

大小：1GB = 2^30
页大小：4KB = 2^12

映射过程

通过页表进行虚拟存储器-物理存储器映射

如果页在内存中：进行存取

如果页在磁盘中：缺页

• (1) 将程序挂起
• (2) OS将磁盘中的页换入内存
• (3) 换页完成后，重起程序

虚拟存储器设计时需要考虑的问题

• 页的大小设置，典型4KB～16KB

• 降低缺页率，采用组相联或是全相联

• 缺页的替换算法

• 由于写磁盘太长，应采用写回机制

页式和段式虚拟存储器

本课程对虚拟存储器的讨论主要集中在使用固定大小的块的页式虚拟存储。

还有一种可变长度的块机制叫段式。
在段式中：地址由段号和段内偏移组成，段寄存器加上段内偏移量得到实际物理地址
缺点：需要程序员管理

分页使页号和偏移量的界限对于程序员和编译器不可见。

页的存放和查找

如果允许一个虚拟页映射到任何一个物理页，当缺页发生时，OS可以选择任意一个页进行替换。如前节所提到，全相联映射的困难在于定位。全部进行检索是不现实的。

页表

在虚拟存储系统中，使用页表来定位页。页表存放在存储器中，每个进程有自己的页表。硬件用一个指向页表首地址的寄存器（页表寄存器）指出页表在存储器中的位置。

缺页

如果有效位是0，就发生缺页，由OS获得控制权，控制的转移由异常机制完成。一旦OS获得控制权，它必须在下一级存储层次中找到该页，然后决定将该页放到主存的什么位置。

有一个数据结构记录每个虚拟页在磁盘上的存放位置，
还有一个数据结构记录使用每个物理页的是哪些进程。

缺页页面的调进方法：

• 预调方式：把将要用到的页面调入内存

• 请调方式：根据请求将需要的页机调入内存

由于预测哪些页面将要用到是比较困难的，故多采用请调方式。

页面的置换方法

最近最少使用策略(LUR)。

要完全准确地实现 (LUR)算法代价较大。

近似的方法：采用引用位(或使用位)：当一页被访问时该位被置位。OS定期将引用位清零，然后再重新记录，这样就可以判断在这段特定时间内哪些页被访问过。有了这个信息，OS就可以从那些最近没有访问的页中选择一页进行替换。

页表容量问题

设：虚拟地址为32，页大小4KB，页表每一项4字节

"页表项数"=2³²÷2¹²=2²⁰

"页表" 容量=2²⁰×4=4(𝑀𝐵)

也就是说，每个程序执行时都需要4MB的存储空间。如果千百个程序同时执行，每个程序都有一个自己的页表，将会怎样？（思路：多级页表）

关于写

虚拟存储系统必须使用写回机制，把整页复制回磁盘比把单个字写回要高效很多。

当某一页被替换时，我们希望知道该页是否需要被写回。为了追踪页是否被写过，可在页表中增加一个重写位，当页中任何字被写时就置位。

5.8 加快地址转换

快表 TLB

由于页表放在主存中，因此程序每次访存最少需要2次：

• 第1次访存：取得物理地址

• 每2次访存：取得数据

根据页表访问的局部性，设置一个特殊的cache，用于追踪最近使用过的地址变换。它将页表的一部分放入其中，这个放置页表的cache就称为快表（TLB）。

TLB 的一些典值

• 大小：16～512个项

• 块大小：1 ～ 2页表项

• 命中时间： 0.5 ～ 1个时钟周期

• 缺失代价： 10 ～ 100个时钟周期

• 缺失率：0.01% ～ 1%

• 缺失采用硬件或软件处理

• 替换策略多采随机策略

TLB 缺失

当TLB中没有一个表项能匹配虚拟地址时，TLB缺失就会发生。TLB缺失有两种可能：

• 页在主存中，只需要创建缺失的TLB表项
• 页不在主存中，需要将控制权交给OS来解决缺页

如何判断是哪种情况？

当处理缺失时，需要查找页表项，如果匹配的页表项的有效位无效，则该页就不在主存中。如果有效位有效，则取回所需的表项。

MIPS通常用软件实现TLB缺失：从主存中取出页表项装入TLB中。然后重新执行引起TLB缺失的那条指令，则TLB命中。

如果缺页，OS需要完成以下步骤：

1. 使用虚拟地址查找页表项，并在磁盘行找到被访问的页；
2. 选择替换一个物理页；
3. 启动读操作，将被访问的页从磁盘上取回到物理页上；
4. 当磁盘读页的操作完成后，操作系统可以恢复原先引起缺页的进程状态，并且执行从异常返回的指令。

数据访问引起的缺页异常很难处理，这是由于：

• 它们发生在指令之间，不同于指令缺页
• 在异常处理前指令没有结束
• 异常处理之后，指令必须重新执行，就好像什么都没有发生一样

TLB 和 Cache 的关系

• 页大小4kB；
• 地址空间32位；
• 页号20位；
• TLB全相联映射；
• Cache是直接映像。

在TLB和Cache中处理读或者写直达操作：

最好情况：虚拟地址由TLB转换，然后送到Cache，找到相应的数据，然后取回并送入处理器

最坏情况：TLB、页表、Cache三个部件都发生缺失。

TLB、页表、Cache可能发生的组合和是否真的可能发生？

5.9 虚拟存储器的保护

虚拟存储器的保护

虚拟存储器的重要功能：保护

• 允许多个进程共享一个单一的主存；
• 为每个进程提供运行空间；
• 保护每个进程的空间不被另外的进程访问；

基本原理：2种模式

• 用户模式（用户态）：只能访问用户自己的地址空间；
• 超级用户管理模式（核心态或管态）：允许访问OS的地址空间、页表和其它状态信息；

系统调用

系统调用：将控制权从用户模式转换到管理员模式的特殊指令。

和其他异常处理一样，系统调用处的程序计数器中的值被保存在异常程序计数器中（EPC），处理器被置于管理态。

共享

每个进程有自己的虚拟地址空间，不同进程能够共享他们虚拟地址空间中的一部分。

但是需要赋予进程保护数据防止被其他进程读或写的能力，即防止一个进程读取另外一个进程的数据。

需要操作系统的保护或协助（操作系统管理页表的组织，使独立的虚拟页映射到不相交的物理页上，就能使一个进程无法访问另外一个进程的数据。同时，由操作系统负责修改页表，防止用户进程更改自己的页表，通过将页表放在操作系统的保护地址空间）。

硬件支持操作系统对虚拟地址空间的保护

• 指示处理器被置于超级用户管理模式（即核心态或管态）
• 系统调用异常处理完成
• 用特殊指令（如MIPS指令集中的syscall）将控制权传到管理代码空间的指令位置

虚拟存储器小结

• 虚拟存储器是管理主存和磁盘的之间数据缓存的一级存储层次
• 虚拟存储器允许单个程序在主存有限的范围内扩展地址空间。
• 虚拟存储器以一种保护的方式，支持多个同时活跃的进程共享主存。
• 管理主存和磁盘之间的存储层次结构由于缺页的代价很高。
• 虚拟存储器机制提供了从被程序使用的虚拟地址到用来访问主存的物理地址空间之间的转换。对于页表，TLB扮演了地址转换cache的角色，利用TLB中的变换，将虚拟地址转换为物理地址
• 这个地址转换允许对主存进行受保护的共享。进程之间受控制地共享页可以在操作系统的协助完成。为了保证进程间受到保护，要求只有操作系统才能改变地址变换，防止用户程序更改页表。

5.10 虚拟机

虚拟机

虚拟机（Virtual Machine, VM）从20世纪60年代到现在，一直是大型机的重要组成部分。

近年来受到关注的原因：

• 隔离性和安全性的重要性日益增长；
• 标准操作系统在安全性和可靠性方面的缺陷；
• 多个不相关的用户间共享计算机；
• 硬件能力大幅增加，虚拟机的开销将至可接受范围内；

VMware虚拟化平台上为多个操作系统（可以是相同的或不同的操作系统）虚拟出相应硬件环境。

虚拟机分类

应用级虚拟机：Java虚拟机

系统级虚拟机：Xen，IBM VM/370

系统级虚拟机让用户觉得自己独享计算机，一台运行多个虚拟机的计算机可以支持多个不同的OS，因此多个不同的OS也共享硬件资源。

虚拟机管理器

管理虚拟机的软件被称为虚拟机管理器（Virtual Machine Monitor，VMM），或管理程序（Hypervisor）

虚拟机管理器（Virtual Machine Monitor，VMM）能管理每个虚拟机状态的必备条件

• 使客户软件在虚拟机中的运行和本地硬件上的运行效果完全相同（相同和不同的指令集结构）；
• 客户软件不能直接改变系统的资源分配；
• VMM能在必要时控制一切，包括访问特权状态，地址转换，I/O，异常和中断等，还能决定由哪个客户虚拟机运行；
• VMM比客户虚拟机的特权态更高；

VMM必须保证客户系统只能和虚拟资源交互。如果客户OS试图直接通过特权指令访问或者修改相关硬件资源，如写一个页表指针，它会向VMM发出中断，然后由VMM来处理。

因此，任何试图在用户模式下读/写这样的敏感信息的指令都应被VMM截获并处理。（需要处理器硬件支持）。

不幸的是，大部分指令集在创建时都没有考虑对虚拟化的支持。

5.11 并行与存储器层次结构

Cache的一致性

支持多处理器(核)共享一个物理地址空间

假设是写直达法，如果是写回法，情况更复杂

一致性（coherence）的定义

通俗的定义：读操作时总是返回最近写的值。

正式的定义：

• P写入X，P读X(之间无其它写操作)，读出的X是最近写入的值 （保证程序的顺序）

• P1写入X，其他处理器与X相对应的cache被更新（定义了存储器的一致性）

• P1写入X，P2写入X，所有处理器看到的都是相同的写入顺序（串行化写入）

监听协议

最常用的cache一致性协议：监听（snooping）协议

• 每个cache都监听总线上的读/写操作

• 每个cache和主存都在一个目录中记录数据块的共享状态

• 当处理器要写数据时，以独占方式对该数据块进行写：

  • 在总线上广播“写无效”信息
  • 随后在另一个读cache缺失时更新

Cache的原理