第4章 存贮体系

1、第4章 存贮体系4.1存贮体系的形成与性能存贮体系的形成与性能4.2虚拟存贮虚拟存贮4.3高速缓冲存贮器高速缓冲存贮器CacheCache4.4主存保护主存保护本章重点：本章重点： 段页式和页式虚拟存贮器的原理；页式虚拟存段页式和页式虚拟存贮器的原理；页式虚拟存贮器的地址映像；贮器的地址映像；LRU/FIFO/OPTLRU/FIFO/OPT替换算法进行页替换算法进行页面替换的过程模拟；面替换的过程模拟；LRULRU算法对页地址流的堆栈算法对页地址流的堆栈处理模拟及性能分析；处理模拟及性能分析；CacheCache存贮器的直接和组存贮器的直接和组相联地址映像；相联地址映像；LRULRU替换算法的

2、硬件实现及替换替换算法的硬件实现及替换过程模拟；过程模拟；CacheCache存贮器的性能分析等。存贮器的性能分析等。本章难点：本章难点： 段页式和页式中虚实地址的计算；各种页面替段页式和页式中虚实地址的计算；各种页面替换算法的模拟和页面命中率的计算；换算法的模拟和页面命中率的计算；CacheCache组相组相联映像和块替换算法的模拟。联映像和块替换算法的模拟。4.1 存贮体系的形成与性能 存储器系统是计算机系统的重要组成部分，现代计算机系统存储器系统是计算机系统的重要组成部分，现代计算机系统都以存储器为中心，程序若要运行，必须先把有关程序和数据装都以存储器为中心，程序若要运行，必须先把有关程

3、序和数据装到存储器中。到存储器中。 l存储器系统与存储器是两个完全不同的概念。存储器系统与存储器是两个完全不同的概念。如果在一台计算机中只有存储器，甚至有多种如果在一台计算机中只有存储器，甚至有多种存储器，但没有存储系统，那么，这台计算机存储器，但没有存储系统，那么，这台计算机的性能将会是很差的，这些存储器的性能也不的性能将会是很差的，这些存储器的性能也不可能得到充分发挥。可能得到充分发挥。l在一台计算机中有多种存储器种类：主存储器（或称内存）、Cache、通用寄存器、磁盘存储器、各种缓冲存储器、磁带和光盘存储器等。从构成存储器的材料上看，有ECL、TTL、MOS、静态存储器SRAM、动态存储

4、器DRAM，还有磁表面存储器和光存储器等。从存储器的访问方式看，有直接译码、先进先出、随机访问、相联访问，也有块交换、文件交换等。4.1.1发展存贮体系的必要性1.1.存贮器的性能要求存贮器的性能要求l一个存储器的性能通常用速度、容量、价格三个主要一个存储器的性能通常用速度、容量、价格三个主要指标来表示，以下也同样用这三个指标来表示存储系指标来表示，以下也同样用这三个指标来表示存储系统的性能。统的性能。速度：指存储器的访问周期（又称存储周期、存取周速度：指存储器的访问周期（又称存储周期、存取周期、读写周期等）、读出时间、频带宽度等期、读写周期等）、读出时间、频带宽度等容量：存储器中的字节容量：

5、存储器中的字节B或者千字节或者千字节KB，或者兆字节，或者兆字节MB和千兆字节和千兆字节GB等不同单位下的数量等不同单位下的数量价格：用每个二进制多少美分（价格：用每个二进制多少美分（$C/bit）等来表示）等来表示 追求的是：大容量、高速度、低价格追求的是：大容量、高速度、低价格 2.2.容量容量 S SM M=W =W l l m m W W：存贮体的字长，单位为：存贮体的字长，单位为bitbit或或ByteByte。 l l：每个存贮体的字数。：每个存贮体的字数。 m m：并行工作的存贮体的个数：并行工作的存贮体的个数。 3.3.速度速度 从下面三个方面来描述从下面三个方面来描述： 1)

6、1)访问时间访问时间T TA A T TA A是存贮器接到访存到信息被读到数据总线上是存贮器接到访存到信息被读到数据总线上 所需的时间。是确定所需的时间。是确定CPUCPU与存贮器时间关系的重与存贮器时间关系的重 要指标。要指标。 2)2)存贮周期存贮周期T TM M T TM M是连续启动一个存贮体所需要的时间间隔。一般来是连续启动一个存贮体所需要的时间间隔。一般来说总比说总比T TA A大。大。 3)3)存贮器频宽存贮器频宽 是指存贮器可以提供的数据传送率，一般用每秒钟所是指存贮器可以提供的数据传送率，一般用每秒钟所传送的信息位数来衡量。传送的信息位数来衡量。 a)a)最大频宽最大频宽B

7、BM M( (极限频宽极限频宽) ) 是存贮器连续访问时能提供的频宽。是存贮器连续访问时能提供的频宽。 单体：单体： B BM M =W/T =W/TM M m m体并行工作：体并行工作：B BM M =mW/T =mW/TM M b)b)实际频宽实际频宽 实际频宽小于最大频宽实际频宽小于最大频宽B BM M。 4.4.价格价格 可以用总价格可以用总价格C C或每位价格或每位价格c c来表示。具有来表示。具有S SM M 位的存贮器每位价格位的存贮器每位价格c=C/Sc=C/SM M。其中包括了存贮。其中包括了存贮 器本身的价格和为该存贮器操作所必须的外围器本身的价格和为该存贮器操作所必须的外

