计算机系统结构 第五章 存储系统

5.1 存储系统介绍 存储系统 指计算机中由存放程序和数据的各种存储设备、 控制部件及管理信息调度的设备（硬件）和算法（ 软件）所组成的系统。 计算机系统中，一般使用具有层次结构的存储系 统，主要可分为三个存储层面：高速缓冲存储器、 主存储器和辅助存储器。 高速缓冲存储器主要用于改善主存储器与中央处 理器（CPU）的速度匹配问题，而辅助存储器则主要 用于扩大计算机系统的存储空间。

5.1.1 存储系统的层次结构 层次存储系统是指把各种不同存储容量、存取速度、 访问方式和单位存储价格的存储器，按照一定的层 次结构组成多层存储器，并通过管理软件和辅助硬 件有机组合成统一的存储体系，使计算机系统中使 用到的各种程序和数据层次的分布到各个存储器中。 辅助软硬件 主存 辅存 图5-1 主/辅存结构

多级存储体系 二级存储体系结构可以进一步扩展到多级存储层次 ，对CPU而言，存储系统是一个整体：越靠近CPU的 存储器存取速度越快，存储容量越小，也即下图中 M1的存取速度最接近于CPU，而存储系统总体容量 和单位存储价格接近于离CPU“最远”的Mn。

多级存储体系(续1)

5.1.2 存储系统的性能参数 存储器有三个主要的性能指标：存储容量、存取速 度、存储单位价格。 用户期望：期望存储器价格尽可能低，提供尽可能 高的存取速度和尽量大的存储容量。系统的观点， 计算机系统性能的发挥要求存储器存取速度与CPU相 匹配，而容量上又应尽可能装入所有系统和用户软 件；应用的观点，要求存储器的价格只能占整个计 算机系统硬件价格的一小部分。 矛盾的现实：存取速度越快，存储器的单位存储价 格就越高；在一定的单位存储价格下，存储容量越 大，存储器的总价就越高。

5.1.2 存储系统的性能参数(续1) 存储容量 引入虚拟存储系统，为计算机系统使用者另设额外 的虚拟地址空间，它既不是主存储器的地址空间， 也不是磁盘存储器的地址空间，是将主存和辅存的 地址空间统一编址，形成的一个庞大的存储空间。 单位存储价格 ，为使得C1 ≈ C2，则需要M2 » M1 存取速度和访问命中率 访问命中率，指CPU访问存储系统时在主存储器中一 次访问得到所需信息的概率。

5.2 高速缓冲存储器Cache 计算机系统为改善CPU与主存储器之间的速度匹配问 题，在CPU和主存储器之间加入一个高速、小容量的 缓冲存储器Cache，构成Cache—主存储器的存储系统 ，使得存储系统对CPU而言，速度接近于高速缓冲存 储器Cache，存储容量接近于主存储器。 Cache存储器主要由三个部分组成： (1)Cache存储器，用于存放由主存储器调入的指令与数据块； (2)地址转换部件，用于实现主存储器地址到Cache存储器地址 的转换； (3)替换部件，当缓存满时根据指定策略进行数据块替换，并对 地址转换部件做对应修改。

Cache工作原理

Cache工作原理(续1) 系统工作时，地址转换部件维护一个映射表，用于 确定Cache存储器中是否有所要访问的块，以及确定 其位置。该映射表中的每一项对应于Cache存储器的 一个分块，用于指出当前该块中存放的信息对应于 主存储器的哪个分块。 为提高CPU对Cache存储器的访问命中率，Cache存储 器的工作原理是基于程序访问局部性原理的，它不 断地将与当前指令集相关联的一部分后继指令集从 主存储器读取到Cache存储器，以供CPU访问，从而 达到存储系统与CPU速度匹配的目的。

Arm Cache 组织结构框图

5.2.2 地址映象与变换方法 地址映象是将主存储器中的数据分块按某种规则装 入Cache存储器中，并建立主存储器地址与Cache存储 器地址之间的对应关系。 地址变换是指当主存储器中的分块按照地址映象方 法装入Cache存储器后，在实际运行过程中，主存储 器地址如何转换成为相应的Cache存储器地址。 地址的映象和变换是紧密相关的，采用什么样的地 址映象方法，就有与这种映象方法相对应的地址变 换方法。 一般可分为以下几种类型： (1)全相联映象及其变换方法 (2)直接映象及其变换方法 (3)组相联映象及其变换方法

