常见锁策略

乐观锁和悲观锁

悲观锁

总是假设最坏的情况, 每次去拿数据的时候都会认为会被别人修改, 因此会上锁, 防止数据在使用过程中被别的线程修改,

乐观锁

假设数据一般情况下不会产生并发冲突,因此在拿数据,操作数据的过程中不加锁, 而在数据进行提交更新的时候, 才会正式对数据是否产生并发冲突进行检测 .
(如何对数据是否产生并发冲突进行检测? 引入版本号)
如果发生并发冲突了, 则返回错误数据给用户,让用户决定如何去解决 .

synchronized 初始使用乐观锁策略, 当发生锁竞争比较频繁的时候, 会自动切换成悲观锁策略

读写锁

多线程之间, 读和读不会产生线程安全问题, 读和写, 写和写之间, 会产生线程安全问题.
如果两种情况下都使用同一种锁, 会产生极大的性能消耗 (得解决线程安全问题吧?), 读写锁就是解决这个问题, 应运而生.

读写锁(readers-writer lock), 把读操作和写操作区分对待
要求在执行加锁操作时, 需要额外表明读写意图

• 读加锁和读加锁之间不互斥
• 读加锁和写加锁之间互斥
• 写加锁和写加锁之间互斥 .

synchronized 不是读写锁

重量级锁和轻量级锁

前置知识
锁的核心特性 “原子性”, 这样的机制追根溯源是 CPU 这样的硬件提供的

• CPU 提供了 “原子操作指令”
• OS 基于 CPU 的原子指令, 实现了 mutex 互斥锁
• JVM 基于 OS 提供的互斥锁, 实现了 synchronized 和 ReentrantLock 等关键字和类

重量级锁 : 加锁机制重度依赖 OS 提供的 mutex

• 大量的内核态用户切换
• 很容易引发线程的较低

轻量级锁 : 加锁机制尽可能不用 mutex , 而是尽量在 用户态 代码完成, 实在搞不定, 在使用 mutex

• 少量的内核态用户切换
• 不太容易引发线程调度

attention : 如果内核态和用户态进行频繁切换, 效率和资源的消耗就会非常大!

synchronized 是一个轻量级锁, 如果锁冲突比较严重, 就会变成重量级锁. (自动转换)

自旋锁 (Spin Lock)

自旋锁可以解决的情况 :
一般情况下, 抢锁失败后, 进入阻塞状态, 放弃 CPU , 然后进行一堆线程之间的锁竞争(时间可能会很漫长 …)
当抢锁失败后, 由于锁一般会被很快释放, 因此没必要放弃 CPU.(即一旦锁被其他线程释放, 能第一时间获取到锁)

可以通过一个伪代码来大概看出自旋锁如何实现的:

while( 抢锁(Lock) == 失败 ) {}  //一直死循环跑, 直到获取到锁

自旋锁 和 挂起等待锁 是相对的

自旋锁是一种典型的 轻量级锁 的实现方式

• 优点 : 没有放弃 CPU , 不涉及线程阻塞和调度 (因此轻量), 一旦锁被释放, 能第一时间获取到锁 .
• 缺点 : 都 while 循环了, 那么如果其他线程长时间持有锁, 那么 CPU 消耗的资源会很多 (挂起等待是不消耗 CPU 的)

synchronized 中的轻量级锁策略, 大概率是通过自旋锁的方式实现的 .

公平锁 VS 非公平锁

公平锁 : 遵循先来后到, 先来的一定会比后到的先执行 .
非公平锁 : 不遵循先来后到, 当锁被释放后, 阻塞队列中的所有线程, 一起竞争锁, 谁能抢到谁先用 .

attertion :

• OS 内部的线程进度可以视为是随机的, 如果要实现公平锁, 就需要依赖额外的数据结构, 来记录线程间的先后顺序
• 公平锁和非公平锁之间无好坏之分, 只有适用不适用

synchronized 是非公平锁

可重入锁(递归锁) VS 不可重入锁

可重入锁 : 允许同一个线程多次获取同一把锁 (如果一个线程内, 两次对同一个对象加锁, 如果中间没有锁释放, 可重入锁是可以进入的, 不可重入锁就不能进入, 会进行阻塞)

