一種基于雙窗口的NAND閃存緩沖區(qū)管理算法

徐之光，嚴(yán) 華

(四川大學(xué)電子信息學(xué)院，成都 610065)

NAND閃存是現(xiàn)今最具前途的存儲(chǔ)介質(zhì)之一，有非易失性、抗沖擊性強(qiáng)、數(shù)據(jù)讀寫速度快、能耗低、噪音低、易移動(dòng)性等特點(diǎn)[1-2]。NAND閃存廣泛應(yīng)用于移動(dòng)設(shè)備、PC設(shè)備及大數(shù)據(jù)中心[3]，在呈現(xiàn)爆發(fā)式增長(zhǎng)的5G應(yīng)用、大數(shù)據(jù)和云計(jì)算、車載、智能終端、VR等領(lǐng)域都有卓越表現(xiàn)。

NAND閃存存儲(chǔ)空間由若干個(gè)塊(Block物理塊)構(gòu)成，而每個(gè)塊又由若干個(gè)頁(yè)(Page物理頁(yè))構(gòu)成。NAND閃存有讀、寫、擦除三種基本操作，其中讀/寫操作執(zhí)行單位為頁(yè)，而擦除操作執(zhí)行單位為塊，一般每個(gè)塊的擦除次數(shù)上限在104～105次，超過(guò)則會(huì)使閃存的存儲(chǔ)性能下降[4]。NAND閃存的3種基本操作的耗時(shí)不同，擦除耗時(shí)最長(zhǎng)、寫操作其次而讀速度最快，同時(shí)閃存必須先擦除才能寫入新數(shù)據(jù)，而不支持覆蓋寫的方式[5-6]。這些特點(diǎn)使得NAND閃存在進(jìn)行讀寫操作的過(guò)程中，其存儲(chǔ)性能逐漸降低，使用壽命逐漸變短。而使用NAND閃存緩沖區(qū)管理是提高閃存存儲(chǔ)性能、延長(zhǎng)其使用壽命的一個(gè)有效方法，其基本原理為利用數(shù)據(jù)訪問(wèn)具有局部性的特點(diǎn)，將訪問(wèn)頻度高的數(shù)據(jù)存入緩沖區(qū)，使得數(shù)據(jù)訪問(wèn)盡量在緩沖區(qū)中命中，有效降低閃存的訪問(wèn)開銷[7]。

近年來(lái)，中外學(xué)者提出了很多緩沖區(qū)管理策略，如LRU(least recently use)算法、LRU-WSR[8](LRU-write sequence reordering)算法、PR-LRU[9](probability of reference LRU)算法等。LRU算法是經(jīng)典緩沖區(qū)頁(yè)面置換算法，它認(rèn)為最有可能下次訪問(wèn)到的頁(yè)面是最近訪問(wèn)過(guò)的頁(yè)面，所以總是將最近訪問(wèn)的數(shù)據(jù)存放在緩沖區(qū)中，而淘汰最近沒(méi)有訪問(wèn)過(guò)的頁(yè)面。但是LRU算法是根據(jù)傳統(tǒng)機(jī)械硬盤設(shè)計(jì)，沒(méi)有考慮閃存的讀/寫操作延遲非對(duì)稱性，因此在閃存中算法性能較差。LRU-WSR算法在LRU的基礎(chǔ)上進(jìn)一步區(qū)分了冷熱數(shù)據(jù)，滯后置換出緩沖區(qū)的臟數(shù)據(jù)頁(yè)，而優(yōu)先置換出干凈數(shù)據(jù)頁(yè)和冷臟數(shù)據(jù)頁(yè)，減少了NAND閃存的寫操作次數(shù)，提高了緩沖區(qū)命中率。但LRU-WSR算法仍存在一些不足：①若某段時(shí)間內(nèi)只對(duì)干凈數(shù)據(jù)頁(yè)進(jìn)行頻繁訪問(wèn)，會(huì)導(dǎo)致熱臟數(shù)據(jù)頁(yè)很快置換出緩沖區(qū)，造成閃存的訪問(wèn)開銷明顯增加；②算法沒(méi)有考慮干凈數(shù)據(jù)頁(yè)面訪問(wèn)頻率，可能會(huì)造成熱干凈數(shù)據(jù)頁(yè)先于冷干凈數(shù)據(jù)頁(yè)被置換出，降低緩沖區(qū)的命中率。PR-LRU算法在LRU-WSR算法冷、熱LRU隊(duì)列基礎(chǔ)上，增加了一個(gè)驅(qū)逐LRU隊(duì)列來(lái)篩選置換出緩沖區(qū)的頁(yè)面，利用之前頁(yè)面的訪問(wèn)歷史，計(jì)算頁(yè)面的訪問(wèn)概率，從而預(yù)測(cè)未來(lái)頁(yè)面訪問(wèn)情況。但PR-LRU算法仍存在一些不足：①?zèng)]有考慮控制冷LRU隊(duì)列長(zhǎng)度，也沒(méi)有在驅(qū)逐LRU隊(duì)列中滯后置換新的冷頁(yè)面，導(dǎo)致冷LRU長(zhǎng)度不夠時(shí)，剛進(jìn)緩沖區(qū)的冷干凈頁(yè)面可能被很快置換出，從而增加了閃存的訪問(wèn)開銷；②算法沒(méi)有考慮根據(jù)負(fù)載不同，調(diào)整冷/熱LRU隊(duì)列長(zhǎng)度比例，負(fù)載局部性較高時(shí)，熱LRU隊(duì)列長(zhǎng)度不足會(huì)導(dǎo)致算法性能下降，而負(fù)載局部性較低時(shí)，熱LRU隊(duì)列則需要被分配更低空間比例。

