天天看點
傳回

可重入鎖 公平鎖 讀寫鎖、CLH隊列、CLH隊列鎖、自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖

1.可重入鎖

如果鎖具備可重入性，則稱作為可重入鎖。

==========================================

（轉）可重入和不可重入

2011-10-04 21:38

這種情況出現在多任務系統當中，在任務執行期間捕捉到信号并對其進行處理時，程序正在執行的指令序列就被信号處理程式臨時中斷。如果從信号處理程式傳回，則繼續執行程序斷點處的正常指令序列，從重新恢複到斷點重新執行的過程中，函數所依賴的環境沒有發生改變，就說這個函數是可重入的，反之就是不可重入的。

衆所周知，在程序中斷期間，系統會儲存和恢複程序的上下文，然而恢複的上下文僅限于傳回位址，cpu寄存器等之類的少量上下文，而函數内部使用的諸如全局或靜态變量，buffer等并不在保護之列，是以如果這些值在函數被中斷期間發生了改變，那麼當函數回到斷點繼續執行時，其結果就不可預料了。打個比方，比如malloc，将如一個程序此時正在執行malloc配置設定堆空間，此時程式捕捉到信号發生中斷，執行信号處理程式中恰好也有一個malloc，這樣就會對程序的環境造成破壞，因為malloc通常為它所配置設定的存儲區維護一個連結表，插入執行信号處理函數時，程序可能正在對這張表進行操作，而信号處理函數的調用剛好覆寫了程序的操作，造成錯誤。

滿足下面條件之一的多數是不可重入函數：

(1)使用了靜态資料結構;

(2)調用了malloc或free;

(3)調用了标準I/O函數;标準io庫很多實作都以不可重入的方式使用全局資料結構。

(4)進行了浮點運算.許多的處理器/編譯器中，浮點一般都是不可重入的 (浮點運算大多使用協處理器或者軟體模拟來實作)。

1) 信号處理程式A内外都調用了同一個不可重入函數B；B在執行期間被信号打斷，進入A (A中調用了B),完事之後傳回B被中斷點繼續執行，這時B函數的環境可能改變，其結果就不可預料了。

2) 多線程共享程序内部的資源，如果兩個線程A，B調用同一個不可重入函數F，A線程進入F後，線程排程，切換到B，B也執行了F，那麼當再次切換到線程A時，其調用F的結果也是不可預料的。

在信号處理程式中即使調用可重入函數也有問題要注意。作為一個通用的規則，當在信号處理程式中調用可重入函數時，應當在其前儲存errno，并在其後恢複errno。(因為每個線程隻有一個errno變量，信号處理函數可能會修改其值，要了解經常被捕捉到的信号是SIGCHLD，其信号處理程式通常要調用一種wait函數，而各種wait函數都能改變errno。)

可重入函數清單:

_exit（）、 access（）、alarm（）、cfgetispeed（）、cfgetospeed（）、cfsetispeed（）、cfsetospeed （）、chdir（）、chmod（）、chown（）、close（）、creat（）、dup（）、dup2（）、execle（）、 execve（）、fcntl（）、fork（）、fpathconf （）、fstat（）、fsync（）、getegid（）、 geteuid（）、getgid（）、getgroups（）、getpgrp（）、getpid（）、getppid（）、getuid（）、 kill（）、link（）、lseek（）、mkdir（）、mkfifo（）、 open（）、pathconf（）、pause（）、pipe（）、raise（）、read（）、rename（）、rmdir（）、setgid （）、setpgid（）、setsid（）、setuid（）、 sigaction（）、sigaddset（）、sigdelset（）、sigemptyset（）、sigfillset（）、 sigismember（）、signal（）、sigpending（）、sigprocmask（）、sigsuspend（）、sleep（）、 stat（）、sysconf（）、tcdrain（）、tcflow（）、tcflush（）、tcgetattr（）、tcgetpgrp（）、 tcsendbreak（）、tcsetattr（）、tcsetpgrp（）、time（）、times（）、 umask（）、uname（）、unlink（）、utime（）、wait（）、waitpid（）、write（）。

書上關于信号處理程式中調用不可重入函數的例子:

#include <stdlib.h>

#include <stdio.h>

