NAND flash (快閃記憶體) 在空間不夠寫入的情況下會利用garbage collection的機制來回收free page。然而，garbage collection發生的時機無法被預估而且會延長task的response time (回應時間)。 在即時系統中，為了確保task不會miss deadline，一個task的maximum response time被估計為task 及garbage collection的執行時間總和，而這時間總和被稱為worst case response time。 過去許多研究都專注於尋找worst case response time的最佳解去降低response time的 jitter (振盪)，藉以改善NAND flash的讀寫效能。
在本篇論文中，我們提出two-mode GC的機制，讓scheduler得知有哪些write request將被garbage collection所延遲，使得scheduler能夠有更精準的排程以達到提升NAND flash的即時寫入效能，在模擬實驗中，在與先前方法所測得的average access time(平均存取時間)相近的情況下，two-mode GC可以擁有較好的排程來增加NAND flash的寫入效能。

The garbage collection (GC) mechanism in NAND flash reclaims free pages based on erasing blocks as a unit and causes delay of response time. Hence, the response time of a task is estimated as the worst case response time which is coupled with task execution time and GC time to avoid missing deadline in real-time system. Many studies focused on finding the optimal worst case response time to improve NAND flash performance. In this paper, we propose a two-mode GC mechanism which separates NAND flash to two modes: normal mode and gc mode. We also give conditions to switch modes and prove the conditions are optimal. In the simulation results, the average access time of two-mode GC is closed to WAO-GC, and two-mode GC can let scheduler know which write request would delay by garbage collection. So that, the schedule is more accurate, and the writing performance of NAND flash is raised.

[1] TechNews.”TechNews” Internet: http://technews.tw/2014/08/26/nand-flash-2015, 2014
[2] Hyunjin Cho, Dongkun Shin and Young Ik Eom, “KAST: K-Associative Sector Translation for NAND Flash Memory in Real-Time System,” Design, Automation & Test in Europe Conference & Exhibition, 20-24 April 2009, pp. 507-512
[3] Jesung Kim, Jong Min Kim, Sam H. Noh, Sang Lyul Min and Yookun Cho, “A Space-efficient Flash Translation Layer for CompactFlash Systems,” IEEE Transactions on Consumer Electronics, May 2002, pp. 366-375
[4] Sang Won Lee, Doug Joo Park, Tae Sun Chung, Dong Ho Lee, Sang Won Park and Ha Joo Song, “A Log Buffer-Based Flash Translation Layer Using Fully-Associative Sector Translation,” ACM Transactions on Embedded Computing Systems (TECS), vol. 6, no. 3, July 2007
[5] Chanik Park, Wonmoon Cheon, Jeonguk Kang, Kangho Roh and Wonhee Cho, “A Reconfigurable FTL(Flash Translation Layer) Architecture for NAND Flash-Based Applications,” ACM Transactions on Embedded Computing Systems (TECS), vol. 7, no. 4, July 2008
[6] Aayush Gupta, Youngjae Kim and Bhuvan Urgaonkar, “DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings,” Proceedings of the 14th international conference on Architectural support for programming languages and operating systems, 2009, pp. 229-240
[7] Atsuo Kawaguch, Shingo Nishioka, and Hiroshi Motoda, “A Flash-Memory Based File System,” Proceedings of the USENIX Technical Conference, 1995, pp. 13
[8] Mei-Ling Chiang, Paul C. H. Lee, Ruei-Chuan Chang, “Manage Flash Memory in Personal Communicate Devices,” Proceedings of 1997 IEEE International Symposium on Consumer Electronics, 2-4 Dec 1997, pp. 177-182
[9] Guangxia Xu, Yanbing Liu, Xiaoqin Zhang and Mingwei Lin, “Garbage Collection Policy to Improve Durability for Flash Memory,” IEEE Transactions on Consumer Electronics, vol. 58, no. 4, November 2012, pp. 1232-1236
[10] Sanghyuk Jung, “Garbage Collection for Low Performance Variation in NAND Flash Storage Systems,” IEEE transactions on computer-aided design of integrated circuits and systems, vol. 34, no. 1, January 2015, pp. 16-28
[11] Junghee Lee, Youngjae Kim , Shipman, G.M., Oral, S. Jongman Kim, ”Preemptible I/O Scheduling of Garbage Collection for Solid State Drives,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32, no. 2, February 2013, pp. 247 – 260
[12] Yi Qin, Dan Feng, Jingning Liu, Wei Tong and Zhiming Zhu, “DT-GC: Adaptive Garbage Collection with Dynamic Thresholds for SSDs,” 2014 International Conference on Cloud Computing and Big Data (CCBD), 12-14 Nov. 2014, pp.182-188
[13] Li-Pin Chang and Tei-Wei Guo, “Real-time Garbage Collection for Flash-memory Storage Systems of Real-time Embedded System,” ACM Trans. Embedded Comput. Syst., vol. 3, no. 4, Nov. 2004, pp. 837-863
[14] Siddharth Choudhuri, Tony Givargis, “Deterministic Service Guarantees for NAND Flash Using Partial Block Cleaning,” in Proc. 6th IEEE ACM Int. Conf. Hardw./Softw. Codesign Syst. Synth., GA, USA, October 2008, pp. 19-24
[15] Zhiwei Qin, Yi Wang, Duo Liu, Zili Shao,” Real-Time Flash Translation Layer for NAND Flash Memory Storage Systems,” Real-Time and Embedded Technology and Applications Symposium (RTAS), 16-19 April 2012, pp. 35 – 44
[16] Qi Zhang, Xuandong Li, Linzhang Wang, Tian Zhang, Yi Wang and Zili Shao, ”Optimizing Deterministic Garbage Collection in NAND Flash Storage Systems,” real-time and embedded technology and applications symposium, 13-16 April 2015, pp. 14-23
[17] “Samsung electronics.samsung K9K8G08U0B(v0.1)-8GB SLC NAND flash data sheet”, July 2008.