MEMORY SYSTEM MANAGING MULTIPLE LOGICAL ADDRESS SPACES

According to one embodiment, a controller of a memory system provides a host with logical address spaces. A plurality of queues of the host include one or more queues allocated to each of the logical address spaces. The controller calculates first use amounts of a nonvolatile memory corresponding to the logical address spaces, respectively, selects a queue from which a command is to be fetched among the plurality of queues, based on the first use amounts, fetches a command from the queue, calculates a predicted use amount of the nonvolatile memory in accordance with the command, and updates a second use amount corresponding to a first logical address space to which the first queue is allocated among the first use amounts by using the predicted use amount.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is based upon and claims the benefit of priority from Japanese Patent Application No. 2023-149123, filed Sep. 14, 2023, the entire contents of which are incorporated herein by reference.

FIELD

Embodiments described herein relate generally to a technique for controlling a nonvolatile memory.

BACKGROUND

In recent years, memory systems that include a nonvolatile memory have been widely used. As one of such memory systems, a solid state drive (SSD) that includes a NAND flash memory is known. The SSD is used as a main storage of various computing devices.

The memory system performs a process for the nonvolatile memory in accordance with a command received from a host.

More specifically, the host includes, for example, a submission queue (SQ). The submission queue is capable of storing one or more commands to be executed in the memory system.

The memory system receives a command from the host by fetching the command from the submission queue. Then, the memory system executes a process in accordance with the received command.

The submission queue may be allocated to a logical address space. The logical address space includes one or more logical addresses. The logical address is used by the host for addressing a storage area of the memory system.

The memory system may provide the host with a plurality of logical address spaces. Each of the logical address spaces is also referred to as a namespace. To each of the logical address spaces, for example, one or more submission queues are allocated. Each of the submission queues stores a command that designates a logical address in a corresponding logical address space.

DETAILED DESCRIPTION

In general, according to one embodiment, a memory system includes a nonvolatile memory and a controller. The controller is electrically connected to the nonvolatile memory. The controller communicates with a host that includes a plurality of queues each being capable of storing one or more commands. The controller provides the host with a plurality of logical address spaces. The plurality of logical address spaces include at least a first logical address space. One or more queues of the plurality of queues are allocated to each of the plurality of logical address spaces. The controller calculates a plurality of first use amounts of the nonvolatile memory that correspond to the plurality of logical address spaces, respectively. The plurality of first use amounts include at least a second use amount that corresponds to the first logical address space. The controller selects a first queue from which a command is to be fetched among the plurality of queues, based on the plurality of first use amounts. The first queue is allocated to the first logical address space. The controller fetches a first command from the first queue. The controller calculates a predicted use amount of the nonvolatile memory. The predicted use amount is an amount of the nonvolatile memory that is to be used in accordance with the first command. The controller updates the second use amount by using the predicted use amount.

First, a configuration of an information processing system that includes a memory system according to an embodiment will be explained with reference toFIG.1. The information processing system1includes a host device2and a memory system3.

The host device2may be a storage server that stores a large amount of various data to the memory system3, or a personal computer. Hereinafter, the host device2is also referred to as a host2.

The memory system3is a storage device configured to write data into a nonvolatile memory and read data from the nonvolatile memory. The nonvolatile memory is, for example, a NAND flash memory4. The memory system3is also referred to as a storage device or a semiconductor storage device. The memory system3may be implemented as, for example, a solid state drive (SSD) including the NAND flash memory4. Hereinafter, a case where the nonvolatile memory is the NAND flash memory4will be mainly described as an example.

The memory system3may be used as a storage of the host2. The memory system3may be provided inside the host2or may be connected to the host2via a cable or a network.

An interface for connecting the host2to the memory system3conforms to standards such as PCI Express™ (PCIe™), Ethernet™, Fibre channel, or NVM Express™ (NVMe™).

The host2includes a CPU21and a random access memory (RAN)22. The CPU21and the RAM22are connected via, for example, a bus20.

The CPU21is, for example, at least one processor. The CPU21controls operations of various components of the host2.

The RAM22is a volatile memory. The RAM22is, for example, a dynamic random access memory (DRAM) or a static random access memory (SRAM). A storage area of the RAM22is allocated as, for example, a plurality of submission queues25.

Each of the plurality of submission queues25is a queue for storing a request issued to the memory system3by the host2. Thus, the host2transmits requests to the memory system3via the submission queues25. The request issued to the memory system3by the host2is, for example, a command. Hereinafter, the request issued to the memory system3by the host2is also referred to as a command or a host command. Each of the submission queues25includes multiple slots to which the host2writes commands, respectively, which are issued. A location in each submission queue25(that is, a slot) to which the host2should write a command is indicated by an SQ tail pointer. A head location in each submission queue25from which the memory system3should fetch a command is indicated by an SQ head pointer.

The host2writes (i.e., issues) a command to a location in the submission queue25that is indicated by the SQ tail pointer. Then, the host2adds one to the SQ tail pointer. When the value obtained by adding one to the SQ tail pointer has reached the number of slots of the submission queue25(that is, the queue size), the host2sets the SQ tail pointer to zero. Then, the host2writes the updated value of the SQ tail pointer to a SQ tail doorbell register of the memory system3.

In the example illustrated inFIG.1, three commands are stored in the submission queue25. The number of commands stored in the submission queue25corresponds to a difference between the SQ head pointer and the SQ tail pointer.

The memory system3includes, for example, the NAND flash memory4, a DRAM5, and a controller6.

The NAND flash memory4includes one or more NAND memory chips41. The one or more NAND memory chips41are, for example, N NAND memory chips41-1, . . . , and41-N. N is an integer of one or larger. Hereinafter, a case where the NAND flash memory4includes N NAND memory chips41-1, . . . , and41-N will be mainly described. Any one of the N NAND memory chips41-1, . . . , and41-N is also simply referred to as a NAND memory chip41.

FIG.2illustrates an example of a configuration of the NAND memory chip41. The NAND memory chip41includes, for example, one or more planes42. Each of the one or more planes42is a unit that performs a data write operation and a data read operation. The number of the planes42included in the NAND memory chip41is freely set. InFIG.2, a case where the NAND memory chip41includes four planes42is illustrated. The four planes42are a zeroth plane42-0, a first plane42-1, a second plane42-2, and a third plane42-3. Any one of the one or more planes42is also simply referred to as a plane42.

The plane42includes a memory cell array421. The memory cell array421includes multiple blocks B0, B1, B2, . . . , and Bm−1 each including a plurality of memory cells arranged in matrix. The blocks B0, B1, B2, . . . , and Bm−1 each function as a minimum unit of a data erase operation. The block may also be referred to as an erase block or a physical block. Each of the blocks B0, B1, B2, . . . , and Bm−1 includes multiple pages P0, . . . , and Pn−1. Each of the pages P0, . . . , and Pn−1 includes a plurality of memory cells connected to a single word line. The pages P0, . . . , and Pn−1 each function as a unit of a data write operation and a data read operation. Note that a word line may also function as a unit of a data write operation and a data read operation.

The tolerable maximum number of program/erase cycles (maximum number of P/E cycles) for each of the blocks is limited. One P/E cycle of a block includes a data erase operation to erase data stored in all memory cells in the block and a data program operation to write data in each page of the block.

The NAND memory chip41may be implemented as a flash memory configured to store multiple bits per memory cell.

The flash memory configured to store multiple bits per memory cell is, for example, a multi-level cell (MLC) flash memory (a four-level cell (4LC) flash memory), a triple-level cell (TLC) flash memory (an eight-level cell (8LC) flash memory), or a quad-level cell (QLC) flash memory (a sixteen-level cell (16LC) flash memory). The MLC flash memory is configured to store 2-bit data per memory cell. The TLC flash memory is configured to store 3-bit data per memory cell. The QLC flash memory is configured to store 4-bit data per memory cell. A flash memory configured to store 1-bit data per memory cell is also referred to as a single-level cell (SLC) flash memory (a two-level cell (2LC) flash memory).

In a case where the NAND memory chip41is implemented as an MLC flash memory, data of two pages is written into memory cells connected to a single word line by writing 2-bit data per memory cell. The data of two pages is composed of lower page data and upper page data. Any area in the MLC flash memory (for example, any one or more blocks) may be used as an area configured to store only one bit per memory cell (i.e., an SLC area). In a write operation to write data into the SLC area, data of only one page is written in memory cells connected to a single word line by writing 1-bit data per memory cell.

In a case where the NAND memory chip41is implemented as a TLC flash memory, data of three pages is written into memory cells connected to a single word line by writing 3-bit data per memory cell. The data of three pages is composed of lower page data, middle page data, and upper page data. Any area in the TLC flash memory (for example, any one or more blocks) may be used as the above-described SLC area, or an MLC area configured to store two bits per memory cell. Note that the SLC area and the MLC area may be defined by a unit smaller than a block. In the MLC area, data of only two pages is written into memory cells connected to a single word line by writing 2-bit data per memory cell.

In a case where the NAND memory chip41is implemented as a QLC flash memory, data of four pages is written into memory cells connected to a single word line by writing 4-bit data per memory cell. Any area in the QLC flash memory (for example, any one or more blocks) may be used as the SLC area, or may be used as the MLC area, or may be used as a TLC area configured to store three bits per memory cell. The SLC area, the MLC area, and the TLC area may be defined by a unit smaller than a block. In the TLC area, data of only three pages is written into memory cells connected to a single word line by writing 3-bit data per memory cell.

Note that the NAND memory chip41may be configured to store five or more bits per memory cell. In this case, any area in the NAND memory chip41may be used as an area in which data of only four or less bits is written per memory cell.

The description returns toFIG.1.

The DRAM5is a volatile memory. A storage area of the DRAM5is allocated to, for example, a storage area of firmware (FW), a cache area of a logical-to-physical address translation table50, and storage areas of a group management table51, a group-NAND use time management table52, and a namespace-NAND use time management table (NS-NAND use time management table)53.

The FW is a program for controlling an operation of the controller6. The FW is loaded from the NAND flash memory4to the DRAM5, for example.

The logical-to-physical address translation table50is a table for managing mapping between each logical address and each physical address. The logical address is used by the host2for addressing a storage area of the memory system3. The logical address is, for example, a logical block address (LBA).

The group management table51is a table for managing a group of submission queues25. The group is a management unit to which one or more submission queues25belong. For example, one or more submission queues25that have the same priority for the memory system3to fetch a command, belongs to one group. An example of a specific configuration of the group management table51will be described later with reference toFIG.3. Note that, in the following description, a submission queue25with a larger value of a priority means that a command stored in the submission queue25is more preferentially fetched.

The group-NAND use time management table52is a table for managing a NAND use time per group. The NAND use time is a duration for which the NAND flash memory4is used. The NAND use time of a group is the cumulative sum of durations for which the NAND flash memory4is used in accordance with commands fetched from submission queues25that belong to the group. An example of a specific configuration of the group-NAND use time management table52will be described later with reference toFIG.4.

The NS-NAND use time management table53is a table for managing a NAND use time per namespace. The NAND use time of a namespace is a cumulative sum of durations for which the NAND flash memory4is used in accordance with commands fetched from submission queues25that are allocated to the namespace. An example of a specific configuration of the NS-NAND use time management table53will be described later with reference toFIG.5.