8、围 电路的价格。电路的价格。5.5.结论结论 由于存贮器的价格、速度和容量的要求是矛盾由于存贮器的价格、速度和容量的要求是矛盾 的，为了同时满足三方面的要求，在一个完整的，为了同时满足三方面的要求，在一个完整 的存贮体系中，必须采用不同工艺的存贮器，的存贮体系中，必须采用不同工艺的存贮器， 使得信息以各种方式分布于不同的存贮体。使得信息以各种方式分布于不同的存贮体。 比如：比如： 主存主存 当前活跃的信息，快，少当前活跃的信息，快，少 辅存辅存 暂时不用的信息，慢，多暂时不用的信息，慢，多 虚存虚存 swapswap 从速度来说，主存远远跟不上从速度来说，主存远远跟不上CPUCPU的要求，为的

9、要求，为 了弥补这一差距，特引入并行和重叠技术，构了弥补这一差距，特引入并行和重叠技术，构 成并行主存系统，但这种并行主存的方法提高成并行主存系统，但这种并行主存的方法提高 频宽是有限的，因此还需从系统结构入手，发频宽是有限的，因此还需从系统结构入手，发 展存贮体系。展存贮体系。4.1.2并行主存系统频宽的分析并行主存系统频宽的分析 1.1.类型类型 1)1)单体单字单体单字 存贮器字长存贮器字长W W与与CPUCPU字长字长W W 相同相同, ,一次访问一个存贮器一次访问一个存贮器 字字, ,主存最大频宽主存最大频宽B BM M =W/T =W/TM MW位读出寄存器读出寄存器地址寄存器单体

10、单字存贮器单体单字存贮器l 2) 2)单体多字单体多字 存贮器字长等于存贮器字长等于m m个个CPUCPU字字, ,B BM M =mW/T =mW/TM M W位W位W位W位地址寄存器单体多字单体多字(m=4)(m=4)存贮器存贮器 W位单字长寄存器单字长寄存器在具体实现时，要把地址在具体实现时，要把地址码分成两个部分，其中一码分成两个部分，其中一部分仍作为存储器的地址部分仍作为存储器的地址去访问存储器（因为存储去访问存储器（因为存储器的字数减少了，因此访器的字数减少了，因此访问存储器的地址码可以缩问存储器的地址码可以缩短），而另一部分则去控短），而另一部分则去控制一个多路选择器，从同制一个

11、多路选择器，从同时读出的时读出的n个数据中选择一个数据中选择一个数据输出。个数据输出。 3)3)多体单字交叉多体单字交叉总线控制地址寄存器0 地址寄存器1 地址寄存器2地址寄存器3M0M1M2M3主控(主存控制部件) CPUIOP多体多体(m=4)(m=4)交叉存贮器交叉存贮器00 00FF 0000 01FF 0100 11FF 11存储器地址寄存器（高位）低位 a) a)存贮器字长等于存贮器字长等于m m个个CPUCPU字，字，B BM M =mW/T =mW/TM M。实际频宽大。实际频宽大于单体多字。于单体多字。 单体多字：并行读出的单体多字：并行读出的m m个字要地址顺序的存在于同个

12、字要地址顺序的存在于同一主存单元。一主存单元。 多体单字：多体单字：m m个个CPUCPU字地址不必顺序存放，只要不发生字地址不必顺序存放，只要不发生冲突。冲突。 b)b)编址模式编址模式 M Mj j体的编制模式为：体的编制模式为：m m i+ji+j； 其中其中I=0I=0，1 1， ，l-1l-1，表示第，表示第i i个字；个字； j=0j=0，1 1， ，m-1m-1，表示第，表示第j j个分体；个分体； m m模模 单体多字：一个主存包含的单体多字：一个主存包含的CPUCPU字数字数 多体单字：分体体数多体单字：分体体数模体模体地址编址序列地址编址序列二进制地址码末二位状态二进制地址

13、码末二位状态M M0 0M M1 1M M2 2M M3 30,4,8, 12, ,4i+0, 1,5,9, 13, , ,4i+1, 2,6,10, 14, , ,4i+2, 3,7,11, 15, , ,4i+3, 00011011地址的模地址的模4 4低位交叉编址低位交叉编址 4) 4)多体多字交叉多体多字交叉 多个存贮体，每个存贮体有多个存贮体，每个存贮体有CPUCPU字。字。 上述能并行读出多个上述能并行读出多个CPUCPU字的单体多字和多体字的单体多字和多体单字或多体多字的交叉存贮主存系统统称为并行单字或多体多字的交叉存贮主存系统统称为并行主存系统。主存系统。2.2.分析分析 提高

14、提高m m值，可以提高主存系统的最大频率，但值，可以提高主存系统的最大频率，但并不能线性提高实际频率。并不能线性提高实际频率。 原因：原因： 1)1)模模m m越高，存贮器数据总线越长，导致传输越高，存贮器数据总线越长，导致传输 延迟增加；延迟增加； 2)2)系统效率问题，对于顺序取指，效率可以系统效率问题，对于顺序取指，效率可以 提高提高m m倍，但遇到转移指令，效率就会下降。倍，但遇到转移指令，效率就会下降。3.3.模型分析模型分析 对于对于m m个独立分体的主存系统，处理机发出一个独立分体的主存系统，处理机发出一 串地址为串地址为A A1 1,A,A2 2, , A Aq q的访存申请队

15、，在每个主的访存申请队，在每个主 存周期到来前，申请队被扫描，截取从队头起存周期到来前，申请队被扫描，截取从队头起 的的A A1 1,A,A2 2, , A Ak k的申请序列。申请序列是在要的申请序列。申请序列是在要 求访存申请的求访存申请的k k个地址中，没有两个或两个以上个地址中，没有两个或两个以上 的地址处于同一分体中的最长序列。显然的地址处于同一分体中的最长序列。显然k k表示表示 可以同时访问的分体个数的随机变量，不大于可以同时访问的分体个数的随机变量，不大于m m， 系统效率取决于系统效率取决于k k的均值的均值B B，其值越大，可访问，其值越大，可访问 的分体个数越多，系统效率

