[工學]王佳林畢業(yè)設計說明書0613

1、沈陽建筑大學畢業(yè)設計說明書畢 業(yè) 設 計 題 目 閃存連續(xù)存儲單元等概率存儲算法設計 學院專業(yè)班級 信息學院通信工程07-2班 學 生 姓 名 王佳林 性別 男 指 導 教 師 白樂強 職稱 教授 2011年6月13日摘 要本文設計了一種新的閃存文件管理存儲算法，能夠整體提高閃存的使用壽命和管理效率，通常，一個閃存是由若干個閃存塊組成，每個閃存塊又分為若干個物理頁。閃存塊是擦除操作的最小單位，而讀和寫都是以頁為單位進行，對一個物理頁進行重寫之前，必須先對該頁所在的塊執(zhí)行擦除操作。而每一個閃存塊的擦除次數(shù)是有限的，一般是在10萬次至100萬次之間，只要有一個閃存塊的擦除次數(shù)達到了上限，數(shù)據(jù)存儲就

2、變得不可靠，會影響到整個閃存的讀寫效率和性能。因此，需要設計高效的磨損均衡處理策略，該算法是在磨損均衡處理策略的基礎上，增加了連續(xù)性的算法，使文件相對連續(xù)，方便管理，并且使每部分的空間利用率達到均衡。在相同操作的情況下，傳統(tǒng)的文件管理系統(tǒng)只有前半部分甚至更少的空間被多次使用，而在本文設計的閃存文件管理系統(tǒng)中不僅能夠使每個閃存塊使用次數(shù)相對均衡而且文件管理方便。本文設計的管理系統(tǒng)相較于傳統(tǒng)系統(tǒng)有更好的性能，尤其在操作次數(shù)較多的情況下，這種系統(tǒng)的優(yōu)勢凸顯。關鍵詞：閃存；磨損均衡；排序；連續(xù)；文件系統(tǒng)abstractthis paper presents a new algorithm for th

3、e flash memory file management, to improve the overall management efficiency and service life of flash memory. usually, a flash memory is made by the number of blocks. each memory block is divided into a number of physical pages. flash block is the smallest unit of erase operation, and is based on p

4、ages reading and writing unit. to rewrite a physical page, you must perform on the page where the block erases operation. and each erase block number of flash memory is limited, generally from 10 million to 100 million times. if there is a flash erase block reached the maximum number of data storage

5、 it will become unreliable, and will affect reading and writing of the whole flash memory efficiency and performance. therefore, it needs to design an efficient strategy for the wearing balance. the equalization algorithm is the wear on the basis of strategies to increase the continuity of the algor

6、ithm, so the file is relatively continuous, easy managing, and space utilization of every part of the equilibrium. in the same operating conditions, the traditional document management system or less only the former half of the space be used multiple times, and in this paper flash file management sy

7、stem designed to enable not only the frequency of use of each flash memory block for file management is relatively balanced and easy to .the management system of the author designs can provide a better performance compared with the traditional system especially in the case of the number of operation

8、s is large.keywords: flash; wear balance; sort; continuous; file system 目錄第一章 前言11.1設計背景11.2基于閃存的文件系統(tǒng)介紹2第二章 flash存儲器32.1 flash存儲器介紹32.1.1 flash存儲器與ram、磁盤的比較32.2 閃存的特點和nand閃存的發(fā)展32.2.1 nor型閃存42.2.2 nand型閃存42.2.3 nor閃存與nand閃存的性能差異42.3 nand flash的問題42.3.1塊擦除次數(shù)有限42.3.2 異位更新（non-in-place update）42.3.3 壞塊4

9、2.3.4差錯校驗碼（error correction code, ecc）42.4 nand flash讀寫尋址方式4第三章 flash存儲關鍵技術43.1地址映射43.1.1 基于頁的地址映射43.1.2 基于塊的地址映射43.1.3混合式地址映射43.2.1垃圾回收的時機43.2.2回收塊的選擇43.2.3垃圾回收的合并操作4第四章 閃存連續(xù)存儲等概率存儲算法設計44.1磨損均衡44.1.1動態(tài)磨損均衡44.1.2靜態(tài)磨損均衡44.2 設計的提出44.3 設計方案44.4設計的基本思想44.5 具體設計44.5.1 空間查詢算法44.5.2 存儲查找空間算法44.5.3 查找斷

10、點算法44.6算法的實現(xiàn)44.6.1 閾值操作44.6.2 工作過程4第五章 閃存連續(xù)存儲等概率存儲算法仿真45.1 c+具體程序設計45.1.1 設計前提45.1.2 設計內(nèi)容45.2 仿真結果4第六章 經(jīng)濟技術分析4第七章 結論4參考文獻4致謝4附錄一：中文譯文附錄二：外文資料原文附錄三：閃存連續(xù)存儲單元等概率存儲算法設計源代碼iv 沈陽建筑大學畢業(yè)設計（論文）閃存連續(xù)存儲單元等概率存儲算法設計第一章 前言1.1設計背景從20世紀80年代的一個概念到2007年在全球范圍內(nèi)產(chǎn)生230億美元收益的產(chǎn)業(yè)，flash存儲器經(jīng)歷了最初應用于個人計算機bi0s(basic inputoutput sy

11、stem)存儲、嵌入式系統(tǒng)的標準存儲器，到目前在某些筆記本電腦中代替磁盤作為外存儲器，并被引入到企業(yè)級存儲的高端存儲陣列中，flash存儲技術已經(jīng)得到很大的發(fā)展。作為一種電可擦除可編程只讀存儲器，flash存儲器不但能在不移除存儲芯片的情況下進行擦除和編程操作，還具有非易失性、固態(tài)性、體積小、重量輕、抗震動、高性能、低能耗等優(yōu)點。由于flash存儲器在價格、訪問延遲、傳輸帶寬、密度和能耗方面彌補了ram(random accessed memory)和磁盤之間的差異，關于flash存儲器在存儲系統(tǒng)體系結構中的地位探討成為研究人員關注的問題之一，主要包括主存儲器層、ram與磁盤之間的buffer

