multi-threading

https://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html

https://docs.oracle.com/cd/E19205-01/820-0619/geojs/index.html

http://www.ibm.com/developerworks/cn/java/j-jtp06197.html

http://blog.csdn.net/crazyjmonkey/article/details/8538602

http://hllvm.group.iteye.com/group/topic/34975

JLS8

Threads and Locks

Java語言支援多線程，多線程程式的每個線程單獨的執行代碼，來操作位于主存的對象和值資料（通信）。通過時間分片技術，多個處理器、單個處理器都支援Java多線程。

在Java裡Thread類表示多線程，建立Thread類的一個對象是建立多線程的唯一方式；每一個線程都關聯這這樣一個對象。通過調用相應Thread上的start方法來啟動一個線程。

線程的行為，特别是沒有正确地同步的時候，可能會令人費解和違反直覺。這章描述了多線程的語義，它包含了多線程更新了共享記憶體，值可能會對某個讀可見的規則。因為這種規範（指多線程語義規範）類似于硬體的記憶體體系架構，這些語義也被稱為Java程式設計語言記憶體模型（Java programming language memory model）。在沒有混淆的情況下，我們稱這些規則為“記憶體模型”。

這些語義規則沒有規定多線程程式應該如何來執行，而是描述了多線程程式允許出現的行為。任何隻産生被允許行為的執行政策都是可接收的執行政策。

Synchronization

Java程式設計語言提供了多種機制來讓多線程之間通信。其中最基本的方法是利用螢幕（monitor）實作的同步（synchronization）。（此處直譯的，筆者認為前面兩句話描述有些不妥。。。）Java裡的每一個對象都關聯着一個monitor，一個線程可以在monitor上lock和unlock。在某一時刻，隻有一個線程可以持有一個monitor上的lock。任何其它試圖lock那個monitor的線程都會被block，直到能擷取那個monitor上的lock為止。一個線程t可以lock一個鎖多次，每次unlock撤銷一個lock操作的影響。

被同步（synchronized）的語句計算對Object對象的引用，然後試圖在那個Object的monitor上執行lock操作，被同步的語句不會進一步的執行直到lock操作成功執行完成。lock被執行後，同步的語句（body）會被執行。當（body）執行完，或成功或發生意外，unlock操作會在那個monitor上自動的被執行。

同步方法被調用時，lock操作會自動被執行；方法體直到lock操作成功完成後才會執行。如果方法是執行個體方法（instance method）,會lock被調用的方法的執行個體的monitor（這個執行個體即被執行方法體所在的對象）。如果方法是靜态的（static），會lock方法被定義的class所代表的Class對象上的monitor。如果方法體執行完，或成功或發生意外，unlock操作會在那個monitor上自動的被執行。

Java程式設計語言不阻止也不檢測死鎖條件（deadlock conditions），多線程lock住多個對象的情況應該用正常的技術避免死鎖，如果有必要，建立進階别的鎖原語避免死鎖。

其它機制，比如讀寫volatile變量和利用java.util.concurrent包來提供其他同步方式。

Wait Sets and Notification

每個對象除了關聯一個monitor以外，還關聯wait set，wait set是線程集合。

當一個對象第一次被建立，它的wait set是空的。在wait set上的添加、删除基本操作是原子操作。wait set隻被Object.wait、Object.nofify和Object.notifyAll來操控。

wait set的操控會被線程的中斷狀态和Thread 類裡的方法進行中斷影響。此外，Thread類的方法sleep和join擁有的性質源自那些wait和notification動作。

Yield, sleep, join do not bother about locks. But Object.wait will release the lock

Wait

調用wait方法發生wait動作。

如果線程沒有抛出InterruptedException則從wait中正常傳回。

讓線程t在對象m上執行了wait方法，n是t在m上執行的lock次數，會發生以下其中一個動作

　　如果n是0，則抛出IllegalMonitorStateException（調用wait之前必須持有鎖）

　　如果是time wait，納秒參數不在0-999999之間，或毫秒參數是負數，會抛出IllegalArgumentException

　　如果線程t被中斷，會抛出InterruptedException，t的中斷狀态置為false

　　否則按以下序列執行：

　　　　1.線程t加到對象m的wait set中，在m上執行n次unlock操作

　　　　2.線程t不執行任何指令，直到它被在m的wait set中移除。以下任何動作都會引起移除wait set，繼續執行後面的操作

　　　　　　執行了m上的notify方法，t被選中，移除wait set

　　　　　　執行了m上的notifyAll方法

　　　　　　在t上執行了interrupt方法

　　　　　　如果是time wait，指定的時間到了

　　　　3.線程t在m上執行n次lock操作

　　　　4.如果因為interrupt線程t在m的wait set中移除，t的interruption 狀态置為false，wait方法抛出InterruptedException

Notification

執行notify，notifyAll必須持有鎖，否則抛出IllegalMonitorStateException

Interruptions

Interactions of Waits, Notification, and Interruption

如果一個線程在等待時，interrupt和notify都發生了，它可能會：

　　從wait中正常傳回，還有一個pending的interrupt（換句話說，Thread.interrupted()傳回true）

　　從wait中傳回，抛出InterruptedException

Sleep and Yield

Thread.sleep會使目前線程睡眠指定時間，線程不會失去lock的所有權，線程恢複執行依賴于排程

sleep和yield沒有同步語義，特别的，在sleep和yield之前，編譯器不會把緩存到寄存器的寫同步到主存，在sleep和yield之後，編譯器也不會重新加載在寄存器中緩存的資料

For example, in the following (broken) code fragment, assume that this.done is a non-volatile boolean field:

