MPMCQueue是一个用C++11编写的有界多生产者多用户无锁队列。
示例代码MPMCQueue<int>q(10);autot1=std::thread([&]{intv;q.pop(v);std::cout<<"t1"<<v<<"\n";});autot2=std::thread([&]{intv;q.pop(v);std::cout<<"t2"<<v<<"\n";});q.push(1);q.push(2);t1.join();t2.join();使用MPMCQueue<T>(size_tcapacity);
Constructsanew MPMCQueue holdingitemsoftype T withcapacity capacity.
voidemplace(Args&&...args);
Enqueueanitemusinginplaceconstruction.Blocksifqueueisfull.
booltry_emplace(Args&&...args);
Trytoenqueueanitemusinginplaceconstruction.Returns true onsuccessand false ifqueueisfull.
boolpush(constT&v);
Enqueueanitemusingcopyconstruction.Blocksifqueueisfull.
template<typenameP>boolpush(P&&v);
Enqueueanitemusingmoveconstruction.Participatesinoverloadresolutiononlyif std::is_nothrow_constructible<T,P&&>::value==true.Blocksifqueueisfull.
booltry_push(constT&v);
Trytoenqueueanitemusingcopyconstruction.Returns true onsuccessand false ifqueueisfull.
template<typenameP>booltry_push(P&&v);
Trytoenqueueanitemusingmoveconstruction.Participatesinoverloadresolutiononlyif std::is_nothrow_constructible<T,P&&>::value==true.Returns true onsuccessand false ifqueueisfull.
voidpop(T&v);
Dequeueanitembycopyingormovingtheiteminto v.Blocksifqueueisempty.
booltry_pop(T&v);
Trytodequeueanitembycopyingormovingtheiteminto v.Return true onsucessand false ifthequeueisempty.
所有操作都是线程安全的，除了构造和析构函数。
实际原理Enqeue:
Acquirenextwrite ticket from head.Waitforour turn (2*(ticket/capacity))towrite slot (ticket%capacity).Set turn=turn+1 toinformthereaderswearedonewriting.Dequeue:
Acquirenextread ticket from tail.Waitforour turn (2*(ticket/capacity)+1)toread slot (ticket%capacity).Set turn=turn+1 toinformthewriterswearedonereading.参考资料:
DaveDice. PTLQueue:ascalablebounded-capacityMPMCqueue.DmitryVyukov. BoundedMPMCqueue.MassimilianoMeneghinetal. Performanceevaluationofinter-threadcommunicationmechanismsonmulticore/multithreadedarchitectures.OleksandrOtenko. US8607249B2:Systemandmethodforefficientconcurrentqueueimplementation.PaulE.McKenney. MemoryBarriers:aHardwareViewforSoftwareHackers.
评论