12、 cache層和持久性存儲層3個層次。和內(nèi)存、磁盤最顯著的不同之處在于，flash存儲器的每個存儲單元只有在擦除以后才能寫數(shù)據(jù)。目前擦除操作所需的時間比寫操作多一個數(shù)量級，并且擦除的基本單位由幾十個讀、寫基本單位組成。此外，每個存儲單元允許的擦除次數(shù)是有限的。這些特點使得對flash存儲的有效管理變得十分重要。目前，有兩種管理flash存儲器的軟件體系結構：通過flash轉換層為flash存儲器提供塊設備接口，使已有的文件系統(tǒng)不需要經(jīng)過修改就能運行，為此，flash轉化層實現(xiàn)了地址映射、垃圾回收、磨損均衡等功能；設計并實現(xiàn)專門的flash文件系統(tǒng)，以充分發(fā)揮flash存儲器的特點。隨著flas

13、h存儲器的容量越來越大，價格越來越低，flash存儲器相對磁盤的優(yōu)勢越來越明顯。尤其是隨著綠色存儲概念的提出，在個人計算機以及服務器等通用計算環(huán)境中使用基于flash的存儲系統(tǒng)迅速成為應用和研究的熱點。emc公司宣布在其高端產(chǎn)品symmetrix中支持ssd(solid state disk)。google公司為了緩解能耗問題，將美國總部部分服務器的硬盤替換為flash ssd。百度公司也宣布開始使用其自行研制的ssd。然而，面向通用計算機環(huán)境的flash存儲系統(tǒng)面臨一些新的問題：一方面，和許多移動設備不同，個人計算機和服務器等系統(tǒng)向存儲子系統(tǒng)發(fā)出大量的隨機寫請求，而由于flash存儲的獨特特

14、性，目前的隨機寫性能有時比磁盤低幾個數(shù)量級，因此提高隨機寫的性能成為flash存儲管理的重要任務之一；另一方面，幾十年來，操作系統(tǒng)、文件系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)等大量上層軟件的設計和實現(xiàn)都是基于底層采用磁盤存儲系統(tǒng)的假設，大量的數(shù)據(jù)結構和算法的設計和實現(xiàn)都以優(yōu)化磁盤系統(tǒng)的性能為目標。如b+樹、buffer cache管理策略等，將這些軟件直接用于基于flash的存儲系統(tǒng)無疑將無法有效地發(fā)揮flash存儲系統(tǒng)的性能，因而修改或設計新的數(shù)據(jù)結構和算法以提高f1ash存儲系統(tǒng)的性能是另一個需要研究的問題1。1.2基于閃存的文件系統(tǒng)介紹閃存的工作原理及其帶來的局限：在嵌入式系統(tǒng)中應用 flash 存儲器的

15、最好辦法是在其上構造一個文件系統(tǒng)，對flash存儲器中的數(shù)據(jù)內(nèi)容進行基于文件代號的存儲管理，同時對于flash 存儲器本身的壞塊進行透明的壞塊管理。但pc中使用的文件系統(tǒng)，如dos下的fat 文件系統(tǒng)、windows下的ntfs文件系統(tǒng)等，并不適合直接移植到flash存儲器中，主要有以下3 個原因2 3：flash 存儲器多用于嵌入式系統(tǒng)，嵌入式系統(tǒng)的應用條件惡劣，電源電壓不穩(wěn)定，突發(fā)性斷電以及非法插拔都將對flash 的存儲器造成災難性的影響，通用文件系統(tǒng)采用大量的緩存技術來提高文件系統(tǒng)的可靠性，而嵌入式系統(tǒng)由于資源有限而不能通過緩存技術來提高可靠性。通用文件系統(tǒng)的某些記錄信息，如fat表、

16、日志文件、曲目數(shù)據(jù)庫等需要被頻繁改寫，這些記錄信息如果存放在固定的flash 塊中，將導致該塊的頻繁擦寫而提前影響整個flash 存儲器的使用。flash 存儲器讀取速度比磁盤驅動器快，存儲的內(nèi)容很多是多媒體數(shù)據(jù)資料。這些數(shù)據(jù)允許一定程度的誤碼率，未必需要像通用文件系統(tǒng)那樣嚴格保證存儲的正確性。如果通過靈活的校驗機制與壞塊管理，則可以達到更高效的存儲空間利用率，這對成本敏感的嵌入式系統(tǒng)來說是更加需要考慮的。第二章 flash存儲器2.1 flash存儲器介紹flash存儲器根據(jù)其內(nèi)部架構和實現(xiàn)技術可以分為and，nand，nor，ninor幾種，目前占據(jù)主流市場的有nor flash和nand

17、 f1ash兩大類。nor flash由intel公司于1988年最初推出。為了提高容量/價格比，東芝公司于1989年推出nand flash。兩種flash技術各有優(yōu)、缺點以及各自適用的場合。2.1.1 flash存儲器與ram、磁盤的比較 flash存儲器在價格、訪問延遲、傳輸帶寬、密度和能耗等方面彌補了ram和磁盤之間異。與其他存儲介質相比，fiash存儲器具有如下優(yōu)點：與低讀、寫延遲和包含機械部件的磁盤相比，flash存儲器的讀、寫延遲較低；統(tǒng)一的讀性能，尋道和旋轉延遲的消除使得隨機讀性能與順序讀性能幾乎一致；低能耗，能量消耗顯著低于ram和磁盤存儲器；高可靠性，mtbf(mean t

18、ime between failures)比磁盤高一個數(shù)量級；能適應惡劣環(huán)境，包括高溫、劇烈震動等。2.2 閃存的特點和nand閃存的發(fā)展隨著嵌入式系統(tǒng)在消費類電子產(chǎn)品、數(shù)據(jù)采集系統(tǒng)以及工業(yè)控制系統(tǒng)中的廣泛應用，隨著各類系統(tǒng)對于數(shù)據(jù)存儲容量的需求日益提高，作為嵌入式系統(tǒng)中最常用的存儲設備，閃速存儲器的應用也日益廣泛。閃速存儲器按其內(nèi)部結構的不同可分為nor 和nand兩種，其中nand 型存儲器以高密度、大容量、高數(shù)據(jù)存儲速率以及更多的擦除次數(shù)等特點，逐漸成為大容量嵌入式存儲設備應用的主流。對于嵌入式系統(tǒng)中的數(shù)據(jù)存儲而言，實現(xiàn)數(shù)據(jù)的高速存儲是系統(tǒng)的主要要求，但由于嵌入式系統(tǒng)的應用環(huán)境變化較大，

