Sil*_*ler 18 c++ algorithm concurrency multithreading lock-free
有趣的是,我发现很多程序员错误地认为"无锁"只意味着"没有互斥的并发编程".通常,还存在一个相关的误解,即编写无锁代码的目的是为了获得更好的并发性能.当然,无锁的正确定义实际上是关于进度保证.无锁算法保证至少一个线程能够前进,无论其他线程正在做什么.
这意味着无锁算法永远不会有一个代码,其中一个线程依赖于另一个线程才能继续.例如,无锁代码不能具有线程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 + 1,
std::memory_order_acq_rel
))
{
break;
}
}
if (difference < 0) return false; // queue is full
}
// Copy user-data and update sequence number
//
s.user_data = data;
s.sequence_number.store(write_index + 1, std::memory_order_release);
return true;
}
现在,一个想要从插槽中弹出元素的线程read_index将无法这样做,直到它观察到插槽的sequence_number等于read_index + 1.
好的,所以这里没有互斥体,算法可能表现良好(它只是PUSH和POP的一个CAS),但这是否无锁？我不清楚的原因是因为如果队列被观察为满或空,则PUSH或POP可能总是失败,因此"进取"的定义似乎是模糊的.
但令我质疑的是,PUSH算法基本上保留了一个插槽,这意味着在推送线程更新序列号之前,插槽永远不能被POP.这意味着想要弹出值的POP线程取决于已完成操作的PUSH线程.否则,POP线程将始终返回,false因为它认为队列是EMPTY.对我而言,这实际上是否符合"取得进步"的定义似乎值得商榷.
通常,真正无锁的算法涉及一个阶段,其中抢占线程实际上试图在完成操作时辅助另一个线程.因此,为了真正无锁,我认为观察正在进行的PUSH的POP线程实际上需要尝试并完成PUSH,然后才能执行原始的POP操作.如果POP线程在PUSH正在进行时简单地返回队列为EMPTY,则POP线程基本上被阻塞,直到PUSH线程完成操作.如果PUSH线程死亡,或进入休眠状态1000年,或以其他方式被安排被遗忘,POP线程除了连续报告队列是EMPTY之外什么都不做.
那么这适合无锁的定义吗？从一个角度来看,你可以说POP线程总是可以取得进展,因为它总是可以报告队列是EMPTY(这至少是我猜的某种形式的进展.)但对我来说,这并没有真正取得进展,因为队列被观察为空的唯一原因是因为我们被并发的PUSH操作阻止了.
所以,我的问题是:这个算法真的无锁吗？或者索引预订系统基本上是伪装的互斥体？
Bee*_*ope 11
这个队列数据结构并不是我认为最合理的定义的严格锁定.这个定义是这样的:
如果任何线程可以在任何点无限期地挂起,同时仍然保留剩余线程可用的结构,则结构是无锁的.
当然,这意味着可用的合适定义,但对于大多数结构而言,这非常简单:结构应继续遵守其合同并允许按预期插入和移除元素.
在这种情况下,成功递增m_write_increment但尚未写入的线程使s.sequence_number容器处于即将成为不可用状态的状态.如果这样的线程被杀害,容器将最终报告既"全"和"空",以push和pop分别违反了固定大小的队列的合同.
还有就是这里隐藏的互斥体(组合m_write_index和相关的s.sequence_number) -但它基本上就像每个元素互斥.因此,只有当你循环并且新的编写器试图获取互斥锁时,失败才会变得明显,但实际上所有后续编写者都有效地未能将其元素插入队列,因为没有读者会看到它.
现在这并不意味着这是并发队列的错误实现.对于某些用途,它可能主要表现为无锁.例如,这种结构可能具有真正无锁结构的大多数有用的性能属性,但同时它缺少一些有用的正确性属性.基本上,无锁定一词通常意味着一大堆属性,其中只有一部分通常对任何特定用途都很重要.让我们逐个看一下它们,看看这个结构是如何做的.我们将它们大致分为性能和功能类别.
无竞争或"最佳情况"表现对许多结构都很重要.虽然您需要并发结构以确保正确性,但您通常仍会尝试设计应用程序,以便将争用保持在最低限度,因此无争用成本通常很重要.一些无锁结构在这里有所帮助,通过减少无竞争快速路径中昂贵的原子操作的数量,或避免a syscall.
这个队列实现在这里做了一个合理的工作:只有一个"绝对昂贵"的操作:compare_exchange_weak和一些可能很昂贵的操作(memory_order_acquire加载和memory_order_release存储)1,以及其他一些开销.
相比之下,std::mutex这意味着像锁定的一个原子操作和解锁的另一个原子操作,在Linux上实际上,pthread调用也有不可忽略的开销.
所以我希望这个队列在无竞争的快速路径中表现得相当好.
无锁结构的一个优点是,当结构严重争用时,它们通常允许更好的缩放.这不一定是固有的优势:一些具有多个锁或读写锁的基于锁的结构可能表现出与某些无锁方法匹配或超过某些无锁方法的扩展,但通常情况下,无锁结构表现出更好的扩展性.一个简单的单锁定规则 - 所有替代方案.
在这方面,该队列合理地执行.该m_write_index变量是由原子所有读者更新,并且将成为一个争论的焦点,但行为应该是合理的,只要底层硬件CAS实现是合理的.
请注意,队列通常是一个相当差的并发结构,因为插入和删除都发生在相同的位置(头部和尾部),因此争用是结构定义中固有的.将此与并发映射进行比较,其中不同的元素没有特定的有序关系:如果访问不同的元素,这样的结构可以提供有效的无争用同时突变.
与上面的核心定义(以及功能保证)相关的无锁结构的一个性能优点是,正在改变结构的线程的上下文切换不会延迟所有其他的mutator.在负载很重的系统中(特别是当可运行线程>>可用内核时),线程可能会被切换出数百毫秒或几秒.在此期间,任何并发的mutator都会阻塞并产生额外的调度成本(或者它们会旋转,这也可能导致不良行为).尽管这种"不合时宜的调度"可能很少见,但是当它确实发生时,整个系统可能会引起严重的延迟峰值.
无锁结构避免了这种情况,因为没有"关键区域",其中线程可以被上下文切换并随后阻止其他线程的前进.
此结构在此区域提供部分保护 - 具体取决于队列大小和应用程序行为.即使在m_write_index更新和序列号写入之间的关键区域中切换了一个线程,其他线程也可以继续到push队列中的元素,只要它们不会从停顿中一直包裹到正在进行的元素中.线.线程也可以是pop元素,但仅限于正在进行的元素.
虽然push行为可能不是高容量队列的问题,但pop行为可能是一个问题:如果队列的吞吐量高于线程上下文切换的平均时间,以及平均完整性,队列将很快出现即使在正在进行的元素之外添加了许多元素,也清空所有使用者线程.这不受队列容量的影响,而只受应用程序行为的影响.这意味着当发生这种情况时,消费者方可能完全失速.在这方面,队列看起来根本没有锁定!
在无锁结构的优点下,它们可以安全地被线程使用,这些线程可以被异步地取消,或者可以在关键区域中异常地终止.在任何点取消线程都会使结构处于一致状态.
如上所述,这不是该队列的情况.
相关的优点是通常可以从中断或信号中检查或改变无锁结构.在中断或信号与常规进程线程共享结构的许多情况下,这很有用.
此队列主要支持此用例.即使在另一个线程处于关键区域时发生信号或中断,异步代码仍然可以push是队列中的一个元素(以后只能通过使用线程来看到),并且仍然可以pop是队列之外的元素.
这种行为并不像真正的无锁结构那样完整:设想一个信号处理程序,它可以告诉剩余的应用程序线程(除了被中断的应用程序线程)静默,然后排出队列中剩余的所有元素.使用真正的无锁结构,这将允许信号处理程序完全耗尽所有元素,但是如果线程在关键区域中断或切换,则此队列可能无法执行此操作.
1特别是在x86上,这只会对CAS使用原子操作,因为内存模型足够强大,可以避免对其他操作使用原子或栅栏.最近的ARM也可以相当有效地获取和发布.
小智 7
我是liblfds的作者。
OP对这个队列的描述是正确的。
它是库中并非无锁的单个数据结构。
队列文档中对此进行了描述。
“尽管必须理解，这实际上不是一个无锁的数据结构。”
这个队列是Dmitry Vyukov（1024cores.net）的一个想法的实现，当我使测试代码正常工作时，我才意识到它不是无锁的。
到那时它已经开始工作了，所以我将其包括在内。
我确实有删除它的想法，因为它不是无锁的。