#include <pwd.h>

static void func(int signo)

{

    struct passwd *rootptr;

    if( ( rootptr = getpwnam( "root" ) ) == NULL )

    {

        err_sys( "getpwnam error" );

    }

    signal(SIGALRM,func);

    alarm(1);

}

int main(int argc, char** argv)

    for(;;)

        if( ( ptr = getpwnam("sar") ) == NULL )

        {

            err_sys( "getpwnam error" );

        }

    return 0;

signal了一個SIGALRM,而後設定一個定時器，在for函數運作期間的某個時刻，也許就是在getpwnam函數運作期間，相應信号發生中斷，進入信号處理函數func，在運作func期間又收到alarm發出的信号，getpwnam可能再次中斷，這樣就很容易發生不可預料的問題。

像synchronized和ReentrantLock都是可重入鎖，可重入性在我看來實際上表明了鎖的配置設定機制：

基于線程的配置設定，而不是基于方法調用的配置設定。

舉個簡單的例子，當一個線程執行到某個synchronized方法時，比如說method1，而在method1中會調用另外一個synchronized方法method2，

此時線程不必重新去申請鎖，而是可以直接執行方法method2。

可重入鎖 公平鎖 讀寫鎖、CLH隊列、CLH隊列鎖、自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖

class MyClass {
    public synchronized void method1() {
        method2();
    }

    public synchronized void method2() {

    }
}
可重入鎖 公平鎖 讀寫鎖、CLH隊列、CLH隊列鎖、自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖

上述代碼中的兩個方法method1和method2都用synchronized修飾了，

假如某一時刻，線程A執行到了method1，此時線程A擷取了這個對象的鎖，而由于method2也是synchronized方法，假如synchronized不具備可重入性，此時線程A需要重新申請鎖。

但是這就會造成一個問題，因為線程A已經持有了該對象的鎖，而又在申請擷取該對象的鎖，這樣就會線程A一直等待永遠不會擷取到的鎖。

而由于synchronized和ReentrantLock都具備可重入性，是以不會發生上述現象。《​​可重入鎖​​》

　2.可中斷鎖

　　可中斷鎖：顧名思義，就是可以相應中斷的鎖。

　　在Java中，synchronized就不是可中斷鎖，而Lock是可中斷鎖。

可重入鎖 公平鎖 讀寫鎖、CLH隊列、CLH隊列鎖、自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖

　　如果某一線程A正在執行鎖中的代碼，另一線程B正在等待擷取該鎖，可能由于等待時間過長，線程B不想等待了，想先處理其他事情，我們可以讓它中斷自己或者在别的線程中中斷它，這種就是可中斷鎖。

　　在前面示範lockInterruptibly()的用法時已經展現了Lock的可中斷性。

3.公平鎖

　　公平鎖即盡量以請求鎖的順序來擷取鎖。比如同是有多個線程在等待一個鎖，當這個鎖被釋放時，等待時間最久的線程（最先請求的線程）會獲得該所，這種就是公平鎖。

　　非公平鎖即無法保證鎖的擷取是按照請求鎖的順序進行的。這樣就可能導緻某個或者一些線程永遠擷取不到鎖。

　　在Java中，synchronized就是非公平鎖，它無法保證等待的線程擷取鎖的順序。

　　而對于ReentrantLock和ReentrantReadWriteLock，它預設情況下是非公平鎖，但是可以設定為公平鎖。這一點由構造函數可知：

可重入鎖 公平鎖 讀寫鎖、CLH隊列、CLH隊列鎖、自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖
1    
2     public ReentrantLock() {
3         sync = new NonfairSync();
4     }
5 
6 
7     public ReentrantLock(boolean fair) {
8         sync = (fair)? new FairSync() : new NonfairSync();
9     }
可重入鎖 公平鎖 讀寫鎖、CLH隊列、CLH隊列鎖、自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖

在ReentrantLock中定義了2個靜态内部類，一個是NotFairSync，一個是FairSync，分别用來實作非公平鎖和公平鎖。

我們可以在建立ReentrantLock對象時，通過知道布爾參數來決定使用 非公平鎖 還是公平鎖

如果參數為true表示為公平鎖，為fasle為非公平鎖。預設情況下，如果使用無參構造器，則是非公平鎖

