FLASH MEMORY SYSTEM AND DEFRAGMENTATION METHOD

• US 20110099326A1
• Filed: 10/27/2010
• Published: 04/28/2011
• Est. Priority Date: 10/27/2009
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: SHIN, Dong Jun, KWON, Moon Sang, JUNG, Dawoon
• Granted Patent: US 8,626,987 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 2206/1004 Defragmentation
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Provided is a flash memory system supporting flash defragmentation. The flash memory system includes a host and a flash storage device. In response to a flash defragmentation command by the host, the flash storage device performs flash defragmentation by grouping fragments stored in fragmented blocks of a flash memory on a flash memory management unit basis. The flash memory management unit may be a memory block or page. The flash storage device performs the flash defragmentation regardless of the arrangement order of fragmented files stored in the flash memory.

Claims

1-20. -20. (canceled)

21. A method of defragmenting a flash memory operated under the control of a host, the flash memory being arranged in a plurality of blocks including a free block and a plurality of fragmented blocks respectively storing at least one fragment, the method comprising:

identifying a plurality of fragments stored in the plurality of fragmented blocks according to corresponding logical addresses;

converting the logical addresses to corresponding physical addresses using a flash translation layer (FTL);

using the physical addresses, reading a subset of fragments in the plurality of fragments from at least one of the plurality of fragmented blocks;

grouping the subset of fragments within a grouping memory having a size defined by a flash management unit; and

writing the grouped subset of fragments from the grouping memory to the free block.

22. The method of claim 21, wherein the reading and the grouping of the subset of fragments are performed regardless of an arrangement order of the plurality of fragments as stored in the flash memory, and the flash management unit is equal in size to a single block in the plurality of blocks.

23. The method of claim 21, wherein the logical addresses are defined by sector addresses compatible with a data storage method used with a hard disk drive (HDD).

24. The method of claim 21, further comprising:

creating at least one new free block from at least one of the fragmented blocks following writing of the grouped subset of fragments to the free block.

25. The method of claim 24, wherein the converting of the logical addresses into the corresponding physical addresses using the FTL is performed with reference to a mapping table managed by the FTL, the method further comprising:

updating the mapping table following writing of the grouped subset of fragments to the free block; and

updating the mapping table following creation of the new free block.

26. The method of claim 25, wherein the host comprises an application and a file system, and the method further comprises:

by operation of the application and the file system, defining systems files in relation to the logical addresses, and

updating the file system is following each updating of the mapping table.

27. The method of claim 26, further comprising:

by operation of the file system, identifying a number of fragmented blocks;

comparing the number of fragmented blocks to a fragmented block threshold; and

only if the number of fragmented blocks exceeds the fragmented block threshold, executing the method of defragmenting the flash memory.

28. The method of claim 27, further comprising after the updating the system files:

identifying an updated number of fragmented blocks;

comparing the updated number of fragmented blocks to the fragmented block threshold; and

if the updated number of fragmented blocks still exceeds the fragmented block threshold, continue execution of the method of defragmenting the flash memory, or if the updated number of fragmented blocks does not exceed the fragmented block threshold, ending the method of defragmenting the flash memory.

29. The method of claim 21, wherein the host further comprises a host memory used as the grouping memory.

30. (canceled)

31. A method of defragmenting a flash memory, the flash memory being arranged in a plurality of blocks including a free block and a plurality of fragmented blocks storing a plurality of fragments, and the method comprising:

managing a mapping table correlating externally applied logical addresses with physical addresses for the flash memory using a flash translation layer (FTL);

identifying the plurality of fragmented blocks and a plurality of fragments stored in the plurality of fragmented blocks;

reading a subset of fragments among the plurality of fragments without regard to an arrangement order of the plurality of fragments as stored in the fragmented blocks, and writing the subset of fragments in the free block.

32. The method of claim 31, further comprising:

updating the mapping table following the writing of the subset of fragments in the free block.

33. The method of claim 31, further comprising:

performing a data invalidity operation on one of the fragmented blocks from which at least one fragment was read during the flash defragmentation operation to thereby convert the one fragmented memory block to a new free block.

34. The method of claim 33, further comprising:

updating the mapping table following the data invalidity operation.

35. The method of claim 31, wherein the logical addresses are defined by sector addresses compatible with a data storage method used with a hard disk drive (HDD).

36. The method of claim 31, wherein the identifying of the plurality of fragmented blocks and the plurality of fragments stored in the plurality of fragmented blocks is performed with reference to the mapping table.

37. A method of defragmenting a flash memory arranged in a plurality of blocks, each block comprising a plurality of pages, the method comprising:

identifying a plurality of fragmented blocks among the plurality of blocks;

identifying a plurality of fragments stored in the fragmented blocks;

identifying N free pages of one fragmented block;

reading N fragments among the plurality of fragments from one of the plurality of fragmented blocks other than the one fragmented block without regard of an arrangement order of the N fragments as stored in the plurality of fragmented blocks; and

writing the N fragments to fill the N free pages to thereby convert the one fragmented block to a new non-fragmented block.

38. The method of claim 37, further comprising:

updating a mapping table correlating externally applied logical addresses with corresponding physical addresses for the plurality of block after converting the one fragmented block to the new non-fragmented block.

39. The method of claim 38, further comprising:

performing a data invalidity operation on one of the plurality of fragmented blocks other than the one fragmented block from which at least one fragment was read during the flash defragmentation operation to thereby convert the one of the plurality of fragmented blocks other than the one fragmented block to a new free block.

40. The method of claim 39, further comprising:

updating the mapping table following the data invalidity operation.

41. (canceled)