湯 顯，周軍鋒（1.燕山大學(xué)經(jīng)濟(jì)與管理學(xué)院，河北秦皇島066004；.燕山大學(xué)信息科學(xué)與工程學(xué)院，河北秦皇島066004）

一種基于閃存的低能耗緩沖區(qū)管理算法

湯 顯1，?，周軍鋒2
（1.燕山大學(xué)經(jīng)濟(jì)與管理學(xué)院，河北秦皇島066004；2.燕山大學(xué)信息科學(xué)與工程學(xué)院，河北秦皇島066004）

摘 要：閃存以其低能耗、低延遲、小巧輕便及高抗震性等特點(diǎn)廣泛應(yīng)用于不同環(huán)境中以消除磁盤機(jī)械尋址所帶來的高能耗及高延遲等問題。提出一種基于閃存硬盤（SSD）的低能耗緩沖區(qū)置換算法AFC。當(dāng)需要選擇置換頁時(shí)，AFC使用基于代價(jià)的啟發(fā)式來選擇置換頁。AFC的設(shè)計(jì)目標(biāo)是基于用戶設(shè)定的權(quán)值，在最小化能耗和最大化吞吐量之間取得平衡。對(duì)不同型號(hào)的閃存芯片進(jìn)行了實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，基于AFC來管理緩沖區(qū)數(shù)據(jù)時(shí)，可以顯著降低系統(tǒng)的能耗。

關(guān)鍵詞：閃存；能耗；緩沖區(qū)；置換策略

0　引言

綠色計(jì)算是最近一段時(shí)間大家關(guān)注的熱點(diǎn)，對(duì)于計(jì)算機(jī)系統(tǒng)來說，基于磁盤的存儲(chǔ)子系統(tǒng)需要消耗大約40%的電量［1］，降低存儲(chǔ)子系統(tǒng)的耗電量可有效降低系統(tǒng)的總能耗。

和磁盤相比，閃存是一種低能耗的純電子產(chǎn)品，符合綠色計(jì)算的初衷和目標(biāo)。目前各種應(yīng)用中基于閃存存儲(chǔ)設(shè)備的表現(xiàn)形式是閃存硬盤SSD，SSD提供與磁盤同樣的存取接口。由于SSD隨機(jī)讀寫操作在耗時(shí)和耗能方面表現(xiàn)不一致，且不同型號(hào)SSD的不一致性存在較大的差異，在一些對(duì)性能或者能耗要求苛刻的應(yīng)用場合，需要充分考慮閃存讀寫速度不一致、低能耗的特點(diǎn)來設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和算法，以便在降低能耗的同時(shí)提升系統(tǒng)性能。

緩沖區(qū)是計(jì)算機(jī)系統(tǒng)的基本組成部分之一。由于容量有限，緩沖區(qū)置換算法的有效性嚴(yán)重影響計(jì)算機(jī)系統(tǒng)的整體性能。文獻(xiàn)［2］在三十多年前已經(jīng)意識(shí)到數(shù)據(jù)頁在緩沖區(qū)中的讀寫狀態(tài)會(huì)影響置換策略的有效性。對(duì)于閃存而言，讀寫延遲和能耗存在不對(duì)稱性問題，數(shù)據(jù)頁的讀寫狀態(tài)對(duì)系統(tǒng)性能的影響更嚴(yán)重。然而現(xiàn)有的基于閃存的緩沖區(qū)置換策略［3?7］沒有考慮能耗問題。已有方法考慮的都是單位時(shí)間最大化系統(tǒng)吞吐量的問題，由于不同類型的閃存的讀寫延遲和所需能耗之間不符合正比關(guān)系，因而單位時(shí)間最大化系統(tǒng)吞吐量可能需要耗費(fèi)更多的電量。

針對(duì)現(xiàn)有緩沖區(qū)置換算法存在的問題，本文提出一種基于閃存的低能耗自適應(yīng)緩沖區(qū)管理算法AFC。AFC的設(shè)計(jì)目標(biāo)是基于用戶設(shè)定的權(quán)值，在最小化能耗和最大化吞吐量之間取得平衡。AFC通過減少讀寫操作的能耗來降低系統(tǒng)耗電量，這和已有的磁盤休眠調(diào)度算法及用SSD取代磁盤并不矛盾，且具有互補(bǔ)性。

