第4章储存体系2

2.直接映象及其变换

1)规则：主存中每一块只能映像到Cache中唯一一个特定位置。

如图所示，主存的第i块只能映像到第imod2ncb块位置上。如图4.35所示：……Cache块位置012ncb-1主存块012nmb-1…2ncb-1块2ncb+02ncb+1…2·2ncb-1块2·2ncb+0…3·2ncb-1……0区1区2区2nmb－ncb-1区图4.35直接映象规则

2)变换过程主存块号块内地址主存地址

nmnmbnmrncbncrCache地址nc…2ncb项

相联比较不等块失效区号…012ncb-1••相等访Cache

区号(按地址访问存贮器)由2ncb中选1图4.36直接映象的地址变换过程快速度的直接相联地址变换

3)优缺点优点：a)所需硬件简单，只需要容量较小的按地址访问的区号标志表存贮器和少量外比较电路，因此成本低。b)访问Cache与访问区号表、比较区号是否相符的操作是同时进行的。当Cache命中时就意味着省去了地址变换所花费的时间。

缺点：直接映象法最致命的缺点就是Cache的块冲突率很高。只要有两个或两个以上经常使用的块恰好被映象到Cache的同一个块位置时，就会使得Cache的命中率急剧下降。而且，即使此时Cache中有大量的空闲块存在，仍然会发生块失效和块冲突，无法使用Cache中的空闲块，所以，Cache的利用率很低。正是因为这个原因才使得目前采用直接映象的Cache存贮器很少了。3.组相联映象及其变换组相联方式是目前在Cache中用得比较多的一种地址映象和变换方式。它是介于全相联和直接相联之间的一种折中方案。

思想：简要说明如下图4.37所示，将Cache空间和主存空间都分组，每组S块(S＝2s)。Cache一共2ncb个块，分成Q组(Q=2q)，整个Cache是一区。主存分成与Cache一样大小的2nd个区，其地址按区号、组号、组内块号、块内地址分成对应的4个字段。主存地址的组号、组内块号分别用q、s'字段表示，它们的宽度和位置与Cache地址的q、s是一致的。规则：组相联映象指的是各组之间直接映象，但组内各块间则是全相联映象。如图4.37所示。为了实现主存块号到Cache块号的变换，需要一个由高速小容量存储器做成的块表存储器。块表存储器采用按地址访问和按相联访问两种方式工作。在组内采用相联方式访问，在组之间采用按地址方式访问。块表的容量与Cache的块容量相等，字长为主存地址中的区号E、组内块号B与Cache地址中的组内块号b的长度之和。为了提高Cache的访问速度，可以把Cache的地址变换与访问Cache并行进行，并采用流水线方式工作。

组号q组内块号s块内地址ncr组号q组内块号s'块内地址nmr区号nd1位1位2位2位1位ncbnmbncnm块位置0块01122334455667789101112131415012301230123012301230123第0组第0组第1组第1组第0组第1组第0区(Cache容量)第1区(Cache容量)Cache主存

组内全相联组间直接相联

图4.37组相联映象规则

3)讨论当组相联映象的S值大到等于Cache的块数(即s=ncb)时就变成了全相联映象，而当S值小到只有1块(即无s字段)时就变成了直接映象。因此全相联映象和直接映象只是组相联映象的两个极端。在Cache空间大小及块的大小都已经确定的情况下，Cache的总块数就定了，但结构设计者仍可以对S和Q值进行选择。Q和S的选取主要依据对块冲突概率、块失效率、映象表复杂性和成本、查表速度等的折衷权衡。组内块数S愈多，块冲突概率和块失效率愈低，映象表愈复杂、成本愈高，查表速度愈慢。所以通常采用在典型工作负荷下进行模拟而定。4)地址变换组号q组内块号s'块内地址nmr区号nd组号q组内块号s块内地址ncrnmnc直接直接相联比较不等块失效相等•相联比较nds's•nd＋s'表的总容量为2ncb＝2q·2s行2q组中选12s行组相联映象方式与直接映象方式相比，最明显的优点是块的冲突概率大大降低。组相联映象方式与全相联映象方式相比，实现起来要容易得多，但Cache的命中率与全相联映象方式很接近。因此，组相联映象方式在许多机器中得到广泛的应用。在Cache的容量和每块的大小确定之后，可以通过选择每组的块容量和Cache的组容量，即分配Cache地址中组号q和组内块号s两个字段的长度，来优化Cache的性能。主要包括块冲突概率，块的失效率，查表的速度，实现的复杂性和成本等。一般来说，每组的块容量s越大，块的冲突概率和Cache的失效率就越低，但由于映象关系复杂，查表的速度就越慢，实现的成本也越越高。

