Linux基础组件之无锁消息队列ypipe/yqueue详解

       CAS定义

       比较并交换（compare and swap,码详 CAS），在多线程编程中用于实现不被打断的码详数据交换，避免数据不一致问题。码详该操作通过比较内存值与指定数据，码详当数值相同则替换内存数据。码详麻花视频app下载页源码

       为什么需要无锁队列

       锁引起的码详问题：cache损坏/失效、同步机制上的码详争抢、动态内存分配。码详

       有锁导致线程切换引发cache损坏

       大量线程切换导致cache数据失效，码详处理器与主存之间数据传输效率下降，码详影响性能。码详

       在同步机制上的码详争抢队列

       阻塞队列导致任务暂停或睡眠，大量时间浪费在获取互斥锁，码详而非处理数据，码详引发严重争用。

       动态内存分配

       多线程中动态分配内存导致互斥，线程频繁分配内存影响应用性能。

       无锁队列的实现

       无锁队列由ypipe_t和yqueue_t类构成，适用于一读一写场景。通过chunk模式批量分配结点，减少动态内存分配的互斥问题。批量分配大小根据业务场景调整，通常设置较大较为安全。利用spare_chunk存储未释放的chunk，降低频繁分配释放。预写机制减少CAS调用。巧妙的唤醒机制，读端等待无数据时进入等待状态，js作业源码写端根据返回值判断队列是否为空以唤醒读端。

       无锁队列使用

       yqueue.write(count,false)用于写入元素并标记完成状态，yqueue.flush()使读端可见更新后数据。yqueue.read(&value)读取元素，返回true表示读到元素，返回false表示队列为空。

       ypipe_t使用

       write(val, false)更新写入位置，flush()刷新数据到管道，read()读取数据并更新可读位置。

       yqueue_t构造函数

       初始化队列，end_chunk总是指向最后分配的chunk，back_chunk仅在有元素插入时指向对应的chunk。

       front()和back()函数

       返回队列头和尾的可读写元素位置。

       push()和pop()函数

       push()更新写入位置，pop()更新读取位置并检测释放chunk，保持数据流。

       源码分析

       yqueue_t内部使用chunk批量分配，减少内存操作，spare_chunk存储释放的chunk以供再次使用。ypipe_t构建单写单读无锁队列，通过CAS操作控制读写位置，实现高效数据交换。

       ypipe_t / yqueue_t无锁队列利用chunk机制避免频繁内存动态分配，提升性能。通过局部性原理复用回收的chunk，减少资源消耗。flush()检测队列状态通知唤醒，优化数据交换过程。asp源码公司

面试必问的CAS，你懂了吗？

       CAS（Compare-and-Swap）是一种实现并发算法时常用的技术，Java并发包中的多个类采用了CAS技术。面试中经常涉及这一概念，本文旨在深入解析CAS的原理。

       在介绍CAS之前，我们通过一个例子来理解其应用。这个例子在运行过程中可能会陷入死循环，通过检查线程状态，发现IDEA监控线程的介入导致了问题。解决这一死循环的方法是使用DEBUG模式运行程序或调整代码逻辑。

       通过volatile关键字的使用，我们可以观察到，其只能确保可见性，而不能保证原子性。在并发场景下，对于自增操作等非原子操作，volatile并不能保证正确结果。因此，解决这类问题的关键是引入原子操作。

       引入synchronized关键字是一种常见的解决方法，通过加锁实现原子操作，确保每次操作的正确性。然而，频繁使用synchronized会导致性能下降，因此引入Java并发包中的原子操作类（如AtomicInteger）成为了更优选择。

       AtomicInteger的`getAndIncrement()`方法即是CAS操作的实例，它通过一系列原子操作确保每次自增操作的荒野plus源码正确性和性能。进一步分析，我们发现其底层实现调用了`compareAndSwapInt`方法，即CAS的核心实现。

       CAS（Compare-and-Swap）本质上是一个比较并替换操作，它需要三个操作数：内存地址、旧的预期值和目标值。执行过程中，当内存地址的值与预期值相等时，CAS尝试将内存地址的值修改为目标值。若失败，则获取最新值，重新尝试，直至修改成功。

       深入到源码层面，可以看到`AtomicInteger`类中的`getAndIncrement()`方法最终调用了`compareAndSwapInt`方法，而`compareAndSwapInt`在Unsafe类中被实现。通过调用`Atomic::cmpxchg`方法，我们能够看到具体的汇编指令实现。

       `Atomic::cmpxchg`方法的实现依赖于系统是否为多处理器环境，以优化性能。它通过`LOCK_IF_MP`宏决定是否添加`lock`前缀，这一优化措施在单处理器环境下通常没有必要，但在多核处理器中能够提升性能。

       CAS操作的缺点包括循环时间长导致的开销大、仅支持单一共享变量的原子操作，以及ABA问题。ABA问题是由于CAS操作的特性导致，即在读取值后，网吧超市 源码值在后续操作中可能被改回原始值，从而产生误判。为解决ABA问题，Java并发包提供了带有版本控制的原子引用类`AtomicStampedReference`。

       在使用CAS操作时，需要考虑其对并发正确性的影响，尤其是ABA问题。如果并发场景中存在可能的ABA问题，传统互斥同步可能比原子类更高效。

       综上所述，理解CAS的原理和其在并发编程中的应用对于深入学习Java并发技术至关重要。掌握CAS操作的原理、优缺点及其解决方法，将有助于更高效、正确地处理并发问题。