(1)全相联映象及其变换方法 全相联映象是指主存储器中的任意分块可以被放置 到Cache存储器中的任意一个位置。其中，主存储器 与Cache存储器的分块大小相同。 地址变换规则 映像规则

(2)直接映象及其变换方法 直接映象是指将主存储器中的某一分块在Cache存储器中 都有唯一对应的位置。主存储器按Cache大小分成若干区 ，在区内进行分块，分块大小与Cache存储器中分块大小 相等，主存储器中每个区包含分块的个数与Cache存储器 中分块的个数相等。 映像规则 地址变换规则

(3)组相联映象及其变换方法 组相联映象把主存储器和Cache按同样大小划分成块，再 将主存储器和Cache按同样大小划分成组，每一组由相同 的块数组成，然后将主存储器按Cache大小分成区，主存 储器每个区的组数与Cache的组数相同。 组相联映象在各组之间是直接映象，但组内各块之间是全 相联映象。

(3)组相联映象及其变换方法(续1) 映像规则 地址变换规则

5.2.3 Cache替换算法及实现 当CPU读Cache时，有两种可能： (一) 需要的数据已在Cache中，那么只需直接访问 Cache； (二)是需要的数据尚未装入Cache，则CPU从主存储 器中读取信息的同时，需按所需的映象规则将该地址所 在的那块存储内容从主存储器拷贝到Cache中。 对于第二种情况，若该块所映象的Cache块位置已全部 被占满，则必须选择将Cache中的某一块替换出去，需 要Cache替换算法解决如何选择被换出块的问题。

Cache替换算法 随机替换算法 随机法是Cache替换算法中最简单的一种。这种方法是随机地选 择可以被替换的一块进行替换。有些系统设置一个随机数产生 器，依据所产生的随机数选择替换块，进行替换。 先进先出替换算法(FIFO) 这种策略总是把最先调入的Cache块作为被替换的块替换出去。 最近最少使用替换算法(LRU) LRU法是依据各块的使用情况，总是选择最近最久没被使用的 块作为被替换的块进行替换。因为目前为止最久没有被访问的 块，很可能也是将来最少访问的块。

Cache替换算法(续1) 堆栈替换算法 堆栈替换算法使用栈顶到栈底各项的先后次序来记录Cache中或 Cache中同一组内各个块被访问的先后顺序。栈顶恒存放近期最 近被访问过的块的块号，栈底恒存放近期最久没有被访问过的 块的块号，即准备被替换掉的块的块号（LRU堆栈实现）。 比较对替换算法 LRU算法用一组硬件的逻辑电路记录同一组中各个块使用的时 间和次数， 然后按照各个块被访问过的时间顺序排序，从中找 出最久没有被访问过的块。用一个两态的触发器的状态来表示 两个块之间的先后顺序，再经过门电路就可以找到LRU块。

Cache替换算法(续2) 各种Cache替换算法的优缺点 (1)随机替换算法： (2)FIFO替换算法： 优点是由于它不需记录各个块的使用情况，实现起来也较容 易；缺点是虽然考虑到了各块进入Cache的先后顺序这一使用“ 历史”，但还不能正确地反映程序的局部性特点。 (3) LRU替换算法： LRU算法较好地反映了程序的局部性特点，失效率较低，但 LRU算法比较复杂，硬件实现较困难，特别是当组的大小增加 时，LRU的实现代价将越来越高。

5.2.4 cache一致性问题 由于Cache中保存的是主存储器的一部分副本，则有可 能在一段时间内，主存储器中某单元的内容与Cache中 对应单元的内容出现不一致。 例如： （1）CPU在写入Cache时，修改了Cache中某单元的内容，而 主存储器中对于单元的内容却可能没有改变，还是原来的。此时 ，如果I/O处理器或其他处理器要用到主存储器中的数据，则可能 会出现主存储器内容跟不上Cache对应内容的变化而造成的数据不 一致性错误。 （2）I/O处理机或其他处理机已修改了主存储器某个单元的 内容，而Cache中对于单元的副本内容却可能没有改变。这时，如 果CPU访问Cache并读取数据，也可能会出现Cache内容跟不上主 存储器对于内容的变化而产生的不一致性错误。

