A summary of previously proposed victim block selection algorithm.
1. Introduction
Flash memory is a non-volatile storage device that can retain its contents when the power is switched off. Generally, it is a form of an electrically erasable programmable read-only memory (EEPROM) that offers several excellent features such as less noise, solid-state reliability, lower power consumption, smaller size, light weight, and higher shock resistant [1 – 5]. Flash memory acts as a slim and compact storage device. It’s main applications are such as compact flash (CF), secured digital (SD), and personal computer memory card international association (PCMCIA) cards, for storage and data transfer in most portable electronic gadgets such as mobile phones, digital cameras, personal digital assistants (PDAs), portable media players (PMPs), gobal positioning system receivers (GPS), just to name a few.
The demand for flash memory has reformed its usage to wide areas. For instance, as illustrated in Figure 1, flash memory is extensively used as embedded systems in several intelligent and novelty applications such as household appliances, telecommunication devices, computer applications, automotives and high technology machinery.
2. Flash memory architecture
As shown in Figure 2, flash memory is a block and page based storage device. The page unit is used to store data where a group of pages is referred to as a block. The page unit is partitioned into two areas, namely, 1)
There are two different types of flash memory in the current market, namely, 1)
(block and page) to be addressed as a set of different accessing units (such as 512 B, 2 KB, 4 KB, depending on the manufacturers). In the native file system, the device accessing unit can directly be accessed without the translation layer. An example of the native file system employed in NAND-flash is the journaling flash file system (JFFS) [7] and yet another flash filing system (YAFFS) [23]. For application purposes, the NOR-flash is used for small amounts of code storage while the NAND-flash is mostly used in data storage applications since its characteristic are more similar to disk storage.
3. Flash memory characteristics
The characteristics of the flash memory can be summarized as follows [8, 9]:
Free accessing time penalties: The flash memory is a semiconductor device which eliminates the use of mechanical components. This allows the time required to access data to be uniform, regardless of the data’s location. For instance, let’s say both data
Data accessing (retrieving and storing) in flash memory is carried out in three phases, 1)
Out-place updating scheme: Data updating in the flash memory is performed via an out-place scheme rather than an in-place scheme. Due to its EEPROM characteristic, if the in-place scheme is employed, the block where the updated data is located needs to be erased first before the data can be restored into the similar location. Furthermore, block erasure in flash memory is time consuming that can degrade I/O performance. Thus, the out-place scheme is employed where the updated data is stored into a new location while its original copy is set as garbage and will not be used any further [10 – 11] (see Figure 5). The main purpose of the out-place scheme is to avoid block erasure during every update process.
Due to the out-place scheme, the page in flash memory falls into three states, namely, 1)
Asymmetric accessing time and unit: There are three types of access functions in flash memory. They are 1)
Bulk cleaning with limited block life cycle: The cleaning process is essential in flash memory due to the employed out-place updating scheme. The cleaning process is carried out on block unit rather than page unit. The block may contain valid data, thus, before initiating the process, all valid data residing in the block must be copied out into available free spaces in other free blocks. However, each block could be tolerant with a limited number of erasure cycles, for example one million (106) cycles. Exceeding the erasure cycles will cause the block to become unreliable and spoiled, permanently. For example, a multi-level cell (MLC) block type typically supports 10,000 erasure cycles. If the same block is erased and then re-programmed every second, the block would exceed the 10,000 cycle limit in just three hours. Thus, wear-leveling policy that wears down all memory blocks as evenly as possible is necessary [14, 15].
4. Cleaning process in flash memory
The cleaning process in flash memory refers to the process of collecting the garbage scattered throughout the memory array and then reclaiming them back into free space due to the out-place updating scheme. It is an essential process to guarantee free space availability on the memory array to ensure new data can be continually stored. However, the cleaning process is carried out by the erase function and involves bulk size of data rather than specific locations. The valid data in the block must be copied into the other blocks (free cells) first, before the cleaning can be initiated. Besides, each flash memory block could tolerate with an individual erasure lifetime. Frequently erasing blocks causes the blocks to become unreliable and thus, reduces physical device capacity.
The effectiveness of the cleaning process is heavily dependent on the efficient cleaning algorithm as well as the data allocation scheme employed by the flash memory system. Moreover, the cleaning process and the block utilization level are key to the cleaning process performance and have substantial impact on the access performance, energy consumption and block endurance [1, 10, 14]. Block utilization is the ratio between valid cells and total cells and it is represented in percentage. Two categories of cleaning processes in flash memory are 1)
4.1. Automatic cleaning
The automatic cleaning process is automatically commenced when a particular block’s state in the memory array turns from an active to an inactive (all pages in the block have turned into invalid state or mixing with several number of free pages). Since there is no valid data copying process required, the block can be erased in the background during execution of the current I/O operations (such as read or write) from/into the memory array. Accordingly, this process requires a constant erase accessing time (
For example, let’s say file
turns into an inactive state and can be erased automatically. Then, block
4.2. Semi-automatic cleaning
Semi-automatic cleaning is commenced when the memory array free spaces reach a certain threshold, for instance, when the available free space is fewer than 20% – 35% of the total memory space. Two primary goals of the semi-automatic cleaning process are: 1)
In Equation 1., the write function is assumed to be 10 times slower than the read function while the erase function is 75 times slower than the read function. Figure 7 presents the cleaning cost required for cleaning a single victim block in the memory array. To illustrate this, assume a block containing 64 pages, and the block utilization level is between 0 and 100 %. The actual time for read, write and erase access functions were taken from Figure 3.
As illustrated in Figure 8, the semi-automatic cleaning is undertaken in three stages. First, a victim block (
The execution time issue refers to the time to initiate the cleaning process, either periodically or according to memory free space availability. The victim block selection procedure refers to the method used to select the block to be erased and the straight forward approach is selecting a victim block that contains the largest amount of garbage. Other parameters include cost to erase, block lifespan, erasure count, and age of data [1, 10, 21, 22]. Again, the victim block amount issue in the semi-automatic cleaning enables single or multiple victim blocks to be erased simultaneously. On the other hand, both approaches have their own pros and cons. Cleaning a single block requires smaller access time but it also requires many erase operations. In contrast, erasing multiple blocks can distract the execution of normal I/O operational system execution [18], but multiple victim blocks cleaning helps in reorganizing many valid data and can also help in reducing the number of blocks to be further erased. Then, the valid data re-organization issue refers to the process of copying the valid data in the victim block into a new free location in the available active blocks. The common approach is the valid data clustering technique, where valid data will be grouped into the similar block according to the data feature (such as regularly modified, irregularly modified, data time-stamp, and related data file). Thus, in order to improve the semi-automatic cleaning process performance, a number of studies that focuses on determining victim blocks have been proposed. The accompanying table shows the summary of the studies. In addition, the cleaning cost in the semi-automatic process depends on two important parameters, namely, 1)
Cleaning scheme | Victim block selection procedure/equation | Wear-leveling |
Greedy (GR) [19] | No | |
Cost-benefit (CB) [20] | Block with maximum value from equation | No |
Cost age time (CAT) & Dynamic dAta clustering (DAC) [21] | Block with minimum value from equation | Yes |
Cost Age Time with Age Sort (CATA) [18] | Blocks those maximize equation | Yes |
S-Greedy (S-GR) [22] | Based on GR algorithm and focus on valid data distribution | Yes |
5. Summary
Flash memory offers several superior features as a secondary storage and has recently been employed in many consumer electronic gadgets. However, due to the hardware operational characteristics, especially the out-place updating scheme, several challenges have emerged in terms of data management in designing and implementing an efficient data storage system. There are existing issues that influence flash memory performance, which are related to the cleaning process in order to allow data storage continuity. Both the automatic and the semi-automatic cleaning processes are two important issues in guaranteeing cleaning process performance in the flash memory. The automatic cleaning is directly related with the efficient data allocation schemes where the cleaning can be initiated without having to disturb the current operations in the flash memory. Although only single inactive blocks can be cleaned every time the process is initiated, when the amount of active-to-inactive state conversion increases, the cleaning performance of the flash memory is guaranteed since the inactive block can be erased automatically without having to disturb current I/O operations. Conversely, the semi-automatic cleaning process is initiated according to a memory array free space threshold or it can be initiated periodically. There are several parameters employed in establishing the victim block to be erased such as cleaning cost, erasure count, age of data, block utilization, etc. Although the cleaning can be initiated on multiple victim blocks, the process can impose a blocking time that would distract the normal I/O operation execution on the memory. On the other hand, the efficiency of re-organizing the valid data in the victim blocks could influence the cleaning process performance further. The well-organized valid data in the new active block will group the regular and irregular accessed data into different blocks and could further increase the amount of inactive blocks. The increase of inactive blocks in the memory array would increase the automatic cleaning process and guarantee flash memory performance. Thus, both cleaning processes are important in order to improve the cleaning process performance in flash memory as well as its endurance.
References
- 1.
Douglis F. Kaashoek F. Marsh B. Caceres R. Li K. Tauber J. 1994 Storage alternatives for mobile computers. In: Proceedings of the 1st USENIX Conference on Operating Systems Design and Implementation (OSDI’94), Nov. 14-17, Monterey, California: ACM/IEEE.25 37 - 2.
Chang L. P. Kuo T. W. 2004 An efficient management scheme for large-scale flash memory storage systems. In: Proceedings of the 2004 ACM Symposium of Applied Computing (SAC’04), March 14-17, Nicosia, Cyprus: ACM.862 868 - 3.
Lawton G. 2006 Improved flash memory grows in popularity. IEEE Computer, 39(1),16 18 - 4.
Lim S. H. Park K. H. 2006 An efficient NAND flash file system for flash memory storage. IEEE Transactions on Computers, 55(7),906 912 - 5.
Breeuwsma M. Jongh M.d. Klaver C. Knijff R.v.d. Roeloffs M. 2007 Forensic data recovery from flash memory. Small Scale Digital Device Forensic Journal, 1(1),1 17 - 6.
Hsieh J. W. Tsai Y. L. Kuo T. W. Lee T. L. 2008 Configurable flash-memory management: Performance versus overheads. IEEE Transactions on Computer, 57(11),1571 1583 - 7.
Woodhouse D. 2001 JFFS: The journaling flash file system. In: Proceedings of the 2001 Ottawa Linux Symposium, July13 16 Ottawa, Canada. - 8.
Barre A. G. 1993 Flash memory magnetic disk replacement? IEEE Transactions on Magnetics, 29(6),4104 4107 - 9.
Sharma A. K. 2003 Advanced semiconductor memories: Architecture, designs, and applications. Canada: WILEY-IEEE Press.4 - 10.
Kawaguchi A. Nishioka S. Motada H. 1995 Flash memory based file system. In: Proceedings of USENIX 95 Technical Conference, Jan. 16-20, New Orleans, Louisiana: USENIX.155 164 - 11.
Wu M. Zwanepoel W. 1994 eNVy: a non-volatile, main memory storage system. In: Proceedings of the 6th International Conference on Architectural Support for Programming language and Operating Systems (ASPLOS), Oct. 5-7, San Jose, California: ACM.86 97 - 12.
Chou L. F. Liu P. 2005 Efficient allocation algorithms for flash file systems. In: Proceedings of 11th International Conference on Parallel and Distribution Systems (ICPADS’05), July 20-22, Fukuoka, Japan: IEEE.634 641 - 13.
Liu P. Chuang C. H. Wu J. J. 2007 Block-based allocation algorithms for flash memory in embedded systems. In: Proceedings of 9th International Conference on Parallel Computing Technologies (PaCT 2007), Sept. 3-7, Pereslavl-Zalessky, Russia: Springer.569 578 - 14.
Kim H. Lee S. G. 2002 An effective flash memory manager for reliable flash memory space management. IEICE Trans. Information and System, E85-D(6),950 964 - 15.
Chang Y. H. Hsieh J. W. Kuo T. W. 2007 Endurance enhancement of flash-memory storage systems: An efficient static wear leveling design. In: Proceedings of 44th ACM/IEEE Design Automation Conference (DAC 2007), June 4-8, San Diego, California: ACM.212 217 - 16.
Rahiman A. R. Sumari P. 2009 Probability based page data allocation scheme in flash memory. In: Proceedings of IEEE Pacific-Rim Conference on Multimedia (PCM 2009), Dec. 15-18, Bangkok, Thailand: IEEE.300 310 - 17.
Ko S. Jun S. Kim K. Ryu Y. 2008 Study on garbage collection schemes for flash based Linux swap system. In: International Conference on Advanced Software Engineering & Its Applications (ASEA 2008), Dec. 13-15, Hainan Island, China: IEEE.13 16 - 18.
Han L. Z. Rhu Y. Chung T. S. Lee M. Hong S. 2006 An intelligent garbage collection algorithm for flash memory storages. In: Proceedings of International Conference on Computational Science and Its Applications (ICCSA 2006), May 8-11, Glasgow, UK: Springer.1019 1027 - 19.
Rosenblum M. Ousterhout J. K. 1992 The design and implementation of a log-structured file system. ACM Transactions on Computer Systems, 10(1),26 52 - 20.
Kawaguchi A. Nishioka S. Motada H. 1995 Flash memory based file system. In: Proceedings of USENIX 95 Technical Conference, Jan. 16-20, New Orleans, Louisiana: USENIX.155 164 - 21.
Chiang M. L. Lee P. C. H. Chang R. C. 1999 Cleaning policies in mobile computers using flash memory. Journal of Systems and Software, 48(3),213 231 - 22.
Kwon O. Ryu Y. Koh K. 2007 An efficient garbage collection policy for flash memory based swap systems. In: Proceedings of International Conference on Computer Science and Applications (ICCSA 2007), Oct. 24-26, San Francisco, USA: IAENG.213 223 - 23.
Yaffs 2006 How does YAFFS work? [Online], [Accessed 30th July, 2010] - 24.
Kang J. U. Kim J. S. Park C. Park H. Lee J. 2007 A multi-channel architecture for high-performance NAND flash-based storage system. Journal of Systems Architecture, 53(9),644 658