已有的NAND閃存緩沖區(qū)頁(yè)面置換算法針對(duì)NAND閃存的特性，基本都對(duì)數(shù)據(jù)頁(yè)面冷熱和讀寫訪問(wèn)開銷差異進(jìn)行了考慮，并制定相應(yīng)的置換策略。但這些算法置換代價(jià)比較固定，缺少對(duì)冷干凈頁(yè)面最少數(shù)量的控制，導(dǎo)致剛進(jìn)入緩沖區(qū)的冷干凈頁(yè)面很快置換出；缺少對(duì)長(zhǎng)時(shí)間未被訪問(wèn)的熱臟頁(yè)面的考慮，導(dǎo)致這些舊熱臟頁(yè)面滯留在緩沖區(qū);且已有算法每次進(jìn)行頁(yè)面頁(yè)面替換時(shí)都需要反向遍歷鏈表，算法效率有待提高。

通過(guò)對(duì)NAND閃存緩沖區(qū)管理算法進(jìn)行更深入的研究，針對(duì)上述3種算法的不足，設(shè)計(jì)一種基于雙窗口的NAND閃存緩沖區(qū)頁(yè)面置換算法——DW-LRU(double windows LRU)算法。與已有算法不同的是：將冷、熱2條LRU隊(duì)列細(xì)分為冷干凈、冷臟、熱干凈、熱臟4條LRU鏈表，并且引入新近度OR(operation recency)，進(jìn)一步細(xì)分頁(yè)面的置換代價(jià)。算法采用新的置換策略調(diào)整頁(yè)面，直接從各鏈表LRU端置換頁(yè)面，無(wú)需反向遍歷鏈表。并且DW-LRU算法在冷干凈LRU鏈表設(shè)置了靜態(tài)窗口w1，限定了冷干凈LRU鏈表的最小長(zhǎng)度；在熱臟LRU鏈表上設(shè)置了動(dòng)態(tài)窗口w2，讓長(zhǎng)時(shí)間沒(méi)被訪問(wèn)的舊熱臟頁(yè)面也能被置換出緩沖區(qū)。實(shí)驗(yàn)基于Linux系統(tǒng)，使用Qemu軟件建立嵌入式仿真平臺(tái)，在數(shù)據(jù)緩沖區(qū)命中率、閃存寫操作次數(shù)和算法運(yùn)行時(shí)間等方面[8-9]與上述3種算法進(jìn)行對(duì)比。

1 算法的實(shí)現(xiàn)

1.1 基本原理

