Name
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1145/1011767.1011774 | PODC |
Keywords | Field | DocType |
non-blocking data structure,compare-and-swap instruction,non-blocking data structure implementation,single word compare-and-swap operation,non-blocking solution,free-list abstraction,high performance,double-width compare-and-swap instruction,data structure,fault-tolerance reason,fault tolerant,stack,memory allocation,compare and swap,linked list,interrupt handler,lock free | Interrupt,Data structure,Non-blocking algorithm,Computer science,Interrupt handler,Call stack,Parallel computing,Thread (computing),Stack trace,Compare-and-swap,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-58113-802-4 | 5 | 0.82 |
References | Authors | |
12 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans Boehm | 1 | 632 | 38.83 |