AQS源码探究_01 手写一个简化的ReentrantLock可重入锁

墨蓝 2023-01-18 06:46 124阅读 0赞

> 文章参考：[小刘老师的源码课][Link 1]

### 完整代码 ###

**MiniLock**：

/** * @author csp * @date 2021-05-01 */
    public interface MiniLock { 
        /** * 加锁 */
        void lock();
    
        /** * 释放锁 */
        void unlock();
    }

**MiniReentrantLock**：

/** * @author csp * @date 2021-05-01 * MiniReentrantLock 是一个独占锁、公平锁、可重入锁 */
    public class MiniReentrantLock implements MiniLock { 
        /** * 加锁的状态：=0 表示未加锁状态，>0 表示加锁状态 * 锁的是什么？ -> 锁的是线程资源 */
        private volatile int state;
    
        /** * 当前独占该锁的线程： * 什么是独占模式？ * 同一时刻，只能有一个线程可以持有该锁，其他线程，在未获取到锁时，会被阻塞 */
        private Thread exclusiveOwnerThread;
    
        /** * 维护阻塞队列需要的2个引用： * 1.head 指向队列头部的节点 -> head节点对应的线程，就是当前占用锁的线程！ * 2.tail 指向队列尾部的节点 */
        /** * 队列头部 */
        private Node head;
        /** * 队列尾部 */
        private Node tail;
    
        /** * 阻塞的线程被封装成Node节点，然后放入FIFO队列 */
        static final class Node { 
            // 前置节点引用
            Node prev;
            // 后置节点引用
            Node next;
            // 封装的线程
            Thread thread;
    
            public Node() { 
            }
    
            public Node(Thread thread) { 
                this.thread = thread;
            }
    
            public Node(Node prev, Node next, Thread thread) { 
                this.prev = prev;
                this.next = next;
                this.thread = thread;
            }
        }
    
        /** * 获取锁： * 假设当前锁被占用，则会阻塞调用线程，知道抢占到锁为止 * 模拟公平锁：公平锁讲究线程的先来后到！ * <p> * lock加锁的过程： * 情景1：当线程执行时，当前state == 0，则该线程刚好可以直接抢到锁 * 情景2：当线程执行时，当前state > 0，这时候就需要将当前线程入队 */
        @Override
        public void lock() { 
            // 令当前线程竞争资源
            // 第1次获取到锁时，将 state = 1
            // 第n次获取到锁时，将 state = n
            acquire(1);
        }
    
        /** * 当前线程竞争资源的方法； * 1.尝试获取锁，获取成功，则占用锁，并返回 * 2.尝试获取锁，获取失败，则阻塞当前线程 * * @param arg */
        private void acquire(int arg) { 
            // 尝试获取锁失败
            if (!tryAcquire(arg)) { 
                // 更复杂的逻辑来了~
                // 将当前线程添加到阻塞队列
                Node node = addWaiter();
                // 入队后，令当前线程不断去竞争资源，直到成功获取锁才停止自旋
                acquireQueued(node, arg);
            }
    
            // 尝试获取锁成功，则当前独占锁的线程exclusiveOwnerThread以及相关属性都在tryAcquire方法中执行了~
        }
    
        /** * 尝试抢占锁失败时，需要做些什么呢？ * 1.将当前线程封装成node，加入到阻塞队列 * 2.将当前线程park掉，使线程处于挂起状态，等待被唤醒 * * 那么，当唤醒后需要做什么呢？ * 1.检查当前node节点是否为 head.next节点 * (head.next节点是拥有抢占权限的线程，其他的node节点都没有抢占的权限) * 2.抢占 * 抢占成功：则将当前node设置为head，将老的head移出队列，接着返回到业务层面 * 抢占失败：则将当前线程继续park，等待被唤醒 * * =====> * 1.将当前线程添加到阻塞队列的逻辑 addWaiter() * 2.当前线程竞争资源的逻辑 acquireQueued() */
    
        /** * 将当前线程添加到阻塞队列: head为持有锁的节点 * addWaiter()执行完毕后，保证当前线程已经入队成功！ * * @return 发返回当前线程对应的Node节点 */
        private Node addWaiter() { 
            // 新建当前线程node节点
            Node newNode = new Node(Thread.currentThread());
    
            // 如何入队呢？
            // 1.找到newNode的前置节点 pred
            // 2.更新newNode.prev = pred
            // 3.CAS更新tail为 newNode
            // 4.更新 pred.next = newNode
    
            // 第1种情况，前置条件：队列已经有等待者node了(不为空)，当前node并不是第一个入队的node
            Node pred = tail;
            if (pred != null) { 
                newNode.prev = pred;
                // 如果条件成立，说明当前线程成功入队！
                if (compareAndSetTail(pred, newNode)) { 
                    pred.next = newNode;
                    return newNode;
                }
            }
    
            // 执行到这里有以下2种情况：
            // 1.tail == null 队列是空队列
            // 2.cas设置当前newNode 为 tail 时失败了，被其他线程抢先一步了
            // 自旋入队，只有入队成功才结束自旋：
            eng(newNode);
    
            return newNode;
        }
    
        /** * 令当前线程不断去竞争资源，直到成功获取锁才停止自旋 * * @param node * @param arg */
        private void acquireQueued(Node node, int arg) { 
            // 只有当前node成功获取到锁以后，才会跳出自旋：
            for (; ; ) { 
                // 什么情况下，当前node被唤醒之后可以尝试获取锁呢？
                // 只有一种情况：当前node是head的后继节点，才有这个权限(FIFO队列，先来后到的道理~)
                Node pred = node.prev;
                // head节点就是当前有权去持锁的节点
                if (pred == head /* 条件成立：说明当前node拥有抢占权限 */ && tryAcquire(arg) /* 尝试获取锁 */) { 
                    // 当进入if里面时，说明当前线程竞争锁成功了！
                    // 接下来需要做什么？
                    // 1.设置当前head为当前线程的node
                    // 2.协助原始head出队
                    setHead(node);
                    pred.next = null;// help GC
                    return;
                }
    
                // 如果没有持锁抢占权限，则当前线程挂起，继续等待...
                // park...线程挂起
                System.out.println("线程：" + Thread.currentThread().getName() + " 挂起！");
                LockSupport.park();
                System.out.println("线程：" + Thread.currentThread().getName() + " 唤醒！");
            }
        }
    
        /** * 自旋入队的方法，只有成功后才结束自旋： * 1.tail == null 队列是空队列 * 2.cas设置当前newNode 为tail 时失败了，被其他线程抢先一步了 */
        private void eng(Node node) { 
            // 自旋~
            for (; ; ) { 
                // 第1种情况：空队列 ===> 即，当前线程是第一个抢占锁失败的线程
                // 当前持有锁的线程(注：tryAcquire方法直接获取到锁的线程，在该方法逻辑中，并没有将持锁线程入队，
                // 而按理说阻塞队列的head节点就应该是当前持有锁的线程才对)并没有设置过任何 node，
                // 所以作为该线程的第一个后驱next，需要给它擦屁股（给持锁线程补一个node节点并设置为阻塞队列的head
                // head节点任何时候，都代表当前占用锁的线程）
                if (tail == null) { 
                    // 如果compareAndSetHead条件成立：说明当前线程给当前持有锁的线程，补充head操作成功了！
                    if (compareAndSetHead(new Node())) { 
                        // tail = head 表示当前队列只有一个元素，这里就表名当前持锁的线程被放入阻塞队列且为head了~
                        tail = head;
                        // 注意：并没有直接返回，还会继续自旋，下次再进入循环时阻塞队列已经不为空，且head为持锁线程节点了...
                    }
                } else { 
                    // 其他情况，说明：当前队列中已经有node了，这里是一个追加node的过程
    
                    // 如何入队呢？和 addWaiter方法入队逻辑一样~
                    // 1.找到newNode的前置节点 pred
                    // 2.更新newNode.prev = pred
                    // 3.CAS更新tail为 newNode
                    // 4.更新 pred.next = newNode
    
                    // 前置条件：队列已经有等待者node了(不为空)，当前node并不是第一个入队的node
                    Node pred = tail;
                    if (pred != null) { 
                        node.prev = pred;
                        // 如果条件成立，说明当前线程成功入队！
                        if (compareAndSetTail(pred, node)) { 
                            pred.next = node;
                            // 注意：入队成功，一定要return结束，无限for循环~
                            return;
                        }
                    }
                }
            }
        }
    
        /** * 尝试获取锁的方法，不会阻塞线程 * * @param arg * @return true -> 尝试获取锁成功 | false -> 尝试获取锁失败 */
        private boolean tryAcquire(int arg) { 
            // 如果当前state加锁状态等于0
            if (state == 0) { 
                // 条件1：!hasQueuePredecessor()：表示如果当前线程前面没有等待的线程(保证公平)
                // 条件2：compareAndSetState(0,arg)：使用CAS的方式对state进行修改操作执行成功
                // 如果条件1、2均成立，则说明当前线程抢锁成功！
                if (!hasQueuePredecessor() && compareAndSetState(0, arg)) { 
                    // 抢锁成功：
                    // 1.需要把exclusiveOwnerThread 设置为当前进入if块中的线程
                    this.exclusiveOwnerThread = Thread.currentThread();
                    // 尝试获取锁成功
                    return true;
                }
                // 如果当前线程就是持有锁的线程，且state > 0
            } else if (Thread.currentThread() == this.exclusiveOwnerThread) { 
                // 该if判断中存在并发么？ 不存在 -> 因为只有当前加锁的线程，才有权限修改state
    
                // 获取当前线程的加锁状态
                int s = getState();
                s = s + arg;
    
                // 越界判断...（略），在ReentrantLock中这里肯定要做越界判断的
    
                // 把s赋给state，更新加锁状态
                this.state = s;
    
                // 尝试获取锁成功
                return true;
            }
            // 尝试获取锁失败：
            // 1.CAS加锁失败 且 当前线程前面有等待的线程
            // 2.state > 0 且 当前线程不是占用锁的线程
            return false;
        }
    
        /** * 方法调用链： * lock -> acquire -> tryAcquire -> hasQueuedPredecessor (ps：state值为0 时，即当前Lock属于无主状态..) */
    
        /** * 判断FIFO队列是否为空： * * @return true -> 表示当前线程前面有等待者线程 | false -> 表示当前线程前面没有等待者线程 */
        private boolean hasQueuePredecessor() { 
            Node h = head;
            Node t = tail;
            Node s;
    
            // 什么时候返回false呢？
            // 1.当前队列为空
            // 2.当前线程为head.next节点线程，head.next在任何时候都有权限去争取lock
    
            // 条件1：h != t
            // 成立：说明当前队列已经有node了
            // 不成立：1. h == t == null 2. h == t == head 第一个获取锁失败的线程，会为当前持有锁的线程 补充创建一个 head 节点。
    
            // 条件2：((s = h.next) == null || s.thread != Thread.currentThread())
            // 排除几种情况:
            // 条件2.1：(s = h.next) == null
            // 极端情况：第一个获取锁失败的线程，会为 持锁线程 补充创建 head ，然后再自旋入队， 1. cas tail() 成功了，2. pred【head】.next = node;
            // 其实想表达的就是：已经有head.next节点了，其它线程再来这时 需要返回 true
            return h != t && ((s = h.next) == null || s.thread != Thread.currentThread());
        }
    
        /** * 释放锁 */
        @Override
        public void unlock() { 
            // 释放锁
            release(1);
        }
    
        /** * 释放锁的方法 * * @param arg */
        private void release(int arg) { 
            // tryRelease条件成立：说明线程已经完全释放锁了
            // 需要干点啥呢？
            // 阻塞队列里面还有好几个睡觉的线程呢？ 是不是 应该喊醒一个线程呢？
            if (tryRelease(arg)) { 
                // 获取head节点
                Node head = this.head;
    
                // 你得知道，有没有等待者？
                // 如果head.next == null 说明没有等待者，
                // 如果head.next != null 说明有等待者，去唤醒该等待者线程
                if (head.next != null) { 
                    // 公平锁，就是唤醒head.next节点
                    unparkSuccessor(head);
                }
            }
        }
    
        /** * 唤醒线程节点 * * @param node */
        private void unparkSuccessor(Node node) { 
            // head之后的节点
            Node s = node.next;
            if (s != null && s.thread != null) { 
                // 等待者线程唤醒
                LockSupport.unpark(s.thread);
            }
        }
    
        /** * 实际上的完全释放锁的方法 * 完全释放锁成功，则返回true|否则，说明当前state > 0 ，返回false. */
        private boolean tryRelease(int arg) { 
            int c = getState() - arg;
    
            if (getExclusiveOwnerThread() != Thread.currentThread()) { 
                throw new RuntimeException("No! You must getLock!");
            }
            // 如果执行到这里？存在并发么？ 只有一个线程 ExclusiveOwnerThread 会来到这里。
    
            // 条件成立：说明当前线程持有的lock锁 已经完全释放了..
            if (c == 0) { 
                // 需要做什么呢？
                // 1.ExclusiveOwnerThread 置为null
                // 2.设置 state == 0
                this.exclusiveOwnerThread = null;
                this.state = c;
                return true;
            }
    
            // state不等于0，不能释放锁，返回false
            this.state = c;
            return false;
        }
    
        private void setHead(Node node) { 
            this.head = node;
            // 为什么thread设置为null？ 因为当前node已经是获取锁成功的线程了
            node.thread = null;
            node.prev = null;
        }
    
        public int getState() { 
            return state;
        }
    
        public Thread getExclusiveOwnerThread() { 
            return exclusiveOwnerThread;
        }
    
        public Node getHead() { 
            return head;
        }
    
        public Node getTail() { 
            return tail;
        }
    
        /** * 基于CAS，得到state、head、tail属性的setter方法 */
        private static final Unsafe unsafe;
        private static final long stateOffset;
        private static final long headOffset;
        private static final long tailOffset;
    
        static { 
            try { 
                Field f = Unsafe.class.getDeclaredField("theUnsafe");
                f.setAccessible(true);
                unsafe = (Unsafe) f.get(null);
    
                stateOffset = unsafe.objectFieldOffset
                        (MiniReentrantLock.class.getDeclaredField("state"));
                headOffset = unsafe.objectFieldOffset
                        (MiniReentrantLock.class.getDeclaredField("head"));
                tailOffset = unsafe.objectFieldOffset
                        (MiniReentrantLock.class.getDeclaredField("tail"));
    
            } catch (Exception ex) { 
                throw new Error(ex);
            }
        }
    
        private final boolean compareAndSetHead(Node update) { 
            return unsafe.compareAndSwapObject(this, headOffset, null, update);
        }
    
        private final boolean compareAndSetTail(Node expect, Node update) { 
            return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
        }
    
        protected final boolean compareAndSetState(int expect, int update) { 
            return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
        }
    }

[Link 1]: https://space.bilibili.com/457326371