License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.28
URN: urn:nbn:de:0030-drops-113356
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11335/
Go to the corresponding LIPIcs Volume Portal

Nikolaev, Ruslan

A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue

pdf-format:
LIPIcs-DISC-2019-28.pdf (0.7 MB)

Abstract

We present a new lock-free multiple-producer and multiple-consumer (MPMC) FIFO queue design which is scalable and, unlike existing high-performant queues, very memory efficient. Moreover, the design is ABA safe and does not require any external memory allocators or safe memory reclamation techniques, typically needed by other scalable designs. In fact, this queue itself can be leveraged for object allocation and reclamation, as in data pools. We use FAA (fetch-and-add), a specialized and more scalable than CAS (compare-and-set) instruction, on the most contended hot spots of the algorithm. However, unlike prior attempts with FAA, our queue is both lock-free and linearizable.
We propose a general approach, SCQ, for bounded queues. This approach can easily be extended to support unbounded FIFO queues which can store an arbitrary number of elements. SCQ is portable across virtually all existing architectures and flexible enough for a wide variety of uses. We measure the performance of our algorithm on the x86-64 and PowerPC architectures. Our evaluation validates that our queue has exceptional memory efficiency compared to other algorithms and its performance is often comparable to, or exceeding that of state-of-the-art scalable algorithms.

BibTeX - Entry

@InProceedings{nikolaev:LIPIcs:2019:11335,
  author =	{Ruslan Nikolaev},
  title =	{{A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11335},
  URN =		{urn:nbn:de:0030-drops-113356},
  doi =		{10.4230/LIPIcs.DISC.2019.28},
  annote =	{Keywords: FIFO, queue, ring buffer, lock-free, non-blocking}
}

Keywords: FIFO, queue, ring buffer, lock-free, non-blocking
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019
Supplementary Material: SCQ’s source code is available at https://github.com/rusnikola/lfqueue.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI