《计算机组成原理Cache替换策略.ppt》由会员分享，可在线阅读，更多相关《计算机组成原理Cache替换策略.ppt（4页珍藏版）》请在三一办公上搜索。
1、举例说明：,设有一道程序，有1至5共五页，执行时的页地址流（即执行时依次用到的程序页页号）为：2，3，2，1，5，2，4，5，3，2，5，2若分配给该道程序的主存有3页，分别采用FIFO和LRU替换算法表示这3页的使用和替换过程。,说明：（1）FIFO算法：替换最早装入主存的页；（2）LRU算法：依据各块使用的情况，选择最近最少使用的块替换。,时间t 1 2 3 4 5 6 7 8 9 10 11 12页地址流 2 3 2 1 5 2 4 5 3 2 5 2,先进先出 FIFO,调进,调进,调进,命中,替换,替换,替换,替换,命中,命中,替换,替换,2,2,3,2,3,2,2*,3,1,3*,
2、1,5,5,1*,2,5*,2,4,2,4,5*,2*,4,3,3,4,2*,3,4*,5,3*,5,2,命中,命中,命中,命中3次,近期最少使用LRU,2,调进,2,3,调进,2,3,2,命中,2,3*,1,调进,2*,1,5,替换,5,1*,2,命中,2,5*,4,替换,2*,4,5,命中,5,4*,3,替换,3,5*,2,替换,3*,2,5,命中,5,2,3*,命中,命中,命中,命中,命中,命中,命中5次,2,注意：,LRU也不是最理想的方法，它仅仅是根据过去访存的频率估计未来的访存情况，因而只是推测的方法；块命中率与地址流、块的大小和块的数量有关，应具体问题具体分析，选择适当的算法；存储单元替换时应注意防止出现颠簸现象，即调入一块时将另一块调出，紧接着又需要访问刚刚调出块的数据，而将该块调入时又将上一块调出，即颠簸。,练习1：,对于一个容量为3个块的全相联Cache，假定访问的地址块号序列为 1，2，3，4，1，2，3，4，分别用FIFO算法和LRU算法，写出其队列变化情况，并得出结论。,练习2,对于一个全相联Cache，假定访问的地址块号序列为 1，2，3，4，1，2，5，1，2，3，4，5，在先进先出替换方式下，分别写出分配给程序的主存页面是3页和4页的情况下，其队列的变化情况，并得出结论。,