1　背景及相關(guān)工作

基于磁盤的緩沖區(qū)置換策略［8?15］的基本假設(shè)是每次置換操作的代價(jià)相同。由于閃存的讀寫代價(jià)不一致，當(dāng)設(shè)計(jì)基于閃存的緩沖區(qū)管理算法時(shí)，以上假設(shè)不再成立。

數(shù)據(jù)頁置換的目的是最小化請求序列的總代價(jià)。文獻(xiàn)［16］提出了最優(yōu)離線算法并通過最小代價(jià)最大流問題［17］進(jìn)行求解。對(duì)于在線算法來說，未來的請求序列是未知的。FAB［4］方法將數(shù)據(jù)頁組織成不同的物理塊，不同物理塊用一個(gè)塊層LRU鏈表來組織。BPLRU［5］和FAB的區(qū)別在于將隨機(jī)寫變成順序?qū)憗硖岣邔懖僮鞯男省?/p>

假設(shè)閃存的寫代價(jià)遠(yuǎn)遠(yuǎn)大于讀代價(jià)，CFLRU［3］用LRU鏈表來組織數(shù)據(jù)頁，如圖1所示。LRU鏈表分成工作區(qū)（Working Region）和置換區(qū)（Clean?First Region）兩個(gè)部分。數(shù)據(jù)頁未命中時(shí)，CFLRU從置換區(qū)中選擇最近最少使用的只讀頁進(jìn)行置換，如圖1的p6。當(dāng)置換區(qū)中沒有只讀頁時(shí)，CFLRU選擇鏈表尾部的修改頁進(jìn)行置換。

圖1　CFLRU置換策略示意圖Fig.1　Illustration of the CFLRU replacement strategy

文獻(xiàn)［6］根據(jù)置換區(qū)中數(shù)據(jù)頁的修改狀態(tài)，將將置換區(qū)中的數(shù)據(jù)頁組織為不同的隊(duì)列。CFDC［7］通過將數(shù)據(jù)頁進(jìn)行重新組織來提升系統(tǒng)性能，如圖2所示。注意CFDC中塊的大小并非固定的。

圖2　CFDC置換策略示意圖Fig.2　Illustration of the CFDC replacement strategy

盡管文獻(xiàn)［18］提出了可以避免多線程環(huán)境下鎖爭用問題的算法，但其對(duì)于循環(huán)和序列的檢測卻由于多線程的存在而降低準(zhǔn)確性；同時(shí)，該方法沒有從能耗的角度來考慮如何基于單位能耗最大化系統(tǒng)吞吐量。

文獻(xiàn)［19］基于日志的特點(diǎn)，提出相應(yīng)的緩沖區(qū)數(shù)據(jù)頁置換算法。文獻(xiàn)［20］對(duì)綠色計(jì)算所涉及到的問題進(jìn)行了綜述。文獻(xiàn)［21］綜述了大數(shù)據(jù)存儲(chǔ)的相關(guān)問題，并討論了閃存在其中的作用。

2　AFC算法

2.1數(shù)據(jù)結(jié)構(gòu)

和文獻(xiàn)［18］類似，AFC將緩沖區(qū)中的數(shù)據(jù)頁根據(jù)其讀寫狀態(tài)組織為兩個(gè)環(huán)形數(shù)據(jù)結(jié)構(gòu)CC和DC，分別維護(hù)只讀頁和修改頁，如圖3所示。假定緩沖區(qū)的容量是s，則｜CC∪DC｜＝s∧CC∩DC＝?。AFC維護(hù)了一個(gè)全局計(jì)數(shù)器Counter，每當(dāng)發(fā)生一次數(shù)據(jù)頁請求，Counter值加1。對(duì)于緩沖區(qū)中的每個(gè)數(shù)據(jù)頁p，AFC為其關(guān)聯(lián)3個(gè)變量：T、C和I，其中T表示p進(jìn)入緩沖區(qū)的時(shí)間（當(dāng)時(shí)的Counter值），否則為最近一次被命中的時(shí)間）；C是p的訪問位計(jì)數(shù)器，表示p被訪問的頻繁程度；I表示p最近兩次被命中之間對(duì)其他數(shù)據(jù)頁訪問的次數(shù)，稱為命中距離［18］。