表3.5采用组相联映象方式的典型机器的Cache分组情况机器型号Cache的块容量Cb每组的块容量GbCache组容量CgDECVAX-11/78010242512Amdahl470/V65122256Inteli860D-Cache2562128Honeywell66/605124128Amdahl470/V720484512IBM370/16810248128IBM303310241664Motolola88110I-Cache2562128当每个组的块容量增大时，需要进行相联访问的存储器的容量将增加，造成查表的速度降低，实现成本增加。但是，当每个组的块数太少时，块的冲突概率和Cache的失效率就会增大。例如，当每组的块容量为2时，主存的各个分区中相对块号相同那些块只能映象到Cache的两个特定块中，当这些块中有两个以上是当前的常用块时，就会出现所谓的颠簸现象。4.段相联映象在全相联、直接相联、组相联映象的基础上还可以有各种变形，段相联就是一例。段相联实质上是组相联的特例。他是采用组间全相联、组内直接映象。为了与组相联加以区别，将这种映象方式称为段相联。就是说，段相联映象是把主存和Cache分成具有相同的Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象。如图4.42所示：块0块1块2Z－1Cache主存…块0块1块2Z－1…≈≈块0块1块2Z－1…块0块1块2Z－1…≈≈块0块1块2Z－1…段0段0(Z个段)段1段2nmb/Z－1段2ncb/Z－1图4.42具有每段Z个块的断相联映象段间全相联段内直接4.3.3替换算法的实现

当访存发生Cache块失效，需要把主存块按所采用的映象规则装入Cache时，如果又出现Cache块冲突，就必须按某种策略选择将Cache中的哪一块替换出去。直接映象及变换方式实际上不需要替换算法，这是因为主存中的一块只能装入到Cache的唯一一个块中。如果Cache的这一块是空的，则可以装入，如果Cache的这一块已经被占用，唯一的办法就是把它替换出去。

在全相联映象及变换方式中，由于主存中的一块可以装入的Cache中任意一块的位置上，因此，它的替换是否也就最复杂。

在组相联及位选择组相联映象及地址变换方式中，需要从Cache同一组内的几个块中选择一块替换出去。Cache——主存存贮层次的替换算法与虚拟存贮器的类似，不外乎也是FIFO法或LRU法，其中LRU法最为常用。由于虚拟存储器中的页面替换算法主要是用软件实现的，而且虚拟存储器都采用全相联映象方式。而在Cache中，由于Cache的访问速度很高，替换算法必须全部用硬件实现，而且Cache中一般不采用全相联映象方式。因此，Cache中的块替换算法与虚拟存储器中的页面替换算法虽然有一些相同的地方，但不相同的地方是主要。

随机法Cache替换算法中最简单的是随机法。

在PDP-11/70的Cache采用组相联映象方式，每组只有两块。当发生块冲突时，使用一个2态的随机数发生器，从组内的两块中任意选择一块替换出去。

随机法的优点是实现起来非常容易，因此，在有些小型微型计算机中被采用。它的缺点是既没有利用程序的局部性特点，也没有利用历史上的块地址流分布情况，因此，它的效果往往不好。

轮换法及其实现轮换法通常用于组相联映象及地址变换方式中，常见的有两种实现方法。

1、每块一个计数器

2、每组一个计数器

每块一个计数器

在上面介绍组相联及位选择组相联地址变换方式中，块表内用来表示每一块映象关系的一个存储字由三字段组成，包括主存地址的区号E和块号B（在位选择组相联映象方式中只有主存地址的区号E，没有块号B）、Cache的块号b及一个有效位e。为了实现轮换法，还要再增加设置一个替换计数器字段。计数器字段的长度与Cache地址中的组内块号字段的长度相同。替换方法及计数器的管理规则是：被装入或被替换的块，它所属的计数器清为“0”，同组的其它块所属的计数器都加“1”。需要替换时，在同组中选择计数器的值最大的块作为被替换的块。

Solar-16/65机的Cache采用位选择组相联映象方式。Cache每组的块容量为4，因此，每块用一个2位的计数器。刚开始时，同组的4个计数器均为00。序列初始值装入块00装入块01装入块10装入块11替换块00块00000001101100块01000100011011块10000110000110块11000110110001一种轮换法的装入及替换过程2、每组一个计数器

分析上面的方法，实际上同组内的所有块是按顺序轮流替换的。为此，只要为每个组设置一个计数器即可。

替换规则和计数器的管理方法很简单。本组有替换时，计数器加"1"，计数器的值就是要被替换出去的块号。

轮换法的优点是实现比较简单。与随机法相比，它能够利用历史上的块地址流情况，把最先装入的块作为被替换的块。但是，与随机法相同，它也没有能够利用程序的局部性特点。因为最先装入cache的块，很可能也是经常要使用的块。因此，它的效果虽然比随机法好，但仍然不理想。

