Lecture-X-存储系统5.ppt

* * * * * * * * * * * * * * * * * * * 新 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 主存不同区的相同序号的组和Cache的同序号的组采用直接映象。主存和Cache同序号的组内各块采用全相联映象。（不同序号的组没有映象关系）参见图4-42所示。 * * 4-42 * * 从图4-42可以看出，当每组仅有1块时，就成了直接映象方式；而当主存每区只有一个组，且Cache也只有一个组时，就成了全相联映象方式。 * * 组相联映象方式既避免了全相联方式时分配页面时的大量计算，也减少了直接相联方式时块的冲突，提高了存储体系的效率，因而在计算机中得到广泛的应用。 2）地址变换 * * 4-43 * * 在程序执行过程中，用主存地址的组号G访问块表，从块表中读出K个字（K是组内分块时块的个数），每个字含有区号E，组内块号B以及b，将读出的K个字的E和B的值和主存地址E和B的值逐一进行相联比较， * * 如果相等，表示命中，于是将同时读出的b送入CAR的b字段，而MAR中的G和W亦分别送入CAR的g和w字段，于是得到Cache的地址。由此去读Cache，最后把从Cache读出的信息送往CPU。 * * 如果不等，表示没有命中，需用MAR中的地址去访问M，并将从主存中读出的信息送向CPU。与此同时，还要将包括被访问的信息在内的一块信息从主存调入Cache，还要修改块表等等。 * * * * * * 4.3.3 替换算法 在地址变换过程中，如果发现Cache失效则需要将主存的一个新块数据调入Cache存储器中；由于此时与之相应的Cache块中已装满数据，这就要使用替换算法，从相应的Cache块中找出一个不常用的块，把它存到主存中原来的块位置，而Cache中空出的位置存放从主存调入的新块。 * * 替换算法和映象方式有关，直接映象方式不需要替换算法，全相联映象方式由于存储器任何一块数据都可以调入Cache中任意一块位置，因此替换算法比较复杂，组相联映象也需要从Cache中的相应块中淘汰（调出）一块，然后再从主存调入。 * * 常用的替换算法有FIFO算法和随机替换算法、LRU算法、LFU算法、OPT算法、环形FIFO算法。 * * FIFO（First In First Out）算法是一种先进先出替换算法，其算法思想是将同一组中最先调入Cache中的块替换出去。这种方法实现容易，开销较小。缺点是一些频繁使用的页面也会被替换出去。而频繁调入调出又增加了开销。 * * LRU（Least Recently used）算法即最近最少使用算法，这是一种最常用的替换算法。这种算法的思想是把一组中近期最少使用的块替换出去，因此必须记录组中各块的使用情况，这样才能确定出近期最少使用的块。其优点是LRU能提供较好的命中率。 * * LFU（Least Frequently Used），称为最久没有使用算法（最少频度使用算法），在虚拟存储器使用较为普遍。其算法思想是替换到目前为止最长时间没有使用的块（替换到目前为止访问最少的块），且认为该块也是将来最少访问的块。这反映了程序的局域性。LFU需在块表中为每一个块设置一个计数器。LFU算法命中率较高但控制逻辑较复杂。LFU算法包括堆找型算法和比较对法。 * * 4.3.4 高速缓存的写策略 在Cache与主存储器之间保持一致性是很重要的。每次对Cache执行写操作，在两个存储器的内容之间都会产生差别，要保持Cache一致性，对Cache的写，最终必须传送给主存储器。 当执行写操作时，Cache控制器判断其地址是否定位在Cache中。如果在，CPU的数据就会写到Cache中。对于进一步的主存储器操作，Cache控制器有以下几种主要的写策略。 * * 1）写直通方式（write through） 任一从CPU发出的写信号送到Cache的同时，也送到主存，以保证主存的数据能同步地更新。它的优点是操作简单，但由于主存的速度相对较慢，降低了系统的写速度并占用了部分总线时间。 * * 2）写回方式（write back） 为了尽量减少对主存的访问次数，克服写直通方式中每次数据写入都要访问主存，从而导致系统写速度降低并占用总线时间的弊病，就有了写回方式。它的工作原理是：数据一般只写到cache，而不写入主存，从而使写入的速度加快。但这样有可能出现Cache中的数据得到更新而对应主存中的数据却没有变（即数据不同步）的情况。此时可在Cache中设置一个标志地址及数据陈旧的信