java 鎖

源碼看 github

java 中的鎖，宏觀上分為樂觀鎖和悲觀鎖

• 樂觀鎖：讀多寫少，都是基于CAS實(shí)現(xiàn)的，CAS是一種原子操作。
• 悲觀鎖： 寫多，遇到并發(fā)寫的可能性高，是采用AQS框架實(shí)現(xiàn)的。

樂觀鎖：

認(rèn)為數(shù)據(jù)每次都不會(huì)被修改，但是在使用前都會(huì)進(jìn)行對(duì)比，如果已經(jīng)被修改，則重試，直到?jīng)]有被修改為止。
其實(shí)現(xiàn)的機(jī)制是CAS，原子操作，它適用于多讀操作；

悲觀鎖

認(rèn)為每次數(shù)據(jù)都被修改，故需要在數(shù)據(jù)讀寫的時(shí)候都加上鎖，這樣就造成了別的線程的阻塞，直到鎖被釋放。java的互斥鎖，synchronized就是一種悲觀鎖。其依靠AQS框架實(shí)現(xiàn)；

CAS

即compareAndSwap，它是一種原子性操作：它是依靠處理器提供的cmpxchg指令完成的

cmpxchg是匯編指令 (百度百科):

• 作用：比較并交換操作數(shù).
• 如：CMPXCHG r/m,r 將累加器AL/AX/EAX/RAX中的值與首操作數(shù)（目的操作數(shù)）比較，如果相等，第2操作數(shù)（源操作數(shù)）的值裝載到首操作數(shù)，zf置1。如果不等,首操作>數(shù)的值裝載到AL/AX/EAX/RAX并將zf清零.
• 該指令只能用于486及其后繼機(jī)型。第2操作數(shù)（源操作數(shù)）只能用8位、16位或32位寄存器。第1操作數(shù)（目地操作數(shù)）則可用寄存器或任一種存儲(chǔ)器尋址方式。

一般變量累加操作：

變量的自增操作i++,分三個(gè)步驟：

1. 從內(nèi)存中讀取出變量i的值

2. 將i的值加1

3. 將加1后的值寫回內(nèi)存

這說明 i++ 并不是一個(gè)原子操作。因?yàn)?，它分成了三步，有可能?dāng)某個(gè)線程執(zhí)行到了第②時(shí)被中斷了，那么就意味著只執(zhí)行了其中的兩個(gè)步驟，沒有全部執(zhí)行。
下面一個(gè)例子：

package test;


import org.w3c.dom.css.Counter;

import java.util.concurrent.atomic.AtomicInteger;

class MyThread extends Thread{
    public volatile static  int cout;   // 使用volatile關(guān)鍵字，說明其只有內(nèi)存可見性但無原子性
    public static int coutp;            
    public static AtomicInteger atomicInteger=new AtomicInteger(0);     // 采用CAS實(shí)現(xiàn)
    private static void addCout(){
        for (int i = 0; i <100 ; i++) {
            cout++;
            coutp++;
            atomicInteger.getAndIncrement();
        }
        System.out.print(Thread.currentThread().getName()+ "  cout="+cout+" coutp="+ coutp+ " atomicInteger="+atomicInteger+"\n");
    }
    public void run(){
        addCout();
    }
}

public class Increase {

    public static void main(String[] args) {
        MyThread[] myThreads=new MyThread[100];
        for (int i = 0; i <100 ; i++) {
            myThreads[i]=new MyThread();
        }
        for (int i = 0; i < 100; i++) {
            myThreads[i].start();
        }
    }
}

===result:

....
Thread-63  cout=9655 coutp=9674 atomicInteger=9700
Thread-60  cout=9755 coutp=9774 atomicInteger=9800
Thread-62  cout=9555 coutp=9574 atomicInteger=9600
Thread-61  cout=9855 coutp=9874 atomicInteger=9900
Thread-58  cout=9955 coutp=9974 atomicInteger=10000

CAS累加：

先看一下 AtomicInteger的累加方法：

/**
* AtomicInteger，調(diào)用了unsafe類的方法
**/

public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }


/**
* Unsafe 類
**/

public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));  // CAS循環(huán)操作

        return var5;
    }
    
    
public native int getIntVolatile(Object var1, long var2);    

上面說到，它是依靠處理器提供的cmpxchg指令完成的

CAS比較與交換的偽代碼可以表示為：

do{   
       備份舊數(shù)據(jù)；  
       基于舊數(shù)據(jù)構(gòu)造新數(shù)據(jù)；  
}while(!CAS( 內(nèi)存地址，備份的舊數(shù)據(jù)，新數(shù)據(jù) ))  