堆栈法1)思想我们在4.2.2中讲过，LRU法是堆栈型替换算法，也讲了对于LRU算法，堆栈St中由栈顶到栈底的各项（行）恒反映出到t时刻，实存中各页被访问过的近远次序，以及每访问一页，堆栈St中各项的变换过程。结果是此堆栈的栈顶恒存放近期最近访问过的页的页号，而栈底恒存放近期最久没有方问过的页的页号，即准备被替换掉的页的页号。那么，我们在Cache——主存存贮层次中就可以按此思想实际组成一个硬件堆栈。

2)过程（块号）（块号）（块号）（块号）（块号）2ncb个寄存器需重新排列的块号都下推一行被访问的块号（经相联比较找到）•寄存器堆栈压入ncb位近期最近访问过的块近期最久没有访问过的块图4.43全相联映象LRU法经堆栈实现（需要有相联比较功能）3)缺点：这种硬件堆栈既要求具有相联比较的功能，又要求能全下移、部分下移和从中间取出一项的功能，成本较高，因此只适用于组相联且组内块数较少的LRU替换场合。4)变形为了避免堆栈中各行存放的内容经常同时进行下移，以便节省成本，我们采用另一种变形，即将存放块号的寄存器的几何位置与Cache中的块号对应，而用寄存器存放值的大小来表示已被访问过的远近次序。以组相联为例，每一组均使用如图4.44那样的一个寄存器组，由2s个寄存器组成，每个寄存器为s位宽，可以存放表示从0到2s－1的次序值。如果让越是最近访问的，其次序值愈小，则只需通过相联比较求最大值（不是相联比较相符），找到该最大值所在的寄存器号，这就是对应Cache中应该被替换掉的块的块号。第0块的访问次序第1块的访问次序第2块的访问次序第2s-1块的访问次序块0块1块2块2s-12s个寄存器

S位（其中一组）Cache存贮器（其中一组）组相联LRU法经寄存器实现（每组一个，需要有相联比较功能）2.比较对法

1)思路比较法的基本思路是让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到LRU块。比如说有ABC三块，互相之间可以组合成AB、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，则这三个触发器状态分别为TAB＝1，TAC＝1，TBC＝1。如果访问过的次序为B-A-C，C为最久未被访问过的块，则此时必有TAB＝0，TAC＝1，TBC＝1。因此最久未被访问过的块C作为被替换掉的块的话，用布尔代数式必有：

CLRU＝TAB•TAC•TBC+TAB•TAC•TBC＝TAC•TBC同理可得：BLRU＝TAB•TBC；ALRU＝TAB•TAC因此，完全可以用门、触发器等硬件组合实现，如图4.45所示：&&&010101TABTACTBC

ALRU

BLRU

CLRU•••访问B访问C访问A图4.15用比较对法实现LRU算法

2)分析我们来看比较对法所用的硬件量。由于每块均可能作为LRU块，其信号需要用一个与门产生，例如ALRU与门要有从TAB、TAC来的输入，BLRU门要有从TAB、TBC来的输入，而与每块有关的对数个数为块数减去1，所以与门的扇入数是块数减去1。若p为块数，两两组合，比较对触发器的个数应为Cp2，即为p(p-1)/2。表4.2给出了比较对法块数p的取值与门数、门的输入端数及比较对触发器数的关系。每组块容量与所需触发器、与门及与门输入端个数的关系每组块容量34681664256触发器个数361528120201632640与门个数34681664256与门输入端个数235715632553)总结替换算法实现的设计要围绕下面两点来考虑：a)如何对每次访问进行记录（使用位法、堆栈法和比较对法所用的记录方法都不同）；b)如何根据所记录的信息来判定近期内哪一块最久没有被访问过。由此可见，实现方法和所用的映象方法密切相关。例如，对于主存——辅存存贮层次的全相联映象宜于采用使用位法或类似的方法，而不宜采用堆栈法和比较对法；但对于Cache——主存存贮层次的组相联映象，因为组内块数较少，就宜于采用比较对法或堆栈法。替换算法的设计和实现也和器件的发展密切相关，随着器件技术的发展，尤其是高速相联存贮器片子的改进，已经而且必然会不断研制出新的更好的实现方法。4.3.4Cache的透明性及性能分析1.Cache的透明性分析

1)两种问题的出现虽然Cache是主存的一部分副本，主存中某单元的内容却可能在一段时间里会与Cache中对应单元的内容不一致。例如，CPU往Cache写入，修改了Cache中某单元的内容，而在主存中对应于此单元的内容却可能仍是原来的，没有改变。这时，如果CPU或I/O处理机及其他处理机要经主存交换信息，那么主存内容跟不上Cache对应内容变化的这种不一致就会造成错误。同样，I/O处理机或其他处理机已把新的内容送入主存某个区域，而Cache中对应于此区域的副本内容却仍可能是原来的。这时，如果CPU要从Cache中读取信息，也会因为这种Cache内容跟不上主存对应内容变化的不一致而造成错误。因此，必须采取措施解决好由于读写过程中产生的Cache和主存对应内容不一致的问题。2)写回法

