一種基于NAND閃存高效的頁面替換算法

于萬鈞　張海軍　劉全

摘 要： 針對不同NAND閃存讀寫操作成本比例的不同，提出一種具有高效頁面替換功能的EPRA算法。在內存中，每個受害者候選頁被分成固定數(shù)量的閃存頁面。 EPRA給每個受害者候選頁分配權重值，在選擇與修改頁面時對權重進行調節(jié)，從候選頁中選擇具有最小權重值的頁面作為受害者頁。EPRA 算法把受害者頁中分為熱的閃存頁和冷的閃存頁，并把這些數(shù)據(jù)寫到 NAND 閃存中不同空閑的塊中。仿真實驗結果表明，EPRA算法使用在不同種類的NAND閃存中時，性能優(yōu)于現(xiàn)有的頁面替換算法。

關鍵詞： 頁面替換算法； 權重值分配； NAND閃存存儲； 受害者頁

中圖分類號： TN915?34； TP311 文獻標識碼： A 文章編號： 1004?373X（2017）16?0053?04

Abstract： In allusion to different cost ratios of read?write operation for different NAND flash memories， an EPRA algorithm with efficient page replacement function is proposed in this paper. Each victim candidate page in the internal storage is divided into a fixed number of flash pages. EPRA assigns a weighted value to each victim candidate page， and adjusts the weighted values in the process of page selection and modification. The page with least weighted value is selected in the candidate page as a victim page. EPRA divides the dirty flash pages into the hot dirty flash memory pages and cold ones， and writes the data in the different blocks in NAND flash memory. The trace?driven simulation resultes show that the EPRA algorithm is superior to the existing page replacement algorithms when it is used in different kinds of NAND flash memories.

Keywords： page replacement algorithm； weighted value allocation； NAND flash memory； victim page

0 引 言

近年來，閃存成為消費電子產(chǎn)品一種最重要的存儲設備。閃存有許多誘人的特點，例如體積小、速度快、可抗震、高可靠性、重量輕、低功耗等。單個的NAND閃存芯片存儲容量正在增加，且其價格不斷下降。因此，越來越多的消費電子產(chǎn)品使用閃存取代磁盤[1]。

由于電子產(chǎn)品中主存儲器空間有限，所以操作系統(tǒng)中應該包含頁面替換算法，當空閑頁的數(shù)量不足時，該算法能夠獲得空閑的頁面。在假設磁盤I/O操作成本相等的情況下，人們研究了如何使磁盤頁面命中率最大化的頁面替換算法[2?4]。NAND閃存存在I/O操作成本不同和先擦后寫的硬件約束，因此，傳統(tǒng)的頁面替換算法不適用于NAND閃存設備，有必要提出一種新的基于NAND閃存設備特點的頁面替換算法。許多NAND頁面替換算法假設寫操作的成本遠遠高于讀操作成本，優(yōu)先驅除干凈頁，并非所有類型的NAND閃存都是這樣的。表1為4種不同的NAND 閃存類型的寫操作和讀操作之間成本比例。因此，以優(yōu)先驅逐干凈頁的頁面替換算法不適用于不同種類的NAND閃存[5?6]。

表1 不同種類的NAND閃存寫操作和讀操作的成本比例 %

1 背 景

目前主要有兩種閃存存儲器，NOR閃存和NAND閃存[7]。兩者都是用于計算機和消費電子產(chǎn)品的非易失性存儲介質。閃存是基于E2PROM的設計原則發(fā)明的，可擦除和重復編程。NOR閃存有兩個突出的特點，快速存取和片內執(zhí)行（XIP），因此它經(jīng)常被用來代替ROM和執(zhí)行時應用程序代碼。

每個NAND閃存是由若干個塊組成，每個塊分成固定數(shù)量的頁。每個塊和頁面的大小通常分別為16 KB和512 B。每一頁有一個備用區(qū)，備用區(qū)的典型大小是16 B，這一般用來存儲讀操作和寫操作過程中發(fā)生錯誤的校驗碼。NAND閃存有三種類型的操作：讀取、寫入及擦除操作。讀、寫操作的基本單元是一個頁面，而擦除操作的基本單元是一個塊。NAND閃存先擦除后寫，且讀操作和寫操作成本不一樣，為了解決NAND閃存中讀操作和寫操作成本不對稱的問題，現(xiàn)有的許多頁面替換算法都是在假設讀操作成本遠高于寫操作成本的情況下做研究的，優(yōu)先驅逐干凈頁。

