# Chapter 1-1. Basics

在並發(**Concurrency**)環境下, 我們需要處理兩個關鍵問題:

* 執行緒之間**如何通信** (所謂的通信, 指的是執行緒之間透過何種機制來交換訊息)
* 執行緒之間**如何同步**

在命令式編程(Imperative programming)中, 執行緒之間的通信機制有兩種:

* **共享記憶體 (shared memory)**: 在此種並發模型裡, 執行緒之間共享程式的公共狀態, 執行緒之間通過讀寫記憶體中的公共狀態來**隱式地**進行通信.
* **消息傳遞**: 執行緒之間沒有公共狀態, 執行緒之間必須通過明確的發送消息來**顯式地**進行通信.

同步: 意為程式用於控制不同執行緒之間操作發生的相對順序之機制, 依模型分類如下:

* 共享記憶體(shared memory model): 同步是顯式(explicitly)進行的, 我們必須顯式地指定某個方法或某段程式需要在執行緒之間互斥執行.
* 訊息傳遞: 由於訊息的發送必須在訊息的接收之前, 因此同步是隱式(implicitly)進行的.

**Java Concurrency採用shared memory model, Java thread之間的通信總是隱式地進行.**

## Java Memory Model的抽象

* 在Java中, 所有instance field, static field和陣列元素都儲存在heap memory中, heap memory在執行緒之間共享(以下皆以"共享變數"代表instance field, static field 與陣列元素).
* 區域變數(Local variables), 方法定義參數(formal method parameters)和例外處理器參數(exception handler parameters)不會在執行緒之間共享, 它們不會有記憶體能見度的問題, 也不受記憶體模型的影響.

**Java執行緒之間的通信由Java記憶體模型(Java Memory Model, JMM, a.k.a JSR-133)控制, JMM決定一個執行緒對共享變數的寫入何時對另一個執行緒可見.**

從抽象的角度來看, JMM定義了執行緒和主記憶體(main memory)之間的抽象關係:

* 執行緒之間的共享變數儲存在主記憶體中, 每個執行緒都有一個私有的區域記憶體(local memory), 區域記憶體中儲存了該執行緒用以讀寫共享變數的副本.區域記憶體是JMM的一個抽象概念, 它並不是真實存在的. 其涵蓋了快取(cache), 寫緩衝區(write buffer), 暫存器以及其他的硬體和編譯器最佳化. JMM的抽象示意圖如下: ![](https://250052241-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o32Rq-1H1Odaot0%2F-M523qKctpHr_YtEUjVW%2F-M523rKh7oNHZuZQkC8y%2Fjmm-01.png?generation=1587042027679878\&alt=media)

單就這張圖來看, 執行緒A跟B之間要通信的話, 基本上要經過以下兩步驟:

* 執行緒A把區域記憶體中更新過的共享變數更新到主記憶體裡去.
* 執行緒B到主記憶體去讀取執行緒A之前已經更新過的共享變數.

流程示意圖如下:\
![](https://250052241-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o32Rq-1H1Odaot0%2F-M523qKctpHr_YtEUjVW%2F-M523rKjBpdZ-ph_IoC5%2Fjmm-02.png?generation=1587042026484479\&alt=media)

* 如上圖所示, 區域記憶體A與B有主記憶體中共享變數foo的副本. 假設初始狀態時, 這三個記憶體中的foo都為0. 執行緒A在執行時, 把更新後的foo(假設foo=1)臨時存放在區域記憶體A中.當執行緒A和B需要通信時, 執行緒A首先會把自己區域記憶體中修改後的foo更新至主記憶體中, 此時主記憶體中的foo就變成了1. 再來, 執行緒B到主記憶體中去讀取執行緒A更新後的foo, 然後執行緒B的區域記憶體的foo也變為了1. 從整體來看, 這兩個步驟實質上是執行緒A在向執行緒B發送訊息, 且此通信過程必須要經過主記憶體.
* JMM通過控制主記憶體與每個執行緒的區域記憶體之間的互動, 來為Java developer提供記憶體可見性的保證.

## 重排序

* 在執行程式時為了要提高性能, 編譯器和處理器常常會對指令做重排序的動作. 重排序大致可分為以下三種:
  * 編譯器最佳化的重排序: 編譯器在不改變單一執行緒程式語意的前提下, 可以重新安排語句的執行順序
  * 指令級平行的重排序: 現代的處理器採用了指令級平行技術(Instruction-Level Parallelism, LIP)來將多條指令重疊執行. 如果不存在資料相依性, 處理器可以改變語句對應機器指令的執行順序.
  * 記憶體系統的重排序: 由於處理器使用快取和讀/寫緩衝區, 這使得加載和儲存操作看上去可能是在亂序執行.
* 從Java原始碼到最終實際執行的指令序列, 分別會經歷下面三種重排序:![](https://250052241-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o32Rq-1H1Odaot0%2F-M523qKctpHr_YtEUjVW%2F-M523rKlVDNb9gUYPaZx%2Fjmm-03.png?generation=1587042027186472\&alt=media)
  * 上述的1屬於編譯器重排序, 2與3都屬於處理器重排序. 這些重排序都可能會導致多執行緒程式出現記憶體可見性的問題. 對於編譯器, JMM的編譯器重排序規則會禁止特定類型的編譯器重排序(並不是所有的編譯器重排序都要禁止). 對於處理器重排序, JMM的處理器重排序規則會要求Java編譯器在生成指令序列時, 插入特定類型的記憶體屏障(memory barriers, intel稱之為memory fence)指令, 通過對記憶體屏障指令來禁止特定類型的處理器重排序(並非所有的處理器重排序都要禁止).
* JMM屬於語言級的記憶體模型, 其確保在不同的編譯器和不同的處理器平台之上, 通過禁止特定類型的編譯器重排序和處理器重排序, 為開發者提供一致的記憶體可見性保證.

## 處理器重排序與記憶體屏障指令

* 現在的處理器使用寫緩衝區來臨時保存向記憶體寫入的資料. 寫緩衝區可以保證指令的pipeline持續運行, 其可以避免由於處理器停頓下來等待向記憶體寫入資料而產生的延遲. 同時, 通過以批次處理的方式刷新寫緩衝區, 以及合併寫緩衝區中對同一記憶體位址的多次寫入動作, 可以減少對memory bus的佔用. 雖然寫緩衝區有這麼多好處, 但每個處理器上的寫緩衝區, 僅僅對其所在的處理器可見. 這個特性會對記憶體操作的執行順序產生重要的影響, 即: 處理器對記憶體的讀/寫操作的執行順序, 不一定與記憶體實際發生的讀/寫操作順序一致. 為了具體說明, 請見以下範例:\
  ![](https://250052241-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o32Rq-1H1Odaot0%2F-M523qKctpHr_YtEUjVW%2F-M523rKnB1knzp6zYga8%2Fjmm-04.png?generation=1587042025431159\&alt=media)
* 假設處理器A和處理器B按程式的順序平行執行記憶體存取, 最終卻可能得到x = y = 0的結果. 具體的原因如下圖所示:![](https://250052241-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o32Rq-1H1Odaot0%2F-M523qKctpHr_YtEUjVW%2F-M523rKpDevtc8PYn-3h%2Fjmm-05.png?generation=1587042027378184\&alt=media)
* 這裡處理器A和處理器B可以同時把共享變數寫入自己的寫緩衝區(A1 and B1), 然後從記憶體中讀取另一個共享變數(A2 and B2),\
  最後才把自己的寫緩衝區中保存的髒資料更新至記憶體中(A3 and B3). 當以這種時序執行時, 程式就可以得到x = y = 0的結果.
* 從記憶體操作實際發生的順序來看, 直到處理器A執行A3來更新自己的寫緩衝區, 寫操作A1才算真正執行了. 雖然處理器A執行記憶體操作的順序為: A1 -> A2, 但記憶體操作實際發生的順序卻是: A2 -> A1(因為把A1真正的動作完全作用到主記憶體上是在A3才完成). 此時, 處理器A的記憶體操作順序被重排序了(處理器B的情況與處理器A一樣).
* 這裡的關鍵是, 由於寫緩衝區僅對自己的處理器可見, 其會導致處理器執行記憶體操作的順序可能會與記憶體實際的操作執行順序不一致. 由於現代的處理器都會使用寫緩衝區, 因此現代的處理器都會允許對寫/讀操作進行重排序.
* 下表是常見處理器允許的重排序類型列表:\
  ![](https://250052241-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o32Rq-1H1Odaot0%2F-M523qKctpHr_YtEUjVW%2F-M523rKrDw-LCH-eKCd2%2Fjmm-06.png?generation=1587042025667517\&alt=media)\
  上表單元格中的"N"表示處理器不允許兩個操作重排序, "Y"表示允許重排序.
* 從上表我們可以得知:
  * 常見的處理器都允許Store-Load重排序
  * 常見的處理器都不允許對存在資料依賴性的操作進行重排序
  * sparc-TSO和x86擁有相對較強的處理器記憶體模型, 它們僅允許對寫-讀操作進行重排序(因為它們都使用了寫緩衝區)
    * 註1: sparc-TSO是指以TSO(Total Store Order)記憶體模型運作時, sparc處理器的特性.
    * 註2: 上表中的x86包含了x64與AMD64
    * 註3: 由於ARM處理器的記憶體模型與PowerPC處理器的記憶體模型非常類似, 本文將忽略之
* 為了保證記憶體可見性, Java編譯器在生成指令序列的適當位置會插入記憶體屏障指令來禁止特定類型的處理器重排序. JMM把記憶體屏障指令分為下列四類:\
  ![](https://250052241-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o32Rq-1H1Odaot0%2F-M523qKctpHr_YtEUjVW%2F-M523rKtOXwDXRYdshKv%2Fjmm-07.png?generation=1587042027379162\&alt=media)
* StoreLoad Barriers是一個"全能型"的屏障, 其同時具有其他三個屏障的效果. 現代的多處理器大多都支援該屏障(其他類型的屏障不一定被所有處理器支持). 執行該屏障開銷會很昂貴, 因為當前處理器通常要把寫緩衝區中的資料全部更新至記憶體中(buffer fully flush).

## Happens-Before

* 從JDK5開始, Java使用新的JSR-133記憶體模型(在這篇筆記裡除非特別說明, 針對的都是JSR-133記憶體模型)
* JSR-133提出了happens-before的概念, 通過這個概念來闡述操作之間的記憶體可見性. 若一個操作執行的結果需要對另一個操作可見, 那麼這兩個操作之間必須存在happens-before關係. 這裡提到的兩個操作既可以是在一個執行緒之內, 也可以是在不同執行緒之間. 與軟體開發人員密切相關的happens-before規則如下:
  * **程式順序規則**: 一個執行緒中的每個操作, happens-before於該執行緒中的任意後續操作.
  * **Monitor Lock規則**: 對一個Monitor Lock的解鎖, happens-before於隨後對這個monitor lock的上鎖.
  * **volatile變數規則**: 對一個volatile field的寫入, happens-before於任意後續對這個volatile field的讀取.
  * **遞移律**: 若A happens-before B, 且B happens-before C, 那麼A happens-before C.
* 值得注意的是, 兩個操作之間具有happens-before關係, 並不意味著前一個操作必須要在後一個操作之前執行, happens-before僅僅要求前一個操作(執行的結果)對後一個操作可見, 且前一個操作按順序排在第二個操作之前 (the first is visible to and ordered before the second).
* Happens-before與JMM的關係可用下圖簡單表示:![](https://250052241-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o32Rq-1H1Odaot0%2F-M523qKctpHr_YtEUjVW%2F-M523rKvTwdwmypyTos1%2Fjmm-08.png?generation=1587042027797634\&alt=media)\
  如上圖所示, 一個happens-before規則通常會對應於多個編譯器重排序規則和處理器重排序規則. 對Java developer來說, happens-before規則簡單易懂, 其避免開發人員為了理解JMM提供的記憶體可見性保證而去學習複雜的重排序規則以及這些規則的具體實作.

## 記憶體語意(Memory Semantics)

在接下來的JMM系列中, 會一直提到**記憶體語意**這個名詞, 所以我想在這先說明一下這個詞彙的意思, 若是在[wikipedia](https://en.wikipedia.org/wiki/Memory_semantics_\(computing\))上看, 其意思為:

> In computing and parallel processing, memory semantics refers to the process logic used to control access to shared memory locations, or at a higher level to shared variables in the presence of multiple threads or processors.
>
> Memory semantics may also be defined for transactional memory, where issues related to the interaction of transactions and locks, and user-level actions need to be defined and specified.

讓我們講中文:

> 在計算機的計算與平行處理中, 記憶體語意指的是用來**控制對共享記憶體位置存取的進程邏輯**, 或是在較高層級(如多執行緒與處理器)之概念中的**共享變數**上.
>
> 記憶體語意也可以為事務性記憶體定義, 而當中涉及事務與鎖的互動以及使用者級別操作的問題需要被定義與指定.

其實這在接下來的context中還是太廣泛與抽象了一點, 所以若要再講得更白話一點的話, 個人認為你可以把記憶體語意想成是: **Java的記憶體模型, 或著說是synchronized/volatile/lock/atomic這類保留字在JVM中的實作原則, 即JVM碰到這些保留字的時候, 它會怎麼去處理記憶體層級上的互動跟一些問題.**
