《存储体系续》PPT课件.ppt

《《存储体系续》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《存储体系续》PPT课件.ppt（95页珍藏版）》请在三一办公上搜索。

1、2.直接映象及其变换 1)规则：主存中每一块只能映像到Cache中唯一一个特定位置，如图所示，主存的第i块只能映像到第i mod2ncb块位置上。如图4.33所示：,Cache,块位置0,1,2ncb-1,主存,块0,1,2nmb-1,2ncb-1,块2ncb+0,2ncb+1,22ncb-1,块22ncb+0,32ncb-1,0区,1区,2区,2nmbncb-1区,图 4.33 直接映象规则,2)变换过程,主存块号,块内地址,主存地址 nm,nmb,nmr,ncb,ncr,Cache地址 nc,2ncb项,相联比较,不等,块失效,区号,0,1,2ncb-1,相等,访Cache,区号(按地址访

2、问存储器),由2ncb 中 选 1,图 4.34 直接映象的 地址变换过程,3)优缺点 优点：a)所需硬件简单，只需要容量较小的按地址访问 的区号标志表存储器和少量外比较电路，因此 成本低。b)访问Cache与访问区号表、比较区号是否相符 的操作是同时进行的。当Cache命中时就意味着 省去了地址变换所花费的时间。,缺点：直接映象法最致命的缺点就是Cache的块冲突率很高。只要有两个或两个以上经常使用的块恰好被映象到Cache的同一个块位置时，就会使得Cache的命中率急剧下降。而且，即使此时Cache中有大量的空闲块存在，仍然会发生块失效和块冲突，无法使用Cache中的空闲块，所以，Cach

3、e的利用率很低。正是因为这个原因才使得目前采用直接映象的Cache存储器很少了。,3.组相联映象及其变换 1)思想：简要说明如下图4.35所示，将Cache空间和主存空间都分组，每组S块(S2s)。Cache一共2ncb个块，分成Q组(Q=2q)，整个Cache是一区。主存分成与Cache一样大小的2nd个区，其地址按区号、组号、组内块号、块内地址分成对应的4个字段。主存地址的组号、组内块号分别用q、s 字段表示，它们的宽度和位置与Cache地址的q、s是一致的。,2)规则：组相联映象指的是各组之间直接映象，但组内各块间则是全相联映象。如图4.35所示。,组号 q,组内块号 s,块内地址 nc

4、r,组号 q,组内块号 s,块内地址 nmr,区号 nd,1位,1位,2位,2位,1位,ncb,nmb,nc,nm,块位置0,块0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,9,10,11,12,13,14,15,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,第0组,第0组,第1组,第1组,第0组,第1组,第0区(Cache容量),第1区(Cache容量),Cache,主存,组内全相联 组间直接相联图4.35 组相联映象规则,3)讨论 当组相联映象的S值大到等于Cache的块数(即s=ncb)时就变成了全相联映象，而当S值小到

5、只有1块(即无s字段)时就变成了直接映象。因此全相联映象和直接映象只是组相联映象的两个极端。在Cache空间大小及块的大小都已经确定的情况下，Cache的总块数就定了，但结构设计者仍可以对S和Q值进行选择。Q和S的选取主要依据对块冲突概率、块失效率、映象表复杂性和成本、查表速度等的折衷权衡。组内块数S愈多，块冲突概率和块失效率愈低，映象表愈复杂、成本愈高，查表速度愈慢。所以通常采用在典型工作负荷下进行模拟而定。,4)地址变换,组号 q,组内块号 s,块内地址 nmr,区号 nd,组号 q,组内块号 s,块内地址 ncr,nm,nc,直接,直接,相联比较,不等,块失效,相等,相联比较,nd,s,

6、s,nd s,表的总容量为2ncb 2q2s行,2q组中选 1,2s行,4.段相联映象 在全相联、直接相联、组相联映象的基础上还可以有各种变形，段相联就是一例。段相联实质上是组相联的特例。他是采用组间全相联、组内直接映象。为了与组相联加以区别，将这种映象方式称为段相联。就是说，段相联映象是把主存和Cache分成具有相同的Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象。如下图所示：,补充知识：,块0,块1,块2,Z1,Cache,主存,块0,块1,块2,Z1,块0,块1,块2,Z1,块0,块1,块2,Z1,块0,块1,块2,Z1,段0,段0(Z个段),段1,段2nmb/Z1,

