Treiber stack
The Treiber stack algorithm is a scalable lock-free stack utilizing the fine-grained concurrency primitive compare-and-swap. It is believed that R. Kent Treiber was the first to publish it in his 1986 article "Systems Programming: Coping with Parallelism". Basic principle The basic principle for the algorithm is to only add something new to the stack once you know the item you are trying to add is the only thing that has been added since you began the operation. This is done by using compare-and-swap. Pushing an item to the stack is done by first taking the top of the stack (old head) and placing it after your new item to create a new head. You then compare the old head to the current head. If the two are matching then you can swap old head to the new one, if not then it means another thread has added an item to the stack, in which case you must try again. When popping an item from the stack, before returning the item you must check that another thread has not added a new item since the operation began. Correctness In some languages—particularly, those without garbage collection—the Treiber stack can be at risk