一、基礎(chǔ)概念

1、同步(Synchronous)與異步(Asynchronous)

同步和異步通常用來形容一次方法調(diào)用。

同步方法調(diào)用：一旦開始，調(diào)用者必須等到方法調(diào)用返回后，才能繼續(xù)后續(xù)的操作行為。

異步方法調(diào)用：類似一個(gè)消息傳遞，一旦開始，方法調(diào)用就會(huì)立即返回，不影響調(diào)用者執(zhí)行后續(xù)的行為。異步調(diào)用是在一瞬間完成的，如果異步調(diào)用需要返回結(jié)果，則會(huì)在異步調(diào)用真正完成時(shí)通知調(diào)用者。

2、并發(fā)(Concurrency)與并行(Parallelism)

并發(fā)和并行都可以表示兩個(gè)或多個(gè)任務(wù)一起執(zhí)行，但側(cè)重點(diǎn)不同。并發(fā)偏重于多個(gè)任務(wù)交替執(zhí)行，而多個(gè)任務(wù)之間可能還是串行的，對(duì)于外部觀察者來說，即使多個(gè)任務(wù)之間是串行并發(fā)的，也會(huì)造成多任務(wù)之間是并行執(zhí)行的錯(cuò)覺。而并行的多個(gè)任務(wù)是真正意義上的同時(shí)執(zhí)行。

如果系統(tǒng)內(nèi)只有一個(gè)CPU，使用多線程或多進(jìn)程任務(wù)，在真實(shí)環(huán)境中這些任務(wù)是不可能實(shí)際并行的，因?yàn)橐粋€(gè)CPU一次只能執(zhí)行一條指令，這種情況下多進(jìn)程或多線程就是并發(fā)的，并非是并行的（操作系統(tǒng)會(huì)不停的切換多個(gè)任務(wù))。真實(shí)的并行只可能出現(xiàn)在多核CPU中。

3、臨界區(qū)

臨界區(qū)表示一種公共資源或者共享數(shù)據(jù)，可以被多個(gè)線程使用。每一次只能有一個(gè)線程使用它，一旦臨界區(qū)資源幣占用，其他線程要想使用這個(gè)資源，就必須等待其他線程將資源釋放。在并行程序中，臨界區(qū)資源是受保護(hù)的對(duì)象。

4、阻塞(Blocking)與非阻塞(Non-Blocking)

阻塞和非阻塞通常用來形容多線程之間的相互影響，如一個(gè)線程占用了臨界區(qū)資源，那么其他所有需要這個(gè)資源的線程就必須在這個(gè)臨界區(qū)中等待。等待會(huì)導(dǎo)致線程掛起，即阻塞。如果占用資源的線程一直不釋放，則其他所有阻塞在這個(gè)臨界點(diǎn)的線程都將不能工作。

非阻塞表示沒有一個(gè)線程可以妨礙其他線程執(zhí)行，所有的線程都會(huì)不斷嘗試?yán)^續(xù)執(zhí)行。

5、死鎖(Deadlock)、饑餓(Starvation)與(Livelock)

死鎖、饑餓和活鎖都屬于多線程的活躍性問題，這幾種情況下線程可能不再活躍或者說不能繼續(xù)執(zhí)行了。

死鎖：指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過程中，由于競爭資源或者由于彼此通信而造成的一種阻塞的現(xiàn)象，若無外力作用，它們都將無法進(jìn)行下去。此時(shí)稱系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖，這些永遠(yuǎn)在互相等待的進(jìn)程稱為死鎖進(jìn)程。死鎖是一個(gè)很嚴(yán)重的問題，一旦死鎖它不能自行恢復(fù)。

一種情形，如果執(zhí)行程序中兩個(gè)或多個(gè)線程發(fā)生永久堵塞（等待），每個(gè)線程都在等待被其他線程占用并堵塞了的資源。例如線程A鎖住了記錄1并等待記錄2，而線程B鎖住了記錄2并等待記錄1，這樣兩個(gè)線程就發(fā)生了死鎖現(xiàn)象。

