劉君玲

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

子頁(yè)感知的閃存頁(yè)面置換算法

劉君玲

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

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

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

0 引言

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

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

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

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

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

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

1 子頁(yè)感知的閃存頁(yè)面置換算法

1.1 子頁(yè)技術(shù)

在操作系統(tǒng)中，為了保持?jǐn)?shù)據(jù)一致性，當(dāng)頁(yè)面置換算法選擇的犧牲頁(yè)為臟頁(yè)時(shí)，頁(yè)面置換算法先要把臟頁(yè)寫回存儲(chǔ)系統(tǒng)中，最后才回收對(duì)應(yīng)的頁(yè)框.現(xiàn)代操作系統(tǒng)中頁(yè)的大小普遍為4 KB，而閃存中頁(yè)的大小為512 B，也就是說(shuō)寫回一個(gè)臟頁(yè)會(huì)觸發(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.通過(guò)測(cè)試發(fā)現(xiàn)，內(nèi)存中的臟頁(yè)通常含有大量的未修改數(shù)據(jù)，即干凈數(shù)據(jù).定義內(nèi)存頁(yè)平均臟度為內(nèi)存頁(yè)中已修改數(shù)據(jù)的數(shù)量與內(nèi)存頁(yè)總的存儲(chǔ)容量比率.

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

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

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

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

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

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

該

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

為了避免過(guò)度優(yōu)先置換出置換成本低的頁(yè)（包括干凈頁(yè)）而影響命中率，所以加權(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)存頁(yè)的熱度成為影響犧牲頁(yè)選擇的重要因素.當(dāng)δ＝8時(shí)，λ≈0．5，選擇犧牲頁(yè)的時(shí)候需要同時(shí)考慮這兩個(gè)因素.當(dāng)δ＞8時(shí)，λ＜0．5，內(nèi)存頁(yè)的置換成本成為影響犧牲頁(yè)選擇的重要因素.當(dāng)δ趨向于無(wú)限大時(shí)，T近似等于1，干凈頁(yè)可以被優(yōu)先置換出去，而不影響算法的整體性能.

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

圖2子頁(yè)感知的閃存頁(yè)面置換算法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ì)算子頁(yè)寫回閃存存儲(chǔ)器后變成不正確頁(yè)（Invalid Page）的概率：1）假定閃存存儲(chǔ)器由T個(gè)物理塊組成，每個(gè)塊包含Np個(gè)頁(yè)，閃存存儲(chǔ)器中臟頁(yè)的數(shù)量為Nd；2）假設(shè)從上次子頁(yè)寫操作結(jié)束到當(dāng)前的時(shí)間間隔，共產(chǎn)生了K次用戶寫操作；3）那么子頁(yè)被更新的概率，即變成不正確頁(yè)的概率為8／（T×Np-Nd）.然后，將具有相似概率的子頁(yè)聚類到同一個(gè)簇：1）設(shè)定一個(gè)概率閾值Pt；2）如果兩個(gè)子頁(yè)的概率差小于等于概率閾值Pt，那么這兩個(gè)子頁(yè)就具有相似概率；3）將具有相似概率的子頁(yè)聚類到同一個(gè)簇，直到簇的大小為8.最后，將大小為8的簇內(nèi)子頁(yè)寫回閃存存儲(chǔ)器.

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)采用中國(guó)科技大學(xué)開發(fā)的Flash-DBSim［11］閃存仿真軟件模擬閃存存儲(chǔ)系統(tǒng).Flash-DBSim是一個(gè)可配置的閃存仿真平臺(tái)，可以根據(jù)上層應(yīng)用程序的需要模擬出不同特性的閃存存儲(chǔ)系統(tǒng)，現(xiàn)有的很多研究都采用了Flash-DBSim進(jìn)行算法性能的測(cè)試實(shí)驗(yàn).

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

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

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

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

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

圖4頁(yè)面命中率Fig.4 Page hit ra tio

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

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

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

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

［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ù)庫(kù)緩沖區(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)用研究.