A namespace is a logical address space that includes one or more logical addresses. The memory system3may provide the host2with a plurality of namespaces. Each of the plurality of namespaces is identified by a namespace ID and includes an independent logical address space. To each of the plurality of namespaces, one or more submission queues25are allocated. Each of the submission queues25stores, for example, a command that designates a logical address in a corresponding namespace (that is, in a corresponding logical address space). In addition, each of the plurality of namespaces is associated with one or more groups. To each of the one or more groups, at least one submission queue25among one or more submission queues25that are allocated to an associated namespace may belong.

A storage area of the DRAM5may be further allocated as buffer areas that temporarily store data. The buffer areas are, for example, a write buffer54and a read buffer55. The write buffer54temporarily stores user data to be written into the NAND flash memory4. The read buffer55temporarily stores user data read from the NAND flash memory4.

The controller6may be implemented with a circuit such as a system-on-a-chip (SoC). The controller6is configured to control the NAND flash memory4. The function of each unit of the controller6may be realized by dedicated hardware in the controller6or may be realized by a processor executing the FW.

The controller6may function as a flash translation layer (FTL) configured to execute data management and block management of the NAND flash memory4. The data management executed by the FTL includes (1) management of mapping data indicative of a relationship between each logical address and each physical address of the NAND flash memory4, and (2) process to hide a difference between data read/write operations in units of page and data erase operations in units of block. The block management includes management of defective blocks, wear leveling, and garbage collection.

The management of mapping between each logical address and each physical address is executed by using, for example, the logical-to-physical address translation table50. The controller6uses the logical-to-physical address translation table50to manage the mapping between each logical address and each physical address in a certain management size. A physical address corresponding to a logical address indicates a physical memory location in the NAND flash memory4to which data of the logical address is stored. The controller6manages, by using the logical-to-physical address translation table50, multiple storage areas that are obtained by logically dividing the storage area of the NAND flash memory4. These multiple storage areas correspond to multiple logical addresses, respectively. In other words, each of the storage areas is identified by one logical address. The logical-to-physical address translation table50may be loaded from the NAND flash memory4to the DRAM5when the memory system3is boot up.

The data write operation into one page is executable only once in a single P/E cycle. Thus, the controller6writes updated data corresponding to a logical address not to an original physical memory location in which previous data corresponding to the logical address is stored but to a different physical memory location. Then, the controller6updates the logical-to-physical address translation table50to associate the logical address with this different physical memory location rather than the original physical memory location and to invalidate the previous data (i.e., data stored in the original physical memory location). Data to which the logical-to-physical address translation table50refers (that is, data associated with a logical address) is referred to as valid data. Furthermore, data not associated with any logical address is referred to as invalid data. The valid data is data to be possibly read by the host2later. The invalid data is data not to be read by the host2anymore.

The controller6may instruct the NAND memory chip41to execute a data write operation, for example, in any one of an SLC mode, an MLC mode, a TLC mode, and a QLC mode. The SLC mode is a mode in which one bit is written per memory cell. The MLC mode is a mode in which two bits are written per memory cell. The TLC mode is a mode in which three bits are written per memory cell. The QLC mode is a mode in which four bits are written per memory cell.

The controller6includes, for example, a DRAM interface (DRAM I/F)11, an SRAM12, and a memory controller13. The DRAM I/F11, the SRAM12, and the memory controller13are connected, for example, via a bus10.

The DRAM I/F11functions as a DRAM control circuit configured to control access to the DRAM5.

The SRAM12is a volatile memory. A storage area of the SRAM12is allocated, for example, as one or more intermediate queues15. Each of the intermediate queues15is configured to store a request to the NAND flash memory4. The request to the NAND flash memory4is referred to as a NAND request. The NAND request is generated on the basis of a command (host command) fetched from the submission queues25. The one or more intermediate queues15correspond to, for example, one or more groups, respectively. An intermediate queue15stores one or more NAND requests that correspond to a command fetched from a submission queue25that belongs to a group corresponding to the intermediate queue15. In the intermediate queue15, one or more NAND requests whose corresponding processes have not been executed may be accumulated. The one or more NAND requests stored in the intermediate queue15are processed by the memory controller13in a specific order (for example, in the order of their being stored). A NAND request that has been processed is discarded from the intermediate queue15.

Note that a storage area of the SRAM12may be allocated for at least any one of the FW, the logical-to-physical address translation table50, the group management table51, the group-NAND use time management table52, and the NS-NAND use time management table53. A storage area of the SRAM12may be allocated as the write buffer54and the read buffer55.

The memory controller13is configured to control various processes on the NAND flash memory4. Specifically, the memory controller13fetches a command from each of the plurality of submission queues25and executes a process according to the fetched command for the NAND flash memory4. The memory controller13includes a front-end unit16and a back-end unit17.

The front-end unit16controls communication between the host2and the memory system3. By the communication, for example, commands and data are transmitted from the host2to the memory system3.

The front-end unit16controls acquisition (i.e., fetch) of commands from the plurality of submission queues25. Specifically, the front-end unit16selects, from the plurality of submission queues25, a target submission queue25from which a command is to be fetched (hereinafter also referred to as a fetch target submission queue25). The front-end unit16fetches a command in order from the head of the fetch target submission queue25. The command to be fetched is, for example, an input/output (I/O) command or a control command. The I/O command may be a write command or a read command. The control command may be an unmap command (trim command) or a flush command.

The front-end unit16may generate one or more requests (NAND requests) to the NAND flash memory4on the basis of a command fetched from a submission queue25. The front-end unit16stores the generated NAND requests in an intermediate queue15corresponding to a group to which the submission queue25belongs.

Specifically, for example, when a read command has been fetched from a submission queue25, the front-end unit16generates one or more NAND requests to the NAND flash memory4, based on the read command. Each of the NAND requests generated based on the read command is, for example, a data read request to the NAND flash memory4. The data read request to the NAND flash memory4is also simply referred to as a read request. For example, in a case where the size of data read in one data read operation from the NAND flash memory4(more specifically, the NAND memory chip41) is 16 KB, the read request is a request to read data of 16 KB. The size of data read in one data read operation from the NAND memory chip41is also referred to as a read unit. The read unit is equivalent to, for example, the size of data of one page.

In addition, for example, when a write command has been fetched from a submission queue25, the front-end unit16generates one or more NAND requests to the NAND flash memory4, based on the write command. Each of the NAND requests generated based on the write command is, for example, a data write request to the NAND flash memory4. The data write request to the NAND flash memory4is also simply referred to as a write request. For example, in a case where the size of data written in one data write operation to the NAND flash memory4(more specifically, the NAND memory chip41) is 192 KB, the write request is a request to write data of 192 KB. The size of data written in one data write operation to the NAND memory chip41is also referred to as a write unit. The write unit is equivalent to, for example, an integer multiple of the size of data of one page.

The back-end unit17electrically connects the controller6and the NAND flash memory4. The back-end unit17conforms to an interface standard such as a toggle double data rate (DDR) and an open NAND flash interface (ONFI).

The back-end unit17functions as a memory control circuit configured to control the NAND flash memory4. The back-end unit17may be connected to the NAND memory chips41via multiple channels respectively. By operating the NAND memory chips41in parallel, it is possible to broaden an access bandwidth between the controller6and the NAND flash memory4.

The back-end unit17performs, for the NAND flash memory4, a process corresponding to a NAND request stored in each of the intermediate queues15. Specifically, the back-end unit17acquires a NAND request from the intermediate queues15so that, for example, the NAND flash memory4is used evenly between the namespaces. The back-end unit17may acquire a NAND request from the intermediate queues15so that the NAND flash memory4is used evenly between groups associated with one namespace. The back-end unit17performs, for the NAND flash memory4, a process corresponding to the acquired NAND request.

Here, an example of the configurations of the group management table51, the group-NAND use time management table52, and the NS-NAND use time management table53will be described.

FIG.3illustrates an example of the configuration of the group management table51. The group management table51includes entries that correspond to groups, respectively. The number of the entries included in the group management table51corresponds to, for example, the sum of the numbers of groups that are capable of being associated with each of the namespaces. For example, in a case where the memory system3provides the host2with two namespaces and four groups are capable of being associated with each of the two namespaces, the group management table51includes eight entries. Each of the entries includes, for example, a group field, a namespace field (NS field), an I/O type field, a submission queue field (SQ field), a weight field, and a priority field.

The group field indicates identification information of a corresponding group.

The NS field indicates identification information of a namespace (i.e., namespace ID) with which the corresponding group is associated.

The I/O type field indicates an I/O type of the corresponding group. The I/O type represents the type of a command stored in a submission queue25that belongs to the corresponding group. In other words, the I/O type represents a use of the submission queue25that belongs to the corresponding group. As the I/O type, “write” or “read” is set, for example. When “write” is set as the I/O type, the submission queue25that belongs to the corresponding group is a submission queue25used for storing write commands (that is, a submission queue25for write). When “read” is set as the I/O type, the submission queue25that belongs to the corresponding group is a submission queue25used for storing read commands (that is, a submission queue25for read). When a target to be managed as the corresponding group has not been determined (for example, when an I/O type of the group has not been determined), for example, “N/A” is set in the I/O type field.

The SQ field indicates identification information of a submission queue25that belongs to the corresponding group. The SQ field indicates, for example, one or more pieces of identification information that are assigned to one or more submission queues25, respectively. When a target to be managed as the corresponding group has not been determined (for example, when the host2has not notified identification information of a submission queue25that belongs to the group), for example, “N/A” is set in the SQ field.

The weight field indicates a weight W used for the corresponding group. The weight W is a coefficient used for calculating a NAND use time of the corresponding group. For example, a larger value of the weight W is set for a group to which a submission queue25storing a command to be more preferentially processed belongs. A value set as the weight W is, for example, any value between 1 and 256 inclusive. When a target to be managed as the corresponding group has not been determined (for example, when a weight W of the group has not been determined), “N/A” is set is the weight field.

The priority field indicates a priority P of fetch from a submission queue25that belongs to the corresponding group. As the priority P of a group increases, a frequency at which a submission queue25that belongs to the group is selected as a fetch target increases. The priority field may indicate whether fetching of a command from a submission queue25that belongs to the corresponding group is enabled or not. In this case, when fetching of a command from a submission queue25that belongs to the corresponding group is enabled, for example, “enable” is set in the priority field. Further, when fetching of a command from a submission queue25that belongs to the corresponding group is disabled, for example, “disable” is set in the priority field. When a target to be managed as the corresponding group has not been determined (for example, when the priority P of the group has not been determined), for example, “N/A” is set in the priority field.

In the example illustrated inFIG.3, a group “10” is associated with a namespace “1”. The I/O type of the group “10” is “write”. Submission queues25that belong to the group “10” are four submission queues25that have pieces of identification information “0”, “1”, “2”, and “3”, respectively. A weight used for the group “10” is W10. A priority of fetch from the submission queues25that belong to the group “10” is P10.

For example, a group “11” is associated with the namespace “1”. The I/O type of the group “11” is “read”. Submission queues25that belong to the group “11” are four submission queues25that have pieces of identification information “4”, “5”, “6”, and “7”, respectively. A weight used for the group “11” is W11. A priority of fetch from the submission queues25that belong to the group “11” is P11.

