计算机系统机构第四精选文档.ppt

《计算机系统机构第四精选文档.ppt》由会员分享，可在线阅读，更多相关《计算机系统机构第四精选文档.ppt（95页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机系统机构第四本讲稿第一页，共九十五页Cache块位置块位置012ncb-1主存主存块块012nmb-12ncb-1块块2ncb+02ncb+122ncb-1块块22ncb+032ncb-10区区1区区2区区2nmbncb-1区区图图 4.35 直接映象规则直接映象规则本讲稿第二页，共九十五页 2)变换变换过程过程主存块号主存块号块内地址块内地址主存地址主存地址 nmnmbnmr ncbncrCache地址地址 nc2ncb项项 相联比较相联比较不等不等 块失效块失效区号区号012ncb-1相等相等访访Cache 区号区号(按地址访问存贮器按地址访问存贮器)由由2ncb 中中 选选 1图图

2、 4.36 直接映象的直接映象的 地址变换过程地址变换过程本讲稿第三页，共九十五页 3)优缺点优缺点 优点：优点：a)所需硬件简单，只需要容量较小的按地址访问所需硬件简单，只需要容量较小的按地址访问 的区号标志表存贮器和少量外比较电路，因此的区号标志表存贮器和少量外比较电路，因此 成本低。成本低。b)访问访问Cache与访问区号表、比较区号是否相符与访问区号表、比较区号是否相符 的操作是同时进行的。当的操作是同时进行的。当Cache命中时就意味着命中时就意味着 省去了地址变换所花费的时间。省去了地址变换所花费的时间。本讲稿第四页，共九十五页 缺点缺点：直接映象法最致命的缺点就是：直接映象法最致

3、命的缺点就是Cache的块的块冲突率很高。只要有两个或两个以上经常使用的块冲突率很高。只要有两个或两个以上经常使用的块恰好被映象到恰好被映象到Cache的同一个块位置时，就会使得的同一个块位置时，就会使得Cache的命中率急剧下降。而且，即使此时的命中率急剧下降。而且，即使此时Cache中有大量的空闲块存在，仍然会发生块失效和块冲中有大量的空闲块存在，仍然会发生块失效和块冲突，无法使用突，无法使用Cache中的空闲块，所以，中的空闲块，所以，Cache的的利用率很低。正是因为这个原因才使得目前采用直利用率很低。正是因为这个原因才使得目前采用直接映象的接映象的Cache存贮器很少了。存贮器很少了

4、。本讲稿第五页，共九十五页3.组相联映象及其变换组相联映象及其变换 1)思想：简要说明如下图思想：简要说明如下图4.37所示，将所示，将Cache空间和主空间和主存空间都分组，每组存空间都分组，每组S块块(S2s)。Cache一共一共2ncb个块，个块，分成分成Q组组(Q=2q)，整个，整个Cache是一区。主存分成与是一区。主存分成与Cache一样大小的一样大小的2nd个区，其地址按区号、组号、个区，其地址按区号、组号、组内块号、块内地址分成对应的组内块号、块内地址分成对应的4个字段。主存地个字段。主存地址的组号、组内块号分别用址的组号、组内块号分别用q、s 字段表示，它们的字段表示，它们的

5、宽度和位置与宽度和位置与Cache地址的地址的q、s是一致的。是一致的。本讲稿第六页，共九十五页2)规则：组相联映象指的是各组之间直接映象，但组内各块规则：组相联映象指的是各组之间直接映象，但组内各块间则是全相联映象。如图间则是全相联映象。如图4.37所示。所示。本讲稿第七页，共九十五页组号组号 q组内块号组内块号 s块内地址块内地址 ncr组号组号 q组内块号组内块号 s块内地址块内地址 nmr区号区号 nd1位位1位位2位位2位位1位位ncbnmbncnm块位置块位置0 块块01122334455667789101112131415012301230123012301230123第第0组组

6、第第0组组第第1组组第第1组组第第0组组第第1组组 第第0区区(Cache容量容量)第第1区区(Cache容量容量)Cache主存主存 组内全相联组内全相联 组间直接相联组间直接相联图图4.37 组相联映象规则组相联映象规则 本讲稿第八页，共九十五页 3)讨论讨论 当组相联映象的当组相联映象的S值大到等于值大到等于Cache的块数的块数(即即s=ncb)时就变成了全相联映象，而当时就变成了全相联映象，而当S值小到只有值小到只有1块块(即无即无s字段字段)时就变成了直接映象。因此全相联映象和直接映时就变成了直接映象。因此全相联映象和直接映象只是组相联映象的两个极端。在象只是组相联映象的两个极端。