就是指當(dāng)兩者進(jìn)行比較時(shí)，如果相等，則證明共享數(shù)據(jù)沒有被修改，替換成新值，然后繼續(xù)往下運(yùn)行；如果不相等，說明共享數(shù)據(jù)已經(jīng)被修改，放棄已經(jīng)所做的操作，然后重新執(zhí)行剛才的操作。容易看出 CAS 操作是基于共享數(shù)據(jù)不會(huì)被修改的假設(shè)，采用了類似于數(shù)據(jù)庫的 commit-retry 的模式。當(dāng)同步?jīng)_突出現(xiàn)的機(jī)會(huì)很少時(shí)，這種假設(shè)能帶來較大的性能提升。(https://www.cnblogs.com/Mainz/p/3546347.html)。
CAS是項(xiàng)樂觀鎖技術(shù)，當(dāng)多個(gè)線程嘗試使用CAS同時(shí)更新同一個(gè)變量時(shí)，只有其中一個(gè)線程能更新變量的值，而其它線程都失敗，失敗的線程并不會(huì)堵塞，而是被告知這次競(jìng)爭(zhēng)中失敗，并可以再次嘗試；

當(dāng)然，CAS也有一些問題：(https://my.oschina.net/xinxingegeya/blog/499223)

• ABA問題

ABA問題: 因?yàn)镃AS需要在操作值的時(shí)候檢查下值有沒有發(fā)生變化，如果沒有發(fā)生變化則更新，但是如果一個(gè)值原來是A，變成了B，又變成了A，那么使用CAS進(jìn)行檢查時(shí)會(huì)發(fā)現(xiàn)它的值沒有發(fā)生變化，但是實(shí)際上卻變化了。ABA問題的解決思路就是使用版本號(hào)。在變量前面追加上版本號(hào)，每次變量更新的時(shí)候把版本號(hào)加一，那么A－B－A 就會(huì)變成1A-2B－3A。從Java1.5開始JDK的atomic包里提供了一個(gè)類AtomicStampedReference來解決ABA問題。這個(gè)類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值。

 /**
     * Atomically sets the value of both the reference and stamp
     * to the given update values if the
     * current reference is {@code ==} to the expected reference
     * and the current stamp is equal to the expected stamp.
     *
     * @param expectedReference the expected value of the reference  預(yù)期引用
     * @param newReference the new value for the reference   更新后的引用
     * @param expectedStamp the expected value of the stamp  預(yù)期標(biāo)志
     * @param newStamp the new value for the stamp   更新后的標(biāo)志
     * @return {@code true} if successful
     */
    public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }

• 循環(huán)開銷大

循環(huán)時(shí)間長(zhǎng)開銷大。自旋CAS如果長(zhǎng)時(shí)間不成功，會(huì)給CPU帶來非常大的執(zhí)行開銷。如果JVM能支持處理器提供的pause指令那么效率會(huì)有一定的提升，pause指令有兩個(gè)作用，第一它可以延遲流水線執(zhí)行指令（de-pipeline）,使CPU不會(huì)消耗過多的執(zhí)行資源，延遲的時(shí)間取決于具體實(shí)現(xiàn)的版本，在一些處理器上延遲時(shí)間是零。第二它可以避免在退出循環(huán)的時(shí)候因內(nèi)存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執(zhí)行效率。

• 只能保證一個(gè)共享變量

只能保證一個(gè)共享變量的原子操作。當(dāng)對(duì)一個(gè)共享變量執(zhí)行操作時(shí)，我們可以使用循環(huán)CAS的方式來保證原子操作，但是對(duì)多個(gè)共享變量操作時(shí)，循環(huán)CAS就無法保證操作的原子性，這個(gè)時(shí)候就可以用鎖，或者有一個(gè)取巧的辦法，就是把多個(gè)共享變量合并成一個(gè)共享變量來操作。比如有兩個(gè)共享變量i＝2,j=a，合并一下ij=2a，然后用CAS來操作ij。從Java1.5開始JDK提供了AtomicReference類來保證引用對(duì)象之間的原子性，你可以把多個(gè)變量放在一個(gè)對(duì)象里來進(jìn)行CAS操作。

自旋鎖

了解了CAS,就來看一下自旋鎖：自旋鎖，基本作用與互斥鎖類似，為線程或者進(jìn)程之間的同步。但是對(duì)于互斥鎖，如A線程獲得了鎖，B線程試圖去獲取該鎖時(shí)，B線程會(huì)被阻塞。但是，如果兩個(gè)線程資源競(jìng)爭(zhēng)不是特別激烈，而處理器阻塞一個(gè)線程引起的線程上下文的切換的代價(jià)高于等待資源的代價(jià)的時(shí)候（鎖的已保持者保持鎖時(shí)間比較短），那么線程B可以不放棄CPU時(shí)間片，而是在“原地”忙等，直到鎖的持有者釋放了該鎖，這就是自旋鎖的原理，可見自旋鎖是一種非阻塞鎖。

一種實(shí)現(xiàn)方式如下：

package test;

import java.util.concurrent.atomic.AtomicReference;