写回法是在CPU执行写操作时，只是把信息写入Cache，仅当需要被替换时，才将已经被写入过的Cache块先送回主存，然后再调入新块。这种方法也称为抵触修改法，类似于虚拟存贮器中进行页面替换时的情况。因此，Cache——主存存贮层次的地址映象表中需对Cache中的每个块设置一个“修改位”，作为该块装入Cache后是否被修改过的标志。这样在块替换时，根据该块的修改位是否位1，就可以决定替换时是否先将该块存回主存原来的位置。3)写直达法写直达法也称为存直达法，它利用Cache——主存存贮层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。这样，在块替换时，就不必先写回主存，而可以立即调入新页。显然，写回法是把开销花在每次需要替换的时候，而写直达法则把开销花在每次写入Cache时都附加一个比写Cache长的多的写主存时间。

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

写回法和写直达法都需要有少量缓冲器。写回法中缓冲器用于暂存将要写回的块，使之不必等待被替换块写回主存后才开始进行Cache取。写直达法中缓冲器则用于缓冲由写Cache所要求的写回主存的内容，使CPU不必等待这些写主存完成就能往下运行。缓冲器由要存的数据和要存入的目标地址组成。在写直达系统中容量为4的缓冲器就可以显著改进其性能，IBM3033就是这样用的。要注意的这些缓冲器对Cache和主存是透明的。在设计时，要处理好可能由它们所引起的错误(如另一个处理机要访问的主存单元的内容正好仍在缓冲器中)。

5)两种方法对比写回法有利于省去许多将中间结果写入主存的无谓开销。但是增加了Cache的复杂性。可靠性上写回法不如写直达法好。具体采用哪种方法还与系统使用场合有关。如果让多CPU共享主存交换信息改成共享Cache交换信息，信息的一致性就能得到保证。对于共享主存的多CPU系统，绝大多数还是采用各个CPU都有自己的Cache的方式与共享主存连接。这样的系统由于Cache的透明性，仅靠写直达法并不能保证同一主存单元在各个Cache中的对应内容都一致。如下图：要采取措施保证让有此单元的各个Cache的内容都一致才行。CPUACacheaCPUBCacheb主存•••••每个处理机都有Cache的共享多处理机系统解决办法：•采用播写法：即任何处理机要写入Cache时，不仅要写入自己Cache的目标块和主存中，还把信息或者播写到所有Cache有此单元的地方，或者让所有Cache有此单元的块作废以便下次访问时按缺块处理，从主存中重新调入。•控制某些共享信息（如信号灯或作业队等）不等进入Cache。•目录表法：即在CPU读/写Cache不命中时，先查主存中的目录表以判定目录块是否在别的Cache内，以及是否正在被修改等，然后再决定如何读写此块。

6)第二种问题

Cache内容跟不上已变化了的主存内容的问题，有两种解决办法：当I/O处理机未经Cache往主存写入新内容的同时，由OS经某个专用指令清除整个Cache。这种办法的缺点是象我们在讲述用专用指令清除快表一样，会使Cache对OS和系统程序员成为不透明的，因此并不好。当I/O处理机往主存某个区域写入新内容时，由专用硬件自动地将Cache内对应此区域地副本作废，而不必由OS进行任何干预，从而保持Cache的透明性。2.Cache的取算法

1)预取法

为了便于硬件实现，通常只预取直接顺序的下一块，即在访问到主存的第i块(不论是否已取进Cache)时，只有第i＋1块才是可能的预取块。至于何时将该块取进，可以有恒预取和不命中时预取两种不同的方法。恒预取指的是只要访问到主存的第i块的某个字，不论Cache是否命中，恒发预取指令。不命中时预取仅当访问第i块不命中时，才发预取指令。2)影响命中率的其它因素a)块的大小：

若每块的字节数过少，预取的效果不明显。从预取的需要出发，希望块尽可能大。但若每块的字节数过多，一方面可能会预取进不需要的信息，另一方面由于Cache容量有限，又可能把正在使用或近期使用到的信息给替换出去，反而降低了命中率。从模拟结果来看，每块的字节数如果超过了256，就会出现这种情况。b)预取开销：要预取就要有访主存开销和将它取进Cache的访Cache开销，还要加上把被替换的块写回主存的开销，这些开销会增加主存和Cache的负担，干扰和延缓程序的执行。由上可知，采用预取法的效果不能只从命中率的提高来衡量，还需要从所花费的开销多少来考虑。而这种开销的多少可以通过对按需取进法的不命中开销与预取法的不命中开销和预取开销(包括访存开销及对Cache的干扰影响)二者之和的比较来得到。

3)计算分析设Dc为Cache不命中时，由主存调一块进Cache的开销，则：

