手写Lock不可重入的公平锁_lock不可重入锁

一、前言

Jdk的锁常见有两种：synchronized关键字和Lock接口，
Lock接口，最常用可重入锁ReentrantLock，底层实现是AQS+CAS+LockSupport。
这里简单手写一把不可重入的公平Lock锁。

1.1、AQS

ReentrantLock中的Sync成员变量，继承自抽象类AbstractQueuedSynchronizer，即AQS抽象队列同步器，它里面有个Node双向链表，通过这个链表可以实现公平锁和非公平锁的机制。

公平锁和非公平锁：
公平锁：就是比较公平，根据请求锁的顺序排列，先来请求的就先获取锁，后来获取锁的就最后获取到，采用队列存放，类似于吃饭排队，先到先得。
非公平锁：不是根据请求顺序排列，而是通过争抢的方式获取锁。
非公平锁比公平锁的效率高，synchronized是非公平锁，ReentrantLock(true)是公平锁，ReentrantLock(false)是非公平锁，底层基于AQS实现。

除了Node双向链表外，AQS的原理还在于volatile变量status，用来表示锁的状态，0代表没有被线程持有，1代表已经被线程持有，大于1代表已经被线程持有且已重入。

锁的可重入性：
在同一个线程中，锁可以不断传递，可以直接读取，不用再获取锁。synchronized、Lock、AQS。

AQS的应用比较多，除了ReentrantLock外，JUC下的一些工具类，内部都是基于它进一步封装实现的，比如信号量Semaphore和计数器CountDownLatch等。

1.1.1、信号量Semaphore

底层AQS。它维护了一个指定数量的许可证permit，有多少资源需要限制就维护多少许可证，假如这里有N个资源，那就对应于N个许可证，同一时刻最多也只能有N个线程访问。
一个线程获取许可证调用acquire()方法，用完了释放资源就调用release()方法。
信号量Semaphore一般常用于接口限流等，限制可以访问某些资源的线程数目。
对应到日常生活中的限流进公园，最多同时只允许一定数量的游客进入。

public class TestSemaphore {

    /**
     * 10个人要拿着票据进公园，公园同时最多只允许5个
     */
    public static void main(String[] args) {
        Semaphore semaphore = new Semaphore(5); // AQS.state=5
        for (int i = 0; i < 10; i++) {
            int finalI = i;
            new Thread(() -> {
                try {
                    // 获取许可证或票据
                    semaphore.acquire(); // AQS.state-1直到等于0（所有许可证或票据都发完了）才不可以走下面的逻辑
                    System.out.println(Thread.currentThread().getName() + " " + finalI);
                    // 逛完了公园出来归还许可证
                    semaphore.release(); // AQS.state+1，一直继续维持阈值5
                } catch (InterruptedException e) {
                }
            }).start();
        }
    }

    public static void main0(String[] args) {
        Semaphore semaphore = new Semaphore(5); // AQS.state=5
        for (int i = 0; i < 10; i++) {
            int finalI = i;
            new Thread(() -> {
                try {
                    // 获取许可证或票据
                    semaphore.acquire(); // AQS.state-1直到等于0（所有许可证或票据都发完了）才不可以走下面的逻辑
                    System.out.println(Thread.currentThread().getName() + " " + finalI);
                } catch (InterruptedException e) {
                }
            }).start();
        }
    }
}
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

1.1.2、计数器CountDownLatch

底层AQS。等待state直到等于0，才唤醒正在等待的线程。
允许其他线程等待，直到最后释放锁，所有线程一起执行加锁后的代码。和join()类似。举例：发令枪只要一响，所有运动员线程同时出发。

public class TestCountDownLatch {

    public static void main(String[] args) {
        int size = 5;
        CountDownLatch latch = new CountDownLatch(size); // AQS的初始状态值state=5
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                System.out.println(Thread.currentThread().getName() + " ready!");
                try {
                    latch.await(); // 直到AQS的状态值state=0，所有线程一起唤醒
                    Thread.sleep(1000l);
                } catch (InterruptedException e) {
                }
                System.out.println(Thread.currentThread().getName() + " run!");
            }).start();
            latch.countDown(); // AQS的状态值state每次-1
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.2、CAS

CAS（Compare And Swap）无锁机制。没有获取到锁的线程不会阻塞，通过循环控制一直不断的获取锁。
CAS是通过硬件指令保证其原子性。原子类AtomicInteger、AtomicBoolean等都是通过CAS实现。
CAS有3个变量，V（Value内存值）、E（Expect期望值）、N（New新值），当内存值V等于期望值E，则原子操作将新值N赋到内存值V上，即V.compareAndSet(E, N)。
优点：自旋锁实现简单，没有线程阻塞，效率高；
缺点：存在ABA问题，可通过版本号机制处理；且一般通过死循环控制，可能消耗cpu资源高，需要控制循环次数避免cpu飙高。

1.3、LockSupport

JUC下locks包下对锁的支持类LockSupport。
主要用来控制当前线程阻塞：

LockSupport.park();
1

以及指定线程的唤醒：

LockSupport.unpark(thread1);
1

二、手写实现

接下来简单实现一个不可重入的公平锁，主要用到三个变量，

• lockStatus，原子类整数，用来获取和释放CAS锁
• lockThread，当前获取锁成功的线程
• deque，获取锁失败的线程双向链表

基本思路：
获取锁，即CAS操作lockStatus值由0变为1；
释放锁，即CAS操作lockStatus值由1再变为0；
因为不可重入，所以不考虑大于1的情况。