5.2.4 cache一致性问题(续1) 对于Cache中的副本与主存储器中的内容能否保持一致 ，是Cache能否可靠工作的一个关键问题。要解决这个 问题，首先要选择合适的Cache更新算法。 对Cache不一致性问题的解决，主要是需要更新主存储 器内容，一般有两种常用更新算法： (1)写回法：写回法也称拷回法。CPU执行“写”操作时，只把 信息写入Cache，而不写入主存储器，仅当该块需被替换时，才 相应Cache块写回到主存储器。 (2)写直达法：写直达法也称存直达法。CPU在执行“写”操作 时，不仅把信息写入到Cache，而且也写回主存储器，当某一块 需要被替换时，不必再写回到主存储器，只需要直接调入新块并 覆盖该块即可。

5.2.4 cache一致性问题(续2) 写回法与写直达法比较： (1)写回法较写直达法速度要快； (2)在可靠性方面，写回法不如写达法； (3)写直达法的控制较写回法简单； (4)写直达法易于实现，但硬件实现代价相对较大。 进行“写”操作时，也可能出现写不命中。由于“写”操作 并不需要访问该单元中的所有的数据，在出现Cache写 不命中时，无论写回法还是写直达法，都需要考虑在写 操作的同时是否将其调入Cache，一般有两种选择： (1)按写分配法：写失效时，除了完成写入主存储器外，还把该 写地址单元所在的块由主存储器调入Cache。 (2)不按写分配法：写失效时，只完成写入主存储器，而不把该 写地址单元所在的块从主存储器调入Cache。

5.2.5 Cache性能分析 评价Cache存储器，主要是看Cache命中率的高低，命中 率主要与下面几个因素有关： (4)采用组相联时组的大小等。

Cache友好代码

Cache友好代码(续1) 适当字节填充，减少缓冲不命中数量 Float x[8] Float x[12]

5.2.5 Cache性能分析(续1) Cache命中率与容量的关系 Cache的容量越大，则Cache的命中率将越高。

5.2.5 Cache性能分析(续2) Cache命中率与块大小的关系

5.2.5 Cache性能分析(续3) Cache命中率与组数的关系

5.2.5 Cache性能分析(续4) 从Cache系统加速比定义可以看出，Cache系统的加速 比与Cache的命中率H和主存储器访问周期Tm及Cache 访问周期Tc有关，而Cache系统中，主存储器的访问周 期和Cache的访问周期一般是一定的，所以只要提高 Cache的命中率，就可以获得较高的Cache系统加速比 ，提高存储系统的速度。

5.3 Cache性能的优化 除加速比定义衡量Cache存储系统性能外，Cache存储器 的平均访问时间是测评存储系统性能的一种更好的指标 ： 平均访问时间 = 命中时间 + 失效率*失效开销 从平均访问时间这一指标来看，还可以从3个方面对 Cache的性能进行优化： （1）降低Cache失效率 （2）减少失效开销 （3）减少命中时间

5.3.1降低Cache失效率的方法 Cache失效的原因分析： (3)冲突失效：在组相联映象或直接相联映象中，如 果太多的冲突块映象到同一组中，产生冲突，则可 能会出现某个块刚被替换出去，随后又重新访问而 被再次调入。

5.3.1降低Cache失效率的方法(续1) 增加Cache块大小

5.3.1降低Cache失效率的方法(续2) 增加Cache容量 Cache容量越大，命中率越高，相关，失效率则越 低。但增加Cache容量不仅会增加成本，而且也可能会 因为复杂的电路结构等而增加Cache的访问时间。 指令和数据硬件预取 指令和数据硬件预取是指在处理器访问指令和数据 之前，就把它们预取到Cache中或预取到可以比存储器 访问速度更快的外部缓冲区中。 指令预取一般有恒预取和不命中预取两种方法。

5.3.1降低Cache失效率的方法(续3) 编译器控制预取 硬件预取的一种替代方法是在编译时加入预取指令，在 数据被使用之前发出预取请求。有以下两种方式： (1)寄存器预取：将数据预取到寄存器中。 (2)Cache预取：只将数据预取到Cache中，并不放入寄存器。 编译器优化以降低Cache失效率 这种方法是采用软件方法来优化Cache性能，试图通过 优化编译时间来改善Cache性能： (1)程序代码和数据重组 (2)循环交换 (3)分块

5.3.2 减少Cache失效开销 与降低失效率一样，减少Cache失效开销同样可以缩短 Cache存储器的平均访问时间并提高Cache的性能。 (1)采用两级Cache：在原Cache和存储器之间增加 一级Cache，构成两级Cache。其中第一级Cache可以让 它小到足以与快速的处理器运行时钟周期相匹配，而 第二级Cache则让它大到足以捕获到对内存进行的大多 数访问，从而有效地降低了失效开销。 (2)让读失效优先于写：提高写直达Cache性能最重 要的方法是设置一个容量适中的写缓存。然而写缓存 中可能包含读失效时所需单元的最新值，这个值尚未 写入存储器，导致了存储器访问的复杂化。解决方法 是让读失效等待，直至写缓存为空。

