Flash memory system and garbage collection method thereof

• US 20080109590A1
• Filed: 12/28/2006
• Published: 05/08/2008
• Est. Priority Date: 11/03/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jung, Myung-Jin, Hwang, Jae-Hyun, Song, Dong-Hyun, Lee, Shea-Yun, Kim, Jang-Hwan, Mo, Yeon-Jin
• Granted Patent: US 7,890,550 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• 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; configuring a hash table using the calculated garbage collection costs; 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 comprising:

applying a weight to each of at least two or more factors to calculate garbage collection costs;

configuring a hash table using the calculated garbage collection costs;

searching a block having the lowest garbage collection cost from the hash table; and

performing garbage collection on the searched block.

2. The garbage collection method of claim 1, wherein each of the factors includes at least either one of wear level information and information of a valid page number per block.

3. The garbage collection method of claim 1, wherein a sum of weights assigned to the factors has a value of 1.0.

4. The garbage collection method of claim 1, wherein the garbage collection costs are calculated by adding a product of a factor and a weight with respect to each physical block.

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

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

7. The garbage collection method of claim 5, 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.

8. 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.

9. 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.

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

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

1) blocks.

12. A memory system comprising:

a host;

a flash memory; and

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

wherein upon the write request, the interface device is configured to apply a weight to each of at least two or more factors to calculate garbage collection costs and to configure a hash table using the calculated garbage collection cost; 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.

13. The flash memory system of claim 12, wherein each of the factors includes at least either one of wear level information and information of a valid page number per block.

14. The flash memory system of claim 12, wherein a sum of weights assigned to the factors has a value of 1.0.

15. The flash memory system of claim 12, wherein the garbage collection costs are calculated by adding a product of a factor and a weight with respect to each physical block.

16. The flash memory system of claim 12, wherein the hash table includes a plurality of data lists corresponding to the garbage collection costs.

17. The flash memory system of claim 16, wherein each of the plurality of data lists is a linked list.

18. The flash memory system of claim 16, 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.

19. The flash memory system of claim 12, wherein the garbage collection costs are updated whenever a write operation of the flash memory is carried out.

20. The flash memory system of claim 12, wherein the garbage collection costs are updated whenever a write operation of the flash memory is ended.

21. The flash memory system of claim 12, wherein the interface device is configured to detect blocks based on increasing garbage collection costs.

22. The flash memory system of claim 21, wherein the interface device performs the garbage collection on N (where N is an integer>

1) blocks.

23. The flash memory system of claim 12, wherein the flash memory stores software to perform a flash translation layer function.

24. The flash memory system of claim 12, wherein the interface device includes a memory in which software to perform a flash translation layer function is loaded from the flash memory.

25. The flash memory system of claim 24, wherein the memory includes either one of DRAM and SRAM.

26. The flash memory system of claim 12, wherein the hash table is stored in the flash memory.

27. The flash memory system of claim 24, wherein the hash table is loaded from the flash memory to the memory.