1、,计算机系统结构,第五章 存储系统,5.1 存储系统介绍,存储系统 指计算机中由存放程序和数据的各种存储设备、控制部件及管理信息调度的设备（硬件）和算法（软件）所组成的系统。 计算机系统中，一般使用具有层次结构的存储系统，主要可分为三个存储层面：高速缓冲存储器、主存储器和辅助存储器。 高速缓冲存储器主要用于改善主存储器与中央处理器（CPU）的速度匹配问题，而辅助存储器则主要用于扩大计算机系统的存储空间。,5.1.1 存储系统的层次结构,层次存储系统是指把各种不同存储容量、存取速度、访问方式和单位存储价格的存储器，按照一定的层次结构组成多层存储器，并通过管理软件和辅助硬件有机组合成统一的存储体系
2、，使计算机系统中使用到的各种程序和数据层次的分布到各个存储器中。,图5-1 主/辅存结构,多级存储体系,二级存储体系结构可以进一步扩展到多级存储层次，对CPU而言，存储系统是一个整体：越靠近CPU的存储器存取速度越快，存储容量越小，也即下图中M1的存取速度最接近于CPU，而存储系统总体容量和单位存储价格接近于离CPU“最远”的Mn。,多级存储体系(续1),5.1.2 存储系统的性能参数,存储器有三个主要的性能指标：存储容量、存取速度、存储单位价格。用户期望：期望存储器价格尽可能低，提供尽可能高的存取速度和尽量大的存储容量。系统的观点，计算机系统性能的发挥要求存储器存取速度与CPU相匹配，而容量
3、上又应尽可能装入所有系统和用户软件；应用的观点，要求存储器的价格只能占整个计算机系统硬件价格的一小部分。矛盾的现实：存取速度越快，存储器的单位存储价格就越高；在一定的单位存储价格下，存储容量越大，存储器的总价就越高。,5.1.2 存储系统的性能参数(续1),存储容量引入虚拟存储系统，为计算机系统使用者另设额外的虚拟地址空间，它既不是主存储器的地址空间，也不是磁盘存储器的地址空间，是将主存和辅存的地址空间统一编址，形成的一个庞大的存储空间。单位存储价格 ，为使得C1 C2，则需要M2 M1存取速度和访问命中率访问命中率，指CPU访问存储系统时在主存储器中一次访问得到所需信息的概率。,5.2 高速
4、缓冲存储器Cache,计算机系统为改善CPU与主存储器之间的速度匹配问题，在CPU和主存储器之间加入一个高速、小容量的缓冲存储器Cache，构成Cache主存储器的存储系统，使得存储系统对CPU而言，速度接近于高速缓冲存储器Cache，存储容量接近于主存储器。Cache存储器主要由三个部分组成：(1)Cache存储器，用于存放由主存储器调入的指令与数据块；(2)地址转换部件，用于实现主存储器地址到Cache存储器地址的转换；(3)替换部件，当缓存满时根据指定策略进行数据块替换，并对地址转换部件做对应修改。,Cache工作原理,Cache工作原理(续1),系统工作时，地址转换部件维护一个映射表，
5、用于确定Cache存储器中是否有所要访问的块，以及确定其位置。该映射表中的每一项对应于Cache存储器的一个分块，用于指出当前该块中存放的信息对应于主存储器的哪个分块。为提高CPU对Cache存储器的访问命中率，Cache存储器的工作原理是基于程序访问局部性原理的，它不断地将与当前指令集相关联的一部分后继指令集从主存储器读取到Cache存储器，以供CPU访问，从而达到存储系统与CPU速度匹配的目的。,Arm Cache 组织结构框图,5.2.2 地址映象与变换方法,地址映象是将主存储器中的数据分块按某种规则装入Cache存储器中，并建立主存储器地址与Cache存储器地址之间的对应关系。地址变换
6、是指当主存储器中的分块按照地址映象方法装入Cache存储器后，在实际运行过程中，主存储器地址如何转换成为相应的Cache存储器地址。地址的映象和变换是紧密相关的，采用什么样的地址映象方法，就有与这种映象方法相对应的地址变换方法。一般可分为以下几种类型：(1)全相联映象及其变换方法(2)直接映象及其变换方法(3)组相联映象及其变换方法,(1)全相联映象及其变换方法,全相联映象是指主存储器中的任意分块可以被放置到Cache存储器中的任意一个位置。其中，主存储器与Cache存储器的分块大小相同。,映像规则,地址变换规则,(2)直接映象及其变换方法,直接映象是指将主存储器中的某一分块在Cache存储器
7、中都有唯一对应的位置。主存储器按Cache大小分成若干区，在区内进行分块，分块大小与Cache存储器中分块大小相等，主存储器中每个区包含分块的个数与Cache存储器中分块的个数相等。,映像规则,地址变换规则,(3)组相联映象及其变换方法,组相联映象把主存储器和Cache按同样大小划分成块，再将主存储器和Cache按同样大小划分成组，每一组由相同的块数组成，然后将主存储器按Cache大小分成区，主存储器每个区的组数与Cache的组数相同。组相联映象在各组之间是直接映象，但组内各块之间是全相联映象。,(3)组相联映象及其变换方法(续1),映像规则,地址变换规则,5.2.3 Cache替换算法及实现
8、,当CPU读Cache时，有两种可能： (一) 需要的数据已在Cache中，那么只需直接访问Cache； (二)是需要的数据尚未装入Cache，则CPU从主存储器中读取信息的同时，需按所需的映象规则将该地址所在的那块存储内容从主存储器拷贝到Cache中。对于第二种情况，若该块所映象的Cache块位置已全部被占满，则必须选择将Cache中的某一块替换出去，需要Cache替换算法解决如何选择被换出块的问题。,Cache替换算法,随机替换算法随机法是Cache替换算法中最简单的一种。这种方法是随机地选择可以被替换的一块进行替换。有些系统设置一个随机数产生器，依据所产生的随机数选择替换块，进行替换。先
9、进先出替换算法(FIFO)这种策略总是把最先调入的Cache块作为被替换的块替换出去。最近最少使用替换算法(LRU) LRU法是依据各块的使用情况，总是选择最近最久没被使用的块作为被替换的块进行替换。因为目前为止最久没有被访问的块，很可能也是将来最少访问的块。,Cache替换算法(续1),堆栈替换算法堆栈替换算法使用栈顶到栈底各项的先后次序来记录Cache中或Cache中同一组内各个块被访问的先后顺序。栈顶恒存放近期最近被访问过的块的块号，栈底恒存放近期最久没有被访问过的块的块号，即准备被替换掉的块的块号（LRU堆栈实现）。比较对替换算法LRU算法用一组硬件的逻辑电路记录同一组中各个块使用的时
10、间和次数， 然后按照各个块被访问过的时间顺序排序，从中找出最久没有被访问过的块。用一个两态的触发器的状态来表示两个块之间的先后顺序，再经过门电路就可以找到LRU块。,Cache替换算法(续2),各种Cache替换算法的优缺点(1)随机替换算法： 优点是简单，容易实现；缺点是没有考虑到Cache块的使用历史情况，没有利用程序的局部性特点，从而命中率较低，失效率较高。(2)FIFO替换算法： 优点是由于它不需记录各个块的使用情况，实现起来也较容易；缺点是虽然考虑到了各块进入Cache的先后顺序这一使用“历史”，但还不能正确地反映程序的局部性特点。(3) LRU替换算法： LRU算法较好地反映了程序
11、的局部性特点，失效率较低，但LRU算法比较复杂，硬件实现较困难，特别是当组的大小增加时，LRU的实现代价将越来越高。,5.2.4 cache一致性问题,由于Cache中保存的是主存储器的一部分副本，则有可能在一段时间内，主存储器中某单元的内容与Cache中对应单元的内容出现不一致。 例如： （1）CPU在写入Cache时，修改了Cache中某单元的内容，而主存储器中对于单元的内容却可能没有改变，还是原来的。此时，如果I/O处理器或其他处理器要用到主存储器中的数据，则可能会出现主存储器内容跟不上Cache对应内容的变化而造成的数据不一致性错误。 （2）I/O处理机或其他处理机已修改了主存储器某个
12、单元的内容，而Cache中对于单元的副本内容却可能没有改变。这时，如果CPU访问Cache并读取数据，也可能会出现Cache内容跟不上主存储器对于内容的变化而产生的不一致性错误。,5.2.4 cache一致性问题(续1),对于Cache中的副本与主存储器中的内容能否保持一致，是Cache能否可靠工作的一个关键问题。要解决这个问题，首先要选择合适的Cache更新算法。对Cache不一致性问题的解决，主要是需要更新主存储器内容，一般有两种常用更新算法： (1)写回法：写回法也称拷回法。CPU执行“写”操作时，只把信息写入Cache，而不写入主存储器，仅当该块需被替换时，才相应Cache块写回到主存
13、储器。 (2)写直达法：写直达法也称存直达法。CPU在执行“写”操作时，不仅把信息写入到Cache，而且也写回主存储器，当某一块需要被替换时，不必再写回到主存储器，只需要直接调入新块并覆盖该块即可。,5.2.4 cache一致性问题(续2),写回法与写直达法比较：(1)写回法较写直达法速度要快；(2)在可靠性方面，写回法不如写达法；(3)写直达法的控制较写回法简单；(4)写直达法易于实现，但硬件实现代价相对较大。进行“写”操作时，也可能出现写不命中。由于“写”操作并不需要访问该单元中的所有的数据，在出现Cache写不命中时，无论写回法还是写直达法，都需要考虑在写操作的同时是否将其调入Cache
14、，一般有两种选择： (1)按写分配法：写失效时，除了完成写入主存储器外，还把该写地址单元所在的块由主存储器调入Cache。 (2)不按写分配法：写失效时，只完成写入主存储器，而不把该写地址单元所在的块从主存储器调入Cache。,5.2.5 Cache性能分析,评价Cache存储器，主要是看Cache命中率的高低，命中率主要与下面几个因素有关：(1)程序在执行过程中的地址流分布情况，其中地址流的分布情况是由程序本身决定的；可通过编写适应Cache的代码；(2)当发生Cache块失效时，所采用的替换算法；(3)Cache的容量，块的大小、块的总数；(4)采用组相联时组的大小等。,Cache友好代码
15、,Cache友好代码(续1),适当字节填充，减少缓冲不命中数量,Float x8,Float x12,5.2.5 Cache性能分析(续1),Cache命中率与容量的关系Cache的容量越大，则Cache的命中率将越高。,5.2.5 Cache性能分析(续2),Cache命中率与块大小的关系在采用组相联映象方式的Cache中，当Cache的容量一定时，块的大小也会影响命中率。,5.2.5 Cache性能分析(续3),Cache命中率与组数的关系当Cache的容量一定时，分组的数目对于Cache命中率的影响也是很明显的：组数分得越多，命中率会下降，命中率会随着组数的增加而下降；当组数不太大时，命
16、中率降低得相当少；当组数超过一定数量时，命中率下降非常快。Cache系统加速定义：,5.2.5 Cache性能分析(续4),从Cache系统加速比定义可以看出，Cache系统的加速比与Cache的命中率H和主存储器访问周期Tm及Cache访问周期Tc有关，而Cache系统中，主存储器的访问周期和Cache的访问周期一般是一定的，所以只要提高Cache的命中率，就可以获得较高的Cache系统加速比，提高存储系统的速度。,5.3 Cache性能的优化,除加速比定义衡量Cache存储系统性能外，Cache存储器的平均访问时间是测评存储系统性能的一种更好的指标： 平均访问时间 = 命中时间 + 失效率
17、*失效开销从平均访问时间这一指标来看，还可以从3个方面对Cache的性能进行优化： （1）降低Cache失效率 （2）减少失效开销 （3）减少命中时间,5.3.1降低Cache失效率的方法,Cache失效的原因分析：(1)强制性失效：对块第一次访问，该块不在Cache中，需从主存储器中将该块调入Cache中。(2)容量失效：如果程序执行时，Cache容纳不了所需的所有块，则会发生容量失效。当某些块被替换后，可能随后重新访问又被调入。(3)冲突失效：在组相联映象或直接相联映象中，如果太多的冲突块映象到同一组中，产生冲突，则可能会出现某个块刚被替换出去，随后又重新访问而被再次调入。,5.3.1降低
18、Cache失效率的方法(续1),增加Cache块大小 Cache命中率和块大小的关系：在Cache容量一定时，当块大小开始增加时，命中率也开始增加，但当增加到一定程度后，命中率反而开始下降。 失效率和命中率是两个相关的概念，命中率增加时，失效率下降；命中率下降时，失效率反而增加。另外，Cache容量越大，则使失效率达到最低的块大小就越大。,5.3.1降低Cache失效率的方法(续2),增加Cache容量 Cache容量越大，命中率越高，相关，失效率则越低。但增加Cache容量不仅会增加成本，而且也可能会因为复杂的电路结构等而增加Cache的访问时间。指令和数据硬件预取 指令和数据硬件预取是指在
19、处理器访问指令和数据之前，就把它们预取到Cache中或预取到可以比存储器访问速度更快的外部缓冲区中。指令预取一般有恒预取和不命中预取两种方法。,5.3.1降低Cache失效率的方法(续3),编译器控制预取 硬件预取的一种替代方法是在编译时加入预取指令，在数据被使用之前发出预取请求。有以下两种方式：(1)寄存器预取：将数据预取到寄存器中。(2)Cache预取：只将数据预取到Cache中，并不放入寄存器。编译器优化以降低Cache失效率这种方法是采用软件方法来优化Cache性能，试图通过优化编译时间来改善Cache性能：(1)程序代码和数据重组(2)循环交换(3)分块,5.3.2 减少Cache失
20、效开销,与降低失效率一样，减少Cache失效开销同样可以缩短Cache存储器的平均访问时间并提高Cache的性能。 (1)采用两级Cache：在原Cache和存储器之间增加一级Cache，构成两级Cache。其中第一级Cache可以让它小到足以与快速的处理器运行时钟周期相匹配，而第二级Cache则让它大到足以捕获到对内存进行的大多数访问，从而有效地降低了失效开销。 (2)让读失效优先于写：提高写直达Cache性能最重要的方法是设置一个容量适中的写缓存。然而写缓存中可能包含读失效时所需单元的最新值，这个值尚未写入存储器，导致了存储器访问的复杂化。解决方法是让读失效等待，直至写缓存为空。,5.3.
21、2 减少Cache失效开销(续1),合并写缓冲区 采用写直达法的Cache要有一个写缓冲区，如果写缓冲区为空，就把被替换的数据和相应地址写入缓冲区。请求字处理技术 处理器在同一时刻只需要调入块中的一个字(即请求字)，不必等到全部的块调入Cache，就可以将该字送往处理器并重新启动处理器进行访问，一般有以下两种策略：(1)请求字优先：调块时，先向存储器请求处理器所要的请求字。一旦该请求字到达即送往处理器，让处理器继续执行，同时可以从存储器中调入该块的其他字。(2)提前重启动：在请求字没到达处理器时，处理器处于等待状态。,5.3.3 减少命中时间,除了通过降低失效率和减少失效开销来优化Cache性
22、能的方法以外，还可通过减少命中时间来优化Cache的性能。命中时间也是平均访问时间的一个组成部分，它的重要性在于它会影响处理器的时钟频率。(1)小而简单的Cache减少命中时间 采用容量小、结构简单的Cache，这样快表较小，查表的速度较快，从而有效地提高了Cache的访问速度。(2)路预测减少命中时间 路预测要求Cache中预留特殊的比较位，用来预测下一次访问Cache时可能会用到的路或块。,5.3.3 减少命中时间(续1),(3)踪迹Cache(Trace Cache)减少命中时间 踪迹Cache中存储的是处理器所执行的动态指令序列，而不是用于存储主存储器中给出的静态指令序列。L例如，在P
23、entium4处理器的踪迹Cache中由于使用了译码微操作，从而节省了译码时间。(4)流水线Cache访问 流水线Cache访问方法是将流水线、Cache访问以及使一级Cache命中时的有效时延分散到几个时钟周期。它实际上并不能真正减少Cache命中时间，但可以提供较短的周期时间和高宽带。,5.4 主存储器及性能优化,主存储器也即主存，是存储层次中紧接着Cache下面的一个层次。它是计算机硬件的一个重要部件，其作用是存放指令和数据，并能由中央处理器直接随机存取。它既被用来满足Cache的请求，也被用作I/O接口。主存的性能指标主要是存储容量、存取时间、存储周期和存储器带宽。存储容量是指在一个存
24、储器中可以容纳的存储单元总数；存取时间是指从启动到完成一次存储器操作所经历的时间；存储周期是指连续启动两次操作所需间隔的最小时间；存储器带宽是指单位时间里存储器所存取的信息量。,5.4.1 主存储器,目前，就主存的速度来看，仍不能满足CPU的要求，这是因为主存速度的改进跟不上CPU速度的提高。Cache的引入，在很大程度上弥补了主存和CPU速度上的巨大差距。主存的延迟因影响Cache的失效开销而成为Cache主要关心的问题，另外，随着第二级Cache的广泛应用，主存带宽对于Cache来说也越来越重要了。在有Cache的存储层次中，主存的性能主要是用主存的延迟和带宽来衡量的。,5.4.2 主存储
25、器性能优化,增加存储器的宽度 增加数据带宽可以增加同时访问的数据量，提高数据的吞吐量，最简单的方法是增加存储器的宽度。 第一级Cache的宽度通常为一个字，因为CPU大部分的访存都是一个字的宽度的。在不具有第二级Cache的计算机系统中，主存的宽度一般与Cache的宽度相同。因此，可以将Cache和主存的宽度同时增加为原来宽度的两倍或以上，从而增加了主存的宽度。,5.4.2 主存储器性能优化(续1),多体交叉存储器采用模m多体交叉编址，利用多体潜在的并行性进行并行存取。其中每个存储体的宽度一般为一个字的宽度，通过同时向多个个体发送地址对它们同时进行访问，从而一次可以读或者写多个字。有两种基本的
26、多体交叉方法：高位多体交叉方法和低位多体交叉方法。,5.4.2 主存储器性能优化(续2),高位多体交叉方法高位交叉存储器的地址高位部分用于区分不同的存储体，低位部分用于选择一个存储体体内不同的存储单元。,5.4.2 主存储器性能优化(续3),低位多体交叉方法低位交叉存储器的地址位使用方法与高位交叉存储器刚好相反：低位部分用于区分不同的存储体，高位部分用于选择一个存储体体内不同的存储单元。,5.5 虚拟存储器,虚拟存储器是由主存和联机的外存共同组成的，在主存的容量不能满足要求时，数据可存放在外存中，但在程序中仍按地址进行访问外存空间。在虚拟存储器中，应用程序员是直接用机器指令的地址码对整个程序统
27、一编址的，虚拟存储器的空间大小取决于它能产生的地址位数。从程序员的角度看，存储空间扩大了，并可以放得下整个程序，程序不必作任何修改就可以以接近于实际主存的速度在这个虚拟存储器上运行。,5.5.1 虚拟存储器工作原理,根据采用的存储映象算法，可以将虚拟存储器的管理方式分为段式、页式和段页式3种。段式管理 将主存按段分配的存储管理方式称为段式管理。对于一个复杂的程序可以分解为多个逻辑上相当独立的模块。这些模块可以是主程序，各种子程序，也可以是表格、向量、数组等。每个模块都是一个单独的程序段，都从0地址开始相对编址，段的长度可长可短，甚至可以事先无法确定。在段式管理的系统中，当某程序段由辅存调入主存
28、时，系统在主存中给该段分配一块空间，并给出基址(即该段在主存中的起始地址)，由基址和每个单元在段内的相对位移量就可以形成这些单元在主存中各自的实际地址，进行访问。,5.5.1 虚拟存储器工作原理(续1),在段式管理中，每一道程序都有一个段表，用以指明各段在主存中的状态信息。段表中包括段号(或段名)、段长和起始位置等信息。断号字段用于存放程序段的断号或名称，如果断号是连续的，则断号这一字段信息可以去掉，直接根据起始位置和段长来实现程序段到主存储器的映象。段长是该段的长度，可用于访问地址的越界检查。起始地址用于存放该程序段装入主存中的起始(绝对)地址。此外，还可能会设置一个装入位来指示该段是否已装
29、入主存，如装入位为“1”，表示已装入；为“0”，表示尚未装入。,5.5.1 虚拟存储器工作原理(续2),段式管理地址映像方法和地址变换方法,5.5.1 虚拟存储器工作原理(续3),段式虚拟存储器的主要优点:(1)程序的模块性能较好。(2)分段还便于程序和数据的共享。(3)容易以段为单位实现存储保护。(4)程序的动态链接和调度比较容易。段式虚拟存储器的主要缺点：(1)地址变换费时。(2)主存储器利用率低。(3)对辅存管理较困难。,5.5.1 虚拟存储器工作原理(续4),页式管理 页式存储是将虚拟存储空间和实际的存储空间都等分成固定大小的页，各虚拟页可以装入到主存中不同的页面位置。页是一种逻辑上的
30、划分，页面的大小随机器而异。目前，一般计算机系统中，页的大小通常指定为磁盘存储器物理块大小的整数倍。 在虚拟存储器中，虚拟地址空间中划分的页称为虚页，主存地址空间中划分的页称为实页。则页式管理的地址映象就是完成虚拟地址空间中的虚页到主存地址空间中的实页的变换。页式管理用一个页表，其中包括页号、主存页号等。页号一般用于存放该页在页表中的页号(或行号)，因此可以省略；页的长度是固定的，因此也省略了。页表中也可以设置一些标志位，如装入位、修改位等。,5.5.1 虚拟存储器工作原理(续5),页式管理地址映像方法和地址转换方法,5.5.1 虚拟存储器工作原理(续6),页式虚拟存储的主要优点：(1)主存的
31、利用率高。(2)页表相对简单。(3)地址映象与变换速度较快。(4)对辅存的管理比较容易。页式虚拟存储的主要缺点：(1)程序的模块化性能不好。由于用户程序被强制按固定大小的页来划分，因此一页可能是程序段的某一部分，也可能包含了两个或两个以上的程序段。(2)页表很长，从而要占用很大的存储空间。,5.5.1 虚拟存储器工作原理(续7),段页式管理 段式管理和页式管理各有其优缺点，段页式管理则是将两者结合起来，同时利用段式管理在程序模块化方面的优点和页式管理在管理主存和辅存方面的优点。 将主存储器的物理空间等分成固定大小的页，将虚拟存储空间中的程序按模块分段，每个段又分成与主存页面大小相同的页。,5.
32、5.1 虚拟存储器工作原理(续8),段页式管理地址映像方法和地址转换方法,5.5.2 地址映像与转换,当把大的虚存空间中的内容压缩到小的主存空间中去，则主存中的每一个页或段必须与多个虚拟存储空间中的页或段相对应。主存中的一个实页要对应多少个实页与采用的映象方式有关。此时，就不可避免地发生两个以上的虚页想要进入主存中同一个页面位置的现象，这种现象称为页面争用或实页冲突。一旦发生实页冲突，只能首先装入其中的一个虚页，等到不再需要这个虚页时才可装入其它的，从而导致了执行效率的下降。因此，映象方式的选择主要应考虑能否尽量减小实页冲突概率。操作系统一般都允许将每道程序的任何虚页可以映象到任何实页位置，即
33、全相联映象。仅当一个任务要求同时调入主存的页面超出主存页数时，两个虚页才会争用同一个实页位置。因此，全相联映象的实页冲突率最低。,5.5.3 内部地址变换优化,在虚拟存储系统中，如果不采取有效的措施，则访问主存储器的速度要降低很多。造成这个速度降低的主要原因是：每次进行访存时，都必须进行内部地址变换，其概率为100%。所以，如何加快用户虚地址到主存实地址的变换，是缩短访存时间的关键。只要内部地址的变换速度高到使整个系统的访存速度非常接近于不采用虚拟存储器时的访存速度，虚拟存储器的性能才能真正实现。在虚拟存储器进行地址变换时，首先必须查段表或页表，或既查段表也查页表，来完成虚地址到实地址相应的转
34、换。由于页表容量较大且存放在主存中，因此每访存一次，还需因查表而加一次访存；如果采用的是段页式虚拟存储器，则需因两次查表而加两次访存。结果是主存储器的访问速度比不采用虚拟存储器的访存速度要慢2到3倍。如何提高页表的访问速度？,5.5.3 内部地址变换优化(续1),快表 根据程序的局部性特点，对页表内各项的访问并不完全是随机的。在一段时间内，实际可能只用到表中很少的几项。因此，应该重点提高使用概率较高的这部分页表的访问速度。可以使用快速硬件来构成比全表小得多的表，表中存放的是近期经常要使用的页表项，这个表称为“快表”。相应地，原先存放全部虚地址和实地址之间映象关系的表还是存放在主存中，将其称为“
35、慢表”。,5.5.3 内部地址变换优化(续2),具有快表的地址转换方法,5.5.3 内部地址变换优化(续3),快表的存在对所有的程序员都是透明的。实际上，快表与慢表也构成了一个两级存储层次，其访问速度接近于快表的速度，存储容量却是慢表的容量。当然，快表的命中率如果不高，则系统的效率就会大大降低。要提高快表的命中率，最直接的办法是增加快表的容量。快表的容量越大，其命中率就越高；但容量越大时，其相联查找的速度就越慢。所以，快表的命中率和查表速度是矛盾的。,5.5.3 内部地址变换优化(续4),为了提高查找速度，可以减少相联比较的位数。在同样容量的情况下，相联比较的位数越少，则相联查找所花费的时间就
36、会越少。例如，将虚地址中参与相联比较位中的用户字段u去掉，这是因为快表在一段时间内总是对应于同一个任务或用户，它们的u值是不变的。这样，相联比较的位数就减少了一位，查找速度也相应地提高了。但是，这种方法会降低快表的命中率，降低虚、实地址的变化速度。也可以采用普通的按地址来访问，可以使用顺序查找法、对分查找法和散列查找法等。,5.5.3 内部地址变换优化(续5),目前，计算机系统都采用相联寄存器组、硬件的散列压缩、快慢表结构和多个相等比较器等方法，来提高系统的性能。,5.5.4 页面替换算法及实现,同高速缓冲存储器一样，在虚拟存储器中，当访问的指令和数据不在主存时，发生页面失效，需要从辅存中将包
37、含该指令或数据的一页（或一段）调入到主存储器中。虚存空间比主存空间大得多，必然也会出现主存中所有页面都已经被占用，或者所有主存空间都已经被占用的情况，这时，如果继续把辅存中一页调入主存，就会发生实页冲突。此时，只有从主存空间中选出一页替换出去，让出空间来接纳新调入的页。应该选择哪一页进行替换呢？这就是页面替换算法要解决的问题。,5.5.4 页面替换算法及实现(续1),页面替换算法(1)随机算法 随机算法是将软的或硬的随机数产生器产生的随机数作为主存储器中被替换的页的页号。这种算法最简单，且易于实现。但是，没有利用主存储器中页面使用情况的“历史”信息，也没有反映程序的局部性特点，从而命中率较低，
38、较少被使用。(2)先进先出算法 选择最早被调入主存储器的页作为被替换的页。它的优点是实现容易，并利用了主存储器中页面使用情况的“历史”信息，但是，不能正确反映程序的局部性。因为最先进入主存的页很可能也是现在经常要使用的页。,10/5/2018,5.5.4 页面替换算法及实现(续2),(3)近期最少使用算法，即LFU算法 选择近期最少被访问的页作为被替换的页。该算法能比较正确地反映程序的局部性。(4)最优替换算法，即OPT算法 选择将来一段时间内最久不被访问的页作为被替换的页。,5.5.4 页面替换算法及实现(续3),页面替换算法性能分析：同一地址流命中率比较,5.5.4 页面替换算法及实现(续
39、4),页面替换算法性能分析：命中率与与地址流关联关系,5.5.4 页面替换算法及实现(续5),堆栈型算法 对任意一个页面地址流，设t为已经处理过 个页面的时间点，m为分配给该地址流的主存页面数， 为在t时间点，在m页的主存中的页面集合。如果对此页地址流作两次主存页面数分配，分别分配m个和n个主存页面，并且当 时，如果替换算法满足：在任何时刻t，Bt有以下关系：,5.5.4 页面替换算法及实现(续6),堆栈型替换算法的命中率随着分配给该程序的主存页面数增加而提高，至少不会下降。对堆栈型替换算法，只需采用堆栈处理技术对地址流模拟处理一次，即可同时获得对此地址流在不同主存页数时的命中率，从而大大节省
40、了存储体系设计的工作量。在多道程序的系统中，可以采用一种动态算法：页面失效频率法，来提高系统的性能。具体实现方法是：根据各道程序实际运行中主存页面失效率的高低情况，由操作系统动态地调节分配给各道程序的实页数。当一道程序的主存页面命中率低于某个限定值时就自动地增加分配给该程序的主存实页数，以提高命中率。,5.5.5 提高主存命中率的方法,通常，影响主存命中率的主要因素有：(1)程序在执行过程中的页地址流分布情况；(2)所采用的替换算法；(3)页面大小；(4)主存容量；(5)所采用的页面调度方法。,5.5.5 提高主存命中率的方法(续1),页面大小的选择 与Cache命中率与页面大小的关系一样，主
41、存命中率与页面大小的关系也不是线性的。页面大小还与主存容量、程序的页地址流分布情况等因素有关。,5.5.5 提高主存命中率的方法(续2),主存容量 与Cache类似，当主存容量增加时，主存命中率也会相应地提高。,5.5.5 提高主存命中率的方法(续3),页面调度方法，页面调度就是系统给用户分配主存页面数的过程。一般有三种方式：(1)分页方式: 将整个程序先链接装配，将整个程序装入主存后才运行，其命中率为100%，但是主存的利用率较低；(2)请求页式: 在发生页面失效时，才将所需要的页装入主存。其主存的利用率很高，但命中率将受到频繁的页面替换的影响；(3)预取式: 根据程序的局部性特点，在程序被
42、挂起之后又重新开始运行之前，预先调入相关的页面。这种方法可能会因为预先调入的页面用不上而造成时间和空间上的浪费。,5.6 进程保护和虚拟存储器实例,在多道程序中，计算机资源可以被多道同时运行的用户程序所共享。为使系统能够正常工作，应防止由于一个用户程序出错而破坏主存中其他用户的程序和数据，还要防止一个用户不合法地访问主存中不是分配给它的存储区域而造成对系统的破坏，即使这种访问不会引起破坏也是不允许的。操作系统和系统结构需要为存储系统的安全提供保护手段。,5.6.1 进程保护,保证进程的正确和安全运行既是系统设计者也是操作系统设计者的责任。保护的手段主要是：将主存区域分为几个区域，使得主存中可以
43、同时存放多个不同进程的状态；并对每个存储区域进行保护，使一个进程的信息不被另一个进程所修改。存储系统的保护分为： (1)存储区域的保护，可用一对寄存器(即界限寄存器)来检查每一个地址，以确保地址在两个界限之间。 (2)访问保护，由系统软件设置用户进程访存的地址上下界，禁止了访问越界。,5.6.1 进程保护(续1),在虚拟存储系统中，由于用户程序的访问空间映射到主存后将不是一个连续的地址空间，而将分部在主存中的各个页面，因此不适用以上述保护方式。在虚拟存储系统中，将采用更细微的方法： (1)映射表保护法，利用映射表的映射关系来限制用户程序的访问地址空间，用户程序不能访问映射表上找不到的主存页面，
44、从而起到保护作用。 (2)键保护，由操作系统根据主存使用分配的情况，给主存中的每一页分配一个存储键，相当于保护锁。所有页的存储键是在主存相应的快速寄存器内，当用户访问这些页面时，需要一个访问键，相当于钥匙，来打开这把锁。,5.6.1 进程保护(续2),(3)环保护，把系统程序和用户程序按其重要性及其访问权限进行分层。最内的几层是系统程序的分层，之外的几层是同一用户程序的分层，保护级别由里向外逐层降低。,5.6.2 Alpha 21064存储管理,Alpha处理机的系统结构采用段页相结合的方式，既提供了存储保护，又将页表减少到最小。Alpha根据64位地址的最高两位将地址空间分为3个段：seg0
45、(最高位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位地址除了高位用于段选择的两位，其余的位则用于表示虚
46、地址。虚地址中有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
47、被分割成独立的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),
