常见锁策略与CAS介绍

1.常见的锁策略

1.1.乐观锁 vs 悲观锁

• 悲观锁: 预期锁冲突的概率很高
  • 总是假想最坏的情况,每次去拿数据的时候都认为别人会修改,所以每次在拿数据的时候都会上锁,这样别人想拿这个数据的话,就会阻塞等待锁释放.
• 乐观锁: 预期锁冲突的概率很低
  • 假设数据一般情况下不会产生并发冲突,所以只有在数据进行提交更新的时候,才会正式对数据是否产生并发冲突进行检测,如果发现并发冲突了,则返回用户错误的信息,让用户决定如何去做.

1.2.读写锁 vs 普通的互斥锁

• 普通的互斥锁: 只有加锁和解锁两个操作
  • 两个线程针对同一个对象加锁,就会产生互斥
• 读写锁: 读者之间并不互斥,写者与任何人互斥
  • 如果代码只是进行读操作,就加读锁
  • 如果代码进行修改,就加写锁
  • 针对读锁和读锁之间没有互斥关系
  • 读锁和写锁之间,写锁和写锁之间 才需要互斥

1.3.重量级锁 vs 轻量级锁

• 重量级锁: 如果使用的锁是基于内核的一些功能来实现的,此时一般认为这是重量级锁
  • 大量的内核态用户态切换
  • 很容易引发线程的调度
• 轻量级锁: 如果锁是纯用户态实现的,此时一般认为这是轻量级锁
  • 少量的内核态用户态切换
  • 不太容易引发线程调度

1.4.挂起等待锁 vs 自旋锁

• 挂起等待锁,往往就是通过内核的一些机制来实现,往往较重 (重量级锁的一种典型实现)
  • 在认为长时间获取不到锁的时候,让线程进入阻塞等待状态.防止过分消耗CPU
• 自旋锁,往往就是通过用户态代码来实现,往往较轻 (轻量级锁的一种典型实现)
  • 在认为很快就可以获得到锁的时候,循环抢锁,虽然当前抢锁失败,但是很快锁就会被释放.没必要放弃 CPU.

自旋锁伪代码

while (抢锁(lock) == 失败) {}
1

如果获取锁失败, 立即再尝试获取锁, 无限循环, 直到获取到锁为止.

• 优点: 没有放弃 CPU, 不涉及线程阻塞和调度, 一旦锁被释放, 就能第一时间获取到锁.
• 缺点: 如果锁被其他线程持有的时间比较久, 那么就会持续的消耗 CPU 资源. (而挂起等待的时候是 不消耗 CPU 的).

1.5.公平锁 vs 非公平锁

此处公平的判定为 “先来后到”

• 公平锁: 遵守 “先来后到”. B 比 C 先来的. 当 A 释放锁的之后, B 就能先于 C 获取到锁.
• 非公平锁: 不遵守 “先来后到”. B 和 C 都有可能获取到锁.

注意

• 操作系统内部的线程调度就可以视为是随机的. 如果不做任何额外的限制, 锁就是非公平锁. 如果要 想实现公平锁, 就需要依赖额外的数据结构, 来记录线程们的先后顺序.
• 公平锁和非公平锁没有好坏之分, 关键还是看适用场景.

1.6.可重入锁 vs 不可重入锁

• 可重入锁: 允许同一个线程多次获取同一把锁.
• 不可重入锁: 不允许同一个线程多次对已获取到的对象加锁

// 第一次加锁, 加锁成功 
lock(); 
// 第二次加锁
lock();
1
2
3
4

比如上述代码,第一次加锁后,如果第二次不能继续加锁，那么这个锁就是不可重入锁.会阻塞等待.
如果可以继续加锁,那么就是可重入锁.

Java中只要以Reentrant开头命名的锁都是可重入锁,而且JDK提供的所有现成的Lock实现类,包括 synchronized关键字锁都是可重入的.而 Linux 系统提供的 mutex 是不可重入锁.

• synchronized: synchronized会用一个计数器来判断锁是否释放,每次对同一个对象加锁,计数器都会+1,每次释放会-1.如果计数器为0的时候,就是真正释放了锁.
• (不同的语言有不同的实现方式)

2.CAS

compare and swap 比较和交换

2.1.CAS 伪代码

下面写的代码不是原子的, 真实的 CAS 是一个原子的硬件指令完成的. 这个伪代码只是辅助理解 CAS 的工作流程.