• Java 中只要以 Reentrant 开头命名的锁, 都是可重入锁, 且 JDK 提供的所有线程的 Lock 实现类, 包括 synchronized 都是可重入锁 .

• Linux 提供的 mutex 是不可重入锁

CAS

什么是 CAS?

CAS (Compare and swap) : “比较与交换”, 是一种实现并发算法时常用到的技术
相当于通过一个原子的操作, 同时完成 “读取内存, 比较是否相等, 修改内存” 这三个步骤. 本质上需要 CPU 指令的支撑

CAS 算法 :
有三个操作数 : 内存中的原数据 (V) , 旧的预期值 (A), 修改后的值 (B)

1. 比较 A 与 V 是否相等
2. 如果 A == V , 那么将 B 写入 V
3. 返回替换操作, 是否成功 (true or false)

伪代码如下 (真实的 CAS 是一个原子操作)

boolean CAS (address, expectValue, swapValue) {
	if(&address == expectValue) {
		&address = swapValue;
		return true;
	}
	return false;
}

attention : CAS 是乐观锁的一种实现方式, 因此该操作不会阻塞其他线程

CAS 是如何实现的?

硬件给予了支持, 软件方面才能对 CAS 进行了实现

• JVM 中的 CAS : 通过 UnSafe 类来调用, OS 底层的CAS指令实现。

CAS 的应用

• 实现原子类
• 实现自旋锁

CAS 的 ABA 问题

什么是 ABA 问题?

假设有两个线程 t1 & t2, 有一个共享变量 num, 初始值为 A
当 t1 想使用 CAS 把 num 的值修改的时候, 会对 num 进行判定

• 先读取 num 的值, 存储到 oldNum 中
• 使用 CAS 判定当前 num 的值是否为 A , 如果为 A, 就修改

但是如果在判定过程中 ( if( num == oldNum )), t2 线程对 num 进行了多次操作, 而且其最后 num 的值最终变成了 原值, 即 A -> B -> … ->A, 那这个时候, t1 进行的判定, 是符合的 (非原子操作), 但是理论上, 他们并不相等 (用一个不太精巧的说法, 值相等, 址不相等)
.

解决方法

引入版本号, 在 CAS 进行数据比对的时候, 也比较版本号是否符合预期

// 伪代码
if(版本号(num) == 版本号(oldNum) && num == oldNum ) { 
	版本号(num)++;
	num = newNum;
}

synchronized 原理

基本特点 (JDK 1.8 版本下)

1. 开始是乐观锁, 如果锁冲突频繁, 会自动转换成悲观锁
2. 开始是轻量级锁实现, 如果锁被长时间持有, 会转换成重量级锁
3. 实现轻量级锁的时候大概率用到自旋锁策略
4. 不公平锁
5. 可重入锁
6. 不是读写锁

加锁工作过程

JVM 将 synchronized 锁分为 无锁, 偏向锁, 轻量级锁, 重量级锁 状态, 会根据情况, 依次升级

偏向锁

偏向锁不是真的加锁, 只是说给一个 “偏向锁标记”, 记录该锁属于哪个线程
如果后续没有其他线程来竞争该锁, 那就不用加锁 (避免加锁解锁的开销)
如果后续有其他线程来竞争该锁, 那么偏向锁就代表我已经被其他线程加锁了, 此时偏向锁取消, 进入轻量锁状态

轻量级锁

轻量锁通过 CAS 实现

• 通过 CAS 检查并更新一块内存 (eg: NULL -> 该线程引用)
• 如果更新成功, 就认为加锁成功
• 如果更新失败, 则认为该锁被占用, 继续自旋式等待 (并不放弃 CPU , 才是轻量级, 放弃了, 就是重量级了)

重量级锁

重量级锁是指用到内核提供的 mutex

• 执行加锁操作, 先进入内核态
• 在内核态中判定当前锁是否已被占用
• 如果该锁没有占用, 则加锁成功, 并切回用户态
• 如果该锁被占用, 则线程进入该锁的等待队列, 挂起等待

一些对于锁的优化操作

锁消除

编译器 + JVM 判断锁是否可消除, 如果判定通过, 则直接消除

