以區塊為基礎之反及閘快閃記憶體管理模式

1、以區塊為基礎之反及閘快閃記憶體管理模式The Nand Type Flash Memory Management Model based on the Block Base以區塊為基礎之反及閘快閃記憶體管理模式164黃文增*W. T. Huang*陳俊達C. T. Chen陳彥勝Y. S. Chen劉倉吉C. C. Liu國立台北科技大學電子工程系摘 要反及閘快閃記憶體(NAND Type Flash，簡稱NandFlash)，是嵌入式計算系統中記憶體的應用主流之一，主要因為NandFlash具有體積小、省電、非揮發性和耐震等特性。由於快閃記憶體具有特殊半導體特性，不僅限制其運用而且導致管理方

2、法複雜化，所以如何有效率管理快閃記憶體，已經成為一項重要研究議題。特別當所管理的記憶體容量愈大時，有效管理機制的重要性將愈被彰顯。在探討文獻中，以Kim和Lee所提出的快閃記憶體管理方式最具其代表性，簡稱為KimLee演算法10。本論文主要以NandFlash為基礎，提出一管理方法，並對KimLee文中未探討之處加以補充。我們所提方法中，是以區塊為研究基礎，因區塊為NandFlash中抹除的基本單位，以區塊作為探討基礎最為貼切。文中探討損壞區塊、均勻抹除、減少抹除頻率及無效資料頁回收之管理。然而，NandFlash管理中的單元抹除成本與均勻抹除兩者間的關係是相互衝突的；因此如何取得系統管理平衡

3、點是一重點。藉由動態方式分析資料屬性，分離成冷資料屬性與熱資料屬性，並將其資料寫至不同屬性區塊中，以降低無意義的搬移動作。動態均勻抹除策略可提昇可靠度，而此方法最大效益是只需要犧牲少量成本，可達到延長使用壽命與提高可靠度。再經由本文所提出的分配政策指標與抹除策略互相搭配，成效亦可彰顯。 關鍵詞：嵌入式計算系統、快閃記憶體、反及閘快閃記憶體、抹除策略、動態均勻抹除、分配政策。投稿受理時間：93年3月15日 審查通過時間：93年8月2日64臺北科技大學學報第三十七之二期ABSTRACTThe NAND type flash, denoted by NandFlash, is on of the m

4、ajor applications in the embedded computing system, since it owns some advantages, the small size, great capacity, light power consummation, not volatility, and enduring vibration. For the special characteristic of the semi-conductor in NandFlash, its applications will be limitation and its manager

5、method will also be complication. It is a major study topic to effectually manage this NandFlash. Especially, when a file system manages the huge size NandFlash, the performance of management mechanism will be more importance. Among the variously effective managements of the flash memory, the major

6、representative method is proposed by Kim and Lee10, 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 proposal, since the basic erasing unit is a block in NandFlash, we use a block as

7、the study basis with the meaning. We discuss the bad block management, the wear-leveling algorithm, the reduction of the erasing frequency, and the management of the invalid page data recovery. For conflicting between the unit cost of erasing cost and wear-leaving algorithm, it is another important

8、issue to get the balance between the clearance and to do the cycle-leveling action.By dynamically analyzing the state of the data attribution, the data is divided into cold or hot data attribution and then re-written into the different block for reducing the nonsensical actions. Further, we can redu

9、ce the cost and promote the performance of the system. It only needs to sacrifice a jot cost for extending the life of flash memory and promoting the high usage. The performance will be more explicit with the allocation strategy index and the cycle-leveling strategy of our proposal model.Keywords: E

10、mbedded computing system, Flash memory, NAND flash memory, Cleaning strategy, Dynamically Cycle-leveling, Allocation strategy.壹、導 論隨著科技的進步，越來越多可攜式電子產品都必須內建作業系統(Operating System, OS)與非揮發性的記憶體。例如，個人數位助理、手機、數位相機、MP3隨身聽和錄音筆 19。而快閃記憶體符合以上電子產品之需求，成為近年來可攜式電子產品所必備使用的新寵兒。以區塊為基礎之反及閘快閃記憶體管理模式3可攜式電子產品對於記憶體都有相同的