5.3.2 减少Cache失效开销(续1) 合并写缓冲区 请求字处理技术 处理器在同一时刻只需要调入块中的一个字(即请求 字)，不必等到全部的块调入Cache，就可以将该字送往 处理器并重新启动处理器进行访问，一般有以下两种策 略： (1)请求字优先：调块时，先向存储器请求处理器所要的请求字。一 旦该请求字到达即送往处理器，让处理器继续执行，同时可以从存 储器中调入该块的其他字。 (2)提前重启动：在请求字没到达处理器时，处理器处于等待状态。

5.3.3 减少命中时间 除了通过降低失效率和减少失效开销来优化Cache性能 的方法以外，还可通过减少命中时间来优化Cache的性 能。命中时间也是平均访问时间的一个组成部分，它的 重要性在于它会影响处理器的时钟频率。 (1)小而简单的Cache减少命中时间 采用容量小、结构简单的Cache，这样快表较小，查 表的速度较快，从而有效地提高了Cache的访问速度。 (2)路预测减少命中时间 路预测要求Cache中预留特殊的比较位，用来预测下 一次访问Cache时可能会用到的路或块。

5.3.3 减少命中时间(续1) (3)踪迹Cache(Trace Cache)减少命中时间 踪迹Cache中存储的是处理器所执行的动态指令序 列，而不是用于存储主存储器中给出的静态指令序列。 L例如，在Pentium4处理器的踪迹Cache中由于使用了译 码微操作，从而节省了译码时间。 (4)流水线Cache访问 流水线Cache访问方法是将流水线、Cache访问以及 使一级Cache命中时的有效时延分散到几个时钟周期。 它实际上并不能真正减少Cache命中时间，但可以提供 较短的周期时间和高宽带。

5.4 主存储器及性能优化 主存储器也即主存，是存储层次中紧接着Cache下面的一 个层次。它是计算机硬件的一个重要部件，其作用是存 放指令和数据，并能由中央处理器直接随机存取。 它既被用来满足Cache的请求，也被用作I/O接口。 主存的性能指标主要是存储容量、存取时间、存储周期 和存储器带宽。 存储容量是指在一个存储器中可以容纳的存储单元总数 ；存取时间是指从启动到完成一次存储器操作所经历的 时间；存储周期是指连续启动两次操作所需间隔的最小 时间；存储器带宽是指单位时间里存储器所存取的信息 量。

5.4.1 主存储器 目前，就主存的速度来看，仍不能满足CPU的要求，这 是因为主存速度的改进跟不上CPU速度的提高。 Cache的引入，在很大程度上弥补了主存和CPU速度上 的巨大差距。 主存的延迟因影响Cache的失效开销而成为Cache主要关 心的问题，另外，随着第二级Cache的广泛应用，主存 带宽对于Cache来说也越来越重要了。 在有Cache的存储层次中，主存的性能主要是用主存的 延迟和带宽来衡量的。

5.4.2 主存储器性能优化 增加存储器的宽度 增加数据带宽可以增加同时访问的数据量，提高数 据的吞吐量，最简单的方法是增加存储器的宽度。 第一级Cache的宽度通常为一个字，因为CPU大部 分的访存都是一个字的宽度的。在不具有第二级Cache 的计算机系统中，主存的宽度一般与Cache的宽度相同 。因此，可以将Cache和主存的宽度同时增加为原来宽 度的两倍或以上，从而增加了主存的宽度。

5.4.2 主存储器性能优化(续1) 多体交叉存储器 采用模m多体交叉编址，利用多体潜在的并行性进行 并行存取。其中每个存储体的宽度一般为一个字的宽 度，通过同时向多个个体发送地址对它们同时进行访 问，从而一次可以读或者写多个字。 有两种基本的多体交叉方法：高位多体交叉方法和低 位多体交叉方法。

5.4.2 主存储器性能优化(续2) 高位多体交叉方法 高位交叉存储器的地址高位部分用于区分不同的存 储体，低位部分用于选择一个存储体体内不同的存 储单元。

5.4.2 主存储器性能优化(续3) 低位多体交叉方法 低位交叉存储器的地址位使用方法与高位交叉存储 器刚好相反：低位部分用于区分不同的存储体，高 位部分用于选择一个存储体体内不同的存储单元。

