并发面试题

线程池

线程池核心参数

corePoolSize：核心线程池个数，通常情况下最多添加corePoolSize个Worker，当任务过多时（阻塞队列满了），会继续添加Worker直到Worker数达到maximumPoolSize
workQueue：用于保存等待执行的任务的阻塞队列。比如基于数组的有界ArrayBlockQueue、基于链表的无界LinkedBlockingQueue、最多只有一个元素的同步队列SynchronousQueue及优先级队列PriorityBlockingQueue等。
maximumPoolSize：线程池最大线程数量（能添加的Worker的最大数量）
ThreadFactory：创建线程的工厂
RejectedExecutionHandler：拒绝策略，当队列满并且线程个数达到maximumPoolSize后采取的策略。
- AbortPolicy：默认的策略，直接抛出RejectedExecutionException
- DiscardPolicy：不处理，直接丢弃
- DiscardOldestPolicy：将等待队列队首的任务丢弃，并执行当前任务
- CallerRunsPolicy：由调用线程处理该任务
keepAliveTime: 存活时间。如果当前线程池中的线程数量比核心线程数量多，并且是闲置状态，则为这些闲置的线程能存活的最大时间。非核心线程空闲后，保持存活的时间，此参数只对非核心线程有效。设置为0，表示多余的空闲线程会被立即终止。
TimeUnit：存活时间的时间单位。

线程池具体线程的分配方式

核心线程数—〉等待队列—〉最大线程数—〉拒绝策略处理

当一个任务被添加到线程池：提交任务

核心线程池是否满：未满则创建线程处理任务，满则执行2
等待队列是否满：未满任务加入等待队列，满则执行3
线程池是否满（最大线程数）：未满则创建线程处理任务，满则拒绝策略处理线程

如何合理分配线程池大小?

n+1 2n+1 n核

CPU密集型任务最佳的线程数为 CPU 核心数的 1~2 倍
IO密集型任务线程数 = CPU 核心数 *（1+平均等待时间/平均工作时间）

分配CPU和IO密集：

CPU密集型时，任务可以少配置线程数，大概和机器的cpu核数相当，这样可以使得每个线程都在执行任务
IO密集型时，大部分线程都阻塞，故需要多配置线程数，2*cpu核数

精确来说的话的话：

从以下几个角度分析任务的特性：
- 任务的性质：CPU密集型任务、IO密集型任务、混合型任务。
- 任务的优先级：高、中、低。
- 任务的执行时间：长、中、短。
- 任务的依赖性：是否依赖其他系统资源，如数据库连接等。

可以得出一个结论：

线程等待时间比CPU执行时间比例越高，需要越多线程。
线程CPU执行时间比等待时间比例越高，需要越少线程。

利特尔法则设置
定义: 一个系统请求数等于请求的到达率与平均每个单独请求花费的时间之乘积
举例: 假设服务器单核的，对应业务需要保证请求量(QPSQ): 10，真正处理一个请求需要 1秒，那么服务器每个时刻都有 10 个请求在处理，即需要 10 个线程
公式:
线程池大小= ((线程 IO time +线程 CPU time ) /线程 CPU time )*CPU数目举例: 假设服务器4核，平均 IO 时间为400ms，cpu处理时间为100ms，线程应设置为20

synchronized锁升级（底层）

Java中的synchronized有偏向锁、轻量级锁、重量级锁三种形式。会按偏向锁->轻量级锁->重量级锁的顺序升级，并且升级之后基本不会降级。

偏向锁：只被一个线程持有。对于轻量级锁每次加锁解锁通常都有一个CAS操作；对于重量级锁而言，加锁也会有一个或多个CAS操作，所以为提高一个对象在一段很长的时间内都只被一个线程用做锁对象场景下的性能，引入了偏向锁，在第一次获得锁时，会有一个CAS操作，之后该线程再获取锁，只会执行几个简单的比较和设置，而不是开销相对较大的CAS命令。
轻量锁：不同线程交替持有锁（即有不是特别多个线程，但同步代码块执行时间短，或者一次持有锁的时间短）
重量锁：多线程竞争锁

ReentrantLock和synchronized区别

synchronized执行完同步块会自动释放锁，ReentrantLock需要手动释放。
synchronized是非公平锁，ReentrantLock可以设置为公平锁
ReentrantLock等待获取锁的现场可中断的，synchonized会一直等。
ReentrantLock 可以设置超时获取锁，指定截止时间，截止时间未获取到锁则返回。
ReentrantLock提供了tryLock()提供非阻塞的获取锁。

AQS锁原理

AQS组成

AQS是一个FIFO的双向队列

通过 head 和 tail 两个节点来对队列进行维护。队列元素类型是Node

Node是AQS的一个静态内部类

SHARED：获取共享资源被阻塞挂起放入AQS队列的线程Node。

EXCLUSIVE：获取独占资源时被阻塞挂起放入AQS队列的线程Node。

thread：存放进入AQS队列里的线程

waitStatus用于记录当前线程的状态

CANCELLED：线程被取消，

SIGNAL：线程需要唤醒，

CONDITION：线程在条件队列里面等待，

PROPAGATE：释放共享资源时需要通知其他节点。

pre：当前节点的前驱节点

next：当前节点的后继节点

