1. 关注

  2. 订阅

    订阅到:

无锁数据结构:队列

王老虎   发布在 2017-01-10   

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

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

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

经典队列

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

一个标准的简单队列

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

(有话说)我的个性宣言

  一小贩街边卖枣,遭城管驱赶,遂换至一偏僻小路继续摆摊。  路过一老人,对小贩说“枣不错,来三斤。当年我还做八路的时候,就推着这么一车枣在敌占区边卖边刺探敌情,转眼六十年过去了。”  小贩不解的问,“大爷,那时候鬼子咋没赶你呢?”  老人怒道“卖个枣有啥赶的,鬼子再浑蛋也不至于啊”

社交评论

您好,请登录后进行评论。点击 登录注册新账号
您好!
    五色云科技