有趣的是,我发现很多程序员错误地认为"无锁"只意味着"没有互斥的并发编程".通常,还存在一个相关的误解,即编写无锁代码的目的是为了获得更好的并发性能.当然,无锁的正确定义实际上是关于进度保证.无锁算法保证至少一个线程能够前进,无论其他线程正在做什么.
这意味着无锁算法永远不会有一个代码,其中一个线程依赖于另一个线程才能继续.例如,无锁代码不能具有线程A设置标志的情况,然后线程B在等待线程A取消设置标志时保持循环.这样的代码基本上实现了一个锁(或者我称之为伪装的互斥锁).
然而,其他情况更微妙,在某些情况下我真的无法确定算法是否符合无锁定的要求,因为"取得进步"的概念有时对我来说似乎是主观的.
其中一个例子是(备受好评的,afaik)并发库liblfds.我正在研究liblfds中多生产者/多消费者有界队列的实现 - 实现非常简单,但我无法确定它是否应该符合无锁定条件.
相关算法在lfds711_queue_bmm_enqueue.c.Liblfds使用自定义原子和内存障碍,但算法很简单,我可以用段落左右来描述.
队列本身是一个有界的连续数组(ringbuffer).共享read_index和write_index.队列中的每个插槽都包含一个用户数据字段和一个sequence_number值,它基本上类似于一个纪元计数器.(这避免了ABA问题).
PUSH算法如下:
write_index write_index % queue_size使用试图设置write_index为的CompareAndSwap循环在队列中保留一个插槽write_index + 1.sequence_index通过使其等于来更新插槽write_index + 1.实际的源代码使用自定义原子和内存障碍,因此为了进一步清楚这个算法,我简要地将它翻译成(未经测试的)标准C++原子以获得更好的可读性,如下所示:
bool mcmp_queue::enqueue(void* data)
{
int write_index = m_write_index.load(std::memory_order_relaxed);
for (;;)
{
slot& s = m_slots[write_index % m_num_slots];
int sequence_number = s.sequence_number.load(std::memory_order_acquire);
int difference = sequence_number - write_index;
if (difference == 0)
{
if (m_write_index.compare_exchange_weak(
write_index,
write_index + …我正在寻找一种方法来实现支持单个生产者和多个消费者的无锁队列数据结构.我看过Maged Michael和Michael Scott(1996)的经典方法,但他们的版本使用链表.我想要一个使用有界循环缓冲区的实现.什么东西使用原子变量？
另外,我不确定为什么这些经典方法是为需要大量动态内存管理的链表设计的.在多线程程序中,所有内存管理例程都是序列化的.我们不是通过将它们与动态数据结构结合使用来破坏无锁方法的好处吗？
我试图在英特尔64位架构上使用pthread库在C/C++中编写代码.
谢谢Shirish
我正在编写一个带有消费者线程和生产者线程的程序,现在看来队列同步在程序中是一个很大的开销,我找了一些无锁队列实现,但只发现了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()需要多长时间等.
我正在为嵌入式系统(Cortex M0)编写代码,并没有所有奢侈的互斥锁/自旋锁/等等.有没有一种简单的方法将数据添加到共享缓冲区(日志文件),该缓冲区将从Main()循环刷新到磁盘？
如果只有一个生产者(1个中断)和单个消费者(主循环),我可以使用一个简单的缓冲区,生产者增加'head',消费者增加'tail'.这将是非常安全的.但现在我有多个生产者(中断)似乎我被卡住了.
我可以为每个中断提供自己的缓冲区,并将它们组合在Main()中,但这需要大量额外的RAM和复杂性.
我在模式中使用QBufferReadWrite.一名工作人员QThread将数据推入缓冲区,另一名工作人员QThread从中读取数据
是QBuffer保证线程安全还是我需要派生QBuffer并添加互斥件？