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

• 資深大佬 : 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 本质上都需要独占资源。