2.1、获取释放锁的细节步骤

1. T0、T1、T2同时尝试获取锁，假设T0获取到了锁（将lockStatus从0变为1，将lockThread设置为自身T0），则T1和T2会被阻塞，依次加入deque，等待被唤醒；
2. T0执行完业务加锁代码块，准备释放锁（将lockStatus从1变为0，将lockThread设置为null），从deque中取出最前面一个线程元素，假设为T2，则T2被唤醒，T2获取到锁（同样将lockStatus从0变为1，将lockThread设置为自身T2，T2将自身移出deque），此时deque中只剩一个T1，等待被唤醒；
3. T2执行完业务加锁代码块，也准备释放锁（将lockStatus从1变为0，将lockThread设置为null），从deque中取出最前面一个线程元素，只有一个T1了，则T1终于被唤醒，T1获取到锁（同样将lockStatus从0变为1，将lockThread设置为自身T1，T1将自身移出deque），此时所有线程都并发安全地加锁释放了锁；
4. 若要改造为非公平锁，则可以唤醒deque中所有的线程，而不是像上面公平锁一样，依次唤醒下一个最先的线程；
5. 若要改造为可重入锁，则可以控制lockStatus的值，不限于1，大于1代表重入次数。

2.2、代码实现

实现如下：

public class MyLock {

    private volatile AtomicInteger lockStatus = new AtomicInteger(0);
    private Thread lockThread; // 当前获取锁成功的线程
    private ConcurrentLinkedDeque<Thread> deque = new ConcurrentLinkedDeque<>(); // 获取锁失败的线程双向链表

    /**
     * 获取锁
     */
    public void lock() {
        acquire();
    }

    public boolean acquire() {
        for (;;) { // 自旋获取锁
            System.out.println("线程" + Thread.currentThread().getName() + "进入自旋！");
            if (compareAndSetStatus(0, 1)) {
                // 获取锁成功，设置thread为自身，唤醒自己线程之前的阻塞状态，还要从deque中移除自身
                lockThread = Thread.currentThread();
                removeSelfFromDeque();
                return true;
            }
            // 获取锁失败：放进双向链表，并阻塞当前线程
            deque.add(Thread.currentThread());
            System.out.println("线程" + Thread.currentThread().getName() + "即将阻塞！");
            LockSupport.park(); // 若park后返回false且没有循环自旋，T2被阻塞则代码会卡在这里，直到T1.unlock()中unpark(T2)才会继续往下走，但会返回false
            System.out.println("线程" + Thread.currentThread().getName() + "刚才被阻塞过，现在唤醒了！");
        }
    }

    public boolean compareAndSetStatus(int expect, int update) {
        return lockStatus.compareAndSet(expect, update);
    }

    public void removeSelfFromDeque() {
        if (deque.contains(Thread.currentThread())) {
            Iterator<Thread> iterator = deque.iterator();
            while (iterator.hasNext()) {
                if (iterator.next().equals(Thread.currentThread())) {
                    deque.remove(Thread.currentThread());
                    System.out.println("线程" + Thread.currentThread().getName() + "这次已被前一个唤醒，现已获取到了锁，被移出deque！");
                }
            }
        }
    }

    /**
     * 释放锁
     */
    public boolean unlock() {
        // 公平锁：唤醒链表的head线程；非公平锁则需要将waitDeque的每个线程unpark唤醒
        if (lockThread == Thread.currentThread()) {
            if (compareAndSetStatus(1, 0)) {
                // 可以释放锁，则还需要置空lockThread，且CAS操作还原status
                lockThread = null;
                Thread first = deque.peekFirst();
                if (first == null) return true;
                System.out.println("线程" + first.getName() + "即将唤醒！");
                LockSupport.unpark(first);
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        MyLock myLock = new MyLock();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Runnable runnable = () -> {
            try {
                Thread thread = Thread.currentThread();
                System.out.println(thread.getName() + " start at " + simpleDateFormat.format(new Date()));
                myLock.lock();
                System.out.println(thread.getName() + "运行加锁代码段");
                Thread.sleep(3000l);
                System.out.println(thread.getName() + " end at " + simpleDateFormat.format(new Date()));
            } catch (InterruptedException e) {
            } finally {
                myLock.unlock();
            }
        };
        Thread t1 = new Thread(runnable);
        Thread t2 = new Thread(runnable);
        Thread t3 = new Thread(runnable);
        t1.start();
        t2.start();
        t3.start();
    }
}
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

执行结果：

Thread-0 start at 2022-03-11 23:45:02
线程Thread-0进入自旋！
Thread-2 start at 2022-03-11 23:45:02
线程Thread-2进入自旋！
Thread-1 start at 2022-03-11 23:45:02
线程Thread-1进入自旋！
线程Thread-2即将阻塞！
Thread-0运行加锁代码段
线程Thread-1即将阻塞！
Thread-0 end at 2022-03-11 23:45:05
线程Thread-2即将唤醒！
线程Thread-2刚才被阻塞过，现在唤醒了！
线程Thread-2进入自旋！
线程Thread-2这次已被前一个唤醒，现已获取到了锁，被移出deque！
Thread-2运行加锁代码段
Thread-2 end at 2022-03-11 23:45:08
线程Thread-1即将唤醒！
线程Thread-1刚才被阻塞过，现在唤醒了！
线程Thread-1进入自旋！
线程Thread-1这次已被前一个唤醒，现已获取到了锁，被移出deque！
Thread-1运行加锁代码段
Thread-1 end at 2022-03-11 23:45:11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22