圖3　AFC置換策略Fig.3　The AFC replacement strategy

如圖3所示，虛線環(huán)用于處理循環(huán)模式的數(shù)據(jù)頁訪問，稱為子環(huán)，CC和DC中的子環(huán)分別用SCCC和SCDC表示。雖然AFC和FClock［18］的數(shù)據(jù)結(jié)構(gòu)基本一致，二者的主要區(qū)別體現(xiàn)在對(duì)數(shù)據(jù)頁的操作策略上，具體來說體現(xiàn)在以下幾點(diǎn)：1）對(duì)于循環(huán)和序列模式數(shù)據(jù)頁的偵測和處理方式上；2）數(shù)據(jù)頁的代價(jià)計(jì)算方式；3）置換頁的選擇策略。本文所用符號(hào)的意義如表1所示。

2.2基于代價(jià)的置換頁選擇策略

如果緩沖區(qū)滿且當(dāng)前請求的數(shù)據(jù)頁p不在緩沖區(qū)中，AFC根據(jù)“代價(jià)”從CC或DC中選擇一個(gè)數(shù)據(jù)頁進(jìn)行置換，并從SSD讀入數(shù)據(jù)頁p。對(duì)于AFC來說，CC和DC的大小用公式（1）來計(jì)算，其意義可闡述為：大小和付出成正比，這里的付出指過去一段時(shí)間內(nèi)由于數(shù)據(jù)頁缺失所付出的外存存取代價(jià)。假設(shè)緩沖區(qū)最多可放s個(gè)數(shù)據(jù)頁，AFC置換策略可表述為：若｜CC｜＜βs，則DC過大，那么從DC中選擇一個(gè)數(shù)據(jù)頁進(jìn)行置換；反之從CC中選擇一個(gè)數(shù)據(jù)頁進(jìn)行置換。本文中過去一段時(shí)間指過去s次訪問，CC的代價(jià)記為CCC，DC的代價(jià)記為CDC。

β＝CCC/（CCC＋CDC）（1）

為了計(jì)算式（1）中的代價(jià)值，需要知道對(duì)于CC和DC中的每個(gè)數(shù)據(jù)頁而言，以什么作為其代價(jià)值。為了綜合考慮置換延遲和能量消耗，本文提出使用CR和CW作為每個(gè)未修改頁和修改頁的加權(quán)值來表示數(shù)據(jù)頁的置換代價(jià)，ER和EW表示讀和寫一個(gè)數(shù)據(jù)頁所需的能耗，其計(jì)算方法為

顯然，當(dāng)x＝1時(shí)，本文提出的代價(jià)計(jì)算方法僅考慮操作延遲、不考慮能耗，這和FClock相同；當(dāng)x＝0時(shí)，本文提出的代價(jià)計(jì)算方法僅考慮能耗、不考慮操作延遲；其它情況可根據(jù)用戶和實(shí)際系統(tǒng)的需求在能耗和操作延遲之間選擇合理的搭配比例。

基于式（2）和（3），筆者使用式（4）和（5）來計(jì)算式（1）中CCC和CDC的值。其中s/n表示數(shù)據(jù)頁被命中的概率，相應(yīng)的沒有命中的概率是（1－s/n）。式（4）和（5）同時(shí)考慮了邏輯操作和物理操作。

上述內(nèi)容僅僅解決了當(dāng)所請求的數(shù)據(jù)頁不在緩沖區(qū)中時(shí)，從CC還是DC中選擇置換頁的問題。當(dāng)確定了置換頁的出處后，下一步的工作是選擇哪個(gè)數(shù)據(jù)頁進(jìn)行置換的問題。