另外在ReentrantLock類中定義了很多方法，比如：

　　isFair()        //判斷鎖是否是公平鎖

　　isLocked()    //判斷鎖是否被任何線程擷取了

　　isHeldByCurrentThread()   //判斷鎖是否被目前線程擷取了

　　hasQueuedThreads()   //判斷是否有線程在等待該鎖

在ReentrantReadWriteLock中也有類似的方法，同樣也可以設定為公平鎖和非公平鎖。

不過要記住，ReentrantReadWriteLock并未實作Lock接口，它實作的是ReadWriteLock接口。

4.讀寫鎖

　　讀寫鎖将對一個資源（比如檔案）的通路分成了2個鎖，一個讀鎖和一個寫鎖。

　　正因為有了讀寫鎖，才使得多個線程之間的讀操作不會發生沖突。

　　ReadWriteLock就是讀寫鎖，它是一個接口，ReentrantReadWriteLock實作了這個接口。

　　可以通過readLock()擷取讀鎖，通過writeLock()擷取寫鎖。

CLH隊列鎖

CLH鎖即Craig, Landin, and Hagersten (CLH) locks，CLH鎖是一個自旋鎖，能確定無饑餓性，提供先來先服務的公平性。

CLH鎖也是一種基于連結清單的可擴充、高性能、公平的自旋鎖，申請線程隻在本地變量上自旋，它不斷輪詢前驅的狀态，如果發現前驅釋放了鎖就結束自旋。

SMP(Symmetric Multi-Processor)，即對稱多處理器結構，指伺服器中多個CPU對稱工作，每個CPU通路記憶體位址所需時間相同。其主要特征是共享，包含對CPU，記憶體，I/O等進行共享。SMP的優點是能夠保證記憶體一緻性，缺點是這些共享的資源很可能成為性能瓶頸，随着CPU數量的增加，每個CPU都要通路相同的記憶體資源，可能導緻記憶體通路沖突，可能會導緻CPU資源的浪費。常用的PC機就屬于這種。

NUMA(Non-Uniform

Memory Access)非一緻存儲通路，将CPU分為CPU子產品，每個CPU子產品由多個CPU組成，并且具有獨立的本地記憶體、I/O槽口等，子產品之間可以通過互聯子產品互相通路，通路本地記憶體的速度将遠遠高于通路遠地記憶體(系統内其它節點的記憶體)的速度，這也是非一緻存儲通路NUMA的由來。NUMA優點是可以較好地解決原來SMP系統的擴充問題，缺點是由于通路遠地記憶體的延時遠遠超過本地記憶體，是以當CPU數量增加時，系統性能無法線性增加。

CLH​​算法​​實作

CLH隊列中的結點QNode中含有一個locked字段，該字段若為true表示該線程需要擷取鎖，且不釋放鎖，為false表示線程釋放了鎖。結點之間是通過隐形的連結清單相連，之是以叫隐形的連結清單是因為這些結點之間沒有明顯的next指針，而是通過myPred所指向的結點的變化情況來影響myNode的行為。CLHLock上還有一個尾指針，始終指向隊列的最後一個結點。CLHLock的類圖如下所示：

當一個線程需要擷取鎖時，會建立一個新的QNode，将其中的locked設定為true表示需要擷取鎖，然後線程對tail域調用getAndSet方法，使自己成為隊列的尾部，同時擷取一個指向其前趨的引用myPred,然後該線程就在前趨結點的locked字段上旋轉，直到前趨結點釋放鎖。當一個線程需要釋放鎖時，将目前結點的locked域設定為false，同時回收前趨結點。如下圖所示，線程A需要擷取鎖，其myNode域為true，些時tail指向線程A的結點，然後線程B也加入到線程A後面，tail指向線程B的結點。然後線程A和B都在它的myPred域上旋轉，一量它的myPred結點的locked字段變為false，它就可以擷取鎖掃行。明顯線程A的myPred

locked域為false，此時線程A擷取到了鎖。

整個CLH的​​代碼​​如下，其中用到了ThreadLocal類，将QNode綁定到每一個線程上，同時用到了AtomicReference,對尾指針的修改正是調用它的getAndSet()操作來實作的，它能夠保證以原子方式更新對象引用。

