多線程基礎——建構高并發應用必會

基本概念

同步(Synchronous)和異步(Asynchronous)

同步：調用方必須等到方法調用傳回後才能繼續下一步。

異步：調用方調用方法後不需要等待傳回結果。

并發(Concurrency)和并行(Parallelism)

• 并發：多個任務交替執行。
• 并行：多個任務同時進行，隻有多CPU系統才能實作并行（比如多核CPU）。

臨界區

公共資源或共享資料，可以被多個線程使用，但是每一次隻能有一個線程使用它，一旦臨界區資源被占用，其他線程想要使用這個資源，就必須等待。

在并行程式中，臨界區資源是保護的對象。

阻塞(Blocking)和非阻塞(Non-Blocking)

阻塞和非阻塞通常用來形容多線程間的互相影響。

比如：一個線程占用了臨界區資源，那麼所有需要這個資源的線程就必須在這個臨界區中等待。等待會導緻線程挂起，這種情況就是阻塞。

非阻塞與阻塞相反，強調沒有一個線程可以妨礙其他線程執行。所有的線程都會嘗試不端向前執行。

死鎖(DeadLock)、饑餓(Starvation)和活鎖(LiveLock)

都屬于多線程的活躍性問題。

死鎖：多個線程所需要的鎖被對方占有，互相等待對方釋放鎖。

饑餓：一個或多個線程因為種種原因（如線程優先級太低、或某個線程一直占着關鍵資源不放）無法獲得所需的資源，導緻一直無法執行。

活鎖：多個線程不斷的主動将資源釋放給對方使用，導緻資源不斷地線上程間跳動，而沒有一個線程可以同時拿到所有資源正常執行。

并發級别

根據控制并發的政策，可以對并發的級别進行分類

參考文章：

無鎖程式設計技術及實作 Lock-Free and Wait-Free, definition and examples

阻塞(Blocking)

一個線程是阻塞的，那麼其他線程釋放資源之前，目前線程無法繼續執行。如使用synchronized關鍵字、可重入鎖。

缺點：會存在饑餓情況。

無饑餓(Starvation-Free)

使用公平鎖，按順序擷取資源，就能避免饑餓。

阻塞是悲觀政策。無阻塞是樂觀政策。

缺點：還是會有阻塞。

無障礙(Obstruction-Free)

最弱的非阻塞排程。都可以無限制進入臨界區，一旦檢測到發生并發修改資料的情況，會進行復原，保證資料安全。

一種可行的無障礙實作：依賴一個"一緻性标記"，線程操作前讀取并儲存該标記，操作完成後，再次讀取并檢查該标記是否被更改過，如果不一緻，說明被更改過，需要重試操作。任何對臨界區資源有修改操作的線程，在修改資料前都需要更新這個“一緻性标記”。

缺點： 沖突比較多時，會不斷的進行復原，導緻都無法走出臨界區。

無鎖(Lock-Free)

在無障礙的基礎上，保證必然有一個線程能夠在有限步内完成操作離開臨界區。

// 如果修改不成功，那麼循環永遠不會停止。
while(atomicVar.compareAndSet(localVar, locaVar+1)){
    localVar = atomicVar.get();
}           

缺點：會出現類似于饑餓的情況。

無等待(Wait-Free)

在無鎖的基礎上，要求所有的線程都必須在有限步内完成，這樣就不會引起饑餓問題。如果限制步驟上限，可分為有界無等待和線程數無關的無等待，差別隻是對循環次數的限制不同。

典型的無等待：++RCU(read-copy-update)++.對讀線程不加限制，都是無等待的，寫線程需要先取得原始資料的副本，接着隻修改副本資料(是以讀可以不加限制)，修改完成後在合适的時機回寫資料。

Amdahl定律

加速比 = 優化前耗時/優化後耗時

加速比公式：

Tn = T1(F+\frac{1}{n}(1-F))=\frac{1}{F+\frac{1}{n}(1-F) }           

n為CPU的數量，F為程式中串行執行的比例，T1為優化後耗時（隻有一個CPU執行），Tn為加速後耗時。

結論：當n無限大時，F越小，加速比越大。僅僅添加CPU對性能影響不是特别大，必須加大并行比例。

Gustafson定律

串行執行時=a

并行時間=b

執行時間=a+b

串行比例=F

F=\frac{a}{a+b}

S(n)=\frac{a+nb}{a+b} = \frac{a}{a+b}+\frac{nb}{a+b}

=F+n(\frac{a+b-a}{a+b})=F+b(1-\frac{a}{a+b})

=F+n-nf 

=n-F(n-1)
           

結論：如果串行比例很小，那麼加速比就是處理器的個數。隻要不斷地累加處理器，就能獲得更快得速度。

Amdahl強調：當串行化比例一定時，加速比是有上限的，不管堆多少cpu都不能突破這個上限。

Gustafson強調：如果可被并行化的代碼所占比重足夠多，那麼加速比就能随着CPU的數量線性增長。

串行化比例為1時，加速比都是1，串行化比例為0時，加速比都是n

JMM（java記憶體模型）

JMM是為了保證多個線程間可以有效地、正确地協同工作，定義的一組規則。

JMM的關鍵技術點都是圍繞多線程的原子性、可見性和有序性來建立的。

參考文章

Memory Model

原子性

指一個操作是不可中斷的，即使多個線程一起執行，一個操作一旦開始就不會被其他線程幹擾。

在32系統中，long型資料的讀寫不是原子性的（因為long有64位）。

可見性

可見性是指當一個線程修改了某一個共享變量的值，其他線程是否能夠立即知道這個修改。

緩存優化、編譯器優化、硬體優化和指令重排都有可能導緻一個線程的修改不會立即被其他線程察覺。

有序性

指令重排：為了提高CPU處理性能，指令可能會被重新排序，指令重排會保證串行語義一緻性，

不會使串行的語義邏輯發生問題，遵守Happen-Before原則，但不保證多線程間的語義也一緻。

//  如果不加volatile，線程ReadT已經讀到ready為false，當主線程修改ready為true後，線程ReadT并不能知道，主線程将一直執行。
private static volatile boolean ready;
private static int number = 0;
public static class ReadT extends Thread{
    @Override
    public void run() {
        while (!ready);
        System.out.println(number);
    }
}
public static void main(String[] args) throws InterruptedException {
    new ReadT().start();
    Thread.sleep(1000);
    number = 42;
    ready = true;
}           

volatile 可以保證可見性，不能保證原子性。能禁止指令重排序（是以能在一定程度上保證有序性），但隻能保證volatile所修飾的變量之前的程式不會在該變量之後執行，該變量之後的代碼不會在變量之前執行。

synchronized 可以保持原子性、可見性和有序性。

Happen-Before原則

指令重排的原則（保證指令重排不會破壞原有的語義結構）：

• 程式順序原則：一個線程内保證語義的串行性。
• volatile規則：volatile變量的寫，先發生于讀，這保證了volatile變量的可見性。
• 鎖規則：解鎖必然發生在随後的加鎖前
• 傳遞性：A先與B，B先于C，那麼A必然先于C。
• 線程的start()方法先于它的每一個動作
• 線程的所有寫操作先于後續所有操作
• 線程的所有操作先于線程的終結(Thread.join())
• 線程的中斷（interrupt()）先于被中斷線程的代碼
• 對象的構造函數的執行、結束先于finalize()方法