5.5 虚拟存储器 虚拟存储器是由主存和联机的外存共同组成的，在主存 的容量不能满足要求时，数据可存放在外存中，但在程 序中仍按地址进行访问外存空间。 在虚拟存储器中，应用程序员是直接用机器指令的地址 码对整个程序统一编址的，虚拟存储器的空间大小取决 于它能产生的地址位数。 从程序员的角度看，存储空间扩大了，并可以放得下整 个程序，程序不必作任何修改就可以以接近于实际主存 的速度在这个虚拟存储器上运行。

5.5.1 虚拟存储器工作原理 根据采用的存储映象算法，可以将虚拟存储器的管理方 式分为段式、页式和段页式3种。 段式管理 将主存按段分配的存储管理方式称为段式管理。对 于一个复杂的程序可以分解为多个逻辑上相当独立的模 块。这些模块可以是主程序，各种子程序，也可以是表 格、向量、数组等。每个模块都是一个单独的程序段， 都从0地址开始相对编址，段的长度可长可短，甚至可 以事先无法确定。在段式管理的系统中，当某程序段由 辅存调入主存时，系统在主存中给该段分配一块空间， 并给出基址(即该段在主存中的起始地址)，由基址和每 个单元在段内的相对位移量就可以形成这些单元在主存 中各自的实际地址，进行访问。

5.5.1 虚拟存储器工作原理(续1) 在段式管理中，每一道程序都有一个段表，用以指明各 段在主存中的状态信息。 段表中包括段号(或段名)、段长和起始位置等信息。断 号字段用于存放程序段的断号或名称，如果断号是连续 的，则断号这一字段信息可以去掉，直接根据起始位置 和段长来实现程序段到主存储器的映象。 段长是该段的长度，可用于访问地址的越界检查。起始 地址用于存放该程序段装入主存中的起始(绝对)地址。 此外，还可能会设置一个装入位来指示该段是否已装入 主存，如装入位为“1”，表示已装入；为“0”，表示尚未 装入。

5.5.1 虚拟存储器工作原理(续2) 段式管理地址映像方法和地址变换方法

5.5.1 虚拟存储器工作原理(续3) 段式虚拟存储器的主要优点: (1)程序的模块性能较好。 (2)分段还便于程序和数据的共享。 (3)容易以段为单位实现存储保护。 (4)程序的动态链接和调度比较容易。 段式虚拟存储器的主要缺点： (1)地址变换费时。 (2)主存储器利用率低。 (3)对辅存管理较困难。

5.5.1 虚拟存储器工作原理(续4) 页式管理 页式存储是将虚拟存储空间和实际的存储空间都等 分成固定大小的页，各虚拟页可以装入到主存中不同的 页面位置。页是一种逻辑上的划分，页面的大小随机器 而异。目前，一般计算机系统中，页的大小通常指定为 磁盘存储器物理块大小的整数倍。 在虚拟存储器中，虚拟地址空间中划分的页称为虚 页，主存地址空间中划分的页称为实页。则页式管理的 地址映象就是完成虚拟地址空间中的虚页到主存地址空 间中的实页的变换。页式管理用一个页表，其中包括页 号、主存页号等。页号一般用于存放该页在页表中的页 号(或行号)，因此可以省略；页的长度是固定的，因此 也省略了。页表中也可以设置一些标志位，如装入位、 修改位等。

5.5.1 虚拟存储器工作原理(续5) 页式管理地址映像方法和地址转换方法

5.5.1 虚拟存储器工作原理(续6) 页式虚拟存储的主要优点： (1)主存的利用率高。 (2)页表相对简单。 (3)地址映象与变换速度较快。 (4)对辅存的管理比较容易。 页式虚拟存储的主要缺点： (1)程序的模块化性能不好。由于用户程序被强制按固定 大小的页来划分，因此一页可能是程序段的某一部分， 也可能包含了两个或两个以上的程序段。 (2)页表很长，从而要占用很大的存储空间。

5.5.1 虚拟存储器工作原理(续7) 段页式管理 段式管理和页式管理各有其优缺点，段页式管理则 是将两者结合起来，同时利用段式管理在程序模块化 方面的优点和页式管理在管理主存和辅存方面的优点 。 将主存储器的物理空间等分成固定大小的页，将虚 拟存储空间中的程序按模块分段，每个段又分成与主 存页面大小相同的页。

