主页 / coding / 问题 / 79201934
Accepted
kakkoko
Asked: 2024-11-19 10:30:33 +0800 CST

std::atomic 在那些不使用二进制补码的平台上是如何实现的？（C++11/14/17）

  • 772

std::atomic::fetch_add()（或atomic_fetch_add()在 C11 中）基于二进制补码对有符号整数进行运算。这与通常的有符号整数算法不同，后者允许使用其他表示方案。

来自N3337 [atomics.types.operations/30]：

备注：对于有符号整数类型，算术定义为使用二进制补码表示。没有未定义的结果。对于地址类型，结果可能是未定义的地址，但操作没有未定义的行为。

我的问题是：

(1) 在使用除二进制补码以外的有符号整数表示的平台上如何std::atomic::fetch_add()实现？ 是否只有使用互斥锁等的非无锁实现？

(2) 当在一个使用二进制补码以外的表示方法的平台上读取包含负值的原子变量的值时，它是否会自动转换为平台的本机格式？还是用户有责任将其转换为本机表示，因为二进制补码表示的位串是从中读取的？

std::atomic<int> a{0};
a.fetch_sub(1);
int x = a.load();  // The value of a is -1 (0xffffffff), so what is the value of x?

（3）我想知道在采用除二进制补码之外的表示方案的平台上的实现示例std::atomic::fetch_add()（或atomic_fetch_add()）。（如果这样的平台不存在，我不会感到惊讶！）

请注意，N2427对上述内容作出了如下规定：

正常的有符号整数加法运算在发生溢出时具有未定义的行为。对于原子变量，这种未定义的行为会带来很大的负担，因为通常没有办法预先测试溢出。我们认识到现代系统的实际行为，并定义原子提取和添加（减法）以使用二进制补码算法，而不是让溢出保持未定义状态。我们知道没有一个 C++ 实现会因为这个定义而出现问题。

（这个问题是基于学术兴趣。我问这个问题并不是因为我在面对任何实际问题时遇到了困难。）

c++

