高可靠度和低成本效益快闪记忆体管理模式.docx

高可靠度和低成本效益快閃記憶體管理模式1高可靠度和低成本效益快閃記憶體管理模式Flash Memory Management Model with High Reliability and Low Cost-Benefit 黃文增* 陳彥勝 陳俊達 鄭重志W. T. Huang*,Y. S. Chen,C. T. Chen,C. C. Cheng國立台北科技大學電子工程系摘 要快閃記憶體可說是目前嵌入式系統記憶體的主流，而其有效的管理方式已被提出，其中以Kim和Lee所提出的管理方式最具代表性，我們簡稱為KimLee演算法8。本論文主要是以KimLee演算法為基礎，提出一個改良式的有效管理方法。我們的方法主要是針對快閃記憶體區塊作均勻抹除和減少抹除的動作；因此，快閃記憶體不但可以提升系統的效能降低清除成本而且能延長使用壽命。然而，快閃記憶單元的降低清除成本與均勻抹除兩者是相互衝突的；如何兩全其美取得一平衡點，是本論文的重點。首先，我們的方法是藉由動態的分析資料屬性，分離成冷資料與熱資料，並將其重寫於不同區段屬性中，以達到降低無意義的搬移動作，更進一步，能降低成本及提高系統壽命。第二目標是採用一種動態的均勻抹除策略，來提昇可靠度；而此方法最大效益是只需要犧牲少量的成本，便可達到延長快閃記憶體的壽命與使用的高可靠度。關鍵詞：嵌入式計算系統、快閃記憶體、儲存系統、檔案系統、清除策略、動態均勻抹除。投稿受理時間: 92 年 10 月 15 日 審查通過時間: 92 年 12 月 24 日ABSTRACT2臺北科技大學學報第三十七之一期Among the variously effective managements of the flash memory, the major representative method is proposed by Kim and Lee8, whose method is denoted by KimLee algorithm in this paper. Based on the KimLee algorithm, we propose a more effective management than that of KimLee algorithm. In our method, we do the cycle-leveling action in a balanced method and reduce the writing action to the flash memory block. Therefore, we not only can promote the effect of the system but also can prolong the service life in this flash memory. However, for the flash memory cell, it is mutually conflict between to reduce the cost of the clearance and to do the cycle-leveling action. First, we dynamically analyze the state of the data attribution. According to the data attribution, we divide this data into cold or hot data and rewrite it to the different block for reducing the nonsensical actions. Further, we can reduce the cost and promote the performance of the system. Then, we adopt a dynamic cycle-leveling strategy to extend the life of flash memory. It only needs to sacrifice a jot cost for extending the life of flash memory and promoting the high usage.Keywords:Embedded computing system, Flash memory, Storage system, File system, Cleaning strategy, Dynamically Cycle-leveling.壹、導 論隨者科技的進步，越來越多的電子產品都必須內建OS與記憶體。例如，個人數位助理、手機、數位相機、MP3隨身聽、和錄音筆。這些電子產品對於記憶體都有相同的需求，那就是必須體積小、容量大、省電、非揮發性和耐震等特性。傳統式的硬碟與記憶體已不能適用於這些新系統，因為EEPROM速度不夠快及容量有限，而DRAM與SRAM必須靠電力來維持記憶，硬碟則體積大、耗電又怕震動。因此，嵌入式系統的最佳解決方案直到快閃記憶體的問世，才解決這些問題。快閃記憶體和一般DRAM或SRAM最大不同是不需電源還能將資料保存的非揮發性記憶體4。它在體積方面，比一個容量相等的DRAM儲存格小，且隨者半導體製程的進步，其單位面積的儲存容量已經越來越大，存取速度也持續成長中，在用途上也漸漸取代移動式硬碟。並且它還具備移動式裝置最重視的兩種性能，省電及耐震。快閃記憶體將成為各種嵌入式計算系統的最佳記憶體解決方案。雖然快閃記憶體擁有多項優點，但卻有兩個硬體電氣上的限制5,6,15；那就是不能直接覆寫和抹除(Erase)次數的限制。首先，不能直接覆寫，在新資料儲存之前，原位置的資料區段必須先被抹除後，才能讓新資料重新寫入。而抹除運算重新設定所有記憶單元，所需要的時間比讀取或寫入運算的時間長。舉例，Toshiba TH58NVG1S3AFT05 2Gbit其讀的速度為50ns、寫的速度為200us、和抹除時間為2ms 15。而新的可用自由空間(Available free space，可立即使用的空間)必須建立在已預先抹除後，因此快閃記憶體更新的速度比傳統硬碟記憶體慢。第二個缺點，是覆寫次數的限制(一般在100,000 1,000,000次，依製造商而定)5,6,14。此兩缺點導致傳統式硬碟記憶體管理策略不適用於快閃記憶體。高可靠度和低成本效益快閃記憶體管理模式3因此必須針對快閃記憶體的缺點特性，重新設計快閃記憶體檔案系統。因為當一個接近週期限制的快閃記憶體區塊(Block)將經歷時常的寫入失敗；使得存入資料的可靠度降低。並且因為不平均的抹除區塊，致使可用記憶體空間快速的減少。如何讓記憶體區塊幾乎同時達到抹除次數界限，是我們演算法中研究的另一個重點，稱之為均勻抹除(Cycle-leveling)。為了解決不能直接覆寫缺點，我們必須考慮如何更新快閃記憶體區塊的資料和管理可用自由空間。對於更新技術，為了增進寫入效率，必須分離寫入和抹除運算。換句話說，更新時須將新資料寫入新自由空間中，並且將原區域空間上的舊版資料宣稱為無效。而當可用的記憶體空間不足時，系統必須啟動清除運算以回收舊資料空間和片段供未來使用。而抹除次數的限制缺點，在快閃儲存系統達成所有的記憶體區塊均勻使用的可能性，此程序被稱為均勻抹除。均勻抹除的基本原理，是將常被更新的資料安置在那些較少抹除次數的記憶體區塊中，不常更新的冷資料則被安置於那些已抹除較多次數的記憶體區塊中，藉此達到動態平衡。因降低清除花費與均勻抹除兩者是相互衝突。如果快閃記憶體管理將重心集中在降低清潔花費，則會因為片段間的抹除次數太過歪斜，使系統的可靠度戲劇性的受到影響。相反的，過度注重均勻抹除動作會增加額外的費用，而且降低了清除性能。本篇論文中，我們為快閃儲存系統中的兩個時常衝突的目標提出一個新的記憶體管理方法。我們主要透過蒐集運算以分開冷熱資料，並將冷熱資料分別存放於不同屬性的區段，以提高清潔效率。當選擇清除片段時，透過一清除索引，它整合了動態的均勻抹除與片段利用率兩個因素。因此，我們可解決清潔成本與均勻抹除兩者間的衝突。本篇論文的架構安排如下。在第二部份中描述快閃記憶體的工作原理。管理最佳化機制演算法的分析和改良在第三部份中討論。第四部份是結論。貳、工作原理為了提高寫入的速度，並且間接達到均勻抹除，我們採用日誌-結構化檔案系統(Log-Structure File System，簡稱LFS，log 即所有的更新動作實行在連續記憶體結構上稱4臺北科技大學學報第三十七之一期為日誌)的架構10。將所有新增或更新資料寫在日誌記錄的最後端，取代了直接更新檔案的方法；只須將舊資料標示為無效(Invalid)，並在某一特定時間啟動清除與抹除機制以回收記憶體區塊至可用的記憶體片段中；此非同步策略將有助於加快寫入效能。快閃記憶體出廠時，已將記憶體分割為數個固定的區塊，每個區塊再切割成數個大小相同的頁(Page)。此架構，正好符合LFS的需求。其中區塊是清除與抹除的單位，對應到LFS中的片段(Segment)，頁則是I/O的操作單位，也是快閃記憶體與主記憶體間資料交換的單位，對應到LFS中的區塊(Block)，以下我們將以片段和區塊來描述快閃記憶體。一、快閃記憶體管理架構本論文主要以KimLee演算法8為比較基礎。因此，只探討快閃記憶體管理部份，架構圖如圖(一)所示。快閃記憶體管理者由三個主要元件組成：分配者(Allocator)、清潔者(Cleaner)、和均勻抹除者(Cycle-Leveler)。分配者負責保存可用自由空間的片段；它決定那個可用自由空間片段(Available free segments)可在下一次分配給需求者(Requester)。清潔者是回收無效(Invalid)的區塊片段和產生新的可用自由空間。均勻抹除者負責維持快閃記憶體片段抹除週期的平均分配。圖(一)快閃儲存系統結構快閃記憶體管理工作如圖(二)所示。首先，在更新時，將目前片段中的舊資料區塊標記為死(Dead)，轉為陳舊資料區塊；並且將新的資料寫到一個新的可用自由區塊，標記活著(Live)，使變成有效資料區塊。當更新程序繼續時，可用自由片段數目將減少。當可用自由片段數目到達某一門檻以下的時候，清潔者被觸發。在快閃記憶體日誌工作上的清潔運算分兩個階段，重寫入和抹除階段。圖(二)快閃記憶體管理在重寫入階段，清潔者首先在日誌中選擇一個片段；分配一個可用自由片段；收集來自選擇片段中有效的資料，並且重寫到資料日誌檔中的結束部份；在抹除階段中，抹除運算的執行是對片段中，所有選擇抹除區塊平行處理。被清理的片段被收集進入可用自由空間的片段之內。高可靠度和低成本效益快閃記憶體管理模式5二、問題定義我們所定義清除花費模型的基礎是根據eNVy快閃儲存系統的清潔花費公式3。清潔花費在eNVy被定義為u/(1-u)，u是片段的利用率（代表有效資料所佔有的空間）。在快閃記憶體中，此花費模式所反映之事實為必須考慮重寫一個片段的有效區塊之費用。而一般硬碟的磁軌蒐尋和迴轉延遲時間並不適用於快閃記憶體，並且其讀取速度比寫入速度更快8。 對於快閃記憶體，在一個固定期間經常性的清潔，將會導致較高的整體運算費用。因此，清潔者應該將抹除（清潔）運算的數目減到最少。特別地，當片段的儲存利用值達到較高的時候，減少片段的利用被清潔是非常重要的8。而清潔頻率f在KimLee演算法中只是一個近似值如下列式子所示：上式並非一個真實的清潔次數，尤其當片段利用率有明顯差異時，其誤差值將比較大。因此，我們重新定義一個真實的清潔頻率，以表示真實的清潔次數。其中W表示在清潔開始之後的寫入請求區塊數目、uc表示清潔的選擇片段利用率、和SegSize表示每片段區塊數。然後，我們可以得知一個真實清潔頻率f值，如引理1所示。引理 1： 證明：清潔是以段為單位。從圖(二)中得知，一個段的清除可以產生(1-uc1)SegSize的可用自由空間。如果，清除兩個段，則將產生(1-uc1)SegSize+(1-uc2)SegSize的可再使用(新鮮)空間。同理，清潔三個段，將產生(1-uc1)SegSize+(1-uc2)SegSize+(1-uc3)SegSize=。 若要寫入資料為W區塊數目，至少必須清除大於W區塊數目，以便產生足夠的可用自由區塊數目。假設共清除f段(次)，則計算清潔頻率f的虛擬碼如下所示：CleaningFrequency( ) f ¬ 0 For i ¬0 to SegNum f = f+1; If (1-Uci)SegSize >W then Exit; Else W=W-(1-Uci)SegSize; End; If i ³ SegNum thenprintf “short of space”; Else Return f; End;6臺北科技大學學報第三十七之一期依據事實的須求，我們定義幾個參數。首先，由清潔頻率f所累積清潔費用如定義1所示8。定義1：累積的清潔費用是。關於平均抹除所有片段上的測量，我們使用齊平程度(Leveling degree)如定義2所示。 定義2：齊平程度(DÎ)是最大的抹除計數值（Îmax）和最小的抹除計數值（Îmin）之間的差。也就是DÎ =ÎmaxÎmin。再來，雖然使用蒐集家來分離冷熱資料有實質上的正面效果，但收集動作本身是一個運算成本。若太頻繁或太大量的收集，便會降低此效益；甚至增加運算的成本。因此，我們必須定義收集時期與收集大小，用來找到一個恰當的蒐集點。定義 3：收集時期 如果收集時期是n，則每n次清潔時間收集運算被呼喚一次8。定義4：收集大小 在每一次的收集時間從日誌檔中收集的冷資料區塊數目8。參、管理的最佳化與演算法改良首先，我們介紹一個基本的清潔方法10-11；再介紹KimLee演算法。並將其管理方法上冷資料(Cold data)與熱資料(Hot data)的分離政策、清潔片段選擇、與抹除均勻策略上的缺點逐一提出改良，以得到一個最佳化的管理效能。一、貪婪演算法的缺點對於快閃記憶體，清除策略演算法的效率直接影響系統效能3,10。此外，依照eNVy的清潔花費模式，由片段利用率決定片段的清潔費用3。因此，如何挑選一個片段進行清除，將是影響成本的最重要因素。直覺地，期待選擇那些最少有效資料區塊的片段是比較有利於節省清潔費用，此乃貪婪清潔法9-10。貪婪清潔法選擇節段的方式是尋找節段內有最多數量的舊資料作回收，目的在花最少的成本以期待獲得較大的回收空間。在存取行為比較平均的情況下，貪婪清潔法與其他清除策略並不會相差太多1。當存取行為有高度集中的情況下(比較符合實作的系統，根據研究在UNIX檔案系統中，有6778%寫入行為集中在少數的檔案上12-13)，貪婪清潔法的抹除與搬移次數會有急速增加趨勢3,7,10。主要原因為貪婪清潔法在挑選節段時，無法有效辨別資料冷熱狀態。因此，會造成剛更新後的節段內迅速增加新的舊區塊，導致再次進入準備被抹除的狀態(忽略了再增加陳舊資料的機會)，而使得效率下降。更進一步，因為貪婪法不能有效的分離冷熱資料，使得冷熱資料同時存在每一個片段裡，造成在每次的清潔時冷資料無益的到處搬移，再度造成降低系統效能。高可靠度和低成本效益快閃記憶體管理模式7二、冷熱資料分離為了解決貪婪清潔法的缺點，在KimLee中提出一收集運算，自熱的資料區段中隔離出冷資料。實際上，這被實行於另一個模式，稱為快閃記憶體管理員的蒐集家。清潔者定期啟動蒐集家，收集日誌中的冷資料碎片。KimLee演算法冷熱資料分離缺點在KimLee演算法中，其冷熱資料分離是藉由蒐集家來完成。其工作分兩個階段：(1)搜尋並且收集冷資料(檔案)區塊碎片；(2)群集冷資料至日誌的尾端，收集運算程序，如圖(三)所示。圖(三)收集程序在第一階段中的在每個收集時間，蒐集家決定收集大小並且在很多的碎片中搜尋冷資料。令收集大小單位為10，而且當很多碎片的冷資料在檔案a和b被收集是可能的，如圖(三)所示。在第二階段中，檔案的區塊被寫入至日誌的後面，直到達收集大小的值為止。如果收集的程序期間可用自由空間不是充足，清潔者可被喚醒，以產生新的可用空間8。由以上的運算模式中，我們研究結果，有下列結論。在KimLee演算法的蒐集家運作中，雖然在第一階段中已將冷資料收集出來，但在第二階段中，將冷資料寫入至日誌的後端，且可能未填滿整個區段。使得後來檔案管理系統因為對某一檔案更新，將一個熱資料寫入日誌的尾端，造成冷熱資料再度的混合；因此，影響整體冷熱資料分離程度的效能。針對此冷熱資料分離缺點我們提出改進方法。冷熱資料分離缺點的改進方式因為一般的LFS結構僅有一個使用中的資料區段LFS與可用自由空間的資料區段8臺北科技大學學報第三十七之一期LFS，在KimLee分離演算法中採用檔案來區別冷熱資料，要收集剛好一個片段大小的資料量是較困難的。因此，無法有效的分離冷熱資料，進而影響整體效能。我們的策略是將快閃記憶體使用中的資料區段分為兩類。一類存放常更新的檔案即熱資料；另一類存放不常更動的資料檔或是唯讀檔即冷資料。每一個節段在快閃記憶體剛起始或經回收至可用自由片段內後，都不具有任何屬性。在存有資料區塊後，會視所存放資料檔屬性，而成為熱片段或冷片段，即常更新或不常更新片段。此後，當蒐集家收集冷資料時，便將其重寫入冷資料片段LFS中的日誌尾端如圖(四)所示，更新或清除資料時則將資料重寫入到熱資料LFS中的日誌尾端，如此可改善冷熱資料混合機率。因此，我們有引理2改善散冷熱資料的混合機率。圖(四)冷資料收集示意圖引理2：當收集冷資料時，將其寫入到冷資料片段LFS中的日誌尾端和當更新或抹除片段時將片段中的有效資料重寫入到熱資料LFS中的日誌尾端，可以改善冷熱資料混合的機率。高可靠度和低成本效益快閃記憶體管理模式9三、均勻抹除快閃記憶體因為有抹除次數的限制，比如Toshiba TH58NVG1S3AFT05 2Gbit，其抹除次數為100,000次15。假若某個片段中存在永遠不被更新的唯讀檔，此時非均勻抹除將嚴重發生。若系統中存在多數的冷資料片段(不被抹除)，則快閃記憶體將因為輪替抹除的區段變少，而增加抹除次數。使得快閃記憶體容量因抹除次數極限值的到達，而降低可用的記憶體空間。舉例，某一快閃記憶體有100個抹除片段，每一個片段的抹除次數為100,000次；假若其儲存空間中永遠包含著30個片段的冷資料，其使用率永遠很高不會被系統回收抹除，故僅剩下70個片段來輪流使用抹除。假設在一個高密度寫入的情況下，每天有5000個片段抹除回收需求(不考慮抹除不均勻)，則其記憶體100%可用的使用壽命為：100%生命週期=。換句話說，當經過3.836年後，其記憶體空間僅剩下30%。那就是只剩存著冷資料的片段可再被使用。而此30%也將會因為記憶體空間不足，而需更頻繁的抹除而快速達到極限值。在上式中並未考慮因為抹除不均勻，使得可用空間急速減少，而需付出的額外抹除次數。若我們在系統中考慮均勻抹除，則此100個片段的抹除次數差異將會控制在某一範圍內，使其幾乎同時達到抹除界限值。在記憶體使用上，也會有較大的空間與彈性，假設均勻抹除必須額外付出8%清除費用8，此時的使用壽命為：100%生命週期=由以上論述可知，雖然均勻抹除需付出額外的清潔費用，但在可靠度與大記憶體空間及壽命延長是非常值得的。KimLee演算法清潔索引策略的缺點清潔索引(CleaningIndex)是選擇片段被清理的準則；最低的索引數值片段，將在清潔時被選擇8。清潔索引定義了降低清潔花費及提高均勻抹除兩者如下：上式中ui表示片段i的利用率、Îi表示抹除計數、和Îmax是表示最大的抹除計數值。清潔索引由二個因素組成：每個片段的利用率和抹除計數。正規化齊平度是此二個因數的加權，使用表示。計算出的齊平度映射到0到1之間的數值。l= 如果抹除是均勻分配，則清潔索引是使用在降低清潔費用。相反的，當發生不均勻(嚴重歪斜)抹除動作時，清潔索引的工作，是為了均勻抹除。換句話說，在正常運作時，當此齊平度在可容忍的臨限之下（的數值接近0）時，ui利用率必定是選擇一個片段的主要因數。當此齊平度超過可容忍的界限（的數值接近1）時，則清潔索引應該被計算考慮此兩10臺北科技大學學報第三十七之一期因數，或偏重均勻抹除。此演算法的立意甚佳，當片段選擇時，須要同時考慮清潔成本與均勻抹除。但此公式卻有一個嚴重缺點，即當片段越接近抹除極限值時，卻疏失於均勻抹除參數，而偏重使用率的參數。是因為(Îi/Îmax+1)抹除權重因子所造成。當快閃記憶體越接近抹除極限值時，(Îi/Îmax+1)抹除權重因子會接近於1，不會有太大的差距，使的清潔索引值僅由利用率來判斷選擇，容易造成高抹除的片段因為可能有低的利用率，再度被清潔與抹除，使的系統壽命縮短。此現象嚴重違反延長壽命的使用規則。舉例，設kÎ值 = 500，DÎ = 400，則標準齊平度 = 0.62，我們考慮不同抹除次數下的片段選擇策略如下。例 1：片段a：ui=0.8，Îi=1000，Îmax=1350，Îmin=950CleaningIndex=(1-0.62)×0.8+0.62×1000/(1350+1)=0.763 片段b：ui=0.5，Îi=1330，Îmax=1350，Îmin=950CleaningIndex=(1-0.62)×0.45+0.62×1330/(1350+1)=0.781例 2：片段a：ui=0.8，Îi=91000，Îmax=91350，Îmin=950CleaningIndex=(1-0.62)×0.8+0.62×91000/(91350+1)=0.922片段b：ui=0.5，Îi=91330，Îmax=91350，Îmin=950CleaningIndex=(1-0.62)×0.45+0.62×91330/(91350+1)=0.790由上面例1中，可以很容易發現片段a與片段b抹除次數相差1330-1000=330次，與最大抹除次數則各相差350次及20次。為達到均勻抹除，本公式選擇片段a，因為它有較小的清潔索引值；但是在例2中，被選擇片段抹除次數也是相差330次，與最大抹除次數同樣各相差350及20次，其餘條件也與例1相同，片段b卻有較小的清潔索引值，結果完全與例1相反。在可靠度及壽命而言，快閃記憶體當越接近抹除極限值時，必須越考慮均勻抹除，但本公式剛好適得其反，是一大缺點。清潔索引策略缺點的改進為了改善KimLee的清潔索引公式，我們修正其清潔索引公式如下：為了方便說明，重新計算與使用節的範例。例 1：片段a：ui=0.8，Îi=1000，Îmax=1350，Îmin=950CleaningIndex =(1-0.62)×0.8+0.62×(1000-950)/(1350-950+1)= 0.381片段b：ui=0.5，Îi=1330，Îmax=1350，Îmin=950CleaningIndex =(1-0.62)×0.45+0.62×(1330-950)/(1350-950+1) = 0.758例 2：片段a： ui=0.8，Îi=91000，Îmax=91350，Îmin=90950CleaningIndex =(1-0.62)×0.8+0.62×(91000-90950)/(91350-90950+1)=0.381 片段b：ui=0.5，Îi=91330，Îmax=91350，Îmin=90950CleaningIndex=(1-0.62)×0.45+0.62×(91330-90950)/(91350-90950+1)=0.758從上面計算得知，我們已經改善了KimLee在越接近抹除界限值時，並不注重均勻抹除的缺點。因此，我們有引理3，如下所示。無論如何，均勻抹除總是會增加清除費用，越是嚴謹的均勻抹除其費用越高；但是越鬆弛的均勻抹除，其可靠度與壽命越低。如何取得一個平衡點是我們本篇論文的另一重點，我們提出一種動態式均勻抹除的方法來達成此平衡點的任務。引理3：我們的CleaningIndex可整體改善在KimLee演算法中接近抹除界限值時的缺點。高可靠度和低成本效益快閃記憶體管理模式11動態式均勻抹除策略一個快閃記憶體其抹除界限值為100,000次。換句話說，在片段被抹除100,000以前，我們不必擔心其抹除界限值的到達。因此，對於均勻抹除我們可以採用漸進嚴謹的策略。一開始時因為不必擔心片段抹除極限的到達，所以我們讓kÎ值取較大，且讓kÎ值隨者最大抹除次數的增加而漸漸往下調整。讓快閃記憶體管理系統在一開始時到最大抹除界限之前，可以加重考量片段使用率。如此，可降低清除費用。當最大抹除次數越接近抹除極限值時，常數kÎ值變的越小時，我們可以使得漸漸注重均勻抹除。讓系統的片段壽命幾乎同時到達，也可提高整體系統的可靠度。如下圖(五)所示，當kÎ值越大時，l值越小，由CleaningIndex公式中知道越不注重均勻抹除，相反的kÎ值越小時，l值越大表示越注重均勻抹除。圖(五)改變kÎ時的l變化曲線圖所以，我們可以用一個動態kÎ值來降低因為均勻抹除所需付出的額外成本，kÎ變數如下：EraseLimit：為快閃記憶體的抹除界限分子與分母各加是為了去除初始值，kÎ的極劇變化，使一開始差異如下圖(六)與圖(七)所示。m和n為常數，其中m決定了kÎ值曲線的變化度與抹除成本；n則決定最後抹除極限值屆臨的嚴僅度。值越大費用越低，但可靠度與均勻抹除越差，值越低清除費用越高，可靠度與均勻抹除越佳。我們以m,n各為100來模擬kÎ變化曲線如圖(七)所示。圖(六)未加0.001EraseLimit的kÎ 變化圖12臺北科技大學學報第三十七之一期圖(七)加上0.001EraseLimit的kÎ 變化圖由圖(七)中得知，我們的KÎ一開始很大，約1096，接著最大抹除次數Îmax的增加，kÎ值變小。當最大抹除次數到10000次時，KÎ值為430，如圖(七)中的a點。到了90000次時，KÎ值變為115，如圖(七)中的b點。最後當最大抹除片段值達到極限值時KÎ值變成100，因此我們可以得到一個從1096變化到100的動態KÎ值，若需更大變化範圍僅需調整m值即可(當m=500時，我們可以得到一個從5083變化到100的動態KÎ值)。配合圖(五)及CleaningIndex公式我們可以知道，這樣的kÎ值變化可以使我們的系統在一開始僅考慮片段利用率，隨著抹除次數的增加漸漸注重均勻抹除，如此動態式的均勻抹除必可降低KimLee的清除費用，並且會有一嚴謹的可靠度。因此，我們有引理4，如下所示。引理4：我們的動態式均勻抹除策略，不但可降低整體清除費用，而且可提高整體系統的可靠度。為了說明KimLee演算法的缺點，我們在此舉例說明，在KimLee 中kÎ是使用一固定常數100作模擬。假設齊平程度值是200，則在KimLee中其l值不論最大抹除次數為何皆保持0.7551，明顯偏重均勻抹除。但是套到我們的公式中(m,n各取100)，我們可發現不同的結果，當Îmax = 1000時，l=0.0458；當Îmax = 10000時，l=0.2078；當Îmax = 50000時，l=0.5382；當Îmax = 90000時，l=0.7197；當Îmax = 100000時，l=0.7551，最後模擬出如圖(八)之曲線值。由圖(八)中之曲線，我們可知在初期l非常小，因此我們並不考慮均勻抹除，使系統省下了可觀的清潔費用。慢慢的注重均勻抹除，到最後抹除極限時，我們擁有和KimLee相同的抹除重視程度，甚至我們可將常數m調大一點，n調小一點，便可擁有更低的清潔費用與更嚴謹的可靠度；但是並不是意味者m調到無窮大，n調到接近0是最好的，m太大曲線變化過劇，n太小則會使的接近抹除極限時，kÎ值過小，使系統為了均勻抹除而做無謂的般移，浪費效能與壽命。圖(八)動態kÎ與固定kÎ 所產生的l比較圖高可靠度和低成本效益快閃記憶體管理模式13考量冷熱區段屬性的清潔索引公式在真實系統的應用中，我們知道資料存取有其慣性與重複參考的傾向2。也就是常更動的資料我們也預期它會保持經常更動的屬性；屬性偏冷的資料檔則不易更新甚永不更新，如唯讀檔。所以我們考慮屬性屬於熱的片段，會有很大的機會再增加新的舊資料，因此清潔索引在挑選這一類片段的機率應該降低。相反的屬性屬於冷的資料片段，因為本身被更新的機會較少，因此我們應該調整權重讓其比相等值的熱片段多一點被清除的機會。所以我們將清潔索引再加入屬性常數h，若該屬性為熱資料區段則h值等於1；冷資料區段屬性則h值介於0.90.99之間。因為我們不希望區段屬性權重過小，進而影響到整體效能，最後修正後的公式如下，最低的清潔索引值優先被選擇。ui選擇片段i的利用Îi選擇片段i的抹除計數Îmin是最小的抹除計數值Îmax是最大的抹除計數值表示標準齊平度映射在0和1之間h代表片段屬性值，hot=1，cold=0.90.99間四、片段分配政策為了達到快閃記憶體的均勻抹除效果，單靠清潔政策是無法達成的；因為可能某一片段其抹除(比齊平度)太過歪斜，使得清潔索引計算時，為所有片段中最小索引值，而回收到自由片段中。但不幸的，若沒有一個有效的片段分配政策，在下一次分配中，可能分配給熱資料屬性的檔案，使得該片段因為更新，快速成為陳舊資料與抹除太過歪斜；而造成系統再次回收，無法達成均勻抹除效果。因此，我們必須有一個適當的片段分配政策。首先我們發現片段分配在三種情況下發生。第一：當系統更新檔案時，必須重寫新資料至日誌的尾端；第二：當系統做清除時，必須將片段中剩餘的有效資料複製到日誌的尾端；第三：當系統執行收集政策時，必須將收集的冷資料碎片寫到日誌的尾端。當這三種情況下，若日誌剩餘的空間不足寫入時，便會向系統要求一新空間。若屬於第一及第二種情況，片段分配政策盡量挑選最少抹除次數的片段作為分配，因為熱資料屬性，會讓該片段檔案更新，使的迅速累積無效的舊資料，而再次回收，拉平抹除均勻度。至於第三種形況，因為蒐集家所蒐集的為冷資料檔案，我們能預期它被更新的機會不多，因此片段分配政策必須分配一個最大抹除次數的片段給該資料，因此，我們便可達到均勻抹除的效果，如引理5所示。引理5：我們的片段分配政策可達成均勻抹除。肆、結 論雖然KimLee演算法已經改善快閃記憶體的兩大缺點。但其演算法在架構上仍有些缺陷，致使清除費用增加與壽命延長不足。我們提出的改良式架構，將冷、熱資料分別置於不14臺北科技大學學報第三十七之一期同屬性的片段中，改善冷熱資料再度混合的機率，達到降低抹除費用與次數的功效，進而提高系統壽命。我們也對清潔索引的缺點提出改善方法。那就是當快閃記憶體越趨近抹除界限值時，不因均勻抹除越寬鬆，而造成可靠度嚴重的受考驗，且加入一動態KÎ值來降低均勻抹除所需付出的額外成本。更進一步，此可提高系統壽命與可靠度。最後，我們在清潔索引中加入片段屬性常數h，藉此來降低清潔費用。參考文獻1T. Blackwell, J. Harris, and M. Seltzer, “Heuristic Cleaning Algorithms in Log- Structured FileSystems”, Proceedings of the 1995 USENIX Technical Confer-ence, pp. 277-288, 1995.2P. J. Denning, “Working sets past and present,” IEEE Trans. on Software Eng., Vol. 6, No.1, pp. 64-84, 1980.3M. Wu and W. Zwaenepoel, “eNVy: A non- volatile main memory storage system,” Proc. ASPL94, pp. 86-97, 1994.4Intel, What is Flash Memory ? http:/www. 2003.5Intel Datasheet, /design/flcomp/specupdt/29813017.pdf, August 2003.6Intel Datasheet, design/flcomp/PRODBREF/298044.htm, August 2003.7A. Kawaguchi, S. Nishioka, and H. Motoda, “Flash memory based file system,” Proc. USENIX95, pp.155-164, 1995.8H. J. Kim and S. G. Lee, “An Effective Flash Memory Manager for Reliable Flash Memory Space Management,” IEICE Trans. Information & System, Vol. E85-D, No. 6, pp. 951-964, June 2002.9J. N. Matthews, D. Roselli, A. M. Costello, R. Y. Wang, and T. E. Anderson, Improving the Performance of Log-Structured File Systems with Adaptive Methods, Proceedings of the Sixteenth ACM Sympo. on Operating System Principles, pp. 5-8, Oct. 1997.10M. Rosenblum and J. K. Ousterh