7、在Cache空间大小及空间大小及块的大小都已经确定的情况下，块的大小都已经确定的情况下，Cache的总块数就定的总块数就定了，但结构设计者仍可以对了，但结构设计者仍可以对S和和Q值进行选择。值进行选择。Q和和S的选取主要依据对块冲突概率、块失效率、映象表复的选取主要依据对块冲突概率、块失效率、映象表复杂性和成本、查表速度等的折衷权衡。组内块数杂性和成本、查表速度等的折衷权衡。组内块数S愈愈多，块冲突概率和块失效率愈低，映象表愈复杂、成多，块冲突概率和块失效率愈低，映象表愈复杂、成本愈高，查表速度愈慢。所以通常采用在典型工作负本愈高，查表速度愈慢。所以通常采用在典型工作负荷下进行模拟而定。荷下进

8、行模拟而定。本讲稿第九页，共九十五页 4)地址变换地址变换组号组号 q组内块号组内块号 s块内地址块内地址 nmr区号区号 nd组号组号 q组内块号组内块号 s块内地址块内地址 ncrnmnc直接直接直接直接相联比较相联比较不等不等块失效块失效相等相等相联比较相联比较ndssnd s表的总容量为表的总容量为2ncb 2q2s行行2q组组中中选选 1 12s行行本讲稿第十页，共九十五页4.段相联映象段相联映象 在全相联、直接相联、组相联映象的基础上还可在全相联、直接相联、组相联映象的基础上还可以有各种变形，段相联就是一例。段相联实质上是以有各种变形，段相联就是一例。段相联实质上是组相联的特例。他

9、是采用组间全相联、组内直接映组相联的特例。他是采用组间全相联、组内直接映象。为了与组相联加以区别，将这种映象方式称为象。为了与组相联加以区别，将这种映象方式称为段相联。就是说，段相联映象是把主存和段相联。就是说，段相联映象是把主存和Cache分分成具有相同的成具有相同的Z块的若干段，段与段之间采用全相块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象。如图联映象，而段内各块之间采用直接映象。如图4.42所示：所示：本讲稿第十一页，共九十五页 块块0块块1块块2Z1Cache主存主存 块块0块块1块块2Z1 块块0块块1块块2Z1 块块0块块1块块2Z1 块块0块块1块块2Z1段段

10、0段段0(Z个段个段)段段1段段2nmb/Z1段段2ncb/Z1图图4.42 具有每段具有每段Z个块的断相联映象个块的断相联映象段间全相联段间全相联 段内直接段内直接本讲稿第十二页，共九十五页4.3.3替换算法的实现替换算法的实现 当访存发生当访存发生Cache块失效，需要把主存块按所采块失效，需要把主存块按所采用的映象规则装入用的映象规则装入Cache时，如果又出现时，如果又出现Cache块冲块冲突，就必须按某种策略选择将突，就必须按某种策略选择将Cache中的哪一块替中的哪一块替换出去。换出去。Cache主存存贮层次的替换算法与虚主存存贮层次的替换算法与虚拟存贮器的没有什么不同，不外乎也是

11、拟存贮器的没有什么不同，不外乎也是FIFO法或法或LRU法，其中法，其中LRULRU法最为常用。法最为常用。本讲稿第十三页，共九十五页1.堆栈法堆栈法 1)思想思想 我们在我们在4.2.2中讲过，中讲过，LRU法是堆栈型替换算法，法是堆栈型替换算法，也讲了对于也讲了对于LRU算法，堆栈算法，堆栈St中由栈顶到栈底的各中由栈顶到栈底的各项（行）恒反映出到项（行）恒反映出到t时刻，实存中各页被访问过的时刻，实存中各页被访问过的近远次序，以及每访问一页，堆栈近远次序，以及每访问一页，堆栈St中各项的变换中各项的变换过程。结果是此堆栈的栈顶恒存放近期最近访问过过程。结果是此堆栈的栈顶恒存放近期最近访问

12、过的页的页号，而栈底恒存放近期最久没有方问过的的页的页号，而栈底恒存放近期最久没有方问过的页的页号，即准备被替换掉的页的页号。那么，我页的页号，即准备被替换掉的页的页号。那么，我们在们在Cache主存存贮层次中就可以按此思想实主存存贮层次中就可以按此思想实际组成一个硬件堆栈。际组成一个硬件堆栈。本讲稿第十四页，共九十五页 2)过程过程（块号）（块号）（块号）（块号）（块号）（块号）（块号）（块号）（块号）（块号）2ncb个寄存器个寄存器需重新排列的块号需重新排列的块号 都下推一行都下推一行 被访问的块号被访问的块号（经相联比较找到）（经相联比较找到）寄存器堆栈寄存器堆栈 压入压入ncb位位近期