public class SpinLock {
    private AtomicReference<Thread> sign=new AtomicReference<>();
    public void lock(){
        Thread current=Thread.currentThread();
        //lock函數(shù)將current設(shè)置為當(dāng)前線程，并且預(yù)測(cè)原來的值為空。unlock函數(shù)將current設(shè)置為null，并且預(yù)測(cè)值為當(dāng)前線程。當(dāng)有第二個(gè)線程調(diào)用lock操作時(shí)由于current值不為空，導(dǎo)致循環(huán)    
  
       //一直被執(zhí)行，直至第一個(gè)線程調(diào)用unlock函數(shù)將current設(shè)置為null，第二個(gè)線程才能進(jìn)入臨界區(qū)。  
        while (!sign.compareAndSet(null,current)){

        }
    }

    public void unlock(){
        Thread current=Thread.currentThread();
        //lock函數(shù)將current設(shè)置為當(dāng)前線程,將current設(shè)置為null，第二個(gè)線程才能進(jìn)入臨界區(qū)。  
        sign.compareAndSet(current,null);
    }
}

一個(gè)例子:

package test;

import java.util.concurrent.TimeUnit;

public class ThreadTest implements Runnable{
    private static int sum;
    private SpinLock lock;

    public ThreadTest(SpinLock lock){
        this.lock=lock;
    }

    public static void main(String[] args) throws InterruptedException {
        SpinLock lock=new SpinLock();
        for (int i = 0; i < 100; i++) {
            ThreadTest threadTest=new ThreadTest(lock);
            Thread t=new Thread(threadTest);
            t.start();
        }
        TimeUnit.MILLISECONDS.sleep(200);
    }

    @Override
    public void run() {
        this.lock.lock();
        sum++;
        System.out.print(sum+"  "+Thread.currentThread().getName()+"\n");
        this.lock.unlock();
    }
}

===RESULT

...
84  Thread-68
85  Thread-67
86  Thread-66
87  Thread-65
88  Thread-64
89  Thread-63
90  Thread-62
91  Thread-61
92  Thread-4
93  Thread-60
94  Thread-59
95  Thread-58
96  Thread-55
97  Thread-71
98  Thread-77
99  Thread-54
100  Thread-57

自旋鎖存在的問題及改進(jìn)

• 過多占用CPU時(shí)間：如果當(dāng)前持有者長(zhǎng)時(shí)間不釋放該鎖，則等待者將長(zhǎng)時(shí)間的占據(jù)cpu時(shí)間片，導(dǎo)致資源浪費(fèi)。因此，要設(shè)定最大自旋等待時(shí)間，若超過這個(gè)時(shí)間，等待者會(huì)放棄cpu時(shí)間片，進(jìn)行阻塞；
• 死鎖，即有一個(gè)線程兩次試圖獲取自旋鎖(如遞歸程序)，第一次這個(gè)線程獲得了該鎖，當(dāng)?shù)诙卧噲D加鎖的時(shí)候，檢測(cè)到鎖已被占用（其實(shí)是被自己占用），那么這時(shí)，線程會(huì)一直等待自己釋放該鎖，而不能繼續(xù)執(zhí)行，這樣就引起了死鎖。這也說明，自旋鎖是非可重入鎖.因此遞歸程序使用自旋鎖應(yīng)該遵循以下原則：遞歸程序決不能在持有自旋鎖時(shí)調(diào)用它自己，也決不能在遞歸調(diào)用時(shí)試圖獲得相同的自旋鎖。

改進(jìn)死鎖，其引入線程計(jì)數(shù)器，可重入鎖的原理也是如此：

package test;

import java.util.concurrent.atomic.AtomicReference;

public class SpinLock {
    private AtomicReference<Thread> sign=new AtomicReference<>();
    private int count;  // 增加計(jì)數(shù)器
    public void lock(){
        Thread current=Thread.currentThread();
     
        if(current==sign.get()){   // 同一線程，獲取鎖，計(jì)數(shù)器加一
            count++;
            return;
        }
       
        while (!sign.compareAndSet(null,current)){
              // 等待鎖被釋放
        }
    }

    public void unlock(){
        Thread current=Thread.currentThread();
      
        if(current==sign.get()){
            if(count>0)
                count--;   // 釋放一個(gè)鎖，該鎖的計(jì)數(shù)器減一
            else
                sign.compareAndSet(current,null);
        }
       
    }
}

對(duì)比運(yùn)行一下：

# 將ThreadTest 的run方法，重寫為：
 @Override
    public void run() {
        this.lock.lock();
        this.lock.lock();
        sum++;
        System.out.print(sum+"  "+Thread.currentThread().getName()+"\n");
        this.lock.unlock();
        this.lock.unlock();
    }

改進(jìn)前死鎖，電腦直接卡死了。
而改進(jìn)后，可重入運(yùn)行OK