7th International Conference on Collaborative Computing: Networking, Applications and Worksharing

Research Article

The ABA Problem in Multicore Data Structures with Collaborating Operations

Download712 downloads
  • @INPROCEEDINGS{10.4108/icst.collaboratecom.2011.247161,
        author={Damian Dechev},
        title={The ABA Problem in Multicore Data Structures with Collaborating Operations},
        proceedings={7th International Conference on Collaborative Computing: Networking, Applications and Worksharing},
        publisher={IEEE},
        proceedings_a={COLLABORATECOM},
        year={2012},
        month={4},
        keywords={nonblocking synchronization collaborating threads multicore computing},
        doi={10.4108/icst.collaboratecom.2011.247161}
    }
    
  • Damian Dechev
    Year: 2012
    The ABA Problem in Multicore Data Structures with Collaborating Operations
    COLLABORATECOM
    ICST
    DOI: 10.4108/icst.collaboratecom.2011.247161
Damian Dechev1,*
  • 1: University of Central Florida
*Contact email: damian.dechev@gmail.com

Abstract

The ABA 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.