7、段2ncb/Z1,具有每段Z个块的段相联映象,段间全相联 段内直接,4.3.3 替换算法的实现 当访存发生Cache块失效，需要把主存块按所采用的映象规则装入Cache时，如果又出现Cache块冲突，就必须按某种策略选择将Cache中的哪一块替换出去。Cache主存存储层次的替换算法与虚拟存储器的没有什么不同，不外乎也是FIFO法或LRU法，其中LRU法最为常用。,1.堆栈法 1)思想 我们在中讲过，LRU法是堆栈型替换算法，也讲了对于LRU算法，堆栈St中由栈顶到栈底的各项（行）恒反映出到t时刻，实存中各页被访问过的近远次序，以及每访问一页，堆栈St中各项的变换过程。结果是此堆栈的栈顶恒存放

8、近期最近访问过的页的页号，而栈底恒存放近期最久没有方问过的页的页号，即准备被替换掉的页的页号。那么，我们在Cache主存存储层次中就可以按此思想实际组成一个硬件堆栈。,2)过程,（块号）,（块号）,（块号）,（块号）,（块号）,2ncb个寄存器,需重新排列的块号 都下推一行,被访问的块号（经相联比较找到）,寄存器堆栈 压入,ncb位,近期最近访 问过的块,近期最久没有 访问过的块,全相联映象LRU法经堆栈实现（需要有相联比较功能）,3)缺点：这种硬件堆栈既要求具有相联比较的功能，又要求能全下移、部分下移和从中间取出一项的功能，成本较高，因此只适用于组相联且组内块数较少的LRU替换场合。4)变形

9、 上述这种堆栈，各块被访问的先后次序由该项在堆栈中距离栈底是近还是远来反映。为了避免堆栈中各行存放的内容经常同时进行下移，以便节省成本，我们采用另一种变形，即将存放块号的寄存器的几何位置与Cache中的块号对应，而用寄存器存,放值的大小来表示已被访问过的远近次序。以组相联为例，每一组均使用如图4.39那样的一个寄存器组，由2s个寄存器组成，每个寄存器为s位宽，可以存放表示从0到2s1的次序值。如果让越是最近访问的，其次序值愈小，则只需通过相联比较求最大值（不是相联比较相符），找到该最大值所在的寄存器号，这就是对应Cache中应该被替换掉的块的块号。,第0块的访问次序,第1块的访问次序,第2块的

10、访问次序,第2s-1块的访问次序,块0,块1,块2,块2s-1,2s个寄存器,S位（其中一组）,Cache存储器（其中一组）,图 4.39 组相联LRU法经寄存器实现（每组一个，需要有相联比较功能）,2.比较对法 1)思路 比较法的基本思路是让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到LRU块。比如说有A BC三块，互相之间可以组合成AB BA AC CA BC CB6对，其中AB和BA、AC和CA、BC和CB是重复的，所以TAB为“1”，表示A比B更近被访问过；TAB为“0”，则表示B比A更近被访问过。TAC、TBC也类似定义。这样，当访问过的

11、次序为A B C，即最近,访问过的为A，最久未被访问过的为C，则这三个触发器状态分别为TAB1，TAC1，TBC1。如果访问过的次序为B A C，C为最久未被访问过的块，则此时必有TAB0，TAC1，TBC1。因此最久未被访问过的块C作为被替换掉的块的话，用布尔代数式必有：CLRUTAB TACTBC+TAB TACTBC TACTBC同理可得：BLRUTABTBC；ALRUTAB TAC因此，完全可以用门、触发器等硬件组合实现，如图4.40所示：,&,&,&,0,1,0,1,0,1,TAB,TAC,TBC,ALRU,BLRU,CLRU,访问B,访问C,访问A,图 4.40 用比较对法实现LR

12、U算法,2)分析 我们来看比较对法所用的硬件量。由于每块均可能作为LRU块，其信号需要用一个与门产生，例如ALRU与门要有从TAB TAC来的输入，BLRU门要有从TAB，TBC来的输入，而与每块有关的对数个数为块数减去1，所以与门的扇入数是块数减去1。若p为块数，量量组合，比较对触发器的个数应为Cp2，即为p(p-1)/2。表4.3给出了比较对法块数p的取值与门数、门的输入端数及比较对触发器数的关系。,3)总结 替换算法实现的设计要围绕下面两点来考虑：a)如何对每次访问进行记录（使用位法、堆栈法和比较对法所用的记录方法都不同）；b)如何根据所记录的信息来判定近期内哪一块最久没有被访问过。由此

