Flash memory system and garbage collection method thereof

• US 7,890,550 B2
• Filed: 12/28/2006
• Issued: 02/15/2011
• Est. Priority Date: 11/03/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Hwang, Jae-Hyun, Lee, Shea-Yun, Kim, Jang-Hwan, Mo, Yeon-Jin, Jung, Myung-Jin, Song, Dong-Hyun
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Shmatov; Alexey
• Application Number:
  US11/646,501
• Publication Number:
  US 20080109590A1
• Time in Patent Office: 1,510 Days
• Field of Search: 707/206, 707/999.206, 707/813, 711/100, 711/154
• US Class Current: 707/813
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

Example embodiments provide a garbage collection method which includes applying a weight to each of at least two or more factors to calculate garbage collection costs. A hash table is configured using the calculated garbage collection costs. The method further includes searching a block having the lowest garbage collection cost from the hash table and performing garbage collection on the searched block.

Claims

1. A garbage collection method of a memory system including an interface device, the method comprising:

applying, by the interface device, a weight to a first factor and a second factor to calculate garbage collection costs, the weight for the first factor being higher than the weight for the second factor;

configuring, by the interface device, a hash table using the calculated garbage collection costs;

searching, by the interface device, a block having the lowest garbage collection cost from the hash table; and

performing, by the interface device, garbage collection on the searched block,

wherein the first factor is wear level information and the second factor is information of a valid page number per block or the second factor is wear level information and the first factor is information of a valid page number per block, and

the garbage collection costs are calculated by adding at least a product of the first factor and the first weight and a product of the second factor and the second weight, with respect to each physical block.

2. The garbage collection method of claim 1, wherein a sum of weights assigned to the first factors and the second factor has a value of 1.0.

3. The garbage collection method of claim 1, wherein the hash table includes a plurality of data lists corresponding to the garbage collection costs.

4. The garbage collection method of claim 3, wherein each of the plurality of data lists is a linked list.

5. The garbage collection method of claim 3, wherein each of the plurality of data lists is one selected from a group of a single linked list, a double linked list, and a circular linked list.

6. The garbage collection method of claim 1, wherein the garbage collection costs are updated whenever a write operation of a flash memory device is carried out.

7. The garbage collection method of claim 1, wherein the garbage collection costs are updated whenever a write operation of a flash memory device is ended.

8. The garbage collection method of claim 1, wherein blocks are detected based on increasing garbage collection costs.

9. The garbage collection method of claim 8, wherein during garbage collection, the garbage collection is performed on N (where N is an integer >

1) blocks.

10. A storage device comprising:

a flash memory; and

an interface device configured to operate responsive to a write request of the flash memory from a host, the interface device including,

a host interface configured to interface with the host,

a control processing unit configured to control an overall operation of the storage device,

a work memory configured to store software for performing flash translation layer functions and to store mapping information of the flash memory, and

a buffer memory configured to temporarily store data when storing data in the flash memory or when reading data form the flash memory,

wherein upon the write request, the interface device is configured to apply a weight to a first factor and a second factor to calculate garbage collection costs and to configure a hash table using the calculated garbage collection cost, the weight for the first factor being higher than the weight for the second factor; and

wherein the interface device is configured to search a block having the lowest garbage collection cost from the hash table and to perform garbage collection on the searched block, and

the first factor is wear level information and the second factor is information of a valid page number per block or the second factor is wear level information and the first factor is information of a valid page number per block, and

the garbage collection costs are calculated by adding at least a product of the first factor and the first weight and a product of the second factor and the second weight, with respect to each physical block.

11. The flash storage device of claim 10, wherein a sum of weights assigned to the first factors and the second factor has a value of 1.0.

12. The flash storage device of claim 10, wherein the hash table includes a plurality of data lists corresponding to the garbage collection costs.

13. The flash storage device of claim 12, wherein each of the plurality of data lists is a linked list.

14. The flash storage device of claim 13, wherein each of the plurality of data lists is one selected from a group of a single linked list, a double linked list, and a circular linked list.

15. The flash storage device of claim 14, wherein the garbage collection costs are updated whenever a write operation of the flash memory is carried out.

16. The flash storage device of claim 10, wherein the garbage collection costs are updated whenever a write operation of the flash memory is ended.

17. The flash storage device of claim 10, wherein the interface device is configured to detect blocks based on increasing garbage collection costs.

18. The flash storage device of claim 17, wherein the interface device performs the garbage collection on N (where N is an integer >

1) blocks.

19. The flash storage device of claim 18, wherein the flash memory stores software to perform a flash translation layer function.

20. The flash storage device of claim 10, wherein software stored in the work memory is loaded from the flash memory.

21. The flash storage device of claim 20, wherein the work memory includes either one of DRAM and SRAM.

22. The flash storage device of claim 20, wherein the hash table is loaded from the flash memory to the work memory.

23. The flash storage device of claim 10, wherein the hash table is stored in the flash memory.