•         高速缓存的工作原理
•         高速缓存的替换策略

高速缓存的工作原理

      字：存放在一个存储单元中的二进制代码组合

     字块：存储在连续的存储单元中而被看作是一个单元的一组字

•          一个字有32位
•          一个字块共B个字
•          主存共M个字块

           B*M = 主存总字数

           B*M*32 = 主存总容量（bits）

            字的地址包含  前m位指定字块的地址   后b位指字在字块中的地址

                 2^m = M           2^b  =  B

  例子：

     假设主存用户空间容量为4G，字块大小为4M，字长为32位，则对于字地址中的块地址m和块内地址b的位数，至少应该是多少？

                                 4  G  =   4096 M

             字块数       4096 /  4   = 1024  

          字块地址m    log2  1024  = 10

          块内字数      4  M  /  32  bit   =  1048576

       块内地址b      log2  1048576  =  20

                         m   >=  10             b   >=   20

•        存储的逻辑结构类似
•        缓存的容量较小
•        缓存的速度更快

•          一个字有32位
•           一个字块共B个字
•          缓存共C个字块

命中率

•              CPU需要的数据在缓存里
•               CPU需要的数据不在缓存里
•               不在缓存的数据需要去主存拿

命中率是衡量缓存的重要性能指标

理论上CPU每次都从高速缓存取数据的时候，命中率为1

访问主存次数：Nm

访问Cache次数：Nc

访问效率：e

访问主存时间：tm

访问缓存时间：tc

访问Cache—主存系统平均时间：ta

例子：

          假设CPU在执行某段程序时，共访问了Cache命中2000次，访问主存50次，已知Cache的存取时间为50ns，主存的存取时间为200ns，求Cache-主存系统的命中率、访问效率和平均访问时间。

                       命中率                         h  = 2000/（2000 + 50）= 0.97

                      访问效率                       e = 50 /（0.97 * 50  + (1 - 0.97) * 200） = 91.7%

                     平均访问时间               ta = 0.97 * 50 + (1 - 0.97) * 200 = 54.5ns

高速缓存的替换策略

            需要性能良好的缓存替换策略

• 随机算法
• 先进先出算法（FIFO）
• 最不经常使用算法（LFU）
• 最近最少使用算法（LRU）

先进先出算法（FIFO）

•       把高速缓存看做是一个先进先出的队列
•         优先替换最先进入队列的字块

最不经常使用算法(LFU)
 

•       优先淘汰最不经常使用的字块
•         需要额外的空间记录字块的使用频率

最近最少使用算法 (LRU)
 

•        优先淘汰一段时间内没有使用的字块
•         有多种实现方法，一般使用双向链表
•        把当前访问节点置于链表前面（保证链表头部节点是最近使用的）

例子：

            缓存4个字块，（）表示使用的字块， []表示淘汰的字块