5.5.1 虚拟存储器工作原理(续8) 段页式管理地址映像方法和地址转换方法

5.5.2 地址映像与转换 当把大的虚存空间中的内容压缩到小的主存空间中去， 则主存中的每一个页或段必须与多个虚拟存储空间中的 页或段相对应。 主存中的一个实页要对应多少个实页与采用的映象方式 有关。此时，就不可避免地发生两个以上的虚页想要进 入主存中同一个页面位置的现象，这种现象称为页面争 用或实页冲突。一旦发生实页冲突，只能首先装入其中 的一个虚页，等到不再需要这个虚页时才可装入其它的， 从而导致了执行效率的下降。因此，映象方式的选择主 要应考虑能否尽量减小实页冲突概率。 操作系统一般都允许将每道程序的任何虚页可以映象到 任何实页位置，即全相联映象。仅当一个任务要求同时 调入主存的页面超出主存页数时，两个虚页才会争用同 一个实页位置。因此，全相联映象的实页冲突率最低。

5.5.3 内部地址变换优化 在虚拟存储系统中，如果不采取有效的措施，则访问主存储器的速 度要降低很多。造成这个速度降低的主要原因是：每次进行访存时 ，都必须进行内部地址变换，其概率为100%。所以，如何加快用 户虚地址到主存实地址的变换，是缩短访存时间的关键。只要内部 地址的变换速度高到使整个系统的访存速度非常接近于不采用虚拟 存储器时的访存速度，虚拟存储器的性能才能真正实现。 在虚拟存储器进行地址变换时，首先必须查段表或页表，或既查段 表也查页表，来完成虚地址到实地址相应的转换。由于页表容量较 大且存放在主存中，因此每访存一次，还需因查表而加一次访存； 如果采用的是段页式虚拟存储器，则需因两次查表而加两次访存。 结果是主存储器的访问速度比不采用虚拟存储器的访存速度要慢2 到3倍。 如何提高页表的访问速度？

5.5.3 内部地址变换优化(续1) 快表 根据程序的局部性特点，对页表内各项的访问并不 完全是随机的。在一段时间内，实际可能只用到表中 很少的几项。因此，应该重点提高使用概率较高的这 部分页表的访问速度。可以使用快速硬件来构成比全 表小得多的表，表中存放的是近期经常要使用的页表 项，这个表称为“快表”。 相应地，原先存放全部虚地址和实地址之间映象关系 的表还是存放在主存中，将其称为“慢表”。

5.5.3 内部地址变换优化(续2) 具有快表的地址转换方法

5.5.3 内部地址变换优化(续3) 快表的存在对所有的程序员都是透明的。 实际上，快表与慢表也构成了一个两级存储层次， 其访问速度接近于快表的速度，存储容量却是慢表 的容量。当然，快表的命中率如果不高，则系统的 效率就会大大降低。 要提高快表的命中率，最直接的办法是增加快表的 容量。快表的容量越大，其命中率就越高；但容量 越大时，其相联查找的速度就越慢。所以，快表的 命中率和查表速度是矛盾的。

5.5.3 内部地址变换优化(续4) 为了提高查找速度，可以减少相联比较的位数。 在同样容量的情况下，相联比较的位数越少，则相联查 找所花费的时间就会越少。 例如，将虚地址中参与相联比较位中的用户字段u去掉， 这是因为快表在一段时间内总是对应于同一个任务或用 户，它们的u值是不变的。这样，相联比较的位数就减少 了一位，查找速度也相应地提高了。 但是，这种方法会降低快表的命中率，降低虚、实地址 的变化速度。 也可以采用普通的按地址来访问，可以使用顺序查找法 、对分查找法和散列查找法等。

5.5.3 内部地址变换优化(续5) 目前，计算机系统都采用相联寄存器组、硬件的散 列压缩、快慢表结构和多个相等比较器等方法，来 提高系统的性能。

5.5.4 页面替换算法及实现 同高速缓冲存储器一样，在虚拟存储器中，当访问 的指令和数据不在主存时，发生页面失效，需要从 辅存中将包含该指令或数据的一页（或一段）调入 到主存储器中。 虚存空间比主存空间大得多，必然也会出现主存中 所有页面都已经被占用，或者所有主存空间都已经 被占用的情况，这时，如果继续把辅存中一页调入 主存，就会发生实页冲突。此时，只有从主存空间 中选出一页替换出去，让出空间来接纳新调入的页。 应该选择哪一页进行替换呢？这就是页面替换算法 要解决的问题。

