rust - 这个 "atomic"Rust 代码和对应的 "non-atomic"代码有什么区别？

Question

我是 Rust 的新手。我 4 年前获得计算机工程学位，我记得在我的操作系统类(class)中讨论(和理解)原子操作。然而，自从毕业以来，我一直主要从事高级语言的工作，而不必关心像原子这样的低级东西。现在我正在学习 Rust，我很难记住这些东西是如何工作的。

我目前正在尝试理解 hibitset 的源代码图书馆，特别是atomic.rs .

此模块指定了一个 AtomicBitSet 类型，它对应于 lib.rs 中的 BitSet 类型，但使用原子值和操作。据我了解，“原子操作”是保证不会被另一个线程中断的操作；对相同值的任何“加载”或“存储”都必须等待操作完成才能继续。根据此定义，“原子值”是其操作完全原子的值。 AtomicBitSet 使用 AtomicUsize，它是一个 usize 包装器，其中所有方法都是完全原子的。但是，AtomicBitSet 指定了几个看起来不是原子的操作(add 和 remove)，其中有一个原子操作:add_atomic 。看看 add 与 add_atomic，我真的说不出有什么区别。

这是添加(逐字):

/// Adds `id` to the `BitSet`. Returns `true` if the value was
/// already in the set.
#[inline]
pub fn add(&mut self, id: Index) -> bool {
    use std::sync::atomic::Ordering::Relaxed;

    let (_, p1, p2) = offsets(id);
    if self.layer1[p1].add(id) {
        return true;
    }

    self.layer2[p2].store(self.layer2[p2].load(Relaxed) | id.mask(SHIFT2), Relaxed);
    self.layer3
        .store(self.layer3.load(Relaxed) | id.mask(SHIFT3), Relaxed);
    false
}

此方法直接调用load() 和store()。我假设它使用 Ordering::Relaxed 的事实使这个方法成为非原子的，因为另一个线程对不同的索引做同样的事情可能会破坏这个操作。

这是 add_atomic(逐字):

/// Adds `id` to the `AtomicBitSet`. Returns `true` if the value was
/// already in the set.
///
/// Because we cannot safely extend an AtomicBitSet without unique ownership
/// this will panic if the Index is out of range.
#[inline]
pub fn add_atomic(&self, id: Index) -> bool {
    let (_, p1, p2) = offsets(id);

    // While it is tempting to check of the bit was set and exit here if it
    // was, this can result in a data race. If this thread and another
    // thread both set the same bit it is possible for the second thread
    // to exit before l3 was set. Resulting in the iterator to be in an
    // incorrect state. The window is small, but it exists.
    let set = self.layer1[p1].add(id);
    self.layer2[p2].fetch_or(id.mask(SHIFT2), Ordering::Relaxed);
    self.layer3.fetch_or(id.mask(SHIFT3), Ordering::Relaxed);
    set
}

此方法使用 fetch_or 而不是直接调用 load 和 store，我假设这就是使此方法成为原子的原因。

但是为什么 Ordering::Relaxed 的使用仍然允许它被认为是原子的？我意识到单个“或”操作是原子的，但完整的方法可以与另一个线程同时运行。不会有影响吗？

此外，为什么像这样的类型会公开非原子方法？仅仅是为了性能吗？这让我感到困惑。如果我选择 AtomicBitSet 而不是 BitSet 因为它将被多个线程使用，我可能只想对它使用原子操作。如果我不这样做，我就不会使用它。对吧？

我还喜欢对 ​​add_atomic 中的注释进行解释。照原样对我来说没有意义。非原子版本不需要关心这个吗？这两种方法似乎在有效地做同样的事情，只是原子性级别不同。

我真的很想在原子学方面得到一些帮助。我认为阅读后我理解了订购 this和 this ，但两者仍在使用我不理解的概念。当他们谈论一个线程从另一个线程“看到”某些东西时，这到底是什么意思？当说顺序一致的操作“在所有线程中”具有相同的顺序时，这甚至意味着什么？处理器是否会针对不同的线程更改不同的指令顺序？

Answer 1

在非原子情况下，这一行:

self.layer2[p2].store(self.layer2[p2].load(Relaxed) | id.mask(SHIFT2), Relaxed);

或多或少等同于:

let tmp1 = self.layer2[p2];
let tmp2 = tmp1 | id.mask(SHIFT2);
self.layer2[p2] = tmp2;

所以另一个线程可以在它被读入 tmp1 和 tmp2 被存储到之间改变 self.layer2[p2]它。因此，如果另一个线程试图同时设置另一个位，则存在以下序列发生的风险:

• 线程 1 读取一个空掩码，
• 线程 2 读取一个空掩码，
• 线程 1 设置掩码的位 1 并写入它，
• 线程 2 设置掩码的位 2 并写入它，从而覆盖线程 1 设置的值，
• 最后只有第 2 位被设置!

self.layer3也是如此。

在原子情况下，fetch_or 的使用保证了整个读-修改-写周期是原子的。

在这两种情况下，由于顺序放宽，对 layer2 和 layer3 的写入可能看起来以从其他线程看到的任何顺序发生。

add_atomic 中的注释旨在避免两个线程尝试添加相同位时出现问题。假设 add_atomic 是这样写的:

pub fn add_atomic(&self, id: Index) -> bool {
    let (_, p1, p2) = offsets(id);

    if self.layer1[p1].add(id) {
        return true;
    }

    self.layer2[p2].fetch_or(id.mask(SHIFT2), Ordering::Relaxed);
    self.layer3.fetch_or(id.mask(SHIFT3), Ordering::Relaxed);
    false
}

然后你冒着以下顺序的风险:

• 线程 1 在 layer1 中设置位 1 并发现它没有事先设置，
• 线程 2 尝试在 layer1 中设置位 1，发现线程 1 已经设置了它，因此线程 2 从 add_atomic 返回，
• 线程 2 执行另一个需要读取 layer3 的操作，但是 layer3 还没有更新，所以线程 2 得到了一个错误的值!
• 线程 1 更新 layer3，但为时已晚。

这就是为什么 add_atomic 案例确保 layer2 和 layer3 在所有线程中正确设置，即使看起来该位已经预先设定。