是否存在乐观无锁 FIFO 队列实现?
Is there any C++ implementation (source codes) of "optmistic approach to lock-free FIFO queues" algorithm?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(5)
爱本泡沫多脆弱2024-09-10 11:00:34
我想总结一下greyfade给出的答案,它基于http://www.drdobbs.com/high-performance-computing/212201163(文章的最后一部分),优化后的代码将是(进行一些修改以适应我的命名和编码约定):
`
template <typename T> class LFQueue {
private:
struct LFQNode {
LFQNode( T* val ) : value(val), next(nullptr) { }
T* value;
AtomicPtr<LFQNode> next;
char pad[CACHE_LINE_SIZE - sizeof(T*) - sizeof(AtomicPtr<LFQNode>)];
};
char pad0[CACHE_LINE_SIZE];
LFQNode* first; // for one consumer at a time
char pad1[CACHE_LINE_SIZE - sizeof(LFQNode*)];
InterlockedFlag consumerLock; // shared among consumers
char pad2[CACHE_LINE_SIZE - sizeof(InterlockedFlag)];
LFQNode* last; // for one producer at a time
char pad3[CACHE_LINE_SIZE - sizeof(LFQNode*)];
InterlockedFlag producerLock; // shared among producers
char pad4[CACHE_LINE_SIZE - sizeof(InterlockedFlag)];
public:
LFQueue() {
first = last = new LFQNode( nullptr ); // no more divider
producerLock = consumerLock = false;
}
~LFQueue() {
while( first != nullptr ) {
LFQNode* tmp = first;
first = tmp->next;
delete tmp;
}
}
bool pop( T& result ) {
while( consumerLock.set(true) )
{ } // acquire exclusivity
if( first->next != nullptr ) { // if queue is nonempty
LFQNode* oldFirst = first;
first = first->next;
T* value = first->value; // take it out
first->value = nullptr; // of the Node
consumerLock = false; // release exclusivity
result = *value; // now copy it back
delete value; // and clean up
delete oldFirst; // both allocations
return true; // and report success
}
consumerLock = false; // release exclusivity
return false; // queue was empty
}
bool push( const T& t ) {
LFQNode* tmp = new LFQNode( t ); // do work off to the side
while( producerLock.set(true) )
{ } // acquire exclusivity
last->next = tmp; // A: publish the new item
last = tmp; // B: not "last->next"
producerLock = false; // release exclusivity
return true;
}
};
`
另外一个问题是如何定义CACHE_LINE_SIZE?它随 CPU 的不同而变化,对吧?
随梦而飞#2024-09-10 11:00:34
这是我的无锁 FIFO 实现。
确保 T 的每一项都是 64 字节(Intel CPU 中的缓存行大小)的倍数,以避免错误共享。
此代码使用 gcc/mingw 编译,并且应该使用 clang 编译。它针对 64 位进行了优化,因此要使其在 32 位上运行需要进行一些重构。
https://github.com/vovoid/vsxu/blob/master /engine/include/vsx_fifo.h
vsx_fifo<my_struct, 512> my_fifo;
发送者:
my_struct my_struct_inst;
... fill it out ...
while (!my_fifo.produce(my_struct_inst)) {}
接收者:
my_struct my_struct_recv;
while(my_fifo.consume(my_struct_recv))
{
...do stuff...
}
反差帅2024-09-10 11:00:34
这个怎么样 lfqueue
这是跨平台、无限enqueue的线程安全队列,已经过测试多 deq、多 enq-deq 和多 enq。保证内存安全。
例如
int* int_data;
lfqueue_t my_queue;
if (lfqueue_init(&my_queue) == -1)
return -1;
/** Wrap This scope in other threads **/
int_data = (int*) malloc(sizeof(int));
assert(int_data != NULL);
*int_data = i++;
/*Enqueue*/
while (lfqueue_enq(&my_queue, int_data) == -1) {
printf("ENQ Full ?\n");
}
/** Wrap This scope in other threads **/
/*Dequeue*/
while ( (int_data = lfqueue_deq(&my_queue)) == NULL) {
printf("DEQ EMPTY ..\n");
}
// printf("%d\n", *(int*) int_data );
free(int_data);
/** End **/
lfqueue_destroy(&my_queue);
睫毛溺水了2024-09-10 11:00:34
如果您正在寻找一个好的无锁队列实现,Microsoft Visual Studio 2010 和 Visual Studio 2010 都可以。 Intel 的 Thread Building Blocks 包含一个与论文类似的良好 LF 队列。
~没有更多了~
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
Herb Sutter 在 Dr. Dobbs Journal 的有效并发专栏中介绍了这样一个队列。
编写无锁代码:正确的队列
Herb Sutter covered just such a queue as part of his Effective Concurency column in Dr. Dobbs Journal.
Writing Lock-Free Code: A Corrected Queue