13、最近访近期最近访 问过的块问过的块近期最久没有近期最久没有 访问过的块访问过的块图图 4.43 全相联映象全相联映象LRU法经堆栈实现（需要有相联比较功能）法经堆栈实现（需要有相联比较功能）本讲稿第十五页，共九十五页 3)缺点：缺点：这种硬件堆栈既要求具有相联比较的功能，又要这种硬件堆栈既要求具有相联比较的功能，又要求能全下移、部分下移和从中间取出一项的功能，求能全下移、部分下移和从中间取出一项的功能，成本较高，因此只适用于组相联且组内块数较少的成本较高，因此只适用于组相联且组内块数较少的LRU替换场合。替换场合。4)变形变形 上述这种堆栈，各块被访问的先后次序由该项在上述这种堆栈，各块被访问

14、的先后次序由该项在堆栈中距离栈底是近还是远来反映。为了避免堆栈堆栈中距离栈底是近还是远来反映。为了避免堆栈中各行存放的内容经常同时进行下移，以便节省成中各行存放的内容经常同时进行下移，以便节省成本，我们采用另一种变形，即将存放块号的寄存器本，我们采用另一种变形，即将存放块号的寄存器的几何位置与的几何位置与Cache中的块号对应，而用寄存器存中的块号对应，而用寄存器存本讲稿第十六页，共九十五页放值的大小来表示已被访问过的远近次序。以组相放值的大小来表示已被访问过的远近次序。以组相联为例，每一组均使用如图联为例，每一组均使用如图4.44那样的一个寄存器那样的一个寄存器组，由组，由2s个寄存器组成，

15、每个寄存器为个寄存器组成，每个寄存器为s位宽，可以位宽，可以存放表示从存放表示从0到到2s1的次序值。如果让越是最近访的次序值。如果让越是最近访问的，其次序值愈小，则只需通过相联比较求最大问的，其次序值愈小，则只需通过相联比较求最大值（不是相联比较相符），找到该最大值所在的寄值（不是相联比较相符），找到该最大值所在的寄存器号，这就是对应存器号，这就是对应Cache中应该被替换掉的块的中应该被替换掉的块的块号。块号。本讲稿第十七页，共九十五页第第0块的访问次序块的访问次序第第1块的访问次序块的访问次序第第2块的访问次序块的访问次序第第2s-1块的访问次序块的访问次序块块0块块1块块2块块2s-1

16、 2s个个寄存器寄存器 S位位（其中一组）（其中一组）Cache存贮器存贮器（其中一组）（其中一组）图图 4.44 组相联组相联LRU法经寄存器实现法经寄存器实现（每组一个，需要有相联比较功能）（每组一个，需要有相联比较功能）本讲稿第十八页，共九十五页2.比较对法比较对法 1)思路思路 比较法的基本思路是让各个块成对组合，用一个比较法的基本思路是让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到序，再经门电路就可以找到LRU块。比如说有块。比如说有A BC三块，互相之间可以组合成三块，互相之间可以组合成AB

17、BA AC CA BC CB6对，其中对，其中AB和和BA、AC和和CA、BC和和CB是重复是重复的，所以的，所以TAB为为“1”，表示，表示A比比B更近被访问过；更近被访问过；TAB为为“0”，则表示，则表示B比比A更近被访问过。更近被访问过。TAC、TBC也类也类似定义。这样，当访问过的次序为似定义。这样，当访问过的次序为A B C，即最近，即最近本讲稿第十九页，共九十五页访问过的为访问过的为A，最久未被访问过的为，最久未被访问过的为C，则这三个触，则这三个触发器状态分别为发器状态分别为TAB1，TAC1，TBC1。如果访。如果访问过的次序为问过的次序为B A C，C为最久未被访问过的块，

18、则为最久未被访问过的块，则此时必有此时必有TAB0，TAC1，TBC1。因此最久未被。因此最久未被访问过的块访问过的块C作为被替换掉的块的话，用布尔代数作为被替换掉的块的话，用布尔代数式必有：式必有：CLRUTAB TACTBC+TAB TACTBC TACTBC同理可得：同理可得：BLRUTABTBC ；ALRUTAB TAC因此，完全可以用门、触发器等硬件组合实现，如因此，完全可以用门、触发器等硬件组合实现，如图图4.45所示：所示：本讲稿第二十页，共九十五页&010101TABTACTBC ALRU BLRU CLRU访问访问B访问访问C访问访问A图图 4.15 用比较对法实现用比较对法

19、实现LRU算法算法本讲稿第二十一页，共九十五页 2)分析分析 我们来看比较对法所用的硬件量。由于每块均可我们来看比较对法所用的硬件量。由于每块均可能作为能作为LRU块，其信号需要用一个与门产生，例如块，其信号需要用一个与门产生，例如ALRU与门要有从与门要有从TAB TAC来的输入，来的输入，BLRU门要有从门要有从TAB，TBC来的输入，而与每块有关的对数个数为块来的输入，而与每块有关的对数个数为块数减去数减去1，所以与门的扇入数是块数减去，所以与门的扇入数是块数减去1。若。若p为为块数，量量组合，比较对触发器的个数应为块数，量量组合，比较对触发器的个数应为Cp2，即，即为为p(p-1)/2

