An Almost Non-Blocking Stack

Boehm, Hans-J.

HP Development Company

关键词: stack;    non-blocking;    lock-free;    linked list;    mostly non-blocking;   

RP-ID  :  HPL-2004-105

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Non-blocking data structure implementations can be useful for performance and fault-tolerance reasons. And they are far easier to use correctly in a signal- or interrupt-handler context. We describe a weaker class of "almost non-blocking" data structures, which block only if more than some number N of threads attempt to simultaneously access the same data structure. We argue that this gives much of the benefit of fully non-blocking data structures, particularly for signal or interrupt handlers. We present an almost non-blocking linked stack implementation which is efficiently implementable even on hardware providing a single word compare-and-swap operation, while potentially providing the same interface as a well-known fully non-blocking solution, which relies on a double-width compare-and-swap instruction. By making a platform-dependent choice between these, we can implement a signal-handler-safe stack or free-list abstraction that is both portable and exhibits uniformly high performance with any flavor of compare-and-swap instruction. Notes: Copyright ACM 2004. To be published in the Symposium on the Principles of Distributed Computing (PODC '04), 25-28 July 2004, St. Johns, Newfoundland, Canada 10 Pages