19、容易遇到突發(fā)情況而導致系統(tǒng)斷電，并且缺少固定的維護機制，因此需要采取措施以便在遇到突發(fā)事件時保證數(shù)據(jù)存儲的完整性和數(shù)據(jù)間的關聯(lián)性，并進一步均衡存儲區(qū)負載以延長系統(tǒng)壽命。因此基于嵌入式存儲器建立文件系統(tǒng)來管理存儲區(qū)數(shù)據(jù)便成為一種必然的方式。nand型閃存作為大容量移動存儲器中的介質，其應用日益廣泛，應用環(huán)境日益增多，因此開發(fā)基于nand 型閃存的文件系統(tǒng)以實現(xiàn)對存儲器的良好管理越來越成為一種必需4。下面來分別介紹這兩類閃存各自的物理特性。2.2.1 nor型閃存nor型閃存是根據(jù)存儲單元連接方式來命名的，其連接方式與nor門相類似。讀取是去判別一個存儲單元的狀態(tài)是“1”還是“0”。最通用的方法是

20、把存儲單元的電流與一標準存儲單元的電流進行比較。此電流會被轉化為電壓值輸出。寫是利用隧道效應或熱電子注入法增加懸浮柵中電子數(shù)量，使vth上升到一定程度。被寫的存儲單元柵極加高電壓(遠大于工作電壓)。此高電壓可由外部提供或內(nèi)部產(chǎn)生電路生成。柵極電壓大小非常敏感，要特別注意。柵極電壓控制不當，可能會導致因電流增大，柵極電壓突然回落；或無柵極電壓情況下溝道打通，增益效應減弱；或懸浮柵中的電子被吸引到柵極等不良后果。nor寫通常是一個字節(jié)或兩個字節(jié)進行的。擦除是利用隧道效應使vth下降到一定程度，主要方法是控制柵極加高負電壓。擦除是以塊為單位進行的。擦出效果的好壞程度對芯片的可靠性有很大影響5。2.2

21、.2 nand型閃存samsung、toshiba和fujistu支持nand技術。這種結構的閃速存儲器適合于純數(shù)據(jù)存儲和文件存儲，主要作為smart media卡、compact flash卡、pcmciaata卡、固態(tài)盤的存儲介質，并正成為閃速磁盤技術的核心。nand技術flash memory具有以下特點：以頁為單位進行讀和編程操作，以塊為單位進行擦除操作。具有快編程和快擦除的功能，其塊擦除時間是2毫秒；而nor技術的塊擦除時間達到幾百毫秒。數(shù)據(jù)、地址采用同一總線，實現(xiàn)串行讀取。隨機讀取速度慢且不能按字節(jié)隨機編程。芯片尺寸小，引腳少，是位成本(bit cost)最低的固態(tài)存儲器，將很快突

22、破每兆字節(jié)l美元的價格限制。芯片包含有失效塊，其數(shù)目最大可達到3到35塊，這取決于存儲器密度。失效塊不會影響有效塊的性能，但設計者需要將失效塊在地址映射表中屏蔽起來。2.2.3 nor閃存與nand閃存的性能差異閃速存儲器按其內(nèi)部存儲矩陣結構不同可分為nor 和nand 兩種，其中nor 型閃存采用或非結構柵格存儲矩陣實現(xiàn)，可按字節(jié)寫入數(shù)據(jù)，讀取速度快，但存儲密度低，數(shù)據(jù)擦除速度慢，因此常用于代碼存儲，如系統(tǒng)啟動代碼和內(nèi)核映像等。表2-1 為nor 與nand 型存儲器性能比較。表2-1 nor 與nand 型存儲器性能比較類型nornand存儲容量1mb16mb8mb512mb擦除塊大小64

23、kb256kb16kb128kb寫入方式按字節(jié)隨機寫入以頁面為單位寫入讀取方式按字節(jié)隨機讀取按字節(jié)隨機或頁面讀取讀取速度快慢寫入速度慢快擦除時間2s5s/塊2ms5ms/塊壞塊比例低高，需要dec/ecc算法nand 型閃存采用與非結構的柵格存儲矩陣實現(xiàn)，由于與非結構的存儲矩陣位元面積僅為或非結構的四分之一，且存取操作以頁面為基本單位進行，故存儲密度高，數(shù)據(jù)寫入速度快，。例如對于512m 的nand flash，采用頁映射需要占用1m 的ram，但采用塊映射僅占用16kb ram6因此適合于數(shù)據(jù)存儲領域。相比nor型閃存，nand型閃存中容易發(fā)生位交換現(xiàn)象，即一個比特位的值由0反轉為1或由1反