13、可见，实现方法和所用的映象方法密切相关。例如，对于主存辅存存储层次的全相联映象宜于采用使用位法或类似的方法，而不宜采用堆栈法和比较对法；但对于Cache主存存储层次的组相联映象，因为组内块数较少，就宜于采用比较,对法或堆栈法。替换算法的设计和实现也和器件的发展密切相关，随着器件技术的发展，尤其是高速相联存储器片子的改进，已经而且必然会不断研制出新的更好的实现方法。,4.3.4 Cache的透明性及性能分析 1.Cache的透明性分析 1)两种问题的出现 虽然Cache是主存的一部分副本，主存中某单元的内容却可能在一段时间里会与Cache中对应单元的内容不一致。例如，CPU往Cache写入，修改

14、了Cache中某单元的内容，而在主存中对应于此单元的内容却可能仍是原来的，没有改变。这时，如果CPU或I/O处理机及其他处理机要经主存交换信息，那么主存内容跟不上Cache对应内容变化的这种不一致就会造成错误。,同样，I/O处理机或其他处理机已把新的内容送入主存某个区域，而Cache中对应于此区域的副本内容却仍可能是原来的。这时，如果CPU要从Cache中读取信息，也会因为这种Cache内容跟不上主存对应内容变化的不一致而造成错误。因此，必须采取措施解决好由于读写过程中产生的Cache和主存对应内容不一致的问题。,2)写回法 写回法是在CPU执行写操作时，只是把信息写入Cache，仅当需要被替

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

16、时候，而写直达法则把开销花在每次写入Cache时都附加一个比写Cache长的多的写主存时间。,4)写不命中处理 当出现写不命中时，无论是写回法还是写直达法都有一个在写时是否取的问题。一种是不按写分配法，即当Cache写不命中时只写入主存，该写地址单元所在块不从主存调进Cache。另一种是按写分配法，即当Cache不命中时除写入主存外，还把该写地址单元所在的块由主存调入Cache。这两种策略对不同的主存修改算法，其效果不同，但命中率差别不大。目前写回法一般采用按写分配法，而写直达法则一般采用不按写分配法。,写回法和写直达法都需要有少量缓冲器。写回法中缓冲器用于暂存将要写回的块，使之不必等待被替换

17、块写回主存后才开始进行Cache取。写直达法中缓冲器则用于缓冲由写Cache所要求的写回主存的内容，使CPU不必等待这些写主存完成就能往下运行。缓冲器由要存的数据和要存入的目标地址组成。在写直达系统中容量为4的缓冲器就可以显著改进其性能，IBM 3033就是这样用的。要注意的这些缓冲器对Cache和主存是透明的。在设计时，要处理好可能由它们所引起的错误(如另一个处理机要访问的主存单元的内容正好仍在缓冲器中)。,5)两种方法对比 a)写回法有利于省去许多将中间结果写入主存的无谓开销。但是增加了Cache的复杂性。b)可靠性上写回法不如写直达法好。c)具体采用哪种方法还与系统使用场合有关。d)如果

18、让多CPU共享主存交换信息改成共享Cache交换信息，信息的一致性就能得到保证。e)对于共享主存的多CPU系统，绝大多数还是采用各个CPU都有自己的Cache的方式与共享主存连接。这样的系统由于Cache的透明性，仅靠写直达法并不能保证同一主存单元在各个Cache中的对应内容都一致。如下图：,要采取措施保证让有此单元的各个Cache的内容都一致才行。,CPU A,Cache a,CPU B,Cache b,主存,图 4.41 每个处理机都有Cache的共享多处理机系统,解决办法：采用播写法：即任何处理机要写入Cache时，不仅要写入自己Cache的目标块和主存中，还把信息或者播写到所有Cach

19、e有此单元的地方，或者让所有Cache有此单元的块作废以便下次访问时按缺块处理，从主存中重新调入。控制某些共享信息（如信号灯或作业队等）不等进入Cache。目录表法：即在CPU读/写Cache不命中时，先查主存中的目录表以判定目录块是否在别的Cache内，以及是否正在被修改等，然后再决定如何读写此块。,6)第二种问题 Cache内容跟不上已变化了的主存内容的问题，有 两种解决办法：a)当I/O处理机未经Cache往主存写入新内容的同时，由OS经某个专用指令清除整个Cache。这种办法的缺点是象我们在讲述用专用指令清除快表一样，会使Cache对OS和系统程序员成为不透明的，因此并不好。b)当I/

