如果 atomic_compare_exchange 在它自己的线程上不是原子的,它如何实现锁?
If atomic_compare_exchange isn't atomic on its own thread, how can it implement a lock?
如果我有
std::atomic<uint64_t> guard;
// ...
if (std::atomic_compare_exchange_strong(
&guard, &kExpected, kValue,
std::memory_order_acquire, std::memory_order_relaxed)) {
int foo = *non_atomic_thing;
// ...
}
我知道 non_atomic_thing
的读取不能在 guard
的读取之前重新排序。但是有没有可能在write之前重新排序呢?也就是说,如果其他线程用 std::memory_order_acquire
读取 guard
,观察到它不等于 kValue
,然后写入它,这是数据竞争吗?
(cppreference.com 对此不是很清楚,但是 Rust 的文档具有相同的语义,特别指出获取仅适用于加载部分,释放仅适用于存储:"Using Acquire as success ordering makes the store part of this operation Relaxed")
如果这是真的,我如何告诉其他线程在我读取它时不要覆盖我的值?
C++ 标准在这一点上有点含糊。但他们可能想要的,以及在许多实现中实际发生的情况是,您的 non-atomic 读取 可以 在写入之前重新排序。参见 For purposes of ordering, is atomic read-modify-write one operation or two?。
然而,对于通常的锁定习惯用法,这不是问题,也不会导致数据竞争。在获取锁时,很容易将基本操作视为“锁定”值的存储,它告诉其他线程锁是我们的,他们不能拥有它。但实际上,重要的是“解锁”值的负载。这就证明锁是属于我们线程的。 read-modify-write 操作的原子性保证在我们重置它之前没有其他线程会加载该值,因此我们可以安全地进入临界区,即使我们存储的“锁定”值直到一段时间后。
您可以想象这发生在 LL/SC architecture 上。假设 load-link 已完成并且 returns 为“解锁”值。 store-conditional 尚未完成,它可能会失败,以防其他核心访问锁变量而我们失去了对它的独占所有权。但是,与此同时,我们可以对 non-atomic 变量执行 推测性 加载,前提是除非 SC 成功,否则它不会退出。如果 SC 失败,则必须重做 LL/SC 对,在这种情况下,我们的 non-atomic 负载也将重做。因此,当我们最终成功时,non-atomic 负载将在 LL 之后可见,但可能在 SC 之前可见。
为了了解这是如何从 C++ 内存排序规则中得出的,让我们考虑一个更 fleshed-out 的例子:
std::atomic<int> lock{0};
int non_atomic;
void reader() {
int expected = 0;
if (lock.compare_exchange_strong(expected, 1,
std::memory_order_acquire, std::memory_order_relaxed)) {
int local = non_atomic;
// ...
lock.store(0, std::memory_order_release);
}
}
void writer() {
int expected = 0;
if (lock.compare_exchange_strong(expected, 2,
std::memory_order_acquire, std::memory_order_relaxed)) {
non_atomic = 42;
// ...
lock.store(0, std::memory_order_release);
}
}
read-modify-write 操作的原子性承诺来自 C++20 [atomics.order p10]:
Atomic read-modify-write operations shall always read the last value (in the modification order) written
before the write associated with the read-modify-write operation.
lock
的修改顺序为总顺序。仅当 compare-exchanges 都读取值 0 时才会进入临界区。reader
加载的 0 必须在修改顺序中紧跟 1,而 writer
加载的 0必须紧跟 2。因此 0 必须出现两次。因此 lock
的修改顺序必须是 0 1 0 2 0
或 0 2 0 1 0
.
如果是 0 1 0 2 0
,则第二个 0 必须来自 reader
中的发布存储。它不能来自 writer
中的存储,因为在修改顺序中那个必须在 2 之后(因为 writer
s 0 的存储在其 2 的存储之后排序;这是 write-write 一致性,[intro.races p15])。因此 writer
中的获取负载读取顺序中的第二个 0,它由 reader
中的发布存储放在那里,因此它们同步。这确保了 reader
中对 non_atomic
的访问发生在 writer
中的访问之前,并且没有数据竞争。
如果是0 2 0 1 0
,则逻辑相反,writer
中的访问发生在reader
中的访问之前;再次没有数据竞争。
如果我有
std::atomic<uint64_t> guard;
// ...
if (std::atomic_compare_exchange_strong(
&guard, &kExpected, kValue,
std::memory_order_acquire, std::memory_order_relaxed)) {
int foo = *non_atomic_thing;
// ...
}
我知道 non_atomic_thing
的读取不能在 guard
的读取之前重新排序。但是有没有可能在write之前重新排序呢?也就是说,如果其他线程用 std::memory_order_acquire
读取 guard
,观察到它不等于 kValue
,然后写入它,这是数据竞争吗?
(cppreference.com 对此不是很清楚,但是 Rust 的文档具有相同的语义,特别指出获取仅适用于加载部分,释放仅适用于存储:"Using Acquire as success ordering makes the store part of this operation Relaxed")
如果这是真的,我如何告诉其他线程在我读取它时不要覆盖我的值?
C++ 标准在这一点上有点含糊。但他们可能想要的,以及在许多实现中实际发生的情况是,您的 non-atomic 读取 可以 在写入之前重新排序。参见 For purposes of ordering, is atomic read-modify-write one operation or two?。
然而,对于通常的锁定习惯用法,这不是问题,也不会导致数据竞争。在获取锁时,很容易将基本操作视为“锁定”值的存储,它告诉其他线程锁是我们的,他们不能拥有它。但实际上,重要的是“解锁”值的负载。这就证明锁是属于我们线程的。 read-modify-write 操作的原子性保证在我们重置它之前没有其他线程会加载该值,因此我们可以安全地进入临界区,即使我们存储的“锁定”值直到一段时间后。
您可以想象这发生在 LL/SC architecture 上。假设 load-link 已完成并且 returns 为“解锁”值。 store-conditional 尚未完成,它可能会失败,以防其他核心访问锁变量而我们失去了对它的独占所有权。但是,与此同时,我们可以对 non-atomic 变量执行 推测性 加载,前提是除非 SC 成功,否则它不会退出。如果 SC 失败,则必须重做 LL/SC 对,在这种情况下,我们的 non-atomic 负载也将重做。因此,当我们最终成功时,non-atomic 负载将在 LL 之后可见,但可能在 SC 之前可见。
为了了解这是如何从 C++ 内存排序规则中得出的,让我们考虑一个更 fleshed-out 的例子:
std::atomic<int> lock{0};
int non_atomic;
void reader() {
int expected = 0;
if (lock.compare_exchange_strong(expected, 1,
std::memory_order_acquire, std::memory_order_relaxed)) {
int local = non_atomic;
// ...
lock.store(0, std::memory_order_release);
}
}
void writer() {
int expected = 0;
if (lock.compare_exchange_strong(expected, 2,
std::memory_order_acquire, std::memory_order_relaxed)) {
non_atomic = 42;
// ...
lock.store(0, std::memory_order_release);
}
}
read-modify-write 操作的原子性承诺来自 C++20 [atomics.order p10]:
Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.
lock
的修改顺序为总顺序。仅当 compare-exchanges 都读取值 0 时才会进入临界区。reader
加载的 0 必须在修改顺序中紧跟 1,而 writer
加载的 0必须紧跟 2。因此 0 必须出现两次。因此 lock
的修改顺序必须是 0 1 0 2 0
或 0 2 0 1 0
.
如果是 0 1 0 2 0
,则第二个 0 必须来自 reader
中的发布存储。它不能来自 writer
中的存储,因为在修改顺序中那个必须在 2 之后(因为 writer
s 0 的存储在其 2 的存储之后排序;这是 write-write 一致性,[intro.races p15])。因此 writer
中的获取负载读取顺序中的第二个 0,它由 reader
中的发布存储放在那里,因此它们同步。这确保了 reader
中对 non_atomic
的访问发生在 writer
中的访问之前,并且没有数据竞争。
如果是0 2 0 1 0
,则逻辑相反,writer
中的访问发生在reader
中的访问之前;再次没有数据竞争。