16、越高。的分体个数越多，系统效率越高。 1)1)数学模型数学模型 设设p(k)p(k)表示申请序列长度为表示申请序列长度为k k的概率密度函数，的概率密度函数，其中其中k=1,2,k=1,2,m m。则。则k k的均值的均值B B为为 B=kB=k p(k)p(k) B B实际就是每个主存周期所访问的平均字数。而实际就是每个主存周期所访问的平均字数。而p(k)p(k)与程序的状态密切相关，特别是指令转移概与程序的状态密切相关，特别是指令转移概率率p p，它定义为给定下条指令地址为非顺序地址，它定义为给定下条指令地址为非顺序地址的概率。因此的概率。因此 p(k)=(1-p)p(k)=(1-p)k-

17、1k-1 p p， 1km 1km 几何概率几何概率 p(m)=(1-p)p(m)=(1-p)m-1m-1k=1k=1m m 所以，所以，B=kB=k p(k)=1p(k)=1 p+2p+2 (1-p)(1-p) p p + +m + +m (1-p)(1-p)m-1m-1 =(1-(1-p)=(1-(1-p)m m)/p)/p 2) 2)讨论：讨论： a)a)若每条指令都是转移指令且转移成功，即若每条指令都是转移指令且转移成功，即p=1,p=1,则则B=1B=1，就是并行多体交叉存取的实际频宽，就是并行多体交叉存取的实际频宽降到和单体单字一样；降到和单体单字一样； b)b)若所有指令都不转移

18、，即若所有指令都不转移，即p=0p=0，则，则B=mB=m，此时，此时多体交叉存贮的效率最高。多体交叉存贮的效率最高。k=1k=1m m 3) )结论结论 由于程序的转移概率不会很低，数据分布的离由于程序的转移概率不会很低，数据分布的离散性较大，所以单纯靠增大散性较大，所以单纯靠增大m m来提高并行主存系来提高并行主存系统的频宽是有限的，而且性价比还会随统的频宽是有限的，而且性价比还会随m m的增大的增大而下降。如果采用并行主存系统仍不能满足速度而下降。如果采用并行主存系统仍不能满足速度上的要求，就必须从系统结构上改进，采用存贮上的要求，就必须从系统结构上改进，采用存贮体系。体系。存储系统的定

19、义存储系统的定义 l 存储系统：两个或两个以上速度、容量和价格各不相存储系统：两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来的系统称为存储系统。这个系统对应用程法连接起来的系统称为存储系统。这个系统对应用程序员序员透明透明，并且，从应用程序员看它是一个存储器，并且，从应用程序员看它是一个存储器，这个存储器的速度接近速度最快的那个主存储器这个存储器的速度接近速度最快的那个主存储器，存存储容量与容量最大的那个主存储器相等或接近，单位储容量与容量最大的那个主存储器相等或接近，单位容量的价格接近最便宜的那个主存

20、储器。容量的价格接近最便宜的那个主存储器。存储器的层次结构存储器的层次结构 各种存储器的主要性能特性各种存储器的主要性能特性存储器层次 通用寄存器 缓冲栈 Cache 主存储器 磁盘存储器 脱机存储器 存储周期 10ns 10ns 1060ns 60300ns 1030ms 220min 存储容量 512B 512B 8KB2MB 32MB1GB 1GB1TB 5GB10TB 价格($C/KB)1200 80 3.2 0.36 0.01 0.0001 访问方式 直接译码 先进先出 相联访问 随机访问 块访问 文件组 材料工艺 ECL ECL SRAM DRAM 磁表面 磁、光等 分配管理 编译

21、器分配 硬件调度 硬件调度 操作系统 系统/用户系统/用户带宽(MB/S)4008000 4001200 200800 80160 10100 0.20.6 l1955年，IBM公司推出的第一台大型计算机IBM704，CPU和主存储器的工作周期均为12微秒，两者恰好能匹配恰好能匹配工作。到了40多年后的今天，CPU的工作速度提高了4个数量级以上，而主存储器的工作速度仅提高两个数量级，两者根本不能匹配工作。因此，计算机系统结构的设计者们必须面对这一现实，找出解决的方法。 l因为存放在各种存储器中的程序和数据，最终都要送到CPU中进行处理的，因此，从CPU的角度看，希望各层次存储器的工作速度是靠近

22、上面的，存储容量和价格是靠近下面的。这正是存储系统要研究和得到的目标。 我的存我的存储系统储系统又大又又大又便宜！便宜！跟我打交道的存储系跟我打交道的存储系统还挺快！统还挺快！ 存储系统的访问速度、容量和价格与各个存储器的速度、容量和价格之间的关系表示如下： Tmin（T1，T2，Tn），用存储周期表示Smax（S1，S2，Sn），用MB或GB表示Cmin（C1，C2，Cn），用每位的价格表示l本章主要介绍两种存储系统，一种是本章主要介绍两种存储系统，一种是Cache存存储系统储系统，另一种是，另一种是虚拟存储系统虚拟存储系统。在计算机系。在计算机系统中，这两种存储系统的作用是不相同的。统中，

23、这两种存储系统的作用是不相同的。Cache存储系统的主要目标是为了提高存储器存储系统的主要目标是为了提高存储器的的速度速度，而虚拟存储系统的主要目标是为了增，而虚拟存储系统的主要目标是为了增加存储器的存储加存储器的存储容量容量。 lCache存储系统存储系统：由：由Cache和主存储器组成的系统，速度接近和主存储器组成的系统，速度接近Cache，容量接近主存储器，每单位的价格跟主存储器相近，这，容量接近主存储器，每单位的价格跟主存储器相近，这个存储系统全部用硬件来调度，因此，个存储系统全部用硬件来调度，因此，它不仅对应用程序员是透它不仅对应用程序员是透明的，而且对系统程序员也是透明的明的，而且

