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

61高可靠度和低成本效益快閃記憶體管理模式FlashMemoryManagementModelwithHighReliabilityandLowCost-Benefit黃文增*陳彥勝陳俊達鄭重志W.T.Huang*,Y.S.Chen,C.T.Chen,C.C.Cheng國立台北科技大學電子工程系摘要快閃記憶體可說是目前嵌入式系統記憶體的主流，而其有效的管理方式已被提出，其中以Kim和Lee所提出的管理方式最具代表性，我們簡稱為KimLee演算法[8]。本論文主要是以KimLee演算法為基礎，提出一個改良式的有效管理方法。我們的方法主要是針對快閃記憶體區塊作均勻抹除和減少抹除的動作；因此，快閃記憶體不但可以提升系統的效能降低清除成本而且能延長使用壽命。然而，快閃記憶單元的降低清除成本與均勻抹除兩者是相互衝突的；如何兩全其美取得一平衡點，是本論文的重點。首先，我們的方法是藉由動態的分析資料屬性，分離成冷資料與熱資料，並將其重寫於不同區段屬性中，以達到降低無意義的搬移動作，更進一步，能降低成本及提高系統壽命。第二目標是採用一種動態的均勻抹除策略，來提昇可靠度；而此方法最大效益是只需要犧牲少量的成本，便可達到延長快閃記憶體的壽命與使用的高可靠度。關鍵詞：嵌入式計算系統、快閃記憶體、儲存系統、檔案系統、清除策略、動態均勻抹除。投稿受理時間:92年10月15日審查通過時間:92年12月24日高可靠度和低成本效益快閃記憶體管理模式162ABSTRACTAmongthevariouslyeffectivemanagementsoftheflashmemory,themajorrepresentativemethodisproposedbyKimandLee[8],whosemethodisdenotedbyKimLeealgorithminthispaper.BasedontheKimLeealgorithm,weproposeamoreeffectivemanagementthanthatofKimLeealgorithm.Inourmethod,wedothecycle-levelingactioninabalancedmethodandreducethewritingactiontotheflashmemoryblock.Therefore,wenotonlycanpromotetheeffectofthesystembutalsocanprolongtheservicelifeinthisflashmemory.However,fortheflashmemorycell,itismutuallyconflictbetweentoreducethecostoftheclearanceandtodothecycle-levelingaction.First,wedynamicallyanalyzethestateofthedataattribution.Accordingtothedataattribution,wedividethisdataintocoldorhotdataandrewriteittothedifferentblockforreducingthenonsensicalactions.Further,wecanreducethecostandpromotetheperformanceofthesystem.Then,weadoptadynamiccycle-levelingstrategytoextendthelifeofflashmemory.Itonlyneedstosacrificeajotcostforextendingthelifeofflashmemoryandpromotingthehighusage.Keywords:Embeddedcomputingsystem,Flashmemory,Storagesystem,Filesystem,Cleaningstrategy,DynamicallyCycle-leveling.壹、導論隨者科技的進步，越來越多的電子產品都必須內建OS與記憶體。例如，個人數位助理、手機、數位相機、MP3隨身聽、和錄音筆。這些電子產品對於記憶體都有相同的需求，那就是必須體積小、容量大、省電、非揮發性和耐震等特性。傳統式的硬碟與記憶體已不能適用於這些新系統，因為EEPROM速度不夠快及容量有限，而DRAM與SRAM必須靠電力來維持記憶，硬碟則體積大、耗電又怕震動。因此，嵌入式系統的最佳解決方案直到快閃記憶體的問世，才解決這些問題。快閃記憶體和一般DRAM或SRAM最大不同是不需電源還能將資料保存的非揮發性記憶體[4]。它在體積方面，比一個容量相等的DRAM儲存格小，且隨者半導體製程的進步，其單位面積的儲存容量已經越來越大，存取速度也持續成長中，在用途上也漸漸取代移動式硬碟。並且它還具備移動式裝置最重視的兩種性能，省電及耐震。快閃記憶體將成為各種嵌入式計算系統的最佳記憶體解決方案。雖然快閃記憶體擁有多項優點，但卻有兩個硬體電氣上的限制[5,6,15]；那就是不能直2臺北科技大學學報第三十七之一期63接覆寫和抹除(Erase)次數的限制。首先，不能直接覆寫，在新資料儲存之前，原位置的資料區段必須先被抹除後，才能讓新資料重新寫入。而抹除運算重新設定所有記憶單元，所需要的時間比讀取或寫入運算的時間長。舉例，ToshibaTH58NVG1S3AFT052Gbit其讀的速度為50ns、寫的速度為200us、和抹除時間為2ms[15]。而新的可用自由空間(Availablefreespace，可立即使用的空間)必須建立在已預先抹除後，因此快閃記憶體更新的速度比傳統硬碟記憶體慢。第二個缺點，是覆寫次數的限制(一般在100,000~1,000,000次，依製造商而定)[5,6,14]。此兩缺點導致傳統式硬碟記憶體管理策略不適用於快閃記憶體。因此必須針對快閃記憶體的缺點特性，重新設計快閃記憶體檔案系統。因為當一個接近週期限制的快閃記憶體區塊(Block)將經歷時常的寫入失敗；使得存入資料的可靠度降低。並且因為不平均的抹除區塊，致使可用記憶體空間快速的減少。如何讓記憶體區塊幾乎同時達到抹除次數界限，是我們演算法中研究的另一個重點，稱之為均勻抹除(Cycle-leveling)。為了解決不能直接覆寫缺點，我們必須考慮如何更新快閃記憶體區塊的資料和管理可用自由空間。對於更新技術，為了增進寫入效率，必須分離寫入和抹除運算。換句話說，更新時須將新資料寫入新自由空間中，並且將原區域空間上的舊版資料宣稱為無效。而當可用的記憶體空間不足時，系統必須啟動清除運算以回收舊資料空間和片段供未來使用。而抹除次數的限制缺點，在快閃儲存系統達成所有的記憶體區塊均勻使用的可能性，此程序被稱為均勻抹除。均勻抹除的基本原理，是將常被更新的資料安置在那些較少抹除次數的記憶體區塊中，不常更新的冷資料則被安置於那些已抹除較多次數的記憶體區塊中，藉此達到動態平衡。因降低清除花費與均勻抹除兩者是相互衝突。如果快閃記憶體管理將重心集中在降低清潔花費，則會因為片段間的抹除次數太過歪斜，使系統的可靠度戲劇性的受到影響。相反的，過度注重均勻抹除動作會增加額外的費用，而且降低了清除性能。本篇論文中，我們為快閃儲存系統中的兩個時常衝突的目標提出一個新的記憶體管理方法。我們主要透過蒐集運算以分開冷熱資料，並將冷熱資料分別存放於不同屬性的區段，以提高清潔效率。當選擇清除片段時，透過一清除索引，它整合了動態的均勻抹除與片段利用率兩個因素。因此，我們可解決清潔成本與均勻抹除兩者間的衝突。本篇論文的架構安排如下。在第二部份中描述快閃記憶體的工作原理。管理最佳化機制演算法的分析和改良在第三部份中討論。第四部份是結論。貳、工作原理為了提高寫入的速度，並且間接達到均勻抹除，我們採用日誌-結構化檔案系統(Log-StructureFileSystem，簡稱LFS，log即所有的更新動作實行在連續記憶體結構上稱高可靠度和低成本效益快閃記憶體管理模式364為日誌)的架構[10]。將所有新增或更新資料寫在日誌記錄的最後端，取代了直接更新檔案的方法；只須將舊資料標示為無效(Invalid)，並在某一特定時間啟動清除與抹除機制以回收記憶體區塊至可用的記憶體片段中；此非同步策略將有助於加快寫入效能。快閃記憶體出廠時，已將記憶體分割為數個固定的區塊，每個區塊再切割成數個大小相同的頁(Page)。此架構，正好符合LFS的需求。其中區塊是清除與抹除的單位，對應到LFS中的片段(Segment)，頁則是I/O的操作單位，也是快閃記憶體與主記憶體間資料交換的單位，對應到LFS中的區塊(Block)，以下我們將以片段和區塊來描述快閃記憶體。一、快閃記憶體管理架構本論文主要以KimLee演算法[8]為比較基礎。因此，只探討快閃記憶體管理部份，架構圖如圖(一)所示。快閃記憶體管理者由三個主要元件組成：分配者(Allocator)、清潔者(Cleaner)、和均勻抹除者(Cycle-Leveler)。分配者負責保存可用自由空間的片段；它決定那個可用自由空間片段(Availablefreesegments)可在下一次分配給需求者(Requester)。清潔者是回收無效(Invalid)的區塊片段和產生新的可用自由空間。均勻抹除者負責維持快閃記憶體片段抹除週期的平均分配。作業系統檔案管理快閃記憶體管理快閃記憶體存取介面快閃記憶體區塊均勻抹除快閃記憶體管理主要內容分配清潔圖(一)快閃儲存系統結構快閃記憶體管理工作如圖(二)所示。首先，在更新時，將目前片段中的舊資料區塊標記為‘死’(Dead)，轉為陳舊資料區塊；並且將新的資料寫到一個新的可用自由區塊，標記活著(Live)，使變成有效資料區塊。當更新程序繼續時，可用自由片段數目將減少。當可用自由片段數目到達某一門檻以下的時候，清潔者被觸發。在快閃記憶體日誌工作上的清潔運算分兩個階段，重寫入和抹除階段。(3)複製(1)選擇LFS快閃記憶體片段均勻抹除者清除者分配者(4)抹除回收(2)分配片段有效資料區塊陳舊資料區塊可用自由區塊日誌尾端圖(二)快閃記憶體管理在重寫入階段，清潔者首先在日誌中選擇一個片段；分配一個可用自由片段；收4臺北科技大學學報第三十七之一期65集來自選擇片段中有效的資料，並且重寫到資料日誌檔中的結束部份；在抹除階段中，抹除運算的執行是對片段中，所有選擇抹除區塊平行處理。被清理的片段被收集進入可用自由空間的片段之內。二、問題定義我們所定義清除花費模型的基礎是根據eNVy快閃儲存系統的清潔花費公式[3]。清潔花費在eNVy被定義為u/(1-u)，u是片段的利用率（代表有效資料所佔有的空間）。在快閃記憶體中，此花費模式所反映之事實為必須考慮重寫一個片段的有效區塊之費用。而一般硬碟的磁軌蒐尋和迴轉延遲時間並不適用於快閃記憶體，並且其讀取速度比寫入速度更快[8]。對於快閃記憶體，在一個固定期間經常性的清潔，將會導致較高的整體運算費用。因此，清潔者應該將抹除（清潔）運算的數目減到最少。特別地，當片段的儲存利用值達到較高的時候，減少片段的利用被清潔是非常重要的[8]。而清潔頻率f在KimLee演算法中只是一個近似值如下列式子所示：SegSizeuWfc)1(上式並非一個真實的清潔次數，尤其當片段利用率有明顯差異時，其誤差值將比較大。因此，我們重新定義一個真實的清潔頻率，以表示真實的清潔次數。其中W表示在清潔開始之後的寫入請求區塊數目、uc表示清潔的選擇片段利用率、和SegSize表示每片段區塊數。然後，我們可以得知一個真實清潔頻率f值，如引理1所示。引理1：SegSizeWuffici1)(證明：清潔是以段為單位。從圖(二)中得知，一個段的清除可以產生(1-uc1)SegSize的可用自由空間。如果，清除兩個段，則將產生(1-uc1)SegSize+(1-uc2)SegSize的可再使用(新鮮)空間。同理，清潔三個段，將產生(1-uc