20、O处理机往主存某个区域写入新内容时，由专用硬件自动地将Cache内对应此区域地副本作废，而不必由OS进行任何干预，从而保持Cache的透明性。,2.Cache的取算法 1)预取法 为了便于硬件实现，通常只预取直接顺序的下一块，即在访问到主存的第i块(不论是否已取进Cache)时，只有第i1块才是可能的预取块。至于何时将该块取进，可以有恒预取和不命中时预取两种不同的方法。恒预取指的是只要访问到主存的第i块的某个字，不论Cache是否命中，恒发预取指令。不命中时预取仅当访问第i块不命中时，才发预取指令。,2)影响命中率的其它因素 a)块的大小：若每块的字节数过少，预取的效果不明显。从预取的需要出发

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

22、干扰影响)二者之和的比较来得到。,3)计算分析 设Dc为Cache不命中时，由主存调一块进Cache的开销，则：a)按需取进法的不命中开销为：Dc 不命中率(按需取进法)b)预取法不命中的开销为：Dc 不命中率(预取法)而预取法还应有预取开销，为此，我们设：预取率：预取总块数/访存总块数 Pa：预取访主存和访Cache的开销,补充知识：,c)预取法取进预取块的开销为：Pa 预取率 访问率：访Cache的总次数/程序访Cache的总次数，即(程序访Cache次数预取访Cache次数)/程序访Cache次数。Ac：由于预取访Cache占用了Cache，延迟、干扰了程序对Cache的访问的预取干扰开

23、销。d)预取法对程序访Cache的映象为：Ac(访问率1)e)结论 由上计算可知，只有下式成立，即：,补充知识：,Dc 不命中率(按需取进)Dc 不命中率(预取)Pa 预取率 Ac(访问率1)时，预取法才是可取的。这里，采用缓冲器技术是减少预取干扰的好办法。Cache和主存都设置预取专用缓冲器，使预取访主存与访Cache都尽可能在主存、Cache空闲时进行。,补充知识：,3.任务切换对失效率的影响 1)两种失效率 a)冷启动(Coldstart)失效率：从Cache为空(指新进程所需的内容都未装入Cache内)开始到Cache全部被装满这一期间的失效率。b)热启动(Warmstart)失效率：

24、从Cache为现行进程装满之后测出的失效率。,补充知识：,2)影响失效率的因素 a)与任务的切换频度(平均时间间隔Qsw)有关 Qsw对失效率的影响和工作负荷有很大关系。比如，如果进程切换发生在用户程序因为系统需要运行管理程序来处理某个I/O中断或时钟中断请求时，则Qsw值愈小，表明由管理程序切换回原先的用户程序愈快，Cache中保留的原先程序的指令和数据就愈多，即失效率愈低。但是如果进程切换是在几个用户程序之间进行，且每个进程都要更换掉Cache中的大部分内容时，Qsw值愈小就会使失效率愈高。,补充知识：,b)与Cache的容量有关 Qsw值一定时，若容量过小，存不下该程序的工作区，那么就会

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

26、从Cache中替换出大量更有希望将重新使用的数据。,补充知识：,4.影响Cache存储器性能的因素 1)不命中率与Cache的容量、组的大小和块的大小的一般关系,不命中率1Hc,Cache容量,组的大小一定,块的大小减小,(a),不命中率1Hc,Cache容量,块的大小一定,组的大小减小,(b),图4.42 块的大小、组的大小与Cache容量对Cache命中率的影响,2)Cache主存存储层次的等效速度与命中率的关系 设：tc为Cache的访问时间；tm为主存周期；Hc为访Cache的命中率；则Cache存储器的等效存储周期为：taHc tc(1 Hc)tm 与主存辅存存储层次不同的是一旦Ca

27、che不命中，由于主存与CPU之间有直接通路，CPU对第二级的访问时间就是tm，而不是调块时间再加一个访Cache的时间了。这样，采用Cache比之于处理机直,接访问主存，其速度提高的倍数为：tm/ta tm/(Hc tc(1 Hc)tm)1/(1(1tc/tm)Hc)因为Hc总是小于1，可以令Hc/(+1)，代入上式得：(+1)显然，不管Cache本身的速度有多高，只要Cache的命中率有限，那么采用Cache主存存储层次后，速度能提高的最大值是有限的，不会超过+1倍。,tm tm+tc,3)Cache的容量对机器速度的影响 对流水机器，机器速度与主存速度、CPU拍宽、Cache容量的可能关

