Eran Gal
Skip Abstract Section
Abstract
Flash memory is a type of electrically-erasable programmable read-only memory (EEPROM). Because flash memories are nonvolatile and relatively dense, they are now used to store files and other persistent objects in handheld computers, mobile phones, digital cameras, portable music players, and many other computer systems in which magnetic disks are inappropriate. Flash, like earlier EEPROM devices, suffers from two limitations. First, bits can only be cleared by erasing a large block of memory. Second, each block can only sustain a limited number of erasures, after which it can no longer reliably store data. Due to these limitations, sophisticated data structures and algorithms are required to effectively use flash memories. These algorithms and data structures support efficient not-in-place updates of data, reduce the number of erasures, and level the wear of the blocks in the device. This survey presents these algorithms and data structures, many of which have only been described in patents until now.
- Aleph One. 2002. YAFFS: Yet another flash filing system. Cambridge, UK. Available at http://www.aleph1.co.uk/yaffs/index.html.]]Google Scholar
- Assar, M., Nemazie, S., and Estakhri, P. 1995a. Flash memory mass storage architecture. US patent 5,388,083. Filed March 26, 1993; Issued February 7, 1995; Assigned to Cirrus Logic.]]Google Scholar
- Assar, M., Nemazie, S., and Estakhri, P. 1995b. Flash memory mass storage architecture incorporation wear leveling technique. US patent 5,479,638. Filed March 26, 1993; Issued December 26, 1995; Assigned to Cirrus Logic.]]Google Scholar
- Assar, M., Nemazie, S., and Estakhri, P. 1996. Flash memory mass storage architecture incorporation wear leveling technique without using CAM cells. US patent 5,485,595. Filed October 4, 1993; Issued January 16, 1996; Assigned to Cirrus Logic.]]Google Scholar
- Axis Communications. 2004. JFFS home page. Lund, Sweden. Available at http://developer.axis.com/software/jffs/.]]Google Scholar
- Ban, A. 1995. Flash file system. US patent 5,404,485. Filed March 8, 1993; Issued April 4, 1995; Assigned to M-Systems.]]Google Scholar
- Ban, A. 1999. Flash file system optimized for page-mode flash technologies. US patent 5,937,425. Filed October 16, 1997; Issued August 10, 1999; Assigned to M-Systems.]]Google Scholar
- Ban, A. 2004. Wear leveling of static areas in flash memory. US patent 6,732,221. Filed June 1, 2001; Issued May 4, 2004; Assigned to M-Systems.]]Google Scholar
- Barrett, P. L., Quinn, S. D., and Lipe, R. A. 1995. System for updating data stored on a flash-erasable, programmable, read-only memory (FEPROM) based upon predetermined bit value of indicating pointers. US patent 5,392,427. Filed May 18, 1993; Issued February 21, 1995; Assigned to Microsoft.]]Google Scholar
- Chang, L.-P., Kuo, T.-W., and Lo, S.-W. 2004. Real-time garbage collection for flash-memory storage systems of real-time embedded systems. ACM Trans. Embed. Comput. Syst. 3, 4, 837--863.]] Google Scholar
- Chiang, M.-L. and Chang, R.-C. 1999. Cleaning policies in mobile computers using flash memory. J. Syst. Softw. 48, 3, 213--231.]] Google Scholar
- Chiang, M.-L., Lee, P. C., and Chang, R.-C. 1999. Using data clustering to improve cleaning performance for flash memory. Softw. Pract. Exp. 29, 3, 267--290.]] Google Scholar
- Daberko, N. 1998. Operating system including improved file management for use in devices utilizing flash memory as main memory. US patent 5,787,445. Filed March 7, 1996; Issued July 28, 1998; Assigned to Norris Communications.]]Google Scholar
- Dan, R. and Williams, J. 1997. A TrueFFS and FLite technical overview of M-Systems' flash file systems. Tech. rep. 80-SR-002-00-6L Rev. 1.30, M-Systems.]]Google Scholar
- Douglis, F., Caceres, R., Kaashoek, M. F., Li, K., Marsh, B., and Tauber, J. A. 1994. Storage alternatives for mobile computers. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI). Monterey, CA. 25--37.]] Google Scholar
- Han, S.-W. 2000. Flash memory wear leveling system and method. US patent 6,016,275. Filed November 4, 1998; Issued January 18, 2000; Assigned to LG Semiconductors.]]Google Scholar
- Intel Corporation. 1998a. Flash file system selection guide. Application Note 686, Intel Corporation.]]Google Scholar
- Intel Corporation. 1998b. Understanding the flash translation layer (FTL) specification. Application Note 648, Intel Corporation.]]Google Scholar
- Jou, E. and Jeppesen III, J. H. 1996. Flash memory wear leveling system providing immediate direct access to microprocessor. US patent 5,568,423. Filed April 14, 1995; Issued October 22, 1996; Assigned to Unisys.]]Google Scholar
- Kawaguchi, A., Nishioka, S., and Motoda, H. 1995. A flash-memory based file system. In Proceedings of the USENIX Technical Conference. New Orleans, LA. 155--164.]] Google Scholar
- Kim, H.-J. and Lee, S.-G. 2002. An effective flash memory manager for reliable flash memory space management. IEICE Trans. Inform. Syst. E85-D, 6, 950--964.]]Google Scholar
- Krueger, W. J. and Rajagopalan, S. 1999a. Method and system for file system management using a flash-erasable, programmable, read-only memory. US patent 5,634,050. Filed June 7, 1995; Issued May 27, 1999; Assigned to Microsoft.]]Google Scholar
- Krueger, W. J. and Rajagopalan, S. 1999b. Method and system for file system management using a flash-erasable, programmable, read-only memory. US patent 5,898,868. Filed 7 June 1995; Issued April 27, 1999; Assigned to Microsoft.]]Google Scholar
- Krueger, W. J. and Rajagopalan, S. 2001. Method and system for file system management using a flash-erasable, programmable, read-only memory. US patent 6,256,642. Filed 29 January, 1992; Issued July 3, 2001; Assigned to Microsoft.]]Google Scholar
- Lofgren, K. M., Norman, R. D., Thelin, Gregory, B., and Gupta, A. 2003. Wear leveling techniques for flash EEPROM systems. US patent 6,594,183. Filed June 30, 1998; Issued July, 15, 2003; Assigned to Sandisk and Western Digital.]]Google Scholar
- Lofgren, K. M. J., Norman, R. D., Thelin, G. B., and Gupta, A. 2000. Wear leveling techniques for flash EEPROM systems. US patent 6,081,447. Filed March 25, 1999; Issued June 27, 2000; Assigned to Western Digital and Sandisk.]]Google Scholar
- Marshall, J. M. and Manning, C. D. H. 1998. Flash file management system. US patent 5,832,493. Filed April 24, 1997; Issued November 3, 1998; Assigned to Trimble Navigation.]]Google Scholar
- Parker, K. W. 2003. Portable electronic device having a log-structured file system in flash memory. US patent 6,535,949. Filed April 19, 1999; Issued March 18, 2003; Assigned to Research In Motion.]]Google Scholar
- Rosenblum, M. and Ousterhout, J. K. 1992. The design and implementation of a log-structured file system. ACM Trans. Comput. Syst. 10, 1, 26--52.]] Google Scholar
- Seltzer, M. I., Bostic, K., McKusick, M. K., and Staelin, C. 1993. An implementation of a log-structured file system for UNIX. In USENIX Winter Conference Proceedings. San Diego, CA. 307--326.]] Google Scholar
- Smith, K. B. and Garvin, P. K. 1999. Method and apparatus for allocating storage in flash memory. US patent 5,860,082. Filed March 28, 1996; Issued January 12, 1999; Assigned to Datalight.]]Google Scholar
- Torelli, P. 1995. The Microsoft flash file system. Dr. Dobb's Journal 20, 62--72.]]Google Scholar
- Wells, S., Hasbun, R. N., and Robinson, K. 1998. Sector-based storage device emulator having variable-sized sector. US patent 5,822,781. Filed October 30, 1992; Issued October 13, 1998; Assigned to Intel.]]Google Scholar
- Wells, S. E. 1994. Method for wear leveling in a flash EEPROM memory. US patent 5,341,339. Filed November 1, 1993; Issued August 23, 1994; Assigned to Intel.]]Google Scholar
- Woodhouse, D. 2001. JFFS: The journaling flash file system. Ottawa Linux Symposium (July). Available at http://sources.redhat.com/jffs2/jffs2.pdf.]]Google Scholar
- Wu, C.-H., Chang, L.-P., and Kuo, T.-W. 2003a. An efficient B-tree layer for flash-memory storage systems. In Proceedings of the 9th International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA). Tainan City,Taiwan. Lecture Notes in Computer Science, vol. 2968. Springer, 409-- 430.]]Google Scholar
- Wu, C.-H., Chang, L.-P., and Kuo, T.-W. 2003b. An efficient R-tree implementation over flash-memory storage systems. In Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems. New Orleans, LA. 17--24.]] Google Scholar
- Wu, M. and Zwaenepoel, W. 1994. eNVy: A non-volatile, main memory storage system. In Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. San Jose, CA. 86--97.]] Google Scholar
Recommendations
External memory algorithms and data structures: dealing with massive data
Data sets in large applications are often too massive to fit completely inside the computers internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major ...
The design and implementation of a log-structured file system
This paper presents a new technique for disk storage management called a log-structured file system. A log-structured file system writes all modifications to disk sequentially in a log-like structure, thereby speeding up both file writing and crash ...
Comments