20、。表。表4.2给出了比较对法块数给出了比较对法块数p的取值与门的取值与门数、门的输入端数及比较对触发器数的关系。数、门的输入端数及比较对触发器数的关系。本讲稿第二十二页，共九十五页3)总结总结 替换算法实现的设计要围绕下面两点来考虑：替换算法实现的设计要围绕下面两点来考虑：a)如何对每次访问进行记录（使用位法、堆栈法和比较对如何对每次访问进行记录（使用位法、堆栈法和比较对法所用的记录方法都不同）；法所用的记录方法都不同）；b)如何根据所记录的信息来判定近期内哪一块最久没有被如何根据所记录的信息来判定近期内哪一块最久没有被访问过。由此可见，实现方法和所用的映象方法密切相访问过。由此可见，实现方法

21、和所用的映象方法密切相关。关。例如，对于主存例如，对于主存辅存存贮层次的全相联映象辅存存贮层次的全相联映象宜于采用使用位法或类似的方法，而不宜采用堆栈宜于采用使用位法或类似的方法，而不宜采用堆栈法和比较对法；但对于法和比较对法；但对于Cache主存存贮层次的主存存贮层次的组相联映象，因为组内块数较少，就宜于采用比较组相联映象，因为组内块数较少，就宜于采用比较本讲稿第二十三页，共九十五页对法或堆栈法。替换算法的设计和实现也和器件的对法或堆栈法。替换算法的设计和实现也和器件的发展密切相关，随着器件技术的发展，尤其是高速发展密切相关，随着器件技术的发展，尤其是高速相联存贮器片子的改进，已经而且必然会

22、不断研制相联存贮器片子的改进，已经而且必然会不断研制出新的更好的实现方法。出新的更好的实现方法。本讲稿第二十四页，共九十五页4.3.4 Cache的透明性及性能分析的透明性及性能分析 1.Cache的透明性分析的透明性分析 1)两种问题的出现两种问题的出现 虽然虽然Cache是主存的一部分副本，主存中某单元的是主存的一部分副本，主存中某单元的内容却可能在一段时间里会与内容却可能在一段时间里会与Cache中对应单元的内中对应单元的内容不一致。例如，容不一致。例如，CPU往往Cache写入，修改了写入，修改了Cache中某单元的内容，而在主存中对应于此单元的内容中某单元的内容，而在主存中对应于此单

23、元的内容却可能仍是原来的，没有改变。这时，如果却可能仍是原来的，没有改变。这时，如果CPU或或I/O处理机及其他处理机要经主存交换信息，那么主处理机及其他处理机要经主存交换信息，那么主存内容跟不上存内容跟不上Cache对应内容变化的这种不一致就会对应内容变化的这种不一致就会造成错误。造成错误。本讲稿第二十五页，共九十五页 同样，同样，I/O处理机或其他处理机已把新的内容送入处理机或其他处理机已把新的内容送入主存某个区域，而主存某个区域，而Cache中对应于此区域的副本内中对应于此区域的副本内容却仍可能是原来的。这时，如果容却仍可能是原来的。这时，如果CPU要从要从Cache中读取信息，也会因为

24、这种中读取信息，也会因为这种Cache内容跟不上主存内容跟不上主存对应内容变化的不一致而造成错误。因此，必须采对应内容变化的不一致而造成错误。因此，必须采取措施解决好由于读写过程中产生的取措施解决好由于读写过程中产生的Cache和主存和主存对应内容不一致的问题。对应内容不一致的问题。本讲稿第二十六页，共九十五页 2)写回法写回法 写回法是在写回法是在CPU执行写操作时，只是把信息写入执行写操作时，只是把信息写入Cache，仅当需要被替换时，才将已经被写入过的，仅当需要被替换时，才将已经被写入过的Cache块先送回主存，然后再调入新块。这种方法块先送回主存，然后再调入新块。这种方法也称为抵触修改

25、法，类似于虚拟存贮器中进行页面也称为抵触修改法，类似于虚拟存贮器中进行页面替换时的情况。因此，替换时的情况。因此，Cache主存存贮层次的主存存贮层次的地址映象表中需对地址映象表中需对Cache中的每个块设置一个中的每个块设置一个“修改修改位位”，作为该块装入，作为该块装入Cache后是否被修改过的标志。后是否被修改过的标志。这样在块替换时，根据该块的修改位是否位这样在块替换时，根据该块的修改位是否位1，就可，就可以决定替换时是否先将该块存回主存原来的位置。以决定替换时是否先将该块存回主存原来的位置。本讲稿第二十七页，共九十五页 3)写直达法写直达法 写直达法也称为存直达法，它利用写直达法也称

