Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-06-01
2004-05-04
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S154000, C711S165000
Reexamination Certificate
active
06732221
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for improving wear leveling of static areas in Flash Memory.
2. Description of the Related Art
Flash memory is non-volatile, able to store recorded data without a power source. Furthermore a computer program using the ability of the Flash memory to be erased and reprogrammed can modify the data stored in Flash memory. These basic capabilities have made Flash arrays suitable for acting as standard storage media in computer systems, i.e. as Flash disks. Several methods have been described in the art of how this can be done, and such methods are in widespread use. Examples of such methods are: U.S. Pat. No. 5,404,485—Flash file system by Amir Ban, incorporated fully herein; and U.S. Pat. No. 5,937,425—Flash file system optimized for page-mode flash technologies by Amir Ban, incorporated fully herein. These two patents describe systems and methods for managing flash file systems, such as coordinating the saving and erasing of data to units. However, these patents do not provide means for wear leveling, as they do not differentiate between frequently and infrequently erased units.
Flash devices are typically divided into several contiguous zones, each of which is individually erasable. Such zones are variously known as units, blocks or sectors in the art, and will be called units, or erase units for clarity, in this disclosure.
A limitation of Flash memory technology is that the number of times a unit can be erased is inherently limited by the physics of the Flash cell. Repeated erasure of a unit wears out the cells in the unit leading to a reduced capability to distinguish between the erased state and the programmed state, resulting in a longer time to erase the unit, appearance of sporadic faults in programming or erasing data, and ultimately the unit may lose entirely the ability to be erased and reprogrammed.
The effects of wear are statistical in nature, and the ability of a Flash device to withstand wear is described by Flash vendors by a number called the program/erase endurance. This number is the minimum or average number of times each Flash unit may be erased without encountering significant failures. Vendor endurance numbers currently range from tens of thousands to a million.
The limited endurance limits the lifetime of a Flash disk. It would be advantageous to have a lifetime that is as long as possible, and this depends on the pattern of access to the Flash disk. Repeated and frequent writes to a single unit, or a small number of units will bring the onset of failures soon and so end the useful lifetime of the media quickly. On the other hand, if writes can be evenly distributed to all units of the media, each unit will experience close to the maximum number of erases it can endure, and so the onset of failures will be delayed as much as possible, maximizing the lifetime of the media.
Flash disk managers take advantage of the fact that their algorithms typically give them discretion over the physical location where new data will be written, and they direct written data in ways designed to guarantee that different Flash units are subjected to the same number of erases. Such a procedure is known in the art as wear leveling. Some managers record the number of erases a unit has experienced in a register in that unit, and enforce a scheme that guarantees that the variation in the number of erases of each unit will not exceed some small constant. Others use a randomization of the choice of the target unit, and depend on statistics and the law of large numbers to maintain an even wear across the Flash media.
An inherent problem for all such wear leveling methods, however, is static areas. Static areas are physical locations on the Flash device that contain data that never or seldom changes. Such data may consist of operating system code or application programs code, which are typically installed once and then never or very seldom change. In many usages of a Flash disk, such data occupies a major part of the Flash media.
Since wear leveling methods exercise their control when choosing a location in which to write new data, they have no influence over the wear experienced by static areas. As these areas are never written to, no choice can be made. While active units of the Flash media may undergo effective wear leveling, the static units, the units of the static areas remain with very low wear. This can significantly reduce the lifetime of the entire Flash media, as for example if static areas span half the media, the effective lifetime is reduced by half.
Furthermore, static areas present various difficulties such as:
1. Identifying static areas, including tracking patterns of usage of the Flash disk by units over long period of time, which is a difficult process requiring control structures and algorithms to support the bookkeeping.
2. Moving the data from a static unit to another location takes time to write the data to its new location and erase the previous location. This represents performance overhead that can degrade the Flash disk throughput if done frequently.
3. Guaranteeing a leveling of wear across the media over time, in spite of the presence of static areas.
Examples of some methods in the art are:
U.S. Pat. No. 5,341,339 by Wells et al., fully incorporated herein by reference, describes a method for wear leveling in a flash EEPROM memory, thus extending significantly the life of a flash memory array. The method of the Wells et al. invention provides for monitoring and subsequently equalizing the switching of different portions of a flash memory array. According to this invention, these and other objects are realized in a process for cleaning up a flash EEPROM memory array separated into blocks which may be separately erased, in which process all valid data on a selected block is first written to other blocks of the array, and then the block is erased, the improvement comprising the step of determining a selected block to clean up based on a comparison of the number of invalid sectors each block includes, and the number of switching operations which each block has undergone. In this way, both maintaining reserve units for recording and maintaining wear leveling are achieved. However, considerable system resources are required to maintain such a system, which includes maintaining an erase count for each unit. In addition, Wells does not really treat static areas. He suggests to give increased weights to the erase count when doing cleanup. In really static areas, there is nothing to clean up, so this is more than setting weights to parameters. Wells omits the crucial step of forcing “cleanup” on units that don't need cleanup, but are static.
U.S. Pat. Nos. 5,388,083, 5,485,595 and 5,479,638, of Assar et al., fully incorporated herein by reference, describe various applications of Flash memory mass storage architecture for wear leveling. According to these patents, an algorithm is provided that prevents any portion of the mass storage from being erased a substantially larger number of times than any other portion. This prevents any one block of the mass storage from failing and becoming unusable earlier than any other block thereby extending the life of the entire mass storage.
Accordingly, a counter tracks the number of times each block is erased. A programmable maximum value for the counter is also provided. As the number of erase cycles for a block becomes one less than the maximum, the block is erased one last time and written with another file having a then smallest number of erase cycles. It is also prevented from being erased thereafter by setting its erase inhibit flag. After all blocks approach this maximum, all the erase counters and inhibit flags are cleared and the second algorithm is then repeated. In this way, no block can be erased a substantial number of times more than any other block. However, like the Wells et al. invention, this invention requires considerable system resources in order to maintain the elaborate monitoring and permissions structu
Elmore Stephen
Friedman Mark M.
Kim Matthew
M-Systems Flash Disk Pioneers LTD
LandOfFree
Wear leveling of static areas in flash memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Wear leveling of static areas in flash memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wear leveling of static areas in flash memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3194906