1、Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系1/169w 存储系统原理存储系统原理w 虚拟存储系统虚拟存储系统w Cache存储系统存储系统w 三级存储系统三级存储系统Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系2/169本章内容w 引入引入w 存储系统的基本概念存储系统的基本概念w 存储器的层次结构存储器的层次结构w 存储器的频带平衡存储器的频带平衡Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系3/169本章内容存储系统原理 现代计算机系现代计算
2、机系统都以存储器为中统都以存储器为中心（不同于以运算心（不同于以运算器为中心的冯器为中心的冯诺依诺依曼计算机），存储曼计算机），存储器是各种信息存储器是各种信息存储和交换的中心。和交换的中心。3 之 1主存储器主存储器取取 指指 令令取取 操操 作作 数数写写 结结 果果I/O I/O 数数 据据Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系4/169 SM=Wlm。其中：其中：W为存储体的字长，为存储体的字长，l为每为每个存储体的字数，个存储体的字数，m为并行工作的存储体个数。为并行工作的存储体个数。w 可以用访问时间可以用访问时间TA、存储周
3、期存储周期TM和频宽（带宽）和频宽（带宽）BM来描述。来描述。w 可以用总价格可以用总价格C或每位价格或每位价格c表示。表示。本章内容存储系统原理3 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系5/169 基本要求是：高速度、大容量、低价格。基本要求是：高速度、大容量、低价格。w 单靠一种工艺的单一存储器无法同时满足容量、单靠一种工艺的单一存储器无法同时满足容量、速度和价格三方面的要求。速度和价格三方面的要求。w 使用多种不同工艺的存储器组成使用多种不同工艺的存储器组成，使，使所有的信息以各种方式分布于不同的存储器上。所有的信息以各种方式
4、分布于不同的存储器上。本章内容存储系统原理3 之 3Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系6/169本章内容存储系统原理w 存储系统的定义存储系统的定义w 常用存储系统常用存储系统w 存储系统的性能指标存储系统的性能指标w 存储系统的设计存储系统的设计Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系7/169本章内容存储系统原理存储系统的基本概念 两个或两个以上速度、容量和价格各不两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件或软硬件相结合相同的存储器用硬件、软件或软硬件相结合的方
5、法连接起来成为一个系统。这个系统对的方法连接起来成为一个系统。这个系统对应用程序员透明，并且，从应用程序员看它应用程序员透明，并且，从应用程序员看它是一个是一个“存储器存储器”，这个，这个“存储器存储器”的速度的速度接近于速度最快的那个存储器，存储容量接接近于速度最快的那个存储器，存储容量接近于容量最大的那个存储器，单位容量的价近于容量最大的那个存储器，单位容量的价格接近于最便宜的那个存储器。格接近于最便宜的那个存储器。3 之 1Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系8/169本章内容存储系统原理存储系统的基本概念M1(T1,S1,C1)
6、M2(T2,S2,C2)Mn(Tn,Sn,Cn)Tmin(T1,T2,Tn),用存储周期表示用存储周期表示Smax(S1,S2,Sn),用用MB或或GB表示表示Cmin(C1,C2,Cn),用每位的价格表示用每位的价格表示从外部看从外部看3 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系9/169本章内容存储系统原理存储系统的基本概念3 之 3有这么好的事？有这么好的事？当然有！当然有！是存储系统设计是存储系统设计的基础。的基础。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系10/169本章内
7、容存储系统原理存储系统的基本概念w 虚拟存储系统虚拟存储系统w Cache存储系统存储系统Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系11/169本章内容存储系统原理存储系统的基本概念常用存储系统 由主存储器和磁盘存储器由主存储器和磁盘存储器构成构成。增加存储器的存储容量。增加存储器的存储容量。采用硬件和软件相结合的采用硬件和软件相结合的方法来调度，因此对应用程方法来调度，因此对应用程序员是透明的，对系统程序序员是透明的，对系统程序员是不透明的。员是不透明的。主存储器主存储器磁盘存储器磁盘存储器 这个存储系统从这个存储系统从看：速度接近主存看：
8、速度接近主存的速度，容量是虚拟地址的速度，容量是虚拟地址空间，每位价格接近磁盘空间，每位价格接近磁盘存储器的价格。存储器的价格。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系12/169本章内容存储系统原理存储系统的基本概念常用存储系统 由由Cache和主存储器构成。和主存储器构成。提高存储器的速度。提高存储器的速度。全部用硬件来调度，不仅全部用硬件来调度，不仅对应用程序员还是系统程序对应用程序员还是系统程序员都是透明的。员都是透明的。Cache主存储器主存储器 这个存储系统从这个存储系统从看：速度接近看：速度接近CacheCache的速度，容量
9、是主存的速度，容量是主存的容量，每位价格接近主的容量，每位价格接近主存的价格。存的价格。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系13/169本章内容存储系统原理存储系统的基本概念w 存储容量存储容量w 存储价格存储价格w 存储速度存储速度M1(S1,C1,T1)M2(S2,C2,T2)M(S,C,T)为了分析方便，采为了分析方便，采用由两个存储器用由两个存储器M1M1和和M2M2组成的存储系统组成的存储系统M M。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系14/169本章内容存储系统原理存
10、储系统的基本概念存储系统的性能指标 存储容量接近于存储容量接近于M2（即：即：SS2）。）。对存对存储系统进行编址的方法有：储系统进行编址的方法有：例如：例如：Cache存储系统。存储系统。例如：虚拟存储系统。例如：虚拟存储系统。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系15/169本章内容存储系统原理存储系统的基本概念存储系统的性能指标 整个存储系统的单位容量平均价格为：整个存储系统的单位容量平均价格为：当当S2S1时，时，cc2，但但S1与与S2不能不能相差太大，否则存储系统要达到比较高的性相差太大，否则存储系统要达到比较高的性能，调度起
11、来很困难。能，调度起来很困难。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系16/169本章内容存储系统原理存储系统的基本概念存储系统的性能指标 在在M1存储器中访问到的概率。存储器中访问到的概率。M1的访问次数的访问次数 M2的访问次数的访问次数6 之 1Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系17/169本章内容存储系统原理存储系统的基本概念存储系统的性能指标 提高存储系统速度的两条途径：提高存储系统速度的两条途径：w 提高命中率提高命中率H（见见例例1）w 两个存储器的速度不要相差太大两
12、个存储器的速度不要相差太大（见见例例3）6 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系18/169本章内容存储系统原理存储系统的基本概念存储系统的性能指标假设假设T2=5T1，在命中率在命中率H为为0.9和和0.99两种情况下，分别计算存储系统的访两种情况下，分别计算存储系统的访问效率。问效率。当当H=0.9时：时：当当H=0.99时：时：6 之 3Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系19/169本章内容存储系统原理存储系统的基本概念存储系统的性能指标 不命中时，把不命中时，把M
13、2存储器中相邻几个单元组成的存储器中相邻几个单元组成的一个数据块都取出来送入一个数据块都取出来送入M1存储器中。存储器中。（见（见例例2）其中：其中：是采用预取技术后的命中率；是采用预取技术后的命中率；是原来的命中率；是原来的命中率；为数据块大小与数据重复使用次数的乘积。为数据块大小与数据重复使用次数的乘积。6 之 4Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系20/169本章内容存储系统原理存储系统的基本概念存储系统的性能指标在一个虚拟存储系统中，在一个虚拟存储系统中，T2105 T1，原来原来的命中率只有的命中率只有0.8，如果访问磁盘存储
14、器的数，如果访问磁盘存储器的数据块大小为据块大小为4K字，并要求访问效率不低于字，并要求访问效率不低于0.9，计算数据在主存储器中的重复利用率至，计算数据在主存储器中的重复利用率至少为多少？少为多少？假设数据在主存储器中的重复利用率为假设数据在主存储器中的重复利用率为m，根据前面的给出关系：根据前面的给出关系：解之得：解之得：m=44mmHHH4096140968.0105)1(19.0，6 之 5Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系21/169本章内容存储系统原理存储系统的基本概念存储系统的性能指标在虚拟存储系统中，两级存储器的速度在
15、虚拟存储系统中，两级存储器的速度相差特别悬殊相差特别悬殊T2=105T1。如果要使访如果要使访问效率问效率e=0.9，问需要有多高的命中率？问需要有多高的命中率？解之得：解之得：H=0.999998888877777.0.9999996 之 6Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系22/169本章内容存储系统原理存储系统的基本概念相邻级的容量差、速度差较大；相邻级的容量差、速度差较大；(减少减少C)存储层次具有较高的命中率；存储层次具有较高的命中率；(减少减少T)存储层次的辅助软、硬件开销较小。存储层次的辅助软、硬件开销较小。块从低层调入
16、高层时放在何位置；块从低层调入高层时放在何位置；如何在本层次中查找需访问的块；如何在本层次中查找需访问的块；发生失效时，替换哪个块；发生失效时，替换哪个块；进行写访问时，应进行那些操作。进行写访问时，应进行那些操作。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系23/169本章内容存储系统原理访问速度越来越快通用寄存器堆指令和数据缓冲Cache(SRAM)主存储器（DRAM）联机外部存储器（磁盘等）脱机外部存储器（磁带、光盘等）每位的价格越来越便宜存储容量越来越大CPU内部Computer ArchitectureV3同济大学.电子与信息工程学院
17、.计算机科学与工程系24/169本章内容存储系统原理 计算机中各级存储器频带应该达到平衡，即：计算机中各级存储器频带应该达到平衡，即：存储器的速度应能跟得上系统的需要。存储器的速度应能跟得上系统的需要。多个存储器并行，采用并行多个存储器并行，采用并行/交叉访问等方法交叉访问等方法提高存储器的访问速度（并行存储器）；提高存储器的访问速度（并行存储器）；设置各种缓冲存储器；设置各种缓冲存储器；采用存储体系，特别是采用存储体系，特别是Cache存储体系。存储体系。2 之 1Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系25/169本章内容存储系统原理w
18、 并行访问存储器并行访问存储器w 交叉访问存储器交叉访问存储器2 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系26/169 增加存储器的字长，例如：把增加存储器的字长，例如：把m字字w位的存储位的存储器（器（单体单字存储器单体单字存储器）改变成为）改变成为m/n字字nw位的位的存储器（存储器（单体多字存储器），单体多字存储器），见见后图后图。实现简单、容易。实现简单、容易。访问的冲突大（取指令冲突、读操作数冲访问的冲突大（取指令冲突、读操作数冲突、写数据冲突和读写冲突）。突、写数据冲突和读写冲突）。本章内容存储系统原理并行存储器2 之 1
19、Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系27/169本章内容存储系统原理并行存储器数据寄存器数据寄存器MDR存储体存储体(m字字 w位位)地址寄存器地址寄存器MAR多路选择器多路选择器MDR存储体存储体(m/n字字 nw位位)MAR一般存储器一般存储器并行访问存储器并行访问存储器2 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系28/169本章内容存储系统原理并行存储器w 地址码高位交叉地址码高位交叉w 地址码低位交叉地址码低位交叉Computer ArchitectureV3同济大学.
20、电子与信息工程学院.计算机科学与工程系29/169本章内容存储系统原理并行存储器交叉访问存储器MDR存储体存储体0MAR0.00.00.0F.FMDR存储体存储体1MAR0.10.00.1F.FMDR存储体存储体n-1MARF.F0.0F.FF.F译码器译码器 高位高位 地址寄存器（低位）地址寄存器（低位）数据寄存器数据寄存器 地址寄存器地址寄存器 3 之 1Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系30/169 为每个存储体的容量（地址码的低为每个存储体的容量（地址码的低log2m位作为存储体位作为存储体的体内地址，而且每个存储体都相同）。
21、的体内地址，而且每个存储体都相同）。为存储体的编号，为存储体的编号，k=0,1,2,n-1（其中其中n为组成存储为组成存储器的存储体个数的总和，地址码的高器的存储体个数的总和，地址码的高log2n位作为一个位作为一个译码器的输入）译码器的输入）为各个存储体的体内地址，为各个存储体的体内地址，k=0,1,2,m-1 如果已知地址如果已知地址A，则：则：本章内容存储系统原理并行存储器交叉访问存储器3 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系31/169本章内容存储系统原理并行存储器交叉访问存储器w 扩大存储器容量。扩大存储器容量。目前，大
22、部分计算机系统中所采用的模块化主存储器通目前，大部分计算机系统中所采用的模块化主存储器通常都是采用高位交叉编址方法实现。常都是采用高位交叉编址方法实现。可用于扩大存储器容量，且扩充性好。可用于扩大存储器容量，且扩充性好。：可以通过把不同的任务分配给：可以通过把不同的任务分配给不同的存储体完成来提高存储器的访问速度。不同的存储体完成来提高存储器的访问速度。3 之 3Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系32/169本章内容存储系统原理并行存储器交叉访问存储器MDR存储体存储体0MAR0.00.0F.F0.0MDR存储体存储体1MAR0.00
23、.1F.F0.1MDR存储体存储体n-1MAR0.0F.FF.FF.F译码器译码器 地址寄存器（高位）地址寄存器（高位）（低位）（低位）数据寄存器数据寄存器 地址寄存器地址寄存器 4 之 1Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系33/169 为每个存储体的容量（地址码的高为每个存储体的容量（地址码的高log2m位作为存储体位作为存储体的体内地址，而且每个存储体都相同）。的体内地址，而且每个存储体都相同）。为存储体的编号，为存储体的编号，k=0,1,2,n-1（其中其中n为组成存储为组成存储器的存储体个数的总和，地址码的低器的存储体个数的总
24、和，地址码的低log2n位作为一个位作为一个译码器的输入）译码器的输入）为各个存储体的体内地址，为各个存储体的体内地址，k=0,1,2,m-1 如果已知地址如果已知地址A，则：则：本章内容存储系统原理并行存储器交叉访问存储器4 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系34/169本章内容存储系统原理并行存储器交叉访问存储器 提高存储器访问速度。提高存储器访问速度。为此在一个存储周期内，为此在一个存储周期内，n个存储体必须同时或分时启个存储体必须同时或分时启动，实际上是一种采用流水线方式工作的并行存储器。动，实际上是一种采用流水线方式工
25、作的并行存储器。4 之 3#0t存储周期Tm#1#2#n-1启动间隔启动间隔t=Tm/n Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系35/169本章内容存储系统原理并行存储器交叉访问存储器4 之 4 主存储器的速度不是随存储体的个数的增加而主存储器的速度不是随存储体的个数的增加而线性增加。例如：在有的大型计算机中采用线性增加。例如：在有的大型计算机中采用32个个存储体低位交叉来构成主存储器，但是主存储器存储体低位交叉来构成主存储器，但是主存储器的速度只比单个存储体高的速度只比单个存储体高10倍左右。倍左右。存在访问冲突，产生冲突的根源主要有二
26、：程存在访问冲突，产生冲突的根源主要有二：程序中有转移指令和数据的随机性。序中有转移指令和数据的随机性。设计一种无访问冲突的存储器。设计一种无访问冲突的存储器。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系36/169本章内容 也称也称、，1961年英国曼彻斯特大学年英国曼彻斯特大学Kilbrn等人提出，等人提出，70年代广泛地应用于大中年代广泛地应用于大中型计算机系统中，目前许多微型机也开始使型计算机系统中，目前许多微型机也开始使用虚拟存储器。用虚拟存储器。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与
27、工程系37/169本章内容Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系38/169本章内容w 虚拟存储系统的工作原理虚拟存储系统的工作原理w 地址的映象和变换方法地址的映象和变换方法w 加快内部地址变换速度的方法加快内部地址变换速度的方法w 页面替换算法页面替换算法w 提高主存命中率的方法提高主存命中率的方法页式虚拟存储器工作原理页式虚拟存储器工作原理磁盘存储器地址磁盘存储器地址 访磁盘存储器访磁盘存储器 命中命中外部地址变换外部地址变换未命中未命中访磁带等访磁带等虚页号虚页号磁盘实地址磁盘实地址外部地址变换外部地址变换 U+PUPD Av多用
28、户虚地址多用户虚地址 主存页面失效主存页面失效 U+P未命中未命中内部地址变换内部地址变换选页选页 命中命中虚页号虚页号主存实页号主存实页号主存页面表主存页面表0 0 页页 主存未满主存未满 主存满主存满1 1 页页X X访问主存访问主存pd A页面页面用用替换算法替换算法户户2P-10 0 页页主存页号主存页号0 0 页页1 1 页页调入页调入页I/OI/O处理机处理机调入页调入页1 1 页页Y Y被替换页被替换页（I/OI/O通道）通道）替换页替换页用用户户2p p-1主存储器主存储器 磁盘存储器磁盘存储器命中？命中？Computer ArchitectureV3同济大学.电子与信息工程学
29、院.计算机科学与工程系40/169本章内容虚拟存储系统 虚拟地址空间、主存地址空间和辅存地址空间。虚拟地址空间、主存地址空间和辅存地址空间。虚拟地址、主存地址和辅存地址。虚拟地址、主存地址和辅存地址。把虚拟地址空间映象到主存地址空间。把虚拟地址空间映象到主存地址空间。在程序运行时，把虚地址变换成主存地址（在程序运行时，把虚地址变换成主存地址（）或辅存地址（）或辅存地址（）。）。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系41/169本章内容虚拟存储系统地址的映象和变换方法装入装入磁盘实地址磁盘实地址用户号用户号页内偏移页内偏移1虚页号虚页号外部
30、地址外部地址变换（软变换（软件实现）件实现）磁盘号磁盘号柱面号柱面号磁头号磁头号块号块号多用户多用户虚地址虚地址外页表外页表Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系42/169本章内容虚拟存储系统 根据所采用的地址映象和变换方法（内根据所采用的地址映象和变换方法（内部地址变换）不同，有三种不同类型的虚拟部地址变换）不同，有三种不同类型的虚拟存储器：存储器：w 段式虚拟存储器段式虚拟存储器w 页式虚拟存储器页式虚拟存储器w 段页式虚拟存储器段页式虚拟存储器Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与
31、工程系43/169本章内容虚拟存储系统地址的映象和变换方法 0段段1k1段段2段段3段段0500020002000段号段号 段长段长 起址起址01k8k150016k22009k320030k08k9k16k30k程序空间程序空间主存储器主存储器主程序主程序段表段表3 之 1段大小可变段大小可变Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系44/169本章内容虚拟存储系统地址的映象和变换方法 0段表段表长度长度段表段表基址基址5As段名段名起始起始地址地址装入装入位位段长段长访问访问方式方式用户号用户号U段号段号S段内偏移段内偏移D多用户多用户虚
32、地址虚地址主存实地址主存实地址432101n-1As段表基址寄存器段表基址寄存器一个用户（一道作业）的段表一个用户（一道作业）的段表3 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系45/169程序的模块化性能好程序的模块化性能好便于程序和数据的共便于程序和数据的共享享程序的动态链接和调程序的动态链接和调度比较容易度比较容易便于实现信息保护便于实现信息保护地址变换所花费的时地址变换所花费的时间比较长，做两次加间比较长，做两次加法运算法运算主存储器的利用率往主存储器的利用率往往比较低往比较低对辅存（磁盘存储器）对辅存（磁盘存储器）的管理比较困
33、难的管理比较困难本章内容虚拟存储系统地址的映象和变换方法 3 之 3Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系46/169本章内容虚拟存储系统地址的映象和变换方法3 之 10页页1页页2页页3页页页号页号主存页号主存页号0123用户程序用户程序主存储器主存储器页表页表虚页号虚页号实页号实页号虚实页号对照表虚实页号对照表页大小固定页大小固定Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系47/169本章内容虚拟存储系统地址的映象和变换方法 3 之 2Pa装入位装入位修改位修改位主存页号主存页号标志标
34、志用户号用户号U虚页号虚页号P页内偏移页内偏移D页内偏移页内偏移d1 pPa页表基址寄存器页表基址寄存器页表页表实页号实页号p01342Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系48/169主存储器的利用率比较高；主存储器的利用率比较高；页表相对比较简单；页表相对比较简单；地址变换的速度比较快；地址变换的速度比较快；对磁盘的管理比较容易。对磁盘的管理比较容易。程序的模块化性程序的模块化性能不好；能不好；页表很长，需要页表很长，需要占用很大的存储占用很大的存储空间。空间。本章内容虚拟存储系统地址的映象和变换方法3 之 3Computer Arc
35、hitectureV3同济大学.电子与信息工程学院.计算机科学与工程系49/169本章内容虚拟存储系统地址的映象和变换方法3 之 10段段(12K)段表段表用户程序用户程序0段页表段页表主存储器主存储器1段段(10K)2段段(5K)页表长度页表长度332页表地址页表地址每页每页4KB4K4K4K1段页表段页表2段页表段页表Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系50/169本章内容虚拟存储系统地址的映象和变换方法3 之 2用户号用户号U段号段号S页内偏移页内偏移页内偏移页内偏移Ap实页号实页号p虚页号虚页号PAsAs装入装入修改修改实页号实
36、页号标志标志0/11p页表页表地址地址页表页表长长标志标志修改修改装入装入Ap0/11多用户页表多用户页表多用户段表多用户段表段表基址段表基址寄存器寄存器Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系51/169 段页式虚拟存储器一方面具有段式虚段页式虚拟存储器一方面具有段式虚拟存储器的主要优点，另一方面具有页式虚拟存储器的主要优点，另一方面具有页式虚拟存储器的主要优点。拟存储器的主要优点。本章内容虚拟存储系统地址的映象和变换方法 3 之 3Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系52/169
37、本章内容虚拟存储系统w 引入引入w 目录表目录表w 快慢表快慢表w 散列函数散列函数w 举例举例Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系53/169本章内容虚拟存储系统加快内部地址变换速度的方法 在段在段/页式虚拟存储器中，要访问主存必须先查段页式虚拟存储器中，要访问主存必须先查段/页页表，在段页式虚拟存储器中，既要查段表也要查页表。如表，在段页式虚拟存储器中，既要查段表也要查页表。如果段、页表都在主存中，则包括访问主存本身这一次在内，果段、页表都在主存中，则包括访问主存本身这一次在内，虚拟存储器的访问速度将要降低虚拟存储器的访问速度将要降
38、低2至至3倍。倍。下面以页式虚拟存储器下面以页式虚拟存储器为例进行介绍为例进行介绍Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系54/169本章内容虚拟存储系统加快内部地址变换速度的方法 压缩页表的存储容量（因为虚存页面压缩页表的存储容量（因为虚存页面数远大于主存页面数），用一个小容量高速数远大于主存页面数），用一个小容量高速存储器存放页表，从而加快页表的查表速度。存储器存放页表，从而加快页表的查表速度。3 之 1Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系55/169 页表中只页表中只保留已装入
39、保留已装入主存的那些主存的那些页。页。采用按内采用按内容访问的相容访问的相联存储器。联存储器。本章内容虚拟存储系统加快内部地址变换速度的方法实页号实页号其它标志其它标志用户号用户号U页内偏移页内偏移Dp虚页号虚页号P多用户多用户虚地址虚地址目录表（按内容访问的相联存储器）目录表（按内容访问的相联存储器）页内偏移页内偏移d实页号实页号p多用户虚页号多用户虚页号U,P修改修改0/1主存实地址主存实地址相联访问相联访问3 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系56/169本章内容虚拟存储系统加快内部地址变换速度的方法 与页表放在主存中相比
40、，查表速度快。与页表放在主存中相比，查表速度快。可扩展性比较差，且主存储器容量增加可扩展性比较差，且主存储器容量增加时，目录表的造价高，速度降低。时，目录表的造价高，速度降低。3 之 3Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系57/169本章内容虚拟存储系统加快内部地址变换速度的方法 根据局部性原理，将页表分为快表和慢表。根据局部性原理，将页表分为快表和慢表。快表快表TLB(Translation Lookaside Buffer)由小容由小容量（几几十个字）、高速硬件实现，采用相联量（几几十个字）、高速硬件实现，采用相联方式访问，存放最近
41、用到的页表信息。当快表中方式访问，存放最近用到的页表信息。当快表中查不到时，再从存放在主存储器中的慢表中查找。查不到时，再从存放在主存储器中的慢表中查找。快表与慢表也构快表与慢表也构成了一个两级存成了一个两级存储系统。储系统。2 之 1Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系58/169本章内容虚拟存储系统加快内部地址变换速度的方法实页号实页号用户号用户号U页内偏移页内偏移Dp虚页号虚页号P多用户虚地址多用户虚地址页内偏移页内偏移d实页号实页号p多用户虚页号多用户虚页号U,P主存实地址主存实地址实页号实页号p装入装入1慢表（按地址访问）慢表
42、（按地址访问）快表（按内容访问）快表（按内容访问）2 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系59/169本章内容虚拟存储系统加快内部地址变换速度的方法 将快表的按内容相联访问变成按地址访将快表的按内容相联访问变成按地址访问，从而可以加大快表容量。为提高快表的问，从而可以加大快表容量。为提高快表的查找速率采用散列查找法，散列（查找速率采用散列查找法，散列（Hash）函数为：快表地址函数为：快表地址H(多用户虚页号多用户虚页号)，为，为避免散列冲突采用相等比较器。避免散列冲突采用相等比较器。2 之 1Computer Architect
43、ureV3同济大学.电子与信息工程学院.计算机科学与工程系60/169本章内容虚拟存储系统加快内部地址变换速度的方法实页号实页号用户号用户号U页内偏移页内偏移Dp虚页号虚页号P多用户多用户虚地址虚地址按地址访问的快表按地址访问的快表页内偏移页内偏移d实页号实页号p多用户虚页号多用户虚页号Pv主存实地址主存实地址散列变换散列变换（硬件实现）（硬件实现）相等比较相等比较多用户虚页号多用户虚页号Pv查慢表查慢表快表地址快表地址Ah快表快表命中命中2 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系61/169本章内容虚拟存储系统加快内部地址变换速度
44、的方法 IBM 370/168计算机的虚拟存储器快表计算机的虚拟存储器快表结构及地址变换过程见后结构及地址变换过程见后图图。虚拟地址长。虚拟地址长48位，页面大小为位，页面大小为4KB，每个用户最多占每个用户最多占用用4K个页面，最多允许个页面，最多允许16M个用户，但同个用户，但同时上机的用户数一般不超过时上机的用户数一般不超过6个。个。采用了两项新的措施：采用了两项新的措施：w 采用两个相等比较器采用两个相等比较器w 用相联寄存器组把用相联寄存器组把24位用户号位用户号U压缩成压缩成3位位2 之 12 24 41 12 21 12 2 多多用用户户虚虚地地用用户户号号 U U虚虚页页号号
45、P P页页内内偏偏移移 D D相相联联比比较较U U1 10 01 10 0U U2 20 01 11 1实实页页号号 p p页页内内偏偏移移 d dU U3 31 10 00 0U U4 41 10 01 1U U5 51 11 10 0 或或U U6 61 11 11 1 拼拼接接相相联联寄寄存存器器组组I ID D 1 15 5 位位 不不等等相相等等比比较较 不不等等相相等等比比较较散散列列变变换换 6 6 位位I ID D 与与 P P 拼拼接接p pI ID D 与与 P P 拼拼接接p p多多用用户户虚虚页页号号 实实地地址址 多多用用户户虚虚页页号号 实实地地址址快快表表（按按
46、地地址址访访问问，有有两两组组）I IB BM M3 37 70 0/1 16 68 8 计计算算机机的的虚虚拟拟存存储储器器快快表表结结构构相等相等2 之 2Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系63/169本章内容虚拟存储系统w 概述概述w 页面替换算法页面替换算法随机算法（随机算法（RAND 算法）算法）先进先出算法（先进先出算法（FIFO算法）算法）近期最少使用算法近期最少使用算法（LFU算法）算法）最久没有使用算法最久没有使用算法（LRU算法）算法）最优替换算法（最优替换算法（OPT算法）算法）w 堆栈型算法堆栈型算法Compu
47、ter ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系64/169本章内容虚拟存储系统页面替换算法w 当发生页面失效时，要从磁盘中调入一页到主当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，此时必须存。如果主存所有页面都已经被占用，此时必须从主存储器中淘汰掉一个不常使用的页面，以便从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。腾出主存空间来存放新调入的页面。w 一是命中率要高，二是算法要容易实现。一是命中率要高，二是算法要容易实现。Computer ArchitectureV3同济大学.电子与信息工程学院.计算
48、机科学与工程系65/169本章内容虚拟存储系统页面替换算法 利用软件或硬件的随机数发生器来确定利用软件或硬件的随机数发生器来确定主存中要被替换的页面。主存中要被替换的页面。算法简单，容易实现；但没有利用历史算法简单，容易实现；但没有利用历史信息，没有反映程序的局部性，命中率低。信息，没有反映程序的局部性，命中率低。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系66/169本章内容虚拟存储系统页面替换算法 选择最先调入主存的页面作为要被替换选择最先调入主存的页面作为要被替换的页面。的页面。比较容易实现，利用了历史信息，但没比较容易实现，利用了历史信
49、息，但没有反映程序的局部性。有反映程序的局部性。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系67/169本章内容虚拟存储系统页面替换算法 选择近期最少访问的页面作为要被替换选择近期最少访问的页面作为要被替换的页面。的页面。既充分利用了历史信息，又反映了程序既充分利用了历史信息，又反映了程序的局部性，但实现起来非常困难。的局部性，但实现起来非常困难。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系68/169本章内容虚拟存储系统页面替换算法 选择近期最久没有被访问过的页面作为选择近期最久没有被访问过的
50、页面作为要被替换的页面。要被替换的页面。既充分利用了历史信息，又反映了程序既充分利用了历史信息，又反映了程序的局部性，而且实现起来比较容易。的局部性，而且实现起来比较容易。Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系69/169本章内容虚拟存储系统页面替换算法 选择将来最久不被访问的页面作为要被选择将来最久不被访问的页面作为要被替换的页面。替换的页面。OPT算法是一种理想化的算法，可用来算法是一种理想化的算法，可用来作为评价其它页面替换算法好坏的标准。作为评价其它页面替换算法好坏的标准。3 之 1Computer ArchitectureV3同
