4

考虑以下对多线程搜索算法的无锁哈希表的尝试（受本文启发）

struct Data
{
    uint64_t key;
    uint64_t value;
};

struct HashEntry
{
    uint64_t key_xor_value;
    uint64_t value;
};

void insert_data(Data const& e, HashEntry* h, std::size_t tableOffset)
{
    h[tableOffset].key_xor_value = e.key ^ e.value;
    h[tableOffset].value = e.value;
}

bool data_is_present(Data const& e, HashEntry const* h, std::size_t tableOffset)
{
    auto const tmp_key_xor_value = h[tableOFfset].key_xor_value;
    auto const tmp_value = h[tableOffset].value;

    return e.key == (tmp_key_xor_value ^ tmp_value);
}

这个想法是HashEntry结构存储结构的两个 64 位字的异或组合Data。如果两个线程对结构的两个 64 位字进行了交错读取/写入HashEntry，则想法是读取线程可以通过再次 XOR-ing 并与原始key. 因此，可能会因哈希条目损坏而降低效率，但在解码后的检索密钥与原始密钥匹配的情况下仍能保证正确性。

该论文提到它基于以下假设：

对于本讨论的其余部分，假设 64 位内存读/写操作是原子操作，即整个 64 位值在一个周期内读/写。

我的问题是：上面没有明确使用的代码是否std::atomic<uint64_t>保证在 C++11 中是线程安全的？或者单独的 64 位字是否会被同时读/写损坏？即使在 64 位平台上？这与旧的 C++98 标准有何不同？

来自标准的报价将不胜感激。

更新：根据Hans Boehm 关于“良性”数据竞争的这篇令人惊叹的论文，一个简单的被咬的方法是让编译器取消 XORinsert_data() 并data_is_present()始终返回true，例如，如果它找到一个本地代码片段，例如

insert_data(e, h, t);
if (data_is_present(e, h, t)) // optimized to true as if in single-threaded code
   read_and_process(e, h, t); // data race if other thread has written
4

3 回答 3

7

C++11 规范几乎将一个线程读取或写入另一个线程正在写入的内存位置的任何尝试定义为未定义的行为（没有使用原子或互斥锁来防止一个线程的读/写，而另一个线程正在写作）。

个别编译器可能会使其安全，但 C++11 规范本身并不提供覆盖。同时读取从来都不是问题；它在一个线程中写入，同时在另一个线程中读取/写入。

这与旧的 C++98 标准有何不同？

C++98/03 标准没有提供关于线程的任何内容。就 C++98/03 内存模型而言，线程不是可能发生的事情。

于 2012-09-20T07:29:34.713 回答
2

我认为它不太依赖于编译器，而是依赖于你正在使用的 CPU（它的指令集）。我不认为这个假设是非常便携的。

于 2012-09-20T07:21:35.533 回答
1

代码完全被破坏了。如果编译器的分析表明整体效果是相同的，那么编译器就有很大的自由来重新排序指令。insert_data例如，不能保证key_xor_value会在 之前更新，value更新是否在写回缓存之前在临时寄存器上完成，更不用说这些缓存更新时 - 无论它们在机器代码语言和 CPU 指令中的“顺序”如何执行管道 - 将从更新核心或核心（如果上下文切换的中间功能）私有缓存中刷新，以对其他线程可见。编译器甚至可以使用 32 位寄存器分步进行更新，具体取决于 CPU，是编译 32 位还是 64 位，编译选项等。

原子操作往往需要诸如 CAS（比较和交换）样式指令或volatile内存屏障指令之类的东西，它们在内核的缓存之间同步数据并强制执行一些排序。

于 2012-09-20T08:46:50.113 回答