圖1為DW-LRU算法緩沖區(qū)結(jié)構(gòu)示意圖。DW-LRU算法在緩存區(qū)維護(hù)了4個(gè)LRU鏈表來(lái)管理，即都是用最少最近原則將數(shù)據(jù)頁(yè)組成鏈表，以最近使用位置(MRU端)為首，以訪問(wèn)時(shí)間間隔最久位置(LRU端)為尾，分別存放冷干凈頁(yè)面(CC)、冷臟頁(yè)面(CD、熱干凈頁(yè)面(HC)和熱臟頁(yè)面(HD)。

圖1 DW-LRU算法結(jié)構(gòu)示意圖

當(dāng)上層文件系統(tǒng)執(zhí)行寫請(qǐng)求時(shí)，在緩存中對(duì)某數(shù)據(jù)頁(yè)面進(jìn)行過(guò)寫操作，該頁(yè)面數(shù)據(jù)被修改為與NAND閃存中數(shù)據(jù)不一致，需要被置換出緩存區(qū)將數(shù)據(jù)寫入NAND閃存設(shè)備中，這樣的頁(yè)面稱為臟頁(yè)面。反之，上層文件系統(tǒng)僅對(duì)某數(shù)據(jù)頁(yè)面進(jìn)行讀操作而未進(jìn)行過(guò)寫操作的頁(yè)面，則稱之為干凈頁(yè)面[8]。顯然，干凈頁(yè)面不必回寫到NAND閃存，對(duì)于緩存區(qū)頁(yè)面置換算法來(lái)說(shuō)置換代價(jià)更低。而考慮數(shù)據(jù)訪問(wèn)頻度，又可將緩沖區(qū)中數(shù)據(jù)頁(yè)面分為冷數(shù)據(jù)頁(yè)面和熱數(shù)據(jù)頁(yè)面，將其中僅被上層文件系統(tǒng)訪問(wèn)過(guò)一次的頁(yè)面稱為冷數(shù)據(jù)頁(yè)面，而將被訪問(wèn)過(guò)多次的頁(yè)面稱為熱數(shù)據(jù)頁(yè)面[8-9]。因此，緩存區(qū)頁(yè)面被分為4類：冷干凈頁(yè)面、冷臟頁(yè)面、熱干凈頁(yè)面及熱臟頁(yè)面。其頁(yè)面緩沖區(qū)置換代價(jià)關(guān)系如式(1)所示：

CCC

(1)

式(1)中：CCC為冷干凈頁(yè)面置換代價(jià)；CCD為冷臟頁(yè)面置換代價(jià)；CHC為熱干凈頁(yè)面置換代價(jià)；CHD為熱臟頁(yè)面置換代價(jià)。

然而，由于冷干凈頁(yè)面置換代價(jià)最小，如果不考慮控制冷干凈LRU鏈表長(zhǎng)度，保留一部分冷干凈頁(yè)面，可能會(huì)很快置換出剛寫入緩存區(qū)的冷干凈頁(yè)面，降低了緩存區(qū)命中率。因此，在冷干凈LRU鏈表頭部設(shè)置了靜態(tài)窗口w1來(lái)控制其長(zhǎng)度，w1大小為占整個(gè)緩沖區(qū)的大小的百分比。同時(shí)，由于熱臟頁(yè)面置換代價(jià)最大，可能會(huì)造成長(zhǎng)時(shí)間未被訪問(wèn)的熱臟頁(yè)面長(zhǎng)期滯留在緩存區(qū)中，稱這些頁(yè)面為舊熱臟頁(yè)面。因此，在熱臟LRU尾部設(shè)置了動(dòng)態(tài)窗口w2來(lái)處理舊熱臟頁(yè)面，w2大小為占整個(gè)緩沖區(qū)大小的百分比。

DW-LRU算法將數(shù)據(jù)頁(yè)面存放在相應(yīng)鏈表中，進(jìn)行頁(yè)面置換時(shí)，檢索一遍緩存區(qū)后，無(wú)需像已有算法如LRU-WSR算法和PR-LRU算法再檢索鏈表查找代價(jià)最低的數(shù)據(jù)頁(yè)來(lái)置換，而是直接對(duì)鏈表LRU端進(jìn)行操作，從而減少了算法所需的運(yùn)行時(shí)間。

DW-LRU算法主要思想如下。

(1)根據(jù)數(shù)據(jù)頁(yè)面的冷熱特征和訪問(wèn)頻率，在緩沖區(qū)中維護(hù)了4個(gè)LRU鏈表來(lái)存放相應(yīng)頁(yè)面，并引入新近度，來(lái)進(jìn)一步細(xì)分熱干凈和熱臟頁(yè)面的置換代價(jià)，將數(shù)據(jù)頁(yè)面繼續(xù)分成6類：冷干凈頁(yè)面、冷臟頁(yè)面、舊熱干凈頁(yè)面、非舊熱干凈頁(yè)面、舊熱臟頁(yè)面及非熱臟頁(yè)面。

(2)在冷干凈LRU鏈表頭部設(shè)置了一個(gè)靜態(tài)窗口w1，僅當(dāng)鏈表長(zhǎng)度大于其窗口值時(shí)，才優(yōu)先從中置換出冷干凈頁(yè)面，避免最近寫入緩沖區(qū)中的冷干凈頁(yè)面被快速置換出，影響緩存區(qū)命中率。

(3)在熱臟LRU鏈表尾部設(shè)置了一個(gè)動(dòng)態(tài)窗口w2，用來(lái)處理長(zhǎng)時(shí)間沒(méi)被訪問(wèn)的熱臟頁(yè)面，提高緩存區(qū)命中率。

1.2 頁(yè)面置換策略

DW-LRU算法為了更全面地分析頁(yè)面狀態(tài)，不僅考慮其冷熱臟凈屬性，還需考慮其新近度OR。一次訪問(wèn)的新近度為在最近一次讀/寫訪問(wèn)當(dāng)前頁(yè)面之后系統(tǒng)執(zhí)行的不同讀/寫訪問(wèn)操作的數(shù)量[10]。

熱臟LRU鏈表尾部動(dòng)態(tài)窗口w2的定義如式(2)、式(3)所示：

(2)

ΔOlru=Olru_i+1-Olru_i

(3)

式中：Olru_i+1為當(dāng)前熱臟LRU鏈表尾部LRU端頁(yè)面的新近度；Olru_i為上次訪問(wèn)熱臟LRU鏈表時(shí)，其LRU端頁(yè)面的新近度；ΔOlru表示當(dāng)前LRU端頁(yè)面新近度與上次的差值；Di+1為當(dāng)前熱臟LRU鏈表動(dòng)態(tài)窗口的大小，其值為占整個(gè)緩沖區(qū)的百分比；Di為上次熱臟LRU鏈表動(dòng)態(tài)窗口的大小；D初始值為Chdm，Chdm為常量，值為占整個(gè)緩存區(qū)大小的固定百分比，表示熱臟LRU鏈表的最小窗口值。

DW-LRU算法通過(guò)動(dòng)態(tài)窗口w2處理舊熱臟頁(yè)面，動(dòng)態(tài)窗口w2大小作用主要為控制從熱臟LRU鏈表移動(dòng)合適數(shù)量的舊熱臟頁(yè)面至冷臟LRU鏈表，移動(dòng)過(guò)多或過(guò)少舊熱臟頁(yè)面都會(huì)影響算法性能。處理熱臟LRU鏈表LRU端頁(yè)面時(shí)，參考其新進(jìn)度與上一次訪問(wèn)熱臟LRU鏈表時(shí)LRU端值的變化情況調(diào)整窗口w2大?。寒?dāng)ΔOlru>0時(shí)，表示熱臟LRU鏈表尾端頁(yè)面未被訪問(wèn)時(shí)間變長(zhǎng)，從側(cè)面表示當(dāng)前熱臟LRU鏈表中仍存在較多舊熱臟頁(yè)面，因此需增加窗口w2大?。划?dāng)ΔOlru<0時(shí)尾端頁(yè)面未被訪問(wèn)時(shí)間變短，從側(cè)面表示當(dāng)前熱臟LRU鏈表中舊熱臟頁(yè)面較少，因此需減少窗口w2大??；當(dāng)ΔOlru=0時(shí)，則保持窗口w2不變。