28、系如图4.49所示，机器的单位是MIPS(每秒执行百万条指令)，主存采用多体交叉存取。a)由图可见，主存速度和CPU周期一定时，由不用Cache到Cache容量从4KB增大到64KB，机器速度有了显著提高，尤其是在主存速度较低时。b)还可以看出，Cache容量的增大，可以显著降低对主存速度的要求。,4)总结 总之，Cache本身的速度与容量都会影响Cache存储器的等效访问速度。如果对Cache存储器的等效访问速度不满意，需要改进的话就要作具体分析，看看现在Cache的等效访问速度是否已接近于第一级Cache本身的访问速度。如果尚差的较远，说明Cache的命中率低，这个时时就不是去采用更高速度

29、的Cache片子来替换现有的Cache片子，而应当从提高Cache的命中率入手，包括调整组的大小、替换算法以及增大Cache容量等方面着手，否则该速度是无法提高的。相反的，如果实际的等效访问速,度已经非常接近于Cache本身的访问速度还不能满足速度要求时，就只有更换更高速的Cache片子。否则，任何其它途径也是不会有什么效果的。因此我们不能盲目设计和改进，否则花了很大代价，却反而降低了系统的性能价格比。,4.3.5“Cache主存辅存”存储层次 1.三级存储层次的地址变换：CPU提供访存的虚地址可能需要变换成Cache地址、主存地址或辅存地址。1)对应于虚地址的单元已在Cache中 这时就需要

30、把虚地址直接变换成Cache地址来访问Cache，而不是先把虚地址变换成主存实地址，再由主存实地址变换成Cache地址，这样可以缩短地址变换的时间。,补充知识：,2)对应单元已在主存但尚未调入Cache 这时则需要把虚地址经快表和慢表变换成主存实地址去访主存，对读访问以及采用按写访问还必须进行虚地址到Cache地址的映象或变换，以便把包含对应此单元所在的一块调入或替换进Cache。3)对应单元还不在主存 这时就需要把虚地址变换成辅存实地址去辅存调页，同时还要将虚地址映象变换成主存实地址将页调入主存，以及把虚地址映象变换成Cache地址，将其中的一块装入Cache。,补充知识：,2.访问Cach

31、e过程 在这三级存储层次中通常总是让页的大小恰好时块的2的幂倍，每一块的大小又是字的2的幂倍。而且每次用虚页号查快表和慢表以取得主存实地址和用虚地址对应Cache块号位置的虚块号经组相联去访Cache(Cache中每个单元存放有主存实地址和对应的数据)同时进行。若能在快表中找到，就用由快表来的主存实地址与由Cache中读出的主存实地址相比较。当两者相符，存在Cache中该单元的数据就是要访问的虚、实地址的内容。写Cache的过程与此类似。,补充知识：,4.4 主存保护,大多数计算机系统设计成让其资源能被并行的多个用户所共享，就主存来说，就同时存有多个用户的程序和系统软件。为使系统能正常工作，应

32、防止由于一个用户程序出错而破坏主存中其它用户的程序或系统软件，还要防止一个用户程序不合法地访问不是分配给它的主存区域，哪怕这种访问不会引起系统破坏。因此，系统结构需要为主存的使用提供存储保护，它是多道程序和多处理机系统所必不可少的。,补充知识：,1.存储区域的保护 1)主存系统的保护 对于不是虚拟存储器的主存系统可采用第二章讲过的界限寄存器方式，由系统软件经特权指令置定上、下界寄存器，从而划定每个用户程序的区域，禁止它越界访问。由于用户程序不能改变上、下界的值，因此不论它如何出错，也只能破坏该用户自身的程序，侵犯不到别的用户程序及系统软件。,补充知识：,2)虚拟存储系统 由于界限寄存器方式只适

33、用于每个用户程序占用主存一个或几个(当有多对上、下界寄存器时)连续的区域；而对于虚拟存储系统，由于一个用户的各页能离散地分布于主存内，从而无法使用这种保护方式。对虚拟存储系统的主存区域保护就需要采用页表保护和键式保护等方式。,补充知识：,a)页表保护 每个程序都有自己的页表，其行数等于该程序的虚页数。例如它有4页，则只能有0、1、2、3这4个虚页号。设由OS建立的程序也表，这4个虚页号分别对应于实页号4、8、10、14，则不论虚地址如何出错，总只能影响主存中分配给该程序的第4、8、10、14号实页。假设虚页号错成5，肯定不可能在该程序的页表中找到，也就访问不了主存，当然就不会映象主存中其它程序

