| |
Click here for full text:
An Almost Non-Blocking Stack
Boehm, Hans-J.
HPL-2004-105
Keyword(s): stack; non-blocking; lock-free; linked list; mostly non-blocking
Abstract: 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
Back to Index
|
Printable version