a)按需取进法的不命中开销为：Dc×不命中率(按需取进法)b)预取法不命中的开销为：Dc×不命中率(预取法)而预取法还应有预取开销，为此，我们设：•预取率：预取总块数/访存总块数•Pa：预取访主存和访Cache的开销

c)预取法取进预取块的开销为：Pa×预取率•访问率：访Cache的总次数/程序访Cache的总次数，即(程序访Cache次数＋预取访Cache次数)/程序访Cache次数。•Ac：由于预取访Cache占用了Cache，延迟、干扰了程序对Cache的访问的预取干扰开销。d)预取法对程序访Cache的映象为：Ac×(访问率－1)e)结论由上计算可知，只有下式成立，即：

Dc×不命中率(按需取进)

>Dc×不命中率(预取)＋Pa×预取率＋Ac×(访问率－1)时，预取法才是可取的。这里，采用缓冲器技术是减少预取干扰的好办法。Cache和主存都设置预取专用缓冲器，使预取访主存与访Cache都尽可能在主存、Cache空闲时进行。3.任务切换对失效率的影响

1)两种失效率a)冷启动(Cold－start)失效率：从Cache为空(指新进程所需的内容都未装入Cache内)开始到Cache全部被装满这一期间的失效率。b)热启动(Warm－start)失效率：从Cache为现行进程装满之后测出的失效率。

2)影响失效率的因素a)与任务的切换频度(平均时间间隔Qsw)有关Qsw对失效率的影响和工作负荷有很大关系。比如，如果进程切换发生在用户程序因为系统需要运行管理程序来处理某个I/O中断或时钟中断请求时，则Qsw值愈小，表明由管理程序切换回原先的用户程序愈快，Cache中保留的原先程序的指令和数据就愈多，即失效率愈低。但是如果进程切换是在几个用户程序之间进行，且每个进程都要更换掉Cache中的大部分内容时，Qsw值愈小就会使失效率愈高。

b)与Cache的容量有关

Qsw值一定时，若容量过小，存不下该程序的工作区，那么就会有很高的热启动失效率。因此，增大Cache的容量可使这个矛盾迅速缓解，而使失效率急剧下降；但在容量增大到基本上保护得了足够大的工作区之后，容量大小对失效率的下降就趋于平缓，也就是说增大容量对降低失效率已影响不大。3)解决办法a)增大Cache容量b)修改调度算法，使任务切换回来前，有用的信息仍能保留在Cache中而不被破坏。c)设置多个Cache，例如设置两个，一个专用于管理程序，一个专用于用户程序。这样，在管态和目态之间切换时，不会破坏各Cache中的内容。d)对于某些操作，例如长的向量运算、长的字符行运算等，可以不经过Cache直接进行，以避免这些操作由于使用Cache而从Cache中替换出大量更有希望将重新使用的数据。4.影响Cache存贮器性能的因素

1)不命中率与Cache的容量、组的大小和块的大小的一般关系不命中率1－HcCache容量组的大小一定块的大小减小(a)不命中率1－HcCache容量块的大小一定组的大小减小(b)块的大小、组的大小与Cache容量对Cache命中率的影响2)Cache——主存存贮层次的等效速度与命中率的关系设：tc为Cache的访问时间；tm为主存周期；Hc为访Cache的命中率；则Cache存贮器的等效存贮周期为：ta＝Hctc＋(1－Hc)tm

与主存—辅存存贮层次不同的是一旦Cache不命中，由于主存与CPU之间有直接通路，CPU对第二级的访问时间就是tm，而不是调块时间再加一个访Cache的时间了。这样，采用Cache比之于处理机直接访问主存，其速度提高的倍数为：

ρ＝tm/ta＝tm/(Hctc＋(1－Hc)tm)＝1/(1－(1－tc/tm)Hc)因为Hc总是小于1，可以令Hc＝α/(α+1)，代入上式得：

ρ＝(α+1)从这个关系式看到，Cache系统的加速比ρ是命中率H和主存周期Tm与Cache周期TC比值的函数。在Cache系统中，主存储器的访问周期Tm和Cache的访问周期TC由于受所用器件的限制通常是一定。因此，要提高Cache系统的加速比ρ最好的途径是提高命中率H。

而且，不管Cache本身的速度有多高，只要Cache的命中率有限，那么采用Cache——主存存贮层次后，速度能提高的最大值是有限的，不会超过α+1倍。tm

tm+αtc

3)Cache的容量对机器速度的影响

对流水机器，机器速度与主存速度、CPU拍宽、Cache容量的可能关系如图4.49所示，机器的单位是MIPS(每秒执行百万条指令)，主存采用多体交叉存取。由图可见，主存速度和CPU周期一定时，由不用Cache到Cache容量从4KB增大到64KB，机器速度有了显著提高，尤其是在主存速度较低时。还可以看出，Cache容量的增大，可以显著降低对主存速度的要求。

