【HBZ分享】AQS + CAS +LockSupport 实现ReentrantLock的原理

根据ReentrantLock手写一把锁源码

手写源码gitee地址: https://gitee.com/huang_bao_se/write_aqs_cas_locksupport

CAS原理

1. cas控制着3个值，分别是【内存地址V】【预期原值A】【改后新值B】
2. 进行更改内存值时，会拿着【内存原值】与【期待原值】进行对比，如果内存地址V中保存的值和预期原值A相等，则处理器会自动将B的值替换到V上
3. 如果V != A，则会更新失败。可以认为期间有人把V改了。一旦更新失败，会进行自旋，重新获取V的值，并重新计算B的新值，然后V继续和A继续比较，如果相等，就把B更新到V上
4. AtomicInteger，AtomicXXX，等原子类底层就是CAS实现，一定程度比Synchonized好，因为后者属于悲观锁
5. 缺点：当过多线程自旋，会导致CPU消耗，这种情况可能就比Synchonized差了。即很多线程情况下，Synchonized很有可能比CAS好

AQS加锁原理

1. 第一次加锁，会获取锁，state加1。
2. 此时线程B来了，获取锁失败了，他就会进入阻塞队列排队。然后线程C也来了，他也会获取失败， 他会插入到B的后面排队。
3. 阻塞队列是一个双向链表，当线程A的state减到0了，此时会遍历这个阻塞队列(注意，是遍历，不是直接去下一个节点的线程)。那从里他最近的那个符合要求的节点获取线程来加锁。这块注意，如果B线程还活着，那就会拿B节点，之所以遍历而不是取下一个节点，就是防止B这个线程可能停止或者死了，如果停止了，那就会拿C。总之大体是先进先出，但线程一定要正常情况下

AQS解锁解锁

1. 解锁首先state会减1， 如果state不为0，依然不会触发队列中的线程激活。
2. 如果state为0了，锁彻底释放，然后遍历阻塞队列的NODE，取出符合要求离他最近的那个节点保存的线程来加锁。

ReentrantLock原理（非公平锁–默认–性能高于公平锁）

1. ReentrantLock在接到一个新线程时，由于是非公平锁，所以直接会直接利用CAS进行判断加锁
2. 当预期原值A = 0， 新值B = 1， 如果加锁成功，则直接返回true即可。并把state = 1，记录该线程重入次数
3. 如果CAS返回false，说明已经有线程拿到了锁，此时判断【当前线程】与【加锁线程】是否时同一个线程，如果是，则state++, 然后返回true
4. 如果CAS返回false，并且【当前线程】不等于【加锁线程】，则当前线程会进入阻塞状态，并且会装入【链表队列】中
5. 多个线程来，会按照来的时间顺序，依次加入到【链表队列】中
6. 解锁时，会把state–,如果state = 0， 表示锁释放，如果state-- 后不为0，则说明只是解锁了一层重入锁，此时锁并不能释放，链表队列中的线程依然不会唤醒
7. 当state = 0时，，由于是非公平锁，会唤醒等待队列中所有的线程，所有的线程会进行抢锁，没抢到的继续回到队列，以此类推知道队列为空

ReentrantLock原理（公平锁）

1. ReentrantLock在接到一个新线程时，由于是公平锁，所以先判断state = 0，而不会直接利用CAS加锁
2. 如果确实为0， 则表示该锁此时未被任意线程获取，那么会通过CAS进行加锁，会加锁成功，拿到锁，然后state = 1;
3. 如果state != 0, 会判断【当前线程】和【加锁线程】是否相等，如果相等，则state++, 否则进入等待队列
4. 多个线程来，会按照来的时间顺序，依次加入到【链表队列】中
5. 解锁时，会把state–,如果state = 0， 表示锁释放，如果state-- 后不为0，则说明只是解锁了一层重入锁，此时锁并不能释放，链表队列中的线程依然不会唤醒
6. 当state = 0时，，由于是公平锁，所以只会唤醒等待队列中第一个线程，此时第一个线程拿到锁，同样操作以此类推，直到队列为空

手写ReentrantLock源码

/**
 * 手写AQS
 */
public class MysLockAQS {

    /**
     * 是否加锁标识，锁状态(0:锁存在；1: 锁已给线程)
     */
    private AtomicInteger lockState = new AtomicInteger(0);

