用户定义的原子小于

Question

我一直在阅读，似乎 std::atomic 不支持 less/greater 比变体的比较和交换。

我正在使用 OpenMP，需要安全地更新全局最小值。我在想这会像使用内置 API 一样简单。但是，唉，所以我试着想出我自己的实现。

我主要担心这样一个事实，即我不想每次都使用 omp 临界区进行小于比较，因为在大多数情况下它可能会产生显着的同步开销而收效甚微。

但是在可能找到新的全局最小值的情况下（不太常见），同步开销是可以接受的。我想我可以使用以下方法来实现它。希望有人指教。

使用 std::atomic_uint 作为全局最小值。
以原子方式将值读入线程本地堆栈。
将它与当前值进行比较，如果小于，则尝试进入临界区。
同步后，验证原子值仍然小于新值并进行相应更新（临界区的主体应该很便宜，只需更新几个值）。

这是一项家庭作业，所以我试图让实施属于我自己。请不要推荐各种库来完成此操作。但是请评论此操作可能产生的同步开销，或者如果不好，请详细说明原因。谢谢。

Answer 1

如果存在，您要查找的内容将被称为 fetch_min()：获取旧值并将内存中的值更新为 min(current, new)，与 fetch_add 完全相同，但带有 min().

x86 上的硬件不直接支持此操作，但是具有 LL/SC 的机器可以发出稍微比用 [= 模拟它更有效的 asm 15=] 重试循环。

您可以使用 CAS 重试循环 模拟任何原子操作。实际上它通常不需要重试，因为成功加载的 CPU 通常在计算加载结果后的几个周期后在 CAS 中也成功，所以它是高效的。

请参阅，了解使用 CAS 重试循环为 atomic<double> 创建 fetch_add 的示例，就 compare_exchange_weak 和普通 + 而言double。使用 min 完成此操作，一切就绪。

回复：评论中的澄清：我想你是说你有一个全局最小值，但是当你找到一个新的时，你也想更新一些相关的数据。 你的问题令人困惑，因为 "compare and swap on less/greater than" 对你没有帮助。

我建议使用 atomic<unsigned> globmin 来跟踪全局最小值，这样您可以阅读它来决定是否进入临界区并更新与该最小值相关的相关状态。

仅在持有锁时修改 globmin（即在临界区内）。然后你可以更新它+相关的数据。它必须是 atomic<>，这样在关键部分之外只查看 globmin 的读者就不会出现数据竞争 UB。查看关联的额外数据的读者必须获取保护它的锁，并确保 globmin + 额外数据的更新发生 "atomically"，从遵守锁的读者的角度来看。

static std::atomic<unsigned> globmin;
std::mutex globmin_lock;
static struct Extradata globmin_extra;

void new_min_candidate(unsigned newmin, const struct Extradata &newdata)
{
    // light-weight early out check to avoid the critical section
    // No ordering requirement as long as globmin is monotonically decreasing with time
    if (newmin < globmin.load(std::memory_order_relaxed))
    {
       // enter a critical section.  Use OpenMP stuff if you want, this is plain ISO C++
       std::lock_guard<std::mutex> lock(globmin_lock);

       // Check globmin again, after we've excluded other threads from modifying it and globmin_extra
       if (newmin < globmin.load(std::memory_order_relaxed)) {
           globmin.store(newmin, std::memory_order_relaxed);
           globmin_extra = newdata;
       }
       // else leave the critical section with no update:
       // another thread raced with use *outside* the critical section

      // release the lock / leave critical section (lock goes out of scope here: RAII)
    }
    // else do nothing
}

std::memory_order_relaxed 对 globmin 来说已经足够了：不需要其他任何东西的顺序，只需要原子性。我们从关键 section/lock，而不是从加载/存储的内存排序语义中获得关联数据的原子性/一致性 globmin。

这样，唯一的原子读取-修改-写入操作就是锁定本身。 globmin 上的所有内容要么加载要么存储（便宜得多）。多线程的主要成本仍然是缓存行的反弹，但是一旦你拥有一个缓存行，每个原子 RMW 可能比现代 x86 上的简单存储贵 20 倍 (http://agner.org/optimize/)。

采用这种设计，如果大多数候选项不低于 globmin，缓存行将大部分时间停留在 Shared state，因此 globmin.load(std::memory_order_relaxed) 在 critical 之外部分可以命中 L1D 缓存。这只是一条普通的加载指令，因此非常便宜。（在 x86 上，即使是 seq-cst 加载也只是普通加载（而 release 加载只是普通存储，但 seq_cst 存储更昂贵）。在默认顺序较弱的其他架构上，seq_cst /获取负载需要障碍。）

用户定义的原子小于

User defined atomic less than

multithreading

openmp

stdatomic