24、对系统程序员也是透明的。l虚拟存储系统虚拟存储系统：虚拟存储系统由主存储器与联机的外部存储器：虚拟存储系统由主存储器与联机的外部存储器（目前一般为磁盘存储器）构成，采用硬件与软件相结合的方法（目前一般为磁盘存储器）构成，采用硬件与软件相结合的方法来调度。由于虚拟存储系统需要通过操作系统的存储管理系统来来调度。由于虚拟存储系统需要通过操作系统的存储管理系统来调度，因此，调度，因此，对系统程序员来说它是不透明的，但对于在操作系对系统程序员来说它是不透明的，但对于在操作系统之上编程的应用程序员来说是透明的。统之上编程的应用程序员来说是透明的。虚拟存储系统的访问速虚拟存储系统的访问速度与主存储器很接近

25、，存储容量是一个很大的虚拟地址空间，许度与主存储器很接近，存储容量是一个很大的虚拟地址空间，许多计算机的虚拟地址空间为多计算机的虚拟地址空间为4GB，这个空间的大小比主存储器的，这个空间的大小比主存储器的实际存储容量要大得多，整个存储系统的每位的价格仍然接近于实际存储容量要大得多，整个存储系统的每位的价格仍然接近于磁盘存储器。磁盘存储器。4.1.3存贮体系的形成与分支存贮体系的形成与分支 1.容量需求容量需求 1)程序覆盖技术程序覆盖技术 方法：将大程序分块，方法：将大程序分块， 确定在辅存中的位置并放入辅存，然后根据要确定在辅存中的位置并放入辅存，然后根据要 求把当前用到的程序和数据调入主存

26、中指定位求把当前用到的程序和数据调入主存中指定位 置以覆盖或替换那些已在主存但现在不用的段。置以覆盖或替换那些已在主存但现在不用的段。 这只构成一个存贮系统而非存贮体系。主辅存这只构成一个存贮系统而非存贮体系。主辅存 间的调入调出间的调入调出完全由程序员安排完全由程序员安排，增大编程难，增大编程难 度和负担，拉长程序运行时间，也难以使用更度和负担，拉长程序运行时间，也难以使用更 好的算法。好的算法。主存主存辅存辅存程序员程序员 2)增设辅助软硬件增设辅助软硬件 随着随着I/O处理处理机的出现及多道机的出现及多道程序的发展，一道程序的发展，一道程序的运行可以与程序的运行可以与另一道程序的调入调出

27、同时进行。因此主辅存间另一道程序的调入调出同时进行。因此主辅存间的地址定位可以改由辅助软硬件来完成，如图。的地址定位可以改由辅助软硬件来完成，如图。这样就构成了存贮体系，或存贮层次。这样就构成了存贮体系，或存贮层次。主存主存辅存辅存辅助软硬设备辅助软硬设备从整体来看，从整体来看，速度是主存的速度是主存的容量是辅存的容量是辅存的主存主存辅存存贮层次辅存存贮层次速度10万倍价格1 0 0 0倍 如果存贮层次能以接近于辅存的每位价格构成等于辅如果存贮层次能以接近于辅存的每位价格构成等于辅存容量的快速主存，存贮系统的性价比就会大大提高。存容量的快速主存，存贮系统的性价比就会大大提高。进一步完善发展就形

28、成进一步完善发展就形成虚拟存贮系统虚拟存贮系统。这样程序员就。这样程序员就可以用机器指令的地址码对整个程序可以用机器指令的地址码对整个程序统一编址统一编址，这一，这一空间远大于实际主存空间。空间远大于实际主存空间。 这种指令地址码称为这种指令地址码称为虚地址、逻辑地址、程序地址虚地址、逻辑地址、程序地址等，等，其对应的存贮容量称为虚存容量或程序空间；而实际其对应的存贮容量称为虚存容量或程序空间；而实际主存的地址称为物理地址、实主存的地址称为物理地址、实( (存存) )地址，其对应的存地址，其对应的存贮容量称为主存容量、实存容量或实贮容量称为主存容量、实存容量或实( (主主) )存空间存空间 由

29、于由于程序空间远大于主存空间程序空间远大于主存空间，特别多道程序，每，特别多道程序，每个用户只用到主存空间的一部分，不能将程序全部个用户只用到主存空间的一部分，不能将程序全部装入主存，只能把程序空间分成较小的块或页，由装入主存，只能把程序空间分成较小的块或页，由系统负责把所需块或页按需调入主存。当用虚地址系统负责把所需块或页按需调入主存。当用虚地址访问主存时，首先检查其对应的内容是否已在主存。访问主存时，首先检查其对应的内容是否已在主存。若在，就由硬件自动把虚地址变换成实地址去访存；若在，就由硬件自动把虚地址变换成实地址去访存；否则需经辅助软硬件将包含所要访问的单元在内的否则需经辅助软硬件将包

30、含所要访问的单元在内的那一块程序由虚存调入主存，然后进行访问。这样，那一块程序由虚存调入主存，然后进行访问。这样，不论是虚实地址的变换还是程序的调入都不必程序不论是虚实地址的变换还是程序的调入都不必程序员安排，而是透明的。也正符合存贮层次的要求。员安排，而是透明的。也正符合存贮层次的要求。2.速度需求速度需求 由于主存和由于主存和CPUCPU的速度差距已达一个数量级，的速度差距已达一个数量级， 为了解决这一问题，提出了多种办法：为了解决这一问题，提出了多种办法： 1)在在CPUCPU中设置通用寄存器中设置通用寄存器(GR)，让运算直接在，让运算直接在CPUCPU的的GRGR中进行，减少与主存的