死鎖發(fā)生的四個(gè)必要條件：

1）互斥條件：指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用，即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用。如果此時(shí)還有其它進(jìn)程請(qǐng)求資源，則請(qǐng)求者只能等待，直至占有資源的進(jìn)程用畢釋放。

2）請(qǐng)求和保持條件：指進(jìn)程已經(jīng)保持至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其它資源保持不放。

3）不剝奪條件：指進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時(shí)由自己釋放。

4）環(huán)路等待條件：指在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程與資源的環(huán)形鏈，即進(jìn)程集合{P0，P1，P2，···，Pn}中的P0正在等待一個(gè)P1占用的資源；P1正在等待P2占用的資源，……，Pn正在等待已被P0占用的資源。

饑餓：指一個(gè)或多個(gè)線程因?yàn)槟撤N原因無法獲取到所需的資源，導(dǎo)致一直無法執(zhí)行。如它的線程優(yōu)先級(jí)可能太低，高優(yōu)先級(jí)的線程不斷搶占它所需的資源，導(dǎo)致低優(yōu)先級(jí)的線程無法工作。另外一種情況，某個(gè)線程一直占用著關(guān)鍵資源不釋放，導(dǎo)致其他需要這個(gè)資源的線程無法執(zhí)行，也會(huì)造成饑餓。與死鎖相比，它有可能在未來一段時(shí)間內(nèi)解決。

活鎖：指的是任務(wù)或者執(zhí)行者沒有被阻塞，由于某些條件沒有滿足，導(dǎo)致一直重復(fù)嘗試，失敗的過程。處于活鎖的實(shí)體是在不斷的改變狀態(tài)，活鎖有可能自行解開?；铈i可以認(rèn)為是一種特殊的饑餓。例如事務(wù)T2再不斷的重復(fù)嘗試獲取鎖R，那么這個(gè)就是活鎖?；铈i是一系列進(jìn)程在輪詢地等待某個(gè)不可能為真的條件為真。發(fā)生活鎖時(shí)的進(jìn)程是不會(huì)blocked，這會(huì)導(dǎo)致耗盡CPU資源。

活鎖和死鎖的區(qū)別在于，處于活鎖的實(shí)體是在不斷的改變狀態(tài)，而處于死鎖的實(shí)體表現(xiàn)為等待；活鎖有可能自行解開，死鎖則不能。

二、并發(fā)級(jí)別

由于臨界區(qū)的存在，多線程之間的并發(fā)需要受到控制，根據(jù)控制并發(fā)的策略，可以把并發(fā)級(jí)別分為：阻塞、無饑餓、無障礙、無鎖、無等待。

1、阻塞(Blocking)

如果一個(gè)線程是阻塞的，那么在其他線程釋放資源錢，當(dāng)前線程將無法繼續(xù)執(zhí)行。當(dāng)使用synchronized關(guān)鍵字或者重入鎖時(shí)，得到的線程就是阻塞的。它們都會(huì)試圖在執(zhí)行后續(xù)代碼前，得到臨界區(qū)的資源鎖，如果得不到，線程就會(huì)被掛起等待，直到占有了所需資源為止。

2、無饑餓(Starvation-Free)

如果線程之間有優(yōu)先級(jí)，則線程調(diào)度時(shí)總會(huì)傾向于高優(yōu)先級(jí)的線程。對(duì)于非公平的鎖來說，系統(tǒng)允許高優(yōu)先級(jí)的線程插隊(duì)，這樣可能會(huì)導(dǎo)致低優(yōu)先級(jí)的線程饑餓，如果鎖是公平的，則不會(huì)產(chǎn)生饑餓，無論線程的優(yōu)先級(jí)高低，要獲取到資源必須排隊(duì)，那么所有的線程就都有機(jī)會(huì)運(yùn)行。

3、無障礙(Obstruction-Free)

