计算机系统结构第三章-存储系统课件.ppt

《计算机系统结构第三章-存储系统课件.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构第三章-存储系统课件.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 存储系统（P130）长期存在的问题：在合理的总价格限制下，单纯性主存设备的速度跟不上CPU的发展，容量不能满足软件尺寸扩大。本章学习两种提高主存系统性能/价格比的结构化方法：并行存储器与存储层次技术。后者为主。2003.3.1 1 计算机系统结构Proc60%/yr.DRAM7%/yr.110100100019801981198319841985198619871988198919901991199219931994199519961997199819992000DRAMCPU1982Processor-MemoryPerformance Gap:(grows 50%/year)Per

2、formance“Moores Law”Processor Only Thus Far in Course:CPU cost/performance,Pipelined Execution CPU-DRAM Gap 1980:no cache in proc;1995 2-level cache on chip(1989 first Intel proc with a cache on chip)提高存储器性能的必要性2003.3.1 2 计算机系统结构3.1 并行存储器（P136）并行存储器技术可以提高主存系统的整体等效速度，实际应用中，常将它与存储层次技术组合使用，可以互为补充，获得很高的

3、性能。并行存储器技术的基本思想是用多个独立的存储部件组成主存系统，让它们并行工作，在一个存储周期内可以访问到多个数据，从而实现较高的存取流量。并行存储器包括多种类型，我们介绍提高访问容量的高位交叉访问存储器和提高访问速度效果最显著的低位交叉访问这两种。2003.3.1 3 计算机系统结构高位交叉访问存储器：它由n个存储体组成（一般n为2的整次幂），每个体均有独立的地址译码器和数据缓冲器，以主存地址高位字段（最高的log2n位）作为体选译码信号，而剩下的低位字段则是体内地址。如图所示（设 n=4）。2003.3.1 4 计算机系统结构低位交叉访问并行存储器的结构：它由n个存储体组成（一般n为2的

4、整次幂），每个体均有独立的地址译码器和数据缓冲器，以主存地址低位字段（最低的log2n位）作为体选译码信号，而剩下的高位字段则是体内地址。如图所示（设 n=4）。2003.3.1 6 计算机系统结构主存地址与结构参数的换算（P139）：其中：n 存储体个数，A 主存地址，j 体内地址，k 体序号（k=0，1，2，n-1）例3.1 已知 n=4，问主存地址13是在几号体的几号单元？解：由于 n=4，体选译码信号使用主存地址的最低 log2n=2位，所以地址13（其二进制为1101B）对应的体号k=1（即01B）、体内地址j=3（即11B），也就是说，地址13位于1号体的3号单元（参看前一页插图）

5、。根据上式，所有k值（即体号）相同的地址之间均相差n的整倍数，称之为“模n同余”。2003.3.1 7 计算机系统结构低位交叉访问并行存储器的加速机理：我们衡量存储器件速度的常用指标是存储周期Tm，它是同一存储单元连续两次启动的最小时间间隔，数值越小表明存储器件速度越快。传统存储系统只有一套地址译码器和数据缓冲器，所以各单元必须串行工作，也就是说每个Tm周期内至多只能完成一次访问。由多个存储体构成的并行存储器中，各个存储体都有独立的地址译码器和数据缓冲器，它们可以并行工作，使得一个Tm周期内可完成多次访问，相当于加速了多倍。最好情况下一个Tm周期内可完成n次访问。当前Tm周期中只要发现有一个新

