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

假如 CPU 只有一个核心,使用 CAS 并发竞争的问题

  •  
  •   zhongpingjing · 172 天前 · 4855 次点击
    这是一个创建于 172 天前的主题,其中的信息可能已经有所发展或是发生改变。
    两个线程互相竞争,A 线程获取锁执行,B 线程通过自旋来获取锁。
    cpu 只有一个核心,A 线程占用了 CPU,B 应该不能自旋了吧??是不是只能等 A 执行完毕
    第 1 条附言  ·  170 天前
    太感谢大家了,看了很多人的回答,收获很大!!!!!谢谢!
    72 条回复    2021-05-12 09:29:46 +08:00
    viakiba
        1
    viakiba   172 天前 via iPhone
    我记得 linux 是分时调度
    iseki
        2
    iseki   172 天前
    单核心时不能使用自旋锁
    ch2
        3
    ch2   172 天前   ❤️ 3
    单核心不需要加锁
    opengps
        4
    opengps   172 天前
    虽然有锁避免了多线程争用,但是对于单核来讲,多线程只能是轮流上岗运行的,这时候的任何线程都是要互相等待的,这也是为什么很多小众的云厂商直接从 2 核起步销售的原因,因为单核上做的工单支持过多了,单核不适合硬烧 cpu 的线上业务
    nlzy
        5
    nlzy   172 天前   ❤️ 1
    。。。。。。这些都是计算机操作系统课程里的基本知识了

    即使计算机只有一个 CPU 核心,操作系统也可以为进程提供同时运行的假象,这叫并发。背后的原理楼上提了,就是分时调度。

    题外话:在编写并发程序的时候,即使 CPU 只有一个核心,也必须要施同步(如加锁)。
    vk42
        6
    vk42   172 天前
    如楼上所说单核中 spinlock 是没有意义的,具体以 Linux 来说单核情况下 spinlock 相当于 nop
    Stain5
        7
    Stain5   171 天前
    @nlzy 操作系统里的并发是对于不同进程间的吧,但这一过程对于单核系统的线程并没有起到并发的作用
    raysonx
        8
    raysonx   171 天前 via iPad
    楼上好多误导楼主的。即使只有一个核,多个线程的情况下也是要加锁的,因为你无法控制操作系统进行线程调度的时机。比如在对一个变量的读和写之间切换到了另一线程就会发生 race condition 。
    Jooooooooo
        9
    Jooooooooo   171 天前
    说到硬件的话就复杂了

    现在很多硬件一个核也可以并行两个线程的, 不上下文切换, 共享计算单元等等
    opengps
        10
    opengps   171 天前
    @Jooooooooo 借问一下,CPU 下由于存在逻辑 cpu,我能大概理解并行的意思。vCPU 下也是你说的这样不用上下文切换不?
    Jooooooooo
        11
    Jooooooooo   171 天前   ❤️ 1
    @opengps 搜一下 simultaneous multi threading
    beichenhpy
        12
    beichenhpy   171 天前
    楼主想说的是单核不能做多线程吗?可以吧。。都能新建多线程,不能用吗。。
    ivechan
        13
    ivechan   171 天前   ❤️ 1
    >cpu 只有一个核心,A 线程占用了 CPU,B 应该不能自旋了吧??
    是的,A 线程占用了 CPU,B 线程的代码无法执行

    >是不是只能等 A 执行完毕
    不是的。即使 A 线程占用了 CPU,那也不意味着你能一直占着直到你的任务结束。
    有因素会打算 A,然后切换到 B 。比如分给 A 任务的时间消耗完了,A 被调度出去;
    比如中断和抢占打断了。


    另外,不要用户态使用自旋锁,非常非常地愚蠢,除非你真的清楚自己在做什么。
    引用 Linus 的话:
    >I repeat: do not use spinlocks in user space, unless you actually know what you're doing. And be aware that the likelihood that you know what you are doing is basically nil.
    fengjianxinghun
        14
    fengjianxinghun   171 天前
    @ivechan

    Linus 也不是神,大伙都在用户态 spinlock

    h_t_tps://github.com/facebook/folly/blob/master/folly/synchronization/MicroSpinLock.h
    vk42
        15
    vk42   171 天前
    @raysonx 没人说多线程不需要锁,lz 问的是自旋锁好吧……只有单个执行核心的情况下多线程直接用阻塞锁,用自旋锁只会浪费时间,而如果是在内核关中断的情况下甚至会有死锁。
    emSaVya
        16
    emSaVya   171 天前
    @nlzy@raysonx 问的是 spinlock 答的什么东西 单核多线程 spinlock 无意义 遇到锁优化的 case 也不会执行自旋
    raaaaaar
        17
    raaaaaar   171 天前 via Android
    自旋锁用在频繁上下文切换比自选的开销大时使用比较多,比如信号量对里面的计数器的操作就用的自选锁,一般内核态比较多,用户态用自选锁太愚蠢了,话说所谓自选锁,你直接实现就是开个循环一直轮询,没干啥事还一直占用时间片,开销也太大了。所以一般都是用睡眠唤醒来代替的。

    至于锁和核心的问题,锁主要用在进线程的同步互斥直接,和核心的关系不是很大,由于线程可以再用户态或者核心态实现,如果在用户态实现,哪怕是单核心的 u,照样宏观上使用自选锁啥的也没有问题。因为线程间抢占的是资源,是资源的竞争而不是 cpu 时间片。比如说,线程 a 在使用 s 资源,这时线程 b 也请求 s 资源,假设是单核心,现在 u 分给了 a,a 使用一段时间,但是时间片到了轮给 b,不过 a 还没有释放 s 资源,到 b 后由于请求的资源 s 没有被释放,那么 b 就一直轮询,也就是执行循环的指令。当然由于是单核心的,s 不可能被释放,所以 b 就只能一直到时间片结束,又到 a,直到 a 释放 s 资源。可以说 b 忙等待了个寂寞。

    从上面也可以看出来,为什么在用户态要少用自选锁,当然如果用的信号量或者互斥锁啥的,是睡眠等待机制,那么轮到 b 后,发现 s 资源没有被释放,所以 b 调用 block 原语,阻塞掉自己陷入睡眠态,u 又轮到 a,直到 a 释放 s 资源后调用 wake 原语唤醒 b 。
    Leviathann
        18
    Leviathann   171 天前 via iPhone
    单核因为没有并行,所以不可能在自旋期间发现锁被释放?
    raysonx
        19
    raysonx   171 天前 via iPad
    @vk42 我表达的意思是多线程单核心依然需要锁,否则程序运行可能会出错。一个程序是不是需要加锁不是由执行环境有几个核心决定的,所以楼主的问题根本不需要考虑环境因素。
    raysonx
        20
    raysonx   171 天前 via iPad
    @emSaVya 你能不能好好说话?我表达的意思是需不需要加锁和核心数无关,扯什么单核多线程 spinlock 无意义? i/o 密集应用经常使用单核多线程的模式,照样可以用自旋锁,
    raysonx
        21
    raysonx   171 天前 via iPad
    @Leviathann 操作系统会给多线程分配不同的时间片,一个线程的时间片用完就会被操作系统挂起调用另一个线程,切换后会发现的。
    raysonx
        22
    raysonx   171 天前 via iPad
    楼主的问题在我理解看来,是问是不是只有一个核心的情况下就没有并发了,自旋锁是不是根本就不会自旋了。答案是否,单核心情况下多个线程会被分配不同时间片进行并发,自旋期间也可能会被切换到另一个线程再切换会来。
    zmxnv123
        23
    zmxnv123   171 天前 via iPhone   ❤️ 2
    楼上某人单核心不加锁是搞笑的吗

    你要是平时写汇编我承认你是大佬,不然建议会大学重修操作系统
    IndexOutOfBounds
        24
    IndexOutOfBounds   171 天前
    有人占着锁(临界区不可中断不是指不能上下文切换),该自旋还是会自旋,只不过单核下自旋没有意义
    LeeReamond
        25
    LeeReamond   171 天前 via Android
    @IndexOutOfBounds 有没有意义倒可以讨论一下,我感觉应该还是有,sl 除了多核心下高效利用时间片以外,单核心中也可以避免挂起的系统调用开销啊
    raaaaaar
        26
    raaaaaar   171 天前 via Android
    @LeeReamond 一般上下文切换的开销要比忙等待的开销小很多。。只有内核态那种很短的时间下可能会用到
    IndexOutOfBounds
        27
    IndexOutOfBounds   171 天前
    @LeeReamond 持有锁的线程不运行,单核自旋在时间片内注定等不到锁,不如直接阻塞,反正时间片一到也得去歇着。可能没解释对,但是我看到一些源码貌似就是基于此结论的

    loopNum = coreNum == 1 ? 1 : 64 ( ConcurrentHashMap#put#1.7#伪代码)
    dalabenba
        28
    dalabenba   171 天前 via Android
    @raysonx race condition 的原因是 core 对同一地址的写对其他 core 不可见,需要用 cas 以及 mem barrier 来保证同步,同一个核不需要锁
    raysonx
        29
    raysonx   171 天前 via iPad
    @dalabenba mem barrier 和这个问题无关。即使所有核都直接读写内存,也需要加锁。加锁与否与核数无关,而是保证对同一地址的 Read- Modify- write 期间不会被另一个线程改写。单核情况下不加锁照样 race condition
    iseki
        30
    iseki   171 天前 via Android
    单核心不能用自旋锁,另外 linus 建议不要在用户态瞎搞自旋锁,似乎是会影响调度器的判断,对吞吐量没有什么好处
    dalabenba
        31
    dalabenba   171 天前 via Android
    @raysonx 是我想错了,确实要加锁
    raysonx
        32
    raysonx   171 天前 via iPad
    我已经懒得去重复多线程单核心需要锁这一观点了。即使自旋锁在这种情况下效率低,也不能说可以去掉锁。不信的自己开个单核虚拟机写个程序跑跑就知道了。
    OSDI
        33
    OSDI   171 天前 via Android
    @raysonx lock free 呢,单核单线程自旋锁感觉就是没啥用啊,反正都得上下文切换
    raysonx
        34
    raysonx   171 天前 via iPad
    @OSDI 我觉得楼主并不是要讨论自旋锁在单核环境下好不好的问题,讨论这个问题就偏题了。
    GeruzoniAnsasu
        35
    GeruzoniAnsasu   171 天前
    @raysonx 反复看了十几遍这楼咋觉得你才是理解偏了的。。

    你说得没错但确实
    单核多线程自旋锁无意义


    lz 想问的不就是单核多线程时调度到 A 线程,B 线程的自旋还在不在旋吗,不旋,B 线程根本就不执行,这都没啥疑问吧

    原问“是不是只能等 A 执行完毕” 有歧义所以引发了争论,厘清一下:
    1. 确实必须得等 A 的时间片执行完毕
    2. 不必等 A 线程执行完毕






    补充一下,单核多线程这种并发条件下,B 线程根本没法通过自己去“抢占”资源,如果 A 没有释放锁,B 拿到的时间片会全部浪费在自旋上,还不如直接等待
    GuuJiang
        36
    GuuJiang   171 天前   ❤️ 2
    这篇帖子生动地展示了什么叫作“你在第二层,你以为我在第一层,实际我在第五层”
    按照“是不是只能等 A 执行完毕”这样的表述,提问者应该在第一层,估计还没有形成时间片这个概念,于是第二层的人敏锐地意识到了这一点,指出了不管是不是单核,实际都有并发,但是这个帖子好巧不巧提到了自旋,于是引来了第五层的人,指出了在单核环境下自旋是无意义的,但是第二层的人无法区分第一层和第五层,把所有第五层的对手都当第一层的来辩论
    ipwx
        37
    ipwx   170 天前
    不要使用自旋——但是有些场景例外。比如你要争取在一个消息队列系统里面消除 20us 的调度延迟(如果用 mutex 等待大概就是这个量级)
    namelosw
        38
    namelosw   170 天前
    菜鸡有个问题想问第五层的大佬:

    单核自旋没意义,这个结论是否适用于单核有超线程 (HT 不是多线程) 的情况?
    raysonx
        39
    raysonx   170 天前
    @GuuJiang 单核环境下自旋当然不是无意义的,起到加锁的作用就是它的意义,只是比较浪费 CPU 计算资源而已,去掉锁会出错。讨论单核下自旋锁是不是一个比较优的方案偏离本题。
    IndexOutOfBounds
        40
    IndexOutOfBounds   170 天前   ❤️ 1
    @namelosw
    单核超线程,只是充分利用上下文切换的时间而已。
    不能并行,自旋就没有意义
    GuuJiang
        41
    GuuJiang   170 天前
    @raysonx 这就是你和其他所有人分歧的出发点,没有人说过去掉锁啊,锁是目的,自旋锁只是其中一种手段,去掉自旋 != 去掉锁,不管怎么说,也改变不了在单核环境中自旋就是被优化掉了这个事实
    GuuJiang
        42
    GuuJiang   170 天前
    更正一下,甚至我自己说的“自旋锁只是其中一种手段”这句话都是不准确的,自旋并不是锁的必要条件,锁也不是靠自旋实现的,有没有自旋,自旋多少次都不影响锁行为的正确性,自旋的存在仅仅是作为“预期能够很快得到锁,自旋的代价小于 wait 的代价”这一前提下的一种优化手段而已,既然是优化,那自然是可以调整其参数甚至去掉的
    如果“预期能很快得到锁”这个条件满足,那么自旋带来的收益就是正的,如果条件不满足,那还不如不自旋,而在单核条件下这个条件显然是不可能满足的,那关掉自旋(其实就是把自旋次数改为 0)也是一种很自然的选择
    lsylsy2
        43
    lsylsy2   170 天前
    总有种上面争吵双方其实是友军的感觉……

    两个线程互相竞争,A 线程获取锁执行,B 线程通过自旋来获取锁。

    Q:cpu 只有一个核心,A 线程占用了 CPU,B 应该不能自旋了吧??
    A:可以,只不过如果明知只有一个核心的话,这里不应该用自旋,而是用其他的锁,因为自旋在这里“性能约等于浪费 CPU 的 mutex 锁”;
    如果需要兼容各种情况,自旋锁是可以用的,只不过在单核的情况下性能较差而已,是可以工作的。

    Q:是不是只能等 A 执行完毕
    A:如果你的“执行完毕”指的是用 mutex 锁之类基于上下文切换的锁,是的;如果指的是“A 的线程完全运行结束,退出这个线程”,那么不是的,在单核的系统里操作系统也会在多个线程间切换,所以多线程读写数据的时候依旧会有并发、加锁的问题需要处理。
    lsylsy2
        44
    lsylsy2   170 天前
    我这里预设的 LZ 的情景是:开发了一款使用自旋锁的多线程软件,想探讨单核机器上运行该软件是否有影响
    这个情景的答案是:性能较低,但是可以正确执行。
    raysonx
        45
    raysonx   170 天前
    @GuuJiang 我觉得你在这里把自旋锁理解为了“先自旋,自旋一定次数后再等待普通锁”这种范式,在你的这种语境下自旋只是一种优化手段。而我的讲的自旋锁是纯自旋锁,最差情况下会无限次自旋那种。
    raysonx
        46
    raysonx   170 天前
    这种理解的不同会让你认为去掉自旋也不会影响程序的正确性。而在我的语境下自旋就是锁本身。
    WuSiYu
        47
    WuSiYu   170 天前
    没必要用自旋锁(不会有优势,纯粹浪费 CPU time ),但你非要这么用也是可以工作的
    raysonx
        48
    raysonx   170 天前
    我讲的自旋锁是类似这种:

    class SpinLock {
    std::atomic_flag locked = ATOMIC_FLAG_INIT ;
    public:
    void lock() {
    while (locked.test_and_set(std::memory_order_acquire)) { ; }
    }
    void unlock() {
    locked.clear(std::memory_order_release);
    }
    };
    Akiya
        49
    Akiya   170 天前 via iPhone
    单核开多线程的意义是什么?
    vk42
        50
    vk42   170 天前
    @raysonx 你要不要再看看 lz 提问描述和我的回答?哪里说了不需要锁了?
    vk42
        51
    vk42   170 天前
    @raysonx 另外不要以偏盖全。内核的自旋锁和用户态自旋锁语义非常不同,Linux 内核中严格限制自旋锁只用来保护“真并行“情况下的竞争,普通并发情况下的竞争用 mutex,不能瞎用 spinlock
    OSDI
        52
    OSDI   170 天前 via Android
    @IndexOutOfBounds 超线程是可以多个线程同时执行的。
    zagfai
        53
    zagfai   170 天前
    系统 callback 可以打断进程
    zagfai
        54
    zagfai   170 天前
    准确来说说叫中断
    shayuvpn0001
        55
    shayuvpn0001   170 天前
    @GuuJiang
    第一层的人看到的是 HAL 下面的硬件行为,事实上单核在开启 SMT 的情况下,是一套算术逻辑单元对应两套寄存器阵列,在这个层级上,连内核空间和用户空间都不会进行区分的,拿到数据就放进去就执行。
    第二层的人注意到了操作系统的存在,在 HAL 以上看这个问题,这个层级上才有 Process, Thread 各种抽象的概念,有了这些才有锁,各种锁更像是操作系统提供的 facility 。
    IndexOutOfBounds
        56
    IndexOutOfBounds   170 天前
    @namelosw
    @OSDI
    #40
    sry,没有仔细考究就答了
    超线程确实可以并行,不过并行度有限,大概率还是无法并行
    至于自旋是否是特殊情况(用到的单元很少和其它线程冲突),不太懂

    总的来说我觉得,单核超线程实际并行度有限的话,自旋还是不如直接阻塞
    kikione
        57
    kikione   170 天前
    CAS 适用于 线程并发量比较低的情况。如果多个核心,在某个线程改变了旧值,占用 cpu 一个核心,其他线程也可以在其他核心上通过 while(true),不断尝试。如果只有一个核心,其他核心就没发去并发尝试了。所以 B 肯定不能自旋,这时候还不如用 synchronize 。
    zoharSoul
        58
    zoharSoul   170 天前
    @GuuJiang #36
    还有个在 负一层的, #12 楼, 不知道他怎么理解成楼主问能不能用多线程的, 还说能新建怎么会不能用, 真是企业级理解, 笑死我了
    4kingRAS
        59
    4kingRAS   169 天前
    这楼生动地展示了面试为什么要搞那么难的重要性,不难就招进来一群参差不齐的人,你在一层,我在三层,他在负一层,我们都以为自己很牛逼。
    killeder
        60
    killeder   168 天前
    感觉大部分都是 1/4 瓶子醋,只有这个 raysonx 兄弟是明白人
    ivechan
        61
    ivechan   167 天前
    @fengjianxinghun 你发的链接恰好证明 Linus 是对的。
    你难道没发现,你所发的代码,都特别注明,大部分情况下不要使用自旋锁吗?
    在能够抢占或者中断的操作系统里,用户态自旋锁在很多情况下都毫无意义(只会浪费 CPU 时间)

    “/*
    * N.B. You most likely do _not_ want to use MicroSpinLock or any
    * other kind of spinlock. Consider MicroLock instead.”
    fengjianxinghun
        62
    fengjianxinghun   167 天前
    @ivechan MicroLock 就是为了解决原始 spinlock 的问题。
    fengjianxinghun
        63
    fengjianxinghun   167 天前
    @ivechan MicroLock 之类的实现很接近 glibc 的 mutex 实现,先自旋计数,然后休眠让出 cpu 。
    现在都是 2 种结合处理。
    fengjianxinghun
        64
    fengjianxinghun   167 天前
    @fengjianxinghun 你只要在用户态用了 mutex,其实你就用了 spinlock

    https://code.woboq.org/userspace/glibc/nptl/pthread_mutex_lock.c.html
    ivechan
        65
    ivechan   166 天前
    @fengjianxinghun 你再仔细看看我说的话,和你说的话,确保你理解我的意思吧。
    ivechan
        66
    ivechan   166 天前
    @fengjianxinghun 在进入睡眠之前自旋一会尝试去获取锁那是因为有时候锁短时间内就能获取到,不必要走 slowpath,多了上下文切换等资源损耗。

    这就是我说的"除非你真的知道你在做什么"的场景。
    spinlock 没有问题,有问题用错场景的人。这里不是解决 spinlock 的问题,这里解决的是 muted lock 在发生竞争时 overhead 过多的问题。


    你没必要再拿这种打自己脸的例子来解释了,用户态锁场景下 99%都不应该用 spinlock,就是事实。
    说什么你用了 mutex 就是用了 spinlock 简直是偷换概念,胡搅蛮缠。



    重要的事情说三遍:

    N.B. You most likely do _not_ want to use MicroSpinLock or any
    * other kind of spinlock. Consider MicroLock instead.”


    N.B. You most likely do _not_ want to use MicroSpinLock or any
    * other kind of spinlock. Consider MicroLock instead.”


    N.B. You most likely do _not_ want to use MicroSpinLock or any
    * other kind of spinlock. Consider MicroLock instead.”
    fengjianxinghun
        67
    fengjianxinghun   165 天前
    @ivechan 那就不用讨论了,任何用户态锁实现,都会 spinlock 提高节省性能,避免直接陷入 syscall futex 。你用 mutex 你代码天生就有 spinlock 。我犯得着和你纠缠?也不用说服你。
    ivechan
        68
    ivechan   164 天前
    N.B. You most likely do _not_ want to use MicroSpinLock or any
    * other kind of spinlock. Consider MicroLock instead.”

    你连英语都不懂吗。。。
    aichunya
        69
    aichunya   164 天前
    @lsylsy2 Q1 有个地方不知道是我理解偏差还是您写的不够清晰,CPU 只有一个核心的话,A 线程占用了 CPU,在这个时间片内,B 线程应该是不能自旋了吧,因为此时此刻 B 线程没有 CPU 的执行权,如果 B 线程要自旋,必须要等 CPU 分配到了时间片吧?
    如果是我理解的话,倒是能理解你回答'可以'的含义了,如果不是的话,烦请再赐教(^_^)
    lsylsy2
        70
    lsylsy2   163 天前
    我来理一个单线程时间轴,以下每一行是一个时间片
    T1 A 获取锁,做事情(没做完)
    T2 B 自旋一整个时间片,一直失败
    T3 A 做完了事情,释放锁
    T4 B 自旋并一次成功,做事情
    T5 B 做完事情,释放锁
    lsylsy2
        71
    lsylsy2   163 天前
    @aichunya 忘记 at 了,在上面一条
    aichunya
        72
    aichunya   163 天前
    @lsylsy2 谢谢解答,这样正好也理解了楼上各位说的,在单线程情况下,自旋锁是浪费 CPU 时间的,因为不管如何自旋,都要等拿了锁的那个线程执行完毕,把锁释放之后才能自旋成功获取到锁,因此不能说不可以用.
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3872 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 06:54 · PVG 14:54 · LAX 23:54 · JFK 02:54
    ♥ Do have faith in what you're doing.