臺灣博碩士論文加值系統

　　在快閃記憶體大量用於嵌入式系統的同時，嵌入式系統上的應用程式強大的資料管理需求和快閃記憶體的大容量皆反應需要有一個好的資料管理方。目前在快閃記憶體上的檔案系統或索引結構大都使用邏輯位址的方式，不僅掃描時間長且系統資訊需要佔用掉大量的記憶體。這篇論文試著使用實體參照的方式實作一個skip list 為基礎的索引結構，克服實體參照在nor 快閃記憶體上獨特的議題，如指標更新傳遞、垃圾回收死結等，提供一個有效率的資料管理方案。而文末將demo 如何在skip list 為索引結構的資料管理前提下，簡單的在上面疊架一個檔案系統。

Flash memory has become a crucial component in building embedded computing systems. To manage a massive amount of data, index structures or file systems are needed. The physical characteristics of flash memory, write once and bulk erase in particular, impose many difficulties on realizing structured data. In past work, the notion of logical address space is introduce to decouple changes to data and to the physical addresses of them. To map between logical addresses and physical addresses, RAM-resident translation tables are needed, it may require lengthy initialization scan procedure. In this work, a skip-list implementation based on physical pointers is proposed. It is to investigate the feasibility of organizing data with physical pointers over flash memory. The benefits are that no translation tables and initialization scan are needed. It is also demonstrated that a file system can be easily realized based on the proposed skip-list implementation

一、 Introduction …………………………………………… 1
二、 Motivation ……………………………………………… 2
2.1 Flash-memory characteristics ……………………… 3
2.2 Logical pointers ……………………………………… 4
2.3 Physical pointers ……………………………………… 5
2.4 Skip-list over Nor Flash …………………………… 7
三、 Background and Related Work ………………………… 8
四、 A Skip-List-Based File System over NOR flash … 9
4.1 Fundamental Issue ……………………………………… 9
4.1.1 Pointer-Update Propagation ………………………… 10
4.1.2 Garbage–Collection Deadlock ……………………… 11
4.1.3 Fast initialization …………………………………… 12
4.2 A Skip-List Implementation ………………………… 13
4.2.1 Physical Pointers and Block Layout ……………… 13
4.2.1.1 Object layout in blocks ……………………………… 13
4.2.1.2 Pointer-update mechanism …………………………… 14
4.2.2 Garbage Collection …………………………………… 16
4.2.3 Split and Merge action of Partition ……………… 18
4.2.4 Pointer Scrubbing ……………………………………… 21
五、 A Skip-List-Based File System ……………………… 23
5.1 Metadata Objects and Data Objects ………………… 24
5.2 Key-coding scheme ……………………………………… 24
5.3 File Operations and Directory Operations ……… 26
5.4 File System mount ……………………………………… 29
六、 Evaluation ……………………………………………… 30
6.1 Experimental Setup and Performance Metrics …… 30
6.2 系統指標讀取負擔分析 ………………………………… 34
6.3 機率和階層的分析 ……………………………………… 36
6.4 一個區塊中預留指標個數和物件個數的比例評估 …… 39
6.5 區塊穩定度策略對系統hot/code資料的分佈影響 …… 40
七、 Conclusion ……………………………………………… 41
八、 Future Work ……………………………………………… 42
參考文獻 ……………………………………………………………… 43

[1]: William Pugh, "Skip lists: a probabilistic alternative to balanced trees, " Communications of the ACM archive, Vol 33, Issue 6, 1990
[2] Intel Corporation, "Understanding the Flash Translation Layer(FTL) Specification".
[3] M-Systems, Flash-memory Translation Layer for NAND Fash (NFTL).
[4] D. Woodhouse, Red Hat, Inc. "JFFS: The Journalling Flash File System".
[5] D. Woodhouse, "JFFS: The Journaling Flash File System,"
[6] Artem B. Bityutskiy, "JFFS3 design issues," http://www.linux-mtd.infradead.org/tech/JFFS3design.pdf.
[7] C. Manning and Wookey, "YAFFS Specification," Aleph One Limited, http://www.aleph1.co.uk/node/37, Dec, 2001.
[8] Chin-Hsien Wu, Li-Pin Chang, and Tei-Wei Kuo, "An Efficient B-Tree Layer Implementation for Flash-Memory Storage Systems," Accepted and to appear in ACM Transactions on Embedded Computing Systems.
[9] Chin-Hsien Wu, Li-Pin Chang, and Tei-Wei Kuo, "An Efficient R-Tree Implementation for Flash-Memory Storage Systems," the ACM GIS conference, 2003
[10] Zeinalipour-Yazti, D., Lin, S., Kalogeraki, V., Gunopulos, D., and Najjar, W. 2005. Mi-crohash: An efficient index structure for flash-based sensor devices. In 4th USENIX Conference on File and Storage Technologies (FAST). 31–44.
[11] University of Szeged , "JFFS2 improvement project ," http://www.inf.u-szeged.hu/jffs2/mount.php
[12] Keun Soo Yim, Jihong Kim, and Kern Koh, "A Fast Start-Up Technique for Flash Memory Based Computing Systems," the ACM Symposium on Applied Computing (ACM SAC), 2005.
[13] Chin-Hsien Wu, and Tei-Wei Kuo, Li-Pin Chang, "Efficient Initialization and Crash Recovery for Log-based File Systems over Flash Memory," the 21st ACM Symposium on Applied Computing (ACM SAC), 2006.
[14] Hans Reiser, "ReiserFS file system," http://www.namesys.com/
[15] C. P. Wright and R. Spillane and G. Sivathanu and E. Zadok, "Extending ACID Semantics to the File System," ACM Transactions on Storage, To appear.
[16] Samsung Electronics Company, "K5A3x40YT(B)C 32M Bit (4Mx8/2Mx16) Dual Bank NOR Flash Memory datasheet
[17] MXIC Electronics Company, "MX-29LV160CBTC-90G 16M-BIT [2Mx8/1Mx16] CMOS SINGLE VOLTAGE 3V ONLY FLASH MEMORY" datasheet
[18] Compact Flash Association, "Compact FlashTM 1.4 Specification," 1998.
[19] SSFDC Forum,"SmartMediaTM Specification," 1999.
[20] Li-Pin Chang, Tei-Wei Kuo, "An Adaptive Striping Architecture for Flash Memory Storage Systems of Embedded Systems," The 8th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2002) September 24 ?27, 2002. San Jose, California.