1、舉例說(shuō)明：,設(shè)有一道程序，有1至5共五頁(yè)，執(zhí)行時(shí)的頁(yè)地址流（即執(zhí)行時(shí)依次用到的程序頁(yè)頁(yè)號(hào)）為： 2，3，2，1，5，2，4，5，3，2，5，2 若分配給該道程序的主存有3頁(yè)，分別采用FIFO和LRU替換算法表示這3頁(yè)的使用和替換過(guò)程。,說(shuō)明： （1）FIFO算法：替換最早裝入主存的頁(yè)； （2）LRU算法：依據(jù)各塊使用的情況，選擇最近最少使用的塊替換。,時(shí)間t 1 2 3 4 5 6 7 8 9 10 11 12 頁(yè)地址流 2 3 2 1 5 2 4 5 3 2 5 2,先進(jìn)先出 FIFO,調(diào)進(jìn),調(diào)進(jìn),調(diào)進(jìn),命中,替換,替換,替換,替換,命中,命中,替換,替換,2,2,3,2,3,2,2*,3,

2、1,3*,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,調(diào)進(jìn),2,3,調(diào)進(jìn),2,3,2,命中,2,3*,1,調(diào)進(jìn),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也不是最理想的方法，它僅僅是根據(jù)過(guò)去訪存的頻率估計(jì)未來(lái)的訪存情況，因而只是推測(cè)的方法； 塊命中率與地址流、塊的大小和塊的數(shù)量有關(guān)，應(yīng)具體問(wèn)題具體分析，選擇適當(dāng)?shù)乃惴ǎ?存儲(chǔ)單元替換時(shí)應(yīng)注意防止出現(xiàn)顛簸現(xiàn)象，即調(diào)入一塊時(shí)將另一塊調(diào)出，緊接著又需要訪問(wèn)剛剛調(diào)出塊的數(shù)據(jù)，而將該塊調(diào)入時(shí)又將上一塊調(diào)出，即顛簸。,練習(xí)1：,對(duì)于一個(gè)容量為3個(gè)塊的全相聯(lián)Cache，假定訪問(wèn)的地址塊號(hào)序列為 1，2，3，4，1，2，3，4，分別用FIFO算法和LRU算法，寫出其隊(duì)列變化情況，并得出結(jié)論。,練習(xí)2,對(duì)于一個(gè)全相聯(lián)Cache，假定訪問(wèn)的地址塊號(hào)序列為 1，2，3，4，1，2，5，1，2，3，4，5，在先進(jìn)先出替換方式