state：单一状态信息。可以通过getState、setState、compareAndSetState函数修改此值。线程同步的关键是对state操作。根据state是否属于一个线程操作state的方式可以分为独占和共享。
- ReentrantLock：独占锁，state用来标识当前线程获取锁的可重入次数
- ReentrantReadWriteLock：读写锁，state的高16位表示读状态（获取该读锁的次数），低16位表示获取到写锁的线程的可重入次数
- Semaphore：信号量，state用来表示当前可用信号个数
- CountDownLatch：state用来表示计数器当前的值
ConditionObject（内部类）：条件变量结合锁实现线程同步。ConditionObject直接访问AQS对象内部的变量，比如state值和AQS队列。ConditionObject是条件变量，每个条件变量对应一个条件队列（单向链表队列），用来存放调用条件变量的await方法后被阻塞的线程，这个条件变量头尾节点分别为firstWaiter和lastWaiter。

并发工具类

CountDownLatch：允许一个或多个线程等待其他线程完成操作。一个线程或多个等待另外n个线程完成之后才能执行。
CyclicBarrier (回环栅栏) ：让一组线程到达一个屏障（也可以叫同步点）时被阻塞，直到最后一个线程到达屏障时，屏障才会开门，所有被屏障拦截的线程才会继续运行。作用就是让所有线程都等待完成后才会继续下一步行动。
初始化参数：等待线程数、达到数量后线程唤醒前执行的函数
- parities：屏障拦截的线程数量，计算调用了CyclicBarrier.await()进入等待的线程数。当线程数达到了这个数目时，所有进入等待状态的线程被唤醒并继续。计数器可复用。
- Runnable参数：在达到parities数量后，所有其他线程被唤醒前被执行。
Semaphore (信号量) 用来控制同时访问资源的线程数量。应用场景：流量控制，特别是公共资源有限的应用场景，比如数据链接，限流等。

ConcurrentHashMap为什么线程安全

ConcurrentHashMap 并发度高，整个 ConcurrentHashMap 对应多把锁，只要线程访问的是不同锁，那么不会冲突

ConcurrentHashMap 1.7

数据结构：Segment(大数组) + HashEntry(小数组) + 链表，每个 Segment 对应一把锁，如果多个线程访问不同的 Segment，则不会冲突
并发度：Segment 数组大小即并发度，决定了同一时刻最多能有多少个线程并发访问。Segment 数组不能扩容，意味着并发度在 ConcurrentHashMap 创建时就固定了
索引计算
- 假设大数组长度是，key 在大数组内的索引是 key 的二次 hash 值的高 m 位
- 假设小数组长度是，key 在小数组内的索引是 key 的二次 hash 值的低 n 位
扩容：每个小数组的扩容相对独立，小数组在超过扩容因子时会触发扩容，每次扩容翻倍
Segment[0] 原型：首次创建其它小数组时，会以此原型为依据，数组长度，扩容因子都会以原型为准

ConcurrentHashMap 1.8

数据结构：Node数组 + 链表或红黑树，数组的每个头节点作为锁，如果多个线程访问的头节点不同，则不会冲突。首次生成头节点时如果发生竞争，利用 cas 而非 syncronized，进一步提升性能
并发度：Node 数组有多大，并发度就有多大，与 1.7 不同，Node 数组可以扩容
扩容条件：Node 数组满 3/4 时就会扩容
扩容单位：以链表为单位从后向前迁移链表，迁移完成的将旧数组头节点替换为 ForwardingNode
扩容时并发 get
- 根据是否为 ForwardingNode 来决定是在新数组查找还是在旧数组查找，不会阻塞
- 如果链表长度超过 1，则需要对节点进行复制（创建新节点），怕的是节点迁移后 next 指针改变
- 如果链表最后几个元素扩容后索引不变，则节点无需复制
扩容时并发 put
- 如果 put 的线程与扩容线程操作的链表是同一个，put 线程会阻塞
- 如果 put 的线程操作的链表还未迁移完成，即头节点不是 ForwardingNode，则可以并发执行
- 如果 put 的线程操作的链表已经迁移完成，即头结点是 ForwardingNode，则可以协助扩容
与 1.7 相比是懒惰初始化
capacity 代表预估的元素个数，capacity / factory 来计算出初始数组大小，需要贴近
loadFactor 只在计算初始数组大小时被使用，之后扩容固定为 3/4
超过树化阈值时的扩容问题，如果容量已经是 64，直接树化，否则在原来容量基础上做 3 轮扩容

扩展：HashMap的实现原理？

HashMap的数据结构：底层使用hash表数据结构，即数组和链表或红黑树

当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
存储时，如果出现hash值相同的key，此时有两种情况。

如果key相同，则覆盖原始值；
如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中

获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

扩展：HashMap的jdk1.7和jdk1.8有什么区别

JDK1.7采用的是拉链法。拉链法：数组+链表。也就是说创建一个数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时并且数组长度达到64时，将链表转化为红黑树，以减少搜索时间。扩容 resize( ) 时，红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表。

扩展：HashMap的扩容机制

在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）
每次扩容的时候，都是扩容之前容量的2倍；
扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
没有hash冲突的节点，则直接使用 e.hash & (newCap - 1) 计算新数组的索引位置
如果是红黑树，走红黑树的添加
如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么

扩展：HashMap在1.7扩容情况下的多线程死循环问题

在jdk1.7的HashMap中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

比如说，现在有两个线程都要进行扩容

线程一：读取到当前的HashMap数据，数据中一个链表，在准备扩容时，线程二介入
线程二：也读取HashMap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束。
线程一：继续执行的时候就会出现死循环的问题。先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，所以B->A->B,形成循环。