Scheduling requests in a solid state memory device

Patent metadata

Field	Value
Publication number	US-9075712-B2
Application number	US-201213688270-A
Country	US
Kind code	B2
Filing date	Nov 29, 2012
Priority date	Nov 30, 2011
Publication date	Jul 7, 2015
Grant date	Jul 7, 2015

Abstract

An apparatus and method for a memory controller for managing scheduling requests in a solid state memory device. The memory includes a set of units wherein a unit within the set of units is erasable as a whole by a unit reclaiming process resulting in a free unit available for writing data to. The memory controller further includes a first queue for queuing user requests for reading and/or writing data from/to the memory, and a second queue for queuing unit reclaiming requests for executing the unit reclaiming process. A scheduler is provided for selecting user requests from the first queue and unit reclaiming requests from the second queue for execution according to a defined ratio. The defined ratio is a variable ratio, is dependent on the current number of free units, and permits the memory controller to select requests from both the first queue and the second queue.

First claim

What is claimed is:

1. Memory controller for managing a memory, the memory controller comprising:
a first queue for queuing user requests which includes either reading data, writing data or reading and writing data from or to the memory;
a second queue for queuing unit reclaiming requests for executing a unit reclaiming process; and
a scheduler for selecting the user requests from the first queue and the unit reclaiming requests from the second queue for execution according to a defined ratio,
wherein the scheduler is adapted to admit the unit reclaiming requests joining the second queue only if the current number of free units is less than the first threshold.

2. The memory controller for managing a memory according to claim 1 , wherein the memory comprises a set of units wherein a unit within the set of units is erasable as a whole by the unit reclaiming process resulting in a free unit available for writing data to.

3. The memory controller for managing a memory according to claim 1 , wherein the defined ratio is a variable ratio and is dependent on a current number of free units.

4. The memory controller for managing a memory according to claim 3 , wherein the variable ratio permits the memory controller to select requests from both the first queue and the second queue.

5. The memory controller for managing a memory according to claim 1 , wherein the scheduler is adapted to select requests according to the defined ratio if the current number of free units is less than a first threshold.

6. The memory controller for managing a memory according to claim 1 , wherein the scheduler is adapted to exclusively select the user requests from the first queue if the current number of free units is equal to or above the first threshold.

7. The memory controller for managing a memory according to claim 1 , wherein the scheduler is adapted to define the ratio so that the more free units that are currently available the more user requests from the first queue are selected for execution.

8. The memory controller for managing a memory according to claim 1 , wherein the scheduler is adapted to define the ratio proportional to the current number of free units.

9. The memory controller for managing a memory according to claim 1 , wherein the scheduler is adapted to define the ratio by defining a first number (m), wherein (m) represents the number of the user requests to be selected for execution in a row from the first queue, and by defining a second number (n), wherein (n) represents the number of the unit reclaiming requests to be selected for execution in a row from the second queue.

10. The memory controller for managing a memory according to claim 9 , wherein if a queue out of the first queue or the second queue which the scheduler currently selects requests from for execution is an empty queue prior to the scheduler selecting the associate defined number of requests in a row, the scheduler is adapted to begin selecting requests from the other queue without waiting for new requests associated with the current queue.

11. The memory controller managing a memory according to claim 9 , wherein a microprocessor is adapted to execute requests from the first and the second queue as selected by the scheduler and the microprocessor is adapted to execute the unit reclaiming process comprising the steps of:
determining a unit out of the set of units for erasure;
relocating valid subunits of the determined unit from the determined unit to another unit; and
erasing the determined unit.

12. The memory controller for managing a memory according to claim 1 , comprising a memory, wherein the memory comprises a set of units wherein a unit within the set of units is erasable as a whole by the unit reclaiming process resulting in a free unit available for writing data to, which forms a storage device.

13. Memory controller for managing a memory, the memory controller comprising:
a first queue for queuing user requests which includes either reading data, writing data or reading and writing data from or to the memory;
a second queue for queuing unit reclaiming requests for executing a unit reclaiming process; and
a scheduler for selecting the user requests from the first queue and the unit reclaiming requests from the second queue for execution, wherein the scheduler is adapted to:
select the user requests from the first queue over selecting the unit reclaiming requests from the second queue if a current number of free units is equal to or above a first threshold;
select the unit reclaiming requests from the second queue over selecting the user requests from the first queue if the current number of free units is equal to or less than a second threshold; and
select the user requests from the first queue over selecting the unit reclaiming requests from the second queue after having preferred selecting the unit reclaiming requests from the second queue over selecting the user requests from the first queue if the current number of free units is equal to or above a third threshold, wherein the third threshold is equal to or less than the first threshold and the second threshold is less than the third threshold.

14. The memory controller for managing a memory according to claim 13 , wherein the scheduler is adapted to:
select the user requests exclusively from the first queue if the current number of free units is equal to or above the first threshold;
select the unit reclaiming requests exclusively from the second queue if the current number of free units is equal to or less than the second threshold; and
select the user requests exclusively from the first queue after exclusively selecting unit reclaiming requests from the second queue if the current number of free units is equal to or above the third threshold.

15. A method for managing a memory, the method comprising the step of:
selecting user requests from a first queue and unit reclaiming requests from a second queue for execution according to a defined ratio;
wherein the first queue is for queuing the user requests which includes either reading data, writing data or reading and writing data from or to the memory,
wherein the second queue is for queuing the unit reclaiming requests for executing a unit reclaiming process,
wherein the defined ratio is a variable ratio and is dependent on a current number of free units which permits selecting requests from both the first queue and the second queue, and
wherein the unit reclaiming requests are admitted to join the second queue only if the current number of free units is less than the first threshold.

16. The method for managing a memory according to claim 15 , wherein:
selecting requests according to the defined ratio if the current number of free units is less than a first threshold;
selecting the user requests from the first queue is preferred over selecting the unit reclaiming requests from the second queue if the current number of free units is equal to or above the first threshold; and
admitting the unit reclaiming requests for joining the second queue only if the current number of free units is less than the first threshold.

17. A method for managing a memory, the method comprising the steps of:
selecting user requests from a first queue is preferred over selecting unit reclaiming requests from a second queue if a current number of free units is equal to or above a first threshold;
wherein the first queue is for queuing the user requests which includes either reading data, writing data or reading and writing data from or to the memory and wherein the second queue is for queuing the

Assignees

• IBM

Inventors

• Bux Werner
• Haas Robert
• Hu Xiao-Yu
• Iliadis Ilias
• Pletka Roman

Classifications

• G06F3/0655

  Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F12/0646 Primary

  Configuration or reconfiguration · CPC title

• G06F2212/7205

  Cleaning, compaction, garbage collection, erase control · CPC title

• G06F12/0253

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title