METHOD OF MANAGING DATA STORAGE DEVICE AND DATA STORAGE DEVICE

• US 20140101373A1
• Filed: 09/26/2013
• Published: 04/10/2014
• Est. Priority Date: 09/27/2012
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: KIM, JAE-GEUK, HWANG, JOO-YOUNG, LEE, SEH-WAN
• Granted Patent: US 9,244,619 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method of managing a data storage device including a memory controller and a memory device includes: calculating a first sequential and consecutive write cost (SCWC) according to a garbage collection (GC) write operation policy, a second SCWC according to a slack space recycling (SSR) write operation policy and a third SCWC according to an in-place updating (IPU) write operation policy respectively, in response to a write request in the memory controller; determining a write operation policy which has a minimum cost of the first through third SCWCs; and writing data in a selected segment in the memory device according to the determined write operation policy.

Claims

1. A method of managing a data storage device including a memory controller and a memory device, the method comprising:

for a write request received at the data storage device;

calculating a first sequential and consecutive write cost (SCWC) according to a garbage collection (GC) write operation policy,

calculating a second SCWC according to a slack space recycling (SSR) write operation policy, and

calculating a third SCWC according to an in-place updating (IPU) write operation policy;

determining a write operation policy which has a lowest cost among the first through third SCWCs; and

writing data in a selected segment in the memory device according to the determined write operation policy.

2. The method of claim 1, wherein calculating the first SCWC comprises:

calculating a valid page consecutive read time for each of one or more consecutive valid page clusters in the selected segment to calculate a segment valid page read time corresponding to a sum of the valid page consecutive read times;

calculating a first consecutive write time for all valid pages in the selected segment;

calculating a second consecutive write time for all invalid pages in the selected segment;

calculating a meta data read time for all of the valid pages in the selected segment;

calculating a meta data write time for all of the valid pages and the invalid pages in the selected segment; and

determining a sum of the segment valid page read time, the first consecutive write time, the second consecutive write time, the meta data read time and the meta data write time as the first SCWC.

3. The method of claim 2, wherein the valid page consecutive read times and the first and second consecutive write times are calculated by referring to a device performance table storing a plurality of consecutive read times and a plurality of consecutive write times which are measured per a consecutive unit storage space.

4. The method of claim 3, wherein a consecutive read time or a consecutive read time which is not included in the device performance table is calculated by interpolating between adjacent consecutive read times or consecutive write times, respectively, included in the device performance table.

5. The method of claim 3, wherein the device performance table is filled by performing a device performance measuring algorithm when a storage space in the memory device is formatted, and the filled device performance table is stored in a super block in the storage space.

6. The method of claim 1, wherein calculating the second SCWC comprises:

calculating an invalid page consecutive write time for each of one or more consecutive invalid page clusters in the selected segment to calculate a segment slack space write time corresponding to a sum of the invalid page consecutive write times;

calculating a segment slack space meta data write time corresponding to a meta data write time for all of invalid pages in the selected segment; and

determining a sum of the segment slack space write time and the segment slack space meta data write time as the second SCWC.

7. The method of claim 1, calculating the third SCWC comprises determining a sum of write times of each unit page of all invalid pages in the selected segment as the third SCWC.

8. The method of claim 1, wherein the selected segment is selected by selecting at least one segment having a minimum valid space among a plurality of used segments of the memory device, and, when the at least one segment includes a plurality of segments, selecting as the selected segment a segment among the plurality of used segments having the minimum valid space which also has a largest consecutive invalid space.

9. A data storage device, comprising:

a memory device; and

a memory controller configured to control the memory device, the memory controller comprising a processor including a write operation module configured to perform a sequential and consecutive write operation when data is written in a selected segment in the memory device,

wherein the write operation module comprises;

a garbage collection (GC) cost calculation module configured to calculate a first sequential and consecutive write cost (SCWC) according to a GC write operation policy;

a slack space recycling (SSR) cost calculation module configured to calculate a second SCWC according to a SSR write operation policy; and

an in-place updating (IPU) cost calculation module configured to calculate a third SCWC according to an IPU write operation policy, and

wherein the processor is configured to write the data in the selected segment according to a write operation policy which has a lowest cost among the first through third SCWCs.

10. The data storage device of claim 9, wherein the GC cost calculation module is:

configured to calculate a valid page consecutive read time for each of one or more consecutive valid page clusters in the selected segment to calculate a segment valid page read time corresponding to a sum of the valid page consecutive read times,

configured to calculate a first consecutive write time for all valid pages in the selected segment,

configured to calculate a second consecutive write time for all invalid pages in the selected segment,

configured to calculate a meta data read time for all of the valid pages in the selected segment,

configured to calculate a meta data write time for all of the valid pages and the invalid pages in the selected segment; and

configured to determine a sum of the segment valid page read time, the first consecutive write time, the second consecutive write time, the meta data read time and the meta data write time as the first SCWC.

11. The data storage device of claim 10, wherein the memory controller further comprises a memory that includes a device performance table storing a plurality of consecutive read times and a plurality of consecutive write times which are measured per a consecutive unit storage space, and the write operation module is configured to calculate the valid page consecutive read times and the first and second consecutive write times by referring to the device performance table.

12. The data storage device of claim 11, wherein the write operation module calculates a consecutive read time or a consecutive read time which is not included in the device performance table by interpolating between adjacent consecutive read times or consecutive write times, respectively, included in the device performance table.

13. The data storage device of claim 9, wherein the SSR cost calculation module is:

configured to calculate an invalid page consecutive write time for each of one or more consecutive invalid page clusters in the selected segment to calculate a segment slack space write time corresponding to a sum of the invalid page consecutive write times;

configured to calculate a segment slack space meta data write time corresponding to a meta data write time for all invalid pages in the selected segment; and

configured to determine a sum of the segment slack space write time and the segment slack space meta data write time as the second SCWC.

14. The data storage device of claim 9, wherein the IPU cost calculation module is configured to determine a sum of write times of each unit page of all invalid pages in the selected segment as the third SCWC.

15. The data storage device of claim 9, wherein the processor further comprises a victim selection module configured to select at least one segment having a minimum valid space among a plurality of used segments of the memory device, and further configured to select as the selected segment, when the at least one segment includes a plurality of segments, a segment among the plurality of used segments having the minimum valid space which also has a largest consecutive invalid space.

16. A method of operation of a data storage device including a memory device and a memory controller, the method comprising:

receiving a write request at the data storage device;

determining whether a free segment exists in the memory device;

when a free segment does not exist in the memory device, selecting a victim segment in the memory device;

determining a first sequential and consecutive write cost (SCWC) corresponding to writing data to the selected victim segment according to a first write operation policy;

determining a second SCWC corresponding to writing the data to the selected victim segment according to a second write operation policy which is different from the first write operation policy;

determining a third SCWC corresponding to writing the data to the selected victim segment according to a third write operation policy which is different from the first and second write operation policies;

selecting a write operation policy among the first, second, and third write operation policies which has a lowest corresponding cost among first through third SCWCs; and

writing the data to the selected memory segment in the memory device via the memory controller according to the selected write operation policy.

17. The method of claim 16, wherein the first write operation policy is a garbage collection policy wherein data stored in the selected victim segment is copied to another, different, segment for allowing the selected victim segment to be rewritten to, the second write operation policy is a slack space recycling write operation policy wherein the data is consecutively written in slack spaces in the selected victim segment according to physical orderings in the selected victim segment, and the third write operation policy is an in-place updating write operation policy wherein the data is randomly written in invalid page clusters of the selected victim segment.

18. The method of claim 17, wherein selecting the victim segment comprises:

searching among a plurality of used segments of the memory device for one or more used segments each having a minimum valid space;

when there is exactly one used segment having the minimum valid space, selecting the one used segment having the minimum valid space as the victim segment; and

when there are more than one used segment having the minimum valid space, selecting as the victim segment a one of the used segments having the minimum valid space which also has a largest sequential invalid storage space.

19. The method of claim 17, wherein determining each of the first, second, and third SCWCs comprises accessing performance data stored in a device performance table, wherein the performance data comprises valid page sequential read times, valid page sequential write times, invalid page sequential write times, meta data read times, and meta data write times for each of a plurality of sequential data units for the memory device.

20. The method of claim 19, further comprising:

measuring the performance data for the memory device;

storing the performance data in the memory device when the memory device is formatted; and

when the memory device is mounted, reading the performance data from the memory device and storing the performance data in the device performance table in a second, separate, memory device of the memory controller.