多线程与高并发
2021-01-12 21:14:50 98 举报AI智能生成
多线程与高并发总结
作者其他创作
大纲/内容
容器
Collection
List
ArrayList
LinkedList
CopyOnWriteArrayList
线程安全，适用于读多写少的情况
Set
HashSet
TreeSet
Queue
BlockingQueue
ArrayBlockingQueue
有界，数组实现
入队出队单锁
LinkedBlockingQueue
可以有界，链表实现
入队出队两个锁
SynchronizedQueue
不存储元素，来一个必须取走才能再来
LinkedTransferQueue
相当于多窗口的SynchronizedQueue
DelayQueue
内部使用PriorityQueue实现
PriorityQueue
Map
HashMap
1.7与1.8
1.7
数组+链表
拉链法解决hash冲突
链表采用头插法，多线程扩容的情况可能会产生死循环
1.8
数组+链表+红黑树
链表采用尾插法
树化
当链表长度大于8，数组长度大于等于64时树化，否则只触发扩容操作
退化
resize时当链表长度小于6，退化为链表
remove时判断树比较小时退化为链表
8和6通过泊松分布得出
当size<=8时，链表整体的插入查询效率高于红黑树
优势：链表过长导致查询效率降低，可通过红黑树优化查询速度
红黑树优势
比普通的二叉树
树高更加均匀，不会出现单链情况
比AVL树
不需要完全平衡，不会牺牲太多的插入性能，插入和查找性能更加平均
线程不安全
多线程环境下可能会产生元素覆盖问题，1.8以前还可能在扩容时死循环
装载因子0.75
空间与时间的权衡
扰动函数
将hash的高16位右移进行异或运算，使得高16位和低16位都参与到定位运算中，减少hash冲突
容量为2^n原因
2^n可以使用位与运算代替取模，提高效率
加快扩容之后的元素移动
延迟初始化数组
当put第一个元素的时候才初始化
扩容
hash直接&oldCap，得出位置不变还是在原位置+oldCap
所以挨个运算后，直接生成两个链表，平移链表和扩容链表
TreeMap
ConcurrentHashMap
1.7
size
先不加锁计算三次，任意连续两次结果相同就返回，否则所有segment加锁计算
（个人感觉没有必要这么搞，即使算准确了，返回的那一刻可能已经发生改变了）
（个人感觉没有必要这么搞，即使算准确了，返回的那一刻可能已经发生改变了）
segment
锁定segment，segment即并发度
默认大小为16，一旦构建完成，后续不可更改
基本依赖lock和CAS保证线程安全
在lock前会尝试自旋一定次数调用trylock，并在自旋时做一些遍历操作
扩容
小细节
在生成两个链表的时候保留链表尾部将在同一链表部分，直接复用
扩容的对象是segment中的小map
即多个segment之间扩容互不干扰
其他同HashMap
1.8
size
已支持更多元素到long，推荐使用mappingCount替代size方法
计数系统详见LongAdder
基本依赖sychronized和CAS保证线程安全
synchronized的对象是链表头结点或者Treebin
扩容
扩容的时候还没有移动或者没有被锁定的Node可以正常使用
迁移单个Node的时候，对该Node加锁
迁移链表类似1.7
迁移树节点，对与其并存的双向链表进行操作，分组后判断是否小于等于6，是则退回链表，否则构建红黑树
协助扩容
如果hash得到的位置被标记为FWD或者多个线程同时进入扩容操作，则尝试协助扩容
扩容的时候会按照容量和CPU核数计算单个线程的步长，最小为16
每个线程通过CAS对sizeCtl进行加1，成功则进入协助扩容，退出时CAS对sizeCtl减1，如果sizeCtl变为原始值，说明所有Node都迁移完毕
ConcurrentSkipListMap
使用跳表实现
三要素
原子性
可见性
有序性
as if serial
单线程
happens before
多线程
8原则
单线程as if serial
volatile
monitor lock
thread start
thread terminate
thread interrupt
object finalizer
传递性
JMM
为了屏蔽各操作系统及硬件的区别，Java定义了JMM
8个原子操作
lock
unlock
read
load
use
assign
store
write
volatile
如何保证可见性和有序性
JVM层面
规定use之前必须load
即读之前必须先从主内存同步数据
规定assign之后必须store
即写之后必须马上同步回主内存
规定volatile的8个操作不能指令重排序
内存屏障实现
写
storestore屏障
volatile写
storeload屏障
读
storeload屏障
volatile读
loadstore屏障
CPU层面
指令lock addl
缓存一致性协议
总线锁
mesi协议
M(Modified)
E(Exclusive)
S(Shared)
I(Invalid)
DCL单例
对象初始化过程
new 分配一块内存
执行初始化
将内存赋值到引用
需要加volatile修饰，因为对象初始化过程中可能发生指令重排序，即初始化和赋值引用重排序，导致其他线程读到未初始化完成的对象
对象结构
从上到下依次为
MarkWord（32位4字节，64位8字节）
klass pointer（压缩指针4字节）
数据区
padding
需要补齐8字节对齐
压缩指针
32G内存失效
原因：压缩指针4字节32位，即4G，由于8字节对齐，所以压缩指针最大只能表示32G
并发工具类
CountDownLatch
countDown方法不阻塞，await方法阻塞
内部类继承自AQS框架，实现share相关方法
不可重复使用，一般用于某些线程等一堆线程操作
CyclicBarrier
循环栅栏，可循环使用，一般用于多个线程互相等待
也可实现CountDownLatch功能，在初始化的时候多加一个Runnable参数
使用lock和condition实现
Semaphore
信号量Java实现
内部类继承自AQS框架，实现share相关方法
与锁类似，只不过不记录获取的线程
Exchanger
需两个线程访问，如果只有一个线程，会阻塞等待另一个线程到来
内部实现：CAS+park
atomic包
简单类
AtomicInteger
AtomicLong
AtomicBoolean
内部转换为Integer，true为1
内部使用Unsafe类的CAS操作，底层指令lock cmpxchg
数组类
AtomicIntegerArray
AtomicLongArray
AtomicReferenceArray
引用类
AtomicReference
AtomicStampedReference
可用来解决CAS的ABA问题
内部使用Pair将Reference和stamp包装起来
字段类
AtomicIntegerFieldUpdater
AtomicLongFieldUpdater
AtomicReferenceFieldUpdater
adder
LongAdder
将并发操作拆分到多个cell，提高并发度
缓存行
单个cell为一个long的包装，使用了@sun.misc.Contended注解，保证该long变量占用单独的一个缓存行
由于高速缓存的操作单元为一个缓存行，而缓存行上其他元素的invalid会导致当前元素一同invalid，从而降低并发度，单独一个缓存行可避免此问题
细节
有一个普通变量base可计数，CAS失败后使用cell数组
通过线程生成随机数，定位cell数组位置
定位到的cell数组位置不为null，则可以尝试CAS增加当前cell
初始化cell数组、填充新的cell元素、扩容cell数组三个操作互斥，会使用CAS乐观锁竞争cellbusy
竞争失败或者CAS失败可以尝试其他方式，比如说重新生成随机数再次定位，或者CAS操作base变量
多次失败则触发cell数组扩容操作，进一步提高并发度
DoubleAdder
超高并发使用，分为多个cell分别进行累加，get的时候将cell的值加一起
锁
synchronized
1.6优化
无锁
MarkWord: 对象hashcode和分代年龄
偏向锁
MarkWord: 偏向线程ID，偏向时间，分代年龄
如果锁标记为可偏向状态，则尝试使用CAS替换对象头的markWord为当前线程id
当有另一个线程尝试获取这个锁时，则升级为轻量级锁
轻量级锁
MarkWord: 指向轻量锁记录的指针
超过N个线程竞争或者自旋超过一定次数，则膨胀为重量级锁
线程数量N和自旋次数由自适应自旋决定，即通过复杂的算法得出
重量级锁
MarkWord: 指向重量级锁的指针
涉及用户态到核心态的切换
流程
获取锁失败则添加到阻塞队列
锁释放后通知阻塞队列中的一个线程抢占锁
锁消除
编译器检测到不会涉及到多线程竞争，则会把锁消除
锁粗化
编译器检测到相邻代码多个小锁，则会粗化为一个大锁
可重入
不可中断
只有一个等待队列
wait、notify
必须在synchronized中使用
wait会释放锁，notify不释放锁
流程
调用wait后将线程放入等待队列，并释放当前锁
调用notify后，会把线程从等待队列移动到阻塞队列，可重新竞争锁
lock
ReentrantLock
可重入锁
在已经被锁定状态，判断是否是当前线程持有，如果是则将state加1
可以实现公平锁
非公平锁性能更好，但可能造成饥饿
可以实现可中断锁
可以有多个等待队列
ReentrantReadWriteLock
读写锁
读读之间共享锁，可以提高读的效率
通过state的前16位和后16位区分写锁还是读锁
写锁可降级为读锁，读锁不能升级为写锁
StampedLock
有同样读写锁的实现
添加优化读
如果读的时候没有写，则可以不加读锁，提高效率
在读之前使用validate验证是否有写入，如果有则需要继续获取读锁
Condition
await类似wait
signal类似notify
CAS
需要配合自旋，如果竞争激烈，比较耗费cpu
linux对应指令: lock cmpchx
AQS源码
volatile int state
充当了信号量，用CAS操作成功表示获取成功
CLH队列
当获取锁失败，需要将线程加入阻塞队列
双端队列
加入队列时，先判断head是否为null，如果为null，则先用CAS添加哨兵节点，如果不为null，则用CAS将当前节点置尾结点
出队时，将head指向当前节点，并清空线程等数据，作为新的哨兵节点
condition队列
调用await方法加入等待队列，并释放锁
调用signal方法将该节点移到阻塞队列中
线程池
ThreadPoolExecutor
参数
corePoolSize
maxPoolSize
keepAliveTime
timeUnit
blockingQueue
threadFactory
rejectedHandler
提交任务
execute
无返回值
submit
有返回值
ForkJoinPool
可窃取工作模式
在当前线程完成给定队列中的任务后，尝试从别的队列尾窃取任务
ThreadLocal
hash冲突
使用线性探测法处理
在线程里有ThreadLocalMap存储相应的值
key为ThreadLocal本身，为弱引用WeakReference
当强引用断开后，该threadLocal变量即可被回收
这样会造成Map中key为null，而value有值，属于内存泄漏
threadLocal在set和get的时候会顺带着检测是否有null的key，如果碰到了就清除掉
即使有清除策略，也只能清除一部分，所以需要在使用完后手动remove掉
value为强引用
初始化长度为16，当容量达到1/2时触发扩容，会将原所有元素重新填入
0 条评论
下一页
