Memory system using flash memory and method of controlling the memory system

• US 5,737,742 A
• Filed: 06/27/1995
• Issued: 04/07/1998
• Est. Priority Date: 06/29/1994
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Yamamoto, Akira, Achiwa, Kyosuke, Yamagata, Hirotsugu
• Primary Examiner(s): Asta, Frank J.
• Application Number:
  US08/495,165
• Time in Patent Office: 1,015 Days
• Field of Search: 395/430, 395/481, 395/485, 395/492, 365/218, 365/189.09, 365/185
• US Class Current: 711/103
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles

Abstract

A memory system includes a flash memory having a plurality of individually erasable physical blocks, table section for holding the relationship in correspondence between the logical blocks allocated by the allocation section and the physical blocks first counting and managing section for counting and managing write counts of the respective logical blocks, first classifying section for classifying the logical blocks into a plurality of groups on the basis of the respective write counts of the logical blocks, erasure section for erasing data in a physical block allocated to a logical block to produce a free physical block, second counting and managing section for counting and managing the erasure counts of the respective physical blocks, second classifying section for classifying the physical blocks into a plurality of groups on the basis of the respective erasure counts of the physical blocks, control section for allocating the respective logical blocks to the physical blocks; and managing section for managing free physical blocks which are not allocated to any logical blocks, wherein the allocation control section performs an exchanging process as required which comprises the steps of allocating a logical block belonging to a logical block group having a larger write count to a free physical block belonging to a physical block group having a smaller erasure count and allocating a logical block belonging to a logical block group having a smaller write count to a free physical block belonging to a logical block group having a larger erasure count, increasing the service life of the memory system by preventing requests from collecting in a particular sector.

Claims

1. A method of controlling a memory system using a flash memory wherein a logical block as a unit accessed by a computer is allocated to a physical block of the flash memory, comprising the steps of:

a) counting and managing a write count of each logical block unit each time data is written into that logical block;

b) counting and managing an erasure count of each physical block unit each time that physical block is erased;

c) classifying a plurality of logical blocks into a plurality of logical block groups according to write count;

d) classifying a plurality of physical blocks into a plurality of physical block groups according to erasure count; and

e) allocating a logical block belonging to a logical block group having a larger write count to a physical block which belongs to a physical block group having a smaller erasure count when data is written into the logical block.

2. A method according to claim 1, wherein the step e) comprises the steps of beforehand preparing in each physical block group at least one free physical block which is not allocated to any logical block and allocating to the logical block a free physical block belonging to a physical block group which has a smaller erasure count.

3. A method according to claim 2, further comprising the steps of locating a physical block having a smaller erasure count and allocated to a logical block belonging to a logical block group which has a smaller write count, when the free physical block is allocated, to handle as a target free physical block a free physical block belonging to the same physical block group as the physical block belongs to.

4. A method according to claim 3, further comprising the steps of copying the data in the physical block having a smaller erasure count to the free physical block belonging to the same physical block group as an old physical block allocated to the logical block having a larger write count belongs to and erasing data in the physical block from which data is copied to produce a free physical block;

newly allocating the physical block to which data is be copied to a logical block to which the physical block from which data is to be copied is allocated; and

erasing data in the old physical block to produce a free physical block.

5. A method according to claim 2, wherein the step of allocating a logical block having a larger write count to a physical block having a smaller erasure count is performed each time the erasure count of a physical block corresponding to the logical block having a larger write count reaches a predetermined multiple, and comprising the step of:

allocating the physical block to a free physical block belonging to the same physical block group as the old physical block to which the logical block is allocated belongs to and erasing the data in the old physical block to produce a free physical block when data is written into a logical block other than the logical block having a larger write count.

6. A method according to claim 1, wherein the logical block group comprises a central group of a predetermined count range to which the average one of write counts of all the logical blocks belongs, and at least one side group on each of both the sides of the central group, and comprising the step of changing the groups each time data is written.

7. A method according to claim 1, wherein the physical block group comprises a central group of a predetermined count range to which the average one of erasure counts of all the physical blocks belongs, and at least one side group on each of both the sides of the central group, and comprising the step of changing the groups each time data is erased.

8. A method of controlling a memory system using a flash memory where a logical block as a unit accessed by a computer is allocated to a physical block of the flash memory, comprising the steps of:

predicting whether a write count of each logical block in the future is larger or smaller on the basis of the situation of access to that logical block;

managing an erasure count of each physical block when that physical block is erased; and

allocating a logical block having a write count which is predicted to be larger to a physical block having a smaller erasure count and allocating a logical block having a write count which is predicted to be smaller to a physical block having a larger erasure count.

9. A memory system using a flash memory where logical blocks each as a unit accessed by a computer are allocated by allocation means to physical blocks of the flash memory, comprising:

a flash memory having a plurality of individually erasable physical blocks;

table means for holding the relationship in correspondence between the logical blocks allocated by the allocation means and the physical blocks;

first counting and managing means for counting and managing write counts of the respective logical blocks;

first classifying means for classifying the logical blocks into a plurality of groups on the basis of the respective write counts of the logical blocks;

erasure means for erasing data in a physical block allocated to a logical block to produce a free physical block;

second counting and managing means for counting and managing the erasure counts of the respective physical blocks;

second classifying means for classifying the physical blocks into a plurality of groups on the basis of the respective erasure counts of the physical blocks;

control means for allocating the respective logical blocks to the physical blocks; and

means for managing free physical blocks which are not allocated to any logical blocks;

wherein said allocation control means performs an exchanging process as required which comprises the steps of allocating a logical block belonging to a logical block group having a larger write count to a free physical block belonging to a physical block group having a smaller erasure count and allocating a logical block belonging to a logical block group having a smaller write count to a free physical block belonging to a logical block group having a larger erasure count.

10. A memory system according to claim 9, wherein said allocation control means allocates, in a normal write process, a logical block in which data is to be written to a free physical block belonging to the same physical block group as an old physical block which is already allocated to the logical block, and changes the old physical block to a free physical one;

and

performs the exchanging process when a predetermined condition is satisfied.

11. A memory system according to claim 10, wherein said allocation control means copies data in the physical block allocated to the logical block having a smaller write count to a free physical block belonging to the same physical block group as the old physical block group belongs to, and changes the old physical block to a free physical block.

12. A memory system according to claim 9, wherein the logical and physical blocks are the same in size.

13. A memory system according to claim 9, wherein the block size of a logical block is a multiple of that of a physical block, and further comprising compression/expansion means for compressing the data in the logical block and expanding the compressed data, wherein one logical block is allocated to at least one physical block in dependence on the degree of its compression.

14. A memory system according to claim 9, further comprising means for composing a queue of physical blocks connected to each of logical block group units of logical blocks to which the physical blocks belonging to each of physical block groups are allocated for that physical block group, and group table means for indicating the head of the queue, wherein said allocation control means performs the exchanging process by referring to said group table means.

15. A memory system according to claim 14, wherein said group table means also manages free physical blocks belonging to each of the physical block groups for each physical block group.

16. A storage system according to claim 10, wherein the predetermined condition is that when a logical block belonging to a logical block group having a larger write count has received a write request, the erasure count of the free physical block in which data is to be written is a multiple of a predetermined number.