而在熱臟LRU鏈表動(dòng)態(tài)窗口w2中舊熱臟頁(yè)面的判斷方法如下：①若Opage≥CoSbuffer，則該頁(yè)面為舊熱臟頁(yè)面；②若Opage

CCC

(4)

式(4)中：COHC為舊熱干凈頁(yè)面置換代價(jià)；CNOHC為非舊熱干凈頁(yè)面置換代價(jià)；COHD為舊熱臟頁(yè)面置換代價(jià)；CNOHD為非舊熱臟頁(yè)面置換代價(jià)。

因此，DW-LRU緩沖區(qū)頁(yè)面置換策略如下。

步驟1當(dāng)緩沖區(qū)空間滿，且數(shù)據(jù)頁(yè)面在緩沖區(qū)被命中時(shí)，若該頁(yè)面為干凈頁(yè)面，同時(shí)該訪問(wèn)為寫操作時(shí)，放之至熱干凈LRU鏈表MRU端；否則，放之至熱臟LRU鏈表MRU端。

步驟2數(shù)據(jù)頁(yè)面未被緩沖區(qū)命中時(shí)，若冷干凈LRU鏈表長(zhǎng)度大于靜態(tài)窗口w1，則置換出鏈表LRU端頁(yè)面。

步驟3若步驟2中條件不符合，而熱干凈LRU鏈表的LRU端為舊熱干凈頁(yè)面，則置換出此頁(yè)面；若該頁(yè)面為非舊熱干凈頁(yè)面，且冷臟LRU鏈表長(zhǎng)度大于靜態(tài)窗口w1，則置換出冷臟LRU鏈表中LRU端頁(yè)面。

