绝代码农 发表于 2021-7-17 22:18:09

一个高性能无锁非阻塞链表队列

这个是一个用c++ 11标准实现的无锁非阻塞链表队列,通过增加一个dummy节点,解偶合链表头指针和尾指针。使得当只有一个生产者和一个消费者时,进队和出队都无需加锁,进队操作的是尾指针,出队操作的是头指针,互不干涉。对于多个生产者且单个消费者时,只需要对尾指针加锁保护,而头指针不需要加锁。反之,对于单生产者且多消费者时,只需要对头指针加锁保护而尾指针不需要加锁。如果是多生产者和多消费者,那么头尾指针各自加锁保护。同时,队列内部会对节点进行缓存,避免重复的内存分配以提高性能。

在双cpu的机器上测试,性能比boost实现的单生产者和单消费者队列boost::lockfree::spsc_queue快6到7倍。

//对模板使用别名,方便使用(说明:NullMutex是一个空锁,是一个自旋锁spin_lock)

//单生产者和单消费者
   template<typename VALUE_TYPE>usingspsc_queue = TDoubleLockLinkedNonBlockingQueue<VALUE_TYPE, NullMutex, NullMutex>;

   //多生产者和单消费者
   template<typename VALUE_TYPE>usingmpsc_queue = TDoubleLockLinkedNonBlockingQueue<VALUE_TYPE, spin_lock, NullMutex>;

   //单生产者和多消费者
   template<typename VALUE_TYPE>usingspmc_queue = TDoubleLockLinkedNonBlockingQueue<VALUE_TYPE, NullMutex,spin_lock>;

   //多生产者和多消费者
   template<typename VALUE_TYPE>usingmpmc_queue = TDoubleLockLinkedNonBlockingQueue<VALUE_TYPE, spin_lock, spin_lock>;

//使用例子:

//定义一个单生产者和单消费者队列
spsc_queue<int> queue;
//进队
queue.push(1);

//出队
int value;
if(queue.pop(value))
{
   printf("value = %d \n",value);
}

下文测试例子在E5-2620 v3 双cpu的机器上的运行结果:

////////////////////////////////////////////////////////////////////////////
单生产者--单消费者模型测试 数据请求:

NullMutex TDoubleLockLinkedNonBlockingQueue :花时 3.010000 秒

boost::lockfree::spsc_queue :花时 19.312000 秒
//代码及测试例子下载:
http://www.oschina.net/code/snippet_2504104_55974

文档来源:开源中国社区https://my.oschina.net/u/2504104/blog/671020
页: [1]
查看完整版本: 一个高性能无锁非阻塞链表队列