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