31、交往。但主存与中进行，减少与主存的交往。但主存与GRGR间的传送要间的传送要由程序设计者安排，且由程序设计者安排，且GRGR的数目不能过多。的数目不能过多。 2)2)采用存贮器的多体交叉并行存取来提高主存的速度。采用存贮器的多体交叉并行存取来提高主存的速度。但这种方法对速度的改善有限，且有可能使性价比下但这种方法对速度的改善有限，且有可能使性价比下降。降。 3)CacheCache主存存贮层次主存存贮层次 通过在通过在CPUCPU与主存间加一级速度高、容量小、每个与主存间加一级速度高、容量小、每个价格较高的价格较高的高速缓冲存贮器高速缓冲存贮器(Cache)(Cache)，借助于硬件使，借助于

32、硬件使CacheCache和主存构成一个整体。信息在和主存构成一个整体。信息在CacheCache与主存间的与主存间的传送全部由硬件完成，所以传送全部由硬件完成，所以CacheCache对应用程序员和系统对应用程序员和系统程序员都是透明的。程序员都是透明的。高速缓冲高速缓冲 CacheCache 主主 存存 M M辅助硬件辅助硬件CPUCPU从从CPUCPU来看，来看，速度是速度是Cache的的容量是主存的容量是主存的 4)多级存贮层次多级存贮层次 从从M M1 1到到M Mn n，速度变慢，容量增大，价格降低。，速度变慢，容量增大，价格降低。CPUCPUM M1 1M M2 2M M3 3M

33、 Mn n从从CPU来看，来看，速度是速度是M M1 1的，的，容量是容量是M Mn n的，的，价格价格是M Mn n的 程序局部性概念：程序局部性概念： a)a)时间局部性：在最近的未来要用到的信息很时间局部性：在最近的未来要用到的信息很可能是现在正在使用的信息，这是由程序循环造可能是现在正在使用的信息，这是由程序循环造成的，即循环中的语句要被重复执行。成的，即循环中的语句要被重复执行。 b)b)空间局部性：在最近的未来要用到的信息很空间局部性：在最近的未来要用到的信息很可能与现在正在使用的信息在程序空间上相邻或可能与现在正在使用的信息在程序空间上相邻或相近，这是由于指令通常是顺序执行的。相

34、近，这是由于指令通常是顺序执行的。 利用程序局部性，可以预知下一步要访问的利用程序局部性，可以预知下一步要访问的程序块而在程序块而在M M1 1中做好准备。中做好准备。时间局部性：存放近期使用过的块或页。时间局部性：存放近期使用过的块或页。空间局部性：从空间局部性：从M M2 2级把访问字所在页或块一同取到级把访问字所在页或块一同取到M M1 1中。中。4.1.4存贮体系的性能参数存贮体系的性能参数 以如图所示的二级体系以如图所示的二级体系(M(M1 1,M,M2 2) )为例来分析为例来分析 1.存贮体系的每位存贮体系的每位 平均价格平均价格c c c c1 1 S SM1 M1 +c+c2

35、 2 S SM2M2 S SM1 M1 +S+SM2M2 1)M M2 2容量大且便宜容量大且便宜，所以，所以， S SM1M122n nv v，使，使得页表中绝大部分行中实页号得页表中绝大部分行中实页号n nv v字段及其它字段都不字段及其它字段都不再有用了，这就会大大降低页表的空间利用率。再有用了，这就会大大降低页表的空间利用率。 c)解决办法解决办法 将页表中装入位为将页表中装入位为0的行用实页号的行用实页号n nv v字段存放该程序字段存放该程序此虚页在辅存中的实地址，以便调页时实现用户虚页此虚页在辅存中的实地址，以便调页时实现用户虚页号到辅存实地址的变换。号到辅存实地址的变换。 相联

36、目录表法相联目录表法: :把页表压缩成只存放已装入主存的那把页表压缩成只存放已装入主存的那些虚页些虚页( (用基号用基号b b和和N Nv v标识标识) )与实页位置与实页位置(n(nv v) )的对应关系。的对应关系。这样该表最多为这样该表最多为2 2n nv v行，简称为目录表法，采用按内容行，简称为目录表法，采用按内容访问的相联存贮器构成。如下图：访问的相联存贮器构成。如下图：基号基号用户虚页号用户虚页号页内位移页内位移某用户虚地址某用户虚地址基号用户基号用户 虚页号虚页号实页号实页号其它其它信息信息目录表目录表( (存在相联存贮器中存在相联存贮器中) )相联比较相联比较查找到查找到目录

37、表法目录表法NvbNrnvnvnr(Nr)npb+Nv2 2n nv v行行 d)相联存贮器相联存贮器 在一个存贮周期内能将给定的在一个存贮周期内能将给定的N Nv v同时与目录表的全同时与目录表的全部部2 2n nv v个单元对应的虚页号字段内容比较进行相联查找。个单元对应的虚页号字段内容比较进行相联查找。如有相符的即相联查找到时，表示此虚页已装入主存，如有相符的即相联查找到时，表示此虚页已装入主存，该单元存放的实页号该单元存放的实页号n nv v就是此虚页所存放的实页位置，就是此虚页所存放的实页位置，将其读出拼接上将其读出拼接上N Nr r就可形成访存实地址就可形成访存实地址n np p；

