簡(jiǎn)介

ReentrantLock的實(shí)現(xiàn)不僅可以替代隱式的synchronized關(guān)鍵字，而且能夠提供超過(guò)關(guān)鍵字本身的多種功能。
這里提到一個(gè)鎖獲取的公平性問(wèn)題，如果在絕對(duì)時(shí)間上，先對(duì)鎖進(jìn)行獲取的請(qǐng)求一定被先滿足，那么這個(gè)鎖是公平的，反之，是不公平的，也就是說(shuō)等待時(shí)間最長(zhǎng)的線程最有機(jī)會(huì)獲取鎖，也可以說(shuō)鎖的獲取是有序的。ReentrantLock這個(gè)鎖提供了一個(gè)構(gòu)造函數(shù)，能夠控制這個(gè)鎖是否是公平的。
而鎖的名字也是說(shuō)明了這個(gè)鎖具備了重復(fù)進(jìn)入的可能，也就是說(shuō)能夠讓當(dāng)前線程多次的進(jìn)行對(duì)鎖的獲取操作，這樣的最大次數(shù)限制是Integer.MAX_VALUE，約21億次左右。
事實(shí)上公平的鎖機(jī)制往往沒(méi)有非公平的效率高，因?yàn)楣降墨@取鎖沒(méi)有考慮到操作系統(tǒng)對(duì)線程的調(diào)度因素，這樣造成JVM對(duì)于等待中的線程調(diào)度次序和操作系統(tǒng)對(duì)線程的調(diào)度之間的不匹配。對(duì)于鎖的快速且重復(fù)的獲取過(guò)程中，連續(xù)獲取的概率是非常高的，而公平鎖會(huì)壓制這種情況，雖然公平性得以保障，但是響應(yīng)比卻下降了，但是并不是任何場(chǎng)景都是以TPS作為唯一指標(biāo)的，因?yàn)楣芥i能夠減少“饑餓”發(fā)生的概率，等待越久的請(qǐng)求越是能夠得到優(yōu)先滿足。

實(shí)現(xiàn)分析

在ReentrantLock中，對(duì)于公平和非公平的定義是通過(guò)對(duì)同步器AbstractQueuedSynchronizer的擴(kuò)展加以實(shí)現(xiàn)的，也就是在tryAcquire的實(shí)現(xiàn)上做了語(yǔ)義的控制。

非公平的獲取語(yǔ)義：

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");
        setState(nextc);
        return true;
    }
    return false;
}

上述邏輯主要包括：

• 如果當(dāng)前狀態(tài)為初始狀態(tài)，那么嘗試設(shè)置狀態(tài)；
• 如果狀態(tài)設(shè)置成功后就返回；
• 如果狀態(tài)被設(shè)置，且獲取鎖的線程又是當(dāng)前線程的時(shí)候，進(jìn)行狀態(tài)的自增；
• 如果未設(shè)置成功狀態(tài)且當(dāng)前線程不是獲取鎖的線程，那么返回失敗。

公平的獲取語(yǔ)義：

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        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;
}

上述邏輯相比較非公平的獲取，僅加入了當(dāng)前線程（Node）之前是否有前置節(jié)點(diǎn)在等待的判斷。hasQueuedPredecessors()方法命名有些歧義，其實(shí)應(yīng)該是currentThreadHasQueuedPredecessors()更為妥帖一些，也就是說(shuō)當(dāng)前面沒(méi)有人排在該節(jié)點(diǎn)（Node）前面時(shí)候隊(duì)且能夠設(shè)置成功狀態(tài)，才能夠獲取鎖。

釋放語(yǔ)義：

protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

上述邏輯主要主要計(jì)算了釋放狀態(tài)后的值，如果為0則完全釋放，返回true，反之僅是設(shè)置狀態(tài)，返回false。
下面將主要的筆墨放在公平性和非公平性上，首先看一下二者測(cè)試的對(duì)比：
測(cè)試用例如下：

public class ReentrantLockTest {
    private static Lock fairLock = new ReentrantLock(true);
    private static Lock unfairLock = new ReentrantLock();
 