24、轉為0。如果反轉出現(xiàn)在關鍵文件數(shù)據(jù)塊中將會導致嚴重后果，基于nand 型閃存的嵌入式文件系統(tǒng)設計存儲器在讀取時需要加入錯誤探測更正（dec/ecc）算法以實現(xiàn)對位交換的檢測與糾正。由于nand型閃存容量大且適合于存儲文件、數(shù)據(jù)的特點，它已經(jīng)成為了嵌入式存儲備介質的首選，本問中研究的文件系統(tǒng)正是基于nand類型閃存的文件系統(tǒng)。2.3 nand flash的問題使用nand flash至少需要解決以下幾個問題：2.3.1塊擦除次數(shù)有限nand flash每塊的擦除次數(shù)都是有限的。對于slc nand flash，一般為10萬次左右，而mlc nand flash的擦除次數(shù)僅有大約1萬次，具體數(shù)據(jù)參

25、考所使用nand flash的產(chǎn)品手冊。如果某塊頻繁擦除而超過擦除次數(shù)限制，該塊內(nèi)的數(shù)據(jù)將不可靠，進而影響整個存儲器的使用，所以需要采用損耗均衡算法使各個塊近似均衡使用。2.3.2 異位更新（non-in-place update）由于nand flash先擦后寫的物理特性，如果將文件存儲在固定的塊內(nèi)，會面臨掉電數(shù)據(jù)丟失及占用較大ram等問題。所以，nand flash一般采用異位更新，即將要更新的數(shù)據(jù)讀入ram中修改后寫入其他空閑空間，在適當?shù)臅r候擦除修改前數(shù)據(jù)所在塊。因此，需要地址映射、垃圾回收等技術來管理存儲空間。2.3.3 壞塊由于nand flash的工藝不能保證nand flash

26、 的存儲區(qū)域里每個塊都是好塊， 因此，在nand flash生產(chǎn)及使用過程中都有可能產(chǎn)生壞塊。壞塊的特性是：當編程/擦除這個塊時，不能將其里面的數(shù)據(jù)置“1”， 這會造成頁編程和塊擦除操作時的錯誤，這種錯誤可以通過狀態(tài)寄存器的值反映。在存儲數(shù)據(jù)時，文件系統(tǒng)的系統(tǒng)數(shù)據(jù)被反復更新的頻率非常高。如果不對存儲方式和區(qū)域進行有效的管理，將使nand flash 很快因為某一部分扇區(qū)被頻繁擦除和寫入而損壞, 從而出現(xiàn)壞塊。2.3.4差錯校驗碼（error correction code, ecc）由于加工工藝的局限性，在nand存儲器(nand flash)控制器設計時應具有處理存儲數(shù)據(jù)出錯的功能,但是還要

27、保持一定的糾錯速度. 常用的ecc有：hamming碼、bch (bose, chaudhuri and hocquenghem)碼、reed-solomon碼等。slc nand flash一般需要能檢測2位，糾正1位錯誤的ecc，而mlc nand flash通常需要檢測并糾正4位的ecc來保證數(shù)據(jù)的安全可靠，很多芯片內(nèi)置硬件運算部分專門處理。第三章 flash存儲關鍵技術f1ash存儲器獨特的擦除操作、非對稱的讀寫性能等特性要求高效的管理技術以提供高性能、高可靠性的flash存儲系統(tǒng)。此外，為了優(yōu)化基于flash的存儲系統(tǒng)的性能，需要重新研究已有的操作系統(tǒng)和文件系統(tǒng)中大量的基于磁盤系統(tǒng)的

28、數(shù)據(jù)結構與算法，提供面向flash的技術。本節(jié)對這些關鍵技術的研究現(xiàn)狀作全面的分析、總結。3.1地址映射地址映射機制建立邏輯地址和flash存儲器的物理地址(物理塊號和物理頁號)之間的映射關系。數(shù)據(jù)更新的寫操作包括耗時、耗能的擦除和數(shù)據(jù)復制操作。為了提供可接受的寫性能，flash存儲管理借鑒了基于日志的文件系統(tǒng)的原則，將更新數(shù)據(jù)存儲在事先已經(jīng)擦除過的塊中，更新地址映射信息，再把原數(shù)據(jù)標記為無效。這種異地更新的策略分離了擦除和寫操作，有效提高了寫性能，但要求動態(tài)的地址映射機制的支持。根據(jù)映射表的粒度大小，可分為基于頁的地址映射、基于塊的地址映射和混合式地址映射。3.1.1 基于頁的地址映射在基于

29、頁的地址映射機制中，地址映射表以頁為粒度，包含的表項數(shù)與flash存儲器的頁數(shù)相同。由于粒度細，基于頁的地址映射機制具有靈活性高、性能好的優(yōu)點，但所需的ram空間較大。在嵌入式系統(tǒng)中，由于價格、能耗等方面的限制，ram資源是寶貴的。尤其隨著flash存儲器的容量不斷增大，基于頁的地址映射所需要的ram大小難以得到滿足。為了解決這個問題，基于塊的地址映射機制被提出。3.1.2 基于塊的地址映射在基于塊的地址映射機制中，塊內(nèi)數(shù)據(jù)必須順序存儲。因此，地址映射表僅需要維護每塊的第1個頁對應的邏輯地址，表項個數(shù)與flash存儲器的塊數(shù)相同。替換塊策略(replacement block scheme)就

30、是一種基于塊的地址映射機制，它為每個需要更新的數(shù)據(jù)塊維護一個或多個日志塊，用來存儲更新的數(shù)據(jù)。由于塊內(nèi)順序存儲的限制，對某頁的多次更新將占用多個日志塊，導致日志塊的空間利用率很低。另外，隨著f1ash存儲器容量的增大，目前的大塊flash存儲器從硬件上要求對塊內(nèi)的所有頁必須順序地寫，這進一步加劇了空間浪費問題。3.1.3混合式地址映射混合式地址映射機制利用文件系統(tǒng)的訪問局部性的特點，對頻繁更新的數(shù)據(jù)維護基于頁的地址映射表，而對大量的其他數(shù)據(jù)維護基于塊的地址映射表，達到以較少的ram空間開銷提供高靈活性和高性能的目標，得到研究人員的重視，不少混合式地址映射機制被提出。日志塊策略(109 bloc

31、k scheme)放松了替換塊策略中對日志塊順序存儲的限制，更新數(shù)據(jù)按寫操作的先后在對應的日志塊中依次存儲，提高了日志塊的空間利用率。由于在每頁的空閑區(qū)中存儲對應的邏輯地址，ram中地址映射表的大小與基于塊的地址映射機制相同。全相聯(lián)塊轉換策略fast(fullassociative sector translation)進一步放松對日志塊的限制，允許任何數(shù)據(jù)塊的更新數(shù)據(jù)存儲在任意日志塊的任意位置。這迸一步提高日志塊的空間利用率。降低垃圾回收的頻率，提高了性能。為通用計算環(huán)境設計的局部性感知的塊轉化策略(10calityaware sector translation，last)l181將日志塊

32、分為順序日志塊和隨機日志塊。順序日志緩沖區(qū)包含多個順序日志塊，能同時處理多個順序寫流。隨機日志緩沖區(qū)采用全相聯(lián)的地址映射機制。超級塊策略(superblock scheme)把相鄰的n個邏輯塊合并為一個超級塊，為每個超級塊分配m個日志塊。在一個超級塊內(nèi)，日志塊和數(shù)據(jù)塊都是共享的，數(shù)據(jù)塊內(nèi)的數(shù)據(jù)布局可隨更新頻率動態(tài)改變。當n=1，超級塊策略退化為日志塊策略。當n為flash存儲器中的總塊數(shù)時，超級塊策略就退化為fast。flash存儲器特殊的異地更新機制使得設計恰當?shù)牡刂酚成錂C制成為保證系統(tǒng)性能的重要方面之一。隨著flash存儲器的容量越來越大以及應用對flash存儲器性能的要求越來越高，地址映

33、射機制從簡單的單粒度映射到靈活的多粒度映射，有了很大的發(fā)展。然而，進一步設計具有自適應能力的地址映射機制仍是值得研究的課題。此外，針對通用計算環(huán)境的flash地址映射機制還沒有得到充分的研究。3.2垃圾回收 由于flash存儲采用異地更新的機制，隨著系統(tǒng)運行，flash存儲器中的空閑塊越來越少，無效數(shù)據(jù)越來越多，需要擦除這些包含無效數(shù)據(jù)的塊以得到新的空閑塊，這就是垃圾回收機制的功能。垃圾回收過程首先選擇一個進行回收的塊，將其中的有效頁復制到空閑塊中，更新地址映射信息，擦除該塊，最后把它加入空閑塊列表中。由于垃圾回收過程涉及數(shù)據(jù)復制以及耗時、耗能的擦除操作，還會降低可靠性，因此被認為是flash

34、存儲系統(tǒng)的性能瓶頸，成為研究的焦點之一。3.2.1垃圾回收的時機垃圾回收通常根據(jù)閾值觸發(fā)垃圾回收。閾值可以是靜態(tài)的，也可以是動態(tài)的。kawaguchi等人提出動態(tài)的閾值策略，綜合考慮了剩余空閑塊個數(shù)和垃圾回收的效益。為垃圾回收的效益設定閾值。當剩余的空閑塊較多時，閾值為無窮大，不進行垃圾回收。當空閑塊個數(shù)少于一定值后，閾值為有限值并隨空閑塊數(shù)目的減少而降低，最終為o。動態(tài)閾值的方法和靜態(tài)閾值相比，一方面考慮了垃圾回收的效益，提高了垃圾回收的性能，另一方面也使垃圾回收的啟動較慢，避免了存儲性能的突然降低。3.2.2 回收塊的選擇對回收塊的選擇與具體的地址映射以及日志塊的管理策略緊密相關，但總的原

35、則是以盡可能少的代價回收盡可能多的頁面。為了最大化垃圾回收的效益代價比，通常選擇包含無效頁個數(shù)最多的塊進行擦除。另一方面，flash存儲器擦除次數(shù)有限的限制，使得垃圾回收中選擇擦除的塊需要考慮其磨損程度的因素，這在3.3.1節(jié)中詳述。3.2.3 垃圾回收的合并操作 在混合式地址映射機制(超級塊策略除外)中，垃圾回收需要通過合并操作將數(shù)據(jù)塊和日志塊中的有效數(shù)據(jù)重新組織為塊內(nèi)順序存儲的形式。合并操作分為3種類型：交換合并、部分合并以及全合并。當數(shù)據(jù)更新為順序進行時，日志塊(也叫更新塊)中的數(shù)據(jù)可以直接轉化為新的數(shù)據(jù)塊，只需要擦除原來的數(shù)據(jù)塊即可，這樣的合并操作叫作交換合并。交換合并只需要進行一個擦

36、除操作即可。當數(shù)據(jù)更新是順序的，但在進行垃圾回收時日志塊還沒有被寫滿，需要把剩下的有效數(shù)據(jù)復制到日志塊中，再擦除原來的數(shù)據(jù)塊，這樣的合并操作叫作部分合并。在一般情況下，對數(shù)據(jù)的更新不是順序進行的，需要將數(shù)據(jù)塊和日志塊中的有效數(shù)據(jù)復制到一個空塊中，再擦除原來的數(shù)據(jù)塊和日志塊，這樣的合并操作叫作全合并。3種合并操作都只產(chǎn)生一個空閑塊，但代價卻有很大差別，交換合并的代價最小，全合并的代價最高。隨機寫會導致大量的全合并操作，只有順序寫時才會出現(xiàn)交換合并和部分合并。這就是flash存儲對順序寫的性能好，而隨機寫的性能很差的原因。表2給出幾種地址映射機制的垃圾回收代價比較。從中可以看出，提高日志塊的空間利

