子頁感知的閃存頁面置換算法

劉君玲

（福建信息職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系，福建福州 350003）

子頁感知的閃存頁面置換算法

劉君玲

（福建信息職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系，福建福州 350003）

根據(jù)閃存的獨(dú)特物理特性，提出了子頁感知的閃存頁面置換算法.該算法引入了子頁技術(shù)和基于相似概率的部分更新機(jī)制，既可以提高閃存存儲系統(tǒng)的性能，又可計(jì)算每個(gè)內(nèi)存頁的置換值，并選擇了置換值最小的內(nèi)存頁為犧牲頁.實(shí)驗(yàn)結(jié)果表明，新算法在頁面命中率、讀／寫操作次數(shù)、運(yùn)行時(shí)間方面均具有優(yōu)勢.

閃存；頁面置換算法；子頁技術(shù)；企業(yè)；存儲；最近最少使用算法

0 引言

由于閃存具備訪問速度快、質(zhì)量輕、抗震性強(qiáng)以及能耗低等優(yōu)點(diǎn)，閃存已經(jīng)成為智能手機(jī)和嵌入式系統(tǒng)的重要存儲介質(zhì)［1］.隨著閃存技術(shù)的不斷發(fā)展和成熟，閃存的容量不斷增大且價(jià)格不斷降低，使得閃存成為代替?zhèn)鹘y(tǒng)機(jī)械硬盤的重要存儲介質(zhì)之一［2］.國內(nèi)的華為、奇虎以及阿里巴巴等大型科技公司已經(jīng)開始采用閃存代替部分傳統(tǒng)機(jī)械硬盤，以提升企業(yè)存儲系統(tǒng)的性能.操作系統(tǒng)中現(xiàn)有的頁面置換算法是針對傳統(tǒng)機(jī)械硬盤的機(jī)械特性進(jìn)行優(yōu)化和設(shè)計(jì)的［3］.然而，閃存表現(xiàn)出與傳統(tǒng)機(jī)械硬盤完全不同的物理特性.例如，閃存的讀寫操作性能是不一致的，其寫操作延遲遠(yuǎn)高于讀操作延遲［4］.如果將現(xiàn)有的頁面置換算法直接應(yīng)用于閃存存儲設(shè)備，勢必會造成閃存存儲系統(tǒng)的能耗居高不下.

最近最少使用算法（LRU）是大部分現(xiàn)代操作系統(tǒng)為最大化頁面命中率而廣泛采用的一種頁面置換算法［5］.為了減少寫操作數(shù)量，文獻(xiàn)［6］提出了第一個(gè)適用于閃存存儲設(shè)備的頁面置換算法——CFLRU.該算法改進(jìn)了原有的LRU算法，在LRU頁面將隊(duì)列分成干凈頁優(yōu)先區(qū)域和工作區(qū)域兩部分.干凈頁優(yōu)先區(qū)域包含將來最有可能被置換出去的最近最少使用頁面.工作區(qū)域包含最近最常使用頁面，所以大部分的緩存命中情況發(fā)生在該區(qū)域內(nèi).CFLRU算法優(yōu)先置換干凈頁優(yōu)先區(qū)域內(nèi)的干凈頁，當(dāng)干凈頁優(yōu)先區(qū)域內(nèi)沒有干凈頁時(shí)，CFLRU算法按LRU順序置換出剩余的臟頁.

文獻(xiàn)［7］引入寫順序重新排序策略對原有的LRU算法進(jìn)行擴(kuò)展，提出了一種新的頁面置換算法LRU-WSR.LRU-WSR按照LRU順序?qū)RU頁面隊(duì)列中的頁面進(jìn)行掃描并檢查.如果該最近最少使用頁面是干凈頁，不管該頁面是否是熱頁面，LRU-WSR算法將該干凈頁回收相應(yīng)的頁框；如果該最近最少使用頁面是熱臟頁，LRU-WSR算法將其設(shè)置為冷臟頁，并將其插入LRU隊(duì)列中MRU端；如果該最近最少使用頁面是冷臟頁，LRU-WSR算法將該頁寫回閃存存儲設(shè)備并回收相應(yīng)的頁框.