已有方法在選擇置換頁時(shí)，都是選擇訪問位計(jì)數(shù)器的值等于0的數(shù)據(jù)頁予以置換，這種方法沒有充分考慮循環(huán)和序列訪問模式的影響，或者說對(duì)循環(huán)和序列訪問模式的偵測方式不夠好。FClock通過檢查連續(xù)未命中數(shù)據(jù)頁的個(gè)數(shù)來判斷是否為循環(huán)和序列訪問模式，這種方式的最大問題在于判斷不夠準(zhǔn)確?？紤]以下兩種情況：1）在多線程環(huán)境下，前面的線程已經(jīng)提前讀取了10號(hào)數(shù)據(jù)頁，當(dāng)后續(xù)線程需要循環(huán)讀取1～20號(hào)數(shù)據(jù)頁時(shí)，由于10號(hào)數(shù)據(jù)頁已經(jīng)在緩沖區(qū)中，因此，F(xiàn)Clock無法判定1～20號(hào)數(shù)據(jù)頁是一個(gè)循環(huán)或者完整序列；2）當(dāng)連續(xù)未命中的數(shù)據(jù)頁個(gè)數(shù)超過指定的閾值后，F(xiàn)Clock會(huì)將后續(xù)未命中的數(shù)據(jù)頁放入子環(huán)中。除非當(dāng)前數(shù)據(jù)頁屬于某個(gè)循環(huán)序列訪問模式，否則保留子環(huán)中的數(shù)據(jù)頁都是對(duì)緩沖區(qū)中有效空間的浪費(fèi)，不幸的是，F(xiàn)Clock無法區(qū)分循環(huán)和序列訪問模式。

針對(duì)以上問題，本文的置換頁選擇策略如算法1所示。第1行根據(jù)CC和DC的代價(jià)比值確定置換頁來自哪里。第2～9行確定選擇DC中的哪個(gè)數(shù)據(jù)頁進(jìn)行置換。如果當(dāng)前處理的數(shù)據(jù)頁屬于一個(gè)序列中（第3行），該序列是一個(gè)循環(huán)序列（第4行）且DC中該序列的長度大于預(yù)先指定的閾值（第5行，λ｜DC｜＜DC.F，DC.F表示當(dāng)前序列的長度），這時(shí)選擇SCDC中的當(dāng)前頁進(jìn)行置換，即使用MRU策略（第6行）。如果第5行的條件不滿足，則說明當(dāng)前處理的是循環(huán)序列且該循環(huán)序列的長度僅有一小部分在緩沖區(qū)中，則處理策略是選擇DC中的一個(gè)數(shù)據(jù)頁進(jìn)行置換（第7行）。如果第4行的條件不滿足，說明當(dāng)前處理的是順序存取序列，則可以直接依照MRU策略扔掉當(dāng)前數(shù)據(jù)頁（第8行）。如果第3行的條件不滿足，說明當(dāng)前處理的數(shù)據(jù)頁不是序列中的一個(gè)數(shù)據(jù)頁，則依照優(yōu)先置換最不頻繁使用的數(shù)據(jù)頁的原則，優(yōu)先置換第一個(gè)訪問位計(jì)數(shù)器的值等于0的數(shù)據(jù)頁（第9行）。對(duì)于CC中數(shù)據(jù)頁的處理類似，這里不再贅述。需要注意的是這里序列的檢測方法是地址連續(xù)且訪問連續(xù)的數(shù)據(jù)頁個(gè)數(shù)大于預(yù)先設(shè)定的閾值即可，和在訪問這些數(shù)據(jù)頁的過程中是否有命中沒有關(guān)系。對(duì)于循環(huán)訪問序列的檢測，可以通過維護(hù)一個(gè)哈希表結(jié)合LRU鏈表來記錄過去一段時(shí)間的訪問序列即可。當(dāng)一個(gè)序列中的數(shù)據(jù)頁被連續(xù)訪問，且出現(xiàn)在哈希表中的概率較大（可以指定一個(gè)閾值），即可認(rèn)為被訪問的數(shù)據(jù)頁是循環(huán)序列中的數(shù)據(jù)頁。所有以上操作均可在O（1）代價(jià)的基礎(chǔ)上完成。具體的操作方法和數(shù)據(jù)頁訪問位修改策略見文獻(xiàn)［18］中的描述。

2.3AFC置換策略

