std :: atomic中的任何内容都无需等待吗? [英] Anything in std::atomic is wait-free?
问题描述
如果T是C ++基本类型，并且std::atomic<T>::is_lock_free()返回true，则std::atomic<T>中是否存在
If T is a C++ fundamental type, and if std::atomic<T>::is_lock_free() returns true, then is there anything in std::atomic<T> that is wait-free (not just lock-free)? Like, load, store, fetch_add, fetch_sub, compare_exchange_weak, and compare_exchange_strong.
您还可以根据C ++标准中指定的内容以及在Clang和/或GCC(您选择的版本)中实现的内容进行回答.
Can you also answer based on what is specified in the C++ Standard, and what is implemented in Clang and/or GCC (your version of choice).
My favorite definitions for lock-free and wait-free are taken from C++ Concurrency in Action (available for free). An algorithm is lock-free if it satisfies the first condition bellow, and it is wait-free if it satisfies both conditions below:
- 如果调度程序在操作过程中将访问数据结构的线程之一挂起，则其他线程仍必须能够完成其操作，而不必等待挂起的线程.
- 每个访问数据结构的线程都可以在无数个步骤中完成其操作，而与其他线程的行为无关.
推荐答案
存在普遍接受的锁自由和等待自由定义，您的问题中提供的定义与此一致.而且我强烈认为，C ++标准委员会肯定会遵循科学界普遍接受的定义.
There exist universally accepted definitions of lock-freedom and wait-freedom, and the definitions provided in your question are consistent with those. And I would strongly assume that the C++ standard committee certainly sticks to definitions that are universally accepted in the scientific community.
通常，有关无锁/无等待算法的出版物都假定CPU指令是无等待的.取而代之的是，有关进度的争论保证将重点放在软件算法上.
In general, publications on lock-free/wait-free algorithms assume that CPU instructions are wait-free. Instead, the arguments about progress guarantees focus on the software algorithm.
基于此假设，我认为对于任何体系结构，任何可以转换为单个原子指令的std::atomic方法在该特定体系结构上都无需等待.但是，这种翻译是否可能有时取决于该方法的使用方式.以fetch_or为例.在x86上，可以将其转换为lock or，但前提是您不使用其返回值，因为此指令未提供原始值.如果使用返回值，则编译器将创建一个CAS循环，该循环是无锁的，但不是等待的. (fetch_and/fetch_xor也是如此.)
Based on this assumption I would argue that any std::atomic method that can be translated to a single atomic instruction for some architecture is wait-free on that specific architecture. Whether such a translation is possible sometimes depends on how the method is used though. Take for example fetch_or. On x86 this can be translated to lock or, but only if you do not use its return value, because this instruction does not provide the original value. If you use the return value, then the compiler will create a CAS-loop, which is lock-free, but not wait-free. (And the same goes for fetch_and/fetch_xor.)
因此，哪些方法实际上无需等待，不仅取决于编译器，而且主要取决于目标体系结构.
假设一条指令实际上是免等待的，从技术上讲是正确的，恕我直言.的确，不能保证指令在有限数量的步骤"内完成执行. (可能会采取任何步骤)，但是机器指令仍然是我们可以看到和控制的最低级别的最小单元.实际上，如果您不能假设一条指令是 wait-free ，那么严格来讲就不可能在该架构上运行任何实时代码，因为实时还需要严格的时间限制/步数.
Whether it is technically correct to assume that a single instruction is actually wait-free or not is a rather philosophical one IMHO. True, it might not be guaranteed that an instruction finishes execution within a bounded number of "steps" (whatever such a step might be), but the machine instruction is still the smallest unit on the lowest level that we can see and control. Actually, if you cannot assume that a single instruction is wait-free, then strictly speaking it is not possible to run any real-time code on that architecture, because real-time also requires strict bounds on time/the number of steps.
这是C ++ 17标准在[intro.progress]中声明的内容:
This is what the C++17 standard states in [intro.progress]:
原子函数的执行，这些原子函数被定义为无锁(32.8)或表示为无锁(32.5) 是无锁执行.
Executions of atomic functions that are either defined to be lock-free (32.8) or indicated as lock-free (32.5) are lock-free executions.
- 如果在标准库函数中只有一个未被阻塞的线程(3.6)，则该线程中的无锁执行应完成. [注意:并发执行线程可能会阻止无锁进程的进行 执行.例如，这种情况可能发生在加载锁定的存储条件实现中.此属性有时称为无障碍. —尾注]
- 当一个或多个无锁执行同时运行时，至少应完成一个. [注意:一些实现方式很难对此效果提供绝对的保证，因为来自其他线程的反复(尤其是不适当的)干扰可能会阻止前向进度，例如，出于不相关的目的而反复地窃取高速缓存行，以便在负载锁定和存储条件之间进行指示.实现应确保此类影响不会无限期地延迟预期操作条件下的进度，因此程序员可以安全地忽略此类异常.在本文档之外，有时将此属性称为无锁. —尾注]
- If there is only one thread that is not blocked (3.6) in a standard library function, a lock-free execution in that thread shall complete. [ Note: Concurrently executing threads may prevent progress of a lock-free execution. For example, this situation can occur with load-locked store-conditional implementations. This property is sometimes termed obstruction-free. — end note ]
- When one or more lock-free executions run concurrently, at least one should complete. [ Note: It is difficult for some implementations to provide absolute guarantees to this effect, since repeated and particularly inopportune interference from other threads may prevent forward progress, e.g., by repeatedly stealing a cache line for unrelated purposes between load-locked and store-conditional instructions. Implementations should ensure that such effects cannot indefinitely delay progress under expected operating conditions, and that such anomalies can therefore safely be ignored by programmers. Outside this document, this property is sometimes termed lock-free. — end note ]
弗朗切斯科·门萨尼(Francesco Menzani)正确地指出，我的原始答案有点不精确，因为存在两种更强大的等待自由亚型.
Francesco Menzani correctly pointed out that my original answer was a bit imprecise, since there exist two stronger subtypes of wait-freedom.
- 无需等待-如果一种方法可以确保每个调用以 finite 个步骤完成执行，则该方法是无需等待的，即无法执行确定上限，但仍必须保证步数是有限.
- 无等待界限-如果一种方法保证每个调用以 bounded 步数完成执行，则该方法不受等待界限的限制，该界限可能取决于线程数上.
- 无等待人口忽略-如果方法保证每个调用以 bounded 步数完成执行，并且此绑定受限制，则该方法将被忽略不取决于线程数.
- wait-free - A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps, i.e., it is not possible to determine an upper bound, but it must still be guaranteed that the number of steps is finite.
- wait-free bounded - A method is wait-free bounded if it guarantees that every call finishes its execution in a bounded number of steps, where this bound may depend on the number of threads.
- wait-free population oblivious - A method is wait-free population oblivious if it guarantees that every call finishes its execution in a bounded number of steps, and this bound does not depend on the number of threads.
严格来说，问题中的定义与无等待界的定义一致.
So strictly speaking, the definition in the question is consistent with the definition of wait-free bounded.
实际上，大多数免等待算法实际上是无等待的有界甚至是无等待的总体，即可以确定步数的上限.
In practice, most wait-free algorithms are actually wait-free bounded or even wait-free population oblivious, i.e., it is possible to determine an upper bound on the number of steps.
这篇关于std :: atomic中的任何内容都无需等待吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