4)总结

总之，Cache本身的速度与容量都会影响Cache存贮器的等效访问速度。如果对Cache存贮器的等效访问速度不满意，需要改进的话就要作具体分析：Cache的等效访问速度与第一级Cache本身的访问速度尚差的较远-----Cache的命中率低-----提高Cache的命中率入手（调整组的大小、替换算法以及增大Cache容量）如果实际的等效访问速度已经非常接近于Cache本身的访问速度------只有更换更高速的Cache片子。否则，任何其它途径也是不会有什么效果的。4.3.5“Cache—主存—辅存”存贮层次三级存贮层次的地址变换：

CPU提供访存的虚地址可能需要变换成Cache地址、主存地址或辅存地址。对应于虚地址的单元已在Cache中

这时就需要把虚地址直接变换成Cache地址来访问Cache，而不是先把虚地址变换成主存实地址，再由主存实地址变换成Cache地址，这样可以缩短地址变换的时间。

2)对应单元已在主存但尚未调入Cache

这时则需要把虚地址经快表和慢表变换成主存实地址去访主存，对读访问以及采用按写访问还必须进行虚地址到Cache地址的映象或变换，以便把包含对应此单元所在的一块调入或替换进Cache。3)对应单元还不在主存

这时就需要把虚地址变换成辅存实地址去辅存调页，同时还要将虚地址映象变换成主存实地址将页调入主存，以及把虚地址映象变换成Cache地址，将其中的一块装入Cache。

2.访问Cache过程在这三级存贮层次中通常总是让页的大小恰好时块的2的幂倍，每一块的大小又是字的2的幂倍。而且每次用虚页号查快表和慢表以取得主存实地址和用虚地址对应Cache块号位置的虚块号经组相联去访Cache(Cache中每个单元存放有主存实地址和对应的数据)同时进行。若能在快表中找到，就用由快表来的主存实地址与由Cache中读出的主存实地址相比较。当两者相符，存在Cache中该单元的数据就是要访问的虚、实地址的内容。写Cache的过程与此类似。根据目前的硬件实现技术，除了上面介绍的采用Cache、主存和辅存（磁盘存储器中的一部分）三个存储器构成两个两级存储系统和一个三级存储系统的方法之外，还有一种新的实现方法。就是不用主存储器，只用Cache和辅存两个存储器构成“Cache—辅存”存储系统。这种存储系统简称为全Cache（all-Cache）存储系统。

全Cache存储系统的等效访问周期与Cache很接近，等效存储容量就是虚拟地址空间的容量。

目前，全Cache存储系统还处于实验阶段，并没有商用化。4.4

主存保护大多数计算机系统设计成让其资源能被并行的多个用户所共享，就主存来说，就同时存有多个用户的程序和系统软件。为使系统能正常工作，应防止由于一个用户程序出错而破坏主存中其它用户的程序或系统软件，还要防止一个用户程序不合法地访问不是分配给它的主存区域，哪怕这种访问不会引起系统破坏。因此，系统结构需要为主存的使用提供存贮保护，它是多道程序和多处理机系统所必不可少的。1.存贮区域的保护

1)主存系统的保护

对于不是虚拟存贮器的主存系统可采用第二章讲过的界限寄存器方式，由系统软件经特权指令置定上、下界寄存器，从而划定每个用户程序的区域，禁止它越界访问。由于用户程序不能改变上、下界的值，因此不论它如何出错，也只能破坏该用户自身的程序，侵犯不到别的用户程序及系统软件。

2)虚拟存贮系统由于界限寄存器方式只适用于每个用户程序占用主存一个或几个(当有多对上、下界寄存器时)连续的区域；而对于虚拟存贮系统，由于一个用户的各页能离散地分布于主存内，从而无法使用这种保护方式。对虚拟存贮系统的主存区域保护就需要采用页表保护和键式保护等方式。a)页表保护每个程序都有自己的页表，其行数等于该程序的虚页数。例如它有4页，则只能有0、1、2、3这4个虚页号。设由OS建立的程序也表，这4个虚页号分别对应于实页号4、8、10、14，则不论虚地址如何出错，总只能影响主存中分配给该程序的第4、8、10、14号实页。假设虚页号错成5，肯定不可能在该程序的页表中找到，也就访问不了主存，当然就不会映象主存中其它程序的区域。这正是虚拟存贮系统本身固有的保护机能，也是它的一大优点。为了便于实现这种保护，还可以在段表中的每行内，不仅设置页表起点，还设置段长(页数)项。若出现该段内的虚页号大于段长，则可以发越界中断。这种页表保护是在没有形成主存实地址前进行的保护，使之无法形成能侵犯别的程序区域的主存地址。然而，若地址形成环节由于软、硬件方面的故障而形成了不属于本程序区域的错误主存地址时，则上述这种保护就无能为力了。因此，还应采取进一步的保护措施，键方式就是其中成功的一种。

