METHODS FOR DISTRIBUTING LOG BLOCK ASSOCIATIVITY FOR REAL-TIME SYSTEM AND FLASH MEMORY DEVICES PERFORMING THE SAME

• US 20100169544A1
• Filed: 01/20/2009
• Published: 07/01/2010
• Est. Priority Date: 12/31/2008
• Status: Active Grant

• Current Assignee: Intellectual Discovery Co., Ltd.
• Original Assignee: Sungkyunkwan University Foundation For Corporate Collaboration (SungKyunKwan University)
• Inventors: EOM, Young-Ik, SHIN, Dong-Kun, CHO, Hyun-Jin
• Granted Patent: US 8,261,010 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/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks

Abstract

A method for distributing log block associativity in log buffer-based flash translation layer (FTL) includes, if write request on page p is generated, checking whether log block associated with corresponding data block that write request is generated exists or not by checking log block mapping table storing mapping information between data blocks and log blocks, wherein the associativity of each log block to data block is set to equal to or less than predetermined value K in advance, and K is a natural number, if log block associated with corresponding data block that write request is generated exists, checking whether associated log block is random log block or sequential log block, and if associated log block is random log block, writing data that write request is generated in first free page of random log block.

Claims

1. A method for distributing a log block associativity in a log buffer-based flash translation layer (FTL) of a flash memory with physical blocks which include a plurality of data blocks which are identified by different logical block numbers and a plurality of log blocks which are identified by different logical log block numbers, the method comprising:

if a write request to write a page p into a log block is generated, checking whether a log block associated with a corresponding data block that the write request is generated exists or not by checking a log block mapping table which stores mapping information between the data blocks and the log blocks, where the associativity of each of the plurality of log blocks to a data block is set to equal to or less than a predetermined value K in advance, and K is a natural number;

if a log block associated with a corresponding data block that the write request is generated exists, checking whether the associated log block is a random log block or a sequential log block; and

if the associated log block is a random log block, writing data that the write request is generated in a first free page of the random log block.

2. The method of claim 1, further comprising, if a log block associated with a corresponding data block that the write request is generated does not exist, writing data that the write request is generated to increase the associativity of a log block to a data block.

3. The method of claim 2, wherein the writing data that the write request is generated to increase the associativity of a log block to a data block comprises distributing the log block associativity to maintain the log block associativity at minimum by writing data of data blocks having the same logical block number in the same log block and writing data of data blocks having different logical block numbers in different log blocks.

4. The method of claim 2, wherein the writing data that the write request is generated to increase the associativity of a log block to a data block comprises

if a log block that a switch merge is possible exists, writing data that the write request is generated in a new log block after performing a switch merge;

and

if a log block that a switch merge is possible does not exist and a free log block exists, writing data that the write request is generated in an available free log block.

5. The method of claim 4, wherein the writing data that the write request is generated to increase the associativity of a log block to a data block further comprises

if the switch merge is impossible and all log blocks are associated with at least one data block, determining whether the associativity of a currently allocated log block reaches the predetermined value K or not or an offset of data that the write request is currently generated is 0 or not;

and

if the associativity of a currently allocated log block does not reach the predetermined value K or an offset of data that the write request is currently generated is not 0, selecting a log block which has most free pages among log blocks having a minimum associativity to write data that the write request is generated.

6. The method of claim 1, further comprising,

if the associated log block is a sequential log block, checking whether the sequentiality of the associated sequential log block can be maintained or not;

and

if the sequentiality of the associated sequential log block can be maintained, writing data that the write request is generated in a first free page of the associated sequential log block.

7. The method of claim 6, further comprising,

if the sequentiality of the associated sequential log block cannot be maintained, checking the number of free pages of the associated sequential log block when the amplitude of a first offset of a last page currently written in the associated sequential log block is equal to or larger than the amplitude of a second offset of data that the write request is generated;

and

if the number of free pages is larger than a predetermined value, transforming the associated sequential log block to a random log block after writing data that the write request is generated in the associated sequential log block.

8. The method of claim 7, further comprising, if the sequentiality of the associated log block cannot be maintained, writing data that the write request is generated in the associated sequential log block to maintain the sequential log block after copying data between intermediate offsets to the associated sequential log block when the amplitude of the first offset is smaller than the amplitude of the second offset and a gap between the first and second offsets is not larger than a predetermined gap.

9. The method of claim 6, wherein the maximum number of sequential log blocks is variable, and the maximum number of sequential log blocks is equal to or more than 1.

10. A flash memory device, comprising:

a flash memory which includes a plurality of blocks each of which includes a plurality of pages; and

a flash translation layer (FTL) which maps a logical address transmitted from a file system with a physical address of the flash memory using an address translation mapping table,

wherein the FTL identifies a plurality of data blocks using different logical block numbers and a plurality of log blocks using different logical log block numbers, and

the FTL performs

if a write request to write a page p in a log block is generated, checking whether a log block associated with a corresponding data block that the write request is generated exists or not by checking a log block mapping table which stores mapping information between the data blocks and the log blocks, where the associativity of each of the plurality of log blocks to a data block is set to equal to or less than a predetermined value K in advance, and K is a natural number;

if a log block associated with a corresponding data block that the write request is generated exists, checking whether the associated log block is a random log block or a sequential log block; and

if the associated log block is a random log block, writing data that the write request is generated in a first free page of the random log block.

11. The flash memory device of claim 10, wherein the FTL further performs if a log block associated with a corresponding data block that the write request is generated does not exist, writing data that the write request is generated to increase the associativity of a log block to a data block.

12. The flash memory device of claim 11, wherein the writing data that the write request is generated to increase the associativity of a log block to a data block comprises distributing the log block associativity to maintain the log block associativity at minimum by writing data of data blocks having the same logical block number in the same log block and writing data of data blocks having different logical block numbers in different log blocks.

13. The flash memory device of claim 10, wherein the FTL further performs

if the associated log block is a sequential log block, checking whether the sequentiality of the associated sequential log block can be maintained or not;

and

if the sequentiality of the associated sequential log block can be maintained, writing data that the write request is generated in a first free page of the associated sequential log block.

14. The flash memory device of claim 13, wherein the FTL further performs

if the sequentiality of the associated sequential log block cannot be maintained, checking the number of free pages of the associated sequential log block when the amplitude of a first offset of a last page currently written in the associated sequential log block is equal to or larger than the amplitude of a second offset of data that the write request is generated;

and

if the number of free pages is larger than a predetermined value, transforming the associated sequential log block to a random log block after writing data that the write request is generated in the associated sequential log block.

15. The flash memory device of claim 14, wherein the FTL further performs, if the sequentiality of the associated log block cannot be maintained, writing data that the write request is generated in the associated sequential log block to maintain the sequential log block after copying data between intermediate offsets to the associated sequential log block when the amplitude of the first offset is smaller than the amplitude of the second offset and a gap between the first and second offsets is not larger than a predetermined gap.

16. The flash memory device of claim 13, wherein the maximum number of sequential log blocks is variable, and the maximum number of sequential log blocks is equal to or more than 1.