【文章內(nèi)容簡介】 改良首先，我們介紹一個基本的清潔方法[1011]；再介紹KimLee演算法。並將其管理方法上冷資料(Cold data)與熱資料(Hot data)的分離政策、清潔片段選擇、與抹除均勻策略上的缺點逐一提出改良，以得到一個最佳化的管理效能。一、貪婪演算法的缺點對於快閃記憶體，清除策略演算法的效率直接影響系統(tǒng)效能[3,10]。此外，依照eNVy的清潔花費模式，由片段利用率決定片段的清潔費用[3]。因此，如何挑選一個片段進行清除，將是影響成本的最重要因素。直覺地，期待選擇那些最少有效資料區(qū)塊的片段是比較有利於節(jié)省清潔費用，此乃貪婪清潔法[910]。貪婪清潔法選擇節(jié)段的方式是尋找節(jié)段內(nèi)有最多數(shù)量的舊資料作回收，目的在花最少的成本以期待獲得較大的回收空間。在存取行為比較平均的情況下，貪婪清潔法與其他清除策略並不會相差太多[1]。當存取行為有高度集中的情況下(比較符合實作的系統(tǒng)，根據(jù)研究在UNIX檔案系統(tǒng)中，有67~78%寫入行為集中在少數(shù)的檔案上[1213])，貪婪清潔法的抹除與搬移次數(shù)會有急速增加趨勢[3,7,10]。主要原因為貪婪清潔法在挑選節(jié)段時，無法有效辨別資料冷熱狀態(tài)。因此，會造成剛更新後的節(jié)段內(nèi)迅速增加新的舊區(qū)塊，導致再次進入準備被抹除的狀態(tài)(忽略了再增加陳舊資料的機會)，而使得效率下降。更進一步，因為貪婪法不能有效的分離冷熱資料，使得冷熱資料同時存在每一個片段裡，造成在每次的清潔時冷資料無益的到處搬移，再度造成降低系統(tǒng)效能。高可靠度和低成本效益快閃記憶體管理模式　7二、冷熱資料分離為了解決貪婪清潔法的缺點，在KimLee中提出一‘收集’運算，自熱的資料區(qū)段中隔離出冷資料。實際上，這被實行於另一個模式，稱為快閃記憶體管理員的蒐集家。清潔者定期啟動蒐集家，收集日誌中的冷資料碎片。 KimLee演算法冷熱資料分離缺點在KimLee演算法中，其冷熱資料分離是藉由蒐集家來完成。其工作分兩個階段：(1)搜尋並且收集冷資料(檔案)區(qū)塊碎片；(2)群集冷資料至日誌的尾端，收集運算程序，如圖(三)所示。圖(三)　收集程序在第一階段中的在每個收集時間，蒐集家決定收集大小並且在很多的碎片中搜尋冷資料。令收集大小單位為10，而且當很多碎片的冷資料在檔案a和b被收集是可能的，如圖(三)所示。在第二階段中，檔案的區(qū)塊被寫入至日誌的後面，直到達收集大小的值為止。如果收集的程序期間可用自由空間不是充足，清潔者可被喚醒，以產(chǎn)生新的可用空間[8]。由以上的運算模式中，我們研究結果，有下列結論。在KimLee演算法的蒐集家運作中，雖然在第一階段中已將冷資料收集出來，但在第二階段中，將冷資料寫入至日誌的後端，且可能未填滿整個區(qū)段。使得後來檔案管理系統(tǒng)因為對某一檔案更新，將一個熱資料寫入日誌的尾端，造成冷熱資料再度的混合；因此，影響整體冷熱資料分離程度的效能。針對此冷熱資料分離缺點我們提出改進方法。 冷熱資料分離缺點的改進方式因為一般的LFS結構僅有一個使用中的資料區(qū)段LFS與可用自由空間的資料區(qū)段8　臺北科技大學學報第三十七之一期LFS，在KimLee分離演算法中採用檔案來區(qū)別冷熱資料，要收集剛好一個片段大小的資料量是較困難的。因此，無法有效的分離冷熱資料，進而影響整體效能。我們的策略是將快閃記憶體使用中的資料區(qū)段分為兩類。一類存放常更新的檔案即熱資料；另一類存放不常更動的資料檔或是唯讀檔即冷資料。每一個節(jié)段在快閃記憶體剛起始或經(jīng)回收至可用自由片段內(nèi)後，都不具有任何屬性。在存有資料區(qū)塊後，會視所存放資料檔屬性，而成為「熱片段」或「冷片段」，即常更新或不常更新片段。此後，當蒐集家收集冷資料時，便將其重寫入冷資料片段LFS中的日誌尾端如圖(四)所示，更新或清除資料時則將資料重寫入到熱資料LFS中的日誌尾端，如此可改善冷熱資料混合機率。因此，我們有引理2改善散冷熱資料的混合機率。圖(四)　冷資料收集示意圖引理2： 當收集冷資料時，將其寫入到冷資料片段LFS中的日誌尾端和當更新或抹除片段時將片段中的有效資料重寫入到熱資料LFS中的日誌尾端，可以改善冷熱資料混合的機率。高可靠度和低成本效益快閃記憶體管理模式　9三、均勻抹除快閃記憶體因為有抹除次數(shù)的限制，比如Toshiba TH58NVG1S3AFT05 2Gbit，其抹除次數(shù)為100,000次[15]。假若某個片段中存在永遠不被更新的唯讀檔，此時非均勻抹除將嚴重發(fā)生。若系統(tǒng)中存在多數(shù)的冷資料片段(不被抹除)，則快閃記憶體將因為輪替抹除的區(qū)段變少，而增加抹除次數(shù)。使得快閃記憶體容量因抹除次數(shù)極限值的到達，而降低可用的記憶體空間。舉例，某一快閃記憶體有100個抹除片段，每一個片段的抹除次數(shù)為100,000次；假若其儲存空間中永遠包含著30個片段的冷資料，其使用率永遠很高不會被系統(tǒng)回收抹除，故僅剩下70個片段來輪流使用抹除。假設在一個高密度寫入的情況下，每天有5000個片段抹除回收需求(不考慮抹除不均勻)，則其記憶體100%可用的使用壽命為：100%生命週期=。換句話說，其記憶體空間僅剩下30%。那就是只剩存著冷資料的片段可再被使用。而此30%也將會因為記憶體空間不足，而需更頻繁的抹除而快速達到極限值。在上式中並未考慮因為抹除不均勻，使得可用空間急速減少，而需付出的額外抹除次數(shù)。若我們在系統(tǒng)中考慮均勻抹除，則此100個片段的抹除次數(shù)差異將會控制在某一範圍內(nèi)，使其幾乎同時達到抹除界限值。在記憶體使用上，也會有較大的空間與彈性，假設均勻抹除必須額外付出8%清除費用[8]，此時的使用壽命為：100%生命週期=由以上論述可知，雖然均勻抹除需付出額外的清潔費用，但在可靠度與大記憶體空間及壽命延長是非常值得的。KimLee演算法清潔索引策略的缺點清潔索引(CleaningIndex)是選擇片段被清理的準則；最低的索引數(shù)值片段，將在清潔時被選擇[8]。清潔索引定義了降低清潔花費及提高均勻抹除兩者如下：上式中ui表示片段i的利用率、206。i表示抹除計數(shù)、和206。max是表示最大的抹除計數(shù)值。清潔索引由二個因素組成：每個片段的利用率和抹除計數(shù)。正規(guī)化齊平度是此二個因數(shù)的加權，使用λ表示。計算出的齊平度映射到0到1之間的數(shù)值。l= 如果抹除是均勻分配，則清潔索引是使用在降低清潔費用。相反的，當發(fā)生不均勻(嚴重歪斜)抹除動作時，清潔索引的工作，是為了均勻抹除。換句話說，在正常運作時，當此齊平度在可容忍的臨限之下（λ的數(shù)值接近0）時，ui利用率必定是選擇一個片段的主要因數(shù)。當此齊平度超過可容忍的界限（λ的數(shù)值接近1）時，則清潔索引應該被計算考慮此兩10　臺北科技大學學報第三十七之一期因數(shù)，或偏重均勻抹除。此演算法的立意甚佳，當片段選擇時，須要同時考慮清潔成本與均勻抹除。但此公式卻有一個嚴重缺點，即當片段越接近抹除極限值時，卻疏失於均勻抹除參數(shù)，而偏重使用率的參數(shù)。是因為(206。i/206。max+1)抹除權重因子所造成。當快閃記憶體越接近抹除極限值時，(206。i/206。max+1)抹除權重因子會接近於1，不會有太大的差距，使的清潔索引值僅由利用率來判斷選擇，容易造成高抹除的片段因為可能有低的利用率，再度被