題目大意
- 在Cache類中實(shí)現(xiàn)fetch方法將數(shù)據(jù)從內(nèi)存讀到Cache(如果還沒有加載到Cache)并返回被更新的Cache行的行號(需要調(diào)用不同的映射策略和替換策略)
- 實(shí)現(xiàn)三種映射策略(直接映射、全關(guān)聯(lián)映射齐板、組關(guān)聯(lián)映射)和三種替換策略(先進(jìn)先出桑李、最少使用击儡、最近使用)
簡單來說就是模擬一個Cache. README.md只提供了這么一些內(nèi)容，具體看了看代碼的TODO勇劣，兩個抽象類分別是MappingStrategy.java和ReplacementStrategy.java怎棱，我們需要完成繼承了他們的幾個策略并在Cache.java中完成調(diào)用。
映射策略
映射策略需要完成3種映射桦踊，部分方法需要調(diào)用父類中的替換策略。
直接映射
-
getTag()方法是根據(jù)內(nèi)存的塊號终畅，取出高12位tag并將后10位置為0籍胯，轉(zhuǎn)換成字符數(shù)組返回. -
map()方法則是訪問Cache類的靜態(tài)成員，讀出對應(yīng)行的tag與getTag()的結(jié)果進(jìn)行比對声离，數(shù)據(jù)有效且tag相等則返回塊號的低10位（這里可以不用對總行數(shù)取模）芒炼，否則返回-1. - 對于
writeCache()方法瘫怜，由于是直接映射术徊，沒有后續(xù)調(diào)用策略，因此這里從memory讀入數(shù)據(jù)后寫進(jìn)Cache鲸湃，再返回塊號的低10位轉(zhuǎn)成的整數(shù)即可赠涮。
關(guān)聯(lián)映射
- 關(guān)聯(lián)映射的tag就是塊號，
getTag()直接返回即可暗挑。 - 關(guān)聯(lián)映射的查找范圍是整個cache笋除，因此
map()需要從0到N-1行調(diào)用替換策略的isHit()方法。 - 同樣的炸裆，
writeCache()方法要先從memory的靜態(tài)成員中讀取data垃它，read()方法的參數(shù)應(yīng)該為以塊號作為高位，低位補(bǔ)充10個0的eip烹看，讀取長度為cache一行的大小国拇，即一個塊的大小Cache.LINE_SIZE_B，然后再調(diào)用策略里的writeCache()方法惯殊，把讀取到的data寫入0到N-1行范圍內(nèi)酱吝。
組關(guān)聯(lián)映射
這里的組關(guān)聯(lián)映射是4路組關(guān)聯(lián)，一共是1024/4=258=28個組土思，即組號占8位务热，標(biāo)記占22-8=14位
-
getTag()方法取出高14位tag并將后8位置為0忆嗜，轉(zhuǎn)換成字符數(shù)組返回。 - 由于是組關(guān)聯(lián)映射崎岂，
map()需要根據(jù)中間的8位組號確認(rèn)查找的起始點(diǎn)捆毫，8位組號為高位，補(bǔ)充低位2個0作為起始行冲甘，補(bǔ)充低位兩個1作為結(jié)束行冻璃，調(diào)用策略中的isHit()方法。 - 類似地损合，組關(guān)聯(lián)中的
writeCache()方法需要在memory的靜態(tài)成員中讀取對應(yīng)的data省艳，處理方式和關(guān)聯(lián)映射是一樣的（因?yàn)閷τ谕粋€塊號，讀取的塊開頭地址與結(jié)尾地址都一樣）嫁审，然后調(diào)用策略的writeCache()方法跋炕，把data寫入第二點(diǎn)提到的起始行與結(jié)束行之間的范圍。
替換策略
需要完成三種策略律适。
FIFO策略
維護(hù)一個內(nèi)容為Integer的隊(duì)列辐烂，從0到N-1個元素是從新到舊的訪問順序。
-
isHit()方法直接根據(jù)起始點(diǎn)訪問Cache里的靜態(tài)成員進(jìn)行比對即可捂贿。 -
writeCache()方法需要遍歷隊(duì)列纠修，如果隊(duì)列中的元素在區(qū)間內(nèi)且有效，更新命中指針并把計(jì)數(shù)器addup加1厂僧，注意這里需要維護(hù)一個invalid指針扣草，如果隊(duì)列中的元素在區(qū)間內(nèi)但無效則更新invalid，遍歷完成后判斷：- 如果指針未被更新或計(jì)數(shù)器小于區(qū)間長度颜屠，說明這個區(qū)間沒有被填滿辰妙，需要尋找在區(qū)間內(nèi)序號最小的有效位為
false的行，如果invalid被更新了甫窟，說明有失效的空行密浑，那么最小的空行號應(yīng)該是min(start+addup,invalid)，沒被更新則說明只是單純地區(qū)間沒有被填滿粗井，這時候需要把數(shù)據(jù)寫入找到的行并把這個行號寫入隊(duì)列開頭尔破。 - 否則說明區(qū)間已經(jīng)被填滿了，由于順序是從新到舊浇衬，順序遍歷最后更新的指針即最老訪問的行懒构。因此在指針的行處寫入數(shù)據(jù)并在隊(duì)列中刪除原行，重新寫入開頭径玖。
- 如果指針未被更新或計(jì)數(shù)器小于區(qū)間長度颜屠，說明這個區(qū)間沒有被填滿辰妙，需要尋找在區(qū)間內(nèi)序號最小的有效位為
LRU策略
維護(hù)一個時間戳痴脾。
-
isHit()需要在返回前更新時間戳，直接設(shè)成++timeStamp. - 類似FIFO梳星，
writeCache()需要判斷區(qū)間是否被填滿赞赖，同樣用指針記錄最小時間戳滚朵，用計(jì)數(shù)器記錄數(shù)量，如果沒滿則找到序號最小的有效位為false的行前域，如果滿了則更新指針行辕近，更新的時候需要多更新一個時間戳。
LFU策略
-
isHit()需要在返回前更新訪問次數(shù)匿垄，設(shè)成原次數(shù)+1. -
writeCache()同樣需要判斷區(qū)間是否填滿移宅， 也需要額外更新訪問次數(shù)，設(shè)成1（這一次是第一次訪問）椿疗。
Fetch方法
由于傳入?yún)?shù)確保了數(shù)據(jù)一定在同一個數(shù)據(jù)塊內(nèi)漏峰，所以我們只需要從地址取出高22位的塊號，調(diào)用映射策略的map()方法届榄，如果為-1說明未命中浅乔，需要寫入，此時返回調(diào)用的writeCache()方法即可铝条，否則說明命中靖苇，直接返回map().
修改了一些小bug之后，通過測試班缰。
代碼見github.