For example, both a group “12” and a group “13” are associated with the namespace “1”. In each of the fields other than the NS fields of the group “12” and the group “13”, “N/A” is set. Therefore, none of targets to be managed as the group “12” and the group “13” has been specified.

Both of a group “21” and a group “22” are set to a namespace “2” and the I/O type “read”. In that case, the controller6can manage the groups (more specifically, submission queues25that belong to each of the groups) set to the same namespace and the same I/O type in different weights W and different priorities P.

Information managed by using the group management table51is based on, for example, information notified to the memory system3by the host2. Alternatively, an interface for the host2to change contents of the group management table51may be provided.

FIG.4illustrates an example of the configuration of the group-NAND use time management table52. The group-NAND use time management table52includes entries that correspond to groups, respectively. Each of the entries includes a group field and a NAND use time field.

The group field indicates identification information of a corresponding group.

The NAND use time field indicates use amount of the NAND flash memory4by the corresponding group. This use amount is an index indicative of the cumulative sum of processing amounts executed in the NAND flash memory4in accordance with one or more commands fetched from one or more submission queues25that belong to the corresponding group. The NAND use time field may indicate a value obtained by dividing the use amount by the weight W that is used for the corresponding group. Every time a command is fetched from any of the submission queues25that belong to the corresponding group, the value indicated in the NAND use time field is updated by using a predicted use amount of the NAND flash memory4in accordance with the command (or by using a value obtained by dividing the predicted use amount by the weight W).

More specifically, this use amount is represented by, for example, a use time VT of the NAND flash memory4of the corresponding group (hereinafter also referred to as NAND use time VT). The NAND use time VT is the cumulative sum of durations for which the NAND flash memory4is used in accordance with commands fetched from the submission queues25that belong to the corresponding group, from a certain time. The NAND use time field may indicate a value obtained by dividing the NAND use time by the weight W that is used for the corresponding group. Every time a command is fetched from any of the submission queues25that belong to the corresponding group, the value indicated in the NAND use time field is updated by using a predicted use time of the NAND flash memory4in accordance with the command (or by using a value obtained by dividing the predicted use time by the weight W).

Note that when a target to be managed as the corresponding group has not been determined in the group management table51, “N/A” is set in the NAND use time field of the group-NAND use time management table52.

In the example illustrated inFIG.4, the NAND use time of the group “10” is, for example, VT10. The NAND use time of the group “11” is, for example, VT11. The NAND use time of the group “20” is, for example, VT20. The NAND use time of the group “21” is, for example, VT21. The NAND use time of the group “22” is, for example, VT22. In addition, the NAND use time of each of the group “12”, the group “13”, and a group “23” is “N/A”. This means that none of targets to be managed as the group “12”, the group “13”, and the group “23” has been specified.

FIG.5illustrates an example of the configuration of the NS-NAND use time management table53. The NS-NAND use time management table53includes entries that correspond to namespaces, respectively. The number of the entries included in the NS-NAND use time management table53corresponds to, for example, the number of namespaces with which the memory system3provides the host2. For example, when the memory system3provides the host2with two namespaces, the NS-NAND use time management table53includes two entries. Each of the entries includes, for example, a namespace field (NS field) and a NAND use time field.

The NS field indicates identification information (namespace ID) of a corresponding namespace.

The NAND use time field indicates a use amount of the NAND flash memory4used by the corresponding namespace. This use amount is an index indicative of the cumulative sum of processing amounts executed in the NAND flash memory4in accordance with one or more commands fetched from one or more submission queues25allocated to the corresponding namespace. Every time a command is fetched from any of the submission queues25allocated to the namespace, the value indicated in the NAND use time field is updated by using a predicted use amount of the NAND flash memory4in accordance with the command (or by using a value obtained by dividing the predicted use amount by the weight W).

More specifically, this use amount is represented by a use time NVT of the NAND flash memory4of the corresponding namespace (NAND use time NVT). The NAND use time NVT is the cumulative sum of durations for which the NAND flash memory4is used in accordance with commands fetched from the submission queues25allocated to the corresponding namespace, from a certain time. Each of the submission queues25allocated to the namespace belongs to any of the groups associated with the namespace. Therefore, the NAND use time NVT of a namespace is the sum of the NAND use times VT of all the groups associated with the namespace. The NAND use time NVT of the namespace is updated, for example, every time the NAND use time VT of any one of the groups associated with the namespace is updated.

Hereinafter, a case where the use amount of the NAND flash memory4is represented by a use time will be mainly described. However, the use amount of the NAND flash memory4may be replaced with various indices indicative of a processing amount in the NAND flash memory4.

In the example illustrated inFIG.5, the NAND use time of the namespace “1” is, for example, NVT1. When the group management table51illustrated inFIG.3and the group-NAND use time management table52illustrated inFIG.4are used, the groups “10”, “11”, “12”, and “13” belong to the namespace “1”. Since “N/A” is set as the NAND use time VT of each of the groups “12” and “13”, the NAND use time NVT1 of the namespace “1” is obtained by calculating the sum of the NAND use time VT10 of the group “10” and the NAND use time VT11 of the group “11”.

In addition, the NAND use time of the namespace “2” is NVT2. In a case where the group management table51illustrated inFIG.3and the groupNAND use time management table52illustrated inFIG.4are used, the groups “20”, “21”, “22”, and “23” belong to the namespace “2”. Since “N/A” is set as the NAND use time VT of the group “23”, the NAND use time NVT2 of the namespace “2” is obtained by calculating the sum of the NAND use time VT20 of the group “20”, the NAND use time VT21 of the group “21”, and the NAND use time VT22 of the group “22”.

Here, an evenness of use of the NAND flash memory4between specific management units will be explained. It is requested for the memory system3that the NAND flash memory4be used evenly between the specific management units. The specific management units are, for example, submission queues25, groups of submission queues25, or namespaces.

First, a case where a NAND flash memory in a memory system3C according to a comparative example is used unevenly between submission queues will be described below.

FIG.6illustrates an example in which the NAND flash memory is used unevenly between two submission queues, in the memory system3C of the comparative example. The two submission queues are a first submission queue25C-1and a second submission queue25C-2. It is assumed that the size of data read in one data read operation on the NAND memory (read unit) is 16 KB.

The first submission queue25C-1is used for a workload that includes read commands each requesting to read user data of 64 KB (hereinafter referred to as read commands of 64 KB). The read commands of 64 KB are continuously stored in the first submission queue25C-1. Specifically, read commands of 64 KB C11, C12, C13, C14, C15, . . . , are stored in the first submission queue25C-1in this order.

The second submission queue25C-2is used for a workload that includes read command each requesting to read user data of 16 KB (hereinafter referred to as read commands of 16 KB). The read commands of 16 KB are continuously stored in the second submission queue25C-2. Specifically, read commands of 16 KB C21, C22, C23, C24, C25, . . . , are stored in the second submission queue25C-2in this order.

In the example illustrated inFIG.6, four read requests that are based on a read command of 64 KB fetched from the first submission queue25C-1and one read request that is based on a read command of 16 KB fetched from the second submission queue25C-2are alternately issued to the NAND flash memory.

Specifically, first, four read requests R11, R12, R13, and R14that are based on the read command C11of 64 KB fetched from the first submission queue25C-1are issued to the NAND flash memory. A read request R21that is based on the read command C21of 16 KB fetched from the second submission queue25C-2is issued to the NAND flash memory. Four read requests R15, R16, R17, and R18that are based on the read command C12of 64 KB fetched from the first submission queue25C-1are issued to the NAND flash memory. Then, a read request R22that is based on the read command C22of 16 KB fetched from the second submission queue25C-2is issued to the NAND flash memory.

The read requests R11to R18correspond to the read commands fetched from the first submission queue25C-1. Therefore, a NAND use time of the first submission queue25C-1corresponds to time required for read operations in the NAND flash memory in accordance with the eight read requests R11to R18.

The read requests R21and R22correspond to the read commands fetched from the second submission queue25C-2. Therefore, a NAND use time of the second submission queue25C-2corresponds to time required for read operations in the NAND flash memory in accordance with the two read requests R21and R22.

Thus, in the example illustrated inFIG.6, the NAND use time of the first submission queue25C-1is longer than the NAND use time of the second submission queue25C-2. Therefore, in the memory system3C of the comparative example, the NAND flash memory is used unevenly between the first submission queue25C-1and the second submission queue25C-2.

The case where the read commands are stored in the submission queues25C-1and25C-2is described with reference toFIG.6. Similarly, in a case where write commands are stored in the submission queues25C-1and25C-2, the NAND flash memory may be used unevenly between the first submission queue25C-1and the second submission queue25C-2.

In contrast, a case where the NAND flash memory4in the memory system3of the present embodiment is used evenly between the submission queues25will be explained.

FIG.7illustrates an example in which the NAND flash memory4in the memory system3is used evenly between two submission queues25. The two submission queues25are a first submission queue25-1and a second submission queue25-2. It is assumed that the size of data read in one data read operation on the NAND memory4(read unit) is 16 KB.

The read commands C11, C12, C13, C14, C15, . . . , stored in the first submission queue25-1and the read commands C21, C22, C23, C24, C25, . . . , stored in the second submission queue25-2are the same as those in the comparative example described with reference toFIG.6.

In the example illustrated inFIG.7, one read request of four read requests that are based on a read command of 64 KB fetched from the first submission queue25-1and one read request that is based on a read command of 16 KB fetched from the second submission queue25-2are alternately issued to the NAND flash memory4.

Specifically, first, the first read request R11among four read requests R11, R12, R13, and R14that are based on the read command C11of 64 KB fetched from the first submission queue25-1is issued to the NAND flash memory4. A read request R21that is based on the read command C21of 16 KB fetched from the second submission queue25-2is issued to the NAND flash memory4. The second read request R12among the four read requests R11, R12, R13, and R14is issued to the NAND flash memory4. A read request R22that is based on the read command C22of 16 KB fetched from the second submission queue25-2is issued to the NAND flash memory4. The third read request R13among the four read requests R11, R12, R13, and R14is issued to the NAND flash memory4. A read request R23that is based on the read command C23of 16 KB fetched from the second submission queue25-2is issued to the NAND flash memory4. The fourth read request R14among the four read requests R11, R12, R13, and R14is issued to the NAND flash memory4. A read request R24that is based on the read command C24of 16 KB fetched from the second submission queue25-2is issued to the NAND flash memory4. The first read request R15among four read requests that are based on the read command C12of 64 KB fetched from the first submission queue25-1is issued to the NAND flash memory4. Then, a read request R25that is based on the read command C25of 16 KB fetched from the second submission queue25-2is issued to the NAND flash memory4.

The read requests R11, R12, R13, R14, and R15correspond to the read commands fetched from the first submission queue25-1. Therefore, the NAND use time of the first submission queue25-1corresponds to time required for read operations in the NAND flash memory4in accordance with the five read requests R11, R12, R13, R14, and R15.

The read requests R21, R22, R23, R24, and R25correspond to the read commands fetched from the second submission queue25-2. Therefore, the NAND use time of the second submission queue25-2corresponds to time required for read operations in the NAND flash memory4in accordance with the five read requests R21, R22, R23, R24, and R25.

Thus, in the example illustrated inFIG.7, the NAND use time of the first submission queue25-1is equal to the NAND use time of the second submission queue25-2. Therefore, in the memory system3, the NAND flash memory4can be used evenly between the first submission queue25-1and the second submission queue25-2.

The case where the read commands are stored in the submission queues25-1and25-2is described with reference toFIG.7. Similarly, in a case where write commands are stored in the submission queues25-1and25-2, the NAND flash memory can be used evenly between the first submission queue25-1and the second submission queue25-2.

With reference toFIG.8toFIG.10, a case where the NAND flash memory is used unevenly between the management units due to a configuration and operations of the memory system3C according to the comparative example will be further explained.

FIG.8illustrates the configuration of the memory system3C according to the comparative example. The memory system3C includes a controller6C and a NAND flash memory4C.

The controller6C is configured to fetch a command from each of a plurality of submission queues25C and executes a process for the NAND flash memory4C in accordance with the fetched command. The controller6C includes a command processing module32C, a plurality of intermediate queues15C, and a scheduling module33C.

Here, the plurality of intermediate queues15C are four intermediate queues15C-1,15C-2,15C-3, and15C-4. The four intermediate queues15C-1,15C-2,15C-3, and15C-4correspond to four management units, respectively.

The plurality of submission queues25C are four submission queues25C-1,25C-2,25C-3, and25C-4. The four submission queues25C-1,25C-2,25C-3, and25C-4correspond to the four management units, respectively.

The command processing module32C selects a fetch target submission queue25C from the submission queues25C-1,25C-2,25C-3, and25C-4. The command processing module32C uses round robin as an arbitration mechanism for the submission queues25C-1,25C-2,25C-3, and25C-4. In other words, the command processing module32C selects the submission queues25C-1,25C-2,25C-3, and25C-4one by one in a specific order.

The command processing module32C fetches a command from the selected submission queue25C. The command processing module32C generates one or more NAND requests to the NAND flash memory4C, based on the fetched command. The command processing module32C stores the one or more NAND requests in a corresponding intermediate queue15C.

The scheduling module33C schedules processes corresponding to NAND requests stored in the intermediate queues15C-1,15C-2,15C-3, and15C-4. Specifically, the scheduling module33C acquires a NAND request of a processing target from the intermediate queues15C-1,15C-2,15C-3, and15C-4so that the NAND flash memory4C is used evenly between the management units. The scheduling module33C executes a process for the NAND flash memory4C, based on the acquired NAND request. Note that in a case where the NAND flash memory4C includes a plurality of NAND memory chips, the scheduling module33C executes the scheduling per NAND memory chip.

In order for the scheduling module33C to acquire a NAND request from the intermediate queues15C-1,15C-2,15C-3, and15C-4so that the NAND flash memory4C is used evenly between the management units, a sufficient number of commands have to be managed in the controller6C. More specifically, for example, a sufficient number of the NAND requests have to be stored in each of the intermediate queues15C-1,15C-2,15C-3, and15C-4.

In order to increase the number of commands that can be managed by the controller6C, the amount of hardware resources (HW resources) of the controller6C for managing commands needs to be increased. The HW resources include, for example, a memory (for example, RAM) that stores information on commands, such as the intermediate queues15C. However, an increase in the HW resources leads to an increase in cost of the memory system3C. If, for example, a relatively small memory is used to avoid the increase in cost of the memory system3C, the controller6C may not be able to manage the sufficient number of commands for the upper limit of commands that are required to be simultaneously managed based on a specification of the controller6C (for example, NVMe).

FIG.9illustrates a case where the controller6C can manage sufficient number of commands for using the NAND flash memory4C evenly between management units, in the memory system3C of the comparative example. In the controller6C, sufficient number of NAND requests for using the NAND flash memory4C evenly between the management units are stored in the intermediate queues15C-1,15C-2,15C-3, and15C-4. Specifically, the intermediate queue15C-1stores four NAND requests. The intermediate queue15C-2stores two NAND requests. The intermediate queue15C-3stores one NAND request. The intermediate queue15C-4stores three NAND requests.

In this case, the scheduling module33C can acquire a NAND request from the intermediate queue15C that corresponds to any one of the four management units. Therefore, the scheduling module33C can schedule execution of processes in accordance with the NAND requests stored in the intermediate queues15C-1,15C-2,15C-3, and15C-4so that the NAND flash memory4C is used evenly among the management units.

Specifically, for example, the scheduling module33C acquires NAND requests from the respective intermediate queues15C-1,15C-2,15C-3, and15C-4in order and executes processes for the NAND flash memory4C on the basis of the acquired NAND requests. Thus, the memory system3C can use the NAND flash memory4C evenly among the management units.

In contrast,FIG.10illustrates t a case where the controller6C cannot manage sufficient number of commands for using the NAND flash memory4C evenly between the management units, in the memory system3C of the comparative example. In the controller6C, sufficient number of NAND requests for using the NAND flash memory4C evenly between the management units are not stored in the intermediate queues15C-1,15C-2,15C-3, and15C-4. Specifically, the intermediate queue15C-1stores four NAND requests. The intermediate queue15C-2stores two NAND requests. However, neither the intermediate queue15C-3nor the intermediate queue15C-4stores any NAND requests.

In this case, the scheduling module33C can acquire the NAND requests from the respective intermediate queues15C-1and15C-2, but cannot acquire a NAND request from the intermediate queue15C-3or15C-4. This prevents the scheduling module33C from scheduling execution of processes in accordance with the NAND requests stored in the intermediate queues15C-1,15C-2,15C-3, and15C-4for using the NAND flash memory4C evenly among the management units.

Specifically, for example, the scheduling module33C acquires the NAND requests from the respective intermediate queues15C-1and15C-2in order and executes processes for the NAND flash memory4C on the basis of the acquired NAND requests. However, since the scheduling module33C cannot acquire any NAND request from the intermediate queue15C-3or15C-4, the scheduling module33C cannot execute a corresponding process for the NAND flash memory4C. Accordingly, the NAND flash memory4C is used for the two management units corresponding to the respective intermediate queues15C-1and15C-2, but the NAND flash memory4C is not used for the two management units corresponding to the respective intermediate queues15C-3and15C-4. Thus, in the memory system3C, the NAND flash memory4C is used unevenly among the management units.

As described above, the controller6C of the memory system3C according to the comparative example may not be able to manage sufficient number of commands for using the NAND flash memory4C evenly between the management units in some cases. Therefore, in the memory system3C, the NAND flash memory4C may be used unevenly between the management units.

In contrast, in the memory system3according to the present embodiment, the controller6is configured to manage sufficient number of commands for using the NAND flash memory4evenly between management units. Specifically, the controller6manages a plurality of use amounts of the NAND flash memory4(for example, a plurality of NAND use times) that correspond to a plurality of namespaces, respectively. When having acquired a command from a submission queue25, the controller6calculates a predicted use amount of the NAND flash memory4in accordance with the acquired command (hereinafter simply referred to as a predicted use amount). The controller6updates a use amount corresponding to a namespace to which the submission queue25is allocated, by using the calculated predicted use amount. Then, the controller6selects a submission queue25from which a command is to be fetched among the plurality of submission queues25by using the plurality of use amounts that correspond to the plurality of namespaces, respectively.

The controller6selects a submission queue25(or increases selection frequency of a submission queue25) that is allocated to a namespace having small use amount, to fetch a command therefrom. Thus, the controller6can manage sufficient number of commands with respect to the namespace for using the NAND flash memory4evenly between the namespaces. Then, the controller6can schedule issuance of commands (more specifically, NAND requests corresponding to the commands) so that the NAND flash memory4is used evenly between the namespaces. Therefore, the memory system3can improve an evenness of use of the NAND flash memory4between the namespaces.

Furthermore, the controller6does not select a submission queue25(or decreases selection frequency of a submission queue25) that is allocated to a namespace having a large use amount, to fetch a command therefrom. This prevents the controller6from excessively fetching commands with respect to the namespace and wasting resources for managing the commands. Therefore, it is possible to reduce resources of the memory system3for managing commands, for example, compared to the memory system3C of the comparative example.

FIG.11illustrates an example of a specific configuration of the controller6of the memory system3.

The controller6is configured to fetch a command from each of the plurality of submission queues25and execute a process for the NAND flash memory4in accordance with the fetched command. In addition, the controller6controls fetching of commands from the plurality of submission queues25so that the NAND flash memory4is used evenly between the namespaces.

In the controller6, the front-end unit16includes a fetch scheduling module31and a command processing module32. The back-end unit17includes a NAND scheduling module33.

Here, a case where the plurality of submission queues25include submission queues25-0,25-1,25-4,25-5,25-8,25-9,25-12, and25-13, and the plurality of intermediate queues15include intermediate queues15-1,15-2,15-3,15-4,15-5, and15-6will be explained. The number of the submission queues25and the number of the intermediate queues15are freely determined.

The submission queues25-0and25-1are used for storing write commands. The submission queues25-0and25-1belong to a group G10. In other words, the I/O type of the group G10is “write”.

The submission queues25-4and25-5are used for storing read commands. The submission queues25-4and25-5belong to a group G11. In other words, the I/O type of the group G11is “read”.

The submission queues25-0,25-1,25-4, and25-5are allocated to a first namespace NS1. In other words, the first namespace NS1is associated with the groups G10and G11.

The submission queues25-8and25-9are used for storing write commands. The submission queues25-8and25-9belong to a group G20. In other words, the I/O type of the group G20is “write”.

The submission queues25-12and25-13are used for storing read commands. The submission queues25-12and25-13belong to a group G21. In other words, the I/O type of the group G21is “read”.

The submission queues25-8,25-9,25-12, and25-13are allocated to a second namespace NS2. In other words, the second namespace NS2is associated with the groups G20and G21.

The groups G10, G11, G20, and G21correspond to the entries of the four groups “10”, “11”, “20”, and “21”, respectively, in the group management table51described above with reference toFIG.3.

The intermediate queues15-1,15-2,15-3,15-4,15-5, and15-6correspond to six management units, respectively. Each of the management units is, for example, a group. Specifically, for example, the intermediate queue15-1corresponds to the group G10. The intermediate queue15-2corresponds to the group G11. The intermediate queue15-3corresponds to the group G20. The intermediate queue15-4corresponds to the group G21. Similarly, each of the intermediate queues15-5and15-6corresponds to one group (not illustrated).

Since the I/O type of the group G10is “write”, the intermediate queue15-1is used for storing write requests. Since the I/O type of the group G11is “read”, the intermediate queue15-2is used for storing read requests. Since the I/O type of the group G20is “write”, the intermediate queue15-3is used for storing write requests. Since the I/O type of the group G21is “read”, the intermediate queue15-4is used for storing read requests.

The fetch scheduling module31schedules the fetching of commands from the plurality of submission queues25. Specifically, for example, the fetch scheduling module31manages a priority P for selecting each of the plurality of submission queues25as the fetch target submission queue25. The fetch scheduling module31manages the priority P of each of the submission queues25, for example, per management unit. In a case where the management unit is a group, the priority P for selecting each of one or more submission queues25that belongs to the group as the fetch target submission queue25, is set for the group. For the management of the priority P, for example, the group management table51is used.

Based on the priority P corresponding to each of the plurality of submission queues25(for example, the priority P set to the group to which each of the submission queues25belongs), the fetch scheduling module31more frequently selects a submission queue25that has a higher priority P as the fetch target submission queue25. The fetch scheduling module31fetches a command from the fetch target submission queue25. The fetch scheduling module31transmits the fetched command to the command processing module32.

In addition, the fetch scheduling module31manages a NAND use time VT of each of the groups G10, G11, G20, and G22and a NAND use time NVT of each of the namespaces NS1and NS2. For the management of the NAND use time VT of each of the groups G10, G11, G20, and G22, for example, the group-NAND use time management table52is used. For the management of the NAND use time NVT of each of the namespaces NS1and NS2, for example, the NS-NAND use time management table53is used.

The management of the NAND use time VT of each of the groups will be described in detail.

Based on a fetched command, the fetch scheduling module31updates a NAND use time VT of a group to which a submission queue25from which the command has been fetched belongs (hereinafter referred to as a belonging group).

Specifically, the fetch scheduling module31calculates a predicted use time of the NAND flash memory4in accordance with the fetched command. The predicted use time of the NAND flash memory4in accordance with the fetched commands is also referred to as a predicted NAND use time.

The fetch scheduling module31updates the NAND use time VT of the belonging group in the group-NAND use time management table52by using the predicted NAND use time, which has been calculated. For example, the fetch scheduling module31adds the predicted NAND use time to the NAND use time VT of the belonging group in the group-NAND use time management table52. Alternatively, the fetch scheduling module31adds, to the NAND use time VT of the belonging group in the group-NAND use time management table52, a quotient that is obtained by dividing the predicted NAND use time by a weight W that is used for the belonging group.

An example of a method of calculating the predicted NAND use time will be described with reference toFIG.12andFIG.13. Here, it is assumed that a write mode illustrated inFIG.12is used.

FIG.12illustrates an example of a write mode for the NAND flash memory4. A data write operation on one NAND memory chip41is executed for a single block, or for a plurality of blocks that are included in a plurality of planes42, respectively, in the NAND memory chip41. Executing a data write operation for the blocks in the respective planes42is also referred to as multi-plane program. In a case where the NAND memory chip41includes the plurality of planes42, the multi-plane program is used in consideration of the programming performance, for example.

InFIG.12, an example in which data is written, in the TLC mode, into four blocks70,71,72,73that are included in four planes42-0,42-1,42-2, and42-3, respectively, in one data write operation on the NAND memory chip41is illustrated. When the data is programed into each of the four blocks70,71,72, and73in the TLC mode, data of three pages (lower page data, middle page data, and upper page data) is transferred to each of the four planes42-0,42-1,42-2, and42-3. The transferred data of three pages is written into a corresponding block in the TLC mode. Here, it is assumed that the size of data of one page is 16 KB.

In this case, in the data write operation on the NAND memory chip41, data of 192 KB (=16 KB×3 pages×4 blocks) is written. In other words, the size of data that can be written into the NAND memory chip41in the data write operation (write unit) is 192 KB.

In addition, in one data read operation on the NAND memory chip41, data of 16 KB (i.e., data of one page) is read. In other words, the size of data that can be read from the NAND memory chip41in the data read operation (read unit) is 16 KB.

When having fetched a command from the submission queues25, the fetch scheduling module31calculates the number of NAND requests to be issued to the NAND memory chip41in accordance with the command.

For example, when having fetched a read command from the submission queues25, the fetch scheduling module31calculates the number Nr of read requests issued to the NAND memory chip41in accordance with the read command. The size of user data requested to be read in accordance with the read command may be smaller than the read unit or may be larger than the read unit. The fetch scheduling module31estimates the number Nr of read requests to be issued to the NAND memory chip41, based on the size of user data requested to be read in accordance with the read command and the read unit. The fetch scheduling module31determines a predicted NAND use time corresponding to the read command, based on the estimated number Nr of read requests. Specifically, the fetch scheduling module31calculates the product of the estimated number Nr of read requests and a read time tR, as the predicted NAND use time corresponding to the read command. The read time tR is time required for a read operation in the NAND flash memory4in accordance with one read request. The read operation is an operation of reading data from the NAND flash memory4(more specifically, from the memory cell array421).

In addition, for example, when having fetched a write command from the submission queues25, the fetch scheduling module31calculates the number Nw of write requests to be issued to the NAND memory chip41in accordance with the write command. The size of user data requested to be written in accordance with the write command may be smaller than the write unit or may be larger than the write unit. The fetch scheduling module31estimates the number Nw of write requests to be issued to the NAND memory chip41, based on the size of the user data requested to be written in accordance with the write command and the write unit. The fetch scheduling module31determines a predicted NAND use time corresponding to the write command, based on the estimated number Nw of write requests. Specifically, the fetch scheduling module31calculates the product of the estimated number Nw of write requests and a program time tProg, as the predicted NAND use time corresponding to the write command. The program time tProg is time required for a program operation in the NAND flash memory4in accordance with one write request. The program operation is an operation of writing (programming) data into the NAND flash memory4. The program time tProg is, for example, longer than the read time tR.

FIG.13illustrates an example of relationships between commands and predicted NAND use times. More specifically,FIG.13illustrates examples of a NAND access size, the number of NAND requests, and a predicted NAND use time that correspond to a command.

The NAND access size is the size of data in the NAND flash memory4to be accessed in accordance with a corresponding command.

In a case where the command is a read command, the NAND access size is the size of user data read from the NAND flash memory4in accordance with the read command. Data read from the NAND flash memory4in one data read operation is data of the read unit. Therefore, the NAND access size in accordance with the read command is Nr times of the read unit. Nr corresponds to the number of read requests generated based on the read command. Nr is an integer of one or larger.

In a case where the command is a write command, the NAND access size is the size of user data written into the NAND flash memory4in accordance with the write command. Data written into the NAND flash memory4in one data write operation is data of the write unit. When the size of user data to be written in accordance with the write command is smaller than the write unit, the user data is written into the NAND flash memory4together with data to be written in accordance with one or more other write commands, as data of the write unit. Thus, when user data to be written in accordance with one or more write commands has reached the write unit, one write request to write the user data of the write unit into the NAND flash memory4is generated.

The number of NAND requests is the number of NAND requests generated based on the corresponding command.

In a case where the command is a read command, the number of NAND requests indicates the number Nr of read requests that are generated based on the read command. One read request requests the NAND flash memory4to read user data of the read unit.

In a case where the command is a write command, the number of NAND requests indicates the number Nw of write requests that are generated based on the write command. One write request requests the NAND flash memory4to write user data of the write unit. The number Nw of write requests corresponding to the write command is indicated by a ratio of the size of user data to be written in accordance with the write command to the write unit.

The predicted NAND use time is a duration for which the NAND flash memory4is predicted to be used in accordance with the corresponding command. In a case where the command is a read command, the product of the number of NAND requests corresponding to the read command (i.e., the number Nr of read requests) and the read time tR is calculated as the predicted NAND use time, for example. In a case where the command is a write command, the product of the number of NAND requests corresponding to the write command (i.e., the number Nw of write requests) and the program time tProg is calculated as the predicted NAND use time, for example.

The examples of the commands illustrated inFIG.13will be specifically described. Here, it is assumed that the read time tR is 50 microseconds (μs) and the program time tProg is 1 millisecond (ms). In addition, as in the example illustrated inFIG.12, it is assumed that the read unit is 16 KB and the write unit is 192 KB.

In the case of a read command to read user data of 4 KB, the user data of 4 KB requested to be read is smaller than the read unit (16 KB). Accordingly, the NAND access size is 16 KB. Since the NAND flash memory4is requested to read data of the read unit, the number Nr of NAND requests is one. Therefore, the predicted NAND use time is 50 ρs (=tR×Nr=50 μs×1).

In the case of a read command to read user data of 16 KB, the user data of 16 KB requested to be read is equivalent to the read unit (16 KB). Accordingly, the NAND access size is 16 KB. Since the NAND flash memory4is requested to read data of the read unit, the number Nr of NAND requests is one. Therefore, the predicted NAND use time is 50 μs (50 μs×1).

In the case of a read command to read user data of 128 KB, the user data of 128 KB requested to be read is eight times the read unit (16 KB). Accordingly, the NAND access size is 16 KB×8. Since the NAND flash memory4is requested to read data of eight times the read unit, the number Nr of NAND requests is eight. Therefore, the predicted NAND use time is 400 μs (=50 μs×8).

In the case of a write command to write user data of 16 KB, the user data of 16 KB requested to be written is smaller than the write unit (192 KB). Accordingly, the NAND access size is 16 KB. This means that the user data of 16 KB, together with user data of 176 KB to be written in accordance with one or more other write commands, is written into the NAND flash memory4as user data of 192 KB (write unit). Thus, a write request corresponding to the write command is equivalent to 1/12 (=16/192) of one write request that requests writing data of the write unit. That is, the number Nw of NAND requests is 1/12. Therefore, the predicted NAND use time is 84 μs (=tProg×Nw=1000 μs×1/12).

In the case of a write command to write user data of 128 KB, the user data of 128 KB requested to be written is smaller than the write unit (192 KB). Accordingly, the NAND access size is 128 KB. This means that the user data of 128 KB, together with user data of 64 KB to be written in accordance with one or more other write commands, is written to the NAND flash memory4as user data of 192 KB (write unit). Thus, a write request corresponding to the write command is equivalent to 2/3 (=128/192) of one write request that requests writing data of the write unit. That is, the number Nw of NAND requests is 2/3. Therefore, the predicted NAND use time is 667 μs (=1000 μs×2/3).

In the case of a write command to write user data of 192 KB, the user data of 192 KB requested to be written is equal to the write unit (192 KB). Accordingly, the NAND access size is 192 KB. A write request corresponding to the write command is one write request that requests writing data of the write unit. That is, the number Nw of NAND requests is one. Therefore, the predicted NAND use time is 1000 μs (1000 μs×1).

As described above, the fetch scheduling module31can estimate the number of NAND requests to be issued to the NAND memory chip41in accordance with a fetched command and calculate a predicted NAND use time corresponding to the command. The fetch scheduling module31updates the NAND use time VT of a belonging group by using the predicted NAND use time, thereby managing the NAND use time VT per group.

The description returns toFIG.11and the management of a NAND use time NVT of a namespace will be specifically described.

In response to the update of the NAND use time VT of a belonging group, the fetch scheduling module31updates a NAND use time NVT of a namespace with which the belonging group is associated. Specifically, for example, the fetch scheduling module31identifies the namespace with which the belonging group is associated (hereinafter referred to as a first target namespace) and identifies all groups associated with the first target namespace by using the group management table51. The fetch scheduling module31acquires NAND use times VT of all the identified groups by using the group-NAND use time management table52. The fetch scheduling module31replaces the NAND use time NVT of the first target namespace in the NS-NAND use time management table53with the sum of the acquired NAND use times VT of all the identified groups. Thus, the fetch scheduling module31can manage the NAND use time NVT per namespace.

The fetch scheduling module31selects a fetch target submission queue25by using at least one of the NAND use time VT per group and the NAND use time NVT per namespace. Specifically, the fetch scheduling module31controls the priority P for fetching a command from each of the plurality of submission queues25by using at least one of the NAND use time VT per group and the NAND use time NVT per namespace. Then, the fetch scheduling module31selects a fetch target submission queue25from the plurality of submission queues25, based on the priority P of each of the plurality of the submission queues25.