無障礙是一種最弱的非阻塞調(diào)度，如果兩個(gè)線程是無障礙的執(zhí)行，則它們都不會(huì)因?yàn)榕R界區(qū)的資源問題導(dǎo)致一方被掛起。就是說所有線程都可以修改共享數(shù)據(jù)，對(duì)于無障礙線程來說，一旦檢測(cè)到這種情況，它就會(huì)立即對(duì)自己所做修改進(jìn)行回滾，確保數(shù)據(jù)安全。若沒有發(fā)生資源競爭，那么線程可以完成任務(wù)，走出臨界區(qū)。

阻塞調(diào)度方式是一種悲觀策略，系統(tǒng)認(rèn)為兩個(gè)線程之間很可能發(fā)生沖突，時(shí)刻以保護(hù)共享數(shù)據(jù)為最高優(yōu)先級(jí)。相對(duì)的，非阻塞的調(diào)度方式就是一種樂觀的策，它認(rèn)為多個(gè)線程間很有可能不會(huì)發(fā)生沖突，大家都應(yīng)該無障礙的執(zhí)行，但一旦檢測(cè)到?jīng)_突，則應(yīng)該回滾操作。

無障礙的線程并不一定能順利的運(yùn)行，當(dāng)臨界區(qū)的資源出現(xiàn)嚴(yán)重沖突時(shí)，所有線程可能都會(huì)不斷的回滾自己的操作，從而導(dǎo)致沒有一個(gè)線程可以走出臨界區(qū)，此時(shí)將會(huì)影響系統(tǒng)的正常運(yùn)行。一種可行的無障礙實(shí)現(xiàn)方式是依賴“一致性標(biāo)記”來實(shí)現(xiàn)，線程在操作前，先讀取并保存這個(gè)標(biāo)記，在操作完成后，再次讀取，比對(duì)這個(gè)標(biāo)記是否被修改過。如果兩者一致則說明資源訪問沒有沖突，否則說明資源在操作過程中與其他寫線程產(chǎn)生沖突，需要重試操作。任何線程在對(duì)資源進(jìn)行修改前，都必須更新這個(gè)一致性標(biāo)記，表示數(shù)據(jù)不再安全。

4、無鎖(Lock-Free)

無鎖的并行都是無障礙的，在無鎖情況下，所有線程都可以嘗試對(duì)臨界區(qū)的資源訪問，不同的是，無鎖的并發(fā)保證必然有一個(gè)線程能夠在有限的步驟內(nèi)完成操作并離開臨界區(qū)。

在無鎖的調(diào)用中，一個(gè)典型的特點(diǎn)是可能會(huì)包含一個(gè)無窮循環(huán)。在此循環(huán)中，線程會(huì)不斷的嘗試修改共享變量，如果沒有沖突則修改成功，否則會(huì)繼續(xù)嘗試修改。無鎖的并行總能保證有一個(gè)線程是可以成功的。對(duì)于臨界區(qū)中競爭失敗的線程，它們必須不斷重試，直到成功為止，若總是失敗，則會(huì)出現(xiàn)類似饑餓的現(xiàn)象。

5、無等待(Wait-Free)

無等待要求所有的線程都必須在有限步內(nèi)完成，這樣不會(huì)引起饑餓問題，如果限制步驟數(shù)，可以分解為有界無等待和線程數(shù)無關(guān)的無等待的類型，它們的區(qū)別是對(duì)循環(huán)次數(shù)的限制不同。

典型的無等待結(jié)構(gòu)是RCU（Read-Copy-Update），基本思想是對(duì)數(shù)據(jù)的讀可以不加控制，所有的讀線程都是無等待的，它們不會(huì)被鎖定等待也不會(huì)引起沖突，在寫的時(shí)候先讀取原始數(shù)據(jù)的副本，接著修改數(shù)據(jù)副本，修改完成后再回寫數(shù)據(jù)。

三、并行相關(guān)的定律

1、Amdahl定律