AFC數(shù)據(jù)頁置換算法的基本思想可以表述為：如果緩沖區(qū)未滿且請求頁p沒有命中，則根據(jù)對(duì)p的讀寫類型從閃存硬盤上讀取數(shù)據(jù)頁并將其放入CC或者DC中，然后更新平均命中距離。如果p命中，則在CC或者DC將相應(yīng)的邏輯操作次數(shù)加1，并將命中距離置0。如果對(duì)p的操作類型是寫且p∈CC，則將p從CC移動(dòng)到DC中。同時(shí)，如果p的命中距離大于等于平均命中距離，則p的訪問計(jì)數(shù)加1，最后更新平均命中距離的值。具體的更新方法和［18］相同，本文不再贅述。

如果緩沖區(qū)已滿且p命中時(shí)，其操作和前面一段所介紹的方法相同。如果p沒有命中，則從CC或者DC中選擇一個(gè)數(shù)據(jù)頁進(jìn)行置換，具體的選擇方法見算法1，其基本思想和計(jì)算方法已在2? 2小節(jié)進(jìn)行了說明。然后根據(jù)p的操作類型從閃存硬盤讀入p并將其放入緩沖區(qū)中，最后更新平均命中距離的值。對(duì)于循環(huán)序列，則直接插入子環(huán)中，否則插入CC或者DC中，之后進(jìn)一步修改序列標(biāo)識(shí)即可。

3　實(shí)驗(yàn)

3.1實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)?zāi)康臑椋涸诳紤]能耗的情況下，本文方法針對(duì)不同SSD的有效性。對(duì)于不考慮能耗的情況，感興趣的讀者可以參考文獻(xiàn)［18］獲取詳細(xì)實(shí)驗(yàn)結(jié)果。用于測試的SSD型號(hào)為三星MCAQE32G5APP（用FD1表示）。FD1的隨機(jī)讀寫的延遲比率是1∶118，能耗比是1∶9。

對(duì)SSD來說，如文獻(xiàn)［18］所述，緩沖區(qū)置換算法的性能受物理讀寫次數(shù)的影響，然而FTL層的實(shí)現(xiàn)是設(shè)備相關(guān)的，由硬盤制造商提供，并沒有為用戶提供跟蹤讀寫次數(shù)的接口。因此，和文獻(xiàn)［18］類似，本文使用模擬器［22］來進(jìn)行測試。實(shí)驗(yàn)了6種置換策略進(jìn)行比較，即：LRU、CLOCK［9］、CFLRU［3］、CFDC［7］、FClock［18］及本文提出的AFC。所有的置換策略都用Visual C＋＋實(shí)現(xiàn)的。這里將CFLRU算法中“置換區(qū)”的“窗口大小”設(shè)為緩沖區(qū)大小的75%，將CFDC的“置換區(qū)”的“窗口大小”設(shè)為緩沖區(qū)的50%，將CFDC的“聚類大小”設(shè)為64。參數(shù)取自對(duì)應(yīng)文獻(xiàn)實(shí)驗(yàn)中所采用的數(shù)值。

將數(shù)據(jù)庫的文件大小模擬為64 MB，相當(dāng)于32 000個(gè)的物理頁，每頁為2 KB。緩沖區(qū)的大小范圍從2 000個(gè)頁到8 000個(gè)頁。本文實(shí)驗(yàn)中，模擬器假定數(shù)據(jù)頁的大小是2 KB，每個(gè)數(shù)據(jù)塊包含64個(gè)數(shù)據(jù)頁。

生成了4種類型的測試數(shù)據(jù)，其統(tǒng)計(jì)數(shù)據(jù)如表2所示，其中“讀/寫比率”列中的“x%/y%”表示對(duì)某種測試數(shù)據(jù)來說，所有請求的x%為讀操作、y%為寫操作；“局部性”列中的“x%/y%”表示對(duì)某種測試數(shù)據(jù)來說，在y%的頁上有x%的操作。

表1中讀寫代價(jià)Cr和Cw可以通過SSD的技術(shù)手冊得到，或者通過執(zhí)行一定量的讀寫操作后取平均值來獲得。本文實(shí)驗(yàn)所用數(shù)據(jù)來自于技術(shù)手冊。

筆者選擇以下標(biāo)準(zhǔn)來評(píng)價(jià)緩沖區(qū)置換策略：1）運(yùn)行時(shí)間；2）能耗比，指不同閃存執(zhí)行相同操作耗費(fèi)的電量的比值。

3.2性能比較和分析