6、的访问地址与前面地址属于同一个存储体，该地址及其后面的地址就会被阻塞（称为访存冲突）,留到下一个Tm周期访问。机器地址序列常常具有顺序性，按照低位交叉的规律分配地址可使相继出现的地址落在相同存储体的概率降到最低（参见上图）。考虑到地址总线与数据总线的拥挤问题，一个Tm周期里发送的多个访问请求最好彼此错开Tm/n时间，如P140图3.11所示，否则实现的复杂度会增加。2003.3.1 8 计算机系统结构对于有n个存储体的主存系统，每个主存周期能取出的平均字数N就是加速比。设 p(k)表示每个主存周期能取出k个字的概率，则：显然，如果 p(n)=1（p(1)p(n-1)=0），则N=n；如果 p(

7、1)=1（p(2)p(n)=0），则N=1。设程序发生转移的概率为g，则：k=1，指从第一个存储体中读出的指令是转移指令，而且转移成功，则 p(1)=g；k=2，指从第二个存储体中读出的指令是转移指令，而且转移成功，则 p(2)=(1-g)g；同理，k=3，p(3)=(1-g)2g k=n-1，p(n-1)=(1-g)n-2g k=n，p(n)=(1-g)n-12003.3.1 10 计算机系统结构2003.3.1 11 计算机系统结构3.2 存储层次原理及性能指标3.2.1 基本原理 定义：a）两个或两个以上的速度、容量和价格各不相同的存储器用硬 件、软件或软件与硬件相结合的方式连接起来成为

8、一个系统；b）这个系统对于应用程序员来讲是透明的；c）从应用程序员来看，它是一个存储器，这个存储器的速度接 近速度最快的那个存储器，存储容量与容量最大的那个存储 器相等。单位容量的价格接近最便宜的那个存储器的价格。分析：由2种或多种存储部件构成的复合存储系统，通过内部管理机构 的自动更换机制，能够不断将大容量低速存储部件中的活跃内 容复制到小容量高速存储部件中（后者作为前者的局部副本）。它既能满足CPU的快速存取需要，又有很大的存储容量，平均 单位价格也很低，等效于同时满足3方面要求的理想单一存储部 件。2003.3.1 13 计算机系统结构 模型：如右图所示，存储层次由n层组成，满足3个不等

9、式：TiTi+1，Sici+1。T min(T1,T2,Tn),存储周期S max(S1,S2,Sn).用MB或GB表示容量C min(C1,C2,Cn),用每位的价格表示M1（T1,S1,C1）M2（T2,S2,C2）Mn（Tn,Sn,Cn）从外部看2003.3.1 15 计算机系统结构3.2.2 存储层次的性能指标（P132-P134）(1)容量：S=S2（理论上）要求：存储系统的容量等于存储容量大的那个存储器 提供尽可能大的地址空间，且能够随机访问。方法：1.只对存储容量大的那个存储器进行编址，存储容量小的 存储器只在内部编址；2.另外设计一个容量很大的逻辑地址空间，在系统内部，对两个存

10、储器分别进行编址，并将这两个存储器的地址 映象到这个逻辑地址空间 虚拟空间。2003.3.1 16 计算机系统结构(3)速度：表现访问速度的参数很多，包括访问周期、存取周期，存取时间等，访问周期与命中率有关。命中率：反映被访问数据事先已在M1的发生概率 其中，N1是对M1存储器的访问次数 N2是对M2存储器的访问次数 等效访问时间：命中时的访问时间为T1，不命中时的访问时间为T2，等效访问时间则是它们的概率均值：2003.3.1 18 计算机系统结构 访问效率：这是一个相对值，便于不同系统之间的比较。访问效率e受H和r的影响（参见右图）：2003.3.1 19 计算机系统结构例3.1：假设T2

