无锁数据结构:队列


队列多种多样,不同之处在于消息生产者、消费的数量不同;在于是基于预先分配的buffer有界队列,还是基于List的无界队列;在于是否支持优先级;在于是无锁非阻塞,还是有锁;在于严格遵守FIFO,公平还是非公平等等。更多细节参见Dmitry Vyukov的文章。

众所周知,更多特定的队列需求,势必需要更加有效的算法。本文中,只考虑队列最常见的版本,多个生产者对多个消费者,无界并发队列,因此不考虑优先级。

我猜队列想必是研究人员最喜欢的数据结构,因为它简单,但却比栈复杂,因为它有两端而非一端。正是因为有两端,那么一个有趣的问题就出来了:如何在多线程环境下管理它们呢?各种版本的队列算法纷纷发表,想要做一个全面的描述是不可能的了。我提炼其中一些最流行的算法简要介绍一下,首先从经典队列开始。

经典队列

经典队列是一个带有两端,即头和尾的列表。从头部读取数据,从尾部写入数据。

一个标准的简单队列

下面的代码拷贝自《无锁数据结构:简介》