boolean CAS(address, expectValue, swapValue) {
    if (&address == expectedValue) {  
        &address = swapValue;    
        return true; 
    }  
    return false;
}
1
2
3
4
5
6
7

CAS就是根据一个值是否改变来判定,是否被操作.

1. 首先读取到要操作的值,并记录(从address读取,记录在expectValue中)
2. 然后执行操作,记录新值和旧值(执行操作后,新值为swapValue,旧值还是expectValue)
3. 再次读取使用旧值来比较(&address == expectValue)
4. 如果相同则认为中间值未被更改,将新的值写入(&address = swapValue)
5. 返回结果

2.2.CAS 是怎么实现的

针对不同的操作系统,JVM 用到了不同的 CAS 实现原理,简单来讲:

• java 的 CAS 利用的的是 unsafe 这个类提供的 CAS 操作
• unsafe 的 CAS 依赖了的是 jvm 针对不同的操作系统实现的Atomic::cmpxchg;
• Atomic::cmpxchg 的实现使用了汇编的 CAS 操作，并使用 cpu 硬件提供的 lock 机制保证其原子 性。

简而言之: 是因为硬件予以了支持,软件层面才能做到原子性.

2.3.基于CAS实现自旋锁(伪代码)

public class SpinLock {
    private Thread owner = null;
    public void lock(){
        // 通过 CAS 看当前锁是否被某个线程持有.
        // 如果这个锁已经被别的线程持有, 那么就自旋等待.
        // 如果这个锁没有被别的线程持有, 那么就把 owner 设为当前尝试加锁的线程.
        while(!CAS(this.owner, null, Thread.currentThread())){
        }
    }
    
    public void unlock (){
        this.owner = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

通过一个循环来实现的,循环里面调用CAS,CAS会比较当前的owner值是否是null,如果是null 就改成当前线程,意思就是当前线程拿到了锁,如果不是null就放回false 进入下次循环,下次循环仍然是进行CAS操作,如果当前这个锁一直被别人持有,当前尝试加锁的线程 就会在这个 while 的地方快速反复进行循环 -> 自旋(忙等)

虽然是忙等 但是这里自旋锁是轻量级锁,也可以视为乐观锁.当前这个锁虽然没能立即拿到,但是预期很快就会拿到(假设锁冲突不激烈).短暂的自旋几次,浪费点CPU问题都不大,好处就是只要这边锁一释放,就能立即拿到锁.

2.4.Java 中 CAS 的应用

标准库中提供了 java.util.concurrent.atomic 包, 里面的类都是基于这种方式来实现的. 典型的就是 AtomicInteger 类.

2.4.1 AtomicInteger类

public class Test {
    /**
     * Java中原子类的 CAS
     * AtomicInteger num = new AtomicInteger(0);
     * num.decrementAndGet();//--num
     * num.incrementAndGet();//++num
     * num.getAndIncrement();//num++
     * num.getAndDecrement();//num--
     * num.getAndAdd(10);//num += 10;
     */
    public static void main(String[] args) throws InterruptedException {
        AtomicInteger num = new AtomicInteger(0);
        Thread t1 = new Thread(()->{
            for (int i = 0; i < 50000; i++) {
                num.getAndIncrement();//num++
            }
        });
        Thread t2 = new Thread(()->{
            for (int i = 0; i < 50000; i++) {
                num.getAndIncrement();
            }
        });
        //在这里 不会有线程安全问题 基于 CAS实现++ 操作
        //这里就可以保证既能线程安全,又能比synchronized高效
        //因为 CAS不涉及线程阻塞等待
        t1.start();
        t2.start();
        t1.join();
        t2.join();

        System.out.println(num.get());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

2.5.CAS 中的 ABA 问题

2.5.1.什么是 ABA 问题

根据 2.1 的伪代码流程来解释

经过了上述流程,(&address)的值已经被改变过了两次.但是比较的时候,在代码看来是没有改变过的.会继续进行正常的操作.这就是 CAS中的 ABA问题.

ABA问题的解决方案

给要修改的值, 引入版本号. 在 CAS 比较数据当前值和旧值的同时也要比较版本号是否符合预期.

• CAS 操作在读取旧值的同时, 也要读取版本号.
• 真正要修改的时候
  • 如果当前版本号和读到的版本号相同, 则修改数据, 并把版本号 + 1.
  • 如果当前版本号高于读到的版本号. 就操作失败(认为数据已经被修改过了).