锁策略与CAS

目录

♫什么是锁策略

♫乐观锁与悲观锁

♫互斥锁和读写锁

♫重量级锁和轻量级锁

♫自旋锁和挂起等待锁

♫公平锁和非公平锁

♫可重入锁和不可重入锁

♫什么是CAS

♫CAS实现原子类

♫CAS实现自旋锁

♫CAS的ABA问题

---

♫什么是锁策略

锁策略指的是在并发访问数据时，为了保证数据的一致性和安全性，对某些数据对象进行加锁的具体策略，下面是几种常见的锁策略。

♫乐观锁与悲观锁

♩乐观锁：认为每次去拿数据的时候都不会被别修改，所以不会进行加锁，在数据进行提交更新的时候，才会正式对数据是否产生并发冲突进行检测，如果发现并发冲突了，则让返回用户错误的信息，让用户决定如何去做。

♩悲观锁：认为每次去拿数据的时候都会被别人修改，所以在进行操作之前，先对数据进行加锁，保证其他线程无法对此数据进行修改，操作完成后再释放锁。

举个例子，在小明通过QQ请教老师问题的事件中：

乐观锁相当于小明每次问问题都认为老师是有空的，直接向老师提问问题（没加锁，直接访问资源），如果老师有空就解决问题，如果老师没空就下次再问（没加锁，也能识别出数据访问冲突）。

悲观锁相当于小明每次问问题都认为老师是比较忙的，在问问题前都先询问老师是否有空，预约个问问题的时间（相当于加锁），老师有空就预约成功，没空则下次再预约时间。

注：

①.乐观锁可以通过引入版本号来识别数据访问是否冲突（数据只要被修改一次，版本号就加一，如果线程1修改数据后要写入的内存时发现版本号小于等于内存里数据的版本号就说明有其他线程修改了数据，写入失败）

②.synchronized先是乐观锁，当锁竞争激烈就会转化为悲观锁

♫互斥锁和读写锁

♩互斥锁：互斥锁则是一次只允许一个线程访问共享资源。当一个线程持有互斥锁时，其他线程必须等待该线程释放锁之后才能获取锁并访问共享资源。Java 中 synchronized 就是读写锁。

♩读写锁：允许多个线程同时读取共享资源，但只允许一个线程写入共享资源。当写入的时候，所有的读取线程和写入线程都必须等待该写操作完成。

读写锁就是把读操作和写操作区分对待，Java 标准库提供了 ReentrantReadWriteLock 类, 实现了读写锁：①.ReentrantReadWriteLock.ReadLock 类表示一个读锁，这个对象提供了 lock / unlock 方法进行加锁解锁。②.ReentrantReadWriteLock.WriteLock 类表示一个写锁，这个对象也提供了 lock / unlock 方法进行加锁解锁。

import java.util.concurrent.locks.ReentrantReadWriteLock;
 
public class Test {
    public static void main(String[] args) {
        //获取一个锁对象
        ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
        //获取lock对象的读锁
        ReentrantReadWriteLock.ReadLock readLock = lock.readLock();
        //获取lock对象的写锁
        ReentrantReadWriteLock.WriteLock writeLock = lock.writeLock();
 
        //t1线程读加锁
        Thread t1 = new Thread(()->{
            readLock.lock();
            System.out.println("t1");
            readLock.unlock();
        });
        //t2线程写加锁
        Thread t2 = new Thread(()->{
            writeLock.lock();
            System.out.println("t2");
            writeLock.unlock();
        });
    }
}

注：其中，读加锁和读加锁之间不互斥；写加锁和写加锁之间互斥；读加锁和写加锁之间互斥

♫重量级锁和轻量级锁

锁的原子性的来源是：CPU提供的原子操作指令→操作系统基于CPU的原子操作指令实现 mutex 互斥锁→JVM基于操作系统提供的 mutex 互斥锁实现 synchronized、ReentrantLock等关键字锁。而轻量级锁和重量级锁的区别就在于是否依赖 mutex 互斥锁。

♩轻量级锁：加锁机制尽可能不使用 mutex, 而是尽量在用户态代码完成，实在搞不定了, 再使用 mutexv 互斥锁。轻量级锁只涉及少量的内核态用户态切换，不太容易引发线程调度。

♩重量级锁：加锁机制重度依赖操作系统提供的 mutex 互斥锁。轻量级锁涉及大量的内核态用户态切换，很容易引发线程的调度。

注：乐观锁大多都是轻量级锁，悲观锁大多是重量级锁

♫自旋锁和挂起等待锁

♩自旋锁：当一个线程发现另一个线程持有锁时，它会一直尝试获取锁，而不是进入等待状态，直到它成功获取到锁。

♩挂起等待锁：当一个线程发现另一个线程持有锁时，它会进入等待状态，释放CPU资源，直到其他线程释放锁，它才会被唤醒。

举个例子，在抢候补票事件中：

