A scalable lock-free stack algorithm

作者：Hendler Danny^*; Shavit Nir; Yerushalmi Lena

来源：Journal of Parallel and Distributed Computing, 2010, 70(1): 1-12.

DOI：10.1016/j.jpdc.2009.08.011

• Synchronization
• Shared-memory
• Lock-freedom
• Stack
• Elimination
• Compare-and-swap

The literature describes two high performance concurrent stack algorithms based on combining funnels and elimination trees. Unfortunately, the funnels are linearizable but blocking and the elimination, trees are non-blocking but not linearizable. Neither is used in practice since they perform well only at exceptionally high loads. The literature also describes a simple lock-free linearizable stack algorithm that works at low loads but does not scale as the load increases. The question of designing a stack algorithm that is non-blocking, linearizable, and scales well throughout the concurrency range, has thus remained open.
This paper presents such a concurrent stack algorithm. It is based on the following simple observation: that a single elimination array used as a backoff scheme for a simple lock-free stack is lock-free, linearizable, and scalable. As our empirical results show, the resulting elimination-backoff stack performs as well as the simple stack at low loads, and increasingly outperforms all other methods (lock-based and non-blocking) as concurrency increases. We believe its simplicity and scalability make it a viable practical alternative to existing constructions for implementing concurrent stacks.

• 出版日期2010-1