2 相關研究工作

LRU是經(jīng)典的頁面替換算法，在現(xiàn)有的系統(tǒng)中，基本上都是采用LRU算法或者類LRU算法[8]。在研究LRU算法的基礎上，大量的用于NAND閃存的頁面替換算法出現(xiàn)了。Park等人提出了一種高效頁面替換算法（CFLRU）[9?10]。 CFLU算法將LRU邏輯鏈表分為工作區(qū)和替換區(qū)。在進行頁面替換時，優(yōu)先替換其中的干凈頁面，該策略將臟頁面保留在替換區(qū)域中，延遲臟頁面寫的時間。當替換區(qū)域沒有干凈頁面的時候，CFLRU將按照LRU順序處理其余的頁面。endprint

Jung等人提出了LRU?WSR算法[11]。LRU?WSR算法為每個鏈表添加一個冷標識位，冷標識位為0表明該頁是熱頁，冷標識位為1表明該頁是冷頁。LRU?WSR算法將熱區(qū)中的數(shù)據(jù)頁轉移到冷區(qū)時，判斷熱區(qū)中LRU位置的數(shù)據(jù)頁屬性，如果是冷標識位為1的臟頁或者是干凈頁，將該頁轉移到冷區(qū)的MRU位置；如果是冷標識位為0的臟頁，將該頁冷標識位置為1，移到熱區(qū)的MRU位置，重復上述判斷。LRU?WSR算法考慮了臟頁的冷熱屬性，但是卻忽略了干凈頁的冷熱屬性。

Li等人提出了CCF?LRU算法[12]。CCF?LRU算法將緩沖區(qū)分為兩個LRU鏈表，即L1和L2，L1用于存放熱干凈頁和臟頁，L2用于存放冷干凈頁。CCF?LRU算法優(yōu)先替換L2中的頁面，當L2鏈表為空時，將在L1中使用LRU?WSR算法選擇頁面。CCF?LRU算法將緩沖區(qū)分為兩列，減少一次操作對緩沖區(qū)的污染，在訪問局部性數(shù)據(jù)時效率很高，但是該算法無法控制L2鏈表的長度，在某些情況下，會降低頁面命中率。

現(xiàn)有頁面替換算法沒有考慮到不同NAND閃存的寫入和讀開銷比例是不同的，因而不能很好地用于各類NAND閃存，所以有必要設計一種適用于各種NAND閃存的高效的頁面替換算法。

3 EPRA頁面替換算法

本節(jié)提出一種高效的EPRA（Efficient Page Replacement Algorithm）算法，適用于不同種類的讀寫成本比例不同的NAND閃存。如圖1所示，EPRA維持兩個頁鏈表，即干凈頁鏈表和臟頁鏈表。

內存中的臟頁面通常包含部分干凈的數(shù)據(jù)[13?14]。典型內存頁和閃存頁的大小分別為4 KB和512 B，因此，將受害者臟頁寫回到NAND設備中需要8次寫操作，包括將干凈數(shù)據(jù)寫回到NAND閃存中的冗余操作。為了識別臟頁內的干凈數(shù)據(jù)，避免多余的寫操作，EPRA算法將臟頁鏈表中每一頁分成8份，臟頁中的閃存頁都設置一個臟標志位。內存中的閃存頁在NAND設備中都有一個副本，如果內容不同，將臟標志位設置為1，如果相同，標志位不變，該頁視為干凈的閃存頁。

EPRA算法給干凈頁鏈表和臟頁鏈表中每一頁加上一個權重值。干凈頁鏈表中的權重值為式（1），而臟頁鏈表中的權重值為式（2）：

[mCrPage] （1）

[nCw+mCrPage] （2）

式中：m是頁面P擁有總的閃存頁數(shù)目；Cr是讀操作成本；Page是頁上次引用的時間；n是頁面P擁有的臟的閃存頁數(shù)目；Cw是寫操作成本。干凈頁鏈表和臟頁鏈表中的頁面從左到右是以權重值升序排列的，EPRA算法比較干凈頁鏈表中最左邊頁的權重值和臟頁鏈表中的最左邊頁的權重值，選擇權重值較小的一頁作為受害者頁。將熱的臟頁和冷的臟頁寫到NAND閃存中同一個空閑塊時，由于熱的閃存頁和冷的閃存頁無效的時間不同，垃圾回收的過程中寫操作造成很大的開銷。為了區(qū)分臟頁鏈表中的臟頁，記錄臟頁鏈表中每個臟頁的最近引用時間。當選擇了一個臟受害者頁時，EPRA使用HD來記錄這個熱度值，臟頁的HD值計算方式為：

