徐之光，嚴 華

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

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

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

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

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

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

1 算法的實現(xiàn)

1.1 基本原理

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

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

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

CCC

(1)

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

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

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

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

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

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

(3)在熱臟LRU鏈表尾部設(shè)置了一個動態(tài)窗口w2，用來處理長時間沒被訪問的熱臟頁面，提高緩存區(qū)命中率。

1.2 頁面置換策略

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

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

(2)

ΔOlru=Olru_i+1-Olru_i

(3)

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

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

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

CCC

(4)

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

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

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

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

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

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

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

2 實驗環(huán)境

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

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

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

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

表3 仿真實驗參數(shù)

3 實驗結(jié)果與分析

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

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

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

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

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

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

Rh=Ch/Ct

(5)

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

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

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

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

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

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

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

3.3 運行時間比較

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

圖4 不同緩存區(qū)大小下的運行時間

4 結(jié)論

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

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