38、如无相符的；如无相符的即相联查找不到，表示此虚页未装入主存，发生页面失即相联查找不到，表示此虚页未装入主存，发生页面失效，请求从辅存中调页。由此可见，采用目录表法不用效，请求从辅存中调页。由此可见，采用目录表法不用设置装入位了。设置装入位了。 6)虚页的调入虚页的调入 当发生页面失效时，要想把该道程序的虚页当发生页面失效时，要想把该道程序的虚页 调入主存，必须给出该页在辅存中的实际地址。调入主存，必须给出该页在辅存中的实际地址。 为了提高调页效率，辅存一般是按信息块编址为了提高调页效率，辅存一般是按信息块编址 的，且块的大小等于页面大小。以磁盘为例，的，且块的大小等于页面大小。以磁盘为例， 辅

39、存实辅存实( (块块) )地址格式地址格式NvNvd d为：为： 这样就需要将多用户虚页号这样就需要将多用户虚页号N Nv v变换成辅存实变换成辅存实 地址地址NvNvd d 。磁盘号磁盘号柱面号柱面号磁头号磁头号块块 号号NvNvd d 外页表外页表:存放用户虚页号存放用户虚页号N Nv v与辅存实地址与辅存实地址NvNvd d的的 映像关系，用于外部地址变换。映像关系，用于外部地址变换。 内页表内页表:存放用户虚页号存放用户虚页号N Nv v与主存实页号与主存实页号n nv v的映的映 像关系，用于内部地址变换。像关系，用于内部地址变换。 由于虚拟存贮器的页面失效率很低，很少调用外由于虚拟

40、存贮器的页面失效率很低，很少调用外页表进行地址变换，因此外页表存放在辅存中，当页表进行地址变换，因此外页表存放在辅存中，当某道程序初始运行时，才把外页表的内容转录到已某道程序初始运行时，才把外页表的内容转录到已建立内页表的实页号地址字段中，这也是前述当内建立内页表的实页号地址字段中，这也是前述当内页表装入位为页表装入位为0时让实页号地址字段改放该虚页在辅时让实页号地址字段改放该虚页在辅存中的实地址的原因。而且对外页表速度要求低，存中的实地址的原因。而且对外页表速度要求低，可以用软件实现。如下图：可以用软件实现。如下图：磁盘号磁盘号柱面号柱面号 磁头号磁头号 块号块号NvNvd d多用户虚地址多

41、用户虚地址辅存地址辅存地址NrNSuNvNvNvd d1 1装入位装入位辅存实地址辅存实地址 地址变换地址变换( (软件实现软件实现) )已装入已装入外页表外页表虚地址到辅存实地址的变换虚地址到辅存实地址的变换2Nv2.替换算法替换算法 1)解决问题解决问题 当处理机要用到的指令或数据不在主存中时，当处理机要用到的指令或数据不在主存中时， 就会产生页面失效，应去辅存中将包含该指令就会产生页面失效，应去辅存中将包含该指令 或数据的一页调入主存。由于虚存空间比主存或数据的一页调入主存。由于虚存空间比主存 空间大得多，必然会出现主存页面位置已全被空间大得多，必然会出现主存页面位置已全被 占用后又发生

42、页面失效，这时再将辅存中的一占用后又发生页面失效，这时再将辅存中的一 页调入主存时就发生页面争用。只用强制腾出页调入主存时就发生页面争用。只用强制腾出 主存中某页后才能接纳从辅存调来的新页。具主存中某页后才能接纳从辅存调来的新页。具 体选择主存中哪一页作为被替换的页，就是替体选择主存中哪一页作为被替换的页，就是替 换算法要解决的问题。换算法要解决的问题。 2)原则原则 a)有高的主存命中率有高的主存命中率 b)算法便于实现算法便于实现 c)辅助软、硬件成本尽量低辅助软、硬件成本尽量低 3)常用算法常用算法 a)随机算法随机算法( (Random,RAND) ) 用软的或硬的随机数产生器来形成主

43、存中要被替换页用软的或硬的随机数产生器来形成主存中要被替换页的页号。这种算法简单，易于实现，但没有利用主存使的页号。这种算法简单，易于实现，但没有利用主存使用情况的历史信息，反映不了程序的局部性，使主存命用情况的历史信息，反映不了程序的局部性，使主存命中率低，很少采用。中率低，很少采用。 b)先进先出算法先进先出算法(First In First Out,FIFO) 选择最早装入的页作为被替换的页。这种算法选择最早装入的页作为被替换的页。这种算法 实现方便，虽然利用了主存使用情况的历史信息，实现方便，虽然利用了主存使用情况的历史信息， 但是不一定能正确反映出程序的局部性，因为最但是不一定能正确

44、反映出程序的局部性，因为最 先进入的页很可能是现在经常要用到的页先进入的页很可能是现在经常要用到的页。 实页号实页号 占用位占用位 程序号程序号 段页号段页号 计数器计数器(使用位使用位) 程序优先位程序优先位 HS其它信息其它信息012nv-1主存页面表主存页面表 c)近期最少使用算法近期最少使用算法(Least Recently Used, ,LRU) ) 选择近期最少访问的页作为被替换的页。这种选择近期最少访问的页作为被替换的页。这种 算法能比较正确的反映程序的局部性，因为当前算法能比较正确的反映程序的局部性，因为当前 最少使用的页一般来说未来也将很少访问，但完最少使用的页一般来说未来也

45、将很少访问，但完 全按此算法实现比较困难，需要为每个实页都配全按此算法实现比较困难，需要为每个实页都配 置一个字长很长的计数器字段才行。所以一般采置一个字长很长的计数器字段才行。所以一般采 用它的变形，即近期最久没被访问过的页作为被用它的变形，即近期最久没被访问过的页作为被 替换的页。这样把替换的页。这样把“多多”和和“少少”简化成简化成“有有”和和“无无” 之后，实现起来比较方便。之后，实现起来比较方便。 主存页面表主存页面表 OS为实现主存管理而设置的，是对主存而言为实现主存管理而设置的，是对主存而言 的，整个主存只有一个。每一行用来记录主存中的，整个主存只有一个。每一行用来记录主存中 各

