Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-09-28
2004-03-30
Moazzami, Nasser (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C365S185110
Reexamination Certificate
active
06715027
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a cleaning policy and a method for recovering error in file systems; and, more particularly, to a ranked cleaning policy and an error recovery method in a file system using flash memory which can be used effectively and longer by dividing it into segments, adopting ranked cleaning policy and arranging its cleaned space evenly, and also the file system using the flash memory which can recover error quickly when sudden power error is caused by subdividing the erasing status, as well as a computer-based recording medium for recording a program to embody the methods above.
DESCRIPTION OF THE PRIOR ART
The present invention concerns operating file systems using flash memories as media of recording and processing data in embedded systems such as information appliances, communication devices, set-top boxes, internet phones and the like.
The embedded systems mentioned above should keep data when power is turned off. Even in sudden power-off, they should secure data consistency. Therefore, flash memories with non-volatile property are mostly used in the embedded systems.
As information industry develops, embedded systems being developed lately refuse to stay as just simple electric devices and develop up to processing systems with a CPU inside. And more and more functions are required for these systems, making their structures more complex. This called for the real-time operating system (RTOS) to achieve the functions and to control and operate the devices, which are getting complex more and more, along with the need for file systems to run them.
To effectively manage the flash memory in embedded systems, the present invention on a file system using flash memory has been developed as well as a new cleaning policy and error recovery method.
Flash memories are stronger than other storage media, non-volatile, with fast access time, working with low electric power and small, which make them suitable for portable appliances. Flash memories have properties in common with EEPROM (Electrically Erasable Programmable ROM). That is, data in a flash memory can be deleted with electric signal and is reusable by programming or storing data therein again.
However, there are three problems using flash memory as a storage medium.
In the first place, once data are stored other data cannot be recorded therein until being cleaned. Secondly, taking 0.5-1 second to clean, it takes quite long time to delete data compared with reading time, 80 ~150 nsec/byte, and storing time, about 10 &mgr;sec/byte. Thirdly, the number of times cleaning the flash memory is limited to about 100,000 times at normal temperature.
So, to address the above problems, the number of times a flash memory is cleaned should be lessen as much as possible and the cleaning should be conducted on the memory space as evenly as possible while being cleaned. The space to be cleaned at a time is predetermined and fixed to be 64 Kbytes mostly. The space that can be cleaned at a time is called a segment.
Among prior arts for solving the problem mentioned above are the U.S. Pat. No. 5,404,485 titled Flash File System and a paper under the tile of A Flash Memory Based File System published in the USEINX, pp 155 ~164, in 1995.
The patent of Flash File System concerns a flash file system for using flash memory as a form of a disk and describes the structure for storing data in the flash memory and a method for reading and controlling data stored therein. The patent calls the erase sector an erase unit (EU), and the EU is composed of a header, block allocation map (BAM) and data block region.
The paper A Flash Memory Based File System describes a structure composing a file system with a flash memory and cleaning policy.
The file system structure of the above dissertation names the memory space to be cleaned at a time a segment, and the segment consists of segment summery and data storage space. The memory storage space is divided into data blocks, which is generally 512 Kbytes, to store data on a block basis. Data blocks are called free blocks when the segment is cleaned, valid blocks when there are useful data, and invalid blocks when the data is not useful any more thus becoming blocks that should be cleaned.
In the cleaning policy of the above prior art, Greedy method and Cost-benefit method are described. Greedy method selects a segment with least useful data block and cleans it prior to other segments, while Cost-benefit selects the segment to clean according to the formula shown below.
benefit
cost
=
age
×
(
1
-
u
)
2
u
[
Formula
1
]
wherein u indicates the utilization coefficient of a segment, that is, the ratio of valid blocks in the segment, and
2
u
being the sum total of reading time and writing time that occur by transferring valid blocks in a segment to be cleaned to another segment, while age is the time that has passed since the block is converted into invalid block.
The conventional technologies do not effectively address the shortcomings of limited number of times in cleaning a flash memory the cleaning time taken longer than reading or writing time. Also, in case of sudden power error while moving useful data from one block to another or conducting while cleaning, there was no way to recover the data or even if there is, other problems may occur performing it.
The conventional cleaning procedures comprise the steps of searching free blocks in a destination segment that valid blocks in the segment to be cleaned will move into; copying the valid blocks in the segment to be cleaned into the free blocks found in the preceding step; converting the destination blocks into valid blocks; converting the source blocks into invalid ones; and cleaning the segment with the invalid blocks and converting it into a free segment.
However, in case power error occurs in the second step there is no way to know whether copying has begun or the data are copied to the destination blocks because the destination blocks are in free status; when error has occurred in the midst of the copying procedure and then when you try to store data in this block again, error occurs because the destination block still remains in free status; and if power error is caused in the third step, the destination block where data are copied is converted to valid block and the source block still remains valid as well, so there is a problem that we do not know which one is normal data block.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide ranked cleaning policy and a method for error recovery as well as a computer-based recording medium in file systems using a flash memory, which are capable of using the flash memory effectively and extending its life by segmenting the flash memory space, employing ranked cleaning policy and arranging spaces to clean evenly, and also capable of recovering error quickly caused by sudden power-off.
In accordance with an embodiment of the present invention, there is provided a method for ranked cleaning policy in file systems using flash memory, the method comprising the steps of: a) calculating rank values for all segments of the flash memory periodically; and b) if the storable space of the flash memory becomes less than a predetermined volume, a cleaner operating to clean invalid space of segments in order of their rank values obtained in the previous step high to low and thus to secure new storage space.
In accordance with an embodiment of the present invention, there is provided a method for power error recovery in file systems using flash memory, the method comprising the steps of: a) examining the block status for a segment of the flash memory and determining the type of blocks in instable status; b) if the results of the step a) shows the block of the segment is in allocated status, converting the status to the invalid status; c) if the results of the step a) shows the block of the segment is in prevalid status, converting the status to the valid status, and finding the source block for that block and if the source bloc
Kim Jeong-ki
Park Seung-Min
Blakely & Sokoloff, Taylor & Zafman
Electronics and Telecommunications Research Institute
Moazzami Nasser
LandOfFree
Ranked cleaning policy and error recovery method for file... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ranked cleaning policy and error recovery method for file..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ranked cleaning policy and error recovery method for file... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3283375