文獻(xiàn)［8］針對閃存讀寫操作成本不對稱的特點(diǎn)，提出了一種基于概率的頁面置換算法APBLRU.該算法根據(jù)數(shù)據(jù)訪問頻度，將緩沖區(qū)分為冷區(qū)和熱區(qū)兩部分，APB-LRU以較高的概率置換出冷區(qū)的干凈數(shù)據(jù)頁，以較低的概率置換出熱區(qū)的臟數(shù)據(jù)頁.

文獻(xiàn)［9］提出了一種新的閃存頁面置換算法PT-LRU，該算法維護(hù)三條主要列表：冷干凈LRU列表、冷臟LRU列表以及混合LRU列表.PT-LRU優(yōu)先從冷干凈LRU列表中置換出LRU頁，如果冷干凈LRU列表為空，PT-LRU則以較高的概率置換出冷臟LRU列表中的頁，以較低的概率置換出熱干凈頁.

通過分析，作者發(fā)現(xiàn)現(xiàn)有的閃存頁面置換算法通過優(yōu)先置換出干凈頁的策略，可以有效地減少寫操作次數(shù)，從而達(dá)到降低閃存存儲系統(tǒng)能耗的目的.但內(nèi)存中的臟數(shù)據(jù)頁通常含有大量的干凈數(shù)據(jù)，置換出這類臟數(shù)據(jù)頁會引發(fā)大量的冗余寫操作.為了減少冗余寫操作次數(shù)并保持較高的頁面命中率，本文試提出一種子頁感知的閃存頁面置換算法.

1 子頁感知的閃存頁面置換算法

1.1 子頁技術(shù)

在操作系統(tǒng)中，為了保持?jǐn)?shù)據(jù)一致性，當(dāng)頁面置換算法選擇的犧牲頁為臟頁時(shí)，頁面置換算法先要把臟頁寫回存儲系統(tǒng)中，最后才回收對應(yīng)的頁框.現(xiàn)代操作系統(tǒng)中頁的大小普遍為4 KB，而閃存中頁的大小為512 B，也就是說寫回一個(gè)臟頁會觸發(fā)8個(gè)寫操作.

為此，本研究在Linux操作系統(tǒng)上獨(dú)立運(yùn)行6個(gè)常見的應(yīng)用程序，分別是Apache OpenOfficeWriter，Apache OpenOffice Calc，F(xiàn)irefox，Viewnior，Xmms以及Foxit Reader.通過測試發(fā)現(xiàn)，內(nèi)存中的臟頁通常含有大量的未修改數(shù)據(jù)，即干凈數(shù)據(jù).定義內(nèi)存頁平均臟度為內(nèi)存頁中已修改數(shù)據(jù)的數(shù)量與內(nèi)存頁總的存儲容量比率.

從表1可以看出，只有Viewnior的臟度相對較高，F(xiàn)irefox和Xmms的臟度低于50%，說明這兩種軟件運(yùn)行時(shí)內(nèi)存頁中含有大量的干凈數(shù)據(jù).

表1 不同工作負(fù)載下臟內(nèi)存頁的平均臟度Tab.1 The average d irty deg ree of the dirty main memo ry page in each workload

如圖1所示，為了識別內(nèi)存頁中的干凈數(shù)據(jù)，本研究采用網(wǎng)絡(luò)系統(tǒng)中常用的子頁技術(shù)（Subpaging Technique）將臟內(nèi)存頁劃分成一定數(shù)量的子頁，子頁的大小跟閃存的大小一致［10］.本文假定操作系統(tǒng)的頁大小為4 KB，而閃存的頁大小為512 B，所以每個(gè)臟內(nèi)存頁可以劃分成8個(gè)子頁.每個(gè)子頁都要關(guān)聯(lián)一個(gè)臟位，如果子頁包含已修改數(shù)據(jù)，說明該子頁為臟子頁，其臟位可設(shè)置為1.如果子頁內(nèi)的數(shù)據(jù)都是未修改數(shù)據(jù)，說明該子頁為干凈子頁，其臟位值為0.

圖1子頁技術(shù)Fig.1 Subpaging technology

1.2 算法設(shè)計(jì)