b)键方式是由OS按当时主存的使用分配状况给主存的每页配一个键，称为存贮键，它相当于一把“锁”。所有页的存贮键存在于相应的快速寄存器内，每个用户(任务)的各实页的页存贮键都相同。为了打开这把锁，需要有把“钥匙”，称为访问键。每个用户的访问键由OS给定，存在处理机的程序状态字(PSW)或控制寄存器中。程序每次访存前，要核对主存地址所在页的存贮键是否与该道程序的访问键相符，只有相符才准访问。这样，就是错误地形成了侵犯别的程序的主存地址，也因为这种键保护而仍然不允许访问。c)环状保护环状保护把系统程序和用户程序按其重要性及对整个系统能否正常工作的影响程度分层，如图4.50所示。设0、1、2三层是系统程序的，之外的各层是同一用户程序的分层。环号大小表示保护的级别，环号愈大，等级愈低。在现行程序运行前，先由OS定好程序各页的环号，并置入也表。而后把该道程序的开始环号送入处理机内的现行环号寄存器，并且把OS规定给该程序的上限环号(规定该程序所能进入的最内层环号)也置入相应的寄存器。若是Pi在某一时候属于i层各页的集合，则当进程执行P∈Pi页内的程序时，允许访问F∈Pj页，这里对应的是j≥i。但是如果是j<i时，则需由OS环控制例行程序判定这个内向访问是否允许和是否正确之后才能访问，否则就是出错，进入保护处理。但j值肯定不能小于给定的上限环号。只要j≠i，就进入中断，若允许访问，则需经特权指令把现行环号寄存器的值由i改为j。这种环式保护既能保证由于用户程序的出错不至于侵犯系统程序，也能保证由于同一用户程序内的低级(环号大)的部分的出错而不致破坏其高级(环号小)的部分。这种环式保护对系统程序的研究和调试运行特别有利，因为可以做到能修改系统程序的某些部分而不必担心会影响到系统程序已设计好并调好的核心部分。至于如何控制j≠i的跨层访问，有的机器规定只能由规定的转移指令执行，且对和j>i和j<i分别只能用不同的转移指令。2.访问方式的保护

上述种种区域保护，如判越界、判建相符、判环号相符、判不超出段长等等，都是经硬件实现的，因此速度可以是很快的。这些区域保护是对允许访问的区域可以进行任何形式的访问，而对允许区域之外，则任何形式的访问都不允许。但在实际中，只是这种限制往往适应不了各种应用的要求，因此还得加上访问方式的保护(限制)。对主存信息的使用可以有读R、写W和执行E三种方式。相应的就有R、W、E访问方式保护，这3者的逻辑组合可以反映出各种应用要求，如：

R∪W∪E——不允许进行任何访问；R∪W∪E——可以进行任何访问；R∩W∪E——只能进行读访问；R∪W∩E——只能按数据进行读写；R∪W∩E——只能执行，不能作为数据使用；R∪E∩W——只能进行写访问；R∪E∩W——不准写访问。对前面讲过的各种区域保护，都可以加上相应的访问方式位以实现这种访问限制。至于环式保护和也表保护，可以把R、W、E等访问方式位设在各个程序的段、页表的各行内，使得同一环内或同一段内的各页可以有上述种种不同的访问保护，以增强灵活性。在某些应用中，我么既要求能实现多个用户可读、写访问共享的数据，但又要保证只当一个用户访问完该数据后，别的用户才可以访问，以防止在一个用户还未把某个共享文件写好之前，别的用户却能把它读了去。可以采用“测试与置定”和“比较与交换”指令实现这点。所以这也是一种保护方法。第4章小节4.1存贮体系的形成与性能

1.存贮器的性能要求

1)大容量

2)低价格3)高速度访问时间TA

存贮周期TM存贮器频宽

4)结论

由于存贮器的价格、速度和容量的要求是相互矛盾的，为了同时满足三方面的要求，在一个完整的存贮体系中，必须采用不同工艺的存贮器，使得信息以各种方式分布于不同的存贮体。2.并行主存系统频宽的分析1)类型单体单字单体多字多体单字交叉多体多字交叉

2)分析结论由于程序的转移概率不会很低，数据分布的离散性较大，所以单纯靠增大m来提高并行主存系统的频宽是有限的，而且性价比还会随m的增大而下降。如果采用并行主存系统仍不能满足速度上的要求，就必须从系统结构上改进，采用存贮体系。3.存贮体系的形成与分支

1)容量需求主存——辅存存贮层次程序局部性

2)速度需求Cache——主存存贮层次程序局部性3)多级存贮层次4.存贮体系的性能参数1)存贮体系的每位平均价格c

2)命中率H=R1/(R1+R2)3)等效访问时间

