我正在编写一个带有消费者线程和生产者线程的程序,现在看来队列同步在程序中是一个很大的开销,我找了一些无锁队列实现,但只发现了Lamport的版本和PPoPP的改进版本' 08:
enqueue_nonblock(data) {
if (NULL != buffer[head]) {
return EWOULDBLOCK;
}
buffer[head] = data;
head = NEXT(head);
return 0;
}
dequeue_nonblock(data) {
data = buffer[tail];
if (NULL == data) {
return EWOULDBLOCK;
}
buffer[tail] = NULL;
tail = NEXT(tail);
return 0;
}
两个版本都需要为数据预先分配的数组,我的问题是,是否存在使用malloc()动态分配空间的任何单用户单生产者无锁队列实现？
另一个相关的问题是,如何测量队列同步中的确切开销？比如pthread_mutex_lock()需要多长时间等.
我正在读TM,而我正在读的其中一篇论文说[ 1 ]:
实际上,这是两个非阻塞算法,无障碍DSTM和无锁FSTM,在过去十年中重新激活了STM研究.
我的印象是锁意味着阻碍.显然,我错了......
有什么条款"之间的差异无锁 "和" 梗阻自由 "？
我试图理解x86/x64上CAS的低级机制,我非常感谢一些帮助/见解.
我一直在考虑的原因是我试图推理指数退避,并原则上弄清楚退避延迟的正确单个单位应该是什么.
如果我看一个没有锁定的freelist基准测试,没有指数退避,我看到线程数量增加,性能迅速变平.
Release 7 Lock-Free Freelist Benchmark #1
M
N
S
L3U
L2U L2U
L1D L1D
L1I L1I
P P
L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 0 1 310134488,31013449,0,1.00
0 1 0 1 136313300,6815665,38365,0.22
0 1 0 1 136401284,6820064,50706,0.22
1 1 1 1 111134328,2778358,23851,0.09
0 0 1 1 334747444,16737372,2421,0.54
1 1 1 1 111105898,2777647,40399,0.09
我们知道,可以发生实时锁定,每个线程阻止其他线程进展.
我的原始 - 我相信现在错了 - 认为CAS正在干扰CAS.我的意思是,CAS指令本身会破坏性地与另一个CAS碰撞,如果它们同时发生的话.两者都会失败.(推荐,因为我在脑海中思考以太网).
这"显然"解释了结果 - 所有CAS指令同时运行,很少有机会在被破坏性中断之前完全执行.
考虑到这一点后,我相信现在情况并非如此.CAS指令实际上并不具有故障模式.它会告诉你目的地等于或不等于比较.就这样.它没有回来说"哦,对不起,碰到别人".
破坏性干扰正在发生,但它发生在数据结构算法本身的更高层次.当我们从空闲列表推送或弹出时,我们实际上正在尝试交换.我们需要目标稳定足够长的时间以便我们可以阅读它,做我们需要做的任何工作,然后找到它不变,这样我们就可以完成我们的推/弹.
如果其他线程保持CASing,目标不稳定 - 它会不断变化 - 我们不得不重试我们的操作.
但现在我很困惑.
我们看到的是单个线程执行大约3000万次推/弹操作.目的地必须在其中一个操作期间保持稳定,以使操作成功,因此我们看到有3000万个"插槽".如果我们有两个线程,那么我们可以拥有的最大理论性能是每个线程1500万个操作; 每个线程使用一半的插槽. …
谷歌为"锁定免费载体"的第一个结果是Damian Dechev,Peter Pirkelbauer和Bjarne Stroustrup描述理论无锁向量的研究论文.这个或任何其他无锁向量是否已实现？
我需要原子地读/写16个字节.我只使用cmpxchg16进行写入,cmpxchg16可以在所有x64处理器上使用,除了我认为对于一个不起眼的AMD处理器.
现在的问题是对齐的16字节值,只使用cmpxchg16进行修改(它就像一个完整的内存屏障)是否有可能读取一个半字节数据和一半新数据的16字节位置？
只要我用SSE指令读取(因此线程不能在读取过程中被中断),我认为读取不可能(甚至在多处理器numa系统中)看不一致的数据.我认为它必须是原子的.
我假设当执行cmpxchg16时,它会原子地修改16个字节,而不是通过编写两个8字节块,其他线程可能在其间进行读取(老实说,我不知道它是如何工作的,如果它不是原子的.)
我对吗？如果我错了,有没有办法在不诉诸锁定的情况下进行原子16字节读取？
注意:这里有几个类似的问题,但它们没有处理只用cmpxchg16进行写入的情况,所以我觉得这是一个单独的,没有答案的问题.
编辑:其实我认为我的推理是错误的.SSE加载指令可以作为两个64位读取执行,并且cmpxchg16可以在两次读取之间由另一个处理器执行.
我正在尝试将std::strings放入boost::lockfree::queues中,以便我的线程可以使用新数据相互更新.
当我尝试使用时boost::lockfree::queue<std::string> updated_data;,g++说:
在'class boost :: lockfree :: queue>'的实例化中:
错误:静态断言失败:(boost :: has_trivial_destructor :: value)
错误:静态断言失败:(boost :: has_trivial_assign :: value)
我一般都会看到这些错误意味着什么,但我自己也没有希望自己解决这个问题,因为我几乎是c ++的新手.
有没有另一种方法在线程之间传递文本数据lockfree？如果不是,请告诉我如何把std::string成boost::lockfree::queue.
我找不到基于锁的原子与无锁原子之间的语义差异.据我所知,就语言而言,差异在语义上毫无意义,因为语言不提供任何时间保证.我能找到的唯一保证是内存排序保证,这两种情况看起来都是一样的.
即,除了打电话is_lock_free或者atomic_is_lock_free是有可能写出其行为实际上是受原子公司是否无锁一个明确的计划？
这些功能甚至具有语义含义吗？或者它们只是编写响应式程序的实用黑客,即使语言从未提供过时间保证？
在我尝试开发一个线程安全的C++弱指针模板类时,我需要检查一个指示对象仍处于活动状态的标志,如果是,则增加对象的引用计数,我需要以原子方式执行这两个步骤.
我知道编译器提供的内在函数的存在,例如_InterlockedCompareExchange()和_InterlockedIncrement().但我想要的是一个interlockedCompareIncrement()函数,有没有一种有效的方法来使用其他原语来模拟这个内在函数,至少在Windows x86平台上？
我是多线程编程的新手,我只知道最常见的Producer-Consumer-Queue.我正在使用boost c ++库,我不知道是否更好地使用boost :: lockfree :: queue或使用`mutex`和`condition_variable`的std :: queue周围的包装类.
哪里更好地使用无锁数据结构哪里更好是使用基于`mutex`和`condition_variables`的简单实现？
请考虑以下代码:
struct payload
{
std::atomic< int > value;
};
std::atomic< payload* > pointer( nullptr );
void thread_a()
{
payload* p = new payload();
p->value.store( 10, std::memory_order_relaxed );
std::atomic_thread_fence( std::memory_order_release );
pointer.store( p, std::memory_order_relaxed );
}
void thread_b()
{
payload* p = pointer.load( std::memory_order_consume );
if ( p )
{
printf( "%d\n", p->value.load( std::memory_order_relaxed ) );
}
}
C++是否对线程a中的fence与线程b中的consume操作的交互做出了任何保证？
我知道在这个例子中我可以用商店版本替换fence + atomic存储并让它工作.但我的问题是关于使用栅栏的这种特殊情况.
阅读标准文本我可以找到关于释放围栏与获取围栏的交互以及具有获取操作的释放围栏的交互的条款,但没有关于释放围栏和消费操作的交互的内容.
我认为,用一个获取取代消费将使代码符合标准.但据我了解处理器实现的内存排序约束,我应该只需要线程b中较弱的"消耗"排序,因为内存屏障强制线程a中的所有存储在存储到指针之前可见,并且读取有效负载取决于从指针读取.
标准是否同意？