37、用率，降低垃圾回收的頻率是提高垃圾回收性能的有效途徑，此外，各種機制的設計還應該考慮到為垃圾回收過程提供更多的交換合并的機會。綜上所述，作為flash存儲系統(tǒng)的性能瓶頸，降低垃圾回收過程的代價成為設計高性能flash存儲系統(tǒng)設計的關鍵技術之一。為此，需要結合系統(tǒng)各個層次上的技術，包括地址映射機制，甚至上層軟件的buffer cache管理策略、索引數(shù)據(jù)結構與算法等。第四章 閃存連續(xù)存儲等概率存儲算法設計4.1磨損均衡 flash的每個存儲單元能夠進行的寫擦除操作次數(shù)有限，超過一定次數(shù)以后，數(shù)據(jù)的可靠性將不能得到保證。通常，slc(sin91e 1evel cell)f1ash存儲器的擦除次數(shù)上

38、限為1×105，而mlc(multiplelevel cell)flash存儲器則只有1 x 104。因擦除次數(shù)過多而被磨損的塊，一方面減少了flash存儲器的可用容量；另一方面可能造成用戶數(shù)據(jù)的丟失。磨損均衡機制的目標是將擦除操作均勻分布在flash存儲器中所有的塊上，最大化flash存儲器第1個磨損塊出現(xiàn)的時間，提高可靠性。4.1.1動態(tài)磨損均衡 動態(tài)損耗均衡算法的工作范圍就是更新頻繁的數(shù)據(jù)和未使用的空間, 在數(shù)據(jù)寫入時實現(xiàn)。這種算法針對閃存中的動態(tài)數(shù)據(jù)提供了較好的解決方法, 它能保證存在固定數(shù)量的空閑塊, 并能解決數(shù)據(jù)寫入延遲、堆積現(xiàn)象。在上面的動態(tài)損耗均衡算法中用到了兩個值,

39、 它們分別是min和th 1。其中min 表示的是當空閑塊鏈表為空時需要每次回收的臟塊數(shù)量。下面解釋一下th1 的含意。在動態(tài)損耗均衡算法中, 塊回收操作發(fā)生在空閑塊鏈表為空的時候, 而在回收臟塊的時候可能需要先將臟塊的有效數(shù)據(jù)進行復制, 所以在進行塊回收的時候需要按無效數(shù)據(jù)頁的降序進行擦除, 這里的th1 表示通過擦除的臟塊的下限, 在超過這個值之后便可以從臟塊鏈表的開始處進行塊的回收了。min 值的選擇, 要滿足的條件為min !th1。若min 的選擇過大, 會使空閑塊數(shù)增多, 從而減少閃存的可用空間; 若min 選擇過小, 則不能完全解決數(shù)據(jù)堆積的問題7。4.1.2靜態(tài)磨損均衡 所謂負

40、載均衡就是使用flash存儲器作為存儲系統(tǒng)時要盡量避免對同一個數(shù)據(jù)塊進行多次擦除操作，要使所有數(shù)據(jù)塊的擦除次數(shù)盡可能的平衡，樣才能延長flash存儲器的壽命，時也會提高系統(tǒng)性能。flash存儲介質上可能包括靜態(tài)文件。它的特點是有成塊的數(shù)據(jù)在很長的一段時間內(nèi)是不變化的，有的甚至和閃存存儲器的壽命一樣長。 如果負載平衡只應用于那些新寫入的扇區(qū)，那么靜態(tài)區(qū)域將永遠也得不到寫周期。這樣一來，如果閃存中含有大量的靜態(tài)數(shù)據(jù),flash存儲器的壽命就會大大降低。要解決這個問題，就要有相應的靜態(tài)負載平衡策略強迫數(shù)據(jù)像在動態(tài)區(qū)域中一樣在靜態(tài)區(qū)域上傳輸，這樣就能在整個存儲介質上應用負載平衡了8。4.2 設計的提出

41、本課題是根據(jù)當今閃存技術發(fā)展，移動存儲市場對閃存存儲設備的性能及壽命越來越高的需求所提出的，通過在傳統(tǒng)閃存文件存儲系統(tǒng)均勻損耗技術選擇存儲單元的基礎上為每個存儲單元添加存儲連續(xù)度參數(shù)，每次存儲均選擇從連續(xù)度最大的的存儲單元開始，并綜合考慮使用次數(shù)，從而避免某些閃存存儲單元因為被不均衡的過度利用導致整個閃存使用速度降低，達到提高性能，增加壽命的目的。4.3 設計方案本文提出的新型文件管理系統(tǒng)是對均勻損耗技術的改進，傳統(tǒng)的均勻損耗文件管理系統(tǒng)中文件的操作基本只考慮存儲空間使用次數(shù)，經(jīng)常會使文件支離破碎，文件管理極不合理，這樣長期下去會減少使硬盤碎片增多，從而影響硬盤壽命。而這種新型的管理系統(tǒng)的目標

42、正是為了克服這種情況而提出的，使得文件存儲操作更加科學便捷。4.4設計的基本思想在均勻損耗技術的基礎上加入一個新的功能尋找連續(xù)空間，即在每次有文件需要存儲的時候，對硬盤上的每一塊空間的操作次數(shù)進行一次排序，結合空間平均使用次數(shù)把文件存儲在連續(xù)程度較大的空間，以此類推，每存儲一次文件都進行一次排序，這樣存儲的文件具有很好的整體性，而且各個部分的操作次數(shù)也趨于一致，因此，改善了傳統(tǒng)管理系統(tǒng)的缺陷。排序申請內(nèi)存算法的具體內(nèi)容如下：假設內(nèi)存塊的序列定義為a=x1，x2，x3xw（w為正整數(shù)），某一時刻某一段的文件的存儲空間排列順序是xa，xb，xc, xd、xe，xf（a,b,c,d,e,f均為正整數(shù)

