臺灣博碩士論文加值系統

NAND 型快閃記憶體有非揮發、體積小、消耗能量低、耐撞擊等等特性，使其成為設計嵌入式系統、手持式行動裝置時，作為主要儲存裝置的首選。但NAND 型快閃記憶體有讀取快，寫入慢，且有非本地更新的限制，故在使用NAND 型快閃記憶體時，設計者常使用快閃記憶體轉換層(Flash Translation Layer, FTL) 將這些特性隱藏，使NAND 型快閃記憶體能如同一般的區塊裝置使用。FTL 同時負責管理抹除位址，以平均每個區塊的抹除次數，此乃因NAND 型快閃記憶體每個區塊的抹除次數有限。
在傳統針對磁碟機設計的分頁子系統上使用NAND 型快閃記憶體作為分頁機制儲存裝置時，直接使用FTL 時會產生多餘有效頁搬移的情形。本論文修改核心，使用無效化機制來減少多餘的有效頁搬移情形。並使用Swap FTL來管理底層的NAND型快閃記憶體，有效平均各區塊的抹除次數，延長NAND 型快閃記憶體壽命。
本論文並在Linux 上實作提出的機制，在MTD (Memory Technology Devices) 子系統內實作Swap FTL 來管理底層的NAND 型快閃記憶體分頁機制儲存裝置。效能評估部份，則先追蹤Linux 作業系統內分頁置換的位址，再將位址存取資訊輸入給MTD 子系統進行模擬分析。模擬結果顯示使用本論文提出的機制能有效地降低
NAND 型快閃記憶體的讀取、寫入、抹除、以及有效頁搬移次數；NAND 型快閃記憶體各區塊的抹除次數也較平均，其使用壽命因而能增長。

NAND flash memory comes with features such as non-volatile, small physical size, low-power consumption, good shock-resistance etc. such that system designers tend to use NAND flash memory as the primary storage when designing mobile devices. However, the characteristics of out-of-place update, wear-leveling, and block-erasing make it very different from a hard disk. In an operating system with virtual memory, these characteristics become challenging issues when using NAND flash memory as paging device.
This thesis presents a study in using NAND flash memory as the paging device in virtual memory management. An investigation on FTL (Flash Translation Layer), which is a common approach to encapsulate the characteristics of NAND flash memory, and the interaction between virtual memory management subsystem and paging device is undertaken. We propose a Swap FTL to manage NAND-Flash-based paging device. In addition to the functions which are commonly supported by FTL such as logical-physical address mapping, in-place update emulation, erase address management, Swap FTL provides a feature to avoid unnecessary living-copies caused by the out-of-place-update characteristic of NAND Flash. To support this feature, the kernel needs merely to implement an invalidation mechanism.
To demonstrate the functionality of Swap FTL, a demo version is implemented in the MTD subsystem of Linux operating system. Its performance is evaluated by feeding a trace of paging addresses logged during some real-world operations. The results show that our approach works effectively and reduces the number of read, write, erase, and living-copies. Furthermore, the erase operations are evenly distributed to the blocks of NAND flash memory.

目錄
摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vii
圖目錄 viii
1 簡介 1
1.1 背景知識. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 虛擬記憶體. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 論文組織. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 相關研究 10
2.1 嵌入式作業系統的記憶體管理. . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 無記憶體管理單元之記憶體管理. . . . . . . . . . . . . . . . . . 10
2.1.2 使用記憶體管理單元之記憶體管理. . . . . . . . . . . . . . . . 12
2.2 快閃記憶體轉換層對應方法. . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 無效空間回收管理策略. . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 使用NAND型快閃記憶體作為分頁機制儲存裝置. . . . . . . . . . . . 18
2.4.1 FASS: A Flash-Aware Swap System . . . . . . . . . . . . . . . . . 19
2.4.2 修改分頁置換策略. . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.3 調整分頁大小. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 NAND 型快閃記憶體存取的加速. . . . . . . . . . . . . . . . . . . . . . 20
2.6 NAND 型快閃記憶體檔案系統. . . . . . . . . . . . . . . . . . . . . . . 21
2.6.1 JFFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6.2 YAFFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 討論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 NAND型快閃記憶體分頁機制之設計 26
3.1 系統架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 多餘的有效頁搬移. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 無效化機制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 Swap FTL - NAND型快閃記憶體管理層的設計. . . . . . . . . . . . . . 31
3.5 大區塊NAND型快閃記憶體的特性與限制. . . . . . . . . . . . . . . . 33
3.6 討論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 NAND型快閃記憶體分頁機制實作 35
4.1 系統架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Linux 的置換系統. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 NAND 型快閃記憶體分頁機制儲存裝置. . . . . . . . . . . . . . . . . . 39
4.4 使用NAND型快閃記憶體分頁儲存裝置帶來的問題. . . . . . . . . . . 40
4.4.1 回收時多餘的搬移動作. . . . . . . . . . . . . . . . . . . . . . . 41
4.4.2 無效化機制的實作. . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4.3 循序寫入的限制. . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5 Swap FTL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5.1 NAND型快閃記憶體分頁機制儲存裝置管理系統. . . . . . . . 50
4.5.2 邏輯-實體位址對應表設計. . . . . . . . . . . . . . . . . . . . . 50
4.5.3 NAND型快閃記憶體寫入位址的決定. . . . . . . . . . . . . . . 50
4.5.4 可用空間分配策略. . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.5.5 無效資料的回收策略. . . . . . . . . . . . . . . . . . . . . . . . 54
4.5.6 空間的管理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5 效能評估 60
5.1 測試環境. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2 模擬考量. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 模擬結果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.1 NAND型快閃記憶體實體空間大小的影響. . . . . . . . . . . . 62
5.3.2 無效化機制的影響. . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3.3 k值的影響. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3.4 抹除位址的分析. . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.5 與YAFFS2的比較. . . . . . . . . . . . . . . . . . . . . . . . . . 66
6 結論與展望 67
6.1 結論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2 展望. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
參考文獻 70
附錄NAND 型快閃記憶體的基本操作 74
自述 75