步驟4若步驟(2)、步驟(3)中條件都不符合，此時(shí)如果熱干凈LRU鏈表長(zhǎng)度大于0，則置換出熱干凈LRU鏈表的LRU端頁(yè)面。

步驟5若步驟(2)～步驟(4)的條件都不符合，則置換出熱臟LRU鏈表的LRU端頁(yè)面，同時(shí)更新動(dòng)態(tài)窗口w2的大小，并且將中的舊熱臟頁(yè)面按原順序依次放至冷臟LRU鏈表的MRU端。

2 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)基于Linux系統(tǒng)，使用Qemu軟件模擬ARM處理器，建立了嵌入式仿真平臺(tái),并對(duì)文件系統(tǒng)YAFFS2進(jìn)行了移植，而NAND閃存設(shè)備則是使用NANDsim來(lái)模擬。實(shí)驗(yàn)對(duì)象模擬的NAND閃存存儲(chǔ)容量為64 MB，而每個(gè)數(shù)據(jù)頁(yè)面存儲(chǔ)容量為2 KB，即共有32 000個(gè)數(shù)據(jù)頁(yè)面。NAND閃存主要參數(shù)特性如表1所示。

表1 NAND閃存主要參數(shù)特性

實(shí)驗(yàn)采用了3種模擬測(cè)試數(shù)據(jù)，其詳細(xì)信息如表2所示，其中“局部性”中的“80%/20%”表示80%的訪問(wèn)請(qǐng)求集中在20%的頁(yè)面上，“讀/寫比例”中“x%/y%”表示總的訪問(wèn)請(qǐng)求中讀寫操作各占x%和y%。每個(gè)測(cè)試數(shù)據(jù)集都包含100萬(wàn)條總訪問(wèn)請(qǐng)求數(shù)，分布在10 000個(gè)不同的數(shù)據(jù)頁(yè)面上。如T1測(cè)試數(shù)據(jù)集中讀請(qǐng)求占10%即105條，寫請(qǐng)求占90%即9×105條，而T1的“局部性”為“80%/20%”，即8×105條訪問(wèn)請(qǐng)求分布在2 000個(gè)不同的數(shù)據(jù)頁(yè)面上，而20萬(wàn)條訪問(wèn)請(qǐng)求分布在8 000個(gè)不同的數(shù)據(jù)頁(yè)面上。仿真實(shí)驗(yàn)中具體參數(shù)值如表3所示。

表2 模擬測(cè)試數(shù)據(jù)的詳細(xì)信息

表3 仿真實(shí)驗(yàn)參數(shù)