26、为存直达法，它利用Cache主主存存贮层次在处理机和主存之间的直接通路，每当存存贮层次在处理机和主存之间的直接通路，每当处理机写入处理机写入Cache的同时，也通过此通路直接写入的同时，也通过此通路直接写入主存。这样，在块替换时，就不必先写回主存，而主存。这样，在块替换时，就不必先写回主存，而可以立即调入新页。显然，写回法是把开销花在每可以立即调入新页。显然，写回法是把开销花在每次需要替换的时候，而写直达法则把开销花在每次次需要替换的时候，而写直达法则把开销花在每次写入写入Cache时都附加一个比写时都附加一个比写Cache长的多的写主存长的多的写主存时间。时间。本讲稿第二十八页，共九十五页

27、4)写不命中处理写不命中处理 当出现写不命中时，无论是写回法还是写直达法当出现写不命中时，无论是写回法还是写直达法都有一个在写时是否取的问题。一种是不按写分配都有一个在写时是否取的问题。一种是不按写分配法，即当法，即当Cache写不命中时只写入主存，该写地址写不命中时只写入主存，该写地址单元所在块不从主存调进单元所在块不从主存调进Cache。另一种是按写分。另一种是按写分配法，即当配法，即当Cache不命中时除写入主存外，还把该不命中时除写入主存外，还把该写地址单元所在的块由主存调入写地址单元所在的块由主存调入Cache。这两种策。这两种策略对不同的主存修改算法，其效果不同，但命中率略对不同的

28、主存修改算法，其效果不同，但命中率差别不大。目前写回法一般采用按写分配法，而写差别不大。目前写回法一般采用按写分配法，而写直达法则一般采用不按写分配法。直达法则一般采用不按写分配法。本讲稿第二十九页，共九十五页 写回法和写直达法都需要有少量缓冲器。写回法写回法和写直达法都需要有少量缓冲器。写回法中缓冲器用于暂存将要写回的块，使之不必等待被中缓冲器用于暂存将要写回的块，使之不必等待被替换块写回主存后才开始进行替换块写回主存后才开始进行Cache取。写直达法取。写直达法中缓冲器则用于缓冲由写中缓冲器则用于缓冲由写Cache所要求的写回主存所要求的写回主存的内容，使的内容，使CPU不必等待这些写主存

29、完成就能往下不必等待这些写主存完成就能往下运行。缓冲器由要存的数据和要存入的目标地址组运行。缓冲器由要存的数据和要存入的目标地址组成。在写直达系统中容量为成。在写直达系统中容量为4的缓冲器就可以显著的缓冲器就可以显著改进其性能，改进其性能，IBM 3033就是这样用的。要注意的这就是这样用的。要注意的这些缓冲器对些缓冲器对Cache和主存是透明的。在设计时，要和主存是透明的。在设计时，要处理好可能由它们所引起的错误处理好可能由它们所引起的错误(如另一个处理机要如另一个处理机要访问的主存单元的内容正好仍在缓冲器中访问的主存单元的内容正好仍在缓冲器中)。本讲稿第三十页，共九十五页 5)两种方法对比

30、两种方法对比 a)写回法有利于省去许多将中间结果写入主存的无谓开写回法有利于省去许多将中间结果写入主存的无谓开销。但是增加了销。但是增加了Cache的复杂性。的复杂性。b)可靠性上写回法不如写直达法好。可靠性上写回法不如写直达法好。c)具体采用哪种方法还与系统使用场合有关。具体采用哪种方法还与系统使用场合有关。d)如果让多如果让多CPU共享主存交换信息改成共享共享主存交换信息改成共享Cache交换交换信息，信息的一致性就能得到保证。信息，信息的一致性就能得到保证。e)对于共享主存的多对于共享主存的多CPU系统，绝大多数还是采用各个系统，绝大多数还是采用各个CPU都有自己的都有自己的Cache的

31、方式与共享主存连接。这样的方式与共享主存连接。这样的系统由于的系统由于Cache的透明性，仅靠写直达法并不能保证的透明性，仅靠写直达法并不能保证同一主存单元在各个同一主存单元在各个Cache中的对应内容都一致。如中的对应内容都一致。如下图：下图：本讲稿第三十一页，共九十五页 要采取措施保证让有此单元的各个要采取措施保证让有此单元的各个Cache的内容的内容都一致才行。都一致才行。CPU ACache aCPU BCache b主存主存图图 4.46 每个处理机都有每个处理机都有Cache的共享多处理机系统的共享多处理机系统本讲稿第三十二页，共九十五页 解决办法：解决办法：采用播写法：即任何处理

