问题 “无锁”的含义是否由C ++标准定义?


我找不到基于锁的原子和无锁原子之间的语义差异。据我所知,就语言而言,差异在语义上毫无意义,因为语言不提供任何时间保证。我能找到的唯一保证是内存排序保证,这两种情况看起来都是一样的。

(如何)原子论的无锁定能否影响程序语义?

即,除了打电话 is_lock_free 要么 atomic_is_lock_free是否有可能编写一个定义良好的程序,其行为实际上受原子是否无锁影响?
这些功能甚至具有语义含义吗?或者它们只是编写响应式程序的实用黑客,即使语言从未提供过时间保证?


8144
2017-07-21 05:28


起源

据我所知(免责声明:我已经多年没有完成C ++了,但是好奇地看了一下文档),区别在于一个线程访问一个 无锁 对象永远不会被阻止,而a 锁为主 如果有其他线程访问该对象(基本上,使用事务内存或纯原子操作,使用互斥锁或类似的锁定方法),对象可能会导致线程阻塞。不发布答案,因为我不知道它是否真的有很大的不同 在实践中。 - Jcl
@Jcl:但是“封锁”的含义是什么意思......? (我的意思是从C ++标准的角度来看。对于阻塞调用意味着什么?) - Mehrdad
从C ++的角度来看,就像大多数事情一样,我想(再一次,只是猜测,我不知道,这就是我没有写答案的原因),它应该是依赖于实现/目标平台......但更可能是短暂的spinwait(pause 要么 rep nop 在更可能的x86 / x64的检查循环中) - Jcl
@Jcl:是的,我的意思是我当然理解“阻塞”对典型实现意味着什么,但我不明白它在抽象机器的上下文中意味着什么,例如用于编程的C ++。这是一个关于语言语义的问题,而不是关于实现的问题。 - Mehrdad


答案:


在C ++ 11标准中,术语“无锁定”的定义不如报告中所述 发行LWG#2075

C ++ 14标准定义了什么 无锁执行 是用C ++语言(N3927 批准)。

引用C ++ 14 1.10 [intro.multithread] /第4段:

原子函数的执行被定义为无锁(29.7)或表示为无锁(29.4) 无锁执行

  • 如果只有一个未阻塞的线程,则该线程中的无锁执行应完成。 [注意:并发执行线程可能会阻止无锁执行的进度。例如,加载锁定的存储条件实现可能会发生这种情况。这个属性有时被称为无阻碍。 - 结束说明]
  • 当一个或多个无锁执行同时运行时,至少应该完成一个。 [注意:某些实现难以为此效果提供绝对保证,因为来自其他线程的重复且特别是不合时宜的干扰可能阻止前向进展,例如,通过在加载锁定和存储条件之间反复窃取高速缓存行以用于不相关的目的说明。实施应该确保这种影响不能无限期地延迟在预期的操作条件下的进展,因此程序员可以安全地忽略这种异常。在此国际标准之外,此酒店有时被称为无锁。 - 结束说明]

“无锁”的上述定义取决于未阻塞线程的行为。 C ++标准没有定义 未阻塞的线程 直接,但17.3.3 [defns.blocked]定义 被阻止的线程

在可以继续执行之前等待某个条件(除处理器的可用性之外)的线程


(如何)原子论的无锁定能否影响程序语义?

我认为答案是否定的,除了信号处理程序 paxdiablo的回答,当“程序语义”意味着原子操作的副作用。 原子的无锁定影响了 进步保证的力量 整个多线程程序。 当两个(或多个)线程同时对同一对象执行无锁原子操作时,至少应完成其中一个操作 任何 最差的线程调度。 换句话说,'evil'线程调度程序可以在理论上故意阻止基于锁的原子操作的进度。


5
2017-07-22 01:07



+1是否也定义了“阻止”一词?因为如果没有,那么它仍然不清楚这应该是什么意思。 - Mehrdad
请参考C ++ 14(也是C ++ 11)17.3.2 [defns.block] define 块 和17.3.3 [defns.blocked]定义 被阻止的线程。 17.3.3表示“一个等待某些条件的线程(除了处理器的可用性)在它可以继续执行之前得到满足。” - yohjp
有意思......但是在语义上阻塞任何与通用函数调用不同的东西?在我看来,从程序的角度来看,差异在语义上没有意义 - 我没有看到程序区分阻塞函数调用和非阻塞函数调用的任何方法。我错过了什么吗? - Mehrdad


至少有  语义差异。

按照 C++11 1.9 Program execution /6

当抽象机器的处理因接收到信号而中断时,对象的值既不是类型的 volatile std::sig_atomic_t 在执行信号处理程序期间,未指定无锁原子对象,并且任何对象的值都不在任何一个中   由处理程序修改的这两个类别变为未定义。

换句话说,使用这两类变量进行清理是安全的,但应避免对所有其他类别进行任何访问或修改。

当然你可以说它不再是一个好的 定义 程序,如果你调用这样的未指定/未定义的行为,但我不完全确定你是否意味着那个或格式良好(即可编译)。

但是,即使你忽略了语义差异,a 性能 差异值得拥有。如果我必须有一个在线程之间进行通信的值,我可能会按优先顺序选择:

  • 无锁定的最小适当数据类型。
  • 如果数据类型是无锁的,则数据类型不是必需的,而较小的数据类型则不是。
  • 一个完全符合竞争条件的共享区域,但与一个完整的区域相结合 atomic_flag (保证无锁)来控制访问。

可以在编译或运行时根据选择此行为 ATOMIC_x_LOCK_FREE 宏,这样,即使程序行为相同,也是最佳的 方法 选择那种行为。


8
2017-07-21 05:46



我从来没有意识到C ++标准甚至首先谈到(C风格?)信号。谢谢,这真的很有趣! +1顺便说一下,我所说的'明确定义'确实基本上是“未定义”,但老实说我并没有考虑这种情况 - 我并不是要排除这种可能性,所以你确实回答了这个问题我打算问。 - Mehrdad
听起来不太可能无锁 int 但没有更小的锁定 char。 - MSalters
@MSalters,现已删除。它最初是基于我的理解,它最有可能在幕后工作,当我准备抒情它时,我意识到标准本身并没有决定 怎么样 它有效,只有它 不 工作,我曾经在这里严厉批评过这里的人:-)所以,你说得对,这里的可能性并不大。 - paxdiablo
所以这个答案留给我的问题是:当我们有异步信号时,是否会出现唯一的语义差异?或者还有其他一些区别吗? - Mehrdad


Paxdiablo回答得很好,但有些背景可能会有所帮助。

“无锁原子”是一个冗余的术语。最初发明的原子变量点是通过利用硬件保证来避免锁定。但是,每个平台都有自己的局限性,而C ++是高度可移植的。因此,实现必须使用细粒度锁来模拟原子性(通常通过库),原子类型在硬件级别并不存在。

硬件原子与“软件原子”之间的行为差​​异最小化,因为差异意味着丢失可移植性。另一方面,一个程序应该能够避免意外使用互斥,因此内省 ATOMIC_x_LOCK_FREE 这对预处理器可用。


3
2017-07-21 06:13



我认为无锁基本数据类型并不那么难,真正的问题是在它们之上创建无锁算法。有人可能会认为,一旦你有 atomic你可以写无锁代码,但甚至可以免费写锁 stack 是非常困难和容易出错的。 - nwp
@nwp我不知道C ++标准库结构的任何无锁实现,或任何标准化新的无锁结构接口的提议。这是一个单独的讨论。 std::atomic可能永远不会特别复杂,但这里的主题是它是否以及什么时候完全是微不足道的。 - Potatoswatter