43、），當有新的文件需要存儲時會在文件存儲開始時對各個存儲空間的操作程度進行排序，選取任意一個數(shù)據(jù)作為關鍵數(shù)據(jù)，設兩個變量i、j,排序開始時i=0，j=w-1，把第一個數(shù)據(jù)x12作為關鍵數(shù)據(jù)，賦值給key，即key= x12；從j開始向前搜索，如式1-3所示；然后從i開始向后搜索，如式1-4所示，重復式1-3和1-4的操作，直到i=j。 4-1 4-2如此操作之后，存儲空間的順序發(fā)生了改變：xb，xa，xe, xd、xf，xc，于是新的文件存儲到排在前面的空間里，如果文件很大的話，會依次存放入第2、3、4空間內(nèi)，這樣就結束了一次文件的寫入操作，下次要求文件存儲時，新的文件存儲之前仍然要進行這種排序

44、操作，久而久之，每一塊存儲空間的利用程度達到均衡。建立此算法的數(shù)學模型，設閃存共有w個物理塊，每個物理塊最多能夠被寫入h次。每個物理塊上有k個物理頁，閃存已使用了m個物理頁來存放有效數(shù)據(jù)，序列e為一組需要存儲的文件物理頁號，e= p1, p2, p3pipl（l為正整數(shù)），序列f為存放更新后的存儲文件的物理頁頁號，f= q1, q2, q3qi ql（l為正整數(shù)），排序申請內(nèi)存算法將一個pi映射到qi的過程稱為一次執(zhí)行更新請求，要求執(zhí)行完l個更新請求之后，任何一個物理塊的擦除次數(shù)都未超過h，即 4-3如果任何一個物理塊的擦除次數(shù)超過了h，則存儲操作結束，操作次數(shù)被保存下來。 這種新型文件管理方

45、式是在閃存等概率存儲算法的基礎上加入了連續(xù)空間控制算法，使文件在存入過程中，盡量分配在連續(xù)空間內(nèi)，從而在文件的查找過程中節(jié)省一部分時間。在控制連續(xù)的過程中，同時也要考慮存儲單元的操作次數(shù)。需要在滿足連續(xù)存儲和操作次數(shù)合理這兩個前提下，達到一個最優(yōu)的穩(wěn)定狀態(tài)。為此筆者提出了一些算法來實現(xiàn)這一功能。首先是最常規(guī)的空閑空間利用算法：此算法由兩個算法組成4.5 具體設計新型閃存等概率存儲算法設計了兩個相對獨立的用于存儲閃存物理地址的動態(tài)鏈表，一個叫做寫入鏈表，另一個叫做刪除鏈表。寫入鏈表用來存儲閃存可用空間的物理地址，而刪除鏈表則有來存儲閃存已使用的空間的物理地址。兩個鏈表在設計上結構基本相同，新型閃

46、存等概率存儲算法為兩個鏈表的每一個節(jié)點均定義了相同格式，如圖4-1所示。 圖4-1 鏈表示意圖在圖4-1中，組成兩個鏈表的節(jié)點被劃分為4個區(qū)域，用于存儲相應的信息。常量用于存儲閃存物理的編號，它被賦予一個不變的固定值。變量一用于存儲該閃存塊已經(jīng)被寫入的次數(shù)，每當這個閃存塊被寫入一次這個數(shù)值就會被加1。第三個區(qū)域用于存儲在該閃存塊內(nèi)所存文件的編號，因為在許多時候一個文件的大小不會正好與閃存塊的大小相吻合，經(jīng)常需要使用多個閃存塊來存儲同一個文件，這就需要把文件分割開來存儲，每個閃存塊只存儲期中的一部分，為了防止在查找與刪除文件時發(fā)生混亂，新型閃存等概率存儲算法為每一段文件生成一個文件編號，既能表示

47、所屬文件的名稱，又能表示該部分在文件中的位置，該設計主要針對閃存物理地址編號和所存文件編號來設計，盡可能的將物理地址相近的空間存儲相同文件，當然寫入次數(shù)也是一個重要的參考依據(jù)，否則就會造成空間使用不均勻，減少使用硬盤壽命。鏈表指針用于存儲指向下一個節(jié)點的指針，因為在每次寫入前都會將寫入鏈表的每一個節(jié)點重新排序，所以各節(jié)點間的相對位置是經(jīng)常變化的。4.5.1 空間查詢算法假設內(nèi)存塊的序列定義為a=x1，x2，x3xixw（w為正整數(shù), i為1至w之間的任意數(shù)），假設r為空間判斷符，即ri為xi的空間判斷符，每次算法開始時，首先判斷r的大小來決定下一步操作：考察每一塊是否被占用，若該塊被占用，則r

48、=1；若未被占用，則r=0。則有： 4-4假設連續(xù)空間的數(shù)量用序列b=n1，n2，n3njnl（l為正整數(shù), j為1至l之間的任意數(shù)），序列里所有的參數(shù)默認值均為0，從x1開始，若其對應的r1為1，則n1自加1，如下所示： 4-5 完成這項操作之后，需要對n的值進行智能判斷： 4-6 同理，推廣到一般情況，則有 4-7 4-8結束序列b的賦值操作之后，需要對其進行從大到小的排序操作：選取任意一個數(shù)據(jù)作為關鍵數(shù)據(jù)，設兩個變量i、j,排序開始時i=0，j=l-1，把第一個數(shù)據(jù)n1作為關鍵數(shù)據(jù)，賦值給key，即key= n1；從j開始向前搜索，如式6所示；然后從i開始向后搜索，如式7所示，重復式6和

49、7的操作，直到i=j。 4-9 4-10完成操作之后，序列b完全成為連續(xù)空閑空間從大到小排列順序的序列。4.5.2 存儲查找空間算法假設每個內(nèi)存快的大小為x，存入文件的大小為y，存儲文件所占有的內(nèi)存塊數(shù)為k，則有： 4-11 4-12通過仿真現(xiàn)實的文件存儲過程，若kb1，即序列中有足夠的連續(xù)空間存儲這個文件，首先查找序列中是否有恰好可以存入此文件的空間， 4-13若不存在這樣一個與k恰好相等，則此文件存入長度稍大與k的空間之中： 4-14的值從逐漸自加，直到找到符合要求的空間為止。若kb1，即沒有連續(xù)空間可以完整的存儲這個文件，此時需要把文件分成幾個部分分別存儲，首先把len分成兩個部分：b1