下面分為3種情況比較不同方法的能耗：1）x ＝1，即最大化單位時(shí)間吞吐量為目標(biāo)；2）x＝0.5，即部分考慮能耗的情況；3）x＝0，即最大化單位能耗吞吐量為目標(biāo)。3種情況對(duì)應(yīng)的算法名字分別是AFC1、AFC2和AFC3。

圖4展示了不同方法在FD1上運(yùn)行T1到T4后得到的運(yùn)行時(shí)間和能耗比，其中子圖（a）、（c）、（e）、（g）展示不同方法的運(yùn)行時(shí)間，與之對(duì)應(yīng)的4個(gè)子圖（b）、（d）、（f）、（h）展示不同方法的能耗比。

從圖4可以看出，由于已有方法沒有考慮能耗，因而其運(yùn)行時(shí)間和x值的變化無關(guān)。與之對(duì)應(yīng)，隨著式（2）和（3）中x值的變化，發(fā)生變化的是AFC1、AFC2和AFC3。從圖4的（a）、（c）、（e）、（g）可以看出，在沒有考慮能耗時(shí)，AFC1因其可以更好的處理循環(huán)和序列訪問模式而取得了最好的性能結(jié)果；而當(dāng)更多的考慮能耗時(shí)，即從單位時(shí)間最大化吞吐量向單位能耗最大化吞吐量時(shí)，AFC3的性能出現(xiàn)了一定程度的下降。結(jié)合圖4的（b）、（d）、（f）、（h）可以看出，AFC3盡管在單位時(shí)間吞吐量方面不如AFC1，但對(duì)于相同的任務(wù)，AFC3所需的能耗是最小的，原因在于對(duì)于AFC3而言，式（2）和（3）中的x＝0，即AFC3的目標(biāo)是單位能耗吞吐量的最大化。總的來看，由于可以較好的處理循環(huán)和序列訪問模式，AFC算法無論從單位時(shí)間還是單位能耗的角度來說，和已有方法相比，均可以做的更好。

圖4　不同方法在FD1上運(yùn)行T1～T4時(shí)的運(yùn)行時(shí)間和能耗比Fig.4　Comparison of the running time and power consumption of different algorithms

4　結(jié)束語

針對(duì)閃存的讀寫操作所需能耗不同且不同類型閃存的讀寫能耗比差別大的問題，本文提出一種基于閃存硬盤（SSD）的低能耗緩沖區(qū)管理算法AFC。當(dāng)需要選擇置換頁時(shí)，AFC使用基于代價(jià)的啟發(fā)式來選擇置換頁。AFC的設(shè)計(jì)目標(biāo)是基于用戶設(shè)定的權(quán)值，在最小化能耗和最大化吞吐量之間取得平衡。實(shí)驗(yàn)結(jié)果驗(yàn)證了AFC算法的有效性。

參考文獻(xiàn)

［1］Roberts D Kgil T Mudge T N.Using non?volatile memory to save energy in servers C //Proceedings of the 2009 International Con?ference on Design Automation and Test in Europe Nice France 2009 743?748.

［2］Effelsberg W Haerder T.Principles of database buffer management J .ACM Transactions on Database Systems 1984 9 4 560?595.

［3］Park S Y Jung D Kang J U et al.CFLRU a replacement algorithm for flash memory C //Proceedings of the 2006 International Con?ference on Compilers Architecture and Synthesis for Embedded Systems Seoul Korea 2006 234?241.

［4］Jo H Kang J U Park S Y et al.FAB flashaware buffer management policy for portable media players J .IEEE Transactions on Consumer Electronics 2006 52 2 485?493.

［5］Kim H Ahn S.BPLRU a buffer management scheme for improving random writes in flash storage C //Proceedings of the 6th USE?NIX Conference on File and Storage Technologies San Jose Cali?fornia USA 2008 239?252.

［6］Koltsidas I Viglas S.Flashing up the storage layer J .Proceedings of the VLDB Endowment Auckland New Zealand 2008 1 1 514?525.

［7］Ou Y Haerder T Jin P.CFDC a flash?aware replacement policy for database buffer management C //The 5th International Workshop on Data Management on New Hardware DaMoN＇09 Providence Rhode Island USA 2009 15?20.

