问题标签 [lockless]

我已经阅读了有关 x64 上的内存排序的英特尔文档：http: //www.multicoreinfo.com/research/papers/2008/damp08-intel64.pdf。他们说锁定指令会导致完全障碍，从而使处理器可以看到例如指定的更新命令。但是，障碍引起的能见度并没有什么。障碍是否会导致其他处理器将立即看到变量的更新，或者更新可能只会以指定的顺序传播到其他处理器但没有指定的时间？

例如

线程1：

线程 2：

如果线程 1 将在线程 2 之前执行其代码，线程 2 是否总是 flag=true？

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

这个想法是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，例如，如果它找到一个本地代码片段，例如

我试图了解 Interlocked.Exchange 的正确用法，所以我正在实现一个简单的排序 LinkedList 与添加和删除功能。

如果这不是线程安全列表，显然要找到插入点，您将有类似下面的内容来找到插入新节点的正确点。

以下是我对您必须如何为并发列表执行此操作的看法。是否有太多 Interlocked.Exchange 正在进行？没有这个，插入仍然是线程安全的吗？成百上千的联锁操作会导致性能下降吗？

我知道，例如，curr = curr.next 是原子读取，但我可以确定特定线程将读取 curr.next 的最新值，而无需 Interlocked？

Go 的缓冲通道本质上是一个线程安全的 FIFO 队列。（参见Is it possible to use Go's buffered channel as a thread-safe queue?）

我想知道它是如何实现的。它是否像Is there a 这样的事情，例如用于多个读取或写入线程的无锁队列中描述的那样无锁？?

Go 的 src 目录 ( ) 中的 grepinggrep -r Lock .|grep chan给出以下输出：

不过，不要锁定我的机器（MacOS，intel x86_64）。是否有任何官方资源来验证这一点？

假设源架构和目标架构不同，模拟器如何有效地转换内存屏障？我知道通常现代仿真器将使用 JIT 将源ISA转换为目标 ISA，但是要知道哪些代码可以被多个程序计数器访问，哪些似乎不是很棘手，然后知道哪些指令可以安全地重新排序（由于 ISA 差异，JIT 可能需要生成一些有效的东西）并且这似乎不是非常棘手。

您甚至不能保证在指令流中找到显式的内存屏障，例如 x86 上的许多人依赖对齐的字写入是原子的。模拟器是否保守地假设每个对齐的单词写入都不能重新排序？这似乎是一个潜在的巨大开销，这让我想知道是否有任何已知的分析来解决这类问题。

我有一个问题需要我使用高并发、无等待的堆栈实现。我必须提前预分配所有内存（没有垃圾收集或 malloc），并且堆栈的大小是可以接受的（如果堆栈已满，则推送可能返回 false）。

我熟悉 Nir ​​Shavit 的堆栈实现：http ://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.8728 ...但这依赖于链表和垃圾收集。我需要基于数组的东西。

看起来 ACM 上有一个：http: //dl.acm.org/citation.cfm?id= 1532611虽然我对低下载率和引用持怀疑态度。

理想的答案是参考代码（在 C/C++ 中）我可以简单地窃取:-)

谁能给我总结一下比较和交换编程的优缺点？（例如多核 CPU 性能）

这是Java中的示例：

=== 编辑===

请在单核/核心 CPU 中专门讨论这个问题。

我有一棵树，T，节点，N。T 代表我正在监视的程序所做的所有内存分配和释放的记录。GUI 检查“计数”和“字节”

我的监控线程将交给我的树管理器一批堆栈跟踪，我的树管理器（如果堆栈被标记为分配）通过并为堆栈跟踪中的每个方法在树上创建一个节点（如果它没有已经存在），一直到 system32.dll。这工作正常。

完成此操作后，我将尝试并行更新树（不起作用）：

在每批中，我保证任何叶节点的分配事件都比释放事件多。但不知何故，在处理一批之后，我有时会在某些节点上出现负计数和/或负字节。 上面有什么不正确的吗？

笔记：

我避免使用锁和互斥锁，因为更新是无滞后的。只要所有数据都正确输入，每批结束时数字应该是正确的。

编辑：

结果是传入的数据有错误。

我正在尝试为从外部数据源获取的数据实现缓存。我试图弄清楚我是否可以一起避免锁定并使用时间戳来确保过时的数据永远不会插入缓存中。是否已经为此开发了一种机制？让我举个例子：

所以现在没有锁，当缓存中不存在 id 时，reader 可能会调用 extDataSrc。如果同时 writer 更新相同的 id，则可能在 writer 提交之前，reader 读取过时的数据并延迟从 extDataSrc 调用返回。同时 writer 执行 cache.remove(id) （缓存中没有数据，因此不会删除任何内容）并返回。Reader 然后执行 cache.put(id)。我在想这可以通过使用时间戳来避免，这样当阅读器检查缓存时，它会保存一个时间戳 TR1（在第 2 行之后：检查缓存的 id 时间）。Writer 在执行 remove 后保存 TW1（第 9 行之后：更新时间）。读取器在执行第 4 行后，再次保存 TR2（第 4 行之后：读取完成且缓存更新即将开始时）。这里如果 TR2 > TW1，它会跳过缓存。

所以，TR1 = 100，TW1 = 105，TR2 = 110 => 跳过 cache.put。

有什么意义吗？

在一些关于算法的文章中，有的使用了这个词lockfree，有的使用了lockless。lockless和有什么区别lockfree？谢谢！

更新

http://www.intel.com/content/dam/www/public/us/en/documents/guides/intel-dpdk-programmers-guide.pdf

第 5.2 节 --“Linux* 中的无锁环形缓冲区”，这是使用“无锁”一词的示例