阿姆達(dá)爾定律是計(jì)算機(jī)系統(tǒng)設(shè)計(jì)的重要定量原理之一，于1967年由IBM360系列機(jī)的主要設(shè)計(jì)者阿姆達(dá)爾首先提出。該定律是指：系統(tǒng)中對(duì)某一部件采用更快執(zhí)行方式所能獲得的系統(tǒng)性能改進(jìn)程度，取決于這種執(zhí)行方式被使用的頻率，或所占總執(zhí)行時(shí)間的比例。阿姆達(dá)爾定律實(shí)際上定義了采取增強(qiáng)（加速）某部分功能處理的措施后可獲得的性能改進(jìn)或執(zhí)行時(shí)間的加速比。它定義了串行系統(tǒng)并行化后的加速比的計(jì)算公式和理論上限。

加速比定義：加速比 =?優(yōu)化前系統(tǒng)耗時(shí) /?優(yōu)化后系統(tǒng)耗時(shí)

公式：S = 1 / (1 - a + a / n)

其中，a為并行計(jì)算部分所占比例，n為并行處理結(jié)點(diǎn)個(gè)數(shù)。

當(dāng)1-a=0時(shí)，(即只有并行)最大加速比s=n；

當(dāng)a=0時(shí)（即只有串行），最小加速比s=1；

當(dāng)n→∞時(shí)，極限加速比s→ 1/(1-a），也就是加速比的上限。

加速比就是優(yōu)化前的耗時(shí)與優(yōu)化后耗時(shí)的比值，加速比越高，表明優(yōu)化效果越明顯。根據(jù)Amdahl定律，使用多核CPU對(duì)系統(tǒng)進(jìn)行優(yōu)化，優(yōu)化的效果取決于CPU的數(shù)量以及系統(tǒng)中的串行化程序的比重。CPU數(shù)量越多，串行化比重越低，則優(yōu)化效果越好。僅提高CPU數(shù)量而不降低程序的串行化比重，無法系統(tǒng)性能。

2、Gustafson定律

gustafson 定律：系統(tǒng)優(yōu)化某部件所獲得的系統(tǒng)性能的改善程度，取決于該部件被使用的頻率，或所占總執(zhí)行時(shí)間的比例。

gustafson定律在Amdahl定律的基礎(chǔ)上提出，但思想角度不同。

執(zhí)行時(shí)間： 串行時(shí)間a + 并行時(shí)間b

優(yōu)化后時(shí)間： a + nb

加速比： (a + nb) / (a + b)

f串行比例 ： a / (a + b)

如果串行化比例很小，并行化比例很大，那么加速比就是處理器的個(gè)數(shù)。只要不斷的增加處理器，就可以獲得更快的速度。

Amdahl定律強(qiáng)調(diào)：當(dāng)串行比例一定時(shí)，加速比是有上限的，不管你增加了多少CPU都不可能突破這個(gè)上限。

Gustafson定律：如果可被并行化的代碼所占比重足夠多，那么加速比就能隨著CPU的數(shù)量線性增長。

兩個(gè)定律最低點(diǎn)、最高點(diǎn)都是一致的結(jié)論：

無可并行的程序，加速比就是1。

全部是并行程序，加速比就是n。

四、Java內(nèi)存模型（JMM）

1、原子性(Atomicity)

原子性是指一個(gè)操作是不可中斷的，即使是在多個(gè)線程一起執(zhí)行的時(shí)候，一個(gè)操作一旦開始就不會(huì)被其他線程影響。如：一個(gè)靜態(tài)全局變量int i，2個(gè)線程同時(shí)對(duì)它賦值，線程A賦值1，線程B賦值2，那么不管這2個(gè)線程以何種方式運(yùn)行，i的值要么是1，要么是2，這2個(gè)線程之間是沒有干擾的。如果將int類型換為long的話就未必是這樣了，對(duì)于32位系統(tǒng)來說，long類型的數(shù)據(jù)讀寫不是原子性的，long有64位長度。若兩個(gè)線程同時(shí)對(duì)long寫入的話，對(duì)線程之間的結(jié)果是有影響的。

2、可見性(Visibility)

可見性是指當(dāng)一個(gè)線程修改了某個(gè)共享變量值，其他線程是否能立即知道這個(gè)修改。對(duì)于串行程序而言不存在可見性問題。對(duì)于并行程序來說，如果一個(gè)線程修改了某個(gè)全局變量，其他線程未必會(huì)立刻知道這個(gè)改動(dòng)。比如在CPU1和CPU2各有一個(gè)線程，它們共享變量t，由于編譯器優(yōu)化或硬件優(yōu)化的原因，在CPU1的線程將t進(jìn)行了優(yōu)化，并緩存在cache或寄存器里。此時(shí)CPU2上的線程修改了t的值，那么CPU1上的線程可能無法知道這個(gè)改動(dòng)，依然讀取使用cache或寄存器里值，這樣就產(chǎn)生了數(shù)據(jù)可見性問題。

導(dǎo)致可見性問題的原因有緩存優(yōu)化或者硬件優(yōu)化、指令重排及編譯器的優(yōu)化等。

3、有序性(Ordering)

對(duì)于一個(gè)線程的執(zhí)行代碼而言，我們總是習(xí)慣性的認(rèn)為代碼的執(zhí)行是從先往后依次執(zhí)行的，在一個(gè)線程內(nèi)這樣理解并無問題，但是在并發(fā)時(shí)，程序的執(zhí)行可能會(huì)出現(xiàn)亂序。造成的感覺就是：前面的代碼會(huì)在后面執(zhí)行。有序性問題的原因是因?yàn)槌绦蛟趫?zhí)行時(shí)，可能會(huì)進(jìn)行指令重排，重排后的指令與原指令的順序未必一致?？此朴悬c(diǎn)奇怪，但它的確可能存在。線程A的指令執(zhí)行順序在線程B看來是沒有保證的，兩個(gè)線程可能執(zhí)行順序一致，也可能不一致。