while (!this.done)
    Thread.sleep(1000);
The compiler is free to read the field this.done just once, and reuse the cached value in each execution of the loop. This would mean that the loop would never terminate, even if another thread changed the value of this.done.      

Memory Model

JMM描述了程式可能的行為，隻要程式的執行結果是可預測的，code都可以自由實作

這帶來了很大的自由執行code轉變，包括重排序和移除不必要的同步等。

Example 17.4-1. Incorrectly Synchronized Programs May Exhibit Surprising Behavior

java語言的語義運作編譯器和處理器執行優化，優化和不正确的同步代碼互相作用會産生看起來奇怪的行為

幾種機制可以産生重排序，jit編譯器， 處理器，記憶體

Shared Variables

線程間可共享的記憶體稱為共享記憶體或堆記憶體，執行個體變量類變量和數組都存儲在堆記憶體上；本地變量，方法參數，異常處理器參數不被線程共享，不受JMM影響

多個線程通路同一個變量，至少有一個讀，這種情況稱為沖突

Actions

inter-thread actions：

Read  read a variable

Write write a variable

Synchronization actions　

　　volatile read 

　　volatile write 

　　Lock

　　Unlock

　　The (synthetic) first and last action of a thread.

　　Actions that start a thread or detect that a thread has terminated

External Actions. An external action is an action that may be observable outside of an execution, and has a result based on an environment external to the execution.

Thread divergence actions . A thread divergence action is only performed by a thread that is in an infinite loop in which no memory, synchronization, or external actions are performed. If a thread performs a thread divergence action, it will be followed by an infinite number of thread divergence actions.

本規範隻關心inter-thread actions，簡稱inter-thread actions為Actions

一個action通過一個元組描述<t,k,v,u>

t，執行動作的線程

k，action的種類

v，action中涉及的變量或monitor

u，action的任意唯一标志符

所謂intra-thread語義就是單個線程執行某條代碼路徑的時候，不管是否存在重排序等操作，在執行結果上都會表現出與源碼一緻的結果。比如這個代碼路徑中有一個寫入變量v的操作o1，隻要中間沒有再寫該變量，後續就能讀到之前o1寫的值

Programs and Program Order

program order意為線程t執行的所有的inter-thread Action都表現出了intra-thread的語義。 

每次對變量v的讀操作r都能看到寫操作w寫入v的值，隻要存在下面的條件： 

·執行順序上w在r之前； 

·且不存在這樣寫操作w'，執行順序上w在w'之前，w'在r之前。 

Program Order是順序一緻（Sequential consistency）的。順序一緻性是可見性的強有力保證。

Synchronization Order

每個線程t中synchronization action的synchronization order是與Program Order一緻的。 

Synchronization action之間的synchronized-with關系有如下幾種： 

1、解鎖monitor m synchronized-with 後續 鎖定monitor m； 

2、volatile寫變量v synchronized-with 後續對該變量的 volatile讀； 

3、啟動一個線程 synchronizes-with 線程中的首個action； 

4、變量寫入預設值 synchronizes-with 線程中的首個action； 

5、線程t1中的最後一個action  synchronizes-with 線程t2中檢測t1是否終止的action（如t1.isAlive() 或 t1.join()）； 

6、若t1中斷t2，該中斷 synchronizes-with 任意時刻其它線程（包括t2）發現t2被中斷了（通過抛出InterruptedException或調用 Thread.interrupted、Thread.isInterrupted）。

synchronized-with有向邊的源叫做release，終點叫做acquire

Happens-before Order

兩個action可以被 happens-before排序，如果一個action happens-before另外一個，則第一個對第二個是可見的

用hb(x,y)表示x happens-before y。 

1、如果x，y在同一個線程裡，x在program order上在y之前，則hb(x, y). 

2、構造方法的結束 happens-before finalizer的開始。也就是說構造方法中對字段的寫操作的最新值在finalize中一定是可見的。 

3、如果 x synchronizes-with y, 那麼hb(x, y). 

4、如果hb(x, y)并且hb(y, z), 那麼 hb(x, z). 

Executions

Well-Formed Executions

Executions and Causality Requirements

final Field Semantics

 volatile

• 可見性。對一個volatile變量的讀，總是能看到（任意線程）對這個volatile變量最後的寫入。
• 原子性：對任意單個volatile變量的讀/寫具有原子性，但類似于volatile++這種複合操作不具有原子性。

final

• • 在構造函數内對一個final域的寫入，與随後把這個被構造對象的引用指派給一個引用變量，這兩個操作之間不能重排序。
  • 初次讀一個包含final域的對象的引用，與随後初次讀這個final域，這兩個操作之間不能重排序。

當線程有資料依賴性的的操作不會被重排序

as-if-serial語義，單線程中不管如何重排序，程式的執行結果不會被改變，編譯器，處理器都必須遵守這個語義

http://ifeve.com/java-memory-model-5/

鎖的語義通過volatile和cas（）來實作的。

cas intel x86 程式根據cpu類型決定是否在cmpxchg指令前加lock字首

lock字首

1.通過總線鎖/緩存鎖確定讀寫原子性

2.禁止重排序

3.重新整理緩沖區到記憶體

AQS

http://ifeve.com/introduce-abstractqueuedsynchronizer/

http://ifeve.com/jdk1-8-abstractqueuedsynchronizer/

http://ifeve.com/jdk1-8-abstractqueuedsynchronizer-part2/

http://www.liuinsect.com

http://www.pwendell.com/2012/08/13/java-lock-free-deepdive.html

轉載于:https://www.cnblogs.com/ukouryou/articles/3535443.html