34、的区域。这正是虚拟存储系统本身固有的保护机能，也是它的一大优点。为了便于实现这种保护，还可以在段表中的每行内，不,补充知识：,仅设置页表起点，还设置段长(页数)项。若出现该段内的虚页号大于段长，则可以发越界中断。这种页表保护是在没有形成主存实地址前进行的保护，使之无法形成能侵犯别的程序区域的主存地址。然而，若地址形成环节由于软、硬件方面的故障而形成了不属于本程序区域的错误主存地址时，则上述这种保护就无能为力了。因此，还应采取进一步的保护措施，键方式就是其中成功的一种。,补充知识：,b)键方式 是由OS按当时主存的使用分配状况给主存的每页配一个键，称为存储键，它相当于一把“锁”。所有页的存储键存

35、在于相应的快速寄存器内，每个用户(任务)的各实页的页存储键都相同。为了打开这把锁，需要有把“钥匙”，称为访问键。每个用户的访问键由OS给定，存在处理机的程序状态字(PSW)或控制寄存器中。程序每次访存前，要核对主存地址所在页的存储键是否与该道程序的访问键相符，只有相符才准访问。这样，就是错误地形成了侵犯别的程序的主存地址，也因为这种键保护而仍然不允许访问。,补充知识：,c)环状保护 环状保护把系统程序和用户程序按其重要性及对整个系统能否正常工作的影响程度分层，如图4.50所示。设0、1、2三层是系统程序的，之外的各层是同一用户程序的分层。环号大小表示保护的级别，环号愈大，等级愈低。在现行程序运

36、行前，先由OS定好程序各页的环号，并置入也表。而后把该道程序的开始环号送入处理机内的现行环号寄存器，并且把OS规定给该程序的上限环号(规定该程序所能进入的最内层环号)也置入相应的寄存器。,补充知识：,若是Pi在某一时候属于i层各页的集合，则当进程执行PPi页内的程序时，允许访问FPj页，这里对应的是ji。但是如果是ji时，则需由OS环控制例行程序判定这个内向访问是否允许和是否正确之后才能访问，否则就是出错，进入保护处理。但j值肯定不能小于给定的上限环号。只要ji，就进入中断，若允许访问，则需经特权指令把现行环号寄存器的值由i改为j。,补充知识：,这种环式保护既能保证由于用户程序的出错不至于侵犯

37、系统程序，也能保证由于同一用户程序内的低级(环号大)的部分的出错而不致破坏其高级(环号小)的部分。这种环式保护对系统程序的研究和调试运行特别有利，因为可以做到能修改系统程序的某些部分而不必担心会影响到系统程序已设计好并调好的核心部分。至于如何控制ji的跨层访问，有的机器规定只能由规定的转移指令执行，且对和ji和ji分别只能用不同的转移指令。,补充知识：,2.访问方式的保护 上述种种区域保护，如判越界、判建相符、判环号相符、判不超出段长等等，都是经硬件实现的，因此速度可以是很快的。这些区域保护是对允许访问的区域可以进行任何形式的访问，而对允许区域之外，则任何形式的访问都不允许。但在实际中，只是这

38、种限制往往适应不了各种应用的要求，因此还得加上访问方式的保护(限制)。,补充知识：,1)对主存信息的使用可以有读R、写W和执行E三种方式。相应的就有R、W、E访问方式保护，这3者的逻辑组合可以反映出各种应用要求，如：RWE不允许进行任何访问；RWE可以进行任何访问；RWE只能进行读访问；RWE只能按数据进行读写；RWE只能执行，不能作为数据使用；REW只能进行写访问；REW不准写访问。,补充知识：,2)对前面讲过的各种区域保护，都可以加上相应的访问方式位以实现这种访问限制。3)至于环式保护和也表保护，可以把R、W、E等访问方式位设在各个程序的段、页表的各行内，使得同一环内或同一段内的各页可以有