[HD=Tc-Tr] （3）

式中，Tc和Tr分別是當前時間和臟閃存頁的最近引用時間。因此，HD值等于其引用經(jīng)過的總時間。

為了避免HD值太大而使精度受到影響，使HD值大小范圍為0～1，公式為式（4）：

[NHD=HD-mini∈n（HDi）maxi∈n（HDi）-mini∈n（HDi）] （4）

式中：NHD是標準化后的HD值；n是受害者頁中臟閃存頁的數(shù)目；HDi是第i個臟閃存頁的HD值。如果臟閃存頁的NHD值小于或者等于受害者頁中所有臟閃存頁的NHD平均值，那么該臟閃存頁是熱臟閃存頁，相反，這個閃存頁將被認為是冷臟閃存頁。

當選擇一個受害者頁面后，EPRA算法檢查該受害者是否是干凈的。如果受害者頁是干凈的，擦除受害者頁，釋放相應的頁存儲空間。如果受害者頁面是從臟頁鏈表中選擇的，只讀取臟受害者頁中的臟閃存頁。如圖2所示，為了減少垃圾回收操作時的性能開銷，EPRA算法利用HD值區(qū)分出熱的臟閃存頁和冷的臟閃存頁，并把它們寫回到NAND設備中不同的空閑塊中。

4 實驗及性能評估

在本節(jié)中，將EPRA和現(xiàn)有的LRU，CFLRU，LRU?WSR，CCF?LRU算法進行比較。本實驗使用K1和K2表示兩種不同的應用類型，如表2所示，K1是寫密集型應用，而K2是讀密集型應用。

表2 測試數(shù)據(jù)的統(tǒng)計信息

本實驗使用兩種讀寫操作成本比例不同的NAND設備進行實驗，分別稱為T1和T2。T1的寫操作成本和讀操作成本比例是120∶1，T2的寫操作成本和讀操作成本的比例是2∶1。DFTL[15]閃存轉換層將這兩種NAND閃存設備模擬為塊設備，使用貪婪垃圾回收算法來回收垃圾。DFTL被設成當NAND設備中空閑塊的比例低于5%時自動進行垃圾回收過程，當空閑塊的比例高于15%時自動停止垃圾回收過程。

性能指標主要是頁面命中率，讀操作的次數(shù)，拷貝操作的次數(shù)，運行時間。圖3為使用不同算法測試T1和T2兩種NAND設備頁面命中率的實驗結果，因為EPRA算法在選擇一個受害者頁時，將每個受害者頁的上一次的引用時間考慮在內，所以EPRA算法頁面命中率最高。

圖4為使用不同算法寫操作的實驗結果，EPRA算法將每個臟受害者頁分成一定數(shù)量的頁面，使頁面大小和NAND閃存頁大小相同，僅僅把臟受害者中的臟閃存頁寫回到NAND閃存中，所以EPRA算法使NAND設備的寫操作次數(shù)最少。

圖5為在T1和T2兩種NAND設備上兩種不同應用類型的拷貝操作次數(shù)的情況分布。EPRA算法考慮到了臟受害者頁中每個臟閃存頁的HD值，把臟受害者頁中的熱臟閃存頁和冷臟閃存頁分別寫到NAND設備不同的空閑塊中，沒有把臟受害者頁中的干凈頁寫到NAND設備中，而其他的頁面替換算法將臟受害者頁中的數(shù)據(jù)全部寫回到NAND設備中。從圖5可以看出，EPRA算法在垃圾回收的過程中，拷貝操作次數(shù)最少。endprint

圖6為T1和T2兩種NAND設備上使用不同算法的運行時間的結果分布。如圖6所示，因為EPRA算法有著最高的頁面命中率和最少的寫操作次數(shù)，所以運行時間也就最短。CFLRU，LRU?WSR和CCF?LRU算法在假設NAND寫操作的成本遠高于讀操作的成本下優(yōu)先驅逐干凈頁，這些算法在T1設備上性能很好，但是在T2這個寫操作和讀操作成本比例很低的設備上，效果很差。EPRA算法把I/O操作成本和每頁上次的引用時間考慮在內，給每頁分配一個權重值，因此，EPRA算法在T1和T2兩種NAND設備上性能都很好。