32、机要写入采用播写法：即任何处理机要写入Cache时，不仅要时，不仅要写入自己写入自己Cache的目标块和主存中，还把信息或者播写的目标块和主存中，还把信息或者播写到所有到所有Cache有此单元的地方，或者让所有有此单元的地方，或者让所有Cache有此单有此单元的块作废以便下次访问时按缺块处理，从主存中重元的块作废以便下次访问时按缺块处理，从主存中重新调入。新调入。控制某些共享信息（如信号灯或作业队等）不等进入控制某些共享信息（如信号灯或作业队等）不等进入Cache。目录表法：即在目录表法：即在CPU读读/写写Cache不命中时，先查主存不命中时，先查主存中的目录表以判定目录块是否在别的中的目录

33、表以判定目录块是否在别的Cache内，以及是内，以及是否正在被修改等，然后再决定如何读写此块。否正在被修改等，然后再决定如何读写此块。本讲稿第三十三页，共九十五页 6)第二种问题第二种问题 Cache内容跟不上已变化了的主存内容的问题，有内容跟不上已变化了的主存内容的问题，有 两种解决办法：两种解决办法：a)当当I/O处理机未经处理机未经Cache往主存写入新内容的同时，由往主存写入新内容的同时，由OS经某个专用指令清除整个经某个专用指令清除整个Cache。这种办法的缺点。这种办法的缺点是象我们在讲述用专用指令清除快表一样，会使是象我们在讲述用专用指令清除快表一样，会使Cache对对OS和系统

34、程序员成为不透明的，因此并不好。和系统程序员成为不透明的，因此并不好。b)当当I/O处理机往主存某个区域写入新内容时，由专用处理机往主存某个区域写入新内容时，由专用硬件自动地将硬件自动地将Cache内对应此区域地副本作废，而不必内对应此区域地副本作废，而不必由由OS进行任何干预，从而保持进行任何干预，从而保持Cache的透明性。的透明性。本讲稿第三十四页，共九十五页2.Cache的取算法的取算法 1)预取法预取法 为了便于硬件实现，通常只预取直接顺序的下一为了便于硬件实现，通常只预取直接顺序的下一块，即在访问到主存的第块，即在访问到主存的第i块块(不论是否已取进不论是否已取进Cache)时，只

35、有第时，只有第i1块才是可能的预取块。至于何时将块才是可能的预取块。至于何时将该块取进，可以有恒预取和不命中时预取两种不同该块取进，可以有恒预取和不命中时预取两种不同的方法。恒预取指的是只要访问到主存的第的方法。恒预取指的是只要访问到主存的第i块的某块的某个字，不论个字，不论Cache是否命中，恒发预取指令。不命是否命中，恒发预取指令。不命中时预取仅当访问第中时预取仅当访问第i块不命中时，才发预取指令。块不命中时，才发预取指令。本讲稿第三十五页，共九十五页 2)影响命中率的其它因素影响命中率的其它因素 a)块的大小：块的大小：若每块的字节数过少，预取的效果不明显。从预若每块的字节数过少，预取的

36、效果不明显。从预取的需要出发，希望块尽可能大。但若每块的字节取的需要出发，希望块尽可能大。但若每块的字节数过多，一方面可能会预取进不需要的信息，另一数过多，一方面可能会预取进不需要的信息，另一方面由于方面由于Cache容量有限，又可能把正在使用或近容量有限，又可能把正在使用或近期使用到的信息给替换出去，反而降低了命中率。期使用到的信息给替换出去，反而降低了命中率。从模拟结果来看，每块的字节数如果超过了从模拟结果来看，每块的字节数如果超过了256，就，就会出现这种情况。会出现这种情况。本讲稿第三十六页，共九十五页 b)预取开销：预取开销：要预取就要有访主存开销和将它取进要预取就要有访主存开销和将

37、它取进Cache的访的访Cache开销，还要加上把被替换的块写回主存的开开销，还要加上把被替换的块写回主存的开销，这些开销会增加主存和销，这些开销会增加主存和Cache的负担，干扰和的负担，干扰和延缓程序的执行。延缓程序的执行。由上可知，采用预取法的效果不能只从命中率的由上可知，采用预取法的效果不能只从命中率的提高来衡量，还需要从所花费的开销多少来考虑。提高来衡量，还需要从所花费的开销多少来考虑。而这种开销的多少可以通过对按需取进法的不命中而这种开销的多少可以通过对按需取进法的不命中开销与预取法的不命中开销和预取开销开销与预取法的不命中开销和预取开销(包括访存开包括访存开销及对销及对Cache

38、的干扰影响的干扰影响)二者之和的比较来得到。二者之和的比较来得到。本讲稿第三十七页，共九十五页 3)计算计算分析分析 设设Dc为为Cache不命中时，由主存调一块进不命中时，由主存调一块进Cache的的开销，则：开销，则：a)按需取进法的不命中开销为：按需取进法的不命中开销为：Dc 不命中率不命中率(按需取进法按需取进法)b)预取法不命中的开销为：预取法不命中的开销为：Dc 不命中率不命中率(预取法预取法)而预取法还应有预取开销，为此，我们设：而预取法还应有预取开销，为此，我们设：预取率：预取总块数预取率：预取总块数/访存总块数访存总块数 Pa：预取访主存和访：预取访主存和访Cache的开销的

