"Lock Free"的流行是什么?事情，队列等 [英] What's with the popularity of "Lock Free" thingies, queues, etc

问题描述

嗨.请忍受，因为这是一个严重的问题.我无法弄清楚为队列等寻找终极无锁"算法的普及程度.我刚刚读完文章还实现了无锁循环数组队列 [一种无锁FIFO的乐观方法队列 [ ^ ]

这是我的困惑，所有涉及N生产者和M生产者的文章最终都会创建某种循环，用while(true){}或do{}while (CAS...)块包装一组指令.这两篇引用的文章都证明了这一点.实际上，它们用自旋循环"代替了阻塞操作，该循环一直持续到操作成功为止，而没有其他进程的争用.

早在20世纪60年代，我们就将其称为自旋锁"，使用读取/修改/写入"硬件指令来测试/设置"条件来保护代码块.早期的IBM/360带有"TS"(测试和设置). PDP-10具有"AOSE"(加1，如果等于零则跳过)，允许类似的逻辑.

我见过的许多算法随后都使用了复杂的方法来检测和不一致的队列设置或"ABA"问题，基本上发现指针已被重用，并且不再指向您认为它已经做什么了.通常引入对象序列号来解决此问题.

现在我的问题.为什么要经历所有这些复杂的步骤?为什么不使用最简单的解决方案呢?我的意思是，您想要避免在低争用"情况下避免使用系统调用进行锁定(Mutex，条件变量等)，因为这种情况很少发生在队列(或其他任何原因)上的冲突.如果人们愿意在争用情况下使用计算绑定旋转循环"，为什么不只是

Hi. Please bear with me as this is a serious question. I cannot figure out the popularity of searching for the ultimate "lock free" algorithm for queues, etc. I just finished reading an article Yet another implementation of a lock-free circular array queue[^] and followed up on some of the references and Googled some other articles, going back almost 20 years. For reference, see An Optimistic Approach to Lock-Free FIFO Queues[^]

Here''s my confusion, all of the articles that address the N-producers and M-consumers end up creating some sort of loop, a while(true){} or do{}while (CAS...) block to wrap a set of instructions. Both referenced articles demonstrate this. Effectively, they replace a blocking operation with a "spin loop" that continues until the operation succeeds without contention from other processes.

Back in the ''60s, we used to call this a "spin lock", protecting a block of code using a "read / modify / write" hardware instruction to "test / set" a condition. Early IBM/360s had "TS" (Test and Set). PDP-10''s had "AOSE" (Add one and skip if equal to zero) allowing similar logic.

Many of the algorithms I''ve seen then used complicated methods to detect and inconsistent queue setup or the "ABA" problem, basically discovering a pointer has been reused and doesn''t point to what you think it does anymore. Object serial numbers are usually introduced to alieviate this problem.

Now my question. Why go through all these convoluted steps? Why isn''t the simpliest solution used instead? I mean I get it, you want to avoid using system calls for locking (Mutex, Conditioned Variables, et al) for the "low contention" cases, when collisions on the queue (or whatever) are rare. If folks are willing to use a "compute bound spin loop" during contention cases, why not just

// assume "m_lock_taken" is initialized to 0 (false)
...
while (!CAS(&m_lock_taken, 0, 1));
// do enqueue or dequeue now that you own the "lock"
m_lock_taken = 0;
...

简单的旋转，无需复杂的检测也无需放松.它具有自旋循环的所有缺点，因为它浪费了cpu时间，直到释放锁为止，什么都不做，可能是m_lock_taken变量的内存争用，更糟的是，当N + M超过系统中的处理器/核心数时，旋转线程正在使用可以赋予拥有锁并由and事件或调度程序抢占的线程的执行周期.我根本不理解所有复杂性的需求.

而且，如果您关心减少CPU时间，那么您想要的情况是，在没有争用的情况下快速取出锁，而在发生罕见争用的情况下则等待对象(Mutex，条件变量).

我一直以来的经验是，当多个线程需要访问一个结构/对象时，该对象需要多个数据项才能保持一致，然后该对象才变为有效"状态，该序列需要通过互锁"进行保护，阻塞或循环.

到目前为止，我所看到的所有算法最终都只是实现了这种简单的情况，即循环执行，直到复杂的操作集产生一致的对象状态为止，但还有更多更简单的方法可以执行此操作.

Simple spin, no complex detection nor unwinding. It has all the drawbacks of a spin loop in that it chews up cpu time doing nothing until the lock is released, probably memory contention for the m_lock_taken variable, and worse, when the N+M exceeds the number of processors / cores in the system, the spinning thread is using execution cycles that could be given to the thread that owns the lock and was pre-empted by and event or the scheduler. I simply do not understand the need for all the complexity.

And if you care about chewing up cpu time, then what you want is the case where the lock is taken out quickly when there is no contention and a waitable object (Mutex, Conditioned Variable) when the rare contention happens.

It has always been my experience that when multiple threads need to access a structure / object that need more than 1 data item to be in a consistent state before the object is "valid", that sequence needs to be protected by an "interlock", blocking or looping.

All the algorithms I''ve seen so far end up implementing just this simple case, loop until the complex set of operations yield a consistent object state yet there are far more simple ways of doing that exact thing.

Discuss?

推荐答案

无锁算法解决了与锁的概念相关的问题，而不是与锁的实现有关的问题.用自旋锁替换操作系统提供的互斥锁不会使您的算法变为无锁:它仍然处于锁定状态，只会浪费很多.

考虑您对自旋锁的实现.线程刚将<1>交换到m_lock_taken中，并且将做一些有用的工作.但是随后调度程序出现了，并使该线程进入睡眠状态！其余线程将等待m_lock_taken变为"0"，但是直到允许锁所有者再次运行时，它才会发生.因此，剩下的线程将在进行零进度时浪费大量CPU时间.

与自旋锁相反，无锁算法中的自旋循环以这样的方式设计:仅当竞争线程有所进展时，才使线程自旋.结果，保证了来自竞争线程束的至少一个线程正在取得一些进展.这与竞争线程不取得进展时的旋转不同，后者在自旋锁的情况下会发生这种情况:如果锁的所有者已经预先拥有，则竞争线程组将不会取得任何进展. -empted.

Lock-free algorithms solve problems associated with the very concept of locking, not with an implementation of it. Replacing OS-supplied mutex with a spin lock does not make your algorithm lock-free: it''s still locking, only with a lot more waste.

Consider your implementation of the spin lock. A thread has just swapped "1" into the m_lock_taken, and is about to do some useful work. But then the scheduler comes along, and puts that thread to sleep! The remaining threads will be waiting for m_lock_taken to become "0", but it''s not going to happen until the lock owner is allowed to run again. So the remaining threads would waste a lot of CPU time while making zero progress.

In contrast to spin locks, spin loops in lock-free algorithms are designed in such a way as to make your thread spin only when a competing thread makes some progress. As the result, at least one thread from the competing bunch is guaranteed to be making some progress. This is different from spinning when a competing thread does not make progress, which is what happens in case of spin locks: the group of competing threads will be making no progress if the owner of the lock has been pre-empted.

这篇关于"Lock Free"的流行是什么?事情，队列等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！