    /**
     * 获取锁的对象
     */
    private Thread thread = null;

    /**
     * 锁类型(true: 公平锁；false: 非公平锁)
     */
    private boolean lockType = false;

    /**
     * 重入锁次数
     */
    private Integer state = 0;

    /**
     * 没有获取锁得线程，保存到该链表
     */
    private ConcurrentLinkedDeque<Thread> concurrentLinkedDeque = new ConcurrentLinkedDeque<Thread>();


    public MysLockAQS(){

    }

    public MysLockAQS(boolean lockType){
        this.lockType = lockType;
    }

    /**
     * 加锁
     * @return
     */
    public boolean lock(){

        // 这里死循环指的是，被阻塞得线程被唤醒后要不断地重试
        for (;;){
            // 通过CAS尝试加锁
            if(acquire()){
                // 加锁成功，thread赋予当前线程
                thread = Thread.currentThread();
                // state赋值1，表示加锁1次
                state = 1;
                // 加锁成功，直接退出循环
                return true;
            }else{
                // 加锁失败，判断是不是当前线程
                if(thread == Thread.currentThread()){
                    // 是当前线程，则依然放行，并且state+1
                    state++;
                    return true;
                }
            }

            // 加锁失败，把该线程加入链表保存
            concurrentLinkedDeque.add(Thread.currentThread());
            // 阻塞当前线程，被unPark唤醒后，继续从这里执行，即进入下一次循环
            LockSupport.park();
        }

    }

    /**
     * 解锁
     * @return
     */
    public boolean unLock(){
        // 判断当前是否有线程拿到锁
        if(thread == null){
            return false;
        }
        // 判断如果是当前线程
        if(thread == Thread.currentThread()){
            // 判断state是否为1
            if(state > 1){
                // 大于1，则说明有重入锁，需要state - 1, 但不能释放锁
                state--;
                return true;
            }
            // CAS执行解锁
            if(compareAndSetState(1, 0)){
                // 解锁成功，判断是公平锁还是非公平锁
                if(lockType){
                    // 公平锁，则唤醒链表中第一个线程
                    Thread first = concurrentLinkedDeque.pollFirst();
                    // 唤醒该线程
                    LockSupport.unpark(first);
                }else{
                    // 非公平锁，循环唤醒链表所有线程，让他们自己抢占去
                    for(;;){
                        if(concurrentLinkedDeque.size() == 0){
                            System.out.println("队列已空");
                           break;
                        }
                        // 公平锁，则唤醒链表中第一个线程
                        Thread first = concurrentLinkedDeque.pollFirst();
                        // 唤醒该线程
                        LockSupport.unpark(first);
                    }

                }
            }
        }

        return false;
    }

    private boolean acquire(){
        if(compareAndSetState(0, 1)){
            return true;
        }
        return false;
    }
    /**
     * CAS
     * @param expect   期待原值
     * @param update   更改新值
     * @return
     */
    private boolean compareAndSetState(int expect, int update){
        return lockState.compareAndSet(expect, update);
    }

调用测试：
public class Test {

    private static MysLockAQS mysLockAQS = new MysLockAQS(true);
    public static void main(String[] args) throws InterruptedException {
        mysLockAQS.lock();
        System.out.println("主线程加锁: " + Thread.currentThread().getName());
        for(int i = 0; i < 10; i++){
            // 开启10条子线程，进行公平锁与非公平锁校验
            new Thread(()->{
                System.out.println("start: " + Thread.currentThread().getName());
                mysLockAQS.lock();
                System.out.println("end: " + Thread.currentThread().getName());
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                mysLockAQS.unLock();
            }).start();
        }

//        System.out.println("主线程解锁: " + Thread.currentThread().getName());
        test2();
        mysLockAQS.unLock();

    }

    /**
     * 重入锁测试
     * @throws InterruptedException
     */
    public static void test2() throws InterruptedException {

        mysLockAQS.lock();
        System.out.println("主线程2次加锁: " + Thread.currentThread().getName());
        Thread.sleep(200);

        test3();
        mysLockAQS.unLock();
    }

    /**
     * 重入锁测试
     * @throws InterruptedException
     */
    public static void test3() throws InterruptedException {

        mysLockAQS.lock();
        System.out.println("主线程3次加锁: " + Thread.currentThread().getName());
        Thread.sleep(300);
        mysLockAQS.unLock();
    }

}