46、页的使用状况。而页表是对程序空间而言的，各页的使用状况。而页表是对程序空间而言的， 每道程序都有一个，是用来存贮地址映像关系和每道程序都有一个，是用来存贮地址映像关系和 实现地址变换的。实现地址变换的。 实页号实页号:主存页号是顺序的，可以省略主存页号是顺序的，可以省略 占用位占用位:表示该主存页面是否被占用表示该主存页面是否被占用 程序号程序号/段页号段页号:该主存页被哪道程序的哪段该主存页被哪道程序的哪段 哪页占用哪页占用 使用位使用位:表示该主存页近期是否被使用过表示该主存页近期是否被使用过实页号实页号 占用位占用位 程序号程序号 段页号段页号 计数器计数器(使用位使用位) 程序优先位程

47、序优先位 HS其它信息其它信息012nv-1 开始时所有页的使用位全为开始时所有页的使用位全为“0 0”，只要某个页的，只要某个页的 任何单元被访问过，硬件就自动将该页使用位置任何单元被访问过，硬件就自动将该页使用位置 “1 1”。由于采用全相联映像，调入页可进入对应。由于采用全相联映像，调入页可进入对应 于主存页面表中任何占用位为于主存页面表中任何占用位为“0 0”的实页位置，的实页位置， 一旦装入主存某实页上，就置该实页的占用位为一旦装入主存某实页上，就置该实页的占用位为 “1 1”。只有当所有占用位都是。只有当所有占用位都是1 1且又发生页面失效且又发生页面失效 时才有页面替换问题，这时

48、就要用到使用位，只时才有页面替换问题，这时就要用到使用位，只 需替换使用位为需替换使用位为“0 0”的页即可。的页即可。 使用位全使用位全“1 ”处理处理 一种办法是由硬件强制全部使用位都为一种办法是由硬件强制全部使用位都为“0”。 从概念上看，近期最少使用的从概念上看，近期最少使用的“期期”是从上次使用是从上次使用位全位全0到这次使用位全到这次使用位全0的这段时间。由于这个期的长的这段时间。由于这个期的长短是随机的，所以称为随机期法。短是随机的，所以称为随机期法。 另一种办法是它定期的置全部使用位为另一种办法是它定期的置全部使用位为“0”。 每间隔一个固定的时间，如几个毫秒或几秒。把所每间隔

49、一个固定的时间，如几个毫秒或几秒。把所有页面的使用位全部清为有页面的使用位全部清为0。那么，这时候的。那么，这时候的近期近期就是一个固定的时间间隔。当然，这个固定的时间间就是一个固定的时间间隔。当然，这个固定的时间间隔要选择得恰当。既要保证不发生全部使用为位都为隔要选择得恰当。既要保证不发生全部使用为位都为1的情况，又要使这个时间间隔尽可能长些。的情况，又要使这个时间间隔尽可能长些。 l另一种比较好的办法是，在主存页面表中再设置一个另一种比较好的办法是，在主存页面表中再设置一个历史位历史位Hs，或者叫做，或者叫做“未使用计数器未使用计数器”。每间隔一段。每间隔一段时间扫描所有页面的使用位。如果

50、使用位为时间扫描所有页面的使用位。如果使用位为“0”，则，则把对应的把对应的Hs加加“1”，否则，把，否则，把Hs清为清为“0”。同时，无。同时，无论使用位原来是论使用位原来是“0”还是还是“1”，都把它们清为，都把它们清为“0”。这样，扫描结束时，所有页面的使用位就都是这样，扫描结束时，所有页面的使用位就都是“0”，相当于又开始了一个相当于又开始了一个“近期近期”。这种方法与上面两种。这种方法与上面两种方法的不同处在于，它把每一个方法的不同处在于，它把每一个“近期近期”都记录在都记录在Hs中了。因此，中了。因此，Hs的值越大，说明所对应的页面最久没的值越大，说明所对应的页面最久没有被访问过，

51、就应该成为最先被替换掉的页面。有被访问过，就应该成为最先被替换掉的页面。l实质上，前两种方法只反映了一个实质上，前两种方法只反映了一个近期近期内主存页面内主存页面的使用情况，而后一种方法能反映多个的使用情况，而后一种方法能反映多个近期近期内主存内主存页面的使用情况。页面的使用情况。 d)优化替换算法优化替换算法(OPT) 定义定义 无论是无论是“近期最少使用近期最少使用”还是还是“近期最久未用过近期最久未用过” 都属于都属于LRU，与，与FIFO类似，都是根据页面使用类似，都是根据页面使用 的历史情况来预估未来的页面使用状况，只是的历史情况来预估未来的页面使用状况，只是 比比FIFO更好反映局

52、部性而已。然而，这种更好反映局部性而已。然而，这种“近期近期”毕毕竟是过去了的近期，如果能根据未来实际使用情况，竟是过去了的近期，如果能根据未来实际使用情况，替换出近期不用的页，主存命中率会更高，这就是优替换出近期不用的页，主存命中率会更高，这就是优化替换算法化替换算法(Optimal Replacement Algorithm,OPT) 方法方法 在时刻在时刻t找出主存中每个页面将要用到的时刻找出主存中每个页面将要用到的时刻ti，然后选择然后选择tit最大的那一页作为被替换的页。显最大的那一页作为被替换的页。显然，这只有让程序运行一遍得到实际的页地址然，这只有让程序运行一遍得到实际的页地址流

