A Conflict-Resilient Lock-Free Linearizable Calendar Queue

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

Published in: ACM Transactions on Parallel Computing, 2023
pdf Download PDF

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:

author = {Marotta, Romolo and Ianni, Mauro and Pellegrini, Alessandro and Quaglia, Francesco},
title = {A Conflict-Resilient Lock-Free Linearizable Calendar Queue},
journal = {ACM Transactions on Parallel Computing},
year = {2023},
month = dec,
issn = {2329-4949},
publisher = {ACM},
series = {TOPC},
doi = {10.1145/3635163}