简介
并发FIFO队列在并行程序以及操作系统中有广泛的应用，为了确保程序的正确性，在并发访问共享队列的时候必须进行同步化。举个例子，比如在生产者与消费者模型的应用中，在没有产品时，消费者就必须要等到生产者生产出产品后才能运行。对于像FIFO队列这样的并发数据结构的算法，一般分成两种：阻塞和非阻塞，阻塞算法使用一个延迟的进程去避免更快进程在不确定的共享内存中完成操作，这个延迟同步进程可以看成锁。非阻塞算法保证在一个或多个活跃进程尝试操作共享数据结构的时候，某些操作将在有限的时间周期内完成，不会发生因为像抢锁所形成的死锁情况。在同步多进程系统中，尤其是多进程的情况，阻塞算法中，当一个进程在不适当的时间被挂起或延迟的时候，阻塞算法的性能将会严重下降。延迟可能的原因有进程的抢占式调度，页面中断(引起页面置换)，以及缓存未命中。但是，在面对以上问题，非阻塞算法鲁棒性更好,更健壮。
许多研究者对于并发FIFO队列使用无锁算法,Hwang和Briggs,Stong,Sites均描述了无锁算法基于compare-and-swap的实现(把共享内存地址,一个保留值,以及一个 新值当作参数，如果共享内存中目前保存着保留值，那么它将被标记为新值，返回一个布尔值标记是否发生交换，显然这个预留值的设定也是一门学问）。但这个算法不是特别详细，他们 省略了一些详细内容，比如处理单元素队列，空队列以及并发的出队，入队行为。Lamport描述了一个无等待算法（非阻塞和无饥俄性算法，该算法保证每一个活动进程在有限的时间片内得到处理），这个算法使用入队器和出队器限制并发。
Gottlieb和Mellor-Crummey描述了一个无锁但是不是非阻塞的算法：他们不使用锁的机制，但是他们允许一个慢的进程去延迟不确定的较快进程。
Treiber描述了一个非阻塞的算法，但是效率低，一个出队操作花费的时间与队列元素个数成正比.许多专家等提议使用 一般的方法，对于非阻塞算法，使用版本序列或者基于锁控制来实现。通常而言，这种的效果相比特殊方法是低效率的。
Massalin和Pu描述了一种基于double-compare-and-swap的无锁算法，该算法可以同时操作两个任意的内存位置，但是似乎只能在Motorola 68000之后的处理器才能使用， Herlihy和Wing描述了一种基于数组的算法，但是该算法对于数组的需求不确定。Valois描述了一种基于数组的算法，需要一个未对齐的compare-and-swap或者double-compare-and-swap`。
Stone描述了一个无锁算法，但是它是非线性(如果在数据结构之外给一个外部的观察者，观察对数据结构的操作，在某时刻对它的调用和响应都能观察到立即产生的影响，就说这个数据结构的实现是可线性的)和阻塞的。因其是非线性的，所以当一个慢的入队器观察到一个空的队列，但是某个快的入队操作已经随后加入了一个元素，甚至可能出现这个已经入队元素永远不出队。因为一个慢的入队操作能够通过其他不确定的进程延迟出队操作，所以它也是非阻塞的。我们的实验同时也揭露存在竞争条件，比如一个慢的入队操作，以及一个快的入队操作和一个快的出队操作，将可能造成某个入队元素丢失(快的出队操作已经执行，慢的出队操作又执行了一次，所以造成了某个入队的元素被莫名其妙移除),这就是两个出队操作存在竞争的原因。Stone也描述了一个基于循环单链表的队列，该算法使用锚点指针代替头尾指针管理队列，我们的实验同样揭露存在一个竞争条件：慢的出队操作进程能造成入队元素永久丢失。
Prakash,Lee 和Johnson描述了一种线性非阻塞算法，它需要入队进程和出队进程在决定更新队列的状态之前获取它的一个快照，这个算法通过允许较快进程去完成(而不是等待)较慢进程的操作代 替阻塞来达到非阻塞的性能。 Valois描述了一种基于列表的非阻塞算法，为了避免Prakash等人的快照算法引起的争论， 该算法通过在单向链表的头部(出队端)添加一个虚拟节点来允许更多的并发，因此也简化了单元素队列和空队列的情况。但是，该算法为了安全的释放和重用出队节点允许尾指针指向头指针，如果一个尾指针指向一个出队节点，但这个出队节点被一进程释放，这个链表将被截断，随后入队的元素都会丢失。由于内存是有限的资源，禁止内存重新使用是不现实的。Valois因此建议一个特殊的机制去释放和分配内存，该机制对每一个节点使用了一个引用计数器，每当进程创建一个指针指向节点时，该节点的引用计数器自动加1。在不打算访问这个被访问过节点以后，他的引用计数器会自动的减少。除此之外，还有来自进程局部变量的临时链接，每一个引用计数器反映了在这个问题中指向这个数据结构节点的链接数。 对于队列，他们是头指针，尾指针，以及链表的链接数。当一个节点没有指针或者临时变量指向他的时候，该节点将被释放。
未完待续