实现无锁队列

参考：
Implementing Lock-Free Queues by John DD Valois
Department of Computer Science, Rensselaer Polytechnic Institute

此文章研究了使用无锁数据队列实现FIFO队列抽象数据类型。
这种无锁数据结构能够在不使用互斥机制的情况下同步并发进程的操作。

文章提出了 2 种基于链表和数组的新算法。针对与 Compare & Swap 指令相关的 ABA 问题提出了一种新的解决方案。

引言

多个进程并发访问共享的数据结构时，必须进行同步，以避免更新冲突。传统方法是使用互斥机制；
进程只能在代码的临界区内修改数据结构，在该临界区内，进程可以独占访问数据结构。

在多处理器系统中，临界区通常使用自旋锁进行保护。

我们将所有使用互斥机制的方法统称为锁定方法或基于锁的方法。

研究人员致力于探索无需互斥机制即可实现并发数据结构的方法。在异步环境中，这种无锁数据结构具有诸多优势。特别是，慢速或停止的进程不会阻碍其他进程访问该数据结构。

FIFO 队列是一种重要的抽象数据类型，是操作系统实现的核心。

队列在实现许多算法的并行版本中也很有用，例如快速排序和分支定界算法，通常作为向多个进程分配工作的一种手段而广泛使用。

目标是设计一个支持常规入队和出队操作的并发队列。在并发数据结构中，各个进程按顺序执行单个操作；然而，不同进程的操作可以同时进行。这不同于并行数据结构（进程间协作，同时执行一个或多个操作）和顺序数据结构（只能由单个进程访问）有所不同。

无锁数据结构可能具有两个有用的特性。

非阻塞（non-blocking）数据结构具有引言所述的特性，即：数据结构始终可访问，即使进程在操作期间速度减慢或停止。

而无等待（wait-free）数据结构还能确保进程不会饿死。

需要注意的是，基于锁的数据结构无法同时具备这两个特性，因为处于临界区内的进程可能会无限期地延迟所有操作（即可能达不到无等待）。

许多作者曾将“无锁”和“非阻塞”这两个术语视为同义词，但我们认为区分不需要互斥的算法和实际提供非阻塞特性的算法是有益的。本文将讨论的几种算法属于前者。

我们使用线性可行性（linearizability）作为数据结构的正确性条件。线性可行性意味着每个操作在某个时间点上都表现为瞬时发生，并且非并发操作的相对顺序得以保持。换句话说，对于非并发操作，数据结构的行为与其顺序对应物完全相同。并发操作可以以任何相对顺序执行。