public class CLHLock implements Lock {  
    AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode());  
    ThreadLocal<QNode> myPred;  
    ThreadLocal<QNode> myNode;  

    public CLHLock() {  
        tail = new AtomicReference<QNode>(new QNode());  
        myNode = new ThreadLocal<QNode>() {  
            protected QNode initialValue() {  
                return new QNode();  
            }  
        };  
        myPred = new ThreadLocal<QNode>() {  
            protected QNode initialValue() {  
                return null;  
            }  
        };  
    }  

    @Override  
    public void lock() {  
        QNode qnode = myNode.get();  
        qnode.locked = true;  
        QNode pred = tail.getAndSet(qnode);  
        myPred.set(pred);  
        while (pred.locked) {  
        }  
    }  

    @Override  
    public void unlock() {  
        QNode qnode = myNode.get();  
        qnode.locked = false;  
        myNode.set(myPred.get());  
    }  
}

從代碼中可以看出lock方法中有一個while循環，這 是在等待前趨結點的locked域變為false，這是一個自旋等待的過程。unlock方法很簡單，隻需要将自己的locked域設定為false即可。

CLH優缺點

CLH隊列鎖的優點是空間複雜度低（如果有n個線程，L個鎖，每個線程每次隻擷取一個鎖，那麼需要的存儲空間是O（L+n），n個線程有n個myNode，L個鎖有L個tail），CLH的一種變體被應用在了JAVA并發架構中。唯一的缺點是在NUMA系統結構下性能很差，在這種系統結構下，每個線程有自己的記憶體，如果前趨結點的記憶體位置比較遠，自旋判斷前趨結點的locked域，性能将大打折扣，但是在SMP系統結構下該法還是非常有效的。一種解決NUMA系統結構的思路是MCS隊列鎖。

自旋鎖（Spin lock）

自旋鎖是指當一個線程嘗試擷取某個鎖時，如果該鎖已被其他線程占用，就一直循環檢測鎖是否被釋放，而不是進入線程挂起或睡眠狀态。

自旋鎖适用于鎖保護的臨界區很小的情況，臨界區很小的話，鎖占用的時間就很短。

簡單的實作 

package com.dxz.sync3;

import java.util.concurrent.atomic.AtomicReference;

public class SpinLock {
    private AtomicReference<Thread> owner = new AtomicReference<Thread>();

    public void lock() {
        Thread currentThread = Thread.currentThread();

        // 如果鎖未被占用，則設定目前線程為鎖的擁有者
        while (owner.compareAndSet(null, currentThread)) {
        }
    }

    public void unlock() {
        Thread currentThread = Thread.currentThread();

        // 隻有鎖的擁有者才能釋放鎖
        owner.compareAndSet(currentThread, null);
    }
}

SimpleSpinLock裡有一個owner屬性持有鎖目前擁有者的線程的引用，如果該引用為null，則表示鎖未被占用，不為null則被占用。

可重入鎖 公平鎖 讀寫鎖、CLH隊列、CLH隊列鎖、自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖

這裡用AtomicReference是為了使用它的原子性的compareAndSet方法（CAS操作），解決了多線程并發操作導緻資料不一緻的問題，確定其他線程可以看到鎖的真實狀态。

缺點

  1. CAS操作需要硬體的配合；
  2. 保證各個CPU的緩存（L1、L2、L3、跨CPU Socket、主存）的資料一緻性，通訊開銷很大，在多處理器系統上更嚴重；
  3. 沒法保證公平性，不保證等待程序/線程按照FIFO順序獲得鎖。

Ticket Lock

Ticket Lock 是為了解決上面的公平性問題，類似于現實中銀行櫃台的排隊叫号：鎖擁有一個服務号，表示正在服務的線程，還有一個排隊号；每個線程嘗試擷取鎖之前先拿一個排隊号，然後不斷輪詢鎖的目前服務号是否是自己的排隊号，如果是，則表示自己擁有了鎖，不是則繼續輪詢。

當線程釋放鎖時，将服務号加1，這樣下一個線程看到這個變化，就退出自旋。

