A Conflict-Resilient Lock-Free Linearizable Calendar Queue

Romolo Marotta, Mauro Ianni, Alessandro Pellegrini, and Francesco Quaglia

Abstract:
In the last two decades, great attention has been devoted to the design of non-blocking and linearizable data structures, which enable exploiting the scaled-up degree of parallelism in off-the-shelf shared-memory multi-core machines. In this context, priority queues are highly challenging.
Indeed, concurrent attempts to extract the highest-priority item are prone to create detrimental thread conflicts that lead to abort/retry of the operations.
In this article, we present the first priority queue that jointly provides:
i) lock-freedom and linearizability;
ii) conflict resiliency against concurrent extractions;
iii) adaptiveness to different contention profiles; and
iv) amortized constant-time access for both insertions and extractions. Beyond presenting our solution, we also provide proof of its correctness based on an assertional approach.
Also, we present an experimental study on a 64-CPU machine, showing that our proposal provides performance improvements over state-of-the-art non-blocking priority queues.

BibTeX Entry: