US 9,870,149 B2Granted

Scheduling operations in non-volatile memory devices using preference values

AssigneeSanDisk Technologies LLC

InventorsSteven Sprouse, Ryan Marlin

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method of scheduling memory operations to be performed by non-volatile memory devices in a storage system includes identifying a plurality of memory operations to be performed by a plurality of non-volatile memory devices in the storage system. The number of memory operations in the plurality of memory operations is no greater than the number of non-volatile memory devices in the plurality of non-volatile memory devices; each memory operation is to be performed by a distinct non-volatile memory device; and the memory operations include host writes, garbage collection writes, and garbage collection reads. The method also includes, for each non-volatile memory device, assigning preference values to each of the memory operations. The method further includes assigning each memory operation to a distinct non-volatile memory device, using the preference values assigned to each of the memory operations for each non-volatile memory device.

Claims20

Dependent claims

A method of managing a storage system, the method comprising:

in the storage system, which includes a storage controller and non-volatile memory devices:
identifying a plurality of memory operations to be performed by a plurality of the non-volatile memory devices in the storage system, wherein
the plurality of memory operations comprises a first number of memory operations and the plurality of non-volatile memory devices comprises a second number of memory devices,
the first number is no greater than the second number,
each memory operation of the plurality of memory operations is to be performed by a distinct non-volatile memory device, and
the memory operations comprise host writes, garbage collection writes, and garbage collection reads;
for each non-volatile memory device in the plurality of non-volatile memory devices, assigning preference values to each of the memory operations in the plurality of memory operations, wherein assigning preference values comprises, for a respective non-volatile memory device:
determining that a first memory operation of the plurality of memory operations is associated with a process for which no more than a specified number of memory operations are incomplete;
and
in response to the determining, assigning preference values to the memory operations that indicate a preference of the respective non-volatile memory device for the first memory operation over other memory operations of the plurality of memory operations;
and
assigning each memory operation in the plurality of memory operations to a distinct non-volatile memory device in the plurality of non-volatile memory devices, using the preference values assigned to each of the memory operations for each non-volatile memory device;
wherein:
assigning each memory operation to a distinct non-volatile memory device comprises:
solving a predefined combinatorial optimization problem, known as The Stable Marriage Problem using the Gale-Shapely algorithm;
or
solving a predefined combinatorial optimization problem, known as The Assignment Problem using the Hungarian algorithm;
and
wherein:
the storage controller manages a plurality of processes;
each memory operation is part of a process;
a respective process comprises memory operations of a common type selected from the group consisting of host writes, garbage collection writes, and garbage collection reads;
and
the memory operations of a respective process comprise memory operations directed to respective pages in each of the non-volatile memory devices.

21 more elements

A storage system, comprising:

a plurality of non-volatile memory devices;
one or more processors;
and
memory storing one or more programs configured for execution by the one or more processors, the one or more programs comprising instructions that when executed by the one or more processors, cause the storage system to:
identify a plurality of memory operations to be performed by a plurality of the non-volatile memory devices in the storage system, wherein
the plurality of memory operations comprises a first number of memory operations and the plurality of non-volatile memory devices comprises a second number of memory devices,
the first number is no greater than the second number,
each memory operation of the plurality of memory operations is to be performed by a distinct non-volatile memory device, and
the memory operations comprise host writes, garbage collection writes, and garbage collection reads;
for each non-volatile memory device in the plurality of non-volatile memory devices, assign preference values to each of the memory operations in the plurality of memory operations, wherein to assign preference values the one or more programs further comprise instructions to cause the storage system to, for a respective non-volatile memory device:
determine that a first memory operation of the plurality of memory operations is associated with a process for which no more than a specified number of memory operations are incomplete;
and
in response to determining that the first memory operation of the plurality of memory operations is associated with the process, assign preference values to the plurality of memory operations that indicate a preference of the respective non-volatile memory device for the first memory operation over other memory operations of the plurality of memory operations;
and
assign each memory operation in the plurality of memory operations to a distinct non-volatile memory device in the plurality of non-volatile memory devices, using the preference values assigned to each of the memory operations for each non-volatile memory device;
wherein:
the storage system assigns each memory operation to a distinct non-volatile memory device by:
solving a first predefined combinatorial optimization problem known as The Stable Marriage Problem using the Gale-Shapely iterative algorithm;
or
solving a second predefined combinatorial optimization problem known as The Assignment Problem using the Hungarian algorithm;
and
wherein:
the one or more processors manage a plurality of processes;
each memory operation is part of a process;
a respective process comprises memory operations of a common type selected from the group consisting of host writes, garbage collection writes, and garbage collection reads;
and
the memory operations of a respective process comprise memory operations directed to respective pages in each of the non-volatile memory devices.

24 more elements

A non-transitory computer-readable storage medium storing one or more programs configured for execution by one or more processors of a storage system that further comprises a plurality of non-volatile memory devices, the one or more programs comprising instructions that when executed by the one or more processors, cause the storage system to:

identify a plurality of memory operations to be performed by a plurality of the non-volatile memory devices in the storage system, wherein
the plurality of memory operations comprises a first number of memory operations and the plurality of non-volatile memory devices comprises a second number of memory devices,
the first number is no greater than the second number,
each memory operation of the plurality of memory operations is to be performed by a distinct non-volatile memory device, and
the memory operations comprise host writes, garbage collection writes, and garbage collection reads;
for each non-volatile memory device in the plurality of non-volatile memory devices, assign preference values to each of the memory operations in the plurality of memory operations, wherein to assign preference values the one or more programs further comprise instructions to cause the storage system to, for a respective non-volatile memory device:
determine that a first memory operation of the plurality of memory operations is associated with a process for which no more than a specified number of memory operations are incomplete;
and
in response to determining that the first memory operation of the plurality of memory operations is associated with the process, assign preference values to the plurality of memory operations that indicate a preference of the respective non-volatile memory device for the first memory operation over other memory operations of the plurality of memory operations;
and
assign each memory operation in the plurality of memory operations to a distinct non-volatile memory device in the plurality of non-volatile memory devices, using the preference values assigned to each of the memory operations for each non-volatile memory device;
wherein:
the storage system assigns each memory operation to a distinct non-volatile memory device by:
solving a first predefined combinatorial optimization problem known as The Stable Marriage Problem using the Gale-Shapely iterative algorithm;
or
solving a second predefined combinatorial optimization problem known as The Assignment Problem using the Hungarian algorithm;
and
wherein:
the one or more processors manage a plurality of processes;
each memory operation is part of a process;
a respective process comprises memory operations of a common type selected from the group consisting of host writes, garbage collection writes, and garbage collection reads;
and
the memory operations of a respective process comprise memory operations directed to respective pages in each of the non-volatile memory devices.

20 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/937,793Filed 10 Nov 2015 · us provisional application
Priority: 8 Jul 2015
Published: US 2017/0010815 A112 Jan 2017
Granted: 16 Jan 2018
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

G06F 3/0604
Specifically adapted to achieve a particular effect: improving or facilitating administration, e.g. storage management
G06F 3/0631
Configuration or reconfiguration of storage systems: by allocating resources to storage systems
G06F 3/0688
Plurality of storage devices: non-volatile semiconductor memory arrays
G06F 12/0246
Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory: in block erasable memory, e.g. flash memory