11、需求，例如：體積小、容量大、功率小、非揮發性和耐震等特性。因此，傳統式的硬碟與記憶體已不適用於新的可攜式系統。快閃記憶體和一般DRAM或SRAM最大不同處，在於當無電源時快閃記憶體能保存資料完整性，是屬於非揮發性記憶體6。並且快閃記憶體具備省電功能及耐震，在移動式裝置運用中是最佳儲存媒介，因此快閃記憶體成為嵌入式計算系統最佳記憶體解決方案。NandFlash結構適合於純資料儲存和檔案存儲，例如主要作為SmartMedia卡、CompactFlash卡、PCMCIA ATA卡、固態盤式儲存介質。NandFlash具有以下基本特點：一、以資料頁(Page)作為單位進行讀取和編程操作，1資料頁單位為

12、512B（位元組）或2KB；以區塊(Block)為單位進行抹除，1區塊單位為16KB或128KB。二、資料和位址線採用同一匯流排(Bus)，實現串列讀取。三、晶片尺寸小及引腳少。四、晶片包含損壞區塊，其數目最大上限達NandFlash容量的1%，此損壞區塊取決於記憶體密度16-17。雖然NandFlash具有多項優點，但有兩項硬體電氣上的限制7-8,16-17，不能直接覆寫和抹除次數限制。首先，不能直接覆寫方面，在新資料儲存之前，原位置的資料區塊必須先被抹除後，新資料才能重新寫入。而覆寫次數的限制方面，一般而言NandFlash抹除次數為100,000次，依製造商而定7-8,16-17。這兩缺

13、點導致傳統式硬碟記憶體管理策略，不適用於快閃記憶體，因此NandFlash管理系統演然而生。因此必須針對NandFlash本身的限制，設計其NandFlash檔案管理系統。在NandFlash中，當一個區塊接近抹除限制時，將會導致寫入失敗，使得資料存取可靠度降低。而非均勻式抹除區塊現象，導致可用記憶體空間快速減少，因此如何均勻化使得NandFlash所有區塊幾乎同時達到抹除次數界限，稱之均勻抹除(Wear-leveling)。換言之，在NandFlash儲存系統中，希望所有記憶體區塊均勻的使用。而均勻抹除基本原理，是將常被更新的資料配置於較少抹除次數區塊中，不常更新的冷資料則安置於抹除次數較多

14、的區塊中，藉此達到動態式平衡。為解決NandFlash不能直接覆寫缺點，必須考慮如何更新區塊資料及管理可用自由空間，進而間接增加使用壽命。對於更新方式，為了增進寫入效率，必須分離寫入和抹除運算。更新時須將新資料寫入至到新自由區塊空間中，且將原區域舊版資料宣稱為無效資料。等至回收條件被觸發時啟動抹除運算，回收無效資料空間，以提供足夠使用空間。在抹除成本與均勻抹除行為上，兩者是相互衝突的議題。如果將NandFlash管理重心集中在降低清潔成本，會導致區塊間抹除次數分佈情況呈現過於歪斜，使得系統可靠度嚴重受影響。相反地，過度注重均勻抹除將增加額外成本，而降低了抹除考量。在抹除區塊時，透過清除索引，得

15、到最佳候選區塊，它整合了動態均勻抹除與區塊利用率兩個因素。因此，可解決清潔成本與均勻抹除兩者間衝突議題。4臺北科技大學學報第三十七之二期本論文的架構安排如下。在第二部份中描述NandFlash的基本工作原理。參數定義及管理演算法之探討於第三部份中討論。第四部份是主要結果。最後，第五部分為結論。貳、基本原理為了提高寫入速度和間接達到均勻抹除目的，採用日誌-結構化檔案系統架構 (Log-Structure File System，簡稱LFS) 1,11-12。此方法是將所有新增或更新資料，寫入日誌記錄的最後端，取代了直接更新檔案的方法。若是執行更新資料動作，只須將舊資料標示為無效(Invalid)