5.5.4 页面替换算法及实现(续1) 页面替换算法 (1)随机算法 随机算法是将软的或硬的随机数产生器产生的随机数作为主存储 器中被替换的页的页号。这种算法最简单，且易于实现。但是，没 有利用主存储器中页面使用情况的“历史”信息，也没有反映程序的 局部性特点，从而命中率较低，较少被使用。 (2)先进先出算法 选择最早被调入主存储器的页作为被替换的页。它的优点是实现 容易，并利用了主存储器中页面使用情况的“历史”信息，但是，不 能正确反映程序的局部性。因为最先进入主存的页很可能也是现在 经常要使用的页。

5.5.4 页面替换算法及实现(续2) (3)近期最少使用算法，即LFU算法 3/11/2017 (3)近期最少使用算法，即LFU算法 选择近期最少被访问的页作为被替换的页。该算法能比较 正确地反映程序的局部性。 (4)最优替换算法，即OPT算法 选择将来一段时间内最久不被访问的页作为被替换的页。

5.5.4 页面替换算法及实现(续3) 页面替换算法性能分析：同一地址流命中率比较

5.5.4 页面替换算法及实现(续4) 页面替换算法性能分析：命中率与与地址流关联关系

5.5.4 页面替换算法及实现(续5) 堆栈型算法 对任意一个页面地址流，设t为已经处理过 个页 面的时间点，m为分配给该地址流的主存页面数， 为在t时间点，在m页的主存中的页面集合。如果对 此页地址流作两次主存页面数分配，分别分配m个和 n个主存页面，并且当 时，如果替换算法满足：在任 何时刻t，Bt有以下关系：

5.5.4 页面替换算法及实现(续6) 堆栈型替换算法的命中率随着分配给该程序的主存 页面数增加而提高，至少不会下降。 对堆栈型替换算法，只需采用堆栈处理技术对地址 流模拟处理一次，即可同时获得对此地址流在不同 主存页数时的命中率，从而大大节省了存储体系设 计的工作量。 在多道程序的系统中，可以采用一种动态算法：页 面失效频率法，来提高系统的性能。 具体实现方法是：根据各道程序实际运行中主存页 面失效率的高低情况，由操作系统动态地调节分配 给各道程序的实页数。当一道程序的主存页面命中 率低于某个限定值时就自动地增加分配给该程序的 主存实页数，以提高命中率。

5.5.5 提高主存命中率的方法 通常，影响主存命中率的主要因素有： (1)程序在执行过程中的页地址流分布情况； (2)所采用的替换算法； (3)页面大小； (4)主存容量； (5)所采用的页面调度方法。

5.5.5 提高主存命中率的方法(续1) 页面大小的选择 与Cache命中率与页面大小的关系一样，主存命 中率与页面大小的关系也不是线性的。页面大小还 与主存容量、程序的页地址流分布情况等因素有关 。

5.5.5 提高主存命中率的方法(续2) 主存容量 与Cache类似，当主存容量增加时，主存命中率 也会相应地提高。

5.5.5 提高主存命中率的方法(续3) 页面调度方法，页面调度就是系统给用户分配主存页面 数的过程。 一般有三种方式： (1)分页方式: 将整个程序先链接装配，将整个程序装入主存后才运行，其命中 率为100%，但是主存的利用率较低； (2)请求页式: 在发生页面失效时，才将所需要的页装入主存。其主存的利用率 很高，但命中率将受到频繁的页面替换的影响； (3)预取式: 根据程序的局部性特点，在程序被挂起之后又重新开始运行之前 ，预先调入相关的页面。这种方法可能会因为预先调入的页面用不 上而造成时间和空间上的浪费。

5.6 进程保护和虚拟存储器实例 在多道程序中，计算机资源可以被多道同时运行的 用户程序所共享。 为使系统能够正常工作，应防止由于一个用户程序 出错而破坏主存中其他用户的程序和数据，还要防 止一个用户不合法地访问主存中不是分配给它的存 储区域而造成对系统的破坏，即使这种访问不会引 起破坏也是不允许的。 操作系统和系统结构需要为存储系统的安全提供保 护手段。

5.6.1 进程保护 保证进程的正确和安全运行既是系统设计者也是操 作系统设计者的责任。 保护的手段主要是：将主存区域分为几个区域，使 得主存中可以同时存放多个不同进程的状态；并对 每个存储区域进行保护，使一个进程的信息不被另 一个进程所修改。 存储系统的保护分为： (1)存储区域的保护，可用一对寄存器(即界限寄 存器)来检查每一个地址，以确保地址在两个界限之 间。 (2)访问保护，由系统软件设置用户进程访存的地 址上下界，禁止了访问越界。