39、上述种种不同的访问保护，以增强灵活性。4)在某些应用中，我么既要求能实现多个用户可读、写访问共享的数据，但又要保证只当一个用户访问完该数据后，别的用户才可以访问，以防止在一个用户还未把某个共享文件写好之前，别的用户却能把它读了去。可以采用“测试与置定”和“比较与交换”指令实现这点。所以这也是一种保护方法。,补充知识：,第4章 小结,4.1 存储体系的形成与性能 1.存储器的性能要求 1)大容量 2)低价格 3)高速度 访问时间TA 存储周期TM 存储器频宽,4)结论 由于存储器的价格、速度和容量的要求是相互矛盾的，为了同时满足三方面的要求，在一个完整的存储体系中，必须采用不同工艺的存储器，使得

40、信息以各种方式分布于不同的存储体。2.并行主存系统频宽的分析 1)类型 单体单字 单体多字 多体单字交叉 多体多字交叉,2)分析结论 由于程序的转移概率不会很低，数据分布的离散性较大，所以单纯靠增大m来提高并行主存系统的频宽是有限的，而且性价比还会随m的增大而下降。如果采用并行主存系统仍不能满足速度上的要求，就必须从系统结构上改进，采用存储体系。3.存储体系的形成与分支 1)容量需求 主存辅存存储层次 程序局部性,2)速度需求 Cache主存存储层次 程序局部性 3)多级存储层次4.存储体系的性能参数 1)存储体系的每位平均价格c 2)命中率H=R1/(R1+R2)3)等效访问时间 TA=HT

41、A1+(1-H)TA2,4.2虚拟存储器 1.管理方式 1)段式管理 a)思想：根据程序的模块性，把一个复杂的大程序分解成多个逻辑上相对独立的模块。b)段表 为了进行段式管理，每道程序都由一个段表(映像表)，以存放该程序各程序段装入主存的状况信息。,段名(号)：实际由于段号与行对应，省略掉 装入位：表征是(1)否(0)已调入主存 地址：调入主存时，在主存的起始(绝对)地址 段长：段的大小，限制偏移越界 访问方式：只读、可写、只执行，提供访问保护 c)段表基址寄存器 段表长度:该道程序的段数(段表行数)段表基地址:程序的段表在主存中的起始地址,d)虚拟地址 基号(程序号):段表在段表基址寄存器的

42、位置 段号:段在段表中的位置 段内位移:所访问单元在段内的偏移 e)实主存管理表 占用区域表 可用区域表 f)可用区域分配算法 首先分配算法 最佳分配算法,2)页式管理 思想：把主存空间和程序空间都机械的等分成固定大小的页(页面大小因机器不同而异，一般在512到几kB)然后按页顺序编号。3)段页式管理 思想：把内存机械的等分成固定大小的页，把程序按模块分段，每个段分成与主存页面大小相同的页，每道程序通过一个段表和相应于每段的一组页表来进行定位。问题：二次查表，费时间,2.页式虚拟存储器的构成 1)地址映像与变换 a)地址映像 就是将虚存单元按某种规则装入(定位于)实存，即建立多用户虚地址NS与

43、实存地址np的对应关系。b)地址变换 指的是程序按这种映像关系装入实存后，在执行时多用户虚地址NS如何变换成对应的实地址np。c)全相联映像 让每道程序的任何虚页可以映像装入到主存的任何实页位置,2)替换算法 a)目的 当辅存中的页面调入主存发生页面争用时，只有强制腾出主存中某页后才能接纳从辅存调来的新页面。替换算法就是解决具体从主存中选择哪一页作为被替换的页。b)原则 有高的主存命中率 算法便于实现 辅助软、硬件成本尽量低,c)常用算法 随机算法(Random,RAND)先进先出算法(First In First Out,FIFO)近期最少使用算法(Least Recently Used,L

44、RU)优化替换算法(OPT)衡量标准 d)堆栈型替换算法 保证命中率随主存页数的增加只可能提高，至少不会下降。e)页面失效频率法(PFF)根据各道程序运行中的主存页面失效率的高低,由OS来动态调节分配给每道程序的实页数。,3)影响命命中率的因素 a)与替换算法有关 b)命中率与页地址流有关 c)与主存容量(即分配给程序的主存页数)有关 4)虚拟存储器工作的全过程 P92图4.13页式虚拟存储器工作原理,3.页式虚拟存储器实现中的问题 1)页面失效处理 后援寄存器技术 预判技术 解决方法 替换算法 页面大小不能过大 2)提高虚拟存储器等效访问速度的措施 快表慢表 散列快表硬件实现散列函数,3)影