如圖2所示，子頁感知的閃存頁面置換算法維護(hù)兩條LRU頁面隊(duì)列，分別是干凈頁面隊(duì)列和臟頁面隊(duì)列.該算法為每一個(gè)內(nèi)存頁分配一個(gè)置換值，當(dāng)內(nèi)存中空閑頁框不足時(shí)，頁面置換算法選擇置換值最小的內(nèi)存頁.為了減少寫操作數(shù)量，同時(shí)保持較高的頁面命中率，該置換值（Rep lacing value）R（p）定義為：

該

置換值的定義考慮了內(nèi)存頁的熱度和置換成本兩個(gè)因素，這兩個(gè)因素通過加權(quán)系數(shù)λ加權(quán)得到頁面的置換索引值．這兩個(gè)因素的比重與加權(quán)系數(shù)λ相關(guān)，會隨著加權(quán)系數(shù)λ的變化而變化.

為了避免過度優(yōu)先置換出置換成本低的頁（包括干凈頁）而影響命中率，所以加權(quán)系數(shù)λ定義成一個(gè)隨δ增大而減小的單調(diào)遞減函數(shù)：λ＝2／（1＋eδ／8），其中：δ＝Cw／Cr且δ≥2，Cw代表寫操作成本，Cr代表讀操作成本，因此δ代表寫操作成本與讀操作成本的比率.從圖3可以看出，加權(quán)系數(shù)λ隨著δ的增大而減小.當(dāng)2≤δ＜8時(shí)，λ＞0．5，內(nèi)存頁的熱度成為影響犧牲頁選擇的重要因素.當(dāng)δ＝8時(shí)，λ≈0．5，選擇犧牲頁的時(shí)候需要同時(shí)考慮這兩個(gè)因素.當(dāng)δ＞8時(shí)，λ＜0．5，內(nèi)存頁的置換成本成為影響犧牲頁選擇的重要因素.當(dāng)δ趨向于無限大時(shí)，T近似等于1，干凈頁可以被優(yōu)先置換出去，而不影響算法的整體性能.

因?yàn)楦蓛魞?nèi)存頁不含有臟數(shù)據(jù)，所以根據(jù)置換值定義可以得到干凈內(nèi)存頁的置換成本為0，也就是說干凈頁隊(duì)列上每個(gè)內(nèi)存頁的置換索引值等于其熱度.因此，干凈頁隊(duì)列上的內(nèi)存頁按照其熱度值從左至右遞增排列，而臟頁隊(duì)列上的內(nèi)存頁按照其置換索引值從左至右遞增排列.

圖2子頁感知的閃存頁面置換算法Fig.2 Subpaging aware flashm emory page rep lacem entalgorithm

圖3函數(shù)曲線圖Fig.3 Function curve graph

1.3 基于相似概率的部分更新機(jī)制

為了進(jìn)一步減少寫操作次數(shù)和降低垃圾回收額外開銷，本文引入基于相似概率的部分更新機(jī)制.首先，計(jì)算子頁寫回閃存存儲器后變成不正確頁（Invalid Page）的概率：1）假定閃存存儲器由T個(gè)物理塊組成，每個(gè)塊包含Np個(gè)頁，閃存存儲器中臟頁的數(shù)量為Nd；2）假設(shè)從上次子頁寫操作結(jié)束到當(dāng)前的時(shí)間間隔，共產(chǎn)生了K次用戶寫操作；3）那么子頁被更新的概率，即變成不正確頁的概率為8／（T×Np-Nd）.然后，將具有相似概率的子頁聚類到同一個(gè)簇：1）設(shè)定一個(gè)概率閾值Pt；2）如果兩個(gè)子頁的概率差小于等于概率閾值Pt，那么這兩個(gè)子頁就具有相似概率；3）將具有相似概率的子頁聚類到同一個(gè)簇，直到簇的大小為8.最后，將大小為8的簇內(nèi)子頁寫回閃存存儲器.

2 實(shí)驗(yàn)分析

