Real-time garbage collection for flash-memory storage systems of real-time embedded systems

ABSTRACT

Flash-memory technology is becoming critical in building embedded systems applications because of its shock-resistant, power economic, and nonvolatile nature. With the recent technology breakthroughs in both capacity and reliability, flash-memory storage systems are now very popular in many types of embedded systems. However, because flash memory is a write-once and bulk-erase medium, we need a translation layer and a garbage-collection mechanism to provide applications a transparent storage service. In the past work, various techniques were introduced to improve the garbage-collection mechanism. These techniques aimed at both performance and endurance issues, but they all failed in providing applications a guaranteed performance. In this paper, we propose a real-time garbage-collection mechanism, which provides a guaranteed performance, for hard real-time systems. On the other hand, the proposed mechanism supports non-real-time tasks so that the potential bandwidth of the storage system can be fully utilized. A wear-leveling method, which is executed as a non-real-time service, is presented to resolve the endurance problem of flash memory. The capability of the proposed mechanism is demonstrated by a series of experiments over our system prototype.

REFERENCES

• 1: Baker, T. P. 1990. A stack-based resource allocation policy for real-time process. In Proceedings of the 11th IEEE Real-Time System Symposium.
• 2: Li-Pin Chang , 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 (RTAS'02), p.187, September 25-27, 2002
• 3: Li-Pin Chang , Tei-Wei Kuo, An efficient management scheme for large-scale flash-memory storage systems, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968076]
• 4: Chang, L. P., Kuo, T. W., and Lo, S. W. 2001. A dynamic-voltage-adjustment mechanism in reducing the power comsumption in flash memory storage systems for portable devices. In Proceedings of the IEEE International Conference on Consumer Electronics.
• 5: Chiang, M. L., Paul, C. H., and Chang, R. C. 1997. Manage flash memory in personal communicate devices. In Proceedings of IEEE International Symposium on Consumer Electronics.
• 6: Douglis, F., Caceres, R., Kaashoek, F., Li, K., Marsh, B., and Tauber, J. 1994. Storage alternatives for mobile computers. In Proceedings of the USENIX Operating System Design and Implementation.
• 7: Journaling Flash File System (JFFS). http://sources.redhat.com/jffs2/jffs2-html/.
• 8: K9f2808u0b 16mb*8 NAND Flash Memory Data Sheet. Samsung Electronics Company.
• 9: Kawaguchi, A., Nishioka, S., and Motoda, H. 1995. A flash memory based file system. In Proceedings of the USENIX Technical Conference.
• 10: Han-joon Kim , Sang-goo Lee, A New Flash Memory Management for Flash Storage System, 23rd International Computer Software and Applications Conference, p.284, October 19-26, 1999
• 11: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 12: Malik, V. 2001a. JFFS---A Practical Guide. Available at http://www.embeddedlinuxworks.com/ articles/jffs_guide.html.
• 13: Malik, V. 2001b. JFFS2 is broken. In Mailing List of Memory Technology Device (MTD) Subsystem for Linux.
• 14: Molano, A., Rajkumar, R., and Juvva, K. 1998. Dynamic disk bandwidth management and metadata pre-fetching in a real-time filesystem. In Proceedings of the 10th Euromicro Workshop on Real-Time Systems.
• 15: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.26-52, Feb. 1992 [doi>10.1145/146941.146943]
• 16: Chin-Hsien Wu , Li-Pin Chang , Tei-Wei Kuo, An efficient R-tree implementation over flash-memory storage systems, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.17-24, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956679]
• 17: Michael Wu , 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, p.86-97, October 05-07, 1994, San Jose, California, United States
• 18: Yet Another Flash-Filing System (YAFFS). Aleph One Company.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
      D.4.7 Organization and Design

General Terms:
Algorithms, Design

Keywords:
Embedded systems, flash memory, garbage collection, real-time system, storage systems