50、與kb1。長度為b1的部分直接存入到b1代表的空間中，長度為kb1的部分要重新查找空間存入，查找方法與公式8所示的方法相同，這樣一個文件存儲過程結束。算法要經(jīng)過兩個步驟，當文件長度較小的時候，查找空間的速度是相當快的，但是當文件很大，占據(jù)很多個存儲單元的時候，查找適合存儲的空間序列就變得很困難，導致空間查找的時間會很長，從而失去了算法原有的優(yōu)越性。因此作者提出了另一種算法來解決這個問題。4.5.3 查找斷點算法此算法相較于前一個算法過程簡單了許多，只需要進行一個文件空間查找過程就可以完成。在文件存儲過程中，假設文件的大小為len,所占的空間為k，有序列c=c1，c2，c3ctcv（v為正整數(shù),

51、 t為1至v之間的任意數(shù)），系統(tǒng)需要在空閑塊鏈表中從第一個塊開始，對空間的連續(xù)程度進行檢查。查詢空間的方法與空間查詢算法相似，只不過查詢的連續(xù)長度是，每次長度為的空間被間斷多少次，如公式和所示，一直判斷到r，把中間的間斷次數(shù)即的賦給c1，同時記錄下空間查找的起始地址，即第一塊，所以序列是一個二維數(shù)組，間斷次數(shù)和起始地址同時存入數(shù)組的元素當中。如完成上述操作之后有c1=j，c11=1，繼續(xù)以第二塊為首地址進行查找。在公式6中 4-15 完成所有操作之后，序列c中存儲了所有可以放入所占空間為的連續(xù)空間的信息，在這些數(shù)據(jù)中，找到間斷次數(shù)最小的，就是文件應該存入的最合理空間。4.6算法的實現(xiàn)4.6.1

52、 閾值操作查找斷點算法主要作用是查找連續(xù)空間，使得文件存入到相對連續(xù)空間中，使得文件的讀取和查找時間減少。與此同時，文件存儲的時間會延長，同時每一個存儲塊的利用的均衡程度也會受到影響。為了達到良好的優(yōu)化效果，需要在連續(xù)空間和均衡存儲之間達到平衡，使得在文件存儲過程中兩者可以兼顧，達到更好的存儲管理效果。設文件存儲的最優(yōu)狀態(tài)為best，文件的空間的連續(xù)度為cont，文件空間的平均使用次數(shù)為ave，x為調整參數(shù)。每次文件存儲過程中，需要把適合存入的空間系統(tǒng)進行適合存儲程度進行排序。如公式 4-16通過這一過程使得文件在存儲過程中對兩個難點的解決方法進行了平衡。4.6.2 工作過程程序開始時對程序進

53、行初始化操作，生成仿真所需的存儲區(qū)域，初始化完畢后準備進行文件操作當閃存接到新指令時，新型閃存等概率存儲算法將會先進行一次判斷，判斷該指令是寫入指令還是刪除指令，若是寫入指令，系統(tǒng)會自動轉入寫入子程序，若是刪除指令，系統(tǒng)會轉入刪除子程序。每次執(zhí)行完操作后對存儲單元進行整理，如圖4-2所示：圖4-2 總體流程圖若確定為寫入操作，接到指令后，寫入子程序將會先進行一次判斷，假設存入文件所占用的內(nèi)存塊數(shù)為k，閃存的空閑塊數(shù)為c，進行如式4-1的判斷，若r=0，則返回操作，發(fā)出警告；若r=1則進行存儲,將參照文件的大小考察所有的存儲空間的連續(xù)程度和寫入次數(shù)，將文件存入最適合的空間內(nèi)。同時將用于寫入該文件

54、存儲物理地址的節(jié)點從寫入鏈表中刪除，保存在刪除鏈表中。 4-1存儲子程序流程圖如圖4-3所示： 圖5-3 存儲子程序流程圖若為刪除操作，則正好相反，接到指令后，刪除子程序也將會進行一次判斷，判斷閃存中是否存在所要刪除的文件，若不存在該文件則發(fā)出警告，若存在該文件則馬上通過指定文件的文件編碼找到其相對應的刪除鏈表中的節(jié)點，把該文件的所有部分刪除，然后將這些節(jié)點從刪除鏈表中刪除，然后保存在寫入鏈表中。刪除子程序流程圖如4-4所示： 圖4-4 刪除子程序流程圖 最佳節(jié)點的選取是本算法的核心，在每次選取最佳節(jié)點時先對存儲單元按存儲編號進行由小到大的整理，然后獲取需要存儲文件長度，創(chuàng)造一個臨時指針pme

55、m用來記錄文件首地址，最開始指向存儲鏈表首地址，再創(chuàng)造一個qmem向后指向數(shù)文件長度個存儲空間并記錄空間連續(xù)長度cont，若qmen->num+1=qmen->link->num則cont加一，并將cont*x-ave賦予temp（其中x是連續(xù)度所占比例系數(shù)，x越高則連續(xù)所占比例越大，x越小這均勻損耗所占比例越大）。pmen向后移動比較每次的temp，知道pmen為空，并將最小的temp賦予best。創(chuàng)造一個rmen記錄best所屬文件的首地址，文件從rmem一次存入存儲鏈表并將對應存儲鏈表轉移到刪除鏈表，流程圖如圖4-5所示： 圖4-2節(jié)點選擇流程圖第五章 閃存連續(xù)存儲等概率存儲算法仿真為了檢驗該算法的可行性和正確性，筆者用c+語言編寫了一個仿真文件管理系統(tǒng)，通過程序的運行，來驗證這個算法。5.1 c+具