實(shí)驗(yàn)的硬件環(huán)境是Intel Core i5-4200 3.5GHz CPU和4GB DDR3內(nèi)存，實(shí)驗(yàn)的運(yùn)行環(huán)境為Windows XP操作系統(tǒng).本文的實(shí)驗(yàn)采用中國科技大學(xué)開發(fā)的Flash-DBSim［11］閃存仿真軟件模擬閃存存儲系統(tǒng).Flash-DBSim是一個(gè)可配置的閃存仿真平臺，可以根據(jù)上層應(yīng)用程序的需要模擬出不同特性的閃存存儲系統(tǒng)，現(xiàn)有的很多研究都采用了Flash-DBSim進(jìn)行算法性能的測試實(shí)驗(yàn).

本文采用Flash-DBSim閃存仿真軟件模擬一個(gè)存儲大小為256 MB的NAND閃存存儲系統(tǒng)，該系統(tǒng)的每個(gè)數(shù)據(jù)塊包含64個(gè)數(shù)據(jù)頁，且每個(gè)數(shù)據(jù)頁大小為2KB.

本文采用真實(shí)軌跡進(jìn)行軌跡驅(qū)動模擬實(shí)驗(yàn)，將本文提出的子頁感知的閃存頁面置換算法（SPF）與現(xiàn)有的CFLRU、LRU-WSR、APB-LRU和PT-LRU算法進(jìn)行性能對比.實(shí)驗(yàn)過程中采用的真實(shí)軌跡是通過磁盤驅(qū)動數(shù)據(jù)跟蹤器DiskMon收集訪問磁盤的I／O數(shù)據(jù)請求.

模擬實(shí)驗(yàn)采用的性能評價(jià)指標(biāo)為頁面命中率、寫操作次數(shù)、讀操作次數(shù)以及運(yùn)行時(shí)間.頁面命中率為從緩存中讀取數(shù)據(jù)的次數(shù)與所有訪問數(shù)據(jù)次數(shù)之比；寫操作次數(shù)定義為閃存存儲系統(tǒng)向閃存寫入數(shù)據(jù)的次數(shù)；讀操作次數(shù)定義為閃存存儲系統(tǒng)從閃存讀取數(shù)據(jù)的次數(shù)；運(yùn)行時(shí)間定義為物理讀操作時(shí)間、物理寫操作時(shí)間和閃存中擦除操作的時(shí)間和.

從圖4顯示的實(shí)驗(yàn)結(jié)果可以看到，本文提出的子頁感知的閃存頁面置換算法的頁面命中率高于現(xiàn)有的閃存頁面置換算法.這是因?yàn)楸疚乃惴ㄔ谶x擇犧牲頁的時(shí)候考慮了每個(gè)內(nèi)存頁的熱度，防止經(jīng)常訪問的內(nèi)存頁被置換出去，可以有效地提高頁面命中率.

圖5顯示的實(shí)驗(yàn)結(jié)果表明，本文提出的子頁感知的閃存頁面置換算法的寫操作次數(shù)低于現(xiàn)有的閃存頁面置換算法，這是因?yàn)楸疚乃惴ㄔ谶x擇犧牲頁的時(shí)候考慮了每個(gè)內(nèi)存頁的置換成本，且只將犧牲頁中的臟子頁寫回閃存存儲設(shè)備.

圖4頁面命中率Fig.4 Page hit ra tio

圖5寫操作次數(shù)Fig.5 The number ofw rite operations

圖6顯示的實(shí)驗(yàn)結(jié)果表明，本文提出的子頁感知的閃存頁面置換算法的讀操作次數(shù)少于現(xiàn)有的閃存頁面置換算法，這是因?yàn)楸疚乃惴ǖ捻撁婷新首罡?

圖7顯示的實(shí)驗(yàn)結(jié)果表明，本文提出的子頁感知的閃存頁面置換算法的運(yùn)行時(shí)間低于現(xiàn)有的閃存頁面置換算法.頁面置換算法的運(yùn)行時(shí)間與其頁面命中率和讀操作次數(shù)有關(guān).頁面命中率越高，其運(yùn)行時(shí)間越低；讀操作次數(shù)越少，其運(yùn)行時(shí)間越低.

圖6讀操作次數(shù)Fig.6 The number of read opera tions

圖7運(yùn)行時(shí)間Fig.7 Runtime

3 結(jié)論

