精华内容
下载资源
问答
  • 2021-12-26 00:20:44

    一、为什么要锁?

    多线程编程有资源竞争。比如,线程A要在一个链表增删节点,线程B也要增删该链表,就可能相互踩踏。一种解决方案是,保证同一时刻只有一个线程在操作,操作完成之后其他线程再操作。锁的意义就是,拿到竞争资源的线程上锁,以保证独占该资源。其他线程要使用该资源,首先查看资源是否被锁,是就等待锁释放。

    二、为什么要多线程编程?

    程序有CPU密集型和IO密集型。有些工作需要等待IO或者其他条件,此时,该线程应该让出CPU以提高CPU效率(干等着是浪费CPU)。

    三、为什么要无锁?

    锁会使得应用低效,很多时候,锁就是应用瓶颈所在。

    四、为什么锁会低效?

    首先,上锁和释放锁,都需要模式切换,本身就是开销。上锁:由用户空间切换到内核空间,上锁后再切回到用户空间,这就是两次切换;释放锁也同样需要两次模式切换,一共是四次模式切换。

    另一个开销,在于进程上下文的切换。线程切换有两种场景:CPU时间片用尽、因阻塞被提前切换。拿竞争资源失败导致阻塞,会使得调度单元放弃未使用完的CPU时间片而切换到其他调度单元。也就是说,因为锁的缘故,导致上下文的切换更多了。无锁并发和CAS并不是说避免了上下文切换,而是减少了上下文切换。即,无锁并发则只有时间片用完后才进行线程切换。

    1、线程运行的时间片时间用完了,线程切换。
    2、若线程在时间片结束前阻塞或结束,线程切换。

    上下文切换需要保存、回复现场,这些都是CPU开销。

    五、如何无锁?Lock-Free

    无锁编程具体使用和考虑到的技术方法包括:原子操作(atomic operations), 内存栅栏(memory barriers), 内存顺序冲突(memory order), 指令序列一致性(sequential consistency)和顺ABA现象等等

    Read-Modify-Write。这其中最常用的原子操作又是 COMPARE AND SWAP(CAS),几乎所有的CPU指令集都支持CAS的原子操作。

    六、无锁编程的缺点

    无锁算法及相关数据结构并不意味在所有的环境下都能带来整体性能的极大提升。循环CAS操作对时会大量占用cpu,对系统时间的开销也是很大。这也是基于循环CAS实现的各种自旋锁不适合做操作和等待时间太长的并发操作的原因。而通过对有锁程序进行合理的设计和优化,在很多的场景下更容易使程序实现高度的并发性。
    在开发维护的成本和复杂度上,无锁编程难度非常高,类似ABA的问题也比较难直观的探测和解决,并且实现细节和硬件平台相关性很强。目前理论和实践上只有少数数据结构可以支持实现无锁编程,比如队列、栈、链表、词典等,目前要在产品业务开发环境中进行大规模的无锁编程较为困难,更多的是用在部分特殊场景解决锁竞争等问题比较合适,比如操作系统中实现metux,semaphare, 一些语言的库的实现(比如 java current lib, lmax disprute)。若想在应用开发中尝试的Lock-Free的方案,建议可以选择合适的第三方lib实现。
     

    更多相关内容
  • 多核多线程已经成为当下一个时髦的话题,而无锁编程更是这个时髦话题中的热点话题。Linux内核可能是当今最大最复杂的并行程序之一,为我们分析多核多线程提供了绝佳的范例。内核设计者已经将最新的无锁编程技术带进...
  • 深入理解无锁编程

    2021-07-27 01:03:16
    hi,大伙好,今天介绍一下无锁编程基础知识,希望大家可以了解无锁编程基本原理。无锁编程是一个挑战,不仅因为任务本身的复杂性,还因为从一开始就很难深入了解这个主题,因为该主题和底层技术(编译...

    hi,大伙好,今天介绍一下无锁编程基础知识,希望大家可以了解无锁编程基本原理。

    无锁编程是一个挑战,不仅因为任务本身的复杂性,还因为从一开始就很难深入了解这个主题,因为该主题和底层技术(编译器,CPU,内存)息息相关,需要深厚底层功底。

    我学习无锁编程是Bruce Dawson 出色而全面的白皮书Lockless Programming Considerations(无锁编程的思考)。和许多技术一样,需要将理论付诸实践,在平台上开发和调试无锁代码。

    在这篇文章中,我想重新介绍无锁编程,首先是定义它,然后将大部分信息提炼为几个关键概念。我将使用流程图展示这些概念如何相互关联,然后我们将深入研究细节。至少,任何从事无锁编程的程序员都应该已经了解如何使用互斥锁和其他高级同步对象(如信号量和事件)编写正确的多线程代码。

    它是什么?

    人们通常将无锁编程描述为没有互斥锁的编程,互斥锁也称为锁。这是真的,但这只是故事的一部分。基于学术文献的普遍接受的定义更广泛一些。从本质上讲,无锁是一种用于描述某些代码的属性,而无需过多说明该代码的实际编写方式。

    基本上,如果您的程序的某些部分满足以下条件,那么该部分可以理所当然地被认为是无锁的。相反,如果代码的给定部分不满足这些条件,则该部分不是无锁的。

    从这个意义上说,无锁中的锁并不直接指互斥锁,而是指以某种方式“锁定”整个应用程序的可能性,无论是死锁、活锁——甚至是由于由你最大的敌人。最后一点听起来很有趣,但这是关键。共享互斥锁被简单地排除在外,因为一旦一个线程获得互斥锁,您最大的敌人就再也不会调度该线程了。当然,真正的操作系统不是这样工作的——我们只是定义术语。

    这是一个不包含互斥锁但仍然不是无锁的操作的简单示例。最初,X = 0。作为读者的练习,考虑如何以一种方式调度两个线程,使得两个线程都不退出循环。

    while(X == 0 ) { 
        X = 1 - X; 
    }
    

    没有人期望大型应用程序是完全无锁的。通常,我们从整个代码库中识别出一组特定的无锁操作。例如,在一个无锁队列中,有可能是无锁的操作,比如极少数的pushpop也许isEmpty等。


    Herlihy & Shavit 是The Art of Multiprocessor Programming(多处理器编程的艺术) 的作者,倾向于将此类操作表示为类方法,并提供以下无锁的简洁定义:

    “在无限执行中,某些方法调用会无限频繁地结束” 

    换句话说,只要程序能够继续调用那些无锁操作,无论发生什么,完成的调用次数都会不断增加。在这些操作期间,系统在算法上不可能锁定。

    无锁编程的一个重要结论是,如果您挂起单个线程,它永远不会阻止其他线程作为一个组通过它们自己的无锁操作取得进展。这暗示了在编写中断处理程序和实时系统时无锁编程的价值,其中某些任务必须在一定的时间限制内完成,无论程序的其余部分处于什么状态。

    最后一个说明:某些操作被设计为阻塞的并不意味是这就不是Lock-Free的。例如,当队列为空时,队列的弹出操作可能会故意阻塞。其余的代码路径仍然可以被认为是无锁的。

    无锁编程技术

    事实证明,当您尝试满足无锁编程的非阻塞条件时,会出现一整套技术:原子操作、内存屏障、避免 ABA 问题,仅举几例。这就是事情很快变得邪恶的地方。

    那么这些技术如何相互关联呢?为了说明,我整理了以下流程图。下面我将逐一详述。

    原子读-修改-写操作

    原子操作是以一种看起来不可分割的方式操作内存的操作:没有线程可以观察到半完成的操作。在现代处理器上,许多操作已经是原子的。例如,简单类型的对齐读取和写入通常是原子的。

    读-修改-写(RMW) 操作更进一步,允许您以原子方式执行更复杂的事务。当无锁算法必须支持多个写入器时,它们特别有用,因为当多个线程在同一地址上尝试 RMW 时,它们将有效地排成一行并一次执行这些操作。我已经在这篇博客中谈到了 RMW 操作,例如实现轻量级互斥锁、递归互斥锁和轻量级日志系统时。

    RMW 操作的示例包括_InterlockedIncrementWin32、OSAtomicAdd32iOS 和std::atomic<int>::fetch_addC++11。请注意,C++11 原子标准并不能保证实现在每个平台上都是无锁的,因此最好了解您的平台和工具链的功能。你可以使用std::atomic<>::is_lock_free确认一下。

    不同的 CPU 系列以不同的方式支持 RMW。诸如 PowerPC 和 ARM 之类的处理器公开了load-link/store-conditional)条件指令,这有效地允许您在低级别实现自己的 RMW 原语,尽管这并不常见。常见的 RMW 操作通常就足够了。

    如流程图所示,即使在单处理器系统上,原子 RMW 也是无锁编程的必要部分。如果没有原子性,线程可能会在事务中途中断,从而可能导致状态不一致。

    Compare-And-Swap Loops

    也许最常讨论的 RMW 操作是compare-and-swap(CAS)。在 Win32 上,CAS 是通过一系列内在函数提供的,例如_InterlockedCompareExchange. 通常使用 CAS Loops 来完成对事务的原子处理:

    void LockFreeQueue::push(Node* newHead)
    {
        for (;;)
        {
            // Copy a shared variable (m_Head) to a local.
            Node* oldHead = m_Head;
    
            // Do some speculative work, not yet visible to other threads.
            newHead->next = oldHead;
    
            // Next, attempt to publish our changes to the shared variable.
            // If the shared variable hasn't changed, the CAS succeeds and we return.
            // Otherwise, repeat.
            if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead)
                return;
        }
    }

    这样的循环仍然符合无锁的条件,因为如果一个线程的测试失败,则意味着它必须在另一个线程上成功——尽管某些架构提供了CAS的较弱变体,而这不一定是真的。每当实现 CAS 循环时,必须特别注意避免ABA 问题。

    顺序一致性

    顺序一致性是指所有线程都同意内存操作发生的顺序,并且该顺序与程序源代码中的操作顺序一致。

    实现顺序一致性的一种简单(但显然不切实际)的方法是禁用编译器优化并强制所有线程在单个处理器上运行。处理器永远不会看到它自己的内存效果出问题,即使线程在任意时间被抢占和调度。

    一些编程语言即使对于在多处理器环境中运行的优化代码也提供顺序一致性。在 C++11 中,您可以将所有共享变量声明为具有默认内存排序约束的 C++11 原子类型。在 Java 中,您可以将所有共享变量标记为volatile. 这是我上一篇文章中的示例,以 C++11 风格重写:

    std::atomic< int > X( 0 ), Y( 0 );
    int r1, r2;
    void thread1()
    { 
        X.store( 1 ); 
        r1 = Y.load();
    }
    void thread2()
    { 
        Y.store( 1 ); 
        r2 = X.load(); 
    }
    
    

    因为 C++11 原子类型保证顺序一致性,结果 r1 = r2 = 0 是不可能的。为了实现这一点,编译器会在幕后输出额外的指令——通常是内存栅栏和/或 RMW 操作。与程序员直接处理内存排序的指令相比,这些附加指令可能会降低实现的效率。

    内存排序

    正如流程图所暗示的那样,任何时候您对多核(或任何对称多处理器)进行无锁编程,并且您的环境不保证顺序一致性,您必须考虑如何防止内存重新排序。

    在当今的体系结构中,强制执行正确内存排序的工具通常分为三类,它们可以防止编译器重新排序和处理器重新排序:

    • 轻量级同步或栅栏指令;

    • 一个完整的内存栅栏指令;

    • 提供获取或释放语义的内存操作。

    获取语义防止在程序顺序中跟随它的操作的内存重新排序,并且释放语义防止在它之前的操作的内存重新排序。这些语义特别适用于存在生产者/消费者关系的情况,即一个线程发布一些信息而另一个线程读取它。

    不同的处理器有不同的内存模型

    不同的 CPU 系列在内存重新排序方面有不同的习惯。这些规则由每个 CPU 供应商记录,并由硬件严格遵守。例如,PowerPC 和 ARM 处理器可以更改相对于指令本身的内存存储顺序,但通常情况下,Intel 和 AMD 的 x86/64 系列处理器不会。我们说前者的处理器具有更宽松的内存模型。

    人们很容易抽象出这些特定于平台的细节,尤其是 C++11 为我们提供了一种编写可移植无锁代码的标准方法。但是目前,我认为大多数无锁程序员至少对平台差异有一些了解。如果要记住一个关键区别,那就是在 x86/64 指令级别,每次从内存加载都带有获取语义,并且每次存储到内存都提供释放语义——至少对于非 SSE 指令和非写组合内存.  因此,过去常常编写能在x86/64 上运行成功但在其他处理器上失败的无锁代码。

    如果你对处理器需要内存排序的硬件细节感兴趣,我推荐附录的并行编程困难吗? 请记住在任何情况下,由于编译器指令重排序也会导致内存重新排序。

    在这篇文章中,我没有过多地谈论无锁编程的实际方面,例如:我们什么时候做?我们真正需要多少?我也没有提到验证无锁算法的重要性。尽管如此,我希望对于一些读者来说,这篇介绍已经提供了对无锁概念的基本熟悉,因此您可以继续深入阅读其他文章而不会感到太困惑。

    参考资料 & 扩展阅读

    • Anthony Williams’ blog and his book, C++ Concurrency in Action

    • Dmitriy V’jukov’s website and various forum discussions

    • Bartosz Milewski’s blog

    • Charles Bloom’s Low-Level Threading series on his blog

    • Doug Lea’s JSR-133 Cookbook

    • Howells and McKenney’s memory-barriers.txt document

    • Hans Boehm’s collection of links about the C++11 memory model

    • Herb Sutter’s Effective Concurrency series

    • http://preshing.com/20120612/an-introduction-to-lock-free-programming/

    - END -


    看完一键三连在看转发,点赞

    是对文章最大的赞赏,极客重生感谢你

    推荐阅读

    高级/专家工程师职位和面试题

    深入理解DPDK程序设计|Linux网络2.0

    深入理解RCU|核心原理

    展开全文
  • 无锁编程

    2018-07-11 16:27:55
    无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程无锁编程...
  • 无锁编程介绍

    2020-02-11 20:24:38
    文章目录无锁编程是什么无锁编程技术原子的 Read-Modify-Write 操作Compare-And-Swap 循环顺序一致性内存保序不同的处理器有不同的内存模型参考文献 无锁编程是一项挑战,不仅仅是因为自身的复杂性所致,还与初次...

    原文地址:http://preshing.com/20120612/an-introduction-to-lock-free-programming


    无锁编程是一项挑战,不仅仅是因为自身的复杂性所致,还与初次探索该课题的困难性相关。

    我很幸运,我第一次介绍无锁 (lock-free,也称为 lockless) 编程,是 Bruce Dawson 的出色而全面的白皮书《无锁编程注意事项》。和大多数人一样,我有机会将 Bruce 的建议用到无锁代码的编写和调试中,例如在 Xbox360 平台上的开发。

    从那时起,出现了很多好的素材,包括抽象的理论、实例的正确性的证明以及一些硬件的细节。我在脚注中会有一些引用。有时,不同来源的资料是不同的。例如,一些材料假设了顺序一致性,这就回避了困扰 C/C++ 无锁代码的内存排序问题。新的 C++11 的原子操作库标准提供了新的工具,这会挑战现有的无锁算法。

    在本文中,我会重新介绍无锁编程,首先对其进行定义,然后从众多信息提炼出少数重要的概念。我会使用流程图来展示各个概念间的关系,然后我们将涉足一些细节问题。任何学习无锁编程的程序员,都应该能理解如何在多线程代码中使用互斥量,理解一些高级同步机制,例如信号和事件等。

    无锁编程是什么

    人们常常将无锁编程描述成不使用 互斥量(Mutex,一种的机制)的程序。这个说法是对的,但并不全面。被广泛接受的基于学术报告的定义含有更广义的含义。从本质上来说,无锁编程是描述一些代码的一个属性,它并没有过多描述代码是如何写的。

    基本上,你的代码的一些部分符合如下条件,即可被认为是无锁的。反之,如果你的代码一些部分不符合下述条件,则被认为不是无锁的。

    在这里插入图片描述

    在该场景中,“无锁” 中的 “锁” 并不是直接指互斥量,而是指 “锁定” 整个应用的所有可能的方式,不论是死锁、活锁甚至可能是线程调度的方式都是你最大的敌人。最后一点听起来似乎很好笑,却是至关重要的一点。首先,共享互斥量被排除了,因为一旦一个线程获取了互斥量,你最大的敌人将永远无法再次调度那个线程。当然,真实的操作系统不是那样做的,只是我们是如此定义的。

    下面这个简单的例子没有使用互斥量,但仍然不是无锁的。X初始值为0。作为练习题,请考虑如何调度两个线程,才能使得两个都不退出循环?

    while (X == 0)
    {
        X = 1 - X;
    }
    

    没人期待整个大型的应用是完全无锁的。通常,我们可以从整个代码库中识别出一系列无锁操作。例如,在一个无锁队列中有少许的无锁操作,像push、pop,或许还有isEmpty等等。

    《多处理器编程艺术》的作者Herlihy和Shavit,趋向于将这些操作表达成类的方法,并提出了一个简单的无锁的定义(第150页):“在一个无限的执行过程中,会不停地有调用结束”。换句话说,程序能不断地调用这些无锁操作的同时,许多调用的也是不断地在完成。从算法上来说,在这些操作的执行过程中,系统锁定是不可能的。

    无锁编程的一个重要的特性就是,如果挂起一个单独的线程,不会阻碍其它线程执行。作为一组线程,他们使用特定的无锁操作来完成这个特性。这揭示了无锁编程在中断处理程序和实时系统方面的价值。因为在这些情况下,特定的操作必须在特定的时间内完成,不论程序的状态如何。

    最后的精确描述:设计用于阻塞的操作不会影响算法运行,这种代码才是无锁的。例如在无锁队列的操作中,当队列为空时,队列的弹出操作会有意地阻塞。但其它的代码路径仍然被认为是无锁的。

    无锁编程技术

    事实证明,当你试图满足无锁编程的无阻塞条件时,会出现一系列技术:原子操作、内存屏障、避免ABA问题,等等。从这里开始,事情很快变得棘手了。

    那么,这些技术间是如何相互关联的?我将它们放在下面的流程图中进行展示。下文将逐一阐述。
    在这里插入图片描述

    原子的 Read-Modify-Write 操作

    所谓原子操作是指,通过一种看起来不可分割的方式来操作内存:线程无法看到原子操作的中间过程。在现代的处理器上,有很多操作本身就是的原子的。例如,对简单类型的对齐的读和写通常就是原子的。

    Read-Modify-Write(RMW)操作更进一步,它允许你按照原子的方式,操作更复杂的事务。当一个无锁的算法必须支持多个写入者时,原子操作会尤其有用,因为多个线程试图在同一个地址上进行RMW时,它们会按“一次一个”的方式排队执行这些操作。我已经在我的博客中涉及了RMW操作了,如实现 轻量级互斥量递归互斥量轻量级日志系统

    在这里插入图片描述
    RMW 操作的例子包括:Win32上 的 _InterlockedIncrement,iOS 上的 OSAtomicAdd32 以及 C++11 中的 std::atomic<int>::fetch_add。需要注意的是,C++11 的原子标准不保证其在每个平台上的实现都是无锁的,因此最好要清楚你的平台和工具链的能力。你可以调用 std::atomic<>::is_lock_free 来确认一下。

    不同的 CPU 系列支持 RMW 的方式也是不同的。例如,PowerPC 和 ARM 提供 load-link/store-conditional 指令,这实际上是允许你实现你自定义的底层 RMW 操作。常用的 RMW 操作就已经足够了。

    如上面流程图所述,即使在单处理器系统上,原子的 RMW 操作也是无锁编程的必要部分。没有原子性的话,一个线程的事务会被中途打断,这可能会导致一个错误的状态。

    Compare-And-Swap 循环

    或许,最常讨论的 RMW 操作是 compare-and-swap (CAS)。在Win32上,CAS 是通过如 _InterlockedCompareExchange 等一系列指令来提供的。通常,程序员会在一个事务中使用 CAS 循环。这个模式通常包括:复制一个共享的变量至本地变量,做一些特定的工作(改动),再试图使用 CAS 发布这些改动。

    void LockFreeQueue::push(Node* newHead)
    {
        for (;;)
        {
            // Copy a shared variable (m_Head) to a local.
            Node* oldHead = m_Head;
    
            // Do some speculative work, not yet visible to other threads.
            newHead->next = oldHead;
    
            // Next, attempt to publish our changes to the shared variable.
            // If the shared variable hasn't changed, the CAS succeeds and we return.
            // Otherwise, repeat.
            if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead)
                return;
        }
    }
    

    这样的循环仍然有资格作为无锁的,因为如果一个线程检测失败,意味着有其它线程成功—尽管某些架构提供一个 较弱的CAS变种 。无论何时实现一个CAS循环,都必须十分小心地避免 ABA 问题

    顺序一致性

    顺序一致性(Sequential consistency)意味着,所有线程就内存操作的顺序达成一致。这个顺序是和操作在程序源代码中的顺序是一致的。在顺序一致性的要求下,像我 另一篇文章 演示的那样的有意的内存重排序不再可能了。

    一种实现顺序一致性的简单(但显然不切实际)的方法是禁用编译器优化,并强制所有线程在单个处理器上运行。 即使线程在任意时间被抢占和调度,处理器也永远不会看到自己的内存影响。

    某些编程语言甚至可以为在多处理器环境中运行的优化代码提供顺序一致性。 在C ++ 11中,可以将所有共享变量声明为具有默认内存排序约束的C ++ 11原子类型。 在Java中,您可以将所有共享变量标记为volatile。下面是 我之前一个案例 用C++11风格重写的例子。

    std::atomic X(0), Y(0);
    int r1, r2;
     
    void thread1()
    {
        X.store(1);
        r1 = Y.load();
    }
     
    void thread2()
    {
        Y.store(1);
        r2 = X.load();
    }
    

    因为 C ++ 11 原子类型保证顺序一致性,所以结果 r1 = r2 = 0 是不可能的。 为此,编译器会在后台输出其他指令——通常是 内存围栏 和/或 RMW 操作。 与程序员直接处理内存排序的指令相比,那些额外的指令可能会使实现效率降低。

    内存保序

    正如前面流程图所建议的那样,任何时候做多核(或者任何对称多处理器)的无锁编程,如果你的环境不能保证顺序一致性,你都必须考虑如何来防止 内存重新排序

    在当今的架构中,增强内存保序性的工具通常分为三类,它们既防止 编译器重新排序 又防止 处理器重新排序

    • 一个轻型的同步或屏障指令,以后的文章会详述;
    • 一个完全的内存屏障指令,如之前所述
    • 提供获取或释放语义的内存操作。

    获取语义可防止按照程序顺序对其进行操作的内存重新排序,而释放语义则可防止对其进行操作前的内存重新排序。 这些语义尤其适用于存在生产者/消费者关系的情况,其中一个线程发布一些信息,而另一个线程读取它。 在以后的文章中,我还将对此进行更多讨论。

    不同的处理器有不同的内存模型

    在内存重新排序方面,不同的CPU系列具有不同的习惯。 每个CPU供应商都记录了这些规则,并严格遵循了硬件。 例如,PowerPC 和 ARM 处理器可以相对于指令本身更改内存存储的顺序,但是通常,英特尔和 AMD 的 x86 / 64 系列处理器不会。 我们说以前的处理器具有更宽松的内存模型

    有人倾向于将这些特定于平台的细节抽象出来,尤其是C ++ 11为我们提供了编写可移植的无锁代码的标准方法。 但是目前,我认为大多数无锁程序员至少对平台差异有所了解。 如果需要记住一个关键的区别,那就是在x86 / 64指令级别上,每次从内存中加载都会获取语义,并且每次存储到内存都将提供释放语义–至少对于非SSE指令和非写组合内存 。 因此,过去通常会编写可在x86 / 64上运行但 在其他处理器上无法运行 的无锁代码。

    如果你对硬件如何处理内存重新排序的细节感兴趣,我建议看看《Is Pararllel Programming Hard》的附录C。无论如何,请记住,由于编译器对指令的重新排序,也会发生内存重新排序。

    在这篇文章中,我没有对无锁编程的实际方面说太多,例如:什么时候做? 我们真正需要多少? 我也没有提到验证无锁算法的重要性。 尽管如此,我希望对某些读者来说,本入门对无锁概念有基本的了解,因此您可以继续阅读其他内容而不会感到困惑。

    参考文献

    [1] 无锁编程注意事项
    [2] Locks Aren’t Slow; Lock Contention Is
    [3] 实现自己的轻量级互斥量
    [4] 实现一个递归互斥量
    [5] 一个轻量级内存日志系统

    展开全文
  • CAS无锁编程详解

    2021-12-02 19:37:32
    volatile原理 应用 经典的多线程取钱问题就可以用CAS无锁编程解决 interface Account { // 获取余额 Integer getBalance(); // 取款 void withdraw(Integer amount); /** * 方法内会启动 1000 个线程,每个线程做 -...

    概述

    在面对并发的场景,我们要对共享的资源进行保护,方式一般有两种,一种是使用Synchronized对资源进行加锁,另外一种方式就是本文要介绍的使用CAS来对共享资源进行保护。

    CAS全称是Compare And Swap,意思是比较与交换。通过比较之前的值是否发生改变,来决定是否对共享资源进行修改,如果这个值变了,那就说明有其它线程已经修改过这个值了,则修改失败,返回false,如果值没变,那顺利修改并且返回true

    CAS底层是调用了native本地函数库,调用的是c++编写的函数,通过操作系统底层实现CAS的原子性。

    Compare,必须需要读这个资源当前的值,才能进行比较,这也就是为什么CAS底层必须需要volatile来帮助。volatile原理

    应用

    经典的多线程取钱问题就可以用CAS无锁编程解决

    interface Account {
     // 获取余额
     Integer getBalance();
     // 取款
     void withdraw(Integer amount);
     /**
     * 方法内会启动 1000 个线程,每个线程做 -10 元 的操作
     * 如果初始余额为 10000 那么正确的结果应当是 0
     */
     static void demo(Account account) {
     List<Thread> ts = new ArrayList<>();
     long start = System.nanoTime();
     for (int i = 0; i < 1000; i++) {
     ts.add(new Thread(() -> {
     account.withdraw(10);
     }));
     }
     ts.forEach(Thread::start);
     ts.forEach(t -> {
     try {
     t.join();
     } catch (InterruptedException e) {
     e.printStackTrace();
     }
     });
     long end = System.nanoTime();
     System.out.println(account.getBalance() 
     + " cost: " + (end-start)/1000_000 + " ms");
     }
    }
    
    class AccountSafe implements Account {
     private AtomicInteger balance;
     public AccountSafe(Integer balance) {
     this.balance = new AtomicInteger(balance);
    }
     @Override
     public Integer getBalance() {
     return balance.get();
     }
     @Override
     public void withdraw(Integer amount) {
     while (true) {
     int prev = balance.get();
     int next = prev - amount;
     if (balance.compareAndSet(prev, next)) {
     break;
     }
     }
     // 可以简化为下面的方法
     // balance.addAndGet(-1 * amount);
     }
    }
    public static void main(String[] args) {
     Account.demo(new AccountSafe(10000));
    }
    
    

    为什么要使用CAS呢?

    相对于加锁,CAS不需要进行消耗繁重的上下文切换,这种上下文切换对于CPU来说消耗是比CAS轮询来的更大的。CAS对于多核CPU来说意义更大一些,多核CPU可以做到真正意义上的并行,一个CPU多执行几次轮询会比执行一次上下文切换所需要的资源少的多。

    CAS的特点

    结合 CAS 和 volatile 可以实现无锁并发,适用于线程数少、多核 CPU 的场景下。

    • CAS是基于乐观锁的思想,我很乐观,觉得这个资源不会被其它线程修改,我不加锁直接去修改,然后发现值不对,大不了我重新执行一下操作。
    • synchronized 是基于悲观锁的思想:最悲观的估计,得防着其它线程来修改共享变量,我上了锁你们都别想 改,我改完了解开锁,你们才有机会。

    ABA 问题及解决

    什么是ABA问题

    在使用CAS解决并发问题的时候,两个线程先后访问共享资源,两个线程读到的值都是A,然后线程1先执行修改,将A改成了B,之后又将B改成了A,然后到线程2进行CAS操作,这个时候按照CAS的原则,应该是要比较失败的。可是结果还是对的,线程2任然会修改这个值。导致CAS失效。

    如何解决这个问题

    加一个版本号,变量每修改一次,就将版本号自增一次,然后比较的时候再根据实时的版本来判断是否需要修改这个值。

    Java中可以使用AtomicStampedReference来对变量进行修饰

    使用方法:

    static AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);
    public static void main(String[] args) throws InterruptedException {
     log.debug("main start...");
     // 获取值 A
     String prev = ref.getReference();
     // 获取版本号
     int stamp = ref.getStamp();
     log.debug("版本 {}", stamp);
     // 如果中间有其它线程干扰,发生了 ABA 现象
     other();
     sleep(1);
     // 尝试改为 C
     log.debug("change A->C {}", ref.compareAndSet(prev, "C", stamp, stamp + 1));
    }
    private static void other() {
     new Thread(() -> {
     log.debug("change A->B {}", ref.compareAndSet(ref.getReference(), "B", 
     ref.getStamp(), ref.getStamp() + 1));
     log.debug("更新版本为 {}", ref.getStamp());
     }, "t1").start();
     sleep(0.5);
     new Thread(() -> {
     log.debug("change B->A {}", ref.compareAndSet(ref.getReference(), "A", 
     ref.getStamp(), ref.getStamp() + 1));
     log.debug("更新版本为 {}", ref.getStamp());
     }, "t2").start();
    }
    
    15:41:34.891 c.Test36 [main] - main start... 
    15:41:34.894 c.Test36 [main] - 版本 0 
    15:41:34.956 c.Test36 [t1] - change A->B true 
    15:41:34.956 c.Test36 [t1] - 更新版本为 1 
    15:41:35.457 c.Test36 [t2] - change B->A true 
    15:41:35.457 c.Test36 [t2] - 更新版本为 2 
    15:41:36.457 c.Test36 [main] - change A->C false 
    

    展开全文
  • C++多线程 - 无锁编程

    千次阅读 2022-04-09 13:18:25
    无锁编程: 就是不使用锁机制就可保证多线程间原子变量同步的编程。无锁(lock-free)的实现只是将多条指令合并成了一条指令形成一个逻辑完备的最小单元,通过兼容CPU指令执行逻辑形成的一种多线程编程模
  • 1.无锁编程与有锁编程的效率无锁编程,即通过CAS原子操作去控制线程的同步。如果你还不知道什么使CAS原子操作,建议先去查看相关资料,这一方面的资料网络上有很多。CAS实现的是硬件级的互斥,在线程低并发的情况下...
  • 曾经有个人,问我对无锁队列的实现是怎么想的。我想了一会儿,还是纳闷儿,无锁,也能做消息队列吗?然后他让我回去好好查查。没错,他就是面试官。 atomic 在有些场景里面,是需要对一些资源进行锁定的。但是有些...
  • Linux内核可能是当今最大最复杂的并行程序之一,为我们分析多核多线程提供了绝佳的范例。内核设计者已经将最新的无锁编程技术带进了2.6系统内核中,本文以2.6.10版本为蓝本,带领您领略多核多线程编程的真谛。
  • 无锁 编程

    2016-03-17 10:07:11
    多线程无锁编程技术
  • 无锁编程(CAS)

    2021-12-30 22:21:47
    参考高并发之无锁编程 多线程并发 在高并发场景下往往需要用到多线程编程,又由于多个线程共享同一个进程中的地址空间,所以又可能会出现同时访问/修改同一个共享变量的情况,这就涉及到线程安全的问题,比如 两个...
  • 无锁编程技术及实现

    2019-08-05 14:34:34
    1.基于锁的编程的缺点 多线程编程是多CPU系统在中应用最广泛的一种编程方式,在传统的多线程编程中,多线程之间一般用各种锁的机制来保证正确的对共享资源(shareresources)进行访问和操作。 在多线程编程中只要...
  • 主要介绍了Java语言中cas指令的无锁编程实现实例,具有一定参考价值,需要的朋友可以了解下。
  • 大佬总结无锁编程.pdf

    2021-01-28 14:15:13
    大佬总结无锁编程.pdf
  • lambda std::bind ...比较互斥锁,自旋锁(spinlock),无锁编程的异同,并进行性能测试;最后会讨论一下内存序的问题;为了流畅阅读你最好先熟悉一下C++11 Atomic的基本操作英文文档,这里还有一份我觉得做
  • 【算法】CAS的实现和无锁编程

    千次阅读 多人点赞 2021-03-31 21:49:06
    CAS(Compare and swap,比较与交换) 是一种有名的无锁算法。比较与交换,先比较,发现与预期一致,说明没有其他线程改动过,于是再交换。如果与预期不一致说明改动过,就再来一次。 与各类锁相比,CAS算法会使得...
  • C++多线程并发(五)---原子操作与无锁编程

    万次阅读 多人点赞 2019-05-12 13:21:23
    文章目录 一、何为原子操作 二、如何使用原子类型 2.1 原子库atomic支持的原子操作 2.2 原子操作中的内存访问模型 2.3 使用原子类型替代互斥锁编程 2.4 使用原子类型实现自旋锁 三、如何进行无锁编程 3.1 什么是无锁...
  • Linux无锁编程.pdf

    2021-09-30 17:52:34
    Linux无锁编程.pdf
  • 编程语言来实现,肯定是无法保证原子性的。而原语是由计算机CPU提供实现,可保证操作的原子性。 原子操作具有不可分割性,不存在并发问题。所以在某些情况下,原语可以用来替代锁,实现一些即安全又高效的并发...
  • 无锁编程CAS

    千次阅读 2019-10-01 14:30:19
    CAS(Compare And Swap,比较并交换),要说CAS是无锁编程,多多少少有些“标题党”的感觉。因为CAS根据其设计思想,可以划分为乐观锁。不同于synchronized关键字,synchronized实现的是悲观锁。我第一次听说乐观锁...
  • 无锁编程基础

    千次阅读 2019-01-29 17:16:46
    文章目录目录背景锁的分类死锁、活锁饥饿、饿死(starvation):优先级反转(Priority inversion)护航现象(Lock Convoys)自旋锁无锁为什么要无锁?(界定问题)如何无锁?(界定问题)CAS等原子操作无锁队列的链表...
  • }   两个线程累加同一个共享变量,线程不安全,输出的count小于等于2000,想要解决这个问题加锁就可以,但是如果要用无锁编程CAS来解决该怎么解决?   现在无论运行多少遍,结果都是2000,也就是在没有加锁的...
  • 透过 Linux 内核看无锁编程.pdf
  • CP.100:不要使用无锁编程方式,除非绝对必要 Reason(原因) It's error-prone and requires expert level knowledge of language features, machine architecture, and data structures. 这种方式容易出错,...
  • 无锁编程设计

    2022-02-08 13:07:40
    什么是无锁编程 LOCK-FREE,字面解释就是不通过锁来解决多线程、多进程之间的数据同步和访问的程序设计方案。 相对来说就是通过数据结构和算法来解决数据并发冲突的实现方案。 无锁编程的实现 比较并交换 Compare-...
  • 这一章内容主要讲解无锁编程相关技能,在生产中,为了解决线程间资源共享问题,最常用的方式就是加锁了,这在上一章并发编程也讲到过很多。关于无锁的时候,也写过一篇无锁队列的实现,而今天这篇文章主要是讲解无锁...
  • 无锁编程

    2017-02-19 22:57:00
    无锁编程,即不使用锁的情况下实现多线程之间的变量同步,也就是在没有线程被阻塞的情况下实现变量的同步,所以也叫非阻塞同步(Non-blocking Synchronization)。 实现非阻塞同步的方案称为“无锁编程算法”(Non-...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,680
精华内容 9,472
关键字:

无锁编程