5 結 語

本文提出了一種高效的頁面替換算法——EPRA算法。該算法在各種類型的NAND閃存上都具有很好的性能。EPRA算法維持兩個鏈表，一個是干凈頁鏈表，另一個是臟頁鏈表。EPRA算法假設內存頁和閃存頁大小為4 KB和512 B，將內存頁分成8份。EPRA算法給兩個頁鏈表中的每頁都分配一個權重值，選擇權重值最小的頁作為受害者頁。如果是從臟頁鏈表中選出了受害者頁，從臟受害者中的臟閃存頁區(qū)分出熱臟閃存頁和冷臟閃存頁，分別將熱臟閃存頁和冷臟閃存頁寫回到NAND閃存不同的塊中。實驗結果表明，EPRA算法適用各種NAND閃存，且在頁面命中率方面，讀寫操作次數(shù)和拷貝操作次數(shù)與運行時間方面性能比現(xiàn)有的算法性能優(yōu)越。

參考文獻

[1] WEI Yuanting， SHIN Dongkun. NAND flash storage device performance in Linux file system [C]// Proceedings of the 6th International Conference on Computer Sciences and Convergence Information Technology. [S.l.： s.n.]， 2011： 574?577.

[2] O′NEIL E J， O′NEIL P E， WEIKUM G. The LRU?K page replacement algorithm for database disk buffering [C]// Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. [S.l.： s.n.]， 1993： 297?306.

[3] JIANG S， ZHANG X D. LIRS： an efficient low inter?reference recency set replacement policy to improve buffer cache performance [C]// Proceedings of ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems. [S.l.： s.n.]， 2002： 31?42.

[4] Johnson Theodore， SHASHA Dennis. 2Q： a low overhead high performance buffer management replacement algorithm [C]// Proceedings of the 20th international Conference on Very Large Databases. [S.l.： s.n.]， 1994： 439? 450.

[5] 林子雨，賴明星，鄒權，等.基于替換概率的閃存數(shù)據(jù)庫緩沖區(qū)替換算法[J].計算機學報，2013（8）：1568?1581.

[6] 陳金忠，姚念民，蔡邵濱.基于NAND閃存的高性能和可靠的PRAID?6[J].電子學報，2015（6）：1211?1217.

[7] BEZ Roberto， CAMERLENGHI Emilio， MODELLI Alberto， et al. Introduction to flash memory [J]. Proceedings of the IEEE， 2003（91）：489?501.

[8] 李芳，徐麗，陳亮亮.LRU近似算法的研究[J].現(xiàn)代電子技術，2009，32（10）：36?38.

[9] PARK Chanik， KANG Jeong?Uk， PARK Seon?Yeong， et al. Energy?aware demand paging on NAND flash?based embedded storages [C]// Proceedings of the 2004 International Symposium on Low Power Electronics and Design. [S.l.： s.n.]， 2004： 338?343.

[10] PARK S Y， JUNG D. CFLRU： A replacement algorithm for flash memory [C]// Proceedings of the 2006 International Conference on Compilers， Architecture and Synthesis for embedded systems. [S.l.： s.n.]， 2006： 234? 241.

[11] JUNG H， SHIM H， PARK S， et al. LRU?WSR： integration of LRU and writes sequence reordering for flash memory [J]. IEEE transactions on consumer electronics， 2008（54）： 1215?1223.

[12] LI Z， JIN P， SU X， et al. CCF?LRU： a new buffer replacement algorithm for flash memory [J]. IEEE transactions on consumer electronics， 2009（55）： 1351?1359.

[13] LI Hanlin， YANG Chialin， TSENG H W. Energy?aware flash memory management in virtual memory system [J]. IEEE transactions on very large scale integration systems， 2008， 16（8）： 952?964.

[14] LIN Mingwei， CHEN Shuyu， WANG Guiping. Greedy page replacement algorithm for flash?aware swap system [J]. IEEE transactions on consumer electronics， 2012（58）： 435?440.

[15] GUPTA Aayush， KIM Youngjae， URGAONKAR Bhuvan. DFTL： a flash translation layer employing demand?based selective caching of pagelevel address mappings [J]. ACM SIGPLAN notices， 2009（44）： 229?240.endprint