Replacing Competition with Cooperation to Achieve Scalable Lock-Free FIFO Queues

Henzinger, Thomas A and Payer, Hannes and Sezgin, Ali (2013) Replacing Competition with Cooperation to Achieve Scalable Lock-Free FIFO Queues. Technical Report. IST Austria.

[img] Text
main-spaa2013.pdf - Published Version
Available under License All rights reserved.
[IST-2013-124-v1+1]
Download (408Kb)

Abstract

In order to guarantee that each method of a data structure updates the logical state exactly once, almost all non-blocking implementations employ Compare-And-Swap (CAS) based synchronization. For FIFO queue implementations this translates into concurrent enqueue or dequeue methods competing among themselves to update the same variable, the tail or the head, respectively, leading to high contention and poor scalability. Recent non-blocking queue implementations try to alleviate high contention by increasing the number of contention points, all the while using CAS-based synchronization. Furthermore, obtaining a wait-free implementation with competition is achieved by additional synchronization which leas to further degradation of performance. In this paper we formalize the notion of competitiveness of a synchronizing statement which can be used as a measure for the scalability of concurrent implementations. We present a new queue implementation, the Speculative Pairing (SP) queue, which, as we show, decreases competitiveness by using Fetch-And-Increment (FAI) instead of CAS. We prove that the SP queue is linearizable and lock-free. We also show that replacing CAS with FAI leads to wait-freedom for dequeue methods without an adverse effect on performance. In fact, our experiments suggest that the SP queue can perform and scale better than the state-of-the-art queue implementations.

Item Type: Monograph (Technical Report)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
Research Group: Henzinger Group
Depositing User: Ali Sezgin
Date Deposited: 13 Jun 2013 11:52
Last Modified: 26 Apr 2017 08:38
URI: https://repository.ist.ac.at/id/eprint/124

Actions (login required)

View Item View Item