ListenableFuture源码解析

       ListenableFuture 是 spring 中对 JDK Future 接口的扩展，主要应用于解决在提交线程池的任务拿到 Future 后在 get 方法调用时会阻塞的问题。通过使用 ListenableFuture，可以向其注册回调函数（监听器），当任务完成时，触发回调。Promise 在 Netty 中也实现了类似的功能，用于处理类似 Future 的场景。

       实现 ListenableFuture 的关键在于 FutureTask 的源码解析。FutureTask 是实现 Future 接口的基础类，ListenableFutureTask 在其基础上做了扩展。其主要功能是在任务提交后，当调用 get 方法时能够阻塞当前业务线程，直到任务完成时唤醒。

       FutureTask 通过在内部实现一个轻量级的 Treiber stack 数据结构来管理等待任务完成的线程。这个数据结构由 WaitNode 节点组成，每个节点代表一个等待的线程。当业务线程调用 get 方法时，会将自己插入到 WaitNode 栈中，并且在插入的同时让当前线程进入等待状态。在任务执行完成后，会遍历 WaitNode 栈，唤醒等待的线程。

       为了确保并发安全，FutureTask 使用 CAS（Compare and Swap）操作来管理 WaitNode 栈。每个新插入的节点都会使用 CAS 操作与栈顶节点进行比较，并在满足条件时更新栈顶。这一过程保证了插入操作的原子性，防止了并发条件下的数据混乱。同时，插入操作与栈顶节点的更新操作相互交织，确保了数据的一致性和完整性。

       在 FutureTask 中，还利用了 LockSupport 类提供的 park 和 unpark 方法来实现线程的等待和唤醒。当线程插入到 WaitNode 栈中后，通过 park 方法将线程阻塞；任务执行完成后，通过 unpark 方法唤醒线程，完成等待与唤醒的流程。

       综上所述，ListenableFuture 通过扩展 FutureTask 的功能，实现了任务执行与线程等待的高效管理。通过注册监听器并利用 CAS 操作与 LockSupport 方法，实现了在任务完成时通知回调，解决了异步任务执行时的线程阻塞问题，提高了程序的并发处理能力。

