ReentrantLock实现原理

Java识堂

发布于 2019-08-13 10:12:39

4170

发布于 2019-08-13 10:12:39

文章被收录于专栏：Java识堂Java识堂

前言

建议和上一篇分享结合着看：深入理解AbstractQueuedSynchronizer

先举个例子，下面程序输出始终是5000，可以用ReentrantLock来保证线程安全

@ThreadSafe
public class CountTest {

    public static int count = 0;
    public static Lock lock = new ReentrantLock();

    public static void main(String[] args) {

        ExecutorService service = Executors.newCachedThreadPool();
        for (int i = 0; i < 5; i++) {
            service.execute(() -> {
                //加锁
                lock.lock();
                try {
                    for (int j = 0; j < 1000; j++) {
                        count++;
                    }
                } finally {
                    //释放锁
                    lock.unlock();
                }
            });
        }
        service.shutdown();
        try {
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("count = " + count);
    }
}

源码

基于jdk1.8.0_20，先看UML图

Lock接口中定义了对锁的各种操作

public interface Lock {

    //不响应中断的获取锁
    void lock();

    //响应中断的获取锁
    void lockInterruptibly() throws InterruptedException;

    //尝试非阻塞的获取锁，true为获取到锁，false为没有获取到锁
    boolean tryLock();

    //超时获取锁，以下情况会返回：时间内获取到了锁，时间内被中断，时间到了没有获取到锁
    boolean tryLock(long time, TimeUnit unit) throws InterruptedException;

    //释放锁
    void unlock();

    //创建一个condition
    Condition newCondition();
}

ReentrantLock在AQS基础上，又扩展出来非公平锁和公平锁，那么它现在有4种功能，各种操作分别在NonfairSync和FairSync这两个静态内部类中实现

响应中断的非公平锁
不响应中断的非公平锁
响应中断的公平锁
不响应中断的公平锁

AQS有一个state变量，在不同子类中有不同的含义，在ReentrantLock中表示锁的状态

status的值表示加锁的次数，无锁时值为0，第一次加锁将status设置为1，由于ReentrantLock是可重入锁，当持有锁的线程是当前线程时，即可加锁，加锁一次，将status的值加1
每解锁一次将status的个数减1，当stauts的值为0，其他线程可以获得锁

ReentrantLock只有一个成员变量Sync，Sync相当于一个代理类，具体的实现在子类中定义

private final Sync sync;

ReentrantLock类有两个构造函数，默认是非公平锁。当传入的参数是true时为公平锁，是false为非公平锁

public ReentrantLock() {
    sync = new NonfairSync();
}

public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

不响应中断的非公平锁

//ReentrantLock
public void lock() {
   sync.lock();
}

//NonfairSync
final void lock() {
   //这就是不公平的地方，上来直接通过CAS尝试将status的值从0设置为1
   if (compareAndSetState(0, 1))
       //设置成功则将持有锁的线程设置为当前线程
       setExclusiveOwnerThread(Thread.currentThread());
   else
       acquire(1);
}

//AbstractQueuedSynchronizer（这个方法已经在上一篇分享中分析了）
public final void acquire(int arg) {
   if (!tryAcquire(arg) &&
       acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
       selfInterrupt();
}

//NonfairSync（重写了AbstractQueuedSynchronizer的方法）
//尝试获取锁
protected final boolean tryAcquire(int acquires) {
   return nonfairTryAcquire(acquires);
}

//Sync
final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        //设置state的值
        setState(nextc);
        return true;
    }
    return false;
}

//AbstractQueuedSynchronizer（锁被当前线程持有，直接设置即可）
protected final void setState(int newState) {
    state = newState;
}

来个小插曲，尝试非阻塞的获取锁直接调用的就是nonfairTryAcquire方法

public boolean tryLock() {
   return sync.nonfairTryAcquire(1);
}

接着看释放锁，公平锁和非公平锁用的都是这个方法

//ReentrantLock
public void unlock() {
   sync.release(1);
}

//AbstractQueuedSynchronizer（上一篇分享已经分析）
public final boolean release(int arg) {
   if (tryRelease(arg)) {
       Node h = head;
       if (h != null && h.waitStatus != 0)
           unparkSuccessor(h);
       return true;
   }
   return false;
}