指令重排的前提是：保證串行語義的一致性。即指令重排不會(huì)使串行的語義邏輯發(fā)生問題。它可以保證串行語義的一致性，但并無法保證多線程間的語義也一致。

指令的執(zhí)行步驟：

1）取指 IF

2）譯碼和取寄存器操作數(shù) ID

3）執(zhí)行或有效地址計(jì)算 EX

4）存儲(chǔ)器訪問 MEM

5）寫回 WB

由于一個(gè)步驟可能使用不同的硬件完成，工程師發(fā)明了流水線技術(shù)來執(zhí)行指令，原理如下：

指令1：IF? ?ID? ?EX? ?MEM? ? WB

指令2：? ? ? IF? ? ID? ? EX? ? ? ?MEM? ? WB

當(dāng)執(zhí)行指令2時(shí)，第一條指令其實(shí)并未執(zhí)行完，只是剛?cè)×酥刀?。假如每一步都需要花費(fèi)1ms，那么指令2等待指令1完全執(zhí)行完再執(zhí)行，需要等待5ms，而是用流水線后，指令2只需等待1ms就可以執(zhí)行，對(duì)性能的提升相當(dāng)明顯。

流水線可以讓CPU高效的運(yùn)行，在滿載時(shí)性能很高，但一旦中斷，所有的硬件設(shè)備都會(huì)進(jìn)入一個(gè)停頓期，再次滿載又需要幾個(gè)周期，性能損失會(huì)很大，故必須盡力保證流水線不中斷。指令重排就是為了盡量少的中斷流水線。

4、哪些指令不能重排：Happen-Before規(guī)則

1）程序順序原則：一個(gè)線程內(nèi)保證語義的串行性

2）volatile規(guī)則：volatile變量的寫，先發(fā)生于讀，保證了volatile變量的可見性

3）鎖規(guī)則：解鎖必然發(fā)生在隨后的加鎖前

4）傳遞性：A先于B，B先于C，那么A必然先于C

5）線程的start()先于它的每一個(gè)動(dòng)作

6）線程的所有操作先于線程的終結(jié)(Thread.join())

7）線程的中斷(interrupt())先于被中斷線程的代碼

8）對(duì)象的構(gòu)造函數(shù)執(zhí)行與結(jié)束先于finalize()方法

--參考文獻(xiàn)《實(shí)戰(zhàn)Java高并發(fā)程序設(shè)計(jì)》