自旋锁相当于不断去抢票，当有人退票的话就能第一时间抢到票。

挂起等待锁相当于没票就不抢了，等到有票了再去抢。

注：自旋锁是一种典型的轻量级锁，挂起等待锁是一种典型的重量级锁

♫公平锁和非公平锁

♩公平锁：多个线程等待获取同一把锁，等到该锁被释放的时候先等待的线程先获取到锁

♩非公平锁：多个线程等待获取同一把锁，不管谁先等待，等到该锁被释放的时候一起竞争这把锁

举个例子，在等待图书馆开门事件中：

公平锁相当于先在图书馆外等开门的人在图书馆开门后先进去。

非公平锁相当于不管谁先在图书馆外等开门，只要门一开，各凭本事挤进去。

注：操作系统内部的线程调度就可以视为是随机的. 如果不做任何额外的限制, 锁就是非公平锁. 如果要想实现公平锁, 就需要依赖额外的数据结构, 来记录线程们的先后顺序

♫可重入锁和不可重入锁

♩可重入锁：支持重复加锁和释放的锁，同一个线程可以多次获得同一个锁，如果线程已经持有该锁，则需要进行重入计数，多少次加锁就需要多少次释放锁才能真正释放。

♩不可重入锁：只能加锁一次，不能重复加锁的锁，如果一个线程已经持有该锁，则再次调用加锁方法会导致死锁。

注：synchronized就是一种可重入锁

♫什么是CAS

CAS的 全称是 Compare and swap ，即 比较并交换 ，一个 CAS 涉及到以下操作：

我们假设内存中的原数据 V ，旧的预期值 A ，需要修改的新值 B 。

1. 比较 A 与 V 是否相等。（比较）

2. 如果比较相等，将 B 写入 V 。（交换）

3. 返回操作是否成功。

下面是CAS的伪代码：

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

注：CAS操作是由CPU指令支持的，保证了操作的原子性

♫CAS实现原子类

Java中的CAS实现原子类主要包括AtomicBoolean、AtomicInteger、AtomicLong、AtomicReference等。

以AtomicInteger为例，CAS实现原子类的原理是在操作值的时候，先读取当前的值，然后对比当前值是否与期望的值相同，如果相同，则执行操作并更新值；如果不同，则说明其他线程已经更新了值，当前线程需要重新读取值并重试。

下面是AtomicInteger的伪代码实现：

class AtomicInteger {
    private int value;
    public int getAndIncrement() {
        int oldValue = value;
        //伪代码，这里的CAS()在Java中并不存在
        while(CAS(value, oldValue, oldValue+1) != true) {
            oldValue = value;
        }
        return oldValue;
    }
}

多个线程修改同一个原子类也可以保障线程安全：

public class Test {
    private static AtomicInteger count = new AtomicInteger(0);
 
    public static void main(String[] args) throws InterruptedException {
        Thread t1 = new Thread(()->{
            for (int i = 0; i < 100; i++) {
                //相当于cout++
                count.getAndIncrement();
                //count--：count.getAndDecrement()
            }
        });
        Thread t2 = new Thread(()->{
            for (int i = 0; i < 100; i++) {
                //相当于++count
                count.incrementAndGet();
                //--count：count.DecrementAndGet()
            }
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(count);
    }
}

运行结果不会出现线程安全问题：

♫CAS实现自旋锁

自旋锁需要不断地尝试获取锁，直到获取锁为止，这与CAS的比较赋值操作类似，故通过CAS可以比较方便地实现一个自旋锁。

下面是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;
   }
}

♫CAS的ABA问题

 CAS是通过判断旧预期值与原数据是否相等来判断原数据是否被修改，可是只要值相同就一定没被改过吗？当一个值从A变成B再变成A时，如果在这个时间间隔内，有另外一个线程对这个值进行了改变并且恰好从A变成了另外一个值C，那么CAS操作会误认为这个值没有被修改过，从而可能导致并发异常，这就是CAS的ABA问题。

虽然大部分情况下，被修改后的值与修改前的值相同不会引发问题，但在极端情况下：

张三有100存款. 张三想从 ATM 取50块钱，而ATM机卡了一下，导致张三按了两次取款按钮，取款机就创建了两个线程并发的来执行 -50操作。一般情况下，线程1执行扣款成功，存款被改成50后，轮到线程2 执行了，发现当前存款为50，和之前读到的100不相同, 执行失败，不会出现问题。但若在线程2执行前，李四恰巧给张三转了50，此时轮到线程2执行时，发现当前存款和之前读到存款相同，就会再扣款一次，此时就出现问题了。

为了避免ABA问题，Java提供了AtomicStampedReference类，它在进行CAS操作时，除了比较当前值是否相等之外，还比较当前的版本号是否相等。如果版本号不同，则说明这个值已经被修改过，CAS操作失败。因此，AtomicStampedReference类可以有效地解决ABA问题。