TA=HTA1+(1-H)TA24.2虚拟存贮器1.管理方式

1)段式管理

a)思想：根据程序的模块性，把一个复杂的大程序分解成多个逻辑上相对独立的模块。b)段表为了进行段式管理，每道程序都由一个断表(映像表)，以存放该程序各程序段装入主存的状况信息。段名(号)：实际由于段号与行对应，省略掉装入位：表征是(1)否(0)已调入主存地址：调入主存时，在主存的起始(绝对)地址段长：段的大小，限制偏移越界访问方式：只读、可写、只执行，提供访问保护c)段表基址寄存器断表长度:该道程序的断数(断表行数)断表基地址:程序的断表在主存中的起始地址d)虚拟地址基号(程序号):断表在断表基址寄存器的位置段号:段在断表中的位置段内位移:所访问单元在段内的偏移e)实主存管理表占用区域表可用区域表f)可用区域分配算法首先分配算法最佳分配算法2)页式管理思想：把主存空间和程序空间都机械的等分成固定大小的页(页面大小因机器不同而异，一般在512到几kB)然后按页顺序编号。3)段页式管理思想：把内存机械的等分成固定大小的页，把程序按模块分段，每个段分成与主存页面大小相同的页，每道程序通过一个断表和相应于每段的一组页表来进行定位。问题：二次查表，费时间2.页式虚拟存贮器的构成1)地址映像与变换a)地址映像就是将虚存单元按某种规则装入(定位于)实存，即建立多用户虚地址NS与实存地址np的对应关系。b)地址变换指的是程序按这种映像关系装入实存后，在执行时多用户虚地址NS如何变换成对应的实地址np。c)全相联映像让每道程序的任何虚页可以映像装入到主存的任何实页位置2)替换算法a)目的当辅存中的页面调入主存发生页面争用时，只有强制腾出主存中某页后才能接纳从辅存调来的新页面。替换算法就是解决具体从主存中选择哪一页作为被替换的页。b)原则有高的主存命中率算法便于实现辅助软、硬件成本尽量低

c)常用算法随机算法(Random,RAND)先进先出算法(FirstInFirstOut,FIFO)近期最少使用算法(LeastRecentlyUsed,LRU)优化替换算法(OPT)——衡量标准d)堆栈型替换算法保证命中率随主存页数的增加只可能提高，至少不会下降。

e)页面失效频率法(PFF)

根据各道程序运行中的主存页面失效率的高低,由OS来动态调节分配给每道程序的实页数。3)影响命命中率的因素

a)与替换算法有关b)命中率与页地址流有关c)与主存容量(即分配给程序的主存页数)有关4)虚拟存贮器工作的全过程P144图4.25页式虚拟存贮器工作原理3.页式虚拟存贮器实现中的问题1)页面失效处理后援寄存器技术预判技术解决方法替换算法页面大小不能过大2)提高虚拟存贮器等效访问速度的措施快表——慢表散列快表——硬件实现散列函数3)影响主存命中率和CPU效率的某些因素a)与Sp有关

P150图4.30页面大小Sp、容量S1与命中率H的关系曲线图b)命中率与主存容量S1有关P151图4.31命中率H与容量S1的关系图c)与所采用的页面调度策略有关4.3高速缓冲存贮器(Cache)1.基本结构特点：9个方面(与虚拟存贮器对比)2.地址的映像与变换

1)全相联映像和变换

a)规则：主存中的任意一块均可映像装入到Cache内的任意一块的位置。b)地址变换过程c)优缺点块冲突率低；代价大，查表速度难以提高。2)直接映像及其变换

规则：主存中每一块只能映像到Cache中唯一一个特定位置：主存的第i块只能映像到第imod2ncb块位置上。相当于把主存空间按Cache空间分区，每区内各块只能按位置一一对应到Cache相应位置上。3)组相联映象及其变换规则：把主存按Cache大小分区，整个Cache是一区，每个区再分成相等的组，组内分块。组间直接映象，组内各块全相联映象。

4)段相联映象规则：把主存和Cache分成具有相同的Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象，实质上就是组相联映象的特例。3.替换算法的实现1)堆栈法思想：栈顶恒存放近期最久访问过的页的页号，而栈底恒存放近期最久没有访问过的页的页号，即准备被替换掉的页的页号。按此思想组成一个硬件堆栈。2)比较对法思路：让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到LRU块。4.Cache的透明性及性能分析1)Cache的透明性分析a)写回法在CPU执行写操作时，只是把信息写入Cache，仅当需要被替换时，才将已经被写入过的Cache块先送回主存，然后再调入新块。b)写直达法也称为存直达法，它利用Cache——主存存贮层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。

2)Cache的取算法a)预取法b)块的大小c)预取开销3)任务切换对失效率的影响a)与任务的切换频度(平均时间间隔Qsw)有关