簡易檢索 / 詳目顯示

回結果列表
研究生： 王廷維
Ting-wei Wang
論文名稱： 基於有限記憶體下的快閃記憶體垃圾回收管理法則
A Garbage Collection Management Method with Limited RAM Space for Flash Memory
指導教授： 吳晉賢
Chin-Hsien Wu
口試委員: 陳維美
Wei-Mei Chen
林昌鴻
Chang Hong Lin
陳雅淑
Ya-Shu Chen
學位類別： 碩士
Master
系所名稱： 電資學院 - 電子工程系
Department of Electronic and Computer Engineering
論文出版年： 2014
畢業學年度： 103
語文別： 英文
論文頁數： 40
中文關鍵詞： NAND型快閃記憶體 、快閃記憶體轉換層 、垃圾回收機制 、儲存裝置
外文關鍵詞： NAND flash memory, Flash Translation Layers, Garbage collections, Storage Systems
相關次數： 點閱：306  下載：7 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • NAND型快閃記憶體大量的被用於行動設備，電腦裝置和企業的計算機系統中，當我們使用NAND型快閃記憶體作為儲存裝置，由於其本身必須先抹除才能寫入的特性，因此需要專門的垃圾回收機制，垃圾回收機制包含一系列操作 (包括讀取、寫入、以及抹除指令)才能完成，這會嚴重的降低NAND型存儲系統的效能。在本篇論文中，我們提出一個考量有限的記憶體情況下的垃圾回收管理方法，在記憶體空間的限制條件下，我們的方法可以和過去所提出的垃圾回收演算法進行合作，實驗結果證明我們提出的方法可以減少65百分比到95百分比的記憶體使用量，並且控制額外指令開銷在1.5百分比以下。

    NAND flash memory has been used for storage in mobile devices, PCs and enterprise systems. When we use NAND flash memory as data storage, it requires a garbage collection procedure due to its erase-before-write characteristic. Garbage collection consists of a series of activities (such as read, write, and erase operations) that usually degrade the performance of NAND-based storage systems. In this thesis, we propose a garbage collection management method with limited RAM space for flash memory. The proposed method can cooperate with the previous garbage collection algorithms with limited RAM space. The experimental results show that the proposed method can reduce the RAM space requirements as much as 65\% to 95\% and only cause less than 1.5\% increase in the amount of the original workloads.

    中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VIII 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Background Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 Characteristics of Flash Memory . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Flash Translation Layers . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Garbage collection procedure . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Previously works of garbage collection . . . . . . . . . . . . . . . . . . . 6 3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4 A Garbage Collection Management Method with Limited RAM Space for Flash Memory . . . . 11 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Data Structures and Operations . . . . . . . . . . . . . . . . . . . . . . . 12 4.2.1 Global Block Status Table . . . . . . . . . . . . . . . . . . . . . 12 4.2.2 Victim Block Status Table (in RAM space) . . . . . . . . . . . . 14 4.2.3 Recently Used Block Status Table (in RAM Space) . . . . . . . . 15 4.2.4 Index Table (in RAM Space) . . . . . . . . . . . . . . . . . . . . 16 4.3 Selection of Victim Blocks . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.4 Shuffling of Victim Blocks . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.5 Recycling of Victim Blocks . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.6.1 Performance Enhancement for Shuffling of Victim Blocks . . . . 23 4.6.2 Initialization and Crash Recovery . . . . . . . . . . . . . . . . . 24 5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.1 Experimental Setup and Performance Metrics . . . . . . . . . . . . . . . 26 5.2 Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2.1 Average number of valid pages copied and free space reclaimed . 29 5.2.2 Average number of block erasures and the standard deviation . . . 31 5.2.3 Shuffling overhead and replacement overhead . . . . . . . . . . . 33 6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    [1] Roberto. Bez, Emilio. Camerlenghi, Alberto. Modelli, and Angelo. Visconti. Introduction
    to flash memory. in Proceedings of the IEEE, 91(4):489–502, April 2003.
    [2] Adam Leventhal. Flash storage memory. Commun. ACM, 51(7):47–51, July 2008.
    [3] Aayush Gupta, Youngjae Kim, and Bhuvan Urgaonkar. DFTL: A flash translation
    layer employing demand-based selective caching of page-level address mappings.
    In Proceedings of the 14th International Conference on Architectural Support for
    Programming Languages and Operating Systems, ASPLOS XIV, pages 229–240,
    New York, NY, USA, 2009. ACM.
    [4] Jesung Kim, Jong Min Kim, S.H. Noh, Sang Lyul Min, and Yookun Cho. A spaceefficient
    flash translation layer for compactflash systems. Consumer Electronics,
    IEEE Transactions on, 48(2):366–375, May 2002.
    [5] Chin-Hsien Wu and Tei-Wei Kuo. An adaptive two-level management for the flash
    translation layer in embedded systems. In Proceedings of the 2006 IEEE/ACM International
    Conference on Computer-aided Design, ICCAD ’06, pages 601–606, New
    York, NY, USA, 2006. ACM.
    [6] Soo-Young Kim and Sung-In Jung. A log-based flash translation layer for large
    NAND flash memory. In Advanced Communication Technology, 2006. ICACT 2006.
    The 8th International Conference, volume 3, pages 1641–1644, Feb 2006.
    [7] Sang-Won Lee, Dong-Joo Park, Tae-Sun Chung, Dong-Ho Lee, Sangwon Park, and
    Ha-Joo Song. A log buffer-based flash translation layer using fully-associative sector
    translation. ACM Transactions on Embedded Computing Systems, 6(3), July 2007.
    [8] Hyunjin Cho, Dongkun Shin, and Young Ik Eom. Kast: K-associative sector translation
    for nand flash memory in real-time systems. In Proceedings of the Conference
    on Design, Automation and Test in Europe, DATE ’09, pages 507–512, 3001 Leuven,
    Belgium, Belgium, 2009. European Design and Automation Association.
    [9] Sungjin Lee, Dongkun Shin, Young-Jin Kim, and Jihong Kim. Last: Locality-aware
    sector translation for nand flash memory-based storage systems. ACM SIGOPS Operating
    Systems Review, 42(6):36–42, October 2008.
    [10] Mendel Rosenblum and John K. Ousterhout. The design and implementation of a
    log-structured file system. ACM SIGOPS Operating Systems Review, 25(5):1–15,
    1991.
    [11] Atsuo Kawaguchi, Shingo Nishioka, and Hiroshi Motoda. A flash-memory based
    file system. in Proceedings of the USENIX 1995 Technical Conference Proceedings,
    pages 13–13, 1995.
    [12] Sang-goo Lee Han-joon Kim. An effective flash memory manager for reliable
    flash memory space management. IEICE Transactions on Information and System,
    85:950–964, 2002.
    [13] Mei-Ling Chiang and Ruei-Chuan Chang. Cleaning policies in mobile computers
    using flash memory. Journal of Systems and Software, 48(3):213 – 231, 1999.
    [14] Li-Pin Chang. On efficient wear leveling for large-scale flash-memory storage systems.
    In Proceedings of the 2007 ACM Symposium on Applied Computing, SAC ’07,
    pages 1126–1130, New York, NY, USA, 2007. ACM.
    [15] Ohhoon Kwon, Kern Koh, Jaewoo Lee, and Hyokyung Bahn. FeGC: An efficient
    garbage collection scheme for flash memory based storage systems. Journal of Systems
    and Software, 84(9):1507–1523, September 2011.
    [16] Bongjae Kim, Minkyu Park, Cheol Jeon, Chang Oan Sung, Yookun Cho, and Jiman
    Hong. Aagc: An efficient associativity-aware garbage collection scheme for hybrid
    ftls. In Proceedings of the 27th Annual ACM Symposium on Applied Computing,
    SAC ’12, pages 1785–1790, New York, NY, USA, 2012. ACM.
    [17] David Woodhouse. JFFS : The journalling flash file system. https://sourceware.
    org/jffs2/jffs2.pdf, 2001. Proceedings of Ottawa Linux Symposium.
    [18] Charles Manning and Wookey. YAFFS specification, 2012. Aleph One Limited.
    [19] Ray Lucchesi. SSD flash drives enter the enterprise. http://www.
    silvertonconsulting.com/newsletterd/SSDf_drives.pdf, 2008. Silverton
    Consulting.
    [20] Chin-Hsien Wu, Tei-Wei Kuo, and Li-Pin Chang. The design of efficient initialization
    and crash recovery for log-based file systems over flash memory. ACM Transactions
    on Storage, 2(4):449–467, 2006.
    [21] SAMSUNG Electronics. http://www.vo.gme.cz/dokumentace/944/944-055/
    dsh.944-055.1.pdf. 2G x 8 Bit / 4G x 8 Bit / 8G x 8 Bit NAND Flash Memory
    Datasheet.
    [22] Ken Bates and Bruce McNutt. http://traces.cs.umass.edu/index.php/
    Storage/Storage. OLTP Application I/O.
    [23] Bruce Worthington Vishal Sharda, Swaroop Kavalanekar. http://iotta.snia.
    org/traces/158. IOTTA Respository.
    [24] Futuremark benchmark development. http://www.futuremark.com/
    benchmarks/pcmark7. PCMark 7.
    [25] Disk monitor. http://technet.microsoft.com/en-us/sysinternals/bb896646.aspx.

    QR CODE