java并发原子类AtomicBoolean解析

       本文针对Java并发包下的原子类AtomicBoolean进行深入解析。在多线程环境中，传统的布尔变量`boolean`并非线程安全，容易导致数据竞争问题。为解决这一问题，引入了AtomicBoolean类，该类提供了一种线程安全的布尔值封装。

       使用`AtomicBoolean`的主要原因在于其提供的原子操作保证了多线程环境下的线程安全。在`AtomicBoolean`内部实现中，主要依赖于`compareAndSet`方法和CAS（Compare and Swap）机制。通过CAS操作，`AtomicBoolean`能够在多线程环境下实现原子的更新操作，有效避免了数据竞争和并发问题。

       在`AtomicBoolean`的源码中，`compareAndSet`方法使用了`Unsafe`类的`compareAndSwapInt`方法进行底层操作。CAS机制的核心思想是：在不进行锁操作的情况下，检查指定内存位置的预期值是否与当前值相等，若相等，则更新该位置的值为预期值；若不相等，则操作失败，返回原值。

       为了理解这一机制，我们可以通过一个简单例子进行说明。假设我们希望在多线程环境下实现一个“先来后到”的规则，例如：一个人完成起床、上班和下班三件事后，另一个人才能开始。在单线程下，这一逻辑自然无问题，但在多线程环境下，`AtomicBoolean`可以确保这一顺序得到实现。

       在实际应用中，`AtomicBoolean`类提供了丰富的原子操作方法，包括但不限于`compareAndSet`、`getAndSet`、`compareAndExchange`等。这些方法允许开发人员在多线程环境下安全地执行原子操作，简化了多线程编程的复杂性。

       总结而言，`AtomicBoolean`是一个在Java并发编程中非常实用的工具类，它通过原子操作保证了多线程环境下的线程安全。对于开发者而言，掌握`AtomicBoolean`的使用方法和原理，可以有效避免数据竞争问题，提升程序的并发性能和稳定性。

C#中使用CAS实现无锁算法

       CAS（Compare-and-Swap）操作是一种多线程并发编程中常用的原子操作，用于实现多线程间的同步和互斥访问。它通过比较内存地址处的值与期望的旧值是否相等来实现这一目标。若相等，则将新值写入该内存地址；否则不做任何操作。CAS 操作的原子性由硬件层面的CPU指令保证，通常通过 Interlocked 类在 C# 中实现。

       在C#中，我们使用Interlocked类的CompareExchange方法来实现CAS操作。此方法接收三个参数：内存地址、期望的旧值和新值。如果内存地址处的值与期望的旧值相等，则将新值写入该内存地址并返回旧值；否则不执行任何操作。通过判断返回值与期望的旧值是否相等，我们可以得知CompareExchange操作是否成功。

       在使用CAS实现无锁算法时，我们通常需要在更新数据后执行进一步的操作。结合while(true)循环，我们可以在每次尝试更新数据后检查是否成功。如果失败，则继续尝试，直到成功为止。

       以下是一个简单的计数器示例，它使用CAS实现了一个线程安全的自增操作。在CLR底层源码中，我们也经常看到使用类似方法实现线程安全计数器的代码。同时，队列类也使用CAS实现线程安全的入队和出队操作，该操作更为复杂，需要不断检查是否有其他线程修改数据。

       在复杂的无锁算法中，每一步操作都必须考虑是否被其他线程修改。每一步操作非原子，因此我们不仅依赖CAS操作，还必须确保在执行每个操作前检查数据是否被修改。类比薛定谔的猫，我们不知道数据状态直到尝试修改时才确定。

       通过测试代码，我们可以观察到在一定数量的操作中，需要重试的次数。这个重试次数取决于队列中是否有数据可供操作，而在多线程环境下，每次操作的结果可能有所不同。

       CAS是一种乐观锁机制，假设数据未被其他线程修改，若未修改则直接修改，若已修改则重新获取数据并再次尝试修改。在实现复杂的数据结构时，我们不仅依赖CAS操作，还需注意数据是否被其他线程修改，以及处理可能的分支情况。

死磕 java集合之ConcurrentLinkedQueue源码分析

       ConcurrentLinkedQueue

       （1）不是阻塞队列

       （2）通过CAS+自旋保证并发安全

       （3）可用于多线程环境，但不能用在线程池中

       简介

       主要属性

       两个属性：头节点与尾节点

       主要内部类

       典型单链表结构

       主要构造方法

       构造简单，实现无界单链表队列

       入队

       add(e)与offer(e)方法

       无异常抛出，流程清晰

       出队

       remove()与poll()方法

       逻辑清晰，不阻塞线程

       总结

       非阻塞队列，不适用于线程池

       彩蛋

       与LinkedBlockingQueue对比

       线程安全与返回null特性相似

       效率与锁机制差异显著

       无法实现等待元素与用在线程池中的限制