coderZoe的博客 - 并发编程
type: channel
link: https://coderzoe.com/tag/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/
items: JUC源码详细分析之Part3——《常见的线程安全集合》
items: JUC源码详细分析之Part2——《锁》
items: JUC源码详细分析之Part1——《CAS和原子类型》

JUC源码详细分析之Part3——《常见的线程安全集合》
type: item
date: 2023-07-20T12:48:00+00:00
description: JUC源码详细分析之Part3——《常见的线程安全集合》本系列笔记笔者将会详细的讲解JUC中核心类的源码，其中基于的JDK版本为1.8.0_291。由于JUC内容很多，因此笔者将笔记拆为四部分：JUC源码详细分析之Part1——《CAS和原子类型》JUC源码详细分析之Part2——《锁》JUC源码详细分析之Part3——《常见的线程安全集合》JUC源码详细分析之Part4——《线程池》另外，本系列笔记部分内容参考自《深入浅出 Java Concurrency》4. 常见的线程安全集合本章主要讲JUC下部分线程安全的数据结构，我们在日常开发中会经常使用他们，但是关于他们的实现原理与源码很多同学可能没了解过，现在就带大家了解JUC下常用数据结构的源码。4.1 ConcurrentHashMap我们之前利用读写锁实现了一个线程安全的HashMap，但是这个Map的性能并不高，因为首先他只支持同一时间一个线程的写入，另外读取的时候也需要加锁读取，在写的时候不允许读取，我们希望一个效率更高的map来替换之前读写锁版本的map，至少他需要改进两个功能：可以支持一定量的并发修改读取的时候不需要加锁在理解ConcurrentHashMap前，我们默认读者对HashMap的实现是有一定了解的，有HashMap源码的经验，包括JDK1.7和JDK1.8版本不同的实现方式。同样，ConcurrentHashMap的实现在JDK1.7和JDK1.8版本中也有所不同，我们先来说JDK1.7版本中ConcurrentHashMap的实现。4.1.1 JDK1.7 ConcurrentHashMap在JDK1.7中，ConcurrentHashMap的实现采用了锁分段的思想（JDK1.8也是，不过锁的颗粒度不同）。首先我们知道JDK1.7中HashMap是一个数组加链表的结构，假设我们将数组进行拆分，拆成n份，那么其实每一份是一个更小的数组，或者说每一份是一个更小的HashMap。我们将每一份小的HashMap称为段(Segment)。那么如果我们在操作的时候，先定位到使用哪个段，然后再在段内进行线程安全的增删改查。也即，每个段都是彼此并行的，段与段没有交集，这样最多可支持并发为n的写入/删除操作（n为段的数量）。如：当前Map数组长度2n，将Map分为n个段，那么每个段的数组长度就是2，每个段都可以认为是个小的HashMap，段与段之间并行，段内的元素操作都是线程安全的。JDK1.7中ConcurrentHashMap的实现，其结构如下：首先ConcurrentHashMap内包含一个segments，即段数组，它包含16个段，每个段都是一个类HashMap结构，这个结构（Segment）持有一个独占锁，保证在对段进行修改操作时是线程安全的。另外哈希桶的实现（HashEntry）的实现是链表的方式，即相同hash值的节点通过链表串起来（与JDK1.7相同）。在这里我们引入了段，为了提高map修改时的并发能力，但同样也带来了一个问题：当我们要操作一个元素时，如何定位这个元素在哪个段上，即原来我们只需要定位哈希桶，然后遍历链表节点，现在需要变为段->哈希桶->节点。JDK1.7中的实现依然是通过hash，即先通过hash定位到段，再通过二次hash定位到哈希桶(hashEntry)，然后再通过遍历链表得到具体的节点。了解了上面这些实现，我们可以从另一个角度看一下ConcurrentHashMap。首先ConcurrentHashMap内部有一个HashMap，这个HashMap的key是段号，value值是Segment。同时Segment也是一个HashMap，因此我们可以认为ConcurrentHashMap是一个value为HashMap的HashMap，这样也就不难理解进行元素操作时需要二次hash了。我们先来看下JDK1.7中ConcurrentHashMap是如何通过key获得段的：首先会将key值的hashCode(每一个Java Object都有hashCode)通过hash()进行二次编码（哈希算法打散均匀），然后将得到打散后的hash值通过segmentFor()函数，就可以定位到key对应的segments数组对应的数组下角标，返回数组下角标出处的Segment即可。熟悉HashMap的同学不难发现这与HashMap获得哈希桶的方式一模一样。//hash算法，打散key的hashcode private static int hash(int h) { // Spread bits to regularize both segment and index locations, // using variant of single-wor…

