# US 2010/0169544 A1 · Methods for distributing log block associativity for real-time system and flash memory devices performing the same

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169544 A1
- Document ID: US20100169544A1
- Status: Published application
- Kind: A1
- Application number: 12/356,306
- Filed: 2009-01-20
- Published: 2010-07-01
- Earliest claimed: 2008-12-31
- Assignees: Sungkyunkwan University Foundation for Corporate Collaboration
- Inventors: Young-Ik EOM; Dong-Kun SHIN; Hyun-Jin CHO
- Web page: https://patentgrep.com/patent/US20100169544A1

## CPC

- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 2212/7201: Logical to physical mapping or translation of blocks or pages
- G06F 2212/7202: Allocation control and policies
- G06F 2212/7203: Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 2)

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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 6)

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.

### Claim 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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 10)

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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 13)

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.