5.6.1 进程保护(续1) 在虚拟存储系统中，由于用户程序的访问空间映射 到主存后将不是一个连续的地址空间，而将分部在 主存中的各个页面，因此不适用以上述保护方式。 在虚拟存储系统中，将采用更细微的方法： (1)映射表保护法，利用映射表的映射关系来限 制用户程序的访问地址空间，用户程序不能访问映 射表上找不到的主存页面，从而起到保护作用。 (2)键保护，由操作系统根据主存使用分配的情 况，给主存中的每一页分配一个存储键，相当于保 护锁。所有页的存储键是在主存相应的快速寄存器 内，当用户访问这些页面时，需要一个访问键，相 当于钥匙，来打开这把锁。

5.6.1 进程保护(续2) (3)环保护，把系统程序和用户程序按其重要性及其 访问权限进行分层。最内的几层是系统程序的分层 ，之外的几层是同一用户程序的分层，保护级别由 里向外逐层降低。

5.6.2 Alpha 21064存储管理 Alpha处理机的系统结构采用段页相结合的方式，既提 供了存储保护，又将页表减少到最小。 Alpha根据64位地址的最高两位将地址空间分为3个段： seg0(最高位63位为0)，seg1(最高两位63和62位都为1)和 kseg(最高位63位为1，次高位62位为0)。 其中，seg0用于存储用户代码和堆，seg1用作用户栈， kseg是操作系统内核段。 kseg是留给操作系统内核使用的，并且整个空间具有相 同的保护权限，不需要存储管理。 seg0和seg1是用户进程使用的，它们所映射到的各个页 面具有不同的保护权限。

5.6.2 Alpha 21064存储管理(续1) seg0段和seg1段的布局结构

5.6.2 Alpha 21064存储管理(续2) 为使页表大小更合理，Alpha采用三级分层页表结构 ，64位地址除了高位用于段选择的两位，其余的位 则用于表示虚地址。 虚地址中有3个域：V1、V2、V3，分别是：一级页 表项偏移，二级页表项偏移、三级页表项偏移，这 三个域分别用于查找这三级页表。 另外，还有一个页内偏移量字段。

5.6.2 Alpha 21064存储管理(续3) Alpha虚地址向物理地址的变化过程

5.7 Alpha 21264存储层次结构

5.7 Alpha 21264存储层次结构(续1) Alpha 21264片上和片外高速缓存提供了特别低的数据 延迟访问能力，允许很高的数据访问带宽。 Alpha21264中设有两级cache：一级cache和二级cache。 由于带宽的原因，三级cache在Alpha 21264中没有被采 用。 一级cache被分割成独立的caches来存储指令和数据， 分别为I-cache(指令缓存) 和D-cache(数据缓存)，这两 个caches都有64KB的容量； 二级cache是一个外部cache，有1到16MB容量。

5.7 Alpha 21264存储层次结构(续2) 21264是乱序执行的，它允许执行指令的顺序和取指令 的顺序不同，实际上做到了指令只要有可能就执行。 每个周期最多可以取四个指令和执行6条指令，通过对 这些指令进行处理来加速执行速度。 Alpha 21264还采用推理执行方法，即使在不能立即知道 哪一条指令将处于最后的执行路径的情况下，Alpha 21264仍然可以用推理的方法取指令和执行指令。 例如，当21264 动态预测出分支方向并且沿着这条预测 路径进行推理执行时，这种方法将特别有用。21264可 以使用48位虚地址和44位物理地址，或者使用43位虚地 址和41位物理地址。其中，物理地址空间被分为相等的 两个部分，低地址部分用于内存地址，高地址部分用于 I/O地址。

5.7 Alpha 21264存储层次结构(续3) 当Alpha启动时，芯片上的硬件从一个外部PROM加 载指令cache，同时串行接口也会加载其他一些配置 信息，这样初始化可以使指令cache省去有效位，因 为这时cache中的指令都是有效的。 预装载的指令在优先级结构库(PAL)模式下运行。 PLA代码执行时，禁止异常发生，因此回避了TLB， 所以由于不受存储管理的限制，取指令时不进行对 存储访问的权限检查。 一旦操作系统准备好执行一个用户程序，它将PC置 为指向seg0段的相应地址。