39、开销本讲稿第三十八页，共九十五页 c)预取法取进预取块的开销为：预取法取进预取块的开销为：Pa 预取率预取率 访问率：访访问率：访Cache的总次数的总次数/程序访程序访Cache的总次数，即的总次数，即(程序访程序访Cache次数预取访次数预取访Cache次数次数)/程序访程序访Cache次数。次数。Ac：由于预取访：由于预取访Cache占用了占用了Cache，延迟、干扰了，延迟、干扰了程序对程序对Cache的访问的预取干扰开销。的访问的预取干扰开销。d)预取法对程序访预取法对程序访Cache的映象为：的映象为：Ac(访问率访问率1)e)结论结论 由上计算可知，只有下式成立，即：由上计算可知

40、，只有下式成立，即：本讲稿第三十九页，共九十五页 Dc 不命中率不命中率(按需取进按需取进)Dc 不命中率不命中率(预取预取)Pa 预取率预取率 Ac(访问率访问率1)时，预取法才是可取的。这里，采用缓冲器技术是时，预取法才是可取的。这里，采用缓冲器技术是减少预取干扰的好办法。减少预取干扰的好办法。Cache和主存都设置预取和主存都设置预取专用缓冲器，使预取访主存与访专用缓冲器，使预取访主存与访Cache都尽可能在都尽可能在主存、主存、Cache空闲时进行。空闲时进行。本讲稿第四十页，共九十五页3.任务切换对失效率的影响任务切换对失效率的影响 1)两种失效率两种失效率 a)冷启动冷启动(Col

41、dstart)失效率：失效率：从从Cache为空为空(指新进程所需的内容都未装入指新进程所需的内容都未装入Cache内内)开始到开始到Cache全部被装满这一期间的失效率。全部被装满这一期间的失效率。b)热启动热启动(Warmstart)失效率：失效率：从从Cache为现行进程装满之后测出的失效率。为现行进程装满之后测出的失效率。本讲稿第四十一页，共九十五页 2)影响失效率的因素影响失效率的因素 a)与任务的切换频度与任务的切换频度(平均时间间隔平均时间间隔Qsw)有关有关 Qsw对失效率的影响和工作负荷有很大关系。比对失效率的影响和工作负荷有很大关系。比如，如果进程切换发生在用户程序因为系统

42、需要运如，如果进程切换发生在用户程序因为系统需要运行管理程序来处理某个行管理程序来处理某个I/O中断或时钟中断请求时，中断或时钟中断请求时，则则Qsw值愈小，表明由管理程序切换回原先的用户程值愈小，表明由管理程序切换回原先的用户程序愈快，序愈快，Cache中保留的原先程序的指令和数据就中保留的原先程序的指令和数据就愈多，即失效率愈低。但是如果进程切换是在几个愈多，即失效率愈低。但是如果进程切换是在几个用户程序之间进行，且每个进程都要更换掉用户程序之间进行，且每个进程都要更换掉Cache中的大部分内容时，中的大部分内容时，Qsw值愈小就会使失效率愈高。值愈小就会使失效率愈高。本讲稿第四十二页，共

43、九十五页 b)与与Cache的容量有关的容量有关 Qsw值一定时，若容量过小，存不下该程序的工值一定时，若容量过小，存不下该程序的工作区，那么就会有很高的热启动失效率。因此，增作区，那么就会有很高的热启动失效率。因此，增大大CacheCache的容量可使这个矛盾迅速缓解，而使失效率的容量可使这个矛盾迅速缓解，而使失效率急剧下降；但在容量增大到基本上保护得了足够大急剧下降；但在容量增大到基本上保护得了足够大的工作区之后，容量大小对失效率的下降就趋于平的工作区之后，容量大小对失效率的下降就趋于平缓，也就是说增大容量对降低失效率已影响不大。缓，也就是说增大容量对降低失效率已影响不大。本讲稿第四十三页

44、，共九十五页 3)解决办法解决办法 a)增大增大Cache容量容量 b)修改调度算法，使任务切换回来前，有用的信息仍能修改调度算法，使任务切换回来前，有用的信息仍能保留在保留在Cache中而不被破坏。中而不被破坏。c)设置多个设置多个Cache，例如设置两个，一个专用于管理，例如设置两个，一个专用于管理程序，一个专用于用户程序。这样，在管态和目态程序，一个专用于用户程序。这样，在管态和目态之间切换时，不会破坏各之间切换时，不会破坏各Cache中的内容。中的内容。d)对于某些操作，例如长的向量运算、长的字符行运算对于某些操作，例如长的向量运算、长的字符行运算等，可以不经过等，可以不经过Cache

