Ranked cleaning policy and error recovery method for file systems using flash memory

• US 6,715,027 B2
• Filed: 09/28/2001
• Issued: 03/30/2004
• Est. Priority Date: 12/27/2000
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Park, Seung-Min, Kim, Jeong-ki
• Primary Examiner(s): MOAZZAMI, NASSER G
• Application Number:
  US09/967,585
• Publication Number:
  US 20020116569A1
• Time in Patent Office: 914 Days
• Field of Search: 711/103, 711/202, 711/171, 714/7, 365/185.11
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory

Abstract

The present invention relates to a cleaning policy and a method for recovering error in a file system using flash memory; and, more particularly, to a ranked cleaning policy in a file system using flash memory which can be used effectively and longer by dividing it into segments, adopting the ranked cleaning policy and arranging cleaned spaces evenly, and to an error recovery method in a file system using flash memory which can recover error by subdividing cleaning status when sudden power error is caused, as well as to a computer-based recording medium for recording a program to embody the methods above. A method for ranked cleaning policy in file systems using flash memory, the method comprising the steps of: calculating rank values for all segments of the flash memory periodically; and 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.

Claims

1. A method for ranked cleaning using a flash memory used in a file system, 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,

wherein the rank values are calculated by an equation expressed as;

$R=A<br><br>\frac{\mathrm{age}·<br><br>i}{2<br><br>v·<br><br>f}$

where v is the ratio of valid blocks to the entire segment, f is the ratio of free blocks in a segment, i is the ratio of invalid blocks, age is the time that has passed since the segment is cleaned, and A is the weight.

2. The method of claim 1, wherein

the flash memory of the step a) is divided into a predetermined number of segments, a segment being the space that can be cleaned at a time;

the segment is divided into read/write blocks; and

the read/write block includes a segment header, BMT (Block Mapping Table) and data blocks.

3. The method as recited in claim 1, wherein in the step b) includes the steps of:

c) the cleaner examining the number of free segments in the flash memory N_fs, and checking whether the examined number of free segments is less than the predetermined number of segments;

d) if the number of free segment is more than the predetermined number of segments, the cleaner stopping operation as there is sufficient space;

e) if the number of free segment is less than the predetermined number of segments, the cleaner examining if there are segments with invalid blocks to be cleaned;

f) if there are segments with invalid blocks, securing new space for storage by cleaning segments with invalid blocks with biggest rank value calculated in step a); and

g) if there is no segment with invalid blocks, checking if the flash memory is full, and in case it'"'"'s full, notifying it to the user and in case it'"'"'s not full, the cleaner stopping operation because the remaining flash memory space can be used.

4. The method of claim 3, wherein, in the step f) of cleaning segments with invalid blocks, the oldest segment with sufficient space to accommodate the valid blocks of a segment to be erased is selected and the valid blocks are copied to the selected segment and the segment targeted for cleaning is erased.

5. The method of claim 4, wherein the procedure of cleaning the segment to be erased includes the steps of:

h) looking for the destination block where the valid blocks of the source segment to be erased will be moved, and converting it to the allocated status;

i) after the original data are copied to the destination block which has been converted to the allocated status in the step h), the destination block being converted to the prevalid status with the source block no longer in need converted to invalid status, then making the destination block converted to valid status; and

j) conducting the cleaning procedure to the target segment of deletion, the source segment and converting it to a free segment.

6. The method of claims 2, wherein in the step b) includes the steps of:

c) the cleaner examining the number of free segments in the flash memory N_fs, and checking whether the examined number of free segments is less than the predetermined number of segments;

d) if the number of free segment is more than the predetermined number of segments, the cleaner stopping operation as there is sufficient space;

e) if the number of free segment is less than the predetermined number of segments, the cleaner examining if there are segments with invalid blocks to be cleaned;

f) if there are segments with invalid blocks, securing new space for storage by cleaning segments with invalid blocks with biggest rank value calculated in the step a); and

g) if there is no segment with invalid blocks, checking if the flash memory is full, and in case it'"'"'s full, notifying it to the user and in case it'"'"'s not full, the cleaner stopping operation because the remaining flash memory space can be used.

7. The method of claim 6, wherein, in the step f) of cleaning segments with invalid blocks, the oldest segment with sufficient space to accommodate the valid blocks of a segment to be erased is selected and the valid blocks are copied to the selected segment and the segment targeted for cleaning is erased.

8. The method of claim 7, wherein the procedure of cleaning the segment to be erased includes the steps of:

h) looking for the destination block where the valid blocks of the source segment to be erased will be moved, and converting it to the allocated status;

i) after the original data are copied to the destination block which has been converted to the allocated status in the step h), the destination block being converted to the prevalid status with the source block no longer in need converted to invalid status, then making the destination block converted to valid status; and

j) conducting the cleaning procedure to the target segment of deletion, the source segment and converting it to a free segment.

9. The method of claims 1 wherein in the step b) includes the steps of:

c) the cleaner examining the number of free segments in the flash memory N_fs, and checking whether the examined number of free segments is less than the predetermined number of segments;

d) if the number of free segment is more than the predetermined number of segments, the cleaner stopping operation as there is sufficient space;

e) if the number of free segment is less than the predetermined number of segments, the cleaner examining if there are segments with invalid blocks to be cleaned;

f) if there are segments with invalid blocks, securing new space for storage by cleaning segments with invalid blocks with biggest rank value calculated in the step a); and

g) if there is no segment with invalid blocks, checking if the flash memory is full, and in case it'"'"'s full, notifying it to the user and in case it'"'"'s not full, the cleaner stopping operation because the remaining flash memory space can be used.

10. The method of claim 9, wherein, in the step f) of cleaning segments with invalid blocks, the oldest segment with sufficient space to accommodate the valid blocks of a segment to be erased is selected and the valid blocks are copied to the selected segment and the segment targeted for cleaning is erased.

11. The method of claim 10, wherein the procedure of cleaning the segment to be erased includes the steps of:

h) looking for the destination block where the valid blocks of the source segment to be erased will be moved, and converting it to the allocated status;

i) after the original data are copied to the destination block which has been converted to the allocated status in the step h), the destination block being converted to the prevalid status with the source block no longer in need converted to invalid status, then making the destination block converted to valid status; and

j) conducting the cleaning procedure to the target segment of deletion, the source segment and converting it to a free segment.

12. A computer-based recording medium for recording a program in file systems with a processor for conducting ranked cleaning policy, the functions of:

a) calculating rank values for all segments of the flash memory periodically; and

b) if the storage space of the flash memory become less than a predetermined volume, the cleaner operating to secure new space by cleaning invalid space of the segment in order of their rank value high to low

wherein the rank values are calculated by an equation expressed as;

$R=A<br><br>\frac{\mathrm{age}·<br><br>i}{2<br><br>v·<br><br>f}$

where v is the ratio of valid blocks to the entire segments, f is the ratio of free blocks in a segment, i is the ratio of invalid blocks, age is the time that has passed since the segment is cleaned, and A is the weight.