Re-Implementation of BQ: A Lock-Free Queue with Batching Using MR Locks

Abstract

This implementation is based on a publication by Gal Milman, Alex Kogan, Yossi Lev, Victor Luchangco, and Erez Petrank in 2018. [1] Titled BQ: A Lock-Free Queue with Batching, they describe the data structures functionality and correctness, along with the previous work it is based on. [1] All implementation details are from this paper unless otherwise stated. In this series of papers, we will be reimplementing and performance testing their data structure. This first paper covers an initial implementation involving no concurrency, using an MR Lock [2] to restrict threads access to the data structure. This ensures correctness as the operations on the queue are guaranteed to be mutually exclusive.

Our source code is available here: ​ https://github.com/ClayDiGiorgio/ParallelTeam24

Journal

Title: ScienceOpen Preprints

Publisher: ScienceOpen

Publication date (Electronic preprint): 23 March 2020

Affiliations

[1 ] University of Central Florida

Article

DOI: 10.14293/S2199-1006.1.SOR-.PP5TSMV.v1

License:

This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .