ReentrantLock源码分析之手写mini版本的ReentrantLock

ReentrantLock作为Lock的实现类,在JUC中扮演者十分重要的角色.学习Java的最好方式就是深入源码.
通过对ReentrantLock的学习,现在试着手写一遍ReentrantLock. PS:这里仅尝试实现简单的mini版本.重要的是体会 其中的思想…

因为Lock接口中很多方法要实现, 我就自己手写一个极简版本的Lock,用来实现一些简单的方法.

public interface Lock {
    void lock();
    void unlock();
}
1
2
3
4

这里仅仅只有 lock和unlock 上锁和解锁两个方法. 简单版本的 ReentrantLock中也主要围绕这两个方法展开.

下面是必要的一些 属性,我都加了注释,方便理解.
这里实现的是独占模式,然后 因为公平锁比非公平锁稍微麻烦一些,所以选择实现公平锁
因为这里用到了阻塞队列.画个图来理解一下

public class MiniReentrantLock implements Lock {
    /**
     * status 作为是否上锁的标志位.
     * status == 0 表示未上锁, status > 0 表示已上锁
     */
    private int status;
    /**
     * exclusiveOwnerThread==>表示 独占锁的线程
     */
    private Thread exclusiveOwnerThread;
    /**
     * head ==>表示 阻塞队列中的头节点
     * tail ==> 表示 阻塞队列的尾节点
     */
    private Node head;
    private Node tail;

    /**
     * 一个内部类 ,作为容器,用来存放阻塞队列中的 线程
     */
    private static final class Node {
        //当前节点的前节点
        Node prex;
        //当前节点的后节点
        Node next;
        //当前节点的线程
        Thread thread;

        public Node() {
        }
        //方便用来用线程创建节点.
        public Node(Thread thread) {
            this.thread = thread;
        }
    }

    @Override
    public void lock() {

    }

    @Override
    public void unlock() {

    }
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46

大体框架已经搭起来了.下面来具体实现 lock方法和unlock 方法.
.首先说一下lock 的思路
我们使用这个类的 lock 方法来进行加锁. 那么 如何加锁呢,就是保证同一时刻,只有一个线程可以拿到我们的一个标识(status),
这样我们可以使用CAS方式来确保只有一个线程能够获取,因为我们这里是重入锁,所以可能会同时拿到好几个锁,这样,我们只要确保status在每次拿到锁的时候进行+1(或者+其他的数字都可以,只要保证作为标识的作用就可以.),这样我们可以设计一个获取锁方法.在lock方法中调用这个方法,来进行操作.具体实现如下:

   @Override
    public void lock() {
        acquire(1);
    }

    /**
     *  获取锁的方法==> 多个线程进入这个方法来获取锁
     *  如果获取锁成功的话,我们就可以直接进入线程的逻辑进行操作.
     *  如果获取锁失败的话,就需要进入阻塞队列进行排队.
     * @param i  表示每次获取一个锁,实际的标识status的增量
     */
    private void acquire(int i) {
        //如果尝试获取锁失败. 将线程加入到阻塞队列中.
        if(!tryAcquire(i)){
            Node node = addWorker();
            acquireQueue(node,i);
        }
        //没有进入到if代码块中,表示获取锁成功.就直接结束方法了
    }

    /**
     *  将传入的节点加入到阻塞队列中
     * @param node  传入的节点
     * @param i  锁的标识
     */
    private void acquireQueue(Node node, int i) {
    }

    /**
     * 线程获取锁失败后,将之封装成一个Node节点,方便入队
     * @return  封装的node节点
     */
    private Node addWorker() {
        return null;
    }
	/**
     * 尝试获取锁的方法
     * @param i  锁的标识
     * @return true 表示获取锁成功, false 表示失败
     */
    private boolean tryAcquire(int i) {
        return false;
    }
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
34
35
36
37
38
39
40
41
42
43

下面来 根据思路 一个个方法实现…首先先来实现tryAcquire()
首先分析一下,怎么才能获取到锁呢.
1.当前没有其他线程来获取锁,也就是阻塞队列中也没有,只有一个线程,就可以直接获取到锁
2.之前的线程已经结束任务,当前尝试获取锁的队列在阻塞队列的首位, 可以拥有去获取锁的权限.
当然这里都有前提,就是当前锁的状态是0,也就是 锁是未被其他线程持有的.
因为要用CAS方式来给锁的标识来+1,那么就需要引入Unsafe类相关API

  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) {
        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }
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

将判断当前线程之前是否有等待的线程 的代码提取成方法:

 /**
     * 判断 当前线程前面是否有等待的线程
     *
     * @return true 表示 当前线程前面有等待的线程  false 表示当前线程前面没有等待的线程,可以去尝试获取锁
     */
    private boolean hasQueuedPredecessor() {
        //h =>头节点  t=>尾节点 n=>head.next
        Node h = head;
        Node t = tail;
        Node n ;
        /**
         * 怎么判断呢?
         * 1.队列如果没有初始化的话,那么肯定当前线程前面没有 等待队列了!  ==> h == t == null ==>true: 无等待队列  ==> 返回false
         *                                                                           false: 有等待队列 ==>返回true
         * 2.因为第一个没有任何竞争拿到锁的线程是没进行任何操作的,也就是说他并没有初始化阻塞队列,第二个线程来竞争锁的时候,就会初始化阻塞队列,
         * 但是这个时候如果因为多线程进来竞争CAS 改变锁状态,导致第二个线程CAS失败,那么n 就是null
         * 这个时候,也要告诉其他线程,前面有人了...当然这是一个非常极端的情况
         * 3. 如果前面两个条件都成立了,那么就是 有了头节点,且头节点的next == n !=null
         * 来判断的这个节点 n 的线程 并不是当前的线程,返回 true ==> n.thread != Thread.currentThead()
         */
        return  h != t &&((n =head.next) == null || n.thread != Thread.currentThread());
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  /**
     * 尝试获取锁的方法
     *
     * @param i 锁的标识要增加的数值
     * @return true 表示获取锁成功, false 表示失败
     */
    private boolean tryAcquire(int i) {
        //先来判断,锁是否没有被其他线程持有!
        if (status == 0) {
            /**
             * 1.首先判断是不是等待队列的首位
             * 2.CAS方式给锁标识+1.也就是争抢锁
             */
            if (!hasQueuedPredecessor() && compareAndSetState(0, i)) {
                //进入if代码块里面之后,说明当前线程获取锁成功了!
                //那么我们就将当前线程,设置为 拥有锁的线程
                this.exclusiveOwnerThread = Thread.currentThread();
                return true;
            }
            //如果当前线程正好就是现在获取到锁的线程
            else if (this.exclusiveOwnerThread == Thread.currentThread()) {
                //那么就是重入锁!
                //需要更新锁的标识
                int c = getStatus();
                c += i;
                this.status = c;
                return true;
            }
        }
        //如果不满足上述条件.,也就是 
        // 1.锁的状态status >0 ,锁被占有了.
        // 2.CAS 抢锁没抢过别人~
        return false;
    }
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
34

那么回到 最初的acquire()方法中,此时我们完成了判断试图获取锁成功与否,获取锁失败之后,我们需要将失败的线程加入到阻塞队列中,然后

那么来实现具体方法:
addWorker():

    /**
     * 线程获取锁失败后,将之封装成一个Node节点,方便入队
     *
     * @return 封装的node节点
     */
    private Node addWorker() {
        //以当前线程创建一个node节点,因为是获取锁失败的,恶搞一下~loser
        Node loser = new Node(Thread.currentThread());
        //然后将之加入到阻塞队列中.
        //因为他是获取锁失败的,那么必定有成功的,那么他就需要入尾
        Node loserPrefix = tail;
        if(null != loserPrefix){
            //将loser 的前引用指向之前的尾
            loser.prefix = loserPrefix;
            //调用CAS方法,将当前线程入尾
            if(compareAndSetTail(tail,loser)){
             //成功入尾
                tail.next = loser;
                return loser;
            }
        }
        //上述条件不满足的话.
        //1. 队列就是空的!
        //2.CAS入尾的时候又被人截胡了..
        //这时候就需要再次尝试入尾~
        intoQueue(loser);
        return loser;
    }

    /**
     * 入尾操作,不成功不退出!
     * @param loser  之前没有入队成功的loser~
     */
    private void intoQueue(Node loser) {
        for (;;){
            //承上启下~上面有两种情况下来.1.队列是空的.2.CAS入尾失败
            if(tail == null){
                //说明队列是空的
                //就是之前是 第一个线程过来,他直接玩去了,没有初始化 阻塞队列..那么我们只能辛苦给他创建了!
                if(compareAndSetHead(new Node())){
                    tail = head;
                }
                //这个时候我们就初始化完了阻塞队列,,继续 尝试入队吧~
            }else{
                //说明队列不是空的,我们是因为CAS入尾失败才来的
                //1.先找到要入队的的位置的前面的节点..因为我们是加到最后面的
                Node front = tail;
                if (front != null){
                    //这里判断是为了防止我们在这里干这个的时候,其他线程把tail给弄成null了...
                    loser.prefix = front;
                    //继续CAS 入队吧,,这次要直到成功才可以
                    if(compareAndSetTail(tail,loser)){
                       tail.next =loser;
                       return;
                    }
                }
            }

        }
    }
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

acquireQueue()方法如下:

   /**
     * 将传入的节点加入到阻塞队列中
     *
     * @param node 传入的节点
     * @param i    锁的标识
     */
    private void acquireQueue(Node node, int i) {
        //因为我们已经在阻塞队列中了,那么久只能在这里自旋,直到拿到锁成功
        for (;;){
            //啥时候我们才能拿到锁呢,,,, 只有我们前面的线程都走了,我们成为head.next了
            //当前节点的前面节点
            Node n = node.prefix;
            if(n == head && tryAcquire(i)){
                //将当前线程的节点 设置成head
                setHead(node);
                //将原来的head节点的引用设置为null,防止内存泄漏
                n.next = null; 
                return;
            }
            //没满足条件你就搁这自旋吧,直到拿到锁~
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

lock 方法的逻辑就写完了…那么继续来解锁~
解锁其实就是释放锁嘛.把我们的锁的标识改为0 ,这样其他线程看到0了,就可以去获取锁了

释放锁的逻辑比较简单…我就写在一起了

 @Override
    public void unlock() {
        //这里写死了.就是1 因为之前加锁的时候 也是加1
        release(1);
    }

    /**
     * 释放锁,因为是重入锁,所以需要一层层的来
     */
    private void release(int i) {
        if (tryRelease(i)) {
            Node n = this.head;
            //如果阻塞队列里面有人等着呢
            if (n.next != null) {
                //唤醒他的后面的那个!
                unParkNext(head);
            }
        }
    }

    /**
     * 唤醒当前节点的下一个等待节点
     * @param node  当前节点
     */
    private void unParkNext(Node node) {
        Node n = node.next;
        if (n != null && n.thread != null){
            //说明n 确实是一个等待的节点
            //借用JUC提供的类去唤醒.
            LockSupport.unpark(n.thread);
        }

    }

    /**
     * 尝试 释放锁
     *
     * @param i 锁的标识的减值
     * @return true 表示释放成功 false 表示释放失败
     */
    private boolean tryRelease(int i) {
        if (getExclusiveOwnerThread() != Thread.currentThread()) {
            //如果当前线程不是持有所锁的线程.
            throw new RuntimeException("你没锁,释放啥呢");
        }
        //经过上述判断之后,只有持有锁的线程才能进来这里,就不存在并发安全问题了
        int c = getStatus() - i;
        if (c == 0) {
            //说明 已经彻底释放干净了
            this.exclusiveOwnerThread = null;
            this.status = 0;
            return true;
        }
        //没进去条件说明 还有锁没释放完.
        this.status = c;
        return false;
    }
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

以上~
这里万分感谢B站的暴躁小刘讲师.因为他的课才会让我更方便的理解JUC~