11、=5T1，在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。解：当H0.9时，e11(0.95(10.9)0.72 当H0.99时，e21(0.995(10.99)0.96 例3.2：在虚拟存储系统中，两级存储器的速度相差特别悬殊 T2=105 T1。如果要使访问效率e0.9，问需要有多高 的命中率？解：0.9H90000(1H)1 89999.1H89999 计算得H0.9999988888777770.999999 2003.3.1 20 计算机系统结构 这里所说的“预取”技术，并不是根据对程序执行的未来趋势进行猜测以提前调入数据，而仅仅是在发生不命中情况时把调入1个数据

12、字改为调入1个数据块的策略。即当发生不命中的时候,把M2存储器中相邻n个单元的数据组成一个数据块都取出来,送入M1存储器中。根据程序的局部化原理，在当前使用数据周围的其它数据未来被使用的几率大于远处数据，所以该数据块中被提前调入的邻近数据很可能成为未来的命中点，从而提高命中率。采用这种预取技术后新的命中率为：其中：H 原命中率（即按照不命中时取入1数据字的策略）；H 新命中率（即按照不命中时取入1数据块的策略）；n 每块数据被访问次数。(4)预取技术对命中率的提高作用（P134）：2003.3.1 21 计算机系统结构按照定义，原不命中率，新不命中率，并且有。由于预取使得每块数据中的不命中次数

13、降低了n倍，所以有。此式可改写为，整理得。H的推导：2003.3.1 22 计算机系统结构例3.3：在一个Cache存储系统中，当Cache的块大小为一个 字时，命中率为H0.8；假设数据的重复利用率为 5，计算Cache的块大小为4个字时，Cache存储系统 的命中率是多少？假设T2=5T1，分别计算访问效率。解：n4520，采用预取技术之后，命中率提高到：Cache的块大小为一个字时，H0.8，访问效率为：e11(0.85(10.8)0.55 Cache的块大小为4个字时，H0.99，访问效率为：e21(0.995(10.99)0.96 2003.3.1 24 计算机系统结构 加速比（P1

14、93）Cache-主存层次的主要作用是提高访问速度，系统的等效速度应高于主存（即M2）的原有速度，两个速度之比称为加速比。2003.3.1 25 计算机系统结构例3.4：在一个虚拟存储系统中，T2105 T1，原来的命中率 只有0.8，现采用预取技术，访问磁盘存储器的数据 块大小为4K字，如果要求访问效率不低于0.9，计算 数据在主存储器中的重复利用率至少为多少？解：假设数据在主存储器中的重复利用率为m，根据前面的给出关系：解这个方程组，得到m44，即数据在主存储器中 的重复利用率至少为44次。2003.3.1 26 计算机系统结构解：2003.3.1 28 计算机系统结构思考题：P202，题

15、3（课内讨论）。2003.3.1 29 计算机系统结构段式虚拟存储器的地址映象 主程序（0段）1段2段3段段号 段长 起始地址01231K5002002008K16K9K30K段 表程序空间 主存储器01K05000200020008K9K16K30K2003.3.1 31 计算机系统结构段式虚拟存储器的优点如下：1.程序的模块性能好。对于大程序，可以划分成多个程 序段，每个程序段赋予不同的名字，由多个程序员并行编写，分别编译和调试。由于各个程序段在功能上是相互独立的，因此，一个程序段的修改和增删等不会影响其他程序段，从而可以缩短程序的编制和调试时间。2.便于程序和数据的共享。由于程序段是按功

16、能来划分的，如子程序段、数据段、表格段等。每个程序段有比较完整的功能，因此，被共享的可能性很大。3.程序的动态链接和调试比较容易。由于每个程序段都是一组有独立意义的数据块或具有完整功能的程序段，因此，在程序运行过程中，可以根据需要一次就把一个程序段或数据块都装入到主存储器中，并且在装入时才实行动态链接。4.便于实现信息保护。在一般情况下，一段程序是否需要保护是根据这个程序的功能来决定的。因此，只有在段表中设置一个信息保护字段，就能根据需要很方便地实现对该程序的保护。2003.3.1 32 计算机系统结构段式虚拟存储器的缺点：1.地址变换所花费的时间比较长。从多用户虚地址变换到主存实地址需要查两

17、次，做两次加法运算。2.主存储器的利用率往往比较低。由于每个程序段的长度不同的，一个程序段通常要装在一个连续的主存空间中，程序段在主存储器中不断地调入调出，有些程序段在执行过程中还要动态增加长度，从而使得主存储器中有很多的空隙存在。当然，也可以采用一些好的算法来减少空隙的数量，或者通过定时运行回收程序来合并着这些空隙，但这无疑增加了系统的开销。3.对辅存（磁盘存储器）的管理比较难。磁盘存储器通常是按固定大小的块来访问的，如何把不定长度的程序段映象到固定长度的磁盘存储器中，需要做一次地址变换。2003.3.1 33 计算机系统结构(2)页式管理(P151)。页是系统规定的固定长度单位。按页划分用

18、户文件可以避免上述零碎空间浪费。我们把用户文件划分得到的一个长度单位称为“虚页”，因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为“实页”。页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。页式管理方法的虚实变换算法是查页表(P152)。页号 主存页号0123主存储器页 表0页1页2页3页用户程序页式虚拟存储器的地址映象2003.3.1 34 计算机系统结构页式虚拟存储器的优点是：1.主存储器的利用率比较高。每个用户程序只有不到一页（平均为半页）的浪费，与段式虚拟存储器每两个程序段之间都有浪费相比要节省许多。2.页表相

19、对比较简单。它需要保存的字段数比较少，一些关键字段的长度要短许多，因此，节省了页表的存储器容量。3.地址映象和变换的速度比较快。在把用户程序装入到主存储器的过程中，只要建立用户程序的虚页号与主存储器的实页号之间的对应关系即可不必使用整个主存的地址长度，也不必考虑页号的长度等。4.对辅存（磁盘存储器）的管理比较容易。因为页的大小一般取磁盘存储器物理块的大小（512字节）的整数倍。页式虚拟存储器的缺点主要有两个：1.程序的模块化性能不好。由于用户程序是强制按照固定大小的页来划分的，而程序段的实际长度一般是不固定的。因此，页式虚拟存储器中一页通常不能表示一个完整的程序功能。2.页表很长，需要占用很大

20、的存储空间。通常，虚拟存储器中的每一页在页表中都需要占用一个存储字。2003.3.1 35 计算机系统结构(3)段页式管理(P153)。它把上述两种管理方式结合起来，首先将整个文件分段，然后在各段内分页，所以有一个段表和若干个页表。其虚实变换算法是先查段表，查出该段的页表起始地址再查相应的页表(P154)。段页式管理的主要缺点是多查一次表，虚实变换费时较多，占用空间也较大。由于段页式管理方法的最小调度单位仍是页，或者说它是分段之后的分页管理，为了叙述简单，下面的分析还是以页式管理为模型。2003.3.1 36 计算机系统结构段页式虚拟存储器的地址映象0段（12K）1段（10K）2段（5K）每页

21、4KB页表长度 页表地址332段 表0段0页0段1页0段2页1段0页1段1页1段2页0段页表1段页表2段0页2段1页2段页表 用户程序 主存储器2003.3.1 37 计算机系统结构3.3 地址映象与变换(P174)基本术语：逻辑地址（又称为相对地址、虚地址）是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号，总是从0开始（可以按字节编址、按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。物理地址（又称为绝对地址、实地址）是任一级存储器为全部存储单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。从M1到Mn各层都有自己的物理地址空间，而对当前执行

22、的程序模块来说，逻辑地址空间只有一个。地址映象方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。地址变换（又叫虚实变换）指逻辑地址到物理地址的变换过程或者算法。页失效指当前被访问存储级中没有所需的信息，也就是不命中现象。实页争用又叫实页冲突，指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。2003.3.1 38 计算机系统结构相联目录表技术1.页表占用空间过大问题 页表必须存放在实存M1里。实际上，命中情况下的访存时间等于查表时间加上访问目标数据的时间，所以页表不能放在M2。页表占用空间=页表行数 每行宽度其中，页表行数=虚存容量/页面大小 以PC机为例，页表行数

23、 60G/4K=236/212=224 1600万！按每行宽度6字节估算约需96MB。减少页表空间的思路分减少行数和减少行宽两类。2.相联目录表方法（P158）仅保留页表中已装入的虚页记录。为避免逐行比对，利用相联存储器存放此表，它具有并行比较功能，但价格远高于普通存储器。3.快慢表方法（P159）4.通过地址映象减少行宽 如下文所示2003.3.1 39 计算机系统结构4种常见的地址映象方式3.3.1 全相联(P174)全相联就是无约束对应，或者说是一个完全关系，意思就是一个虚页可以调入任何一个实页。这种关系可用下页示意图(a)、(b)表示。全相联的虚实变换信息完全来自于变换表，查表过程如图

24、(c)所示。全相联映象方式使虚页调入有最大的选择范围，发生实页争用的可能性最小，调入/调出的操作开销也最少，有利于命中率提高。但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高，在命中情况下花费在虚实变换上的时间也比较多。由于页表必须常驻在实存中，而主存-辅存层次的实存（即主存）相对Cache-主存层次的实存（即Cache存储器）要低廉一些，所以全相联映象方式一般用于主存-辅存层次。2003.3.1 40 计算机系统结构全相联的地址映象方式与地址变换原理示意图(a)(b)2003.3.1 41 计算机系统结构全相联的地址映象方式与地址变换原理示意图(c)2003.3.1 4

25、2 计算机系统结构3.3.2 直接相联(P176)直接相联是一种最强的约束关系，它规定每个虚页只对应唯一的实页。为了便于虚实变换，用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号。实现起来非常简单，因为在二进制中，任何数X对2的整次幂n求模等价于截取X的最低log2n位，如下页示意图(c)所示。例3.3 已知虚页号=7，实页总数=4，用直接相联求实页号。解：可用十进制形式求：7 mod 4=3；也可用二进制形式求：由于n=4，所以log2n=2，取7的二进制形式111B的最低2位，得11B，即3。直接相联映象方式不需要借助页表来进行虚实变换，显然大大节省了相应的空间与时间（当然页表中

26、的装入位和修改位还得保留），但是由于每个虚页的选择范围太小，实页争用的发生频率较高，常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况，这使系统的命中率和运行效率大大下降。这种映象方式主要用于一些对实存价格非常敏感的Cache-主存层次。2003.3.1 43 计算机系统结构直接相联的地址映象方式与地址变换原理2003.3.1 44 计算机系统结构例：假设在某个计算机系统中Cache容量为64K字节，数据块大小是 16个字节，主存容量是4M，地址映象为直接相联方式。（1）主存地址多少位？如何分配？（2）Cache地址多少位？如何分配？（3）目录表的格式和容量？主存地址格式：区

27、号区内块号 块内地址21 16 15 4 3 0 缓存地址格式：块 号 块内地址15 4 3 0 目录表的格式：主存区号有效位6 1 0 解：容量：应与缓存块数量相同即212=4096 2003.3.1 45 计算机系统结构3.3.3 组相联(P178)组相联映象方式是全相联与直接相联的一个折中方案，性能也是二者的折中。具体做法是先将实存分组，每组内有若干实页，然后将虚存空间也以同样大小分组。所有虚组按照直接相联方式映射到实组集合，对应的虚实组之间各页则用全相联映射，如下页示意图(a)、(b)所示（设实组数为2）。由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，首先根据

28、虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为“组号计算、组内查表”。如图(c)所示。采用组相联映象方式时，每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要低；另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。当然这两方面优点是互相抵触的：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。这种映象方式性价比较好，在Cache-主存层次中被

29、普遍使用。2003.3.1 46 计算机系统结构组相联的地址映象方式与地址变换原理(a)(b)2003.3.1 47 计算机系统结构组相联的地址映象方式与地址变换原理(c)2003.3.1 48 计算机系统结构例：主存容量为1MB，缓存容量为32KB，每块为64个字节，缓存共分128组。请写出：（1）主存与Cache的格式；（2）相关存储器的格式与容量解：主存地址：区号 组号 块号 块内地址19 15 14 8 7 6 5 0 缓存地址：组号 块号 块内地址14 8 7 6 5 0 区号Ei 块号Bi 缓存块号bi装入位9 5 4 3 2 1 0 相关存储器的格式：相关存储器的容量，应与缓存的

30、块数相同，即:组数组内块数=1284=512 2003.3.1 49 计算机系统结构3.3.4 段相联(P184)段相联映象方式也是全相联与直接相联的一个折中方案。它的分段方法与组相联相同，不同的是所有虚段按照全相联方式映射到实段集合，对应的虚实段之间各页则用直接相联映射（因为虚实段大小相同，所以实际上是一一对应），如下页示意图(a)、(b)所示（设实段数为2）。段相联的虚实变换与组相联类似，不过可以通过计算来确定的部分不是在段外，而是在段内，即页表内只储存各虚页对应的实段号，段内页号则从虚页号中简单直接复制，拼接在一起就是实页号，简记为“段号查表、段内复制”。如图(c)所示。段相联映象方式的

31、虚实段内页号对应关系是固定的，每个虚页在调入时可以选择的只是实段号。由于虚实段大小相同，所以虚段号比实段号位数多，也就意味着“多少”的映射（组相联是等量映射），其实页争用的发生频率比组相联要高。在节省页表存储空间方面，性能与组相联差不多。2003.3.1 50 计算机系统结构段相联的地址映象方式与地址变换原理(a)(b)2003.3.1 51 计算机系统结构段相联的地址映象方式与地址变换原理(c)2003.3.1 52 计算机系统结构多用户虚地址格式 在多用户或多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从CPU发出的虚地址还需要在前面拼接上

32、一个“当前用户号”字段，形成“多用户虚地址”，如下图所示(参见P154)。在虚实变换时，上面所说的各种查表操作之前还得先去查一个“段表基址寄存器组”或“页表基址寄存器组”的小表格(P150，P152)，确定现在该查哪一张段表或页表。这个小表格建立在CPU里，读写时间很短。思考题：P203，题11（课内讨论）2003.3.1 53 计算机系统结构页表级数 g 的计算（P157）如果虚拟存储空间的大小为Nv，页面大小为Np，一个页表存储字的大小为Nd，则页面级数g可以通过下面的公式计算：g 2 Nv 2Np2 Np 2 Nd2003.3.1 54 计算机系统结构例：如果一个页式虚拟存储器的Nv4G

33、B，Np1KB，Nd4B，计算机页表的级数。解：第一级页表为1页，存储容量1KB，可以有256个存储字（每个存储字占用4个字节），在这里只需要用其中的64个存储字。用第一级页表的64个存储字指向第二级页表的64个页面，每个页面各有256个存储字，这样二级页表共有16K个存储字。第三级页表共有16K个页面，即4M个存储字，这4M个存储字正好用来存放虚拟存储空间的4M个页面信息。2003.3.1 55 计算机系统结构3.4 替换算法(P164)上面所讲的地址映象方式是在虚页调入时的“选址”规则，而地址变换方法则是命中时获得实地址的手段。不命中时需要增加的操作就是首先调出一页，调出之后再调入称为“替

34、换”。替换算法要解决的是选择调出对象的问题。替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。2003.3.1 56 计算机系统结构3.4.1 几种常用的替换算法(P164)(1)随机算法RAND 在比较范围内任取一页作为淘汰页；优点：算法简单，容易实现。缺点：没有利用历史信息，没有反映程序的局部性，命中率低。(2)先进先出算法FIFO 在比较范围内选取调入最早的一页作为淘汰页；优点：比较容易实现，利用了历史信息，没有反映程序的局部性。缺点：最先调入主存的页面，很可能

35、也是经常要使用的页面。(3)最不经常使用算法LFU 在比较范围内选取最近单位时间内使用 次数最少的一页作为淘汰页；优点：既充分利用了历史信息，又反映了程序的局部性缺点：实现起来非常困难。2003.3.1 57 计算机系统结构(4)最不接近使用算法LRU 在比较范围内选取最后一次使用离现在最久 的一页作为淘汰页；(5)最优替换算法OPT 在比较范围内选取下一次使用时间离现在最久 的一页作为淘汰页。优点：它把LFU算法中的“多”与“少”简化成“有”与“无”，实现起来比较容易。是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。2003.3.1 58 计算机系统结构从LFU到LRU的近似逻辑

36、推理：近期最少使用LFU 最近一个单位时间内使用次数最少 相邻两次使用的平均间隔时间最大 上次使用时间离现在最久 最久没有使用LRU偶然偏差：使用稀疏的页面有可能恰巧刚刚用过，离现在更近。统计性能：“现在”离“上次”使用时间的平均距离，应为相邻两次使用时间距离的1/2，所以大多数情况下LRU与LFU的判断结论应该是一致的。2003.3.1 59 计算机系统结构算法模拟：实存状况图（P166图3.32）以 LRU 算法为例（其中*号表示被选中的淘汰页）：2003.3.1 60 计算机系统结构2003.3.1 61 计算机系统结构LRU与OPT的对称性算法：LRU选择“过去”末次访问离现在最远的，

37、OPT选择未来首次访问离现在最远的。2003.3.1 62 计算机系统结构 这是对某些替换算法的统称。如果某些算法在同一地址流同一时刻的小容量分区情况下的保留页面集合必是大容量分区情况下的保留页面集合的子集（当容量超过虚页总数时，保留页面集合相同），则小容量下的命中点到大容量情况下仍然是命中点，并且随着容量加大，还可能会有新的命中点产生。具有这一特性的一类替换算法中成为“堆栈型算法”。例如：P166图3.32中，对LRU算法，如果实页数增加到4，则t=5时为了调入虚页4就不必替换掉虚页2，而是将虚页1、2、4、5都留在实存，这时大容量分区情况下的保留页面集合S2=1，2，4，5，同一时刻的小容

38、量分区情况下的保留页面集合S1=1，4，5。显然有S1 S2。P167第48行是堆栈型算法的数学定义。堆栈型替换算法的主要性质就是命中率H随着实页分区容量n的上升而单调上升（不减性）。可以证明，LFU、LRU、OPT等算法都是堆栈型算法，而RAND和FIFO算法不是堆栈型算法。P168的图3.34是一个实例，当实页数从3增加到4时，FIFO的命中率反倒从3降到2。具体观察，比如t=7时，S1=1，2，5，S2=2，3，4，5，不满足子集关系。所以FIFO不能保证当实页数增加时，原来的命中点不丢。3.4.2 堆栈型替换算法(P166)2003.3.1 63 计算机系统结构实例：堆栈模拟图 研究堆

39、栈型替换算法的性质，一方面可以设计优化的操作系统算法（例如P167倒数第3行的PFF法），另一方面也可推导出一些分析工具，例如“堆栈模拟法”。堆栈模拟图可以通过一次作图，描述同一地址流在各种实存分区容量下的命中情况。例3.42003.3.1 64 计算机系统结构3.5 提高命中率的方法影响命中率的主要因素：(1)程序在执行过程中的页地址流分布情况。(2)所采用的页面替换算法。(3)页面大小。(4)存储器的容量(5)所采用的页面调度方法。以下，对后三个因素进行分析。2003.3.1 65 计算机系统结构1.页面大小与命中率的关系 页面大小为某个值时，命中率达到最。解释：假设At和At+1是相邻两

40、次访问主存储器的逻辑地址，d=|At-At+1|。如果dSp，At和At+1一定不在同一个页面内。随着Sp的增大，主存的页面数减少，页面的替换将更加频繁。随着Sp的增大而降低。当Sp比较小的时1命 2S中率 SH 页面大小SP 页面大小与主存命中率的关系候，前一种情况是主要的，随着Sp的增大而提高。当Sp达到某一个最大值之后，后一种情况成为主要的，随着Sp的增大而降低。当页面大小增大时，造成的浪费也要增加；当页面大小减小时，页表和页面表在主存储器中所占的比例将增加。2003.3.1 66 计算机系统结构2.主存容量与命中率的关系 主存命中率H随着分配给该程序的主存容量S的增加而单调上升。在S比

41、较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。1.0 命 中 率 H 主存容量S 主存命中率H于贮存容量S的关系2003.3.1 67 计算机系统结构3.页面调度方式与命中率的关系 请求式：当使用到的时候，再调入主存。预取式：在程序重新开始运行之前，把上次停止运行前一段 时间内用到的页面先调入到主存储器，然后才开始 运行程序。优点：可以避免在程序开始运行时，频繁发生页面失效的情况。缺点：如果调入的页面用不上，浪费了调入的时间，占用了主 存资源。2003.3.1 68 计算机系统结构3.6 虚拟存储器与Cache的特点(P146，P1

42、72)常用的两种存储系统:1.Cache 存储系统:由 Cache+主存储器构成Cathe主存储器从系统程序员看2.虚拟存储系统:主存储器+磁盘存储器主存 磁盘存储器从应用程序员看2003.3.1 69 计算机系统结构虚拟存储器与Cache的主要区别（P173页）存储系统Cache虚拟存储器要达到的目标 提高（主存）速度 扩大（主存）容量实现方法 全部硬件 软件为主，硬件为辅两级存储器的速度比3倍10倍 105倍页（块）大小1字16字 1KB16KB等效存储容量 主存储器 虚拟存储器透明性 对系统和应用程序员 仅对应用程序员不命中时处理方式 等待主存储器 任务切换2003.3.1 70 计算机

43、系统结构 使用Cache的动机动机：容量大的存储器（DRAM）速度慢 容量小的存储器（SRAM）速度快通过如下策略，使得平均访问时间变小：在小量、高速的存储器中完成大多数访问减少对大容量存储器的带宽要求。2003.3.1 71 计算机系统结构Cache 块号B 块内地址W 主存-Cache地址变换 块号b 块内地址w Cache替换部件 主存地址替换块装入块不命中命中数据或指令Cache地址主存地址(来自CPU)已满未满主存储器2003.3.1 72 计算机系统结构 工作流程命中不命中 已满 替换策略 替换块未满 装入块 与虚存（VM）的区别当未命中的时候，在Cache中，用主存地址访问主存储

44、器，从主存中读出一个字直接送入CPU，同时将被访问的信息从主存中装入到Cache里。而在VM中，必须先将虚存的内容调入到主存，再从主存送入CPU，虚存和CPU间没有直接的数据通路。在Cache 存储系统中，把Cache 和主存储器都划分成相同大小的块。因此，主存地址由块号B和块号W两部分组成。同样，Cache的地址也由块b和块内地址w组成。工作原理2003.3.1 73 计算机系统结构 Cache 的写操作 1.1.全写法 全写法，亦称写直达法(WT法Write through)：在对Cache进行写操作的同时，也对主存该内容进行写。2.2.写回法 写回法(WB法Write back)：在CP

45、U执行写操作时，只写Cache，不写入主存；需要替换时，把修改过的块写回主存。3.3.写不命中 写不命中：不按写分配法 不按写分配法 按写分配法 按写分配法 按写分 按写分配法 配法不按写 按写分配法 分配法直接将数据写入主存，不调入缓存。数据写入主存，并将该数据调入Cache。2003.3.1 74 计算机系统结构 CacheCache的实用举例的实用举例 1.Cache的分体 多体存储器：分为数据体Cache与指令体Cache。原因：a)数据与指令不在一体可以减少多个访问源访问存储器的冲突；b)两个体的访问操作不完全相同，数据体有读操作和写操作，而指令体只有读操作。因此在替换时，只有数据体

46、有写回的问题。在Cache容量相等的情况下，指令与数据分体的Cache比一体化的Cache命中率要高。2003.3.1 75 计算机系统结构2.Cache的分级 实例：Pentium PC的Cache 1 12 114 2 0微缓存地址 组号 双字 字节5组内块号 数据 数据 数据0101位 标记 M 标记 E 标记 S组号 0 1127 标记 I 标记 S 标记 E 数据 数据 数据目录1路120位 2位32字节 32字节路020位 2位目录0主存地址：2003.3.1 76 计算机系统结构本章小结(1)并行存储系统原理；(2)存储层次的原理及5项性能指标；(3)存储层次的3种管理方式；(4

47、)4种地址映象与地址变换方式；(5)5种替换算法；(7)主存-辅存层次与Cache-主存层次的特点。习题：P206，题19(3)(4)(6)(8)。2003.3.1 77 计算机系统结构第三章补充练习题1（堆栈模拟图应用）一个二级存储层次，采用全相联映象和最久没有使用算法，实存共5页，为2道程序分享，页地址流分别如下P1=1 2 3 4 1 3 2 1P2=1 2 3 4 2 2 3 3试作2个实存分配方案，分别使2道程序满足(1)命中率相同；(2)命中次数之和最大。解：分别为2道程序作“堆栈模拟图”，其中“”表示命中。2003.3.1 78 计算机系统结构程序1“堆栈模拟图”2003.3.1 79 计算机系统结构程序2“堆栈模拟图”2003.3.1 80 计算机系统结构将两图结果综合，得到4个分配方案的命中率情况表如下结论如下(1)命中率相同的方案是 n1=3 而 n2=2；(2)命中次数之和最大的方案是 n1=4 而 n2=1。2003.3.1 81 计算机系统结构