Lock-free communication storage request reordering
View Patent ↗Lock-free communication storage request reordering enables reduced latency and/or increased bandwidth in some usage scenarios, such as a multi-threaded driver context operating with a device, such as a storage device (e.g. a Solid-State Disk (SSD)) enabled to respond to a multiplicity of outstanding requests.
1. A method comprising:
managing a request queue, the managing comprising performing request addition via a tail of the request queue and performing request removal via a head of the request queue;
adding a particular request to the request queue and assigning a unique identifier to the particular request based at least in part on an offset between the tail and the head at the time of the adding;
completing the particular request;
updating a particular one of a plurality of completion status entries as identified by the unique identifier;
waiting until all requests of the request queue that are older than the particular request are completed; and
after the waiting, updating the request queue head.
2. The method of claim 1 , wherein after the updating of the request queue head, resources of the request queue associated with the particular request are available for reuse.
3. The method of claim 1 , wherein the adding is performed by driver software of a host.
4. The method of claim 3 , wherein the host comprises one or more of a computer,
a workstation computer,
a server computer,
a storage server,
a Storage Attached Network (SAN),
a Network Attached Storage (NAS) device,
a Direct Attached Storage (DAS) device,
a storage appliance,
a Personal Computer (PC),
a laptop computer,
a notebook computer,
a netbook computer,
a tablet device or computer,
an ultrabook computer,
an electronic reading device (an e-reader),
a Personal Digital Assistant (PDA),
a navigation system,
a (handheld) Global Positioning System (GPS) device,
an automotive control system,
an automotive media control system or computer,
a printer, copier or fax machine or all-in-one device,
a Point Of Sale (POS) device,
a cash-register,
a media player,
a television,
a media recorder,
a Digital Video Recorder (DVR),
a digital camera,
a cellular handset,
a cordless telephone handset, and
an electronic game.
5. The method of claim 1 , wherein the waiting is performed by a controller of a device enabled to service the particular request.
6. The method of claim 1 , wherein the waiting is performed by a controller of a device enabled to service the particular request at least in part via operation of a flash memory interface.
7. The method of claim 6 , wherein the flash memory interface is compatible with one or more of
an Open NAND Flash Interface (ONFI),
a Toggle-mode interface,
a Double-Data-Rate (DDR) synchronous interface,
a DDR2 synchronous interface,
a synchronous interface, and
an asynchronous interface.
8. The method of claim 1 , wherein the waiting is performed by a controller of a device enabled to service the particular request at least in part via accessing of at least one flash memory.
9. The method of claim 8 , wherein at least a portion of the at least one flash memory comprises one or more of
NAND flash technology storage cells, and
NOR flash technology storage cells.
10. The method of claim 8 , wherein at least a portion of the at least one flash memory comprises one or more of
Single-Level Cell (SLC) flash technology storage cells, and
Multi-Level Cell (MLC) flash technology storage cells.
11. The method of claim 8 , wherein at least a portion of the at least one flash memory comprises one or more of
polysilicon technology-based charge storage cells, and
silicon nitride technology-based charge storage cells.
12. The method of claim 8 , wherein at least a portion of the at least one flash memory comprises one or more of
two-dimensional technology-based flash memory technology, and
three-dimensional technology-based flash memory technology.
13. The method of claim 1 , wherein the particular request is communicated at least in part via a storage interface that is compatible with at least one storage interface standard.
14. The method of claim 13 , wherein the at least one storage interface standard comprises one or more of
a Universal Serial Bus (USB) interface standard,
a Compact Flash (CF) interface standard,
a MultiMediaCard (MMC) interface standard,
an embedded MMC (eMMC) interface standard,
a Thunderbolt interface standard,
a UFS interface standard,
a Secure Digital (SD) interface standard,
a Memory Stick interface standard,
an xD-picture card interface standard,
an Integrated Drive Electronics (IDE) interface standard,
a Serial Advanced Technology Attachment (SATA) interface standard,
an external SATA (eSATA) interface standard,
a Small Computer System Interface (SCSI) interface standard,
a Serial Attached Small Computer System Interface (SAS) interface standard,
a Fibre Channel interface standard,
an Ethernet interface standard, and
a Peripheral Component Interconnect express (PCIe) interface standard.
15. A non-transitory tangible computer readable medium having a set of instructions stored therein that when executed by one or more processing elements cause the processing elements to collectively perform and/or control operations comprising:
managing a request queue, the managing comprising performing request addition via a tail of the request queue and performing request removal via a head of the request queue;
adding a particular request to the request queue and assigning a unique identifier to the particular request based at least in part on an offset between the tail and the head at the time of the adding;
completing the particular request;
updating a particular one of a plurality of completion status entries as identified by the unique identifier;
waiting until all requests of the request queue that are older than the particular request are completed; and
after the waiting, updating the request queue head.
16. The non-transitory tangible computer readable medium of claim 15 ,
wherein at least one of the processing elements is comprised in a controller of a device enabled to service the particular request.
17. An apparatus comprising:
logic circuitry enabled to manage a request queue at least in part by performing request addition via a tail of the request queue and performing request removal via a head of the request queue;
logic circuitry enabled to add a particular request to the request queue and to assign a unique identifier to the particular request based at least in part on an offset between the tail and the head at the time of the adding;
logic circuitry enabled to complete the particular request;
logic circuitry enabled to update a particular one of a plurality of completion status entries as identified by the unique identifier;
logic circuitry enabled to wait until all requests of the request queue that are older than the particular request are completed; and
logic circuitry enabled to, after the waiting, update the request queue head.
18. The apparatus of claim 17 , wherein at least some of the logic circuitry elements are comprised in a controller of a device enabled to service the particular request.