多线程无锁循环队列

本文主要是介绍多线程无锁循环队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转自：https://blog.csdn.net/weixin_40825228/article/details/80783860

1、Lamport提出的无锁SPSC队列。

在其论文【论文】中证明了，在遵守【顺序一致性】内存模型的计算机中，单生产者单消费者（SPSC）先进先出队列中的锁是可以去除的，从而得到了一个无锁队列，并第一次给出了并发无锁先进先出（Concurrent Lock-free FIFO,CLF）队列的实现。通过去除队列中的锁，生产者、消费者可以并发的访问队列，从而提高了系统的并发执行度。

一种实现：

#define DEFAULT_SIZE 30
template<typename T>
class CircuBuffer
{
public:
CircuBuffer(unsigned size):
size_(size)
{
writeIndex_=0;
readIndex_=0;
buffer_=new T[size_];
}
CircuBuffer():
size_(DEFAULT_SIZE)
{
writeIndex_=0;
readIndex_=0;
buffer_=new T[size_];
}
~CircuBuffer()
{
delete [] buffer_;
}
unsigned getReadIndex() const
{
return readIndex_;
}
unsigned getWriteIndex() const
{
return writeIndex_;
}
bool isEmpty()
{
return writeIndex_==readIndex_;
}
bool isFull()
{
return (readIndex_+1)%size_==writeIndex_;
}
bool pushAnEle(T element)
{
//队列不为满
if(!isFull())
{
buffer_[writeIndex_]=element;
writeIndex_=(writeIndex_+1)%size_;
return true;
}
else
{
return false;
}
};
T* getAnEle()
{
//队列不为空
if (!isEmpty())
{
T* temp=buffer_+readIndex_;
readIndex_=(readIndex_+1)%size_;
return temp;
}
else
{
return nullptr;
}
}
private:
//写指针
unsigned writeIndex_;
//读指针
unsigned readIndex_;
//环形队列首地址
T* buffer_;
//环形队列的尺寸
unsigned size_;
};

往SPSC型的队列中放入数据的生产者改变【写指针】，消费者改变【读指针】。然而，生产者放入数据至队列中需要判满，这就需要读取【读指针】；同理消费者从队列中取数据，需要判空，这也需要读取【写指针】。若读指针与写指针在同一缓存行，而读写线程分别在不同的核上，这在多核平台上会产生严重的缓存颠簸。所谓的缓存颠簸是运行于多个核上的线程同时修改位于某个缓存行中的不同位置的数据时，导致该缓存行频繁地在多个核上被写无效的现象，这种现象会极大地损害系统的性能。

2、对于Lamport提出的无锁SPSC队列的改进型——FastForward队列。

第一节阐明了Lamport提出的无锁队列存在以下两个缺点：<1>由于生产者与消费者需要使用共享变量头指针与尾指针来同步信息，保存有头指针与尾指针的cacheline会频繁的分别被生产者与消费者修改，产生缓存颠簸，伤害系统的性能；<2>Lamport的CLF队列不能运行在支持弱内存一致性模型的机器中。

【改进1】针对上述去缺点，Join Giacomoni等人提出了针对缓存友好的CLF队列【缓存友好的CLF队列】。

针对缺点2的改进的CLF队列的一种实现：