［8］Robinson J Devarakonda M V.Data cache management using fre?quency?based replacement C //Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Com?puter Systems University of Colorado Boulder Colorado USA 1990 134?142.

［9］Babaoglu O Joy W.Converting a swap?based system to do paging in an architecture lacking page?reference bits J .ACM SIGOPS Op?erating Systems Review 1981 15 5 78?86.

［10］Robinson J T Devarakonda M V.Data cache management using frequency?based replacement C //Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Com?puter Systems Boulder Colorado USA 1990 134?142.

［11］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 Washington USA 1993 297?306.

［12］Johnson T Shasha D.2q A low overhead high performance buffer management replacement algorithm C //Proceedings of the 20th International Conference on Very Large Data Bases Santiago de Chile Chile 1994 439?450.

［13］Jiang S Zhang X.Making lru friendly to weak locality workloads A novel replacement algorithmto improve buffer cache performance J .IEEE Transactions on Computers 2005 54 8 939?952.

［14］Megiddo N Modha D S.Arc A self?tuning low overhead replace?ment cache C //Proceedings of the FAST′03 Conference on File and Storage Technologies San Francisco California USA 2003 115?130.

［15］Lee D Choi J Kim J H et al.LRFU a spectrum of policies that subsumes the least recently used and least frequently used policies J .IEEE Transactions on Computers 2001 50 12 1352?1361.

［16］Chrobak M Karloff H J Payne T H et al.New results on server problems J .SIAM Journal on Discrete Mathematics 1991 4 2 172?181.

［17］Cormen T H Leiserson C E Rivest R L et al.Introduction to Al?gorithms M .USA The MIT Press 2001.

［18］湯顯 孟小峰.FClock 一種面向SSD的自適應(yīng)緩沖區(qū)管理算法 J .計(jì)算機(jī)學(xué)報(bào) 2010 33 8 1460?1471.

［19］盧科 金培權(quán) 岳麗華.一種針對(duì)塊內(nèi)日志存儲(chǔ)模型的緩沖區(qū)管理方法 J .小型微型計(jì)算機(jī)系統(tǒng) 2013 34 5 1021?1027.

［20］金培權(quán) 邢寶平 金勇 等.能耗感知的綠色數(shù)據(jù)庫研究綜述J .計(jì)算機(jī)應(yīng)用 2014 34 1 46?53.

［21］金培權(quán) 郝行軍 岳麗華.面向新型存儲(chǔ)的大數(shù)據(jù)存儲(chǔ)架構(gòu)與核心算法綜述 J .計(jì)算機(jī)科學(xué)與工程 2013 35 10 12?24.

［22］Jin P Su X Li Z.A flexible simulation environment for flashaware algorithms C //Proceedings of the 18th ACM Confer?ence on Information and Knowledge Management Hong Kong China 2009 2093?2094.

A flash?based buffer replacement algorithm towards low power consumption

TANG Xian1ZHOU Jun?feng2
1.School of Economics and Management Yanshan University Qinhuangdao Hebei 066004 China 2.School of Information Science and Engineering Yanshan University Qinhuangdao Hebei 066004 China

AbstractAs an important alternative to conventional magnetic disks flash?based devices which have the features of lower power consumption no mechanical parts portable and shock resistance are used extensively in different environments to reduce the power consumption and long time of mechanical addressing for conventional magnetic disks.An adaptive flash?aware buffer replacement al?gorithm namely AFC is proposed based on flash chip based hard disk namely Solid?State Disk SSD .AFC adopts cost?based heu?ristics to select victim pages for replacement.The aim of AFC is to leverage between maximum performance and minimum power consumption.The experimental results show that AFC significantly reduces power consumption based on different flash chips.

Key wordsflash power consumption buffer replacement strategy

作者簡介：?湯顯（1978?），女，山東榮成人，博士，講師，主要研究方向?yàn)殚W存數(shù)據(jù)庫，Email：txianz＠gmail.com。

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61303040，61472339）

收稿日期：2015?03?16

文章編號(hào)：1007?791X（2015）03?0269?07

DOI：10.3969/j.issn.1007?791X.2015.03.011

文獻(xiàn)標(biāo)識(shí)碼：A

中圖分類號(hào)：TP391