16、，在某一特定時機啟動抹除機制，以回收記憶體區塊至可用的記憶體區塊中。NandFlash將記憶體分割為數個固定的區塊，每個區塊切割成數個大小相同的資料頁。其中區塊是抹除的基本單位，資料頁則是I/O的操作單位，也是NandFlash與主記憶體間資料交換的單位，以下將以區塊和資料頁，描述NandFlash。一、NandFlash管理架構NandFlash因不能覆寫及抹除次數之兩項主要限制，進而延伸出以下之必要管理考量。壞區塊管理(Bad Block Management)，均勻抹除(Wear-Leveling)，無效資料頁蒐集(Garbage Collection)。本文中，以此三項要點為探討主軸，

17、且以KimLee演算法10為研究基礎，必且增加其他考量研究議題之探討。而整體NandFlash儲存系統中，使用者透過作業系統，呼叫系統檔案管理，作為檔案存取服務；而檔案管理中，透過NandFlash管理方式作適當的檔案紀錄；最後，經由NandFlash存取介面，直接存取NandFlash實體記憶體中之檔案資料。在NandFlash管理中，由三個主要策略元素構成，分配(Allocation)、清潔(Clean)和均勻抹除(Wear-Leveling)。而所謂分配主要負責管理可用的自由空間區塊和決定可用自由空間區塊(Available free Blocks)的分配。清潔工作是負責回收無效的區塊及

18、產生新的自由空間。均勻抹除工作在於平均化使用每個區塊，避免抹除有集中化現象。圖(一) NandFlash儲存系統結構。二、NandFlash管理方式從圖(一)整體NandFlash儲存系統結構中，我們探討其中NandFlash基本管理方式。當檔案更新時NandFlash管理機制中，首先在所更新的資料區塊中，將目前區塊中的舊資料頁標記為無效，並且將新資料寫至一個新的可用自由區塊中，標註有效，成為有效資料頁，如圖(二)所示。以區塊為基礎之反及閘快閃記憶體管理模式5圖(二) NandFlash管理。參、參數定義及管理演算法之探討本文中所定義的抹除花費模型基礎是根據eNVy快閃儲存系統的清潔花費公式u

19、/(1-u)作為探討依據，u是區塊的利用率（代表有效資料所佔的空間）5。此公式用來表示，當考慮將一區塊中的有效資料重新寫入至另一區塊，所需的花費成本。 對於NandFlash，在固定期間經常性的抹除將會導致較高整體運算費用。因此，應該將抹除數目減至最少，進而增加使用壽命期限。特別當區塊的儲存利用率較高時，減少區塊被抹除是非常重要的10。以下將定義三個參數，作為指標運算之參考參數，分別為累積清潔費用、齊平程度(D)及蒐集大小。首先，由清潔頻率f所累積清潔費用如定義1所示10。定義1：累積清潔費用：。關於均勻抹除快閃記憶體中所有區塊的測量，我們使用齊平程度(Leveling degree)如定義2

20、所示。 定義2：D =max-min。齊平程度(D)是最大的抹除計數值（max）和最小的抹除計數值（min）之間的差。再者，雖然使用蒐集策略分離冷熱資料屬性區塊有實質上正面效果，但蒐集動作本身為運算成本。若蒐集次數太頻繁或收集量過大，便會降低此效益；甚至增加運算成本。因此，必須適當定義蒐集時機與蒐集單位大小。定義3：蒐集大小 在每一次的蒐集時，從日誌檔中，收集冷資料的資料頁數目10。一、管理最佳化與演算法改良首先，介紹貪婪清潔演算法12-13，再探討KimLee清潔演算法。並針對管理方法上冷資料(Cold data)與熱資料(Hot data)的分離政策、清潔區塊選擇與抹除均勻策略提出改良，並