本文針對閃存的物理特性，提出了子頁感知的閃存頁面置換算法.先是引入子頁技術(shù)將每個(gè)臟內(nèi)存頁劃分成8個(gè)大小相同的子頁，接著結(jié)合內(nèi)存頁的置換成本和熱度計(jì)算出每個(gè)內(nèi)存頁的置換值，然后選擇置換值最小的內(nèi)存頁作為犧牲頁，最后引入基于相似概率的部分更新機(jī)制將具有相似概率的子頁聚類到同一個(gè)簇并將該簇內(nèi)的子頁寫回閃存存儲器.實(shí)驗(yàn)結(jié)果表明，本文提出的子頁感知的閃存頁面置換算法的性能高于現(xiàn)有的閃存頁面置換算法.

［1］WEIY T，SHIN D K.NAND flash storage device performance in Linux file system［C］／／Proceedings of the 6th International Conference on Computer Sciences and Convergence Information Technology，Washington：IEEE Computer Society，2011：574-577.

［2］NO JAECHUN.Hybrid file system using NAND-flash SSD［C］／／Proceedings of2011 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery，Piscataway，USA：IEEE Computer Society，2011：380-385.

［3］ASIT DAN，DON TOWSLEY.Approximate analysis of the LRU and FIFO buffer replacement schemes［C］／／Proceedings of the 1990 ACM Sigmetrics Conference on Measurementand Modeling of Computer Systems，New York：Association for Computing Machinery，1990：143-152.

［4］CHANIK PARK，JEONG-UK KANG，SEON-YEONG PARK，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，New-Port Beeth，USA：Association for Computing Machinery，2004：338-343.

［5］ELIZABETH JO'NEIL，PATRICK E O'NEIL，GERHARDWEIKUM.The LRU-K page replacement algorithm for database disk buffering［C］／／Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data，F(xiàn)ort Collins，USA：Association for Computing Machinery，1993：297-306.

［6］SEON-YEONG DAWOON JUNG，JEONG-UK KANG，JIN-SOO KIM，et al.CFLRU：a replacement algorithm for flash memory［C］／／Proceedings of the 2006 International Conference on Compliers，Architecture and Synthesis for Embedded Systems，New York：Association for Computing Machinery，2006：234-241.

［7］HOYOUNG JUNG，HYOKISHIM，SUNGMIN PARK，et al.LRU-WSR：Integration of LRU and writes sequence reordering for flash memory［J］.IEEE Transactions on Consumer Electronics，2008，54（3）：1215-1223.

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

［9］CUI JH，WUW G，WANG Y F，et al.PT-LRU：A probabilistic page replacement algorithm for NAND flash-based consumer electronics［J］.IEEE Transactions on Consumer Electronics，2014，60（4）：614-622.

［10］LIH L，YANG C L，TSENG H W.Energy-aware flash memory management in virtualmemory system［J］.IEEE Transactions on Very Large Scale Integration Systems，2008，16（8）：952-964.

［11］SU X，JIN P Q，XIANG X Y，et al.Flash-DBSim：A simulation tool for evaluating flash-based database algorithms［C］／／2009 2nd IEEE International Conference on Computer Science and Information Technology，Piscataway，USA：IEEE Computer Society，2009：185-189.

（責(zé)任編輯 朱雪蓮 英文審校 黃振坤）

Subpaging Aware Page Replacement Algorithm for Flash M emory

LIU Jun-ling
（Fujian Polytechnic of Information Technology，F(xiàn)uzhou 350013，China）

Due to distinctive physical characteristics，this paper proposes a subpaging aware page replacement algorithm for flashmemory.The proposed algorithm introducesa subpaging technology and a partial update scheme based on similar probability in order to improve the performance for flash memory storage system.At the same time，the proposed algorithm calculates the replacing value of each main memory page and selects the onewith the least replacing value as the eviction page.Experimental results show that the proposed subpaging aware page replacement algorithm is better than current page replacement algorithms on page hit ratio，the number ofwrite／read operations and runtime.

flash memory；page replacement algorithm；subpaging technology；enterprise；storage；least recently used algorithm

TP 15

A

1007-7405（2015）05-0396-05

2014-12-22

2014-05-22

劉君玲（1973—），女，實(shí)驗(yàn)師，從事計(jì)算機(jī)應(yīng)用研究.