For example, the fetch scheduling module31sets the same priority P to one or more submission queues25that are allocated to one namespace. The fetch scheduling module31may further set the same priority P to one or more submission queues25that belong to one group. For example, in response to update of the NAND use time NVT of any of the namespaces, the fetch scheduling module31updates the priority P set for each of the plurality of groups.

Two specific examples of methods of controlling the priority P will be described.

(Method for Using NAND Flash Memory4Evenly Between Namespaces)

For example, when the NAND use time NVT of a namespace is relatively long among the NAND use times NVT of the plurality of namespaces, the fetch scheduling module31decreases the priority P of at least any of groups associated with the namespace by a first value. Note that when the NAND use time NVT of a namespace is relatively short, the fetch scheduling module31may increase the priority P of at least any of groups associated with the namespace by a second value. The second value may be equal to or different from the first value.

Specifically, the fetch scheduling module31calculates the average of the NAND use times NVT of all the plurality of namespaces (hereinafter also referred to as an NS average use time). When a value obtained by subtracting the NS average use time from the NAND use time NVT of a namespace is larger than a threshold value A, the fetch scheduling module31determines that the namespace has a relatively long NAND use time NVT. In this case, the fetch scheduling module31may determine that each of the namespaces, other than the namespace having the relatively long NAND use time NVT, has a relatively short NAND use times NVT.

Alternatively, when a value obtained by subtracting the NAND use time NVT of a namespace from the NS average use time is larger than a threshold value B, the fetch scheduling module31determines that the namespace has a relatively short NAND use time NVT. The threshold value B may be equal to or different from the threshold value A. In this case, the fetch scheduling module31may determine that each of the namespaces, other than the namespace having the relatively short NAND use time NVT, has a relatively long NAND use time NVT.

For example, the fetch scheduling module31may disable the fetching of a command from at least any of the submission queues25that are allocated to a namespace having a relatively long NAND use time NVT. In addition, for example, the fetch scheduling module31may enable the fetching of a command from at least any of the submission queues25allocated to a namespace having a relatively short NAND use time NVT. Note that each of the submission queues25allocated to a namespace is a submission queue25that belongs to one of groups associated with the namespace.

As described above, the fetch scheduling module31can decrease a frequency at which a command is fetched from a submission queue25allocated to a namespace having a relatively long NAND use time NVT. In addition, the fetch scheduling module31can increase a frequency at which a command is fetched from a submission queue25allocated to a namespace having a relatively short NAND use time NVT. Thus, for any of the plurality of namespaces, the controller6can manage sufficient number of commands (more specifically, NAND requests based on commands) for using the NAND flash memory4evenly between the namespaces. Therefore, the controller6can improve an evenness of use of the NAND flash memory4between the plurality of namespaces. In addition, the controller6can prevent commands corresponding to a specific namespace from being fetched excessively and then prevent a waste of resources of the memory system3.

(Method for Using NAND Flash Memory4Evenly Between Groups)

For example, when the NAND use time VT of a group is relatively long among the NAND use times VT of the plurality of groups which are associated with a namespace, the fetch scheduling module31decreases the priority P of the group by the first value. This namespace has, for example, a relatively long NAND use time NVT.

For example, when the NAND use time VT of a group is relatively short among the NAND use times VT of the plurality of groups which are associated with a namespace, the fetch scheduling module31may increase the priority P of the group by the second value. This namespace has, for example, a relatively long NAND use time NVT or a relatively short NAND use time NVT.

Specifically, the fetch scheduling module31calculates the average of the NAND use times VT of all of groups associated with a namespace (hereinafter also referred to as a group average use time). When a value obtained by subtracting the group average use time from the NAND use time VT of a group is larger than a threshold value C, the fetch scheduling module31determines that the group has a relatively long NAND use time VT. In this case, the fetch scheduling module31may determine that each of the groups, other than the group having the relatively long NAND use time VT, has a relatively short NAND use time VT.

Alternatively, when a value obtained by subtracting the NAND use time VT of a group from the group average use time is larger than a threshold value D, the fetch scheduling module31determines that the group has a relatively short NAND use time VT. The threshold value D may be equal to or different from the threshold value C. In this case, the fetch scheduling module31may determines that each of the groups, other than the group having the relatively short NAND use time VT, has a relatively long NAND use time VT.

For example, the fetch scheduling module31may identify a group having a relatively long NAND use time VT from the groups associated with a namespace and disable the fetching of a command from the submission queues25that belong to the identified group. For example, the fetch scheduling module31may identify a group having a relatively short NAND use time VT and enable the fetching of a command from the submission queues25that belong to the identified group.

As described above, the fetch scheduling module31can decrease a frequency at which a command is fetched from the submission queues25that belong to a group having a relatively long NAND use time VT. In addition, the fetch scheduling module31can increase a frequency at which a command is fetched from the submission queues25that belong to a group having a relatively short NAND use time VT. Thus, for any of the groups associated with a namespace, the controller6can manage sufficient number of commands for using the NAND flash memory4evenly between the groups. Therefore, the controller6can improve an evenness of use of the NAND flash memory4between the groups associated with the namespace. In addition, the controller6can prevent commands corresponding to a specific group from being fetched excessively and then prevent a waste of resources of the memory system3.

The command processing module32generates one or more NAND requests on the basis of a command received from the fetch scheduling module31and stores the one or more NAND requests in the intermediate queue15.

Specifically, for example, in a case where the received command is a read command, the command processing module32converts a logical address designated in the read command to a physical address by using the logical-to-physical address translation table50. The command processing module32generates one or more NAND requests (read requests), based on the size of user data to be read in accordance with the read command and the read unit of the NAND flash memory4.

For example, in a case where the received command is a write command, the command processing module32generates one NAND request (write request) when the size of user data to be written in accordance with one or more write commands has reached the write unit of the NAND flash memory4. The size of user data to be written in accordance with the one or more write commands is the size of user data designated in the one or more write commands.

The command processing module32stores the generated one or more NAND requests in a corresponding intermediate queue15. The corresponding intermediate queue15is an intermediate queue15that corresponds to a group to which a submission queue25from which the command has been fetched belongs. For example, a NAND request based on a command fetched from the submission queue25-0is stored in the intermediate queue15-1corresponding to the group G10to which the submission queue25-0belongs. For example, a NAND request based on a command fetched from the submission queue25-13is stored in the intermediate queue15-4corresponding to the group G21to which the submission queue25-13belongs.

In some cases, an actual NAND use time corresponding to a command may be different from the NAND use time corresponding to the command calculated by the fetch scheduling module31. In this case, the command processing module32may feed information for correcting the NAND use time back to the fetch scheduling module31. The information for correcting the NAND use time is also referred to as correction information. A specific example of the correction information will be described below.

While user data to be read in accordance with a read command is cached in the read buffer55(cache hit), the command processing module32does not have to read the user data from the NAND flash memory4. In this case, the command processing module32does not generate NAND requests based on the read command. For example, the command processing module32sends correction information indicative of the number of the NAND requests that were not generated according to the cache hit (hereinafter referred to as first correction information) to the fetch scheduling module31.

For example, the fetch scheduling module31subtracts a NAND use time based on the number of the NAND requests indicated in the first correction information (=the number of the NAND requests×the read request time tR) from the NAND use time VT of a corresponding group. Alternatively, the fetch scheduling module31may subtract a value obtained by dividing the NAND use time based on the number of the NAND requests indicated in the first correction information by the weight W of the corresponding group, from the NAND use time VT of the group.

In a case where a logical address designated in a read command is not associated with any physical address in the logical-to-physical address translation table50(in other words, the designated logical address corresponds to an unmapped area), the command processing module32does not generate NAND requests based on the read command. The command processing module32sends, for example, correction information indicative of the number of the NAND requests that were not generated according to the designated logical address corresponding to the unmapped area (hereinafter referred to as second correction information) to the fetch scheduling module31.

For example, the fetch scheduling module31subtracts a NAND use time based on the number of the NAND requests indicated in the second correction information (=the number of the NAND requests×the read request time tR) from the NAND use time VT of a corresponding group. Alternatively, the fetch scheduling module31may subtract a value obtained by dividing the NAND use time based on the number of the NAND requests indicated in the second correction information by the weight W of the corresponding group, from the NAND use time VT of the group.

The fetch scheduling module31may further update the NAND use time NVT of a namespace with which the group is associated by using the NAND use time VT subtracted based on the first correction information or the second correction information.

In a case where a command received from the fetch scheduling module31is a flush command, the command processing module32generates a NAND request for writing user data corresponding to write commands, which have been received, into the NAND flash memory4with padding. Writing the user data with padding means writing data of the write unit that includes the user data stored in the write buffer54and data for padding. The command processing module32sends, for example, correction information indicative of the number of NAND requests corresponding to the data for padding (hereinafter referred to as third correction information) to the fetch scheduling module31.

The fetch scheduling module31adds a NAND use time based on the number of NAND requests indicated in the third correction information (=the number of NAND requests×the program time tProg), to the NAND use time VT of a corresponding group. Alternatively, the fetch scheduling module31may add a value obtained by dividing the NAND use time based on the number of the NAND requests indicated in the third correction information by the weight W of the corresponding group, to the NAND use time VT of the group.

The fetch scheduling module31may further update the NAND use time NVT of a namespace with which the group is associated by using the NAND use time VT added based on the third correction information.

As described above, the fetch scheduling module31may correct the NAND use time VT of a group or the NAND use time NVT of a namespace by using correction information provided by the command processing module32.

The NAND scheduling module33schedules processes in accordance with NAND requests stored in the plurality of intermediate queues15. Specifically, the NAND scheduling module33acquires a NAND request of a processing target so that the NAND flash memory4is used evenly between the namespaces. Alternatively, the NAND scheduling module33may acquire a NAND request of a processing target from the intermediate queues15so that the NAND flash memory4is used evenly between the namespaces and the NAND flash memory4is used evenly between the groups. The NAND scheduling module33executes a process for the NAND flash memory4, based on the acquired NAND request. Note that in a case where the NAND flash memory4includes the plurality of NAND memory chips41, the NAND scheduling module33may perform the scheduling per NAND memory chip41.

The NAND scheduling module33may feed information that indicates use status of the NAND flash memory4(hereinafter referred to as use status information) back to the fetch scheduling module31. For example, the NAND scheduling module33periodically sends the use status information based on NAND requests acquired from each of the intermediate queues15in a specific time period, to the fetch scheduling module31. The specific time period, is for example, 50 ms.

Alternatively, in response to acquiring L read requests from an intermediate queue15, the NAND scheduling module33may send use status information indicating that the L read requests of a group corresponding to the intermediate queue15have been processed, to the fetch scheduling module31. Alternatively, in response to acquiring M write requests from an intermediate queue15, the NAND scheduling module33may send use status information that indicates that the M write requests of a group corresponding to the intermediate queue15have been processed, to the fetch scheduling module31. L is, for example, larger than M. M is, for example, one. That is because the program time tProg in accordance a write request is long and thus, overhead of a process for feedback of the use status information indicating that the M write requests have been processed tends not to affect processes of NAND requests by the NAND scheduling module33.

The fetch scheduling module31may correct the NAND use time VT of a group and the NAND use time NVT of a namespace, by using the use status information received from the NAND scheduling module33. For example, the fetch scheduling module31may subtract a NAND use time calculated based on the use status information, from the NAND use time VT of the group.

Processes executed in the memory system3will be described with reference toFIG.14andFIG.15.

