在 C++11 中,没有 std::atomics 的无锁哈希是否能保证线程安全?

2024-02-15

考虑以下针对多线程搜索算法的无锁哈希表的尝试(受此启发paper http://www.cis.uab.edu/hyatt/hashing.html)

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);
}

这个想法是HashEntrystruct 存储 a 的两个 64 位字的异或组合Data结构。如果两个线程对 a 的两个 64 位字进行交错读/写HashEntry结构体,其想法是,读取线程可以通过再次异或并与原始结构进行比较来检测到这一点key。因此,哈希条目损坏可能会降低效率,但如果解码后的检索密钥与原始密钥匹配,仍然可以保证正确性。

论文提到,它基于以下假设:

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

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

如果能引用该标准,我们将不胜感激。

UPDATE:基于这篇令人惊叹的论文汉斯·伯姆 (Hans Boehm) 谈“良性”数据竞争 https://www.usenix.org/legacy/event/hotpar11/tech/final_files/Boehm.pdf,一个简单的方法是让编译器取消两个异或insert_data() and 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

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

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

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

C++98/03标准没有提供any关于线程的覆盖范围。就C++98/03内存模型而言,线程不是可能发生的事情 https://stackoverflow.com/a/6319356/734069.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

在 C++11 中,没有 std::atomics 的无锁哈希是否能保证线程安全? 的相关文章

随机推荐

  • 编码时需要考虑哪些安全问题?

    我知道 SQL 注入是其中之一 其他是什么 OWASP org 保留了一个列表 从OWASP 前十名 http www owasp org index php Category OWASP Top Ten Project
  • PHP 分页与 MySQLi

    我正在构建自己的 CMS 我制作了一个管理系统 我可以用它在数据库中插入帖子 显示帖子不是问题 但我不知道如何进行分页 这是我的查询 SELECT FROM posts WHERE status draft 构建您的查询以获得LIMIT 结
  • 如何使用 xsom\dom\jaxb 获取 xsd 的最大深度?

    如何使用 xsom 获取 xsd 的最大深度 例如 xsd 的每个复杂类型下的元素总数 另外 如果该复杂类型下存在复杂类型 则该复杂类型下的元素 属性的数量 使用 dom xsom jaxb
  • 对c中的int数组进行排序并删除重复项

    我正在学习C 并且谈到了排序的主题 我写了一个comp 功能和使用qsort对数组进行排序int 现在 对于下一个任务 我需要从数组中删除重复项 是否可以同时排序和删除重复项 include
  • 如何使用 Selenium 和 Python 通过爬虫测试非标准下拉列表

    我正在参与一个大学项目 构建一个网页爬虫 现在我遇到了在网页中测试下拉列表的情况 具体来说 以下页面不使用标准的 下拉 类 https www mirrorfiction com zh Hant book 406 我很难实施决策程序来判断网
  • R-闪亮| cat(list(...)、file、sep、fill、labels、append) 中的错误:参数 1(类型“list”)无法由“cat”处理

    我正在尝试编写一个闪亮的应用程序 并且需要先操作我的数据 然后才能开始可视化它 我有三个输入来操纵数据 1 渠道 2 排除某个词 3 查找所有含有该词的评论 我能够完成前两个任务 但是当使用 grep 函数查找包含某个单词的所有行时 我遇到
  • 如何通过NotificationListener利用Android Nougat的直接回复功能?

    我的应用程序正在使用NotificationListener读取来自各种 3rd 方应用程序的消息 例如 WhatsApp 到目前为止 如果只有一个聊天未读 我就能够发送回复 代码如下 然而 就 WhatsApp 而言 getNotific
  • ASP.NET MVC 多线程,值得吗?

    我有点困惑 我的 ASP NET MVC 应用程序将托管在服务器上 那么使其成为多线程有什么意义吗 例如 如果我想要一个线程来执行我的翻译 这是一个好主意吗 有人可以向我详细说明一下吗 我对网络应用程序多线程与桌面应用程序多线程有点困惑 这
  • 安全终止 Spring JMS 应用程序

    我正在开发一个 Spring boot JMS 应用程序 该应用程序严格使用 bean 注释进行设置 并从 WebshpereMQ 读取消息 一切正常 除了我不知道如何安全地关闭这个应用程序 一旦我的 JMSListener 方法读取了所有
  • 如何从 C++ 中的 void 函数中退出?

    如果函数是 void 函数 如何在不返回值的情况下提前退出 我有一个 void 方法 如果某个条件为真 则不需要执行其代码 我真的不想改变方法来实际返回一个值 使用返回语句 return or if condition return 如果您
  • 跟踪通过我的应用程序发送和接收的数据的使用情况

    如何跟踪通过我的应用程序发送和接收的数据的使用情况 我只想记录我的应用程序运行时发送和接收的字节 如果我可以获取 Wifi 和蜂窝网络的单独信息 那就太好了 但这不是优先事项 我知道如何查找设备的总使用情况 https stackoverf
  • 内联表单集在保存时返回空列表?

    当我尝试保存内联表单集时 它只返回一个空列表 并且数据库中没有反映任何更改 我尝试过在没有选项和 commit False 的情况下执行此操作 但它们都有相同的结果 我知道有数据 因为我将表单集打印为表格 并且我知道它是有效的 因为属性 i
  • Typescript 如何声明子类类型?

    有可能有这样的事情吗 export abstract class FilterBoxElement abstract getEntities any export interface FilterBoxControlSuggestions
  • 如何测试我的 PHP 上是否安装了 SimpleXML?

    有人知道吗 那个东西是默认安装的 但是有没有一种简单的方法来检查扩展是否安装了呢 我检查 simplexml load string 对我可用 但是 simplexml 没有在 php ini 上列出怎么办 还有另一种方法 您可以创建一个p
  • 错误“Keras 需要 TensorFlow 2.2 或更高版本”

    我刚刚安装了 Visual Studio 2019 和 Tensorflow 但无法导入 Keras 因为收到以下错误消息 Keras 需要 TensorFlow 2 2 或更高版本 通过以下方式安装 TensorFlowpip insta
  • 处理 .NET 中的部分/不完整日期

    我需要处理部分日期 例如 2009 年 4 月 1 日 存储为 1 4 200 2000 年 1 月 存储为 null 1 2000 90 年 3 月 存储为 null 1990 年 3 月 00 存储为 null null 2000 等等
  • Tortoise SVN 提交时出错:“无效的 PROPPATCH 属性”

    我在 Windows 7 机器上使用 tortoise svn 1 6 16 并在提交时出现错误 如下所示 Error Commit failed details follow Error At least one property cha
  • 如何在Mule中通过HTTP请求发送文件并通过FTP上传到文件服务器

    我想在 HTTP POST 请求中发送一个文件 然后让 Mule 使用 FTP 将文件上传到服务器上的文件目录 看起来 FTP 连接器将有效负载保存到文件目录 但这实际上是空的 并且 FTP 将一个空文件写入该目录 我已经使用 Postma
  • 向 Blackberry 项目添加外部 Jar 并测试兼容性

    我是黑莓开发的新手 我有 Eclipse 3 5 1 和 Blackberry JRE 4 7 0 在我的应用程序中 我向项目中添加了 2 个外部 jar 和一个属性文件 我不确定我尝试添加的 jar 和我调用的 Web 服务是否与 Bla
  • 在 C++11 中,没有 std::atomics 的无锁哈希是否能保证线程安全?

    考虑以下针对多线程搜索算法的无锁哈希表的尝试 受此启发paper http www cis uab edu hyatt hashing html struct Data uint64 t key uint64 t value struct