45、直接进行，以避免这些操作由于直接进行，以避免这些操作由于使用使用Cache而从而从Cache中替换出大量更有希望将重新使用中替换出大量更有希望将重新使用的数据。的数据。本讲稿第四十四页，共九十五页4.影响影响Cache存贮器性能的因素存贮器性能的因素 1)不命中率与不命中率与Cache的容量、组的大小和块的大小的一般的容量、组的大小和块的大小的一般关系关系不命中率不命中率1HcCache容量容量组的大小一定组的大小一定块的大小减小块的大小减小(a)不命中率不命中率1HcCache容量容量块的大小一定块的大小一定组的大小减小组的大小减小(b)图图4.47 块的大小、组的大小与块的大小、组的大小与

46、Cache容量对容量对Cache命中率的影响命中率的影响本讲稿第四十五页，共九十五页 2)Cache主存存贮层次的等效速度与命中率的关主存存贮层次的等效速度与命中率的关系系 设：设：tc为为Cache的访问时间；的访问时间；tm为主存周期；为主存周期；Hc为访为访Cache的命中率；的命中率；则则Cache存贮器的等效存贮周期为：存贮器的等效存贮周期为：taHc tc(1 Hc)tm 与主存与主存辅存存贮层次不同的是一旦辅存存贮层次不同的是一旦Cache不命不命中，由于主存与中，由于主存与CPU之间有直接通路，之间有直接通路，CPU对第二对第二级的访问时间就是级的访问时间就是tm，而不是调块时

47、间再加一个访，而不是调块时间再加一个访Cache的时间了。这样，采用的时间了。这样，采用Cache比之于处理机直比之于处理机直本讲稿第四十六页，共九十五页接访问主存，其速度提高的倍数为：接访问主存，其速度提高的倍数为：tm/ta tm/(Hc tc(1 Hc)tm)1/(1(1tc/tm)Hc)因为因为Hc总是小于总是小于1，可以令，可以令Hc/(+1)，代入，代入上式得：上式得：(+1)显然，不管显然，不管Cache本身的速度有多高，只要本身的速度有多高，只要Cache的命中率有限，那么采用的命中率有限，那么采用Cache主存存贮层次主存存贮层次后，速度能提高的最大值是有限的，不会超过后，速

48、度能提高的最大值是有限的，不会超过+1倍。倍。tm tm+tc本讲稿第四十七页，共九十五页 3)Cache的容量对机器速度的影响的容量对机器速度的影响 对流水机器，机器速度与主存速度、对流水机器，机器速度与主存速度、CPU拍宽、拍宽、Cache容量的可能关系如图容量的可能关系如图4.49所示，机器的单位是所示，机器的单位是MIPS(每秒执行百万条指令每秒执行百万条指令)，主存采用多体交叉存，主存采用多体交叉存取。取。a)由图可见，主存速度和由图可见，主存速度和CPU周期一定时，由不周期一定时，由不用用Cache到到Cache容量从容量从4KB增大到增大到64KB，机器速，机器速度有了显著提高，

49、尤其是在主存速度较低时。度有了显著提高，尤其是在主存速度较低时。b)还可以看出，还可以看出，Cache容量的增大，可以显著降容量的增大，可以显著降低对主存速度的要求。低对主存速度的要求。本讲稿第四十八页，共九十五页 4)总结总结 总之，总之，Cache本身的速度与容量都会影响本身的速度与容量都会影响Cache存存贮器的等效访问速度。如果对贮器的等效访问速度。如果对Cache存贮器的等效存贮器的等效访问速度不满意，需要改进的话就要作具体分析，访问速度不满意，需要改进的话就要作具体分析，看看现在看看现在Cache的等效访问速度是否已接近于第一的等效访问速度是否已接近于第一级级Cache本身的访问速

50、度。如果尚差的较远，说明本身的访问速度。如果尚差的较远，说明Cache的命中率低，这个时时就不是去采用更高速的命中率低，这个时时就不是去采用更高速度的度的Cache片子来替换现有的片子来替换现有的Cache片子，而应当从片子，而应当从提高提高Cache的命中率入手，包括调整组的大小、替的命中率入手，包括调整组的大小、替换算法以及增大换算法以及增大Cache容量等方面着手，否则该速容量等方面着手，否则该速度是无法提高的。相反的，如果实际的等效访问速度是无法提高的。相反的，如果实际的等效访问速本讲稿第四十九页，共九十五页度已经非常接近于度已经非常接近于Cache本身的访问速度还不能满本身的访问速度