    @Test
    public void fair() {
        System.out.println("fair version");
        for (int i = 0; i < 5; i++) {
            Thread thread = new Thread(new Job(fairLock));
            thread.setName("" + i);
            thread.start();
        }

        try {
            Thread.sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    @Test
    public void unfair() {
        System.out.println("unfair version");
        for (int i = 0; i < 5; i++) {
            Thread thread = new Thread(new Job(unfairLock));
            thread.setName("" + i);
            thread.start();
        }

        try {
            Thread.sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    private static class Job implements Runnable {
        private Lock lock;
        public Job(Lock lock) {
            this.lock = lock;
        }

        @Override
        public void run() {
            for (int i = 0; i < 5; i++) {
                lock.lock();
                try {
                    System.out.println("Lock by:"
                            + Thread.currentThread().getName());
                } finally {
                    lock.unlock();
                }
            }
        }
    }
}

調(diào)用非公平的測(cè)試方法，返回結(jié)果(部分)：
unfair version
Lock by:0
Lock by:0
Lock by:2
Lock by:2
Lock by:2
Lock by:2
Lock by:2
Lock by:0
Lock by:0
Lock by:0
Lock by:1
Lock by:1
Lock by:1
調(diào)用公平的測(cè)試方法，返回結(jié)果：
fair version
Lock by:0
Lock by:1
Lock by:0
Lock by:2
Lock by:3
Lock by:4
Lock by:1
Lock by:0
Lock by:2
Lock by:3
Lock by:4
仔細(xì)觀察返回的結(jié)果(其中每個(gè)數(shù)字代表一個(gè)線程)，非公平的結(jié)果一個(gè)線程連續(xù)獲取鎖的情況非常多，而公平的結(jié)果連續(xù)獲取的情況基本沒(méi)有。那么在一個(gè)線程獲取了鎖的那一刻，究竟鎖的公平性會(huì)導(dǎo)致鎖有什么樣的處理邏輯呢？
通過(guò)之前的同步器(AbstractQueuedSynchronizer)的介紹，在鎖上是存在一個(gè)等待隊(duì)列，sync隊(duì)列，我們通過(guò)復(fù)寫(xiě)ReentrantLock的獲取當(dāng)前鎖的sync隊(duì)列，輸出在ReentrantLock被獲取時(shí)刻，當(dāng)前的sync隊(duì)列的狀態(tài)。
修改測(cè)試如下：

public class ReentrantLockTest {
    private static Lock fairLock = new ReentrantLock2(true);
    private static Lock unfairLock = new ReentrantLock2();
    @Test
    public void fair() {
        System.out.println("fair version");
        for (int i = 0; i < 5; i++) {
            Thread thread = new Thread(new Job(fairLock)) {
                public String toString() {
                    return getName();
                }
            };
            thread.setName("" + i);
            thread.start();
        }
        // sleep 5000ms
    }

    @Test
    public void unfair() {
        System.out.println("unfair version");
        for (int i = 0; i < 5; i++) {
            Thread thread = new Thread(new Job(unfairLock)) {
                public String toString() {
                    return getName();
                }
            };

            thread.setName("" + i);
            thread.start();
        }
        // sleep 5000ms

    }

    private static class Job implements Runnable {
        private Lock lock;

        public Job(Lock lock) {
            this.lock = lock;
        }

        @Override
        public void run() {
            for (int i = 0; i < 5; i++) {
                lock.lock();
                try {
                    System.out.println("Lock by:"
                            + Thread.currentThread().getName() + " and "
                            + ((ReentrantLock2) lock).getQueuedThreads()
                            + " waits.");
                } finally {
                    lock.unlock();
                }
            }
        }
    }

    private static class ReentrantLock2 extends ReentrantLock {
        // Constructor Override
        private static final long serialVersionUID = 1773716895097002072L;

        public Collection<Thread> getQueuedThreads() {
            return super.getQueuedThreads();
        }
    }
}

上述邏輯主要是通過(guò)構(gòu)造ReentrantLock2用來(lái)輸出在sync隊(duì)列中的線程內(nèi)容，而且每個(gè)線程的toString方法被重寫(xiě)，這樣當(dāng)一個(gè)線程獲取到鎖時(shí)，sync隊(duì)列里的內(nèi)容也就可以得知了，運(yùn)行結(jié)果如下：
調(diào)用非公平方法，返回結(jié)果：
unfair version
Lock by:0 and [] waits.
Lock by:0 and [] waits.
Lock by:3 and [2, 1] waits.
Lock by:3 and [4, 2, 1] waits.
Lock by:3 and [4, 2, 1] waits.
Lock by:3 and [0, 4, 2, 1] waits.
Lock by:3 and [0, 4, 2, 1] waits.
Lock by:1 and [0, 4, 2] waits.
Lock by:1 and [0, 4, 2] waits.
調(diào)用公平方法，返回結(jié)果：
fair version
Lock by:0 and [] waits.
Lock by:1 and [0, 4, 3, 2] waits.
Lock by:2 and [1, 0, 4, 3] waits.
Lock by:3 and [2, 1, 0, 4] waits.
Lock by:4 and [3, 2, 1, 0] waits.
Lock by:0 and [4, 3, 2, 1] waits.
Lock by:1 and [0, 4, 3, 2] waits.
Lock by:2 and [1, 0, 4, 3] waits.
可以明顯看出，在非公平獲取的過(guò)程中，“插隊(duì)”現(xiàn)象非常嚴(yán)重，后續(xù)獲取鎖的線程根本不顧及sync隊(duì)列中等待的線程，而是能獲取就獲取。反觀公平獲取的過(guò)程，鎖的獲取就類似線性化的，每次都由sync隊(duì)列中等待最長(zhǎng)的線程（鏈表的第一個(gè)，sync隊(duì)列是由尾部結(jié)點(diǎn)添加，當(dāng)前輸出的sync隊(duì)列是逆序輸出）獲取鎖。一個(gè) hasQueuedPredecessors方法能夠獲得公平性的特性，這點(diǎn)實(shí)際上是由AbstractQueuedSynchronizer來(lái)完成的，看一下acquire方法：

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

可以看到，如果獲取狀態(tài)和在sync隊(duì)列中排隊(duì)是短路的判斷，也就是說(shuō)如果tryAcquire成功，那么是不會(huì)進(jìn)入sync隊(duì)列的，可以通過(guò)下圖來(lái)深刻的認(rèn)識(shí)公平性和AbstractQueuedSynchronizer的獲取過(guò)程。
非公平的，或者說(shuō)默認(rèn)的獲取方式如下圖所示：