3 實(shí)驗(yàn)結(jié)果與分析

表4為DW-LRU算法在T1測(cè)試數(shù)據(jù)集和緩存區(qū)大小為1 MB情況下，靜態(tài)窗口w1取不同值時(shí)，緩沖區(qū)命中率、閃存寫操作次數(shù)和運(yùn)行時(shí)間情況。由表4可知，w1取值為1%時(shí)，相比取值為0時(shí)(即不使用靜態(tài)窗口w1)，雖然因?yàn)樗惴ūＡ袅瞬糠掷涓蓛繇?yè)面在緩存區(qū)的緣故，閃存寫操作次數(shù)有小幅度上升，但是緩沖區(qū)命中率明顯提升，運(yùn)行時(shí)間也明顯下降，說(shuō)明此時(shí)算法性能更佳。同時(shí)，相比其他取值，w1取值為1%時(shí)，緩沖區(qū)命中率、閃存寫操作次數(shù)、運(yùn)行時(shí)間均取到最優(yōu)值。因此，在驗(yàn)證DW-LRU算法性能時(shí)選擇參數(shù)w1為1%。

表4 DW-LRU算法取不同w1的實(shí)驗(yàn)結(jié)果

表5為DW-LRU算法在T1測(cè)試數(shù)據(jù)集和緩存區(qū)大小為1 MB情況下，取不同Co時(shí)，緩沖區(qū)命中率、閃存寫操作次數(shù)和運(yùn)行時(shí)間情況。由表5可知,Co=3時(shí)，緩沖區(qū)實(shí)現(xiàn)命中率最大值且閃存寫操作次數(shù)、運(yùn)行時(shí)間均為最小值，故選擇參數(shù)Co=3。

表5 DW-LRU算法取不同Co的實(shí)驗(yàn)結(jié)果

3.1 緩沖區(qū)命中率比較

緩沖區(qū)命中率的計(jì)算公式為

Rh=Ch/Ct

(5)

式(5)中：Ch為數(shù)據(jù)訪問(wèn)在緩沖區(qū)中命中的次數(shù)；Ct為總數(shù)據(jù)訪問(wèn)請(qǐng)求數(shù)。

圖2為DW-LRU算法和3種已有算法在不同測(cè)試數(shù)據(jù)集及T1～T3下，緩沖區(qū)命中率的比較情況。實(shí)驗(yàn)表明4種算法的命中率都隨著緩沖區(qū)大小增加而提升，而DW-LRU算法緩沖區(qū)命中率始終高于其他算法。這是由于DW-LRU算法將緩存區(qū)細(xì)分成了4個(gè)LRU鏈表并將緩沖區(qū)頁(yè)面置換代價(jià)細(xì)分為6類，對(duì)置換策略做了詳盡考慮，因此提高了命中率。對(duì)于冷干凈LRU鏈表，考慮控制其長(zhǎng)度，為其設(shè)置了一個(gè)最小窗口w1，使得最近被訪問(wèn)且剛寫入緩沖區(qū)的冷干凈頁(yè)面不會(huì)立即被置換出；同理，對(duì)于冷臟LRU鏈表，也考慮了其長(zhǎng)度問(wèn)題，當(dāng)冷臟LRU鏈表長(zhǎng)度大于冷干凈LRU鏈表時(shí)，才會(huì)考慮從冷臟LRU鏈表進(jìn)行置換。另外，DW-LRU算法引進(jìn)了新近度OR，對(duì)頁(yè)面的置換代價(jià)進(jìn)行進(jìn)一步劃分。對(duì)于冷臟LRU鏈表和熱干凈LRU鏈表，置換策略為若后者LRU端頁(yè)面為舊熱干凈頁(yè)面，則優(yōu)先置換出，否則選擇置換冷臟LRU鏈表LRU端頁(yè)面，最后選擇置換熱干凈LRU端頁(yè)面；而對(duì)于熱臟LRU鏈表，使用動(dòng)態(tài)窗口w2把鏈表中舊熱臟頁(yè)面調(diào)整至熱干凈鏈表，避免舊熱臟頁(yè)面一直存儲(chǔ)在緩沖區(qū)，影響算法命中率。