eg: StringBuffer 是线程安全, 原因在于有很多操作 (eg: append) 是加锁的, 但是如果是单线程环境下, 就没有必要进行上锁, 此时 编译器 和 JVM 就会进行判断, 并且消除锁

锁粗化

一段逻辑中如果出现多次锁解锁, 编译器 + JVM 会自动进行锁的粗化

锁的粒度: 粗和细

比如上面的一段过程反复加锁解锁, 中间如果没有其他线程的介入, JVM 就会自动把这一段的锁操作合并为一个, 减少了资源消耗

Callable 接口

Callable 是什么?
Callable 是一个接口, 和 Runnable 相对, 但是 Callable 会有一个返回值 (Runnable 没有)
Callable 和 Runnable 都是描述一个 “任务”, 二者的区别在于有没有返回值 .

示例代码

• 泛型参数表示返回值的类型
• futureTask.get() 可以阻塞等待线程计算完毕, 并获取 futureTask 中的结果

JUC (java.util.concurrent) 的常见类

ReentrantLock 类

可重入互斥锁, 和 synchronized 定位相似, 都是用来实现互斥效果, 保证线程安全的
“Reentrant” 该单词原意就是 “可重入”

ReentrantLock 的用法 :

• lock () : 加锁, 死等
• trylock (超时时间) : 加锁, 超时就放弃加锁
• unlock () : 解锁

ReentrantLock 和 synchronized 的区别

• synchronized 是一个关键字, 是 JVM 内部实现的. ReentrantLock 是标准库的一个类, 在 JVM 外实现 (基于 Java 实现) .
• synchronized 使用时不需要收到那个释放锁, ReentrantLock 需要手动释放, 使用更灵活.
• synchronized 在申请锁失败时, 会死等, ReentrantLock 可以设置超时时间
• synchronized 是非公平锁, ReentrantLock 默认是非公平锁, 可通过构造方法, 设置为公平锁 .
• ReentrantLock 有更强大的唤醒机制(这个了解就好, 有点深了), synchronized 通过 Object 的 wait / notify 实现 等待-唤醒, 随机唤醒(非公平锁). ReentrantLock 搭配 Condition 类实现 等待-唤醒, 可以精确控制唤醒哪个线程 (可设置为公平锁).

如何选择使用二者?

• 锁竞争不激烈的时候, 选 synchronized, 更方便高效
• 需要公平锁, 用 ReentrantLock 并设置构造方法

原子类

原子类内部使用 CAS 实现, 所以性能要优于加锁, 有以下几个

• AtomicBoolean
• AtomicInteger
• AtomicIntegerArray
• AtomicLong
• AtomicReference
• AtomicStampedReference

原子类内部有许多方法, 具有原子性

线程池

解决频繁创建线程的问题

ExecutorService & Executors

• ExecutorService 表示一个线程池的实例
• Executor 是一个工厂类, 能够创建出集中不同风格的线程池
• ExecutorService 的 submit 方法能够向线程池中提交若干个任务

代码示例

private static void test01() {
    ExecutorService pool = Executors.newFixedThreadPool(10);
    pool.submit(new Runnable() {
        @Override
        public void run() {
            System.out.println("hello_zrj!");
        }
    });
}

Executors 创建线程池的几种方法

• newFixedThreadPool : 创建固定线程数的线程池
• newCachedThreadPool : 创建线程数数目动态增长的线程池
• newSingleThreadExecutor : 创建只含单个线程的线程池
• newScheduledThreadPool : 设置延迟时间后执行命令, 或者定期执行命令, 进阶版的 Timer

Executors 本质上是 ThreadPoolExecutor 类的封装
ThreadPoolExecutor 提供了更多的可选参数, 可以进一步细化线程池行为的设定

信号量

表示 “可用资源的数量”, 本质上就是一个计数器
Semaphore 的 PV 操作中, 加减计数器操作都是原子的, 可在 多线程 下直接使用

代码示例

