Title

The Aba Problem In Multicore Data Structures With Collaborating Operations

Keywords

collaborating threads; multicore computing; nonblocking synchronization

Abstract

An increasing number of modern real-time systems and the nowadays ubiquitous multicore architectures demand the application of programming techniques for reliable and efficient concurrent synchronization. Some recently developed Compare-And-Swap (CAS) based nonblocking techniques hold the promise of delivering practical and safer concurrency. The ABA 2 problem is a fundamental problem to many CAS-based designs. Its significance has increased with the suggested use of CAS as a core atomic primitive for the implementation of portable lock-free algorithms. The ABA problem's occurrence is due to the intricate and complex interactions of the application's concurrent operations and, if not remedied, ABA can significantly corrupt the semantics of a nonblocking algorithm. The current state of the art leaves the elimination of the ABA hazards to the ingenuity of the software designer. In this work we provide the first systematic and detailed analysis of the ABA problem in lock-free Descriptor-based designs. We study the semantics of Descriptor-based lock-free data structures and propose a classification of their operations that helps us better understand the ABA problem and subsequently derive an effective ABA prevention scheme. We supplement our analysis with a statistical model of the probability for an ABA event in a concurrent system. Our ABA prevention approach outperforms by a large factor the use of the alternative CAS-based ABA prevention schemes. It offers speeds comparable to the use of the architecture-specific CAS2 instruction used for version counting. We demonstrate our ABA prevention scheme by integrating it into an advanced nonblocking data structure, a lock-free dynamically resizable array. © 2011 ICST.

Publication Date

12-1-2011

Publication Title

ColiaborateCom 2011 - Proceedings of the 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing

Number of Pages

158-167

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.4108/icst.collaboratecom.2011.247161

Socpus ID

84857525317 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84857525317

This document is currently not available here.

Share

COinS