1 个回答

  1. Best Answer

    这都是假设的；我认为没有任何 C++11 到 17 实现针对一的补码或符号/幅度机器。（或者任何实现_Atomic和的C11 实现<stdatomic.h>；与 C++ 的<atomic>标头不同，C11 的这一部分是可选的。）
    C++20（和 C23）也为普通整数类型标准化了二进制补码，我认为这就是您的标题指定 11/14/17 的原因。

    std::atomic<>并非真正打算在不使用 2 的补码的机器上实现。我的理解是这std::atomic<>不是可选的，尽管只atomic_flag需要无锁。但 C11 使用了相同的定义，并且在那里它是可选的。不过，这似乎是在试水 2 的补码标准化。也因为没有人 (?) 对为不存在且不太可能建造的假设机器编写原子规则感兴趣。

    fetch_add二进制补码上的int二进制运算与二进制运算相同unsigned（假设它们具有相同的宽度）。二进制补码的主要优点之一是不需要单独的 ALU 配置或单独的指令来执行有符号和无符号运算。

    因此，编译器可以使用与 for 相同的 asm atomic<unsigned>（可能是也可能不是 CAS 重试循环），假设unsigned至少具有与普通 一样多的值位。（如果具有比 更多的值位，或者编译器生成代码在某个时候截断它们，例如在转换为 期间，int则没问题。）atomic<int>intint

    C++ 需要支持具有unsigned明确包装的整数类型，我的理解是，大多数补码和符号/幅度机器都具有有符号加法和无符号加法指令，至少对于可以并且确实有效实现 K&R 或 C89 的 ISA 而言。如果原子 RMW 加法不能直接通过一条指令获得，那么您必须回退到 CAS 重试循环来同时进行atomic<unsigned>和atomic<int>。

    如果机器的原始操作是LL/SC，那么您只需使用它而不是 CAS。如果机器的原始原子构建块是 CAS ，并带有按位相等性比较，例如memcmp，那也是可以的。
    但是，如果它只有一个有符号的CAS，它会在负数时陷入陷阱0（符号/数值为 0x80000000，二进制补码为 0xffffffff）或将其视为等于，那么您就会遇到问题，无法为有符号类型+0实现无锁。std::atomic

    需要额外的代码来将 arg 和 retval 在机器本机int和 2 的补码位模式之间进行转换，以用作无符号，但不是作为原子操作本身的一部分。（不在重试循环内）。

    例如，将 1 的补码转换为 2 的补码就是将 1 添加到负数的位模式中。（分别-1用位模式0xfffffffe和和 1 的补码表示）。因此，对于 32 位机器，使用无符号右移和加法。而要将 2 转换为 1，则将 转换为最负的 2 的补码值，这将绕回到。0xffffffff-x = ~xx += x>>31x -= x>>31INT_MAX-2^n

    如果机器有包装 int <-> unsigned 转换指令，那么这些指令至少应该可以转换为unsigned。C 要求 int 到 unsigned 通过将值模数减少到目标的值范围来工作，对于负输入，这意味着将 2 32添加到 以-1使4294967295= 0xffffffff。（在 2 的补码机器上，这是一个无操作，只是对位的重新解释。）我不太确定 unsigned -> 1 的补码或符号/幅度是否与 2 的补码相同，我还没有尝试过一个例子。

    C++ 不允许您将进位或有符号溢出标志作为额外输出读取，并且除了相等之外，没有任何原子 RMW 操作包括比较。在手写 asm 中，您可能希望在有符号溢出时进行分支（或者特别是在之后sub，在有符号条件（例如大于或小于，包括 SF 和 OF）下），但在 C++ 中，您必须使用纯int值（可能保存从 2 的补码原子类型转换的值）单独编写比较。

    顺便说一句，RMW 之后的单独加载是一种反模式。其他线程的操作可能发生在 RMW 和重新加载之间，而且效率较低。 .fetch_sub返回旧值，因此通常您会这样做a.fetch_sub(1) - 1以获取存储的值。但然后您将-1在普通 int 上执行。您可以使用x = --a，但这被定义为等同于.fetch_sub(1) - 1IIRC。您可以将原子初始化为-1，但执行从那里获取它的操作0值得一提。所以现在我明白你为什么这样写你的例子了！

        std::atomic<int> a{0};
    int result = --a;  

    int x = a.load();  // maybe in another thread

    正如您所说，a = -1使用位模式0xffffffff表示对象a。 (或者至少a其中的一部分实际上保存了int值；std::atomic<>对象可以更大，并且对于它可能拥有的任何私有成员都有其他值位。)

    std::atomic 成员函数的返回int值是普通的，因此在生成返回值时必须进行int从 2 的补码int到机器本机的转换。 （然后将其副本分配给。）intint x

    C++17，第 7.8 节 整数转换

    （2）如果目标类型是无符号的，则结果值是与源整数一致的最小无符号整数（模 2 n，其中 n 是用于表示无符号类型的位数）。
    [注意：在二进制补码表示中，这种转换是概念性的，并且位模式没有变化（如果没有截断）。— 结束注释]

    （3）若目标类型是有符号的，且该值能在目标类型中表示，则该值不变； 否则，该值是实现定义的。

    （从其他数字类型如 FP，超出范围的转换是 UB。以上适用于积分到积分。）

    2 的补码最大负值比 低 1。INT_MIN因此，即使宽度相等， 值也可能无法表示。

    我认为甚至unsigned tmp = a.load();无法生成所有 2 32 个可能的值a（再次假设是 32 位机器），因为该值必须通过int返回值。如果它只有2^32 - 1不同的值，那么某些东西必须在某个地方崩溃。也许从-2^31包装到+2^31 - 1（INT_MAX）。（负零与正常情况没有区别，0即使它不是陷阱表示。它必须转换为无符号0。 memcpy可以提取位模式int...）

    我认为将 内部使用的 2 的补码表示形式视为整数类型是有意义的std::atomic<int>，尽管值得检查标准的措辞以查看在实现使用非 2 的补码的 C++17 Deathstation 9000 时是否允许您作恶。 （或者相反，我们是否仍然可以通过将位模式直接复制到unsignedfor来符合要求unsigned x = a.load()，跳过与本机有符号的转换int。）

    顺便说一句，当前草案中的语言更加简单，因为只存在 2 的补码类型和无符号类型：

    （3）否则 [非布尔值]，结果是与源整数模 2 N一致的目标类型的唯一值，其中 N 是目标类型的宽度。

    因此，即使转换为有符号数，也需要进行模数减少，而不仅仅是无符号数。因为这是你通过截断位模式得到的 2 的补码。

    • 5

相关问题