53、，才能找到为实现这种替换算法所需要的各流，才能找到为实现这种替换算法所需要的各页使用信息，这是不现实的。所以，优化替换页使用信息，这是不现实的。所以，优化替换算法只是一种理想化的算法，它可以被用作评算法只是一种理想化的算法，它可以被用作评价其它替换算法好坏的标准，看看哪种替换算价其它替换算法好坏的标准，看看哪种替换算法能使主存的命中率接近于优化替换算法。法能使主存的命中率接近于优化替换算法。 4)影响命命中率的因素影响命命中率的因素 a)与替换算法有关与替换算法有关 例：设有一道程序，有例：设有一道程序，有1 1至至5 5共共5 5页，执行时的页，执行时的 页地址流页地址流( (即执行时依次使

54、用到的程序页页号即执行时依次使用到的程序页页号) )为：为： 2 2，3 3，2 2，1 1，5 5，2 2，4 4，5 5，3 3，2 2，5 5，2 2 若分配给该道程序的主存有若分配给该道程序的主存有3 3页，如下图表示分别用页，如下图表示分别用FIFO,LRU,OPT3FIFO,LRU,OPT3种替换算法对这种替换算法对这3 3页的使用和替换过程。页的使用和替换过程。FIFOFIFO的命中率最低，而的命中率最低，而LRULRU的接近于的接近于OPTOPT的。的。2* *312323命中命中2调进调进 调进调进调进调进53* *1替换替换521* *替换替换5* *24替换替换5* *2

55、4命中命中32* *4替换替换32* *4命中命中354* *替换替换3* *52替换替换 FIFO命中命中3次次2323命中命中2调进调进 调进调进2323命中命中2调进调进 调进调进 LRU命中命中5次次 OPT命中命中6次次页地址流页地址流 2 3 2 1 5 2 4 5 3 2 5 2时间时间t 1 2 3 4 5 6 7 8 9 10 11 1223* *1调进调进2* *51替换替换251* *命中命中25* *4替换替换2* *54命中命中354* *替换替换35* *2替换替换3* *52命中命中3* *52命中命中231* *调进调进23* *5替换替换2* *35命中命中4

56、* *35替换替换4* *35命中命中4* *35命中命中23* *5替换替换235命中命中235命中命中3 3种替换算法对同一页地址流的替换过程种替换算法对同一页地址流的替换过程 b)命中率与页地址流有关命中率与页地址流有关 例如一个循环程序，当所需页数大于分配给例如一个循环程序，当所需页数大于分配给 它的主存页数时，无论是它的主存页数时，无论是FIFO还是还是LRU算法的算法的 命中率都明显低于命中率都明显低于OPT的。如下图所示，的。如下图所示，LRU 和和FIFO一次都没有命中，因为它恰好总是将马一次都没有命中，因为它恰好总是将马 上要用到的页面给替换出去了，从而连续不断上要用到的页面

57、给替换出去了，从而连续不断 的出现页面失效，产生所谓的颠簸现象。的出现页面失效，产生所谓的颠簸现象。 l例例2：一个循环程序，依次使用：一个循环程序，依次使用P1，P2，P3，P4四个四个页面，分配给这个程序的主存页面数为页面，分配给这个程序的主存页面数为3个。个。FIFO、LRU和和OPT三种页面替换算法对主存页面的调度情况三种页面替换算法对主存页面的调度情况如图如图3.33所示。所示。OPT算法命中算法命中3次，而次，而FIFO和和LRU算算法一次也没有命中。在法一次也没有命中。在FIFO和和LRU算法中，总是发生算法中，总是发生下次就要使用的页面本次被替换出去了。这就是下次就要使用的页面

58、本次被替换出去了。这就是颠簸颠簸现象。现象。 一般来说，对于一个循环程序，当分配给它的页面一般来说，对于一个循环程序，当分配给它的页面数小于程序所需要的页面数数时，有可能发生数小于程序所需要的页面数数时，有可能发生颠簸颠簸现象。这时，无论是现象。这时，无论是FIFO算法，还是算法，还是LRU算法，它们算法，它们的命中率都明显地低于的命中率都明显地低于OPT算法。算法。1* *2312142* *3413* *4* *1231* *2342* * FIFO无命中无命中121121 LRU无命中无命中 OPT命中命中3次次页地址流页地址流 1 2 3 4 1 2 3 4时间时间t 1 2 3 4

59、5 6 7 812* *4134* *123* *1* *24命中命中命中命中13* *4命中命中 命中率与页地址流有关命中率与页地址流有关124* *1* *2342* *3413* *4* *1231* *2342* * c)与主存容量与主存容量(即分配给程序的主存页数即分配给程序的主存页数)有关有关 一般来说，分配给程序的主存页数越多，虚一般来说，分配给程序的主存页数越多，虚页装入主存的机会就越多，命中率也可能就越页装入主存的机会就越多，命中率也可能就越高。但具体还与所采用的替换算法有很大关系。高。但具体还与所采用的替换算法有很大关系。如下图所示，当分配给程序的主存页数如下图所示，当分配

60、给程序的主存页数n由由3增增加到加到4时，时，FIFO的命中率反而由的命中率反而由3/12降到降到2/12;而而LRU的命中率却不会发生这种情况，随着分的命中率却不会发生这种情况，随着分配给该道程序的主存页数的增加，命中率一般配给该道程序的主存页数的增加，命中率一般都会得到提高，至少不会降低。都会得到提高，至少不会降低。121* *21413* *4* *1251* *251* *2命中命中51* *2命中命中532* *5* *345* *34命中命中 n=3命中命中3次次12121 n=4命中命中2次次页地址流页地址流 1 2 3 4 1 2 5 1 2 3 4 5时间时间t 1 2 3