FA-Stack: A Fast Array-Based Stack with Wait-Free Progress Guarantee
Yaqiong Peng, Zhiyu Hao · IEEE Transactions on Parallel and Distributed Systems · 2017
The prevalence of multicore processors necessitates the design of efficient concurrent data structures. Shared concurrent stacks are widely used as inter-thread communication structures in parallel applications. Wait-free stacks can ensure that each thread completes operations on them in a finite number of steps. This characteristic is valuable for parallel applications and operating systems, especially in real-time environments. Unfortunately, because wait-free algorithms are typically hard to design and considered inefficient, practical wait-free stacks are rare. In this paper, we present a practical, fast array-based concurrent stack with wait-free progress guarantee, named FA-Stack. A series of optimizations are proposed to bound the number of steps required to complete every push and pop operation. In addition, FA-Stack adopts a time-stamped scheme to reclaim memory. We use linearizability, a correctness condition for concurrent data structures, to prove that FA-Stack is a wait-free linearizable stack with respect to the Last in First Out (LIFO) semantics. Our evaluation with representative benchmarks shows that FA-Stack is an efficient wait-free stack. For example, compared to Sim-Stack (a state-of-the-art wait-free stack), FA-Stack improves the throughput of halfhalf benchmark by upto 2.4×.