笑傲java面试
2022-01-01 09:53:58 0 举报AI智能生成
学习笔记
作者其他创作
大纲/内容
总决篇-Java攻略
导学：给你一份进大厂的学习计划
写一份让HR无法拒绝的简历
建立投递网络——如何扩大选择面？
白板篇-Java编程
Java的Collection和Map：如何实现Key-Value的LRU缓存？
面试题
请用Iterable实现一个随机序列产生器?
Collection和Set的区别？
Map是不是Collection?
TreeMap和HashMap的区别？
HashMap vs Hashtable
实现Key-Value的LRU缓存
容器(Collection)
容纳数据的容器
一组(group)对象
增删改
遍历(traverse)
Iterable<T>
coding
Collection接口
源代码阅读
集合(Set<E>)
内容不重复的容器
实现
ConcurrentSkipListSet
跳表
CopyOnWriteArraySet
数组
EnumSet
位运算
HashSet
ImmutableCollections.SetN
LinkedHashSet
TreeSet
树
源码阅读
顺序问题
coding（对比HashSet和TreeSet)
可浏览的(Navigable)
coding
Null Object
TreeSet不允许（因为元素必须是Comparable)
HashSet允许
性能测试
coding
映射(Map)
两个集合间的对应关系
key->value
实现
HashMap
TreeMap
Hashtable
SortedMap
Map是不是Entry的容器
Entry<K,V>是一个key-value集合
阅读Entry源代码思考结论
Map<K,V>接口
阅读Map的源代码
Map的实现
ConcurrentHashMap，HashMap、Hashtable、LinkedHashMap是基于哈希表的实现
TreeMap是基于树的实现
ConcurrentSkipListMap是基于跳表的实现
EnumMap是基于位运算的实现
HashMap vs HashTable
对比源码（synchronized）
HashMap允许null
HashTable(Dictionary不允许null key/value)
LinkedHashMap
实现LRUCache<T>
C -> B -> A
新增D: D->C->B
新增C: C->D->B
总结
Map的本质？
HashMap是什么？
TreeSet是什么？
知识是简单的，但是理解到本质是困难的？思考：为什么简单的知识却很难理解到本质？
Tree/HashTable/位运算/跳表
Java8 Stream<T>接口： 流和并发计算实例
面试题
什么是流？
::运算符的作用？
Java 8的Stream价值是什么？
创建Stream有几种方法？
coding:利用parallel并发执行任务？
Java8 Stream
为一组序列提供顺序、并行运算
流：随着时间产生的数据序列
特点
1. 支持函数式编程
2. 提供管道运算能力
3. 提供并行(parallel)计算能力
4. 提供大量的操作
提供流计算
pipeline的过程
操作
状态
有状态(stateful)
sorted
skip
limit
任何触发状态变化的程序
无状态(stateless)
map
reduce
副作用
纯函数(pure function)
非纯函数
coding
map/reduce/filter
flatMap
forEach/collect
提供并行计算
分支主题
Spliterator类
coding
函数式基本概念
类型
Int -> String
toString
(Int) -> int[]
int[]::new
高阶函数: Int -> Int -> Int
Integer::max
类型类
类似Java的toString （interface）
性质
immutable/pure
lazy
safty
monad架构
总结
和面试官聊聊实现管道和流计算的基石：函数式的Monad
面试题
Optional<T>的作用？
FunctionalInterface在做什么？
说说你理解的函数式编程？
1. 解释下什么是Monad？
2. 如何实现管道和流？
函数式
OOP
现实世界的投影
Functional Programming
用函数写程序
核心：计算
没有副作用
并行
数学证明
安全
复用
……
引入：流计算的类型设计
分支主题
观察类型的变化？
为什么中间的运算不用Optional类型？
为什么两端的数据用Optional类型？
对空值的处理
Monad
Monad是一个自函子范畴上的一个幺半群
Monad设计模式
目标：构造流计算(管道运算)
特点
一个泛型的构造函数。比如： Optional<T>
不改变泛型类型的运算操作，内部是非泛型计算：例如：Optional<R> map(T -> R)
泛型类型不变。 比如可以是Optional<Integer>到Optional<String>，但还是Optional<T>类型。
泛型类型不变是构造流计算的基石
映射
过滤
聚合
……
实战举例 & Event\<T\>的实现
数据库的搜索结果
定义Review: Monad是一个自函子范畴上的一个幺半群
自函子（EndFunctor)
(A -> B) -> (M<A> -> M<B>)
A->B的函数
apply操作
函子的实现
T是Integer ： 代表事件类型的编号
T是EventData : 代表事件的详细描述
整体程序
幺半群(Monoid)
思考：Transform::transform是什么？
可插拔的程序
复用性强
map是自函子
群——一类事物
一类符合某种条件的对象
Optional
Stream
Event
自函子上的群
群中的对象和自函子一起使用达到XXX效果
封闭性
M x M -> M
结合律
Optional(100) | op1 | op2 | op3 …… | Optional<?>
a*b*c = a*(b*c)
单位元
empty * any = empty
a * e = e * a =a
总结
Buffer的原理和使用场景+面试题解读
引入
流 vs 缓冲区
流：随着时间到来的数据
缓冲区：顾名思义-缓冲作用
按键太快
磁盘写入操作太多
网络请求太多
现实模型：理发店
缓冲的本质是排队、流的本质是数据
面试题
1. 缓冲区是不是流？
2. 缓冲区的几种操作含义：flip/rewind/clear?
3. 缓冲区设置多大？
4. NIO的Channel比缓冲区快吗？
5. 缓冲过程中，中文乱码如何处理？
6. 并发分析数据更快吗?
7. 计算一个大文件的词频(coding)？
缓冲区的概念
FIFO（水管）
价值何在？
用户按键太快->beep（缓冲区满）
思考：如何缓冲区大小=2？如果=1024？
增加缓冲区成本低、效果好
核心逻辑：用户不会一直乱按键（并发峰值不会持续太久）
知识迁移思考
系统的对接
服务对接
举例：聊天服务
没有缓冲：拒绝服务、性能低下
有缓冲：排队处理、批量处理
排队处理请求避免拒绝服务
批量写入磁盘快过多次写入
批量执行Sql快过多次执行
I/O的成本
理解数据拷贝的成本
用户空间缓冲区->处理线程
网卡->内核空间(可DMA）
内核空间->用户空间缓冲区
概念解读
内核空间：操作系统内核使用的内存区域
用户空间：用户程序使用的内存区域
为什么不直接将设备的数据拷贝到用户空间呢？
进程的隔离
内核是连接设备和进程的桥梁：用户程序直接沟通设备非常危险
I/O的成本
设备准备、程序初始化……
3次拷贝
缓冲区的实现原理
单向缓冲区
Position、Limit、Capacity
翻转(flip）操作
Limit才是实际限制，Capacity是物理限制
clear操作
rewind操作
实战演示
总结
补充资料：同步、异步、阻塞、非阻塞概念解读
Coding训练：中文处理和词频计算
中文处理
UTF8编码的字符串（100个）
缓存大小=10
导致中文乱码
词频计算
1G个单词统计
多少个线程？
如何并行运算
课前两道面试题：结合业务逻辑实现AOP和注解
实战场景Coding训练：解读反射+代理+AOP 并结合业务逻辑实现
面试题
什么是反射？有什么用处？
写一个关于XXX反射的程序？
解释下为什么要面向切面编程？
为什么Proxy.newProxyInstance要传入ClassLoader?
写一个程序实现AOP？
反射的概念
反射(reflection)：运行时查看、反观程序内部结构，甚至修改
运行时数据（通常称为元数据 MetaData)
模块、类、函数、注解、源代码……
反观自身
通过字符串找到一个类，并调用某个方法
查看类的方法、属性
查看注解
……
运行时修改
运行时修改的是的Bytecode
byte[]
工具：Javasist
见ClassLoader部分
面向切面编程（Aspect Oriented Programming)
关注点分离原则（Seperation of Concern )
把程序分成多个部分，每个部分负责独立的功能
举例：订单业务场景
核心逻辑：订单相关
下单
支付
辅助能力（Annotation 或 Aspect)
日志
用户通知
触发奖励：如抽奖
……
举例：Java的设计
容器
Collection
Map
……
并发
AQS
BlockingQueue
……
……
Anti-Pattern
耦合
没有领域建设：per业务实现逻辑
如何理解切面(Aspect)
程序有一个主关注点+多个其他关注点（Aspect)
可以配置主关注点和其它关注点如何一起工作
When: 何时触发
before
after
around
……
触发什么？
方面对象
代理
思考：如何实现AOP?
方案1： （违反关注点分离原则）手动在核心方法中增加before、after的内容（例如打日志）
方案2
给Aspect建模（每个方面独立模块）
固定一些Join Point，甚至允许自定义
用程序衔接：结合核心业务对象+Aspect对象
调用一个核心方法的包装方法（代理模式）
函数式：高阶函数
f : 核心方法
g : 方面包装方法
x : 核心方法输入
最后调用的方法： h = fg(x)
核心方法动态增加bytecode：Javassist库
API解读:代理
Proxy类
Proxy.newProxyInstance(classloader, interfaces, invocationHandler)
思考：为什么需要InvocationHandler?
思考：为什么需要传入Interface?
思考：为什么需要ClassLoader?
代码示例
coding
总结
元编程面试专项
面试题
什么是元编程？
有什么用处？
概念
元（meta） - 数据
程序的元数据还是程序（程序本身就是数据）
元编程：一个程序可以把另一个程序作为数据
反射
eval
eval("var a = 3+5+7;")
Java：ScriptEngine
执行Javascript程序
Java9 : jdk.jshell
可动态生成程序并执行（bash）
宏（编译时生成程序）
字符串查找和替换
有中间语言的语言（Java Bytecode, C# IL……）
可以动态修改中间语言
用处
代码生成（减少样板代码 - 相似逻辑反复写）
实现编程框架（AspectJ， SpringAOP)
研发DSL(例如Java执行LUA、JS程序作为业务脚本）
思考：为什么一个语言使用另一个语言做脚本？
Java不是脚本语言：类型很复杂
方便存储和执行
程序语言是目前描述业务逻辑最强大的工具，没有替代品（图灵完备性）
总结
Java 8以上版本新特性总结
白板篇-数据结构和算法
教你面试时不会忘记的5种手写排序
面试题
写一个插入排序？
写一个冒泡排序？
写一个快速排序？
写一个合并排序？
给定0~99之间的数字，怎样排序最快？
只有0,1,2的数组，怎样排序最快？
进步的方式
加1/减1法
分治策略
哈希函数
加1法、减1法
插入排序(Insertion sort)
最直观的排序
进步：无序到有序的过程(抓牌然后整理的过程）
加1
有序的集合+1
减1
无序的集合-1
程序框架
思考：i代表什么？
循环不变式（loop invariant）
每次循环之后，保持、且引起进步的条件
插入排序外层循环不变式：每次循环之后i指向下一个需要排序的元素；脚标小于i的元素已经排序好了。
内层循环：抓牌的实现
coding
冒泡排序和选择排序
编程模型
分支主题
选择排序
选最大的元素放到A[i]；然后i--
思考：稳定性？
序列2 2 1 1 用选择排序2 2相对顺序是否会发生变化？
类比：按时间排序的商品卡片
稳定排序：同值顺序在排序过程中不会调换
课后题：测试排序的稳定性，用例如何写？
如何实现稳定性——冒泡
冒泡排序（Bubble Sort)
选最大元素的算法：不断交换相邻元素
coding
思考：稳定性？
2 2 1 1
完美解决
稳定的排序
分治策略
英文：Divide And Conquer
举例：打扫房间
第一级：房间
第二级：大家具
第三级：物品
排序的分治策略
数组A
1/2
1/4
1
……
1/4
1/2
1/4
1/4
每一个节点都是将问题拆分、处理、合并
如此递归……
伪代码
合并排序（Merge Sort)
代码框架
l-r ： 区间脚标，左闭右开
mid：中间脚标
合并过程
i:B中下一个需要选择的值
j:C中下一个需要选择的值
MAX:哨兵（减少边界条件判断）
coding
快速排序(Quick Sort)
随机取一个x
期望上x平分原问题
正确性的思考方式
规模1：正确
规模2：正确
规模3：正确
归纳（看现象找规律）
人类的思考方式
日出月落……潮涨潮灭……
coding（框架）
coding（函数式+Immutable）
coding（mutable实现）
时间复杂度讨论
分治策略
拆分子问题的时间
分别处理每个子问题的时间
合并子问题的时间
递归的时间复杂度，需要递归思考
规模N递归节点时间
d：拆分时间(忽略不计）
c*N: 合并的时间（主要因素）
2*T(N/2): 子问题处理时间
快速排序的讨论
拆分的期望是 :平分
O(NlogN)
思考：最坏情况是多少？什么情况出现？
哈希函数
思考：排序100万个0~99之间的数字，什么样的排序方法最优？
桶排序(Bucket Sort)
100个桶
桶0存0
桶1存1
……
桶99存99
桶索引：X % 100
coding
思考：推广到一般的桶排序coding
桶排序的时间复杂度分析
QuickSort - O(N)
QuickSort1
思考：如果只有1个桶？
O(NlogN)
k个等大的子问题
从桶中取出结果部分的时间复杂度：k*O(N/klog(N/k))
k是常数
O(NlogN)
N/k=c
N/c*O(clogc) = O(N)
思考：复杂度为何可以忽略常数？
总结
1：循环不变式，循环变量
2：递归和归纳
世界如此
3：哈希函数
映射
4 稳定性
思考：如何让本课程的快速排序拥有稳定性？桶排序有没有稳定性？
手写链表相关算法
面试题
Coding：链表的表示？
Coding：增删改查？相关复杂度？
Coding：合并两个链表的操作？
Coding：反转链表？
实现队列、栈（见队列、栈部分）
Coding：判断链表中是否有环？
和CAS Loop结合（见并发部分）
链表和表示
链表是一种跳跃结构
连续结构
数组（内存上连续）
跳跃结构(指针)
分支主题
链表
树
图
链表是一种抽象数据结构(Abstract Data Structure)
抽象
interface
实现有很多种
数据结构：聚合数据和操作的容器
单向链表
节点(Node)
next指针
数据
链表（List）
head指针
双向链表
节点（Node）
next指针
prev指针
数据
链表（LinkedList)
head指针
tail指针
增删改查
单向链表插入
头插法
查询的复杂度？
删除
思考：关于内存的回收
反转链表问题
核心问题
3个指针
递归（状态空间）
另一种理解：递归的语义
判断链表中是否有环的问题？
难点：不用HashTable
fast能不能追上slow?
fast追上slow前一个位置(下一次会追上slow)
fast追上slow
总结
思考：两个链表合并时间复杂度是？两个数组是？
链表查询是O(n)，链表插入是O(1)，双向链表删除元素是O(1)
思考：获取链表的第k个元素的时间复杂度是？
链表的作用
跳跃结构可以无限分配空间(unbounded)
数据的容器
实现stack/queue：并发编程中大量链表实现的队列
组织存储（双向链表）：分配/回收内存
实现哈希表
……
手写栈、队列相关算法
面试题
栈和队列的基本概念：什么是栈、队列？
栈和队列的实现和基本操作接口？
栈实现队列？队列实现栈？
括号匹配问题？
表达式解析问题？
栈（Stack）
比喻：摆放整齐的一打书
举例：函数嵌套（书）——摆放整齐摞起来的函数
先调用的函数被后调用的函数压在上面
子函数调用过程完成，上级函数才能返回
FIFO序（先入后出，First In Last Out)
接口
push(ele)
O(1)
pop()
O(1)
实现：基于LinkedList、数组
队列（Queue）
比喻：排队（First In First Out ,FIFO）
举例：排队执行的线程
接口
enqueue(ele)
O(1)
dequeue
实现：基于LinkedList、数组
面试题：两个栈实现队列？
负负得正
FILO | FILO -> FIFO
实现复杂度分析：push、pop都是O(1)
思考题：请问可以不可以用两个队列实现栈？
面试题：括号匹配问题？
判断一个含有{}的表达式中括号是否匹配
{}{} ： ture
{123{a+b}} : true
}{ : false
将{压栈，遇到}出栈检查栈中的元素是不是{
课后习题：解析4则运算的表达式
中序表达式转后序表达式
1+2*3+ 4
1 2 3 * 4 + +
转化方法
需要一个队列 （queue）和一个栈（stack）
从左到右处理每个输入，遇到数字就加入队列，遇到符号就加入栈
操作符优先级保证：符号入栈的时候，低优先级符号会导致之前的高优先级符号出栈，并加入队列
最后栈中剩余的符号都加入队列
利用栈计算 1 2 3 * 4 + +
分支主题
手写树相关算法
面试题
树的表示？
反转二叉树？
计算树的深度？
广度优先算法和深度优先算法
树遍历的序？如何判断二叉树是不是二叉搜索树？
关于对平衡二叉树的认知？
树的表示
根节点(root node)
叶子节点(leaf node)
边（edge)
路径
高度和深度
翻转二叉树
水平将二叉树反转过来
遍历的「序」
是「递归」的序
先序
举例： 5 3 2 4 7
后续
2 4 3 7 5
中序
2 3 4 5 7
广度优先和深度优先
深度优先（以上3中，Depth first)
广度优先算法 （Breadth first)
像火焰蔓延一样，一层一层遍历
12
8 23
7 11 15 28
需要队列Queue，保证一层和下一层节点之间的关系
二叉搜索树
二叉搜索树：左子树比当前节点小，右子树比当前节点大
搜索元素的时间复杂度与二分查找相同O(logn)
打印二叉搜索树
计算树的深度
二叉搜索树中序是顺序
Leetcode题目：判断一个树是不是二叉搜素树？
树的平衡
旋转操作（向右）
让树重新平衡
代表：红黑树，AVL Tree
哈希表：HashMap实现原理和ConcurrentHashMap
面试题
HashTable的原理？
说一个Hash函数?
Java的HashMap是如何实现的？
除了哈希表还有哪些适合存Key/Value的数据结构？
ConcurrentHashMap是怎么回事？什么时候用？
Java Object的hashCode是如何计算的？
哈希表
一种存储映射（Key -> Value）的数据结构
举例：字典
思考：用数组存储映射
根据Key查询Value的时间复杂度是？
思考：有没有更好的存储结构？Key可以是数字、字符串、类型等等
树怎么样？
二叉搜索树？
HashTable的结构
一种实现：基于桶和链表的实现
hashcode：哈希函数计算的结果和映射到桶的索引（数组的脚标）
Hash碰撞：两个Key的hashcode一样
解决碰撞的逻辑：放入相同的链表
查询步骤
计算hashcode
找到桶
遍历链表
第二种实现：基于数组（开放寻址）
解决碰撞的逻辑：向后1个位置放
查询步骤
计算hashcode
从hashcode所在位置找到对应的Key（多次探测）
优势：简单，速度快，较高的空间利用率
问题
扩容问题（随着输入量增加需要不断扩容）
负载因子：达到多少比例需要扩容，比如0.75
指数扩容 16，32，64， ……
哈希函数
h : key -> hashcode
hashcode不能超过桶的数量
例如：（0, 100000) -> (0, 99)
h( something ) -> integer(0 ~ 99)
12345 % 100 = 45
h = %
字符串的hash: h(str) = (str[0] * a + str[1] * b + str[2] * c + .. str[n-1] * x) % P
Java的String hashcode函数
s[0]*31^(n - 1) + s[1]*31^(n - 2) + ... + s[n - 1]
"abcdefghijklmn".hashCode()
结果：2093908199
Java的hashCode用在哈希表的时候还需要: %桶的容量
思考：什么样的hashcode好？
不同的Key hashcode碰撞概率低的
分布均匀：Key能够平均打散到桶中
计算中使用了素数
只能被1和自己整除的数字
自己可以组成别的数字，别的数字不能组成自己
用素数生成数字可以减少这个数字出现的概率
例如：容量=100的哈希表存储500个<key,value> ，平均每个桶（链表）中存5个性能最优！
Java对象Object的hashCode
如果没有重写hashCode，那么由native代码生成
如果：A=B，那么hashCode(A) = hashCode(B)
如何hashCode(A) = hashCode(B) , A不一定等于B
思考：用什么算法分配hashCode?
思考：自增ID?
思考：内存地址？
思考：randomNumber?
时间复杂度分析
计算hashcode的时间复杂度 ~ O(1)
插入/查询的时间复杂度
思考：冲突越多越慢
链表实现的哈希表
平均冲突=哈希表中<k,v>个数/容量
接近常数：O(1)
开放寻址
平均冲突=哈希表中<k,v>个数/容量
接近常数：O(1)
优化版的HashMap
基于红黑树+链表
ConcurrentHashMap
Java 1.7
每个Segment类似一个HashTable
两次Hash
解决什么问题？
Hash表的所有操作安全吗？
初始化、插入、删除（不安全）
读取（结合volatile关键字）可以做到安全
hash函数计算（安全）
减少并行线程竞争的问题
Java1.8 LockFree数据结构-类似HashMap结构（CAS控制操作）
手写搜索和八皇后问题
思考：在迷宫中搜索出口？
不断进行选择然后进入新的位置
所有的位置称为状态空间，找到终点，就是状态空间中进行搜索
八皇后问题
方案1
依次寻找位置放8个皇后
64*63*62*61*60*59*58*57种做法
方案2
每列放一个皇后，并且利用数学关系减少计算量
不能同行
不能斜对角
动态规划专题
Dynamic Programming怎么翻译？
Dynamic形容Programming很棒！
Programming翻译成规划！
规划类问题：帮人找到最优解！
时间规划
路程规划
动态规划例子1：找最优路径
分支主题
并发基础篇
解读：并发编程知识体系
知识体系结构
并发编程的知识图谱（https://voice-static.oss-accelerate.aliyuncs.com/9eac0bf1ca21c9004a65ead293191b8a.png）
内容清单
1. 进程和多线程
2. JVM底层：CAS和原子操作
3. 同步器（上）：synchronized关键字和Monitor
4. 同步器（中）：AbstractQueuedSynchronizer
5. 同步器（下）：ReentrantLock/CyclicBarrier/Phaser/CountDownLatch等
6. 内存一致性模型——volatile和happens-before关系
7. Java的7种同步队列
8. 饥饿（死锁、活锁）和Lock-Free数据结构
9. Java的6种LockFree数据结构
10. 任务(Task)、执行(Executors)和结果(Future)
11. 线程安全和ThreadLocal
12. 并发编程的8个核心应用场景解读
场景举例
并发处理任务
支持并发的索引
高并发作业
高并发锁
高并发I/O
连接池技术
消息队列
并发计算
进程和线程
关联面试题
进程和线程的区别？
为什么要有线程？
为什么要减少线程切换？
进程开销为什么比线程大？
JAVA线程有哪些状态？如何转换？
Java线程是内核级线程还是用户级线程？
什么是进程？
进程（Process）是程序的执行副本
一开始操作系统没有进程
和微信、QQ、Word等是类似
Java在一台服务器上执行多个服务，其实就是启动了多个Java的进程
什么是线程？
线程(Thread)还被称为是轻量级的进程。
Linux的LWP
并发（concurrent）
在一段时间内多个任务看上去同时进行
交错执行（interleaved）
并行（parallel)
指任务被同时执行
同时执行（simultaneously)
线程是一种并发的模型
进程和线程的模型
进程是一个线程的容器
资源分配问题
线程：计算资源（CPU)
进程：内存
进程：文件
思考：为什么会有线程？
早期操作系统设计
资源都给进程
后来：进程内部不同任务需要分时
主线程
进程创建时跟随创建的线程
思考：创建线程需要什么？
需要提供一段程序
入口指令内存地址
线程对内存权限
共享进程的内存
受限于程序语言（Java）
内核级线程和用户级线程
内核：应用程序和硬件沟通的桥梁
用户空间
内核空间
内核级线程和用户级线程
内核级线程由内核调度，用户级线程有应用自己调度。
思考：Java如果采用用户级线程
思考：Java如果采用内核级线程
总结：Java采用用户-内核级线程映射（总体来说是内核级线程）
线程的状态
基本3态
1. 运行态(Running)
执行
2. 就绪态(Ready)
排队
3. 休眠态(Sleeping)。我们通常说的阻塞态（Blocking）是休眠态的一种情况。
举例：读取磁盘
面试题&思考
就绪态能不能到阻塞态？
阻塞态能不能到执行态？
Java线程的6个状态
特有状态：NEW/TERMINATED
RUNAABLE对应排队和执行
WAITING/TIME_WAITING/BLOCKED对应休眠
面试题&思考
Thread.join是哪种状态?
Thread.sleep是哪种状态?
网络请求是哪种状态？
线程的切换
线程是执行单位
线程不拥有资源，线程计算
ThreadLocal如何理解？
Context Switch
保存当前线程的状态（CPU寄存器的值）
重新执行调度程序（操作系统），重新选择其他线程执行
过程图示
CAS和原子操作
面试题
1. 竞争条件是怎么产生的？解决竞争条件有哪些方法？
2. 原子操作是如何实现的？
3. Java的CAS是如何实现的？
4. CAS的ABA问题是怎么回事?
5. AtomicInterger类是如何实现的？
6. AtomicStampedReference解决什么问题？内部如何实现？
原子操作
操作不可分
举例：CPU指令
i++是3个原子操作组合而成的
1. 读取i的值
2. 计算i+1
3. 写入新的值
竞争条件
竞争条件(race condition)，也叫做竞争灾难(race hazard)
举例
结果取决于执行时的精准时序
临界区（critical section)：发生竞争的区域（访问共享资源）
临界区（critical section)
两个线程发生竞争的区域（访问共享资源i )
场景：两个自动提款机扣款
解决竞争的办法
减少竞争
ThreadLocal
举例
Thread -- HashMap<String, Integer>
内存屏障(Barrier)
空间换时间
实现原子操作
CAS(Compare And Swap 或者 Compare And Set）
CPU指令支持
作用：设置一个地址的值
约束：要求指令的使用方必须知道这个地方原来的值
问题示例：扣款问题
小明的支付宝余额是10000元，某个时刻小明并发的买了两个东西
1. 线程1： 读取余额(10000)
2. 线程2： 读取余额(10000)
3. 线程1： 设置余额=9000（扣1000款）
4. 线程2： 设置余额=8000（扣2000款）
结论
非cas操作：竞争条件
cas操作呢？
CAS解决
因为线程2不知道内存的值是9000因此拒绝第二笔交易
分支主题
CPU指令提供的原子操作
执行过程不会中断
举例
读取i
计算i+1
cas操作：比较i和i'的值是否相等，如果是，更新目标值
i++问题
线程1 ： 读取i
线程2 ： 读取i
线程1 ： 计算i+1，得到1
线程2 ： 计算i+1, 得到1
线程1 ： cas(&i, 0, 1)，成功，i=1
线程2 ： cas(&i, 0, 1), 失败，返回false
结论：cas解决了部分问题，拒绝了竞争条件
解决进步(make a progress)
TAS指令
Test-And-Set
可以看做一个CAS的特例
CAS实现TAS
互斥
Mutual Exclusion
让最多只有一个线程可以进入临界区
俗称为锁(lock)
可以用 tas 或者 cas来实现
互斥的程序示例
伪代码
Java的CAS
底层类Unsafe
jdk.internal.misc.Unsafe
文章推荐：http://mishadoff.github.io/blog/java-magic-part-4-sun-dot-misc-dot-unsafe/。
CMPXCHG指令
x86/64
ARM机器
ABA问题
朋友钱包的钱，我偷偷拿走了100，晚上再趁朋友没注意放100到里面，算不算偷窃？
幂等改库存接口问题
正常CAS并发：100->99
更复杂的情况ABA出现
Thread 1： 读取库存， 100
Thread 1: 计算接下来的库存 99
Thread 2： 读取库存， 100
Thread 2: 计算接下来的库存 99
本来要失败了！
Thread 1： cas,更新库存 -> 99
Thread 3: 读取库存 -> 99
Thread 3： 计算库存 -> 100(增加库存)
Thread 3: cas更新库存 -> 100
Thread 2: cas更新库存 -> 99
ABA（成功）计算错了
举例子：栈的更新问题
一个链表实现的栈：push头插法新增，pop头部删除。
假设现在链表中是：head->A->B->C。
线程1执行操作 `pop()` ，期望链表之后变成 `head->B->C`
线程2执行两次pop操作，再push(A)，期望链表之后变成 `head->A->C` 。
问题示例：被删除的节点又回来了
Atomic操作
AtomicInteger(带看源码）
类似
- AtomicBoolean
- AtomicInteger
- AtomicLong
- AtomicReference
Java解决ABA(带看源码）
- AtomicMarkableReference
- AtomicStampedReference
同步器（上篇）：设计者角度学synchronized和Monitor
面试题
1. 什么是同步？
2. 简述下Java有哪些同步器？
3. synchronized是如何实现的？
4. ReentrantLock和synchronized的区别？
5. 为什么需要AbstractQueuedSynchronizer?
6. 偏向锁、轻量级锁、重量级锁是怎么回事？
什么是同步？
执行同步
多个参与方（多线程、进程）
汇合(Join)
例如：互相等待
执行后续操作
数据同步
多份数据保持数据一致
缓存和存储的同步
不同机房订单数据的同步
Java同步器概要
Java同步器整体架构
1. 开发工具层：提供开箱即用的同步工具(Synchronizer)
2. 开发框架层：提供开发同步工具的框架AQS（注意AQS不仅仅用于开发同步工具，还用于我们之后会讲的Non-Blocking，也称为Lock-Free的工具），所以它是一个开发神器。
3. JVM层
4. Java Native Interface（JNI）层（用于调用本地操作系统API）
5. 操作系统层
思考：为什么在synchronized外还要设计其他同步器？
Non-Blocking算法（tryLock)
见Lock-Free部分：后续章节
获取锁的timeout
灵活使用
跨语句块
性能优化
早期Java没有轻量级锁设计
AQS简介
Java提供的同步器开发框架
将用户和真正意义的底层隔离
用户实现同步控制算法时不再需要使用JVM提供的最底层的API
例如：LockSupport.park、CAS、Unsafe等等
示例
思考：synchronized关键字的设计
用法
分支主题
一种不完全的实现方案
分支主题
思考：对休眠的3中理解
1. 休眠少量CPU周期（自旋锁）
2. 定时休眠（类似Thread.sleep）。
3. 信号休眠、信号唤醒（类似wait/notify）
改进：初版方案
分支主题
优势：先尝试自旋锁（提升竞争少时的性能）
睡眠/唤醒一个线程的能力怎么实现？
操作系统API修改线程状态
READY->SLEEPING
JVM知道哪些线程在休眠
WaitSet(马上学习）
再看synchronized关键字需要的能力
1. 需要实现锁/解锁的逻辑
2. 需要自旋锁到休眠的升级逻辑
3. API设计：每个对象都可以上锁
synchronized(任何东西){...}
4. 线程可以在竞争不到资源时休眠
5. 释放资源时唤醒休眠线程
需要知道有哪些线程休眠
Monitor:synchronized的实现方案
第3版方案：Monitor
每个对象都关联一个Monitor
线程抢占锁，就是抢占Monitor
解决：每个对象都可以上锁的问题（不用再定义锁变量了）
Monitor内部实现等待集合，没有竞争到资源的线程自旋失败后，在等待集合中休眠
解决：释放资源时唤醒休眠线程
能力汇总：JVM的monitor指令
monitorenter
获得锁->进入临界区
失败：自旋->休眠->WaitSet
//临界区
monitorleave
唤醒
Monitor的更多设计因素
线程间协作
读/计算/写的模型
1. Polling
while循环不断检查有没有新的读入
2. Queuing
实现生产者消费者
队列满
生产者休眠
队列空——消费者休眠
消费者开工——唤醒生产者
生产者开工——唤醒消费者
需要Java提供的wait和notify
Monitor提供、Object代理
Coding示例（手把手教学）
锁的升级（偏向锁、轻量级锁和重量级锁）
举例：高并发场景自旋锁（spin-lock）带来的灾难。 如果每个线程自旋15次没有获得锁就休眠，那么10ms足够所有线程自旋15次。
1. 自旋锁消耗大量计算能力（CPU资源）
2. 大量线程进入WaitSet
解决方案
算法
问题：没有竞争情况如何处理？
更好的方案，增加偏向锁
偏向锁：直接获取临界区
自旋竞争获取锁：轻量级锁
自旋竞争失败：升级重量级锁
不可降级
面试官：给我讲讲AQS?诶？？？什么是AQS?
面试题
AbstractQueuedSynchronizer可以用来做什么？
简述AbstractQueuedSynchronizer如何工作？
手写程序：如何用AbstractQueuedSynchronizer实现Mutex?
AQS如何实现公平性？
CAS在AQS中的作用是什么？
AQS内部的CHL算法工作原理是什么？
什么是AQS?
复习和思考
有临界区要保护
互斥量(Mutex)
synchronized
上锁/解锁：acquire/release
monitorenter/monitorexit
底层：偏向锁、轻量级锁、重量级锁（OS的锁、真实线程休眠）
思考：Java的线程谁在调度?
信号量(Semaphore)
控制临界区的并发量，并发量=1就是互斥量
？？？怎么实现呢？
伪代码参考
线程间通信（休眠+唤醒）
Object.wait/Object.notify
ReentrantLock.newCondition
await/signal
底层支持：无锁休眠当前线程/唤醒线程
LockSupport.park()
LockSupport.unpark(Thread t)
思考：synchronized够不够用？
回顾下生产者消费者的例子程序
回顾Semaphore的实现
思考：让用户底层API好吗？
性能问题
死锁问题
小明和小红鞠躬
解决方案：小明——既然你不肯先来， 我等不到你伸出手，我就伸出手吧！
tryLock(小红的锁，1000ms) {...}
思考：synchronized支持吗？
AQS
区别于synchronized(build-in or intrinsic lock)， Java提供的另一个实现同步的体系
同步器开发框架
基于Java实现
提供同步元语和高性能生产消费者结构
提供Non-Blocking能力(Cas/tryLock)
提供定时能力
提供中断能力
提供线程间写作(Condition)
提供扩展数据结构的能力
内部提供整数状态
封装CAS操作
acquire/release都基于cas状态
cas失败触发在等待队列中等待
内部封装高性能CLH队列
CAS失败自动进入队列
条件等待自动进入队列
性能层面
面试题：AQS为什么要提供等待队列？
AQS的工作原理
加锁的工作原理
控制反转：获取锁的程序由用户提供
竞争被AQS分成两个阶段
while...部分进行自旋竞争
竞争的失败者在队列中休眠(park)，直到有竞争成功者退出(unpark)
队列的实现采用CLH高性能队列
利用cas实现的无锁编程(Lock-Free)结构
复用、代码重构
Coding（手把手Mutex实现）
源代码解读ReentrantLock
AQS队列（CLH）
思考：普通的链表怎么实现队列?
分支主题
头插法
代码示例：
思考：如何出队？
无法删除尾部元素：因为没有尾部线程前一个节点的指针
CLH的解决方案
插入：尾部插入; 头部删除
思考：优势在哪里？
避免双向链表
单向链表性能好
AQS的公平性
ReentrantLock
源码解读FairSync vs UnFairSync
什么是公平？
朴素的公平
FIFO
Random
后来者不能抢占(上面就是不公平）
并发提高篇
面试官：说6个Java的同步器？还有么？ ……
面试题
synchronized和ReentrantLock的区别？
什么场景下需要锁可以重入？
什么场景下用CountDownLatch？
什么场景用Semaphore？
Phaser是怎么实现的？
什么场景会用到Exchanger?
ReentrantLock
同步原理
和synchronized相似点
临界区保护（提供锁/解锁能力）
可重入
都提供线程间协作
提供锁的升级逻辑
monitor: 偏向锁->轻量级锁->重量级锁
AQS: CAS竞争->休眠+排队竞争
都提供等待队列
monitor: EntrySet,WaitSet
AQS: CLH队列
区别点
基于AQS vs 基于Monitor
Java生态 vs 非Java生态
响应线程中断(InterruptedException) vs 不响应
提供tryLock vs 不提供
跨Block vs 单Block
可配置公平性 vs 不可配置
分支主题
重入
抢占锁的线程可以多次执行lock（原理见上一节分析ReentrantLock源代码部分）
降低心智负担
公平性
朴素的公平
性能差
允许插队
性能好
信号量（Semaphore）
允许N个线程同时进入临界区
程序示例：信号量控制并发量
分支主题
源码解读
面试
问：信号量作用是什么？
控制并发量
追问：具体的作用?
可以实现生产者消费者
追问：那ArrayBlockingQueue为何不用Semaphore实现？
条件变量性能更好
追问：那Semaphore的价值是？
抽象的价值——降低心智负担
其他场景：比如流量控制
CyclicBarrier
屏障（Barrier）
多个线程在一个屏障上互相等待，直到所有线程都到达了，再执行一个同步程序。
示例：1000W个订单要处理，分成1000批数据
1000W个订单需要处理
10000个订单*1000代
每代2个线程——2个party合作方
1个准备商品
1个准备发货单
思考：解决了什么问题？
并发读取订单关联的商品和发货单
降低计算成本、内存使用等等（分治策略）
T(排序1000W个数据) > 1000 * T(排序1W数据）
控制处理速度
Coding程序示例
思考：CyclicBarrier解决了什么问题？
多个线程协作(通信)处理任务的问题
实现了一套协作机制(循环+屏障）
追问：为什么不用ReentrantLock+条件变量？
其他方法也可以实现。但是CyclicBarrier的场景具有通用性，抽象成数据结构有价值。比如批量处理大量的数据和任务。
CountDownLatch
相当于只有一代CyclicBarrier
程序示例
思考: CountDownLatch解决了什么问题？
多个线程协作(通信)处理任务的问题
实现了一套屏障机制
Phaser
屏障部分领域语言
屏障(Barrier）：合作的线程们在屏障上等待， 然后进入同步点
同步点（Synchronization Point），通过屏障后执行的同步代码
合作方数量(paties)，就是互相等待的线程数量，只有当等待数量达到parties，才会进入同步点
到来(arrive)，代表一个线程到达屏障，并等待，每次有线程到来，arrives + 1
到达数量(arrives)，带到的线程数量
等待（wait），代表线程在barrier上等待
进步（advance），一个线程通过屏障，称为进步，代表工作有进度
开动\下一阶段（tripping/next phase）：到来的线程数量=parties，开始进入同步点
阶段(phase number)：类似CyclicBarrier中的代，每次完成一次开动，phase number加1
per线程能力
arrive (到达）：在屏障上等待其他合作方， 到达线程(arrivies)增1
waitAdvance(等待进步）：在屏障上等待其他线程，数量够了就进入同步点
register（注册），相当于声明自己是一个合作方，将parties 增1
deregister(注销），相当于注销自己，parties减1
Coding示例手把手
实现CyclicBarrier的能力
Exchanger
思考：线程间交换数据?
举例：利用Exchanger在生产者、消费者间交换Buffer
分支主题
思考：Exchanger解决了什么问题？
线程间交换数据
交换是一个高效操作
总结
思考：同步器解决了什么问题？
同步
协作模式
内存一致性模型——volatile和happens-before关系
引入
如果考虑到CPU缓存之前学的实现锁的方法会有什么变化？
关联面试题
如何解释内存一致性模型？
什么情况下会发生指令重排？
volatile关键字的用途？
double-check单例为什么要用volatile?
如何理解happens-before关系？
什么是内存一致性
抽象：指令不断读写内存形成历史
分支主题
每次写入会形成新的版本
不同观测者对历史的理解是否一致？
在某个时刻，线程1、线程2观察内存，会不会得到不同的版本？图中，线程2认为版本3的写操作已经发生；线程1认为版本3的写操作还没有发生。产生分歧，我们称为不一致。
线性一致：任何时刻都一致
弱一致：部分时刻一致
没有一致：无法确定何时一致
为什么会产生不一致？
观察下面的程序推测不一致性的成因
分级缓存策略：CPU、缓存和内存的关系。为什么这么设计？
性价比：成本不变：速度越快的存储发热越大，容量越小。
速度：L1、L2缓存消耗个位数的CPU周期。L3缓存消耗2位数的CPU周期。L3缓存比内存速度还能块10-100倍。
命中率：每一级命中率在80%左右。
a更新的路径
事件1完成后，同核心的线程就可以读到最新版本的A了。跨CPU的线程，得从内存或者L3中读取，这个时候读不到最新版本
现象：a=1执行完成后，线程B可能会print出a=0（不同CPU,并发），也可能print出a=1（同CPU）。
在同一时刻，线程A和B对a、b的值理解不一致
思考：指令需不需要重排？
println(b)需要一次读取操作（速度快，读L1）
a=1是一次写入操作(100-1000个CPU周期）
写L1\L2\L3和主存
对b的读取需不需要等待对a的写入呢？
结论：这是两个不相关的操作，可以重排
重排可以节省平均等待时间
思考顺序执行3个任务：3分钟、4分钟、5分钟， 不同顺序的平均等待时间是多少？
3-4-5: (0 + 3 + 4 )/ 3 = 2.33分钟
5-4-3: (0+5+4) / 3 = 3分钟
最短作业优先(Shortest Job First)，能减少平均等待时间
另外，在执行写入内存过程中，CPU可以做其他事情
Java虚拟机做了指令重排，这是一个复杂的技术
总结
内存不一致
相对的，需要观察者(线程）
成因
分级缓存策略
指令重排
解决内存不一致问题
变量读写不一致问题（Coding）
volatile关键字
如果逻辑上，变量的写在读之前发生，那么确保观察到的结果，写也在读之前发生。
happens-before关系
如果事件A应该在时间B之前发生，那么观察到的结果也是如此。
时间关系的一致性
双检测的单例程序(Coding)
volatile解决
还有哪些happens-before关系
单线程规则：单线程对内存的访问符合happens-before规则
Monitor规则：synchronized对锁的释放 happens-before 对锁的获取
volatile规则：volatile变量的写 happens-before读
Thread Start规则：start()调用前的操作 happens-before 线程内的程序
Thread.join规则：线程的最后一条指令 happens-before join后的第一条指令
happens-before传递性：如果A happens-before B， B happens-before C，那么A happens-before C
总结
happens before不是时间关系
happens before是发生顺序和观察到的结果关系
happens-before是操作顺序和可见性的关系
A happens-before B
如果A在B前发生，那么A带来的变化在B可以观察到（对B时刻在观察的线程可见）
面试官：LinkedBlockingDeque和SynchronousQueue工作原理一样吗？
面试题
ArrayBlockingQueue和LinkedBlockingQueue的区别？
add/offer/put的区别？remove/poll/take的区别？
DelayQueue的应用场景是什么？
SynchronousQueue的应用场景是什么？
LinkedTransferQueue和SynchronousQueue有什么异同？
LinkedBlockingDeque和SynchronousQueue工作原理一样吗？
生产者、消费者问题
也称作：有限缓冲区问题(bounded-buffer problem)
生产者、消费者问题：一个经典的多处理问题(multi-processing)。生产者产生数据，消费者消费数据。 中间用一个有界限的缓冲区连接。
举例：睡觉的理发师问题
理发师：消费者
顾客不断到来：生产者
没顾客的时候理发师休眠（消费者休眠）
坐位满了顾客不进入（生产者休眠）
思考：程序怎么写？
片面实现：没有考虑竞争条件(死锁）
死锁一种case
消费者睡眠前(itemCount == 0)，中断
生产者执行并填满队列
生产者唤醒消费者
消费者执行sleep()
思考：有哪些方法解决这个死锁问题？
对producer/consumer方法上锁
缺点：锁的范围太大
锁一部分，锁itemCount判断和sleep、wakeup操作
缺点：程序复杂
Semaphore
解决了程序复杂度的问题
思考：从面相对象角度还有没有更好的设计？
将同步控制算法在队列中实现（2合一）
条件变量
生产者消费者模型的用途
举例：web服务
类似睡觉的理发师
多生产者、多消费者
入队(enqueue)和出队(dequeue)需要考虑竞争条件。
举例：消息队列
单播(1:1)
1个生产者，1个消费者
广播(1:n)
缓存所有消息
为每个接入消费者创建一套指针
生产者消费者模型的改造变种
BlockingQueue
7种实现
ArrayBlockingQueue
LinkedBlockingQueue
LinkedBlockingDeque
PriorityBlockingQueue
DelayQueue
LinkedTransferQueue
SynchronousQueue
3类方法
抛异常
add/remove
非阻塞
offer/poll
阻塞
put/take
代码示例
线程安全
通常: 只思考单线程
处理竞争条件（锁等）
BlockingQueue：queue.take() —— 不需要思考竞争条件
心智负担低
哪些是线程安全？
java.util.concurrent下的数据结构
ArrayList、HashMap等不是线程安全
ThreadLocal
自己实现（上锁、同步器、阻塞队列、无锁编程……）
BlockingQueue的应用场景
场景1：Web服务器
多生产者+多消费者模型
队列满了拒绝服务
队列空了休眠Worker
***BlockingQueue
ArrayBlockingQueue
ListedBlockingQueue
ArrayBlockingQueue vs ListedBlockingQueue
扩容List更容易
索引成本低
代码示例
场景2：undo
undo操作
***Deque
LinkedBlockingDeque
API
putLast/putFirst
takeLast/takeFirst
offerFirst/offerLast
pollFirst/pollLast
场景3：优先级调度算法
调度任务/进程
不限个数
堆(Heap)实现
堆（Heap）实现
删除最小元素过程演示（O(logn))
1000W数据->几十次计算
插入新元素过程演示(O(logn))
PriorityBlockingQueue
线程安全的PriorityQueue
场景4：延迟队列
场景举例：控制流速
例如：营销引擎大量发券
为什么要控制？
思考：雪崩发生的原因？
大量任务来临
系统负载超过临界点
线程切换频繁
虚拟内存频繁交换
I/O资源争夺
……
方案：延迟队列
延迟队列
支持反向压力（backpressure)
阻塞任务的提交者
访问拒绝
拒绝任务的提交者
延迟队列的方案：将任务打散到未来
内部实现：PriorityQueue(每次检查Heap顶部元素的延迟是否超时）
例如：大量定时器场景
每个订单处理完成后1s后给用户发送一封邮件、短信
避免大量定时器消耗CPU资源
例如：大量延迟重试场景
需要发送大量消息给用户
指数补偿
1s,2s,4s,8s……
用法示例
场景5：线程池
线程池设计模式
Pattern
任务：Task
每个线程——Worker
复用Worker处理Task
Fixed
Worker数目固定
Cached
Worker数据看任务处理情况
线程池工作图示
每个任务尽快交给一个线程处理
线程不够->新建线程
线程复用——尽量减少创建线程
方案思考
传统模式
反向压力的实现：消费者唤醒生产
保持基于Task的接口操作: 双向结构（Dual Queue)
生产者放入红色元素
消费者放入绿色元素
每次放入——匹配
cas实现
同样的能力(Dual Stack)
Why? DualQueue DualStack
目标Review
1. 生产者等待消费者足够再生产
2. 消费者等待生产者足够再消费
vs 传统目标：生产者生产有足够空间就生产、消费者有足够元素就消费（生产者-消费者之间没有默契）
DualQueue(FIFO)
公平
DualStack(FILO)
非公平
SynchronousQueue可以用DualQueue/DualStack
new SynchronousQueue(fair:true/false)
LinkedTransferQueue——DualQueue
Coding:实现Scheduler+线程池
其他面试题
说说SynchronousQueue和LinkedTransferQueue的区别？
原理
API
面试题：说说ArrayBlockingQueue和SynchronousQueue最大的区别？以及使用场景？
见目标Review
面试题：什么是有界队列、什么是无界队列？
有界——缓冲区大小恒定
ArrayBlockingQueue
无界——缓冲区大小无限
其他
可选
LinkedBlockingQueue
LinkedBlockingDeque
面试题：LinkedBlockingDeque是一种双向队列，那么它和SynchronousQueue和LinkedTransferQueue中实现的双向有什么区别？
原理不同：有无Match操作
入无锁境：给面试官讲讲无锁编程(Lock-Free Programming)
面试题
什么是无锁编程(Lock Free)？
请举一个无锁编程的例子？
自旋锁是不是无锁编程的设计？
Obstruction Free/Lock Free/Wait Free的区别？
请举一个Obstruction Free/Wait Free的例子？
如何用LockFree实现一个栈/队列？
什么是无锁编程（Lock Free？）
引入：思考 a = a + 1 有什么问题？
分支主题
解决ABA问题：用二元组描述数据，带值和版本号
思考上面程序和锁的区别
区别1：上面程序不是一种排队结构，一个线程休眠，不会引起另一个线程等待
区别2：上面的程序总有一个线程可以进步
Lock Free：线程之间互相隔离（一个线程的延迟、阻塞、故障）不会影响其他线程，同一时刻且至少有一个线程可以进步
隔离（不互相影响进步）
延迟(e.g. sleep)
阻塞(e.g. i/o blocking)
故障(e.g. 死循环）
进步
达成计算目标
约束：至少有一个线程在进步(cas)
场景举例：CLH队列
线程通过cas竞争加入CLH队列
场景举例：SynchrounousQueue
cas竞争实现transfer操作（双向队列、双向栈）
难点解析：自旋锁spinlock是不是Lock Free
实现i++
对照组：casLoop
Coding：实战演练——Lock Free Stack
push ： 链表头插法
pop：链表头删法
并发设计思路总结
锁：互斥（Mutual Exclusion）
减少锁的范围
Obstruction Free
线程间隔离（一个线程的延迟不影响其他线程进步）
不要求一定有线程进步
线程最终可以进步
举例：嵌套的cas
第一个cas可以和第二个cas合并
第一个cas起到了「逐渐进步」的作用
Lock Free
在 Obstruction Free的基础上保证至少有一个线程进步
Wait Free
在Lock Free基础上，保证所有线程同时进步
Obstruction Free -> Lock Free -> Wait Free
隔离 + 最终进步 -> 同时时间至少1个进步 -> 所有都进步
Wait Free举例：CopyOnWrite的读线程
更新对象o
1. 拷贝o -> p
2. 更新p
3. 替换指向o的引用
疑难解答：Lockless（不用锁）和LockFree（无锁）区别？
不用锁的算法通常都是Lockless，线程之间可能会互相影响
例如：阻塞队列（本质还是排队）
高阶并发训练：N个哲学家就餐问题的优化方法
图：哲学家就餐问题
5个哲学家，5份面、5个叉子
多台机器访问多个磁带
左右手两个叉子都拿起才能吃面
哲学家吃碗面，就思考，随机到某个时刻又会饿，再去吃面……周而复始
初步协议的实现
协议：做事的规范
规则1：每个哲学家（线程）都先拿左边的叉子，再拿右边的叉子
规则2：如果拿不到，就等待
死锁（deadlock）：所有哲学家都拿起左叉子
coding哲学家的抽象
id（1-5）
三种状态
Thinking
Hungry
Eating
方法
takeLeft
takeRight
putLeft
putRight
……
时间统计
coding：初步协议的实现：死锁演示
改进协议
规则2：如果拿不到，就放下所有的叉子，重新来过
活锁（livelock）：所有哲学家都拿起左叉子（然后放下）
coding：活锁的演示
饥饿
线程因无法得到资源而无法进步
两种形式
deadlock
线程间互相等待资源导致线程冻结（哲学家同时拿起左叉子）
livelock
线程没有阻塞但是仍然无法进步（哲学家同时拿起左叉子，又同时放下左叉子）
粗糙的设计可能会把出现livelock用作实战，但是非常不建议。
协议改进
锁（Lock)
coding
减少锁的范围
coding
思考：当前算法是不是Obstruction-Free的算法？
不是：如果eating方法出错，拿起的叉子没有放下
利用条件变量
coding
通信：进一步优化
允许哲学家向周围哲学家索要叉子
进一步增加并发度（无法进餐的哲学家主动让出叉子，而不是等待）
另一种解法：阻塞队列
目标：减少程序负担
简单、好写、性能好
实现
控制队列：由一个控制线程决定哪个哲学家可以拿起叉子
工作队列：由5个工作线程处理哲学家思考和吃饭
coding
构造异常处理
假设哲学家进餐有10%的概率触发错误（一个非常长的100000s的等待）
延迟中断队列：所有进餐的哲学家超时会被中断、回滚
coding
思考：是不是Obstruction Free?
是：中断回滚构成了一个最基本的隔离，一个线程执行太长就会被其他线程中断，从而保证了进步的隔离
面试官：说说ConcurrentHashMap和synchronizedMap区别？
任务(Task)、执行(Executors)和结果(Future)
线程安全和ThreadLocal
并发编程的8个核心应用场景解读
JVM原理篇
章节导学
面试官：说说堆和栈的区别?
说法：调用函数时临时变量存在栈(Stack)中、对象存在堆(Heap)中？
栈（Stack）
一种数据结构（FILO）
一摞纸
最上面一本称为「栈顶」
栈的作用是配合执行程序，提供执行程序的必须内存空间
var a=1;
var b=2;
var c=a+b;
分支主题
int add(int a, int b) { return a + b; }
var a = 1, b = 100;
var c = add(a,b);
分支主题
结论：栈存储程序执行时的临时数据
每个线程有自己的栈和程序指针
堆(Heap)
堆不是一种数据结构（什么结构都可以存放在堆中）
垃圾堆
应用通过堆存储数据（申请、回收、托管）
allocate/de-allocate
dynamic GC
JVM的内存布局
面试题
给我讲讲JVM的内存布局？
JVM中Object都有哪些数据？
JVM的运行时数据都有哪些？
从Object角度：内存布局
围绕对象有哪些数据需要存储？
本教程以HotSpot为主
堆（Heap）也称作GC Heap，由Java的GC管理
实例数据在堆（Heap)中
思考：元数据放堆中还是堆外？
思考：编译后的代码放堆中还是堆外？
思考：常量放堆中还是堆外？
思考：对象和操作系统内核间通过内存映射构造的缓冲区呢？
思考：如何引用了Native对象呢？
重新划分区域
分支主题
从线程角度：内存布局
分支主题
整体架构解读
图
ClassLoader将.class文件导入JVM，形成运行时的类
执行引擎执行bytecode和处理GC
执行引擎调用本地库接口，执行本地方法
本地方法执行时使用Native Stack（可能形成Native Memory)
GC基本功面试：说说STW、吞吐量、FootPrint和Latency？
面试题
为什么要GC?
什么是STW?
如何提高Throughput?
高吞吐量、低延迟和低FootPrint，可以兼得吗？ 谈谈你的理解？
GC（Gabage Collection)
GC：妈妈在打扫
应用程序：孩子弄乱房间
如果打扫的速度 < 弄乱房间的速度 ？ 怎么办？
STW（Stop The World) - 不许孩子再动
吞吐量(Throughput)
程序工作时间占比（没有STW）
GC没有占用的CPU时间
-XX： GCTimeRatio=99
tips：JVM参数
- 标准参数
-cp
-X 扩展参数（非标准，不保证每个JVM都支持）
-Xmx256m
设置HeapSize
-XX 开发用（比如打印详细日志）
-XX: +PrintGCDetails
提问：如果GCTimeRatio=19代表什么？
其他方法提高Throughput?
给更大的内存（Heap+++）
-Xmx4G
最大4G Heap
更改GC算法(见后续节）
思考：多线程GC能不能提高Throughput?
原本的工作: 100s
10个线程是不是10s？
CPU占用率下降了吗？
一定能到10s吗？
任务
可并发部分（90%)
不可并发部分(10%)
10个线程极限速度倍数：1 / (90%/10 + 10%)
不到10倍！
什么应用需要高吞吐量？
A. 离线任务
B. 抢购服务
C. 竞技游戏服务
D. 音视频服务
Latency
指GC造成的停顿(STW)时间
Pause Time: 一次STW的时间
思考：Throughput小那么Latency就高吗？
思考：什么类型应用对延迟要求高？
A. 看网页
B. 刷抖音
C. 玩游戏
D. 连麦
思考：多线程能不能减少Latency?
思考：内存更大能不能减少Latency?
FootPrint
指最终应用对内存的需求
内存使用速度100M/s，回收速度80M/s
会Out of Memory
需要：STW回收
每10s做一次GC（STW全部回收）
Latency上升
峰值是200M内存（FootPrint)
思考：鱼和熊掌是否可以兼得？
假如内存无限大？——你还回收吗？
FootPrint要求
假如GC可以无限使用CPU
FootPrint可以很低，延迟很高
假如每次GC可以不中断
高延迟
参数说明
打印GC详情
-XX:+PrintGCDetails
增加时间描述
-XX:+PrintGCTimeStamps
HeapSize
-Xmx<Size>
构造OutOfMemory
参数-Xmx20M
GC基本功面试：说说引用计数和三色标记清除算法？
面试题
引用计数法有什么问题？
为什么需要3色标记而不是双色？
3色标记算法如何处理mutation?
引用计数
分支主题
节点引用为2
循环引用问题
Root Tracing
分支主题
思考：Java中的Root?
方法区中的常量、静态变量的引用
当前活跃的栈中的引用
思考：遍历图用bfs还是dfs？
一样，但是都要解决「环」
思考：需要分阶段吗？
标记（mark）阶段（上色）
清除（sweep）阶段（2 phase）
需要finalize的类
不需要finalize的类
双色标记-清除算法
从Root Ojbect开始
白：需要GC
黑：不需要GC
进行标记（Root可达标记黑色）
剩余的白色：可以清除
模型
Mark：标记
Sweep：清除
Mutation：相对于GC而言，程序执行就是变更
思考：如果Mark和Sweep之间Mutation？
如果Mutation后，将C置为黑色， D、E会被回收
结论：这种情况由C开始都需要重新标记！
三色标记-清除
解决方案：增加一种颜色
灰色：代表不确定
不确定集合： {C}
不确定集合中存在元素{C}，Sweep无法进行，继续标记
从{C}开始遍历，能到达的全部涂黑
分支主题
重新梳理算法
分支主题
Root Object可以找到的第一级元素标记灰色
灰{A}
白{B,C,D,E}
黑{}
从灰色集合中取出元素A，然后BFS递归下一级
灰{B,C}
白{D,E}
黑{A}
尝试灰色元素B
灰{C}
白{D,E}
黑{A,B}
尝试灰色元素C（灰色元素为空，标记结束）
灰{}
白{D,E}
黑{A,B,C }
思考：灰色中间状态的意义是什么？
灰色代表还有未完成的标记
思考：Sweep过程中，Java如何定位所有白色对象？
Java需要可以遍历Heap中所有对象（GC提供能力）
GC基本功面试：说说复制、整理和生代算法？
面试题
Java的堆分成哪些部分？
新生代、老生代、存活代、永久代是什么？如何工作的？
什么时候发生复制和整理？
现象：对象不断被创建和回收
碎片
整理好(compact)会得到更多的空间（复制）
结论：需要整理
现象：新创建对象死亡率高
新对象死亡率高
容易被回收
生存下来的对象更容易生存更久
因此……
分出一个内存区域给新创建的对象
新生代（New、Eden）
可能：很快就被弄乱了
思考：该如何做？
整理（compact）吗？
那不是很快又满了
而且越接近满，整理就越徒劳
有更好的方法吗？
复制（Copy） & 整理(Compact)
频繁整理的话,Survivor可以比Eden小
-XX:SurvivorRatio=8(默认）
默认Survivor:Eden=1:8
思考：Survivor中的对象去哪里？
Survivor1 -> Survivor2 -> Tenured
Survivor分成两个区域（都存活下来进入老生代）
老生代（Tenured)
对象死亡概率最小（也最稳定）
tips：S2进入Tenured，S1和S2就可以交换
作用？
减少1次复制
堆
参数
-Xmx
堆的大小
-XX:SurvivorRatio=8
Eden：Survivor
-XX:NewSize
新生代最小大小
-XX:MaxNewSize
新生代最大大小(默认没有限制）
-XX:NewRatio=2
Old:Eden = 2:1
GC的目标：你分的清楚G1/CMS/Serial/ParNew/Z/Parallel Scaveng吗？
面试题
G1/CMS/Serial/ParNew/Z/Parallel的区别？
如果对延迟要求高可以考虑哪种GC？
内存空间很大的情况（TB）级别推荐哪种GC？
Serial(连续的）Collector
Single Thread
STW
GC完才能继续
相反：concurrent
-XX:+UseSerialGC
算法：Root Tracing & Mark-Sweep系
场景
吞吐量小：内存回收工作量不大
容忍延迟：不在意卡顿
单核、内存小：0~100M
来自Oracle文档
Parallel(并行） Collector
提供最大的Throughput
MultiThread
STW
和Serial一样（只不过并行）
Not Concurrent
Mark/Sweep/Mutation不是交错执行
-XX:+UseParallelGC
算法：Root Tracing & Mark-Sweep系
场景
吞吐量要求 > 延迟要求
Concurrent Mark Sweep(CMS)
减少Pause Time
STW
Mark/Sweep/Compact/Copy等交替进行
Mark阶段(tracing阶段）
利用多核(三色标记算法）
多次
Sweep/Compact/Copy（单核）
不需要STW
算法：Root Tracing & triColor Mark-Sweep & Copy/Compact & Aging
参数
-XX:+UseConcMarkSweepGC
-XX:+CMSIncrementalMode
开启增量CMS模式（i-cms)
「增」在哪里？
约定每次最多工作的比例
Minor vs Major
Minor GC
Eden GC
触发条件
JVM无法分配更多内存
思考：如果有Object从Eden到Tenured呢？
Major GC
Tenured GC
Full GC
both
浮动垃圾（Floating gabage)的问题
已经标记为可达（不回收）的对象又需要被回收
下一次GC会被回收
问题的影响：需要使用更多内存
场景
覆盖Serial/Parallel Collector的场景
需要减少 pause Time的场景
G1(Garbage First)
目标：大内存
兼顾：Latency、Throughput
替代：CMS（尚未、部分）
最大的特点
过程图示
G1了解哪个区域最「空」
G1帮助最快回收最多内存
ZGC
低延迟的GC
最大延迟时间几个ms
暂停时间不会随着堆大小、存活对象数目增加
8MB~16TB
面试突破：JVM调试工具实操集合(jps,jstat,jmap,jinfo,jhat,jstack,jconsole)
JMeter
Java Meter(Measure Performance)
下载：https://jmeter.apache.org/download_jmeter.cgi
jps
Java Virtual Machine Process Status Tool
JVM进程状态查询工具
jstat
Java Virtual Machine statistics monitoring tool
JVM统计监控工具
jmap
Java Memory Map
打印JVM实例的共享对象映射、堆内详细信息（支持远程调试）
jinfo
Java Configuration Info
查看修改虚拟机配置（可远程）
jhat
Java Heap Analysis Tool
JVM堆分析工具（支持网页查看)
jstack
Java Stack Trace
打印Java的Stack(支持远程调试）
jconsole
可视化的JVM监控工具
5个GC实战场景的解决方案
实例1： 网络阻塞导致OutOfMemory
某分布式集群的数据缓存节点
特点：读、写操作频繁
QPS > 500
故障现象
节点内存年发生溢出（然后无法再恢复）
dump-发现很多网络相关对象
如何dump?
原因
写操作太多，导致集群同步数据网络压力上升
问题节点积压排队的网络请求
请求对象太多占用了空间
解决方案
降低集群写操作负担（读、写分离、缓冲）
实例2：堆外内存溢出
特点：频繁和服务端进行网络交互
故障现象
nio Channel提示OutOfMemory
GC不频繁
堆（各个生代）压力不大
原因
太多网络连接导致堆外内存溢出
解决方案
-XX:MaxDirectMemorySize 调整堆外映射内存的大小
思考：如果是栈溢出呢？
-Xss2m 设置每个线程堆栈的大小
实例3： 进程崩溃
某服务
特点：依赖较慢的外部服务
故障现象
JVM进程崩溃
崩溃前找到大量的Socket拒绝服务日志（Connection reset)
原因
Socket连接积压导致崩溃
大量Socket文件
解决方案
外部请求使用异步队列
实例4： 从ElasticSearch调优看GC优化策略
特点：8core CPU， 64G 内存， 500GB NvMe
Heap 大小选择： 32GB
-Xmx32g -Xms32g
设置成一样防止缓慢增加heap空间导致GC频繁
64G的50%给操做系统和Lucene(堆外内存）
sudo swapoff -a
/etc/fstab
关闭swap区域防止缺页中断
日志：
-Xlog:gc*,gc+age=trace,safepoint:file=/var/log/myapp/gc.log:utctime,pid,tags:filecount=32,filesize=64m
拆解
-Xlog:gc*
打印所有和GC相关的信息
-Xlog:gc+age=trace
打印老生代信息
-Xlog:safepoint
打印从上一次暂停点距离的(STW,Pause)的时间
filecount:最大文件数
filesize:最大文件大小
实例5：IDEA的配置加速
-Xms128m
-Xmx1998m
-Xmn512m
新生代大小
-XX:ReservedCodeCacheSize=240m
-XX:+UseConcMarkSweepGC
可以考虑用G1
-ea
启动断言机制
assert关键字
-XX:+HeapDumpOnOutOfMemoryError
-Xverify:none
不进行bytecode校验
实战字节码：反编译一个Java文件
指令介绍
invoke(调用）
invokespecial
call super(), private, init()
invokedynamic
duck typing……
绕过检查、限制等
call lambda
操作符+-*/
invokestatic
call static method
invokevirtual
虚函数-可以重写的函数
except:static,private,final
invokeinterface
load（压栈）
local variable -> stack
getxxxx
store(存储）
ref -> local variable
计算
add/mul/div/sub……
跳转
jsr/jsr_w/return/goto……
面试官：说说Java的对象在内存中的结构
面试题
说一下Object在内存中的格式？
说一下初始化一个类的过程？
空的Object多大？
Class Header里都有什么？
对象的生命周期
load
例如： disk -> memory
ClassLoader
static initializers
static fields
触发原因：new/访问静态成员/loader加载等
loaded
create
allocate memory
constructor
created
live
in use
Root Set可以找到（且被使用）
invisible
泄露，Root Set可以找到，但是没有使用
unreachable
Root Set不可达（会被回收）
destroy/gc
collected
finalize
deallocated
Object在内存中的格式(Object Memory Layout)
分支主题
mark word
hashCode
对象的hashCode
age
分代年龄
标志位(3bit)
unlocked
light-weight locked
heavy-weight locked
marked for gc
biased
Lock Record Address
轻量级锁(指向栈中的锁记录）
检查Mark Word是否指向当前线程的栈
Monitor Address
指向对象的Monitor
Forwarding Address
gc自己使用
klass
指向Object的元数据
padding：对齐
Hotspot：8字节对齐
注意描述
给我讲讲Java Object的格式
总
有严格定义
不同虚拟机可能会不同
分成头部和数据，可能还有Padding
问：空Object多大？
面试官：ClassLoader如何打破双亲委派模型？
面试题
什么是双亲委派模型？
说说双亲委派的过程？
只有一个ClassLoader为什么不够用？
如何打破双亲委派模型？
ClassLoader
运行时加载类到JVM
文件
内存
网络……
图：ClassLoader接收.class，产出bytecode
思考：只有1个ClassLoader够不够用？
多样的需求
从文件
从内存
从TCP/UDP/HTTP
从其他Library
其他策略
不一样的缓存策略
不一样的安全策略
不一样的统计策略
不一样的代理策略
……
……
思考：软件设计在遇到多样化的需求时，怎么办？
举例：I/O Stream
版本问题
分支主题
安全与缓存
委托父类加载（把缓存设置到父类）
父子之间信任关系传递
MetaProgramming
运行时生成Class，然后执行
思考：需要什么样的模型？
树状关系
Root Class Loader
Leaf Class Loader
委托模型
子Class Loader委托父Class Loader完成工作
缓存设置在父节点
都有哪些ClassLoader?
BootStrap Class Loader
加载 Java核心类
例如：Standard JDK
Extensions Class Loader
加载扩展: 如JRE目录下lib/ext
Application Class Loader
classpath
Custom Class Loader
用户自定义
一种方案：双亲委派(Delegate)模型
分支主题
加载过程
Coding阅读
实战ClassLoader: 远程加载程序
存储、缓存、搜索篇
ACID和CAP原则专题
行存储和列存储专题
NoSQL数据库专题
MongoDB专题
Mysql锁、事务面试题整理
Mysql的分库分表面试专题
主从、binlog同步专题
高性能Mysql表结构设计面试专题
TIDB专题
ElasticSearch原理专题
ElasticSearch的3个重要使用场景
数据仓库和大数据专题
数据库技术选型分析：给你10款可选的数据库
缓存原理相关面试题整理
Redis原理专题
Redis集群方案专题
Linux、网络和、I/O篇
Linux重点指令梳理
Linux管道运用整理
Linux Bash编程整理
TCP协议专题
UDP协议专题
IPv4和IPv6专题
Socket原理专题
操作系统的5种I/O模型专题
4种网络和I/O的线程模型
NIO vs IO专题
网络面试题整理
网络I/O场景面试题整理
网络调试和TCP优化实战面试题整理
大厂高并发、大数据场景篇
电商场景方案整理
社交场景方案整理
游戏场景方案整理
海量数据分析解决方案整理
海量数据搜索解决方案整理
海量日志分析+监控解决方案整理
架构师成长篇
后续1年让自己天翻地覆——学习资料推荐
P6-P8的路如何走？
0 条评论
下一页
