快閃記憶體由於具有耐震、省電以及成本低廉等特性，已經成為嵌入式產品的主流儲存裝置。然而，由於在執行寫入前必須抹除原有資料，造成空間回收的機制不定時的被觸發，此種不明確的執行時間傷害了系統的效能。猶有甚者，快閃記憶體先天上有著抹寫次數的限制，對其中任一區塊的過度抹寫會造成快閃記憶體的提早損壞。耗損平均的策略著眼於區塊的挑選，戮力於消除各區塊抹寫次數的差異。定時啟動回收工作的方式被提出來消除不明確的執行時間及達到均勻耗損。然而，過高的執行頻率使得系統必須負擔額外的回收成本；過低的執行頻率則易流於造成可用空間不足的窘境。在這個研究中，我們提出了一個均衡的回收機制，該機制藉由明確的寫入回應時間來滿足系統之所需，並且適時的啟動回收機制來保證足夠的空間的供給。在此篇論文中，我們提出了一個名為DBFTL均衡的回收機制。DBFTL於處理寫入需求時，以明確的回應時間為嵌入式系統提供可預測性，並且藉由適時的啟動回收機制來保證足夠的可用空間供給。實驗的結果顯示出DBFTL於任何時刻均能提供足夠的空間給系統使用，並且在讀寫的處理能力也有著較佳的表現。

Due to the characteristics of the flash memory, the NAND flash memory-based storage device has become the favorite of the embedded system. However, the non-deterministic response time of reclaiming space, which is subject to out-of-place writes, always degrades the system performance. Moreover, the flash memory has the constraint of the limited erase counts. Hence, any excessive erase operations on certain block would lead the flash memory into the premature death. Wear-leveling policies are devoted to the victim selection to eliminate the wear deviation of each block. A periodic based approach is proposed in the previous study to remove the uncertainty of the write response time and get the flash memory erased evenly. However, the frequency to trigger the periodical mechanism has a strong impact on the performance of reclaiming space. The over-recycling incurs the extra cost when the system has no demand for the space. Oppositely, less frequency imposes insufficient space while serving the write requests. In this thesis, we propose a balanced reclaiming scheme named DBFTL which provides the predictability for the embedded system with deterministic response time while servicing each write request and guarantees enough free space by the appropriately triggered timing. The simulation results show that DBFTL can provide sufficient space to use at any time and has the better performance in read/write throughput.

摘要 I
Abstract II
誌謝 III
Contents IV
List of Figures V
List of Tables VI
Chapter 1 Introduction 1
Chapter 2 Related Work 4
Chapter 3 Time/Space Balanced Flash Translation Layer (DBFTL) 6
3.1 YaFTL & LWD 6
3.2 DBFTL 7
3.2.1 Predictable Response Time 7
3.2.2 Sufficient space 8
3.2.3 Victim Selection 11
Chapter 4 Experimental Results 13
4.1 Environment 13
4.2 Deterministic Write Latency and Throughput 14
4.3 The Quantity of Free Pages 16
Chapter 5 Conclusions and Future Work 18
References 19

[1] T. A. Henzinger, "Two Challenges in Embedded Systems Design: Predictability and Robustness," Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 366, pp. 3727-3736, October 2008.
[2] A. Kawaguchi, S. Nishioka, and H. Motoda, "A Flash-memory Based File System," in Proceedings of the USENIX 1995 Technical Conference New Orleans, Louisiana: USENIX Association, 1995.
[3] L. Chang, T. Kuo, and S. Lo, "Real-time Garbage Collection for Flash-memory Storage Systems of Real-time Embedded Systems," ACM Transactions on Embedded Computing Systems (TECS), vol. 3, pp. 837-863, 2004.
[4] S. Choudhuri and T. Givargis, "Deterministic Service Guarantees for Nand Flash Using Partial Block Cleaning," in Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis Atlanta, GA, USA: ACM, 2008.
[5] S. Choudhuri and T. Givargis, "Real-Time Access Guarantees for NAND Flash Using Partial Block Cleaning," in Proceedings of the 6th IFIP WG 10.2 international workshop on Software Technologies for Embedded and Ubiquitous Systems Anacarpi, Capri Island, Italy: Springer-Verlag, 2008.
[6] L. Song-He, Z. Xiang-Mo, Z. Jun, and H. Ya-Nan, "A Static Trigger Wear-Leveling Strategy for Flash Memory In Embedded System," in The Fifth IEEE International Symposium on Embedded Computing, SEC '08 2008, pp. 255-259.
[7] M. Chiang, P. Lee, and R. Chang, "Using Data Clustering to Improve Cleaning Performance for Flash Memory," Software-Practice and Experience, vol. 29, pp. 267-290, 1999.
[8] Y.-H. Chang, J.-W. Hsieh, and T.-W. Kuo, "Endurance Enhancement of Flash-memory Storage Systems: An Efficient Static Wear Leveling Design," in Proceedings of the 44th annual Design Automation Conference San Diego, California: ACM, 2007.
[9] R.-Y. R. Tzeng, "Yet Another Flash Translation Layer ".
[10] M. T. Devices, "NAND Simulator (Nandsim)."
[11] S. Electronic, "128M x 8 Bit / 256M x 8 Bit NAND Flash Memory."
[12] W. Norcott and D. Capps, "Iozone Filesystem Benchmark."