private static void test02() {
	Semaphore semaphore = new Semaphore(4);
	
	Runnable runnable = new Runnable() {
		@Override
		public void run() {
			try {
				System.out.println("申请资源");
				semaphore.acquire();
				System.out.println("获取到资源");
				Thread.sleep(1000);
				System.out.println("释放资源");
				semaphore.release();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	};
	
	for (int i = 0; i < 20; i++) {
		Thread t = new Thread(runnable);
		t.start();
	}
}

上述代码因为设置的信号量为4, 因此最多只能有四个线程在同时正常进行, 其余的线程, 需要阻塞队列等待信号量空余才能调用 .

CountDownLatch

同时等待 N 个任务结束

示例代码

private static void test03() throws InterruptedException {
    CountDownLatch latch = new CountDownLatch(10);
    Runnable runnable = new Runnable() {
        @Override
        public void run() {
            try {
                Thread.sleep(1000);
                latch.countDown();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    };
    for (int i = 0; i < 10; i++) {
        new Thread(runnable).start();
    }
    // 必须等到 10 个线程都结束
    latch.await();
    System.out.println("阻塞结束, 运行后续代码");
}

线程安全的集合类

Vector , Stack , HashTable

多线程环境下使用 ArrayList

1. 加锁, synchronized & ReentrantLock

2. Collections.synchronizedList(new ArrayList) ;
   synchronizedList 是标准库提供的一个基于 synchronized 进行线程同步的 List
   synchronizedList 的关键操作上都带有 synchronized

3. 使用 CopyOnWriteArrayList
   CopyOnWrite 容器即写时复制的容器, 采用读写分离思想
   往该容器添加元素的时候, 不会直接添加, 而是先将该容器进行拷贝到新容器, 往新容器添加元素, 再将原容器的引用指向新的容器
   好处是可以进行并发的读, 而不用加锁 (读也是拷出来读, 所以对原容器的修改不会涉及到这个读的容器)

• 优点 :
  在读多写少的情况下, 性能高 (不涉及锁竞争)
• 缺点 :
  占用内存多 (容器拷贝)
  新写的数据, 不能第一时间获取到 (写完后, 还得把原容器的引用指向新容器, 中间涉及时间消耗)

多线程环境使用队列

ArrayBLockQueue
基于数组实现的阻塞队列

LinkedBlockQueue
基于链表实现的阻塞队列

PriorityBlockQueue
基于堆实现的优先级阻塞队列

TransferQueue
最多只包含一个元素的阻塞队列

多线程环境使用哈希表

HashMap 不是线程安全的

多线程下可以使用 :

• HashTable
• ConcurrentHashMap

HashTable
只是简单的把关键方法加上了 synchronized 关键字
相当于直接针对 Hashtable 对象本身加锁

• 多线程访问同一个 HashTable 对象, 会造成锁冲突
• size 属性也通过 synchronized 来控制同步, 比较慢
• 一旦触发扩容, 由当前占用线程完成整个扩容过程, 该过程设计大量元素拷贝, 效率相当低

ConcurrentHashMap
相当于对 HashTable 进行一定的优化

• 读操作没有加锁 (但是使用 volatile 保证内存可见性), 写操作加锁 (仍使用 synchronized), 锁的不是整个对象, 而是 “锁桶 (每个链表的头结点)”, 这样只有两个线程访问的恰好是一个哈希桶上的数据才会出现锁冲突
• 充分利用 CAS 特性, 如 size 属性通过 CAS 更新, 避免出现重量级锁
• 优化扩容方式: 化整为零
  发现需要扩容的线程, 只需要创建一个新的数组, 同时搬几个元素过去
  扩容期间, 新老数组同时存在
  后续每个操作 ConcurrentHashMao 的线程, 都会参与搬元素的过程 (每个线程只操作一部分)
  搬完最后一个元素后, 删除老数组
  在搬元素的过程中, 插入数据只操作新数组, 查找数据只操作老数组

死锁

什么是死锁

多个线程同时阻塞, 并且互相占有彼此所需的资源, 并且资源之间不可抢夺, 导致程序被无限期阻塞, 因此程序不可能正常终止

死锁的特性

• 互斥使用
• 不可抢占
• 请求和保持
• 循环等待

如何避免死锁

从特性入手
具体的话, emm … (翻课本吧 BUSHI )
(写累了, 下次再说, 有缘再补上 …)