45、响主存命中率和CPU效率的某些因素 a)与Sp有关 P108图4.28 页面大小Sp、容量S1与命中率H的关系曲线图 b)命中率与主存容量S1有关 P109图4.29命中率H与容量S1的关系图 c)与所采用的页面调度策略有关,4.3高速缓冲存储器(Cache)1.基本结构 特点：9个方面(与虚拟存储器对比)2.地址的映像与变换 1)全相联映像和变换 a)规则：主存中的任意一块均可映像装入到Cache内的任意一块的位置。b)地址变换过程 c)优缺点 块冲突率低；代价大，查表速度难以提高。,2)直接映像及其变换 规则：主存中每一块只能映像到Cache中唯一一个特定位置：主存的第i块只能映像到第im

46、od2ncb块位置上。相当于把主存空间按Cache空间分区，每区内各块只能按位置一一对应到Cache相应位置上。3)组相联映象及其变换 规则：把主存按Cache大小分区，整个Cache是一区，每个区再分成相等的组，组内分块。组间直接映象，组内各块全相联映象。,4)段相联映象 规则：把主存和Cache分成具有相同的Z块的若干段，段与段之间采用全相联映象，而段内各块之间采用直接映象，实质上就是组相联映象的特例。3.替换算法的实现 1)堆栈法 思想：栈顶恒存放近期最久访问过的页的页号，而栈底恒存放近期最久没有访问过的页的页号，即准备被替换掉的页的页号。按此思想组成一个硬件堆栈。,2)比较对法 思路：

47、让各个块成对组合，用一个触发器的状态来表示该比较对内两块访问的远近次序，再经门电路就可以找到LRU块。4.Cache的透明性及性能分析 1)Cache的透明性分析 a)写回法 在CPU执行写操作时，只是把信息写入Cache，仅当需要被替换时，才将已经被写入过的Cache块先送回主存，然后再调入新块。,b)写直达法 也称为存直达法，它利用Cache主存存储层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。2)Cache的取算法 a)预取法 b)块的大小 c)预取开销 3)任务切换对失效率的影响 a)与任务的切换频度(平均时间间隔Qsw)有关 b)与Cac

48、he的容量有关,4)影响Cache存储器性能的因素 a)不命中率与Cache的容量、组的大小和块的大小的一般关系 看P121图4.42块的大小、组的大小与Cache容量对Cache命中率的影响。b)Cache主存存储层次的等效速度与命中率的关系5.Cache主存辅存存储层次 1)对应于虚地址的单元已在Cache中 2)对应单元已在主存但尚未调入Cache 3)对应单元还不在主存,4.4主存保护 1.存储区域的保护 1)页表保护 2)键方式 3)环式保护 2.访问方式的保护,第4章 习题,1.某虚拟存储器共8个页面，每页为1024个字，时间主存为4096个字，采用页表法进行地址映象。映象表内容如

49、右图：1)列出会发生页面失效 的全部虚页号；2)按以下虚地址计算主 存实地址：0，3728，1023，1024，2055，7800，4096，6800。,实页号,装入位,1,1,0,0,1,0,1,0,3,1,2,3,2,1,0,0,【分析】要找出会发生页面失效的全部虚页号，关键是搞清楚页表法进行地址映象所用的虚页表的构成。要由虚地址计算出主存的实地址，首先应根据题意将虚、实地址中各个字段及其位数确定下来。由于虚拟存储器共8个页面，每个页面大小为1024字，,实页号,装入位,1,1,0,0,1,0,1,0,3,1,2,3,2,1,0,0,虚页号,0,1,2,3,4,5,6,7,可知，虚页号字段

50、为3位二进制位(238)，页内位移字段为10位二进制位(2101024)。由于虚实页面大小是一样的，实际主存为4096个字，不难得到实页号字段为2位(224)，页内位移为10位(2101024)，所以：,虚页号,页内位移,实页号,页内位移,虚地址字段,实地址字段,3位,10位,10位,2位,这样，根据题目所给的虚地址可以按下面方法来计算出虚页号和页内位移量。其中，虚页号为：虚地址/页面大小取整数 页内位移量为：虚地址虚页号页面大小 或：虚地址页面大小取余数 计算主存实地址为：实页号页面大小页内位移量【解答】1)发生页面失效的全部虚页号就是映象表中装入位为0的行所对应的虚页号，即2，3，5，7。