Ticket Lock 雖然解決了公平性的問題，但是多處理器系統上，每個程序/線程占用的處理器都在讀寫同一個變量serviceNum ，每次讀寫操作都必須在多個處理器緩存之間進行緩存同步，這會導緻繁重的系統總線和記憶體的流量，大大降低系統整體的性能。

下面介紹的CLH鎖和MCS鎖都是為了解決這個問題的。

MCS 來自于其發明人名字的首字母： John Mellor-Crummey和Michael Scott。

CLH的發明人是：Craig，Landin and Hagersten。

CLH鎖 

package com.dxz.sync3;

import java.util.concurrent.atomic.AtomicInteger;

public class TicketLock {
    private AtomicInteger serviceNum = new AtomicInteger(); // 服務号
    private AtomicInteger ticketNum = new AtomicInteger(); // 排隊号

    public int lock() {
        // 首先原子性地獲得一個排隊号
        int myTicketNum = ticketNum.getAndIncrement();

        // 隻要目前服務号不是自己的就不斷輪詢
        while (serviceNum.get() != myTicketNum) {
        }

        return myTicketNum;
    }

    public void unlock(int myTicket) {
        // 隻有目前線程擁有者才能釋放鎖
        int next = myTicket + 1;
        serviceNum.compareAndSet(myTicket, next);
    }
}

MCS鎖

MCS Spinlock 是一種基于連結清單的可擴充、高性能、公平的自旋鎖，申請線程隻在本地變量上自旋，直接前驅負責通知其結束自旋，進而極大地減少了不必要的處理器緩存同步的次數，降低了總線和記憶體的開銷。

package com.dxz.sync3;

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class MCSLock {
    public static class MCSNode {
        MCSNode next;
        boolean isLocked = true; // 預設是在等待鎖
    }

    volatile MCSNode queue;// 指向最後一個申請鎖的MCSNode
    private static final AtomicReferenceFieldUpdater<MCSLock, MCSNode> UPDATER = AtomicReferenceFieldUpdater
            .newUpdater(MCSLock.class, MCSNode.class, "queue");

    public void lock(MCSNode currentThreadMcsNode) {
        MCSNode predecessor = UPDATER.getAndSet(this, currentThreadMcsNode);// step
                                                                            // 1
        if (predecessor != null) {
            predecessor.next = currentThreadMcsNode;// step 2

            while (currentThreadMcsNode.isLocked) {// step 3
            }
        }
    }

    public void unlock(MCSNode currentThreadMcsNode) {
        if (UPDATER.get(this) == currentThreadMcsNode) {// 鎖擁有者進行釋放鎖才有意義
            if (currentThreadMcsNode.next == null) {// 檢查是否有人排在自己後面
                if (UPDATER.compareAndSet(this, currentThreadMcsNode, null)) {// step
                                                                                // 4
                    // compareAndSet傳回true表示确實沒有人排在自己後面
                    return;
                } else {
                    // 突然有人排在自己後面了，可能還不知道是誰，下面是等待後續者
                    // 這裡之是以要忙等是因為：step 1執行完後，step 2可能還沒執行完
                    while (currentThreadMcsNode.next == null) { // step 5
                    }
                }
            }

            currentThreadMcsNode.next.isLocked = false;
            currentThreadMcsNode.next = null;// for GC
        }
    }
}

CLH鎖 與 MCS鎖 的比較

下圖是CLH鎖和MCS鎖隊列圖示：

可重入鎖 公平鎖 讀寫鎖、CLH隊列、CLH隊列鎖、自旋鎖、排隊自旋鎖、MCS鎖、CLH鎖
  1. 從代碼實作來看，CLH比MCS要簡單得多。
  2. 從自旋的條件來看，CLH是在前驅節點的屬性上自旋，而MCS是在本地屬性變量上自旋
  3. 從連結清單隊列來看，CLH的隊列是隐式的，CLHNode并不實際持有下一個節點；MCS的隊列是實體存在的。
  4. CLH鎖釋放時隻需要改變自己的屬性，MCS鎖釋放則需要改變後繼節點的屬性。
多線程 JUC lock 公平鎖 結點
上一篇: PHP利用消息隊列來解決高并發庫存
下一篇: Spring Cloud 之 Gateway.

繼續閱讀