于萬鈞　張海軍　劉全

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

關(guān)鍵詞： 頁面替換算法； 權(quán)重值分配； NAND閃存存儲； 受害者頁

中圖分類號： TN915?34； TP311 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

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

1 背 景

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

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

2 相關(guān)研究工作

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

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

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

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

3 EPRA頁面替換算法

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

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

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

[mCrPage] （1）

[nCw+mCrPage] （2）

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

[HD=Tc-Tr] （3）

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

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

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

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

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

4 實(shí)驗(yàn)及性能評估

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

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

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

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

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

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

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

5 結(jié) 語

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

參考文獻(xiàn)

[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] 林子雨，賴明星，鄒權(quán)，等.基于替換概率的閃存數(shù)據(jù)庫緩沖區(qū)替換算法[J].計(jì)算機(jī)學(xué)報(bào)，2013（8）：1568?1581.

[6] 陳金忠，姚念民，蔡邵濱.基于NAND閃存的高性能和可靠的PRAID?6[J].電子學(xué)報(bào)，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)代電子技術(shù)，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