21、補充相關研究議題，以得到一個適當化的管理效能。(一)貪婪清潔演算法對於NandFlash，抹除策略演算法效率將直接影響管理系統效能5,12。依據eNVy的清潔花費模式，藉由區塊利用率決定區塊清潔費用5。因此，如何挑選區塊進行抹除，將是影響整體管理效益的最重要因素。6臺北科技大學學報第三十七之二期貪婪清潔法選擇的方式是尋找區塊內具有最多數量的舊資料頁作回收依據，目的在於花費最少的成本，以期待獲得較大的回收空間。而在存取行為平均的情況下，貪婪清潔法與其他抹除策略成效並不會有很大差異性1。但當存取行為高度集中的情況下(根據在UNIX檔案系統研究中，將近6778%寫入行為，集中在少數檔案上14-15，

22、因此貪婪清潔法的抹除與搬移次數將有急速增加趨勢5,9,12。貪婪清潔法挑選區塊時無法有效辨別區塊資料冷熱屬性狀態。因此，會造成剛更新後的區塊迅速增加新的舊資料，導致進入準備被抹除狀態，而使得效率驟降。此法不能有效分離冷熱資料區塊，使得冷熱資料區塊同時存在每一個區塊中，造成每次抹除時冷資料頁無益的搬移，再度造成降低系統效能。(二)KimLee演算法冷熱資料分離缺點在KimLee演算法中，將冷熱資料分離，其工作約分兩個階段：(1)蒐尋並且收集冷資料碎片資料頁；(2)群集冷資料至日誌尾端。收集運算程序，如圖(三)所示。此模式程序中，有下列結論。在KimLee蒐集演算法中，雖然在第一階段中已將冷資料分

23、別收集，但第二階段中，將冷資料寫入至日誌後端，而可能未填滿整個區塊空間，使得檔案管理系統後來因為某一檔案的更新，又將一個熱資料寫入日誌尾端，造成冷熱資料再度混合；影響整體冷熱資料分離程度效能。圖(三)蒐集程序。(三)冷熱資料分離缺點改進一般LFS結構僅用一個使用的資料區段LFS與可用自由空間的資料區段LFS，在KimLee分離演算法中採用檔案方式區別冷熱資料，若要剛好蒐集一個區塊大小的資料頁量是困難的。因此，無法有效的分離冷熱資料屬性，進而影響整體效能。在策略上，我們將NandFlash使用中的資料區塊段分為兩類。一類存放常更新的檔案，即熱資料；另一類存放不常更動的資料檔，即冷資料。每一個區塊

24、在NandFlash初始或經回收後不具有屬性類別。當存有資料區塊後，視所存放資料屬性，而成為熱資料區塊組或冷資料區塊組，即常更新或不常更新之資料區塊。此後，當蒐集冷資料資料頁時，便將其資料頁寫入冷資料區塊組LFS的日誌尾端，如圖(四)所示。再更新或抹除資料時則將資料重寫入到熱資料區塊LFS的日誌尾端，如此可改善冷熱資料混合機率。以區塊為基礎之反及閘快閃記憶體管理模式7圖(四) 冷資料頁蒐集示意圖。肆、主要結果首先，在NandFlash中我們大約區分為四個主要區塊。重要資訊區(Information area)、儲存資料區1、儲存資料區2和可使用之空閒資料區，其NandFlash空間之規劃示意圖

25、，如圖(五)所示。圖(五)NandFlash規劃表示圖。重要資訊區，主要紀錄損壞區塊表(Bad Block Table-BBT)、 根目錄(File Description Block- FDB)、檔案配置表 (File Allocation Table-FAT)和其它區塊重要紀錄資料20。儲存資料區1 (Storage area1)及儲存資料區2 (Storage area2)，主要用來儲存資料。而約分成兩部分的原因，在於將資料依屬性區分為熱及冷資料屬性，假定儲存資料區1儲存熱屬性資料；而儲存資料區2儲存冷屬性資料，當抹除次數達到所規定限制時，其儲存資料將會依據區塊的抹除次數及資料屬性作合適

26、配置，因此儲存區資料1及儲存區資料2的抹除次數限制將會達到平衡，達到壽命延長的效果。可使用之空間資料區表示目前可用來配置存放資料頁之區域。一、壞區塊管理(Bad Block Management)首次NandFlash使用時，因為NandFlash可能約有1%的壞損區塊，所以必須對NandFlash區塊依序掃描，將損壞區塊一一記錄至BBT中，避免日後資料寫入該區塊，造成資料錯誤或任何不正常狀態發生16-17。任何資料寫入NandFlash中時，必須先檢查BBT，若所安排寫入之區塊在BBT範圍內，必須另外指定其他區塊存放資料，並且變更資料存取指標，以確保正確地鏈結；倘若寫入的資料區塊位址不在BB

27、T內，但在寫入動作時發生錯誤訊息，經ECC檢查碼重覆執行多次檢查，如仍有誤，則必須考慮將該區塊標示為損壞，將此區塊加入BBT中，並另外指定區域存放資料，並同時更新鏈結指標 20。8臺北科技大學學報第三十七之二期BBT建立之虛擬碼如下所示：Crate Bad_Block_Table1Block address =0;2for Block address to Last_Block_address;.3Check “FFh” or “FFFFh” at the column address 2048(x8 device) or (x16 device) of the1st and 2nd page

28、 in the block;4if Block address Last_Block_address & value “FFh”or “FFFFh”;/value= the column address 2048(x8 device) or (x16 device) of the 1st and2nd page5crate to Bad_Block_Table;圖(六)壞區塊建立之流程。因我們所記錄的損壞區塊資訊單位為區塊，如果以K9XXG08XX為例16，必須紀錄4096筆記錄。而檢查方式如圖(六)流程所示，而損壞區塊之記錄表，採取使用2個資料頁容量存放BBT，而此BBT將存放在NandFl

29、ash中所劃分的重要資訊區中。二、均勻抹除(Wear-Leveling)快閃記憶體因為有抹除次數的限制，舉例Samsung K9XXG08XXM，其抹除次數為100,000次16。假若某個區塊中，永遠存在著不被更新的資料區塊，此時非均勻抹除情況將嚴重發生。若系統中存在多數的冷資料區塊，則NandFlash整體上，將因為輪替抹除的區塊候選變少，而增加抹除次數。使得快閃記憶體容量，因抹除次數極限值的限制，而失去可用的記憶體空間。舉例，某一NandFlash有100個抹除片段，每一個區塊抹除次數為100,000次；假若其儲存區塊空間中永遠包含著25個區塊的冷資料，其使用率將很高，因此不會被系統回收抹

30、除，故僅剩下75個區塊輪流使用抹除。假設在一個高密度寫入的情況下，每天有6000個區塊抹除回收需求(不考慮抹除均勻)，則其記憶體100%可用的使用壽命為：100%生命週期=。換句話說，當經過3.424年後，其記憶體空間僅剩下25%。換言之，只剩存著冷資料區塊可再被使用。而25%的區塊使用空間也將會因為記憶體空間不足，而需更頻繁的抹除，而快速達到抹除極限值。上式中並未考慮均勻抹除，使得可用空間急速減少。若我們在系統中考慮均勻抹除，則此100個區塊的抹除次數差異，將會控制在某一範圍內，使其幾乎同時達到抹除界限值。在記憶體使用上，也會有較大的空間與彈性，假設均勻抹除必須額外付出8%抹除費用8，此時的

31、使用壽命為：以區塊為基礎之反及閘快閃記憶體管理模式9100%生命週期=雖然均勻抹除需付出額外的成本，但在可靠度、記憶體使用空間及使用壽命議題上是相當值得的花費。(一)KimLee演算法清潔索引策略 清潔索引(CleaningIndex)是在NandFlash管理中挑選區塊被抹除的準繩；最低的清潔索引值，清潔時此區塊將被選擇抹除10。清潔索引中，定義了降低清潔花費及提高均勻抹除兩者兼顧的參考式，如下所示：上式在KimLee文中 10，ui表示區塊i的利用率、i表示區塊i的抹除計數、max表示全部區塊中最大的抹除計數值。清潔索引由二個考量因素所組成：每個區塊利用率和抹除計數值。正規化齊平度()，是

32、此兩因數的加權。計算出的齊平度數值映射於0至1之間。l= 若抹除是呈現均勻式分配，則清潔索引主要之目的在於降低清潔費用。換言之，當發生非均勻式抹除時，清潔索引之目的是為了均勻抹除。此清潔費用索引的立意甚佳，因當區塊選擇時，須要同時考慮清潔成本與均勻抹除。但此公式卻有一缺失，當片段抹除次數越接近抹除極限值時，卻疏乎均勻抹除參數，反而偏重區塊使用率參數。此現象違反使用壽命的規則 10。舉例：假設 = 0.9情況下，考慮不同抹除次數區塊選擇策略。區塊A：ui=0.8，i=95000，max=95350，min=90950CleaningIndex=(1-0.9)0.8+0.995000/(95350

33、+1)=0.976687區塊B：ui=0.4，i=95330，max=95350，min=90950CleaningIndex=(1-0.9)0.4+0.995330/(95350+1)=0.939802 區塊A與區塊B在以上的條件下，而經由KimLee清除指標計算，發現將選擇抹除次數即將達抹除極限之區塊作為抹除標準，與所期待之行為背道。因此，此清除指標有部分缺失，需加以改進。(二)高可靠度和低成本效益快閃記憶體管理模式-清潔索引策略在高可靠度和低成本效益快閃記憶體管理模式-清潔索引策略文中18，改善了KimLee清潔索引式子，如下所示：舉例：假設 = 0.9情況下，考慮不同抹除次數區塊選擇策

34、略。區塊A：ui=0.8，i=95000，max=95350，min=90950CleaningIndex=(1-0.9)0.8+0.995000-90950/(95350-90950+1)=0.908221 區塊B：ui=0.4，i=95330，max=95350，min=90950CleaningIndex=(1-0.9)0.4+0.995330-90950/(95350-90950+1)=0.93570610臺北科技大學學報第三十七之二期因本文所探討基礎為區塊，因此ui於此將修改表示為區塊利用率。而此修正後的抹除索引，改善了KimLee在接近抹除界限值時，不注重均勻抹除的缺失。均勻抹除將

35、增加清除指標費用，因此越是嚴謹均勻抹除策略其清除指標費用越高；但越鬆弛的均勻抹除策略，其快閃記憶體的可靠度與使用壽命將降低。(三)動態式均勻抹除策略假設NandFlash其抹除界限值為100,000次，在區塊被抹除100,000次之前，不必擔心其抹除限制。因此，均勻抹除可採用漸進嚴謹策略，此方式的優點在於可提供更大的配置彈性。我們採用動態方式，降低均勻抹除，所需付出的額外成本k 18。k變數如下所示：在初始時不必因擔心區塊抹除極限到達，因此k值取較大，且k值隨者最大抹除次數的增加而漸進式向下調整。NandFlash管理系統在初始時，未達最大抹除界限之前，加重考量區塊使用率，如此可降低抹除費用。

36、當最大抹除次數越接近抹除極限時，常數k值將逐漸式趨小，漸注重均勻抹除。使得系統的區塊壽命幾乎同時到達，亦可提高整體系統的可靠度。當k值改變越大時，l值越小，越不注重均勻抹除，相反的當k值越小時，l值變大時，表示越注重均勻抹除，如下圖(七)所示。圖(七)k 與l 變化曲線圖m及n為常數，其中m決定了k值曲線的變化度與抹除成本；n則決定最後抹除極限值屆臨的嚴僅度。值越大費用越低，但可靠度與均勻抹除越差，值越低抹除費用越高，可靠度與均勻抹除越佳 18 。配合CleaningIndex索引公式，進一步可知道，k值變化可使系統在初始時僅考慮區塊利用率，隨著抹除次數的增加，系統漸漸注重均勻抹除，如此動態式

37、的均勻抹除，必可降低KimLee抹除費用，並且將有嚴謹的可靠度。(四)考量冷熱區塊屬性的清潔索引在系統應用中，資料存取有其慣性與重複參考的傾向4。即常更動的資料預期會保持經常更動屬性；冷資料屬性則不易更新甚至不更新。所以屬於熱資料屬性，將有很大的機會再次增加舊資料，因此清潔索引在挑選此類區塊的機率時應該降低挑選權重。相反的，屬於冷資料屬性，因為本身被更新的機會少，因此應該調整權重，讓其比值相等的熱資料區塊，多一點被抹除的機會。因此在清潔索引中，加入屬性常數h，若該屬性為熱資料區塊，則h值為1；冷資料區塊屬性則h值為0.9。因不希望區塊屬性權重過小，影響整體效能，最後修正後的清除索引公式如下所示

38、。而於此是以區塊為評量，與之前片段單位不同。以區塊為基礎之反及閘快閃記憶體管理模式11ui：區塊i的利用率。i ：區塊i的抹除計數。min：最小的抹除計數值。max：最大的抹除計數值。：標準齊平度。h：區塊屬性，hot=1，cold=0.9。(五)區塊抹除策略模型在區塊抹除策略中，以下分成三種模型方式探討，平均抹除型、初始集中抹除型和平緩抹除型。1.模型一：此模型是一理想方式的均勻抹除管理方式，以平均抹除方式對每個區塊操作，如圖(八)所示。在管理上，要求區塊依循此模型方式，但實際上是有困難的，因為這將導致系統嚴重負擔，而造成執行上困難。2.模型二：此模型是屬於初始時區塊有集中性抹除現象，當達到

39、所設定之抹除臨界時，則遲緩抹除行為，如圖(九)所示。3.模型三：此模型一開始之初，區塊可能儲存冷屬性資料，因此抹除次數趨於平緩，但會因分配策略執行，將導致抹除次數漸增，再趨於緩和之現象，如圖(十)所示。而在我們所提出的管理模式上，區塊抹除次數的模型是模型二及模型三兩者之優點的分佈情況。這是由於初始時策略採取開放式管理機制，這將有助於存取管理，而當抹除次數到達預期臨限時，抹除策略開始監控，因此從模擬圖中可知，我們的機制可增加使用壽命。圖(八) 區塊抹除模型一示意圖圖(九)區塊抹除模型二示意圖175臺北科技大學學報第三十七之二期圖(十) 區塊抹除模型三示意圖三、區塊資料頁分配政策為達到快閃記憶體的

40、均勻抹除效果，僅靠清潔政策是無法達成；因為可能某一區塊其抹除程度太過歪斜，使得清潔索引計算時，成為所有區塊中最小索引值，而回收至自由片段中，無法達成均勻抹除效果。因此，必須有一個適當的區塊分配政策。首先我們發現區塊配置時，有以下三種情況下發生。一、當系統更新檔案時，必須重寫新資料至日誌的尾端。二、當系統做抹除時，必須將片段中剩餘的有效資料複製到日誌的尾端。三、當系統執行蒐集政策時，必須將蒐集的冷資料碎片寫到日誌的尾端。若屬於情況一及情況二，則分配政策上儘量挑選最少抹除次數的區塊作為分配，因為熱資料屬性會讓該區塊檔案更新，使得迅速累積無效的舊資料，而再次回收，拉平抹除均勻度。至於情況三，因所蒐集

41、的資料頁為冷資料檔案，預期被更新的機會不多，因此區塊分配政策可分配一個抹除次數大的區塊給該資料，便可達到均勻抹除的效果。所以我們希望提出分配政策指標(AllocationIndex)，透過此指標將資料置於適合的NandFlash資料頁中。其中是資料寫入指標。當資料是屬於更新或是因即時抹除所做的搬動時，=1。當資料是屬於冷資料頁蒐集時所做的資料搬動時，=0。由此式中可發現，當系統作更新或抹除時將會以作為參考數據。而當系統作收集政策時，將以作為參考依據。因此能有效的將資料作合適的分配，進一步達到均勻使用區塊效用。四、無效資料頁回收(Garbage Collection)定義無效資料頁回收指標(Ga

42、rbage Collection Index，簡稱GCI)，作為有效資料頁之收集及無效資料頁之回收的依據指標。無效資料頁回收策略，主要目的在於抹除無效資料，釋放自由空間，以保持足夠的使用空間。而此機制啟動的時機如下所示。一、當空間不足時，系統自動啟發此機制。二、當被使用的區塊中，有效資料只剩25%(可調整其參數)時，而經評估合乎蒐集效益則啟動此機制。以區塊為基礎之反及閘快閃記憶體管理模式13當GCI1值小於1時，亦則啟動無效資料回收策略，freeBlocknum表示目前NandFlash中可用來寫入資料的區塊數量。totalBlocknum表是此NandFlash中，用來讀寫資料全部的區塊數量

43、。若以K9XXG08XXM 16為例，共有4096個區塊。而精密的totalBlocknum表示應為4096個區塊扣除失效區塊及重要資料區塊。表示一個加權值，會因所設定的空間不足百分比而有所調整。例如：當空間不足百分比，為20%時則，= 5。如當空間不足百分比，為25%時，則= 4。其中與空間不足比例之關係圖，如圖(十一)所示。圖(十一)與空間不足比例之示意圖當GCI2值小於1時，亦則啟動資料碎片蒐集策略，其中表示i區塊中有效資料只佔據此區塊容量大小的25%。表示一個區塊中的資料頁數，一般而言1區塊有32個資料頁或64個資料頁。全部的區塊中，若區塊已被使用並且此區塊中有效資料只佔此區塊的25%

44、時，則列入收集的候選之一，而當所有候選區塊的有效資料容量大小，當大於等於一個區塊容量大小時，則此資料碎片蒐集策略將啟動。因無效資料蒐集頁之目的在於使得系統使用容量上有足夠的空間。但蒐集行為後將會使得抹除行為發生，而抹除行為之次數將間接影響使用區塊使用壽命之問題。若單以整體的可用空間百分比作為蒐集，如GCI1之指標。因在NandFlash操作中抹除操作是必須花費最長的執行時間，因此若以GCI1作為單一考量基準，則將導致整體系統嚴重負擔，並且此行為將頻繁發生，造成效率不佳。假若加入GCI2之衡量指標。則可動態式確保有足夠之使用空間，並可減少系統在無足夠空間時大量抹除操作時間之負擔。因此我們採用動態

45、式無效資料頁百分比之方式，在足夠使用空間條件及區塊抹除次數條件下取一平衡點。假設，當區塊只佔據25%有效資料時，則將此區塊加入蒐集候選中，當蒐集條件成立時啟動資料頁碎片蒐集。而因初期所假設之有效資料比率較大(25%)，因此區塊抹除的次數將增多而影響區塊使用壽命，所以當區塊抹除次數比例增大時，適當調小有效資料比率，而減少抹除次數機會，進而偏重GCI1指標。因此在CGI2指標中，Blocki之有效資料頁百分比例是可經由抹除次數百分比作調整，而動態調整區塊有效資料頁比例之圖示，如圖(十二)所示。14臺北科技大學學報第三十七之二期圖(十二)動態調整GCI2中無效資料頁百分比之示意圖伍、結 論雖然許多有

46、關Flash演算法探討中已改善快閃記憶體的限制缺點。其演算法在架構上仍有抹除費用增加與壽命延長不足之處。針對此缺失，我們以區塊及資料頁作為NandFlash管理單元提出改良式架構，將冷、熱資料分別置於不同屬性的區塊中，改善冷熱資料再度混合的機率，以達到降低抹除費用與抹除次數的功效，進而可提高系統壽命。在清潔索引缺失方面，我們提出改善方法，當NandFlash越趨近抹除界限值時，不因均勻抹除越寬鬆，而造成可靠度嚴重的受考驗，並且加入動態K值，以降低均勻抹除所需付出的額外成本，因此可提高系統壽命與可靠度。在壞區塊管理中，本文中敘述其管理方法及記錄方式。均勻抹除中以KimLee演算法為基礎，改善Cl

47、eaningIndex提供一妥善抹除索引指標。在資料配置方面，以一合理的配置指標，與清除政策互相輝映，以達到區塊均勻使用之目的。在無效資料頁蒐集方面，以GCI索引指標為依據，適當的蒐集無效資料頁，以達到其蒐集目的。參考文獻1T. Blackwell, J. Harris, and M. Seltzer, “Heuristic Cleaning Algorithms in Log- Structured File Systems,” Proceedings of the 1995 USENIX Technical Conference, pp. 277-288, 1995.2M. L. Chia

48、ng, Paul C. H. Lee, and R. C. Chang, Managing Flash Memory in Personal Communication Devices, Proceedings of the 1997 International Symposium on Consumer Electronics (ISCE97), pp. 177-182, Singapore, Dec.3M. L. Chiang, “A Study on the Design of Memory Based Embedded Storage Systems,” PhD Thesis, Dep

49、artment of Computer and Information Science, National Chiao Tung University, Jan. 1999.以區塊為基礎之反及閘快閃記憶體管理模式154P. J. Denning, “Working sets past and present,” IEEE Trans. on Software Eng., Vol. 6, No.1, pp. 64-84, 1980.5M. Wu and W. Zwaenepoel, “eNVy: A non- volatile main memory storage system,” Proc. ASPL94, pp. 86-97, 1994.6Intel, What is Flash Memory ? 2003.7Intel Datasheet, /design/flcomp/specupdt/29813017.pdf, August