问一个关于无锁编程的问题

[AceCandy]

看了一些说无锁编程的文章，还是有些不太理解到底什么是无锁。 感觉上是说 cas 自旋就是无锁，那自旋锁不也是靠 cas 自旋吗？ 所以自旋锁是无锁编程？

[CRVV]

lock-free 的算法需要用到 cas，但不是说用到了 cas 就是 lock-free
比如用 cas 来实现 counter 就是 lock-free，但用 cas 实现的自旋锁就不是 lock-free

具体的定义在 wiki 里面有写 https://en.wikipedia.org/wiki/Non-blocking_algorithm
A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress.

比如一共有 10 个线程，有一个线程在拿着锁的情况下被停了下来，其它的线程也拿不到这个锁，整个系统就停了。
避免这种情况出现的算法叫 lock-free

[anthow]

不阻塞。

[hxndg]

这个逻辑是不可叠加的，

@anthow 说的实际上更精确，应该叫做无阻塞。

[hxndg]

当然，无阻塞不代表不需要付出代价

[codehz]

无锁的定义和锁倒是没有直接联系，只要求当任意线程在任意时刻卡死时（但是不能死光）起码剩下的线程中至少还有一个能继续跑（无等待就是剩下没死的线程都能继续跑）
卡死可以理解为依据设定跑一个死循环，或者调度器不再调度到那个线程，而不要管为啥（这里必须假设 CAS/FAA 一类的操作不能被任意方式打断，要么没有执行到，要么已经执行过了，原则上关闭中断也算，但是这里就复杂化了）。
继续跑的定义就比较麻烦了，通常可以理解为在有限步骤内能成功完成（失败的不算，比如你拿不到锁直接返回错误的那种）。
普通的无锁允许出现某个线程永远无法继续，（因为只要求至少一个，只要保证系统中永远存在两个或以上的线程在运行，其中一个就可以一直卡下去，即所谓的饿死）无等待要求所有线程都要能在有限步骤完成（除了依据设定卡死的）
所以判定一个算法是不是无锁的就很简单了，只要找不到任何一种能让所有剩余线程卡死的中断点的组合（也就是每个选中线程都按设定在特定位置停下，并且此时其他线程也按设定跑到特定的位置，可以理解为极端条件），就是无锁算法，而如果甚至无法让剩余线程中的任意一个卡死，那就是无等待算法。

[leviathan0992]

lock free (cas) 主要是避免操作系统因为 mutex 陷入内核中断导致 context switch 的开销

[bugmakerxs]

我其实不是很理解 cas 为啥说是无锁的，因为他包含两个动作
1. Compare
2.set
如果 cas 是一个原子操作的话，必须保证动作 2 前不会有其他线程修改我已经比较过的值，那就一定会有锁。

我挖到的最底层是 cmpxchg 指令，再往深没挖了。。

[raaaaaar]

读-复制-写？

[AceCandy]

@codehz 自旋锁不是属于在有线程卡死的时候剩下的线程还在跑吗？

[codehz]

@AceCandy 如果让持有锁的线程一直不释放不就其他的就没法继续了，不能在有限的步骤内完成，不要问为啥让它不释放，这就是无锁算法定义的一部分，CAS/FAA 不可拆分更是前提条件，这玩意就是证明题，前置条件满足了之后，证明不可能存在这个特殊情况，就证明了算法是无锁的，反之就是阻塞的。

@bugmakerxs CAS 由 cpu 实现者保证至少有一个线程能在任意冲突场景的情况下写入成功（当然，总得符合条件，你不能全部参与比较的都不与原值相等），至于 cpu 怎么实现的，并不重要，因为这属于定义的一部分，不符合这个定义的，就不是这个上下文里的 CAS 操作。
（话说回来，CAS 通常是作为无锁算法实现的基础组件，很少会有恰好只需要 CAS 就可以完成的需求，另外 CAS 也可以用于实现阻塞算法）

[LeeReamond]

@bugmakerxs 一看就是看了马士兵的视频被忽悠傻了。。cas 写入当然要保持原子性，保持原子性意思是硬件层面上总是要有个锁的。不过问题在于硬件级别的锁，跟你程序里实现的各种级别的锁，能是一个概念么。。

[bugmakerxs]

@LeeReamond 没看过马士兵的视频，硬件级别的锁，jvm 层面的锁，分布式锁，在我看来本质上都一样，所以网上说的 CAS 是『无锁』我就觉得很奇怪。

[guyeu]

自旋也是阻塞，但用 CAS 的话，set 失败不一定要自旋等待的。

[no1xsyzy]

@bugmakerxs 你要上层来看，Haskell （极端点 coq ）最后还不是得运行 CPU 指令？这并不影响它是纯函数式。

[byaiu]

无锁的本意是不要被 kernel schedule 出去……只要满足这个的多线程应该就算无锁了

原子操作参考 c++里的 atomic 。

[FrankHB]

无锁指的是没等一直傻等在锁上，无死锁 /活锁。
CAS 只是个 primitive，自身不保证 non-blocking 。

[LeeReamond]

@bugmakerxs 硬件实现原子操作的指令一样而已，我不理解你所谓的本质一样是什么意思。有的锁需要切换内核态，与不需要切换的锁，本质相同吗？我不觉得

[bugmakerxs]

@LeeReamond 本质上都需要独占资源。

[GrayXu]

@bugmakerxs 你理解是错误的。因为 CAS 操作的原子性是在硬件上来支持保证的，所以操作内部不需要上锁。虽然 CAS 需要消耗资源，但避免的是 context switch 的开销。

[bugmakerxs]

@GrayXu 硬件上的支持是指？可以具体点吗