395
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      scite_
       
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

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

      Preprint
      In review
      research-article
      1 , 1 ,   1 ,
      ScienceOpen Preprints
      ScienceOpen
      parallelism, data structure, parallel, queue
      Bookmark

            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

            Content

            Author and article information

            Journal
            ScienceOpen Preprints
            ScienceOpen
            23 March 2020
            Affiliations
            [1 ] University of Central Florida
            Author information
            https://orcid.org/0000-0002-6176-6988
            Article
            10.14293/S2199-1006.1.SOR-.PP5TSMV.v1
            ed675caf-fc4a-4359-9102-e351b514ebab

            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 .

            History
            : 23 March 2020

            The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.
            Data structures & Algorithms
            parallelism, data structure, parallel, queue

            Comments

            Comment on this article