FIG.14is a flowchart illustrating an example of the procedure of a use time update process executed by the fetch scheduling module31. The use time update process is a process of updating, based on a command fetched from a submission queue25, the NAND use times of a namespace and a group that correspond to the submission queue25. The fetch scheduling module31executes the use time update process, for example, when a command has been fetched from a submission queue25among the plurality of submission queues25. Here, a case where the command fetched from the submission queues25is either a write command or a read command will be explained. The submission queue25from which the command has been fetched is referred to as a target submission queue25.

First, the fetch scheduling module31determines whether the fetched command is a read command or not (step S101).

When the fetched command is a read command (yes in step S101), the fetch scheduling module31calculates the number Nr of NAND requests (i.e., the number Nr of read requests) corresponding to the read command (step S102). The fetch scheduling module31acquires the weight W associated with a group to which the target submission queue25belongs (belonging group), from the group management table51(step S103).

The fetch scheduling module31adds the read time×the number of read requests/the weight (that is, tR×Nr/W) to the current NAND use time VT of the belonging group in the group-NAND use time management table52, thereby updating the NAND use time VT of the belonging group (step S104), and proceeds to step S105. Specifically, for example, the fetch scheduling module31acquires the current NAND use time VT of the belonging group from the group-NAND use time management table52. The fetch scheduling module31calculates a value obtained by adding the read time×the number of read requests/the weight to the acquired current NAND use time VT. Then, the fetch scheduling module31sets the calculated value as the NAND use time VT of the belonging group in the group-NAND use time management table52.

When the fetched command is a write command, (no in step S101), the fetch scheduling module31calculates the number Nw of NAND requests (i.e., the number Nw of write requests) corresponding to the write command (step S106). The fetch scheduling module31acquires the weight W associated with the group to which the target submission queue25belongs (belonging group) from the group management table51(step S107).

The fetch scheduling module31adds the program time×the number of write requests/the weight (that is, tProg×Nw/W) to the current NAND use time VT of the belonging group in the group-NAND use time management table52, thereby updating the NAND use time VT of the belonging group (step S108), and proceeds to step S105. Specifically, for example, the fetch scheduling module31acquires the current NAND use time VT of the belonging group from the group-NAND use time management table52. The fetch scheduling module31calculates a value obtained by adding the program time×the number of write requeststhe weight to the acquired current NAND use time VT. The fetch scheduling module31sets the calculated value as the NAND use time VT of the belonging group in the group-NAND use time management table52.

Next, in step S105, the fetch scheduling module31updates the NAND use time NVT of a namespace to which the target submission queue25is allocated (first target namespace) and ends the use time update process. Specifically, for example, the fetch scheduling module31identifies all groups that are associated with the first target namespace by using the group management table51. The fetch scheduling module31acquires the NAND use times VT of all the identified groups from the group-NAND use time management table52. The fetch scheduling module31calculates the sum of the acquired NAND use times VT. Then, the fetch scheduling module31sets the calculated sum of the NAND use times VT as the NAND use time NVT of the first target namespace in the NS-NAND use time management table53.

With the use time update process described above, the fetch scheduling module31can update the NAND use time VT of a group to which the target submission queue25belongs and the NAND use time NVT of a namespace to which the target submission queue25is allocated, based on a command fetched from the target submission queue25.

FIG.15is a flowchart illustrating an example of the procedure of a priority control process executed by the fetch scheduling module31. The priority control process is a process of controlling the priority P for the fetching commands from each submission queue25, based on the NAND use time NVT per namespace and the NAND use time VT per group. The fetch scheduling module31executes the priority control process, for example, when having completed the use time update process described above with reference toFIG.14.

First, the fetch scheduling module31calculates the average of the NAND use times NVT of all the plurality of namespaces (NS average use time) by using the NS-NAND use time management table53(step201).

Next, the fetch scheduling module31selects one namespace from the plurality of namespaces (step S202). The selected namespace is referred to as a second target namespace. The fetch scheduling module31determines whether a difference obtained by subtracting the NS average use time from the NAND use time NVT of the second target namespace is larger than the threshold value A or not (step S203).

When the difference obtained by subtracting the NS average use time from the NAND use time NVT of the second target namespace is equal to or smaller than the threshold value A (no in step S203), the fetch scheduling module31increases the priority P (or priorities P) of the one or more submission queues25that are allocated to the second target namespace (step S204) and proceeds to step S211. Specifically, for example, the fetch scheduling module31increases, in the group management table51, the priority P corresponding to each of the one or more groups that are associated with the second target namespace by the second value. Each of the groups associated with the second target namespace is a group to which at least one of the submission queues25allocated to the second target namespace belongs. Alternatively, for example, the fetch scheduling module31may enable fetching from the submission queues25allocated to the second target namespace.

When the difference obtained by subtracting the NS average use time from the NAND use time NVT of the second target namespace is larger than the threshold value A (yes in step S203), in step S205, the fetch scheduling module31calculates the average of NAND use times VT of all the groups associated with the second target namespace (group average use time).

Next, the fetch scheduling module31selects one group from the one or more groups associated with the second target namespace (step S206). The selected group is referred to as a target group. The fetch scheduling module31determines whether a difference obtained by subtracting the group average use time from the NAND use time VT of the target group is larger than the threshold value C or not (step S207).

When the difference obtained by subtracting the group average use time from the NAND use time VT of the target group is larger than the threshold value C (yes in step S207), the fetch scheduling module31decreases the priority P (or priorities P) of the one or more submission queues25that belong to the target group (step S208). Specifically, for example, the fetch scheduling module31decreases, in the group management table51, the priority P corresponding to the target group by the first value. Alternatively, the fetch scheduling module31may disable fetching from the submission queues25that belong to the target group.

When the difference obtained by subtracting the group average use time from the NAND use time VT of the target group is equal to or smaller than the threshold value C (no in step S207), the fetch scheduling module31increases the priority P (or priorities P) of the one or more submission queues25that belong to the target group (step S209). Specifically, for example, the fetch scheduling module31increases, in the group management table51, the priority P corresponding to the target group by the second value. Alternatively, the fetch scheduling module31may enable fetching from the submission queues25that belong to the target group.

Next, the fetch scheduling module31determines whether or not there is another group that is associated with the second target namespace and has not been selected (step S210). When there is another group that has not been selected (yes in step S210), the process by the fetch scheduling module31returns to step S206. In other words, the fetch scheduling module31further performs a process for controlling the priority P with respect to said another group associated with the second target namespace.

When all the groups associated with the second target namespace have been selected (no in step S210), the process by the fetch scheduling module31proceeds to step S211.

Next, the fetch scheduling module31determines whether or not there is another namespace that has not been selected (step S211).

When there is another namespace that has not been selected (yes in step S211), the process by the fetch scheduling module31returns to step S202. That is, the fetch scheduling module31further performs a process for controlling the priority P per group with respect to submission queues25allocated to said another namespace.

When all the namespaces have been selected, (no in step S211), the fetch scheduling module31ends the priority control process.

With the priority control process described above, the fetch scheduling module31can control the priority P for the fetching of commands from each submission queue25, based on the NAND use time NVT per namespace and the NAND use time VT per group. Specifically, when a condition that: the NAND use time NVT of a namespace to which a submission queue25is allocated is longer than the NS average use time by the threshold value A or more; and the NAND use time VT of a group to which the submission queue25belongs is longer than the group average use time by the threshold value C or more is satisfied, the fetch scheduling module31decreases the priority P (or priorities P) of the one or more submission queues25that belong to the group or disables fetching from the submission queues25that belong to the group. In contrast, the fetch scheduling module31increases the priority P (or priorities P) of the one or more submission queues25that belong to a group that does not satisfy the condition or enables fetching from the submission queues25that belong to the group.

Thus, the fetch scheduling module31can even out the use times of the NAND flash memory4between the namespaces. In addition, the fetch scheduling module31can even out the use times of the NAND flash memory4between the groups associated with one namespace.

Note that the fetch scheduling module31may be configured to strike a use balance of the NAND flash memory4per namespace between read operations and program operations. In this case, the fetch scheduling module31manages an index per namespace that indicates a relationship between a use amount of the NAND flash memory4in the read operations and a use amount of the NAND flash memory4in the program operations. This index is hereinafter referred to as a read-write use amount. For example, the fetch scheduling module31calculates as the read-write use amount: a value obtained by (1) subtraction of a processing amount in the NAND flash memory4executed in accordance with a read command fetched from the submission queues25allocated to a namespace and (2) addition of a processing amount in the NAND flash memory4executed in accordance with a write command fetched from the submission queues25allocated to the namespace. The fetch scheduling module31manages the read-write use amount, for example, by using the NS-NAND use time management table53.

FIG.16illustrates another example of the configuration of the NS-NAND use time management table53. Each entry in the NS-NAND use time management table53illustrated inFIG.16further includes a read-write use time field in addition to the NS field and the NAND use time field described above with reference toFIG.5.

The read-write use time field indicates a read-write use amount with respect to a corresponding namespace. Every time a command is fetched from the submission queues25allocated to the namespace, the value indicated in the read-write use time field is updated by using a predicted use amount of the NAND flash memory4in accordance with the command (or a value obtained by dividing the predicted use amount by the weight W).

More specifically, the read-write use amount is represented by an index indicative of a relationship between a use time of the NAND flash memory4in read operations and a use time of the NAND flash memory4in program operations (hereinafter referred to as a read-write use time RWVT) with respect to the corresponding namespace. The read-write use time RWVT is, for example, represented by a value that is obtained by (1) subtraction of a use time of the NAND flash memory4in accordance with a read command fetched from the submission queues25allocated to the corresponding namespace and (2) addition of a use time of the NAND flash memory4in accordance with a write command fetched from the submission queues25allocated to the namespace, from a certain time point. Specifically, when a read command has been fetched from the submission queues25allocated to the namespace, a predicted use time of the NAND flash memory4in accordance with the read command (or a value obtained by dividing the predicted use time by the weight W) is subtracted from the read-write use time RWVT corresponding to the namespace. When a write command has been fetched from the submission queues25allocated to the namespace, a predicted use time of the NAND flash memory4in accordance with the write command (or a value obtained by dividing the predicted use time by the weight W) is added to the read-write use time RWVT corresponding to the namespace.

In the example illustrated inFIG.16, the NAND use time of the namespace “1” is, for example, NVT1. The read-write use time of the namespace “1” is RWVT1. The NAND use time of the namespace “2” is NVT2. The read-write use time of the namespace “2” is RWVT2.

Note that when using the NS-NAND use time management table53illustrated inFIG.16, the fetch scheduling module31may not use the group-NAND use time management table52. In this case, every time a command is fetched from the submission queues25allocated to a namespace, the fetch scheduling module31updates the NAND use time NVT corresponding to the namespace by using a predicted NAND use time in accordance with the command (or a value obtained by dividing the predicted NAND use time by the weight W). In other words, when the group-NAND use time management table52is not used, the fetch scheduling module31updates the NAND use time NVT of the corresponding namespace by using the predicted NAND use time in accordance with the fetched command, instead of calculating the sum of the NAND use times VT of all the groups associated with the namespace, as the NAND use time NVT of the namespace.

Processes to strike a use balance of the NAND flash memory4between read operations and program operations with respect to a namespace will be explained with reference toFIG.17andFIG.18.

FIG.17is a flowchart illustrating another example of the procedure of the use time update process executed by the fetch scheduling module31. The use time update process is a process of updating, based on a command fetched from a submission queue25, the NAND use time NVT and the read-write use time RWVT of a namespace corresponding to the submission queue25. For example, the fetch scheduling module31executes the use time update process when a command has been fetched from any of the submission queues25. Here, a case where the command fetched from the submission queues25is either a write command or a read command will be explained.

First, the fetch scheduling module31determines whether the fetched command is a read command or not (step S301).

When the fetched command is a read command (yes in step S301), the fetch scheduling module31calculates the number Nr of NAND requests (the number Nr of read requests) corresponding to the read command (step S302). The fetch scheduling module31acquires the weight W associated with a group to which the target submission queue25belongs, from the group management table51(step S303).

The fetch scheduling module31subtracts the read time×the number of read requests/the weight (that is, tR×Nr/W) from the current read-write use time RWVT of a namespace to which the target submission queue25is allocated (first target namespace), thereby updating the read-write use time RWVT of the first target namespace in the NS-NAND use time management table53(step S304). Specifically, for example, the fetch scheduling module31acquires the current read-write use time RWVT of the first target namespace from the NS-NAND use time management table53. The fetch scheduling module31calculates a value by subtracting the read time×the number of read requests/the weight from the acquired current read-write use time RWVT. Then, the fetch scheduling module31sets the calculated value as the read-write use time RWVT of the first target namespace in the NS-NAND use time management table53.

Next, the fetch scheduling module31adds the value obtained by the read time×the number of read requests/the weight (that is, tR×Nr/W) to the current NAND use time NVT of the first target namespace, thereby updating the NAND use time NVT of the first target namespace in the NS-NAND use time management table53(step S305), and ends the use time update process. Specifically, for example, the fetch scheduling module31acquires the current NAND use time NVT of the first target namespace from the NS-NAND use time management table53. The fetch scheduling module31calculates the value obtained by adding the read time×the number of read requests/the weight to the acquired current NAND use time NVT. Then, the fetch scheduling module31sets the calculated value as the NAND use time NVT of the first target namespace in the NS-NAND use time management table53.

When the fetched command is a write command, (no in step301), the fetch scheduling module31calculates the number Nw of NAND requests (the number Nw of write request) corresponding to the write command (step S306). The fetch scheduling module31acquires the weight W associated with a group to which the target submission queue25belongs, from the group management table51(step S307).

The fetch scheduling module31adds a value obtained by the program time×the number of write requests/the weight (that is, tProg×Nw/W) to the current read-write use time RWVT of the first target namespace, thereby updating the read-write use time RWVT of the first target namespace in the NS-NAND use time management table53(step S308). Specifically, for example, the fetch scheduling module31acquires the current read-write use time RWVT of the first target namespace from the NS-NAND use time management table53. The fetch scheduling module31calculates the value obtained by adding the program time×the number of write requests/the weight to the acquired current read-write use time RWVT. Then, the fetch scheduling module31sets the calculated value as the read-write use time RWVT of the first target namespace in the NS-NAND use time management table53.

Next, the fetch scheduling module31adds the value obtained by the program time×the number of write requests/the weight (that is, tProg×Nw/W) to the current NAND use time NVT of the first target namespace, thereby updating the NAND use time NVT of the first target namespace in the NS-NAND use time management table53(step S309), and ends the use time update process. Specifically, for example, the fetch scheduling module31acquires the current NAND use time NVT of the first target namespace from the NS-NAND use time management table53. The fetch scheduling module31calculates the value by adding the program time×the number of write requests/the weight to the acquired current NAND use time NVT. Then, the fetch scheduling module31sets the calculated value as the NAND use time NVT of the first target namespace in the NS-NAND use time management table53.

With the use time update process described above, the fetch scheduling module31can update the NAND use time NVT and the read-write use time RWVT of a namespace to which the target submission queue25is allocated, based on a command fetched from the target submission queue25.

In the use time update process described above, the fetch scheduling module31updates the read-write use time RWVT by the subtraction of the read time×the number of read requests/the weight (step S304) or the addition of the program time×the number of write requests/the weight (step S308). However, the fetch scheduling module31may update the read-write use time RWVT by a first operation (for example, addition, multiplication, or division) of the read time×the number of read requests/the weight, or by a second operation (for example, subtraction, division, or multiplication) of the program time×the number of write requests/the weight. The second operation is, for example, an inverse operation of the first operation.

FIG.18is a flowchart illustrating another example of the procedure of the priority control process executed by the fetch scheduling module31. The priority control process is a process of controlling the priority P for the fetching of commands from each submission queue25, based on the NAND use time NVT and the read-write use time RWVT per namespace. The fetch scheduling module31executes the priority control process, for example, when having completed the use time update process described above with reference toFIG.17.

The processes from step S401to step S404are the same as the processes from step S201to step S204of the priority control process described above with reference toFIG.15. That is, the fetch scheduling module31determines whether the NAND use time NVT of a selected namespace (second target namespace) is relatively long or not. Then, when the NAND use time NVT of the second target namespace is relatively short, the fetch scheduling module31increases the priority P (or priorities P) of the one or more submission queues25that are allocated to the second target namespace.

When the NAND use time NVT of the second target namespace is relatively long, in other words, a value obtained by subtracting the NS average use time from the NAND use time NVT of the second target namespace is larger than the threshold value A (yes in step S403), the fetch scheduling module31decreases the priority P (or priorities P) of the submission queues25allocated to the second target namespace (step S405). Alternatively, the fetch scheduling module31may disable the fetching of a command from the submission queues25allocated to the second target namespace. Then, the fetch scheduling module31determines whether the read-write use time RWVT of the second target namespace is larger than a threshold value E or not (step S406). The threshold value E is zero or larger, and is, for example, zero. The read-write use time RWVT of the second target namespace larger than the threshold value E means that the NAND use time in program operations is longer than the NAND use time in read operations with respect to the second target namespace.

When the read-write use time RWVT of the second target namespace is larger than the threshold value E (yes in step S406), the fetch scheduling module31increases the priority P of the submission queues25for read allocated to the second target namespace (step S407). Then, the fetch scheduling module31decreases the priority P of the submission queues25for write allocated to the second target namespace (step S408) and proceeds to step S412.

When the read-write use time RWVT of the second target namespace is equal to or smaller than the threshold value E (no in step S406), the fetch scheduling module31determines whether the read-write use time RWVT of the second target namespace is smaller than a threshold value F or not (step S409). The threshold value F is zero or smaller, and is, for example, zero. The threshold value F is equal to or smaller than the threshold value E. For example, in a use case where shortening latency related to read commands is emphasized, the threshold value F is set to a smaller value. The read-write use time RWVT of the second target namespace smaller than the threshold value F means that the NAND use time in read operations is longer than the NAND use time in program operations with respect to the second target namespace.

When the read-write use time RWVT of the second target namespace is smaller than the threshold value F (yes in step S409), the fetch scheduling module31increases the priority P of the submission queues25for write allocated to the second target namespace (step S410). Then, the fetch scheduling module31decreases the priority P of the submission queues25for read allocated to the second target namespace (step S411) and proceeds to step S412.

When the read-write use time RWVT of the second target namespace is equal to or larger than the threshold value F (no in step S409), the process by the fetch scheduling module31proceeds to step S412.

Next, the fetch scheduling module31determines whether there is another namespace that has not been selected (step S412).

When there is another namespace that has not been selected (yes in step S412), the process by the fetch scheduling module31returns to step S402. That is, the fetch scheduling module31further executes a process to control the priority P of each submission queue25allocated to said another namespace.

When all the namespaces have been selected, (no in step S412), the fetch scheduling module31ends the priority control process.

Note that, in the priority control process, the determination on which of the program operations and the read operations have longer NAND use time (step S406and step S409) may be changed depending on types of the first operation and the second operation used for updating the read-write use time RWVT.

With the priority control process described above, the fetch scheduling module31can even out the use times of the NAND flash memory4between the namespaces and can strike a use balance of the NAND flash memory4between the read operations and the program operations with respect to the second target namespace having a relatively long NAND use time NVT. Specifically, when the NAND use time in the program operations is longer than the NAND use time in the read operations with respect to the second target namespace, the fetch scheduling module31increases the priority P of the submission queues25for read allocated to the second target namespace and decreases the priority P of the submission queues25for write allocated to the second target namespace. When the NAND use time of the read operations is longer than the NAND use time of the program operations with respect to the second target namespace, the fetch scheduling module31increases the priority P of the submission queues25for write allocated to the second target namespace and decreases the priority P of the submission queues25for read allocated to the second target namespace.

As described above, according to the memory system3of the present embodiment, an evenness of use of a nonvolatile memory corresponding to a plurality of logical address spaces can be improved. The fetch scheduling module31communicates with the host2that includes a plurality of submission queues25each being capable of storing one or more commands. The fetch scheduling module31provides the host2with a plurality of namespaces. The plurality of namespaces include at least a first namespace. One or more of the plurality of submission queues25are allocated to each of the plurality of namespaces. The fetch scheduling module31calculates a plurality of first use amounts of the NAND flash memory4that correspond to the plurality of namespaces, respectively. The plurality of first use amounts include at least a second use amount that corresponds to the first namespace. The fetch scheduling module31selects a first submission queue25from which a command is to be fetched among the plurality of submission queues25, based on the plurality of first use amounts. The first submission queue25is allocated to the first namespace. The fetch scheduling module31fetches a first command from the first submission queue25. The fetch scheduling module31calculates a predicted use amount of the NAND flash memory4. The predicted use amount is an amount of the NAND flash memory4that is to be used in accordance with the first command. The fetch scheduling module31updates the second use amount by using the calculated predicted use amount.

For example, the fetch scheduling module31selects a submission queue25that is allocated to a namespace having a small use amount of the NAND flash memory4as a fetch target submission queue25(or increases frequency at which the submission queue25is selected as the target submission queue25), thereby storing sufficient number of NAND requests corresponding to the namespace in the intermediate queue15. Thus, the NAND scheduling module33can schedule issuance of the NAND requests stored in the intermediate queues15so that the NAND flash memory4is used evenly between the namespaces. Therefore, the memory system3can improve the evenness of the use of the NAND flash memory4between the namespaces.

For example, the fetch scheduling module31does not select a submission queue25that is allocated to a namespace having a large use amount of the NAND flash memory4as the fetch target submission queue25(or decreases frequency at which the submission queue25is selected as the target submission queue25), thereby preventing excessively storing NAND requests corresponding to the namespace in the intermediate queue15and preventing a waste of resources of the memory system3for managing fetched commands. Therefore, it is possible to reduce the resources of the memory system3for managing commands (for example, the size of storage area allocated as the intermediate queues15), compared to the memory system3C of the comparative example.

Each of the various functions described in the embodiment may be realized by a circuit (e.g., processing circuit). An exemplary processing circuit may be a programmed processor such as a central processing unit (CPU). The processor executes computer programs (instructions) stored in a memory thereby performs the described functions. The processor may be a microprocessor including an electric circuit. An exemplary processing circuit may be a digital signal processor (DSP), an application specific integrated circuit (ASIC), a microcontroller, a controller, or other electric circuit components. The components other than the CPU described according to the embodiment may be realized in a processing circuit.