JUC源码详细分析之Part2——《锁》
type: item
date: 2023-07-20T12:45:00+00:00
description: JUC源码详细分析之Part2——《锁》本系列笔记笔者将会详细的讲解JUC中核心类的源码，其中基于的JDK版本为1.8.0_291。由于JUC内容很多，因此笔者将笔记拆为四部分：JUC源码详细分析之Part1——《CAS和原子类型》JUC源码详细分析之Part2——《锁》JUC源码详细分析之Part3——《常见的线程安全集合》JUC源码详细分析之Part4——《线程池》另外，本系列笔记部分内容参考自《深入浅出 Java Concurrency》3. 锁锁是JUC中最核心的内容，在本章我们将讲解JUC下常见的锁，以及介绍下著名的AQS框架。在讲解源码前，我们先来介绍一些基本的但常见的概念。锁是什么？解决了什么问题？在多线程下，我们希望有些代码是线程安全的执行的，我们将这样的代码行叫临界区。锁保证了临界区的代码可以像单条指令一样原子的执行，当某个线程持有锁的时候，就可以执行临界区的代码，其他线程此时是不可以的，只有这个持有锁的线程释放锁才能继续由下一个线程执行。悲观锁，乐观锁悲观锁：每次都以悲观的态度假设最坏的情况，每次拿数据的时候都认为别人会修改，所以每次在操作前会先上锁，操作后再将锁释放，Java中的synchronized和ReentrantLock都是悲观锁。乐观锁：每次都是乐观的态度假设当前是最好的情况，每次拿数据的时候都认为别人不会修改，所以不会上锁，但是在修改的时候会判断别人有没有修改这个数据（通过CAS和版本号实现），Java中的AtomicInteger就是乐观锁的一种实现，依赖了CAS。我们一般也认为悲观锁是阻塞锁，而乐观锁是非阻塞锁。非阻塞指的是不阻塞其他线程，即自己可以失败可以阻塞挂起，但不能因为自己的失败和挂起影响其他线程导致其他线程失败挂起。很多乐观锁的实现都依赖于CAS，但CAS本质是没有锁的，虽然叫乐观锁但它并没有锁。CAS只是通过比较和替换的方式，只有比较之后符合要求才进行替换，其中比较和替换是个原子操作，这其中并没有上锁以及并不会干扰任何其他线程，通常CAS都是自旋的，不断的尝试比较和替换，所以这里可以看到CAS是非阻塞锁，他的执行并不会干扰其他线程。由于CAS没有加锁，所以需要通过CAS同步修改的变量都应该使用volatile修饰符，这样保证变量的修改可以被其他线程看到。通常而言乐观锁应用于写少读多的情况，悲观锁应用于写多读少的情况。可重入锁，不可重入锁所谓可重入锁就是如果一个线程持有了锁，那么它可以重复执行需要这种锁的临界区代码，可以进行重复加锁。反之为不可重入锁。如：public void test(){ lock.lock(); try { while (x > 10){ x--; test(); } }finally { lock.unlock(); } }独占锁，共享锁所谓独占锁和共享锁是对资源而言的，如果某个资源只能同时被一个线程访问，那么就需要使用独占锁。而如果可以被所有线程一起访问，那么就可以使用共享锁。其中独占锁又叫互斥锁。大多数情况下我们在说锁的时候都是默认独占锁。公平锁，非公平锁如果获取一个锁是按照请求的顺序得到的，那么就是公平锁，否则就是非公平锁。这里有一篇很棒的文章，可以方便大家对Java中的锁有个大体了解：不可不说的Java“锁”事 - 美团技术团队 (meituan.com)3.1 Lock与AQSJava下的Lock接口定义如下：public interface Lock { //获取锁，如果锁不可用，出于线程调度目的，将禁用当前线程，并且在获得锁之前，该线程将一直处于休眠状态。 void lock(); void lockInterruptibly() throws InterruptedException; boolean tryLock(); boolean tryLock(long time, TimeUnit unit) throws InterruptedException; //释放锁 void unlock(); Condition newCondition(); }JUC下大部分锁的实现均是继承自该接口，其中Lock比较重要的两个函数是lock和unlock，我们在讲具体实现类的时候也主要讲这两个接口的实现。在讲JUC下锁的实现类前，我们先想下如果让你设计一个锁，实现lock()方法，你需要做什么？首先要判断是否允许当前线程获取锁，对于是否允许获取锁，得有一个状态位，这个状态位的修改必须是线程安全的。其次如果允许获取锁，就获取，否则就阻塞等待或者直接获取失败。若线程需要阻塞等待，那么就需要一个阻塞等待的队列。最后阻塞的时候，线程往往需要挂起不消耗资源。当状态位由不允许获取变更到允许获取时，得唤醒队列里的线程，并且线程得从阻塞队列中移除出去。综上…

JUC源码详细分析之Part1——《CAS和原子类型》
type: item
date: 2023-07-20T12:39:00+00:00
description: JUC源码详细分析之Part1——《CAS和原子类型》在笔者看来，后端的技术点主要是两个，一个是并发一个是IO。其中并发涉及很多知识点：线程安全、锁、线程池等等，而这些知识点都在Java的JUC包下。本系列笔记笔者将会详细的讲解JUC中核心类的源码，其中基于的JDK版本为1.8.0_291。由于JUC内容很多，因此笔者将笔记拆为四部分：JUC源码详细分析之Part1——《CAS和原子类型》JUC源码详细分析之Part2——《锁》JUC源码详细分析之Part3——《常见的线程安全集合》JUC源码详细分析之Part4——《线程池》另外，本系列笔记部分内容参考自《深入浅出 Java Concurrency》1. CAS1.1 原子操作假设疫情期间，你们老板要做一款微信扫描场所码的功能，其中有个功能需要你统计一下一天共扫了多少次码。作为资深程序员的你很快就写好了代码：public class ScanCode { private int count = 0; //注：打印语句打印出的并非是当前线程加过后的count值，这两句也并非原子操作，这里加打印语句只是方便展示问题 public void scanCode(){ count++; System.out.println("当前扫码："+count); } }这段代码在单线程下没有任何问题，但是如果多线程一起请求就会有想不到的错误，我们假设当前有1000个用户一起来扫码：public static void main(String[] args) { ScanCode scanCode = new ScanCode(); Thread[] threads = new Thread[1000]; for(int i = 0; i < 1000; i++){ threads[i] = new Thread(() -> scanCode.scanCode()); } for(Thread thread:threads){ thread.start(); } }打印结果中最大的一条==“当前扫码”==的记录往往是小于1000的，且每次运行得到的结果也不相同。这是为什么呢？首先我们需要知道现代计算机为了弥补CPU与存储介质的速度差异，往往采用多级缓存的架构。一般CPU在做计算的时候会将内存中的数据加载到寄存器，在寄存器中对数据操作计算后，再写回到内存。如果在这之间发生中断，进行了线程上下文切换，会有可能发生意想不到的情况。我们模拟两个线程A,B的执行来解释这一情况：时间OS线程A线程BT1 从内存中取count，此时count=50，将50写入寄存器 T2 在寄存器中做++操作，此时寄存器中的值是51 T3发生中断，保存线程A状态，恢复线程B执行 T4 从内存中取count，此时count=50，将50写入寄存器T5 在寄存器中做++操作，此时寄存器中的值是51T6 将51写回内存，此时内存中count=51T7发生中断，保存线程B状态，恢复线程A执行 T8 将寄存器中的值写回内存，此时count=51 可以看到，我们扫了两次码，但count只加了1。根本原因在于count++这一操作不是原子操作。那么什么是原子操作？《Java并发编程实战》一书中给出了定义，但描述的依然生涩难懂。笔者在此简单解释下：所谓原子操作就是不可再切分的操作，不能在运行期间插入别的任务的，一个要么一口气执行完要么不执行的操作。以上面的线程AB例子来看：在执行count++的过程中，需要做如下几件事：从内存中将数据加载到寄存器在寄存器中做操作将值写回内存上述任意一步之间均可被中断，此时就不是一个原子操作。1.2 CAS我们需要一个超级指令，当这个指令执行时，它会像期望那样执行更新。它不能在指令中间中断，如果发生中断，指令根本没有运行，或者运行完成，没有中间状态。而这一超级指令是由现代CPU实现的（注意是硬件CPU，而非软件层）。现代CPU提供了一个叫CAS的功能，CAS全称compare and swap，即比较并交换，其用伪代码大概如下：int compareAndSwap(int * ptr, int expected, int new){ int actual = *ptr; if(actual == expected){ *ptr = new; } return actual; }基本思路是检测 ptr 指向的值是否和 expected 相等；如果是，更新 ptr 所指的值为新值。否则，什么也不做。不同的是这一过程会原子的执行。CAS有一个高频的面试问题——ABA问题：比如说一个线程one从内存位置V中取出A，这时候另一个线程two也从内存中取出A，并且two进行了一些操作变成了B，然后two又将V位置的数据变成…