圖2 不同緩存區(qū)大小下的緩沖區(qū)命中率

實(shí)驗(yàn)結(jié)果表明，DW-LRU鏈表緩沖區(qū)命中率相較于LRU算法、LRU-WSR算法、PR-LRU算法，平均提升16.8%、12.3%、2.8%。

3.2 閃存寫操作次數(shù)比較

圖3為4種算法在3種測(cè)試數(shù)據(jù)集下的閃存寫操作次數(shù)比較情況，觀察可知DW-LRU算法的閃存寫操作次數(shù)均小于其他算法。而在T1測(cè)試數(shù)據(jù)集DW-LRU此性能優(yōu)勢(shì)最明顯，相較于LRU算法、LRU-WSR算法、PR-LRU算法，閃存寫操作次數(shù)平均降低了35.7%、28.9%、5.8%。因?yàn)镈W-LRU算法有較高的緩沖區(qū)命中率，故閃存在NAND設(shè)備上直接物理寫操作次數(shù)較少，且DW-LRU算法一般優(yōu)先選擇從緩存區(qū)中置換出干凈頁(yè)面，而盡可能保留臟頁(yè)面，并以冷熱新舊作為輔助評(píng)判標(biāo)準(zhǔn)，有效減少閃存寫操作次數(shù)。

圖3 不同緩存區(qū)大小下的閃存寫操作次數(shù)

3.3 運(yùn)行時(shí)間比較

圖4為4種算法在3種測(cè)試數(shù)據(jù)集下運(yùn)行時(shí)間比較情況，觀察可知DW-LRU算法的運(yùn)行時(shí)間均小于其他算法。這是由于DW-LRU算法在緩沖區(qū)命中率上取得較好效果，直接作用到NAND閃存設(shè)備的物理讀/寫/擦除操作次數(shù)較少，故運(yùn)行時(shí)間較短。此外，DW-LRU算法通過(guò)特定置換策略調(diào)整頁(yè)面在各鏈表的位置，執(zhí)行置換時(shí)直接從某鏈表的LRU端進(jìn)行置換，避免了反向遍歷整條鏈表，在一定程度上提高了算法運(yùn)行速率。在T3測(cè)試數(shù)據(jù)集中DW-LRU算法比LRU算法、LRU-WSR算法、PR-LRU算法，運(yùn)行時(shí)間平均降低了46.2%、29.5%、13.1%。

圖4 不同緩存區(qū)大小下的運(yùn)行時(shí)間

4 結(jié)論

提出了一種基于雙窗口的NAND閃存的緩存區(qū)管理算法，與現(xiàn)有算法做的改進(jìn)有：①在緩存區(qū)中根據(jù)訪問(wèn)頻度、冷熱特征維護(hù)了4個(gè)LRU鏈表分別存放相應(yīng)頁(yè)面,并且引入了新近度OR，將頁(yè)面進(jìn)一步細(xì)分為了6類：冷干凈頁(yè)面、冷臟頁(yè)面、舊熱干凈頁(yè)面、非舊熱干凈頁(yè)面、舊熱臟頁(yè)面、非舊熱臟頁(yè)面，通過(guò)細(xì)化置換代價(jià)提高緩沖區(qū)命中率；②通過(guò)置換策略調(diào)整頁(yè)面，直接從各鏈表LRU端置換頁(yè)面，避免反向遍歷鏈表帶來(lái)的問(wèn)題，提高了算法運(yùn)算效率；③冷干凈LRU鏈表設(shè)置了靜態(tài)窗口w1，給了冷干凈頁(yè)面一些保留在緩沖區(qū)的機(jī)會(huì)；④在熱臟LRU鏈表上設(shè)置了動(dòng)態(tài)窗口w2，讓長(zhǎng)時(shí)間沒(méi)被訪問(wèn)的舊熱臟頁(yè)面也有機(jī)會(huì)被置換出緩沖區(qū)。

實(shí)驗(yàn)證明該算法相比于LRU、LRU-WSR和PR-LRU算法，在緩沖區(qū)命中率、閃存寫操作次數(shù)和算法運(yùn)行時(shí)間等方面具有更好的性能。