V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
AceCandy
V2EX  ›  程序员

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

  •  
  •   AceCandy · 2021-03-30 19:42:16 +08:00 · 2935 次点击
    这是一个创建于 1094 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    20 条回复    2021-05-22 17:32:08 +08:00
    CRVV
        1
    CRVV  
       2021-03-30 20:08:30 +08:00   ❤️ 3
    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
        2
    anthow  
       2021-03-30 20:37:31 +08:00
    不阻塞。
    hxndg
        3
    hxndg  
       2021-03-30 20:43:49 +08:00
    这个逻辑是不可叠加的,

    @anthow 说的实际上更精确,应该叫做无阻塞。
    hxndg
        4
    hxndg  
       2021-03-30 20:44:05 +08:00
    当然,无阻塞不代表不需要付出代价
    codehz
        5
    codehz  
       2021-03-30 21:46:40 +08:00   ❤️ 1
    无锁的定义和锁倒是没有直接联系,只要求当任意线程在任意时刻卡死时(但是不能死光)起码剩下的线程中至少还有一个能继续跑(无等待就是剩下没死的线程都能继续跑)
    卡死可以理解为依据设定跑一个死循环,或者调度器不再调度到那个线程,而不要管为啥(这里必须假设 CAS/FAA 一类的操作不能被任意方式打断,要么没有执行到,要么已经执行过了,原则上关闭中断也算,但是这里就复杂化了)。
    继续跑的定义就比较麻烦了,通常可以理解为在有限步骤内能成功完成(失败的不算,比如你拿不到锁直接返回错误的那种)。
    普通的无锁允许出现某个线程永远无法继续,(因为只要求至少一个,只要保证系统中永远存在两个或以上的线程在运行,其中一个就可以一直卡下去,即所谓的饿死)无等待要求所有线程都要能在有限步骤完成(除了依据设定卡死的)
    所以判定一个算法是不是无锁的就很简单了,只要找不到任何一种能让所有剩余线程卡死的中断点的组合(也就是每个选中线程都按设定在特定位置停下,并且此时其他线程也按设定跑到特定的位置,可以理解为极端条件),就是无锁算法,而如果甚至无法让剩余线程中的任意一个卡死,那就是无等待算法。
    leviathan0992
        6
    leviathan0992  
       2021-03-30 23:11:49 +08:00
    lock free (cas) 主要是避免操作系统因为 mutex 陷入内核中断导致 context switch 的开销
    bugmakerxs
        7
    bugmakerxs  
       2021-03-31 01:12:40 +08:00 via Android
    我其实不是很理解 cas 为啥说是无锁的,因为他包含两个动作
    1. Compare
    2.set
    如果 cas 是一个原子操作的话,必须保证动作 2 前不会有其他线程修改我已经比较过的值,那就一定会有锁。

    我挖到的最底层是 cmpxchg 指令,再往深没挖了。。
    raaaaaar
        8
    raaaaaar  
       2021-03-31 09:12:22 +08:00
    读-复制-写?
    AceCandy
        9
    AceCandy  
    OP
       2021-03-31 10:11:05 +08:00
    @codehz 自旋锁不是属于在有线程卡死的时候剩下的线程还在跑吗?
    codehz
        10
    codehz  
       2021-03-31 11:12:23 +08:00 via Android
    @AceCandy 如果让持有锁的线程一直不释放不就其他的就没法继续了,不能在有限的步骤内完成,不要问为啥让它不释放,这就是无锁算法定义的一部分,CAS/FAA 不可拆分更是前提条件,这玩意就是证明题,前置条件满足了之后,证明不可能存在这个特殊情况,就证明了算法是无锁的,反之就是阻塞的。

    @bugmakerxs CAS 由 cpu 实现者保证至少有一个线程能在任意冲突场景的情况下写入成功(当然,总得符合条件,你不能全部参与比较的都不与原值相等),至于 cpu 怎么实现的,并不重要,因为这属于定义的一部分,不符合这个定义的,就不是这个上下文里的 CAS 操作。
    (话说回来,CAS 通常是作为无锁算法实现的基础组件,很少会有恰好只需要 CAS 就可以完成的需求,另外 CAS 也可以用于实现阻塞算法)
    LeeReamond
        11
    LeeReamond  
       2021-03-31 11:34:36 +08:00 via Android
    @bugmakerxs 一看就是看了马士兵的视频被忽悠傻了。。cas 写入当然要保持原子性,保持原子性意思是硬件层面上总是要有个锁的。不过问题在于硬件级别的锁,跟你程序里实现的各种级别的锁,能是一个概念么。。
    bugmakerxs
        12
    bugmakerxs  
       2021-03-31 11:37:34 +08:00
    @LeeReamond 没看过马士兵的视频,硬件级别的锁,jvm 层面的锁,分布式锁,在我看来本质上都一样,所以网上说的 CAS 是『无锁』我就觉得很奇怪。
    guyeu
        13
    guyeu  
       2021-03-31 11:39:29 +08:00
    自旋也是阻塞,但用 CAS 的话,set 失败不一定要自旋等待的。
    no1xsyzy
        14
    no1xsyzy  
       2021-03-31 12:08:22 +08:00
    @bugmakerxs 你要上层来看,Haskell (极端点 coq )最后还不是得运行 CPU 指令?这并不影响它是纯函数式。
    byaiu
        15
    byaiu  
       2021-03-31 17:04:13 +08:00
    无锁的本意是不要被 kernel schedule 出去……只要满足这个的多线程应该就算无锁了

    原子操作参考 c++里的 atomic 。
    FrankHB
        16
    FrankHB  
       2021-03-31 18:23:32 +08:00
    无锁指的是没等一直傻等在锁上,无死锁 /活锁。
    CAS 只是个 primitive,自身不保证 non-blocking 。
    LeeReamond
        17
    LeeReamond  
       2021-04-01 00:45:29 +08:00 via Android
    @bugmakerxs 硬件实现原子操作的指令一样而已,我不理解你所谓的本质一样是什么意思。有的锁需要切换内核态,与不需要切换的锁,本质相同吗?我不觉得
    bugmakerxs
        18
    bugmakerxs  
       2021-04-01 07:58:39 +08:00
    @LeeReamond 本质上都需要独占资源。
    GrayXu
        19
    GrayXu  
       2021-05-12 17:05:05 +08:00
    @bugmakerxs 你理解是错误的。因为 CAS 操作的原子性是在硬件上来支持保证的,所以操作内部不需要上锁。虽然 CAS 需要消耗资源,但避免的是 context switch 的开销。
    bugmakerxs
        20
    bugmakerxs  
       2021-05-22 17:32:08 +08:00
    @GrayXu 硬件上的支持是指?可以具体点吗
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1147 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:01 · PVG 07:01 · LAX 16:01 · JFK 19:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.