问题标签 [lock-free]

我一直在用谷歌搜索 C++ 中的无锁队列。我找到了一些代码和一些试验——但我无法编译。也欢迎使用无锁哈希。

摘要：到目前为止，我没有肯定的答案。没有“生产就绪”的库，令人惊讶的是，现有的库都不符合 STL 容器的 API。

在内核端设置内存屏障很容易：由于 Linux 内核头文件，宏 mb、wmb、rmb 等始终存在。

如何在用户端做到这一点？

这是我目前正在维护的一些代码的简化版本：

lCurrentIndex 由另一个线程定期更新。问题是; 制作 m_CurrentIndex 的本地副本是否会确保对 m_someArray 的两个访问都使用相同的索引？

请注意，这是一个简化的示例；我正在考虑制作本地副本的概念，而不是此处显示的确切代码。我知道编译器会将值放入寄存器中，但这仍然是本地副本，而不是从 lCurrentIndex 读取两次。

谢谢！

编辑：初始分配是安全的，在我们的设置中都保证是 32 位的。Edit2：它们在 32 位边界上正确对齐（忘了那个）

在数据结构同步的上下文中，有人可以澄清“无锁”和“非阻塞”之间的区别吗？这些术语似乎被很多人互换使用，但我还不确定是否在某处隐藏了一些细微的差异。

我的意思是无锁是“没有锁”，非阻塞更像是保证进度。我怀疑一个暗示另一个，但不是相反，我不确定。

欢迎参考。

在 Sparc 上的 64 位 Solaris 上，atomic_cas_64() 函数调用是否使用加载链接/条件存储实现？

如果没有，如果 Solaris 为用户模式 ​​C 代码提供任何 API 以利用 ll/sc 怎么办？

所以; 在符合 v9 的 64 位 SPARC CPU 上，存在我知道cas指令。这对单个字长值进行操作。

我还在网上看到了对casx指令的引用——但我找不到更多关于它的信息。

我想知道 - 这是一个双字比较和交换吗？

如果不是，一般的问题是；是否有双字比较和交换？

对于一个简单的指针增量分配器（他们有正式名称吗？）我正在寻找一种无锁算法。这似乎微不足道，但我想获得一些反馈，无论我的实施是否正确。

不是线程安全的实现：

我对线程安全实现的尝试：

whereCMPXCHG是与参数的互锁比较交换(destination, exchangeValue, comparand)，返回原始值

对我来说看起来不错 - 如果另一个线程在 get-current 和 cmpxchg 之间分配，则循环再次尝试。任何意见？

有人告诉我 Clojure 具有无锁并发，这很重要。

我使用了多种语言，但没有意识到它们在幕后执行锁定。

为什么这是 Clojure（或任何具有此功能的语言）的优势？

我只阅读了一点关于这个主题的内容，但似乎唯一的好处是解决争用问题，但它不会对死锁问题产生任何重要影响，因为无锁代码是如此之小和基本（fifos， lifos, hash) 从来没有出现过死锁问题。

所以这一切都与性能有关——对吗？

Summary:

It seems to me that:

1. wrapping fields representing a logical state into a single immutable consumable object
2. updating the object's authoritative reference with a call to Interlocked.CompareExchange<T>
3. and handling update failures appropriately

provides a kind of concurrency that renders the "lock" construct not only unnecessary, but a truly misleading construct that dodges certain realities about concurrency and introduces a host of new problems as a result.

Problem Discussion:

First, let's consider the main problems with using a lock:

1. Locks cause a performance hit, and must be used in tandem for reading and writing.
2. Locks block thread execution, hindering concurrency and risking deadlocks.

Consider the ridiculous behavior inspired by the "lock". When the need arises to update a logical set of resources concurrently, we "lock" the set of resources, and we do so via a loosely associated, but dedicated locking object, which otherwise serves no purpose (red flag #1).

We then use the "lock" pattern to mark-off a region of code where a logically consistent state change on a SET of data fields occurs, and yet we shoot ourselves in the foot by mixing the fields with unrelated fields in the same object, while leaving them all mutable and then forcing ourselves into a corner (red flag #2) where we have to also use locks when reading these various fields, so we don't catch them in an inconsistent state.

Clearly, there's a serious problem with that design. It's somewhat unstable, because it requires careful management of the lock objects (locking order, nested locks, coordination among threads, blocking/waiting on a resource in use by another thread that's waiting for you to do something, etc.), which depends on the context. We also hear people talk about how avoiding deadlock is "hard", when it's actually very straightforward: don't steal the shoes of a person you plan on asking to run a race for you!

Solution:

Stop using "lock" altogether. Properly roll your fields into an incorruptible/immutable object representing a consistent state or schema. Perhaps it's simply a pair of dictionaries for converting to and from display-names and internal-identifiers, or maybe it's a head node of a queue containing a value and a link to the next object; whatever it is, wrap it into it's own object and seal it for consistency.

Recognize write or update failure as a possibility, detect it when it occurs, and make a contextually informed decision to retry immediately (or later) or do something else instead of blocking indefinitely.

While blocking seems like a simple way to queue a task that seems like it must be done, not all threads are so dedicated and self-serving that they can afford to do such a thing at the risk of compromising the entire system. Not only is it lazy to serialize things with a "lock", but as a side affect of trying to pretend a write shouldn't fail, you block/freeze your thread, so it sets there unresponsive and useless, forsaking all other responsibilities in its stubborn wait to accomplish what it set out to do some time earlier, ignorant of the fact that assisting others is sometimes necessary for fulfilling it's own responsibilities.

Race conditions are normal when independent, spontaneous actions are occurring simultaneously, but unlike uncontrolled Ethernet collisions, as programmers we have total control over our "system" (i.e. deterministic digital hardware) and its inputs (no matter how random, and how random can a zero or one really be?) and outputs, and the memory that stores our system's state, so livelock should be a non-issue; furthermore, we have atomic operations with memory barriers that resolve the fact that there may be many processors operating concurrently.

To summarize:

1. Grab the current state object, consume its data, and construct a new state.
2. Realize that other active threads will be doing the very same thing, and may beat you to it, but all observe an authoritative reference point representing the "current" state.
3. Use Interlocked.CompareExchange to simultaneously see if the state object you based your work on is still the most current state, and replace it with your new one, otherwise fail (because another thread finished first) and take appropriate corrective action.

The most important part is how you handle the failure and get back on your horse. This is where we avoid livelocks, thinking too much and not doing enough or doing the right thing. I would say that locks create the illusion that you'll never fall off your horse, despite riding in a stampede, and while a thread daydreams in such a fantasy land, the rest of the system can fall apart and crash and burn.

So, is there something the "lock" construct can do that can't be achieved (better, in a less unstable fashion) with a lock-free implementation using CompareExchange and immutable logical state objects?

All of this is a realization I've come to on my own after dealing with locks intensely, but after some searching, in another thread Is lock free multithreaded programming making anything easier?, someone mentions that lock-free programming is going to be very important when we face highly parallel systems with hundreds of processors, were we cannot afford to use highly contended locks.