//Sync（重写了AbstractQueuedSynchronizer的方法）
//尝试释放锁
protected final boolean tryRelease(int releases) {
    //当前加锁的次数-释放的次数
    int c = getState() - releases;
    //当前线程不是持有锁的线程
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        //为true时表示已经释放锁了
        free = true;
        //设置持有锁的线程为null
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

不响应中断的公平锁

这几步都一样

//ReentrantLock
public void lock() {
    sync.lock();
}

//FairSync
final void lock() {
    acquire(1);
}

//AbstractQueuedSynchronizer
public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

从这开始不一样了

//FairSync
protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        //这就是公平的地方，线程是按照FIFO顺序来执行的
        if (!hasQueuedPredecessors() &&
            compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

//当前线程前面有等待线程，返回true
//当前线程位于队列的头部或者队列为空，返回false
public final boolean hasQueuedPredecessors() {
    //AQS内部的FIFO队列的头节点
    Node t = tail; // Read fields in reverse initialization order
    //尾节点
    Node h = head;
    Node s;
    return h != t &&
        ((s = h.next) == null || s.thread != Thread.currentThread());
}

如果head=tail，则表示FIFO队列为空，如刚开始head和tail都为null，返回false 如果head!=tail，并且head的next为空时，则FIFO队列不为空

有两种情况会导致h的next为空

当前线程进入hasQueuedPredecessors的同时，另一个线程已经更改了tail，但还没有将head的next指向tail
当前线程将head赋给h后，head被另一个线程移除队列，导致h的next为空，这种情况说明锁已经被占用

//ReentrantLock->enq
private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                //第一种情况在这行字中间
                t.next = node;
                return t;
            }
        }
    }
}

//ReentrantLock->acquireQueued
final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                //第二种情况在这里，p.next=null
                setHead(node);
                p.next = null; 
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

后记

最后再说一下公平锁和非公平锁，举个例子

public class SyncTest {

    public static Lock lock = new ReentrantLock();

    public static void main(String[] args) {

        Thread[] threads = new Thread[10];
        for (int i = 0; i < 10; i++) {
            threads[i] = new Thread(new Runnable() {
                @Override
                public void run() {
                    System.out.println(Thread.currentThread().getName() + " 开始运行");
                    testMethod();
                }
            });
        }
        for (int i = 0; i < 10; i++) {
            threads[i].start();
        }
    }

    public static void testMethod() {
        lock.lock();
        try {
            System.out.println(Thread.currentThread().getName() + " 获得锁");
        } finally {
            lock.unlock();
        }
    }
}

执行结果有时如下

Thread-0 开始运行
Thread-2 开始运行
Thread-0 获得锁
Thread-3 开始运行
Thread-1 开始运行
Thread-2 获得锁
Thread-4 开始运行
Thread-4 获得锁
Thread-5 开始运行
Thread-3 获得锁
Thread-6 开始运行
Thread-6 获得锁
Thread-1 获得锁
Thread-9 开始运行
Thread-7 开始运行
Thread-5 获得锁
Thread-8 开始运行
Thread-9 获得锁
Thread-7 获得锁
Thread-8 获得锁

可以看到开始运行的顺序和获得锁的顺序是不一致的

将lock成员变量改为如下

public static Lock lock = new ReentrantLock(true);

执行结果有时如下

Thread-0 开始运行
Thread-2 开始运行
Thread-1 开始运行
Thread-3 开始运行
Thread-4 开始运行
Thread-6 开始运行
Thread-0 获得锁
Thread-5 开始运行
Thread-2 获得锁
Thread-7 开始运行
Thread-1 获得锁
Thread-9 开始运行
Thread-8 开始运行
Thread-3 获得锁
Thread-4 获得锁
Thread-6 获得锁
Thread-5 获得锁
Thread-7 获得锁
Thread-9 获得锁
Thread-8 获得锁

可以看到开始运行的顺序和获得锁的顺序是一致的，但是这并不是绝对的，假设线程B调用tryAcquire失败后，并在调用addWaiter之前，线程A释放了锁，且线程C判断到锁空闲，进入hasQueuedPredecessors返回false（等待队列为空），最终C比B先获取到锁，因此公平锁并不是绝对公平的

非公平的锁的效率高于公平锁的效率，是因为在恢复一个被挂起的线程与该线程真正运行之间存在着严重的延迟，假设线程A持有一个锁，并且线程B请求这个锁。由于锁被A持有，因此B将被挂起。当A释放锁时，B将被唤醒，因此B会再次尝试获取这个锁。与此同时，如果线程C也请求这个锁，那么C很可能会在B被完全唤醒之前获得、使用以及释放这个锁。这样就是一种双赢的局面：B获得锁的时刻并没有推迟，C更早的获得了锁，并且吞吐量也提高了。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-05-02，如有侵权请联系 cloudcommunity@tencent.com 删除

unix

编程算法

本文分享自 Java识堂微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

unix

编程算法

登录后参与评论

0 条评论

热度