[1] “Demand Paging on Symbian OS”,
http://www.symbian.com/symbianos/demandpaging/index.html.
[2] “JFFS2”, http://en.wikipedia.org/wiki/JFFS2.
[3] “K9F8G08B0M Datasheet”,
http://www.samsung.com/Products/Semiconductor/NANDFlash/index.htm.
[4] “YAFFS - A Flash file system for embedded use”,
http://www.yaffs.net/.
[5] Tom Archer, “ReadyBoost “Q&A””,
http://blogs.msdn.com/tomarcher/archive/2006/06/02/615199.aspx.
[6] Daniel P. Bovet and Marco Cesati, “Understanding the Linux Kernel”, 3rd edition,
O’Reilly, 2005, ISBN: 0-596-00565-2.
[7] Mike Calligaro, “Paging Dr. RAM”,
http://blogs.msdn.com/windowsmobile/archive/2006/03/31/566187.aspx.
[8] Li-Pin Chang and Tei-Wei Kuo, “An Adaptive Striping Architecture for Flash Memory
Storage Systems of Embedded Systems, Proceedings of the Eighth IEEE Real-Time
and Embedded Technology and Applications Symposium, page 187, 2002.
[9] M. Chiang, P. Lee, and R. Chang, “Managing Flash Memory in Personal Communication
Devices”, Proceedings of the 1997 International Symposium on Consumer
Electronics (ISCE’97), pages 177–182, 1997.
[10] Mei-Ling Chiang, Paul C. H. Lee, and Ruei-Chuan Chang, “Using data clustering to
improve cleaning performance for flash memory”, Software Practice and Experience,
29(3):267–290, 1999.
[11] Mel Gorman, “Understanding The Linux Virtual Memory Manager”, Prentice Hall,
2004, ISBN: 0-13-145348-3.
[12] Yongsoo Joo, Yongseok Choi, Chanik Park, Sung Woo Chung, EuiYoung Chung,
and Naehyuck Chang, “Demand paging for OneNAND Flash eXecute-in-place”, In
CODES+ISSS ’06: Proceedings of the 4th international conference on Hardware/software
codesign and system synthesis, pages 229–234, New York, NY, USA, 2006. ACM
Press.
[13] Dawoon Jung, Jin-Soo Kim, Seon-Yeong Park, Jeong-Uk Kang, and Joonwon Lee,
“FASS: A Flash-Aware Swap System”, Proceedings of International Workshop on
Software Support for Portable Storage, 2005.
[14] Jesung Kim, Jong Min Kim, S.H. Noh, Sang Lyul Min, and Yookun Cho, “A spaceefficient
flash translation layer for CompactFlash systems”, IEEE Transactions on Consumer
Electronics, 48:366–375, 2002.
[15] Russell King, “The ARM Linux Project”, http://www.arm.linux.org.uk/.
[16] Jean J. Labrosse, “MicroC/OS II: The Real Time Kernel”, CMP Books, 2002, ISBN:
1-57820-103-9.
[17] Charles Manning, “Introduction to YAFFS, the first NAND-specific flash file system”,
http://www.linuxdevices.com/articles/AT9680239525.html.
[18] David McCullough, “uClinux for Linux Programmers”, Linux Journal, 123, July 2004.
[19] Chanik Park, Jeong-Uk Kang, Seon-Yeong Park, and Jin-Soo Kim, “Energy-aware
demand paging on NAND flash-based embedded storages”, Proceedings of the 2004
international symposium on Low power electronics and design, pages 338–343, 2004.
[20] Chanik Park, Jaeyu Seo, Sunghwan Bae, Hyojun Kim, Shinhan Kim, and Bumsoo Kim,
“A low-cost memory architecture with NAND XIP for mobile embedded systems, Proceedings
of the 1st IEEE/ACM/IFIP international conference on Hardware/software
codesign and system synthesis, pages 138–143, 2003.
[21] David A. Patterson and John L. Hennessy, “Computer organization and design: the
hardware/software interface”, 3rd edition, Morgan Kaufmann Publishers Inc., San
Francisco, CA, USA, 2005, ISBN: 9812592172.
[22] Mendel Rosenblum and John K. Ousterhout, “The design and implementation of a
log-structured file system”, ACM Trans. Comput. Syst., 10(1):26–52, 1992.
[23] Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, “Operating System Concepts”,
6th edition, John Wiley & Sons, Inc., 2001, ISBN: 0-471-25060-0.
[24] Hung-Wei Tseng, Han-Lin Li, and Chia-Lin Yang, “An energy-efficient virtual memory
system with flash memory as the secondary storage, Proceedings of the 2006 international
symposium on Low power electronics and design, pages 418–423, 2006.
[25] Michael Wu and Willy Zwaenepoel, “eNVy: a non-volatile, main memory storage
system”, Proceedings of the sixth international conference on Architectural support
for programming languages and operating systems, pages 86–97, 1994.
[26] Karim Yaghmour, “Building Embedded Linux Systems”, O’Reilly, 2003, ISBN: 0-
596-00222-X.
[27] 許勝杰, “快閃記憶體儲存管理系統之設計與實作”, 國立成功大學, 2004.
[28] 莊俊傑, “異質性處理器核心嵌入式系統之動態程式碼疊置機制之設計與實作”,
國立成功大學, 2006.
[29] 薛智文, “作業系統”, 旗標出版, 2002.