串行（Sequential）痰滋、并發(fā)（Concurrent）筐摘、并行（Parallel）

目標(biāo)：將串行計算改為并發(fā)乃至并行計算

競態(tài)（Race Condition）

1芯丧、競態(tài)是指計算的正確性依賴于相對時間順序（Relative Timing）或者線程的交錯（Interleaving）稍计。一個計算結(jié)果的正確性與時間有關(guān)的現(xiàn)象就被稱為競態(tài)席赂。

2援雇、競態(tài)表現(xiàn)為計算的結(jié)果事兒正確時而錯誤矛渴。、

3惫搏、二維表分析法是分析和解釋競態(tài)的有效和常用工具具温。

4、一個類能夠?qū)е赂倯B(tài)筐赔，那么它就不是線程安全的铣猩。

5、線程安全意味著不存在競態(tài)茴丰，但是不存在競態(tài)卻未必是線程安全达皿。

6、保障操作的原子性可以消除競態(tài)贿肩。

7峦椰、競態(tài)模式：

7.1、read-modify-write

7.2尸曼、check-then-act

線程安全性

一般而言们何，如果一個類在單線程環(huán)境下能夠運(yùn)作正常，并且在多線程環(huán)境下控轿，在其使用方不必為其做任何改變的情況下也能運(yùn)作正常冤竹，那么就稱其是線程安全（Thread-safe）的，相應(yīng)地稱這個類具有線程安全性（Thread Safety）

1茬射、線程安全問題包括原子性（Atomic）鹦蠕、可見性（Visibility）、有序性（Ordering）

1.1在抛、原子性的保障能夠消除競態(tài)钟病。原子性和可見性一同得以保障了一個線程能夠共享變量的相對新值「账螅可見性是有序性的基礎(chǔ)肠阱，而有序性可能影響可見性

2、原子性

對于設(shè)計共享變量訪問的操作朴读，若該操作從其執(zhí)行線程以外的任意線程看來是不可分割的屹徘，那么該操作就是原子操作，并且該操作具有原子性衅金。

2.1噪伊、原子操作具有不可分割性：兩層含義簿煌，a、一個線程無法看到其他線程的中間結(jié)果;b鉴吹、原子操作無法被交錯

2.2姨伟、對 long/double型以外的任何變量的寫操作都是原子的

2.3、volatile能夠保障變量寫操作的原子性

3豆励、可見性

在多線程環(huán)境下夺荒，一個線程多某個共享變量進(jìn)行更新后，后續(xù)訪問該變量的線程可能無法立刻讀取甚至永遠(yuǎn)無法讀取到這個更新的結(jié)果肆糕。這就是線程安全問題的可見性

3.1般堆、可見性問題并非必然出現(xiàn)

3.2、軟件和硬件的因素都可以導(dǎo)致可見性問題

3.3诚啃、線程啟動與可見性：父線程在啟動子線程之前對共享變量的更新對于子線程來說是可見的。

3.4私沮、線程終止與可見性：一個線程終止后該線程對共享變量的更新對于調(diào)用該線程的join方法的線程而言是可見的

4始赎、有序性

指在什么情況下一個處理器上運(yùn)行的一個線程所執(zhí)行的內(nèi)存訪問操作在另外一個處理器上運(yùn)行的其他線程看來是亂序的（out of order）

4.1、重排序

4.1.1仔燕、重排序類型：指令重排序和存儲子系統(tǒng)重排序（內(nèi)存重排序（Memory Ordering））

源代碼順序與程序順序不一致造垛，或者程序順序與執(zhí)行順序不一致，就會發(fā)生指令重排序（Instruction Reorder）晰搀。編譯器五辽、運(yùn)行時和處理器導(dǎo)致指令重排序。

源代碼順序外恕、程序順序和執(zhí)行順序三者保持一致杆逗，但是感知順序和執(zhí)行順序不一致，就會發(fā)生內(nèi)存重排序

4.1.2鳞疲、內(nèi)存重排序類型：LoadLoad重排序罪郊，StoreStore重排序、LoadStore重排序尚洽、StoreLoad重排序悔橄。

4.1.3、貌似串行語義（As-if-serial Semantics）

重排序并非隨意地對指令腺毫、內(nèi)存操作的結(jié)果進(jìn)行雜亂無章的排序或者順序調(diào)整癣疟，而是遵循一定的規(guī)則。

編譯器（主要是JIT編譯器）潮酒、處理器（包括其存儲子系統(tǒng)）都會遵守這些規(guī)則睛挚，

從而給單線程程序創(chuàng)造一種假象──指令是按照源代碼順序執(zhí)行的。這種假象就被稱為貌似串行語義澈灼。

貌似串行語義只是從單線程程序的角度保證重排序后的運(yùn)行結(jié)果不影響程序的正確性竞川，它并不保證多線程環(huán)境下程序的正確性店溢。

4.1.4、數(shù)據(jù)依賴關(guān)系(Data Dependency)

為了保證貌似串行語義委乌，存在數(shù)據(jù)依賴關(guān)系的語句不會被重排序床牧，只有不存在數(shù)據(jù)依賴關(guān)系的語句才會被重排序。

如果兩個操作(指令)訪問同一個變量(地址)遭贸，且其中一個操作(指令)為寫操作戈咳，

那么這兩個操作之間就存在數(shù)據(jù)依賴關(guān)系，這些操作包括：寫后讀(WAR)壕吹、讀后寫(RAW)著蛙、寫后寫(WAW)三種操作。

4.1.5耳贬、控制依賴關(guān)系(Control Dependency)

如果一條語句（指令）的執(zhí)行結(jié)果會決定另外一條語句（指令）能否被執(zhí)行踏堡，

那么這兩條語句（指令）之間就存在控制依賴關(guān)系。存在控制依賴關(guān)系的語句是可以允許被重排序的咒劲，

存在控制依賴關(guān)系的語句最典型的就是if語句中的條件表達(dá)式和相應(yīng)的語句體顷蟆。

允許這種重排序意味著處理器可能先執(zhí)行f語句體所涉及的內(nèi)存訪問操作，然后再執(zhí)行相應(yīng)的條件判斷腐魂。

允許對存在控制依賴關(guān)系的語句進(jìn)行重排序同樣也是出于性能考慮帐偎，

這是因為存在控制依賴關(guān)系的語句(如if語句)會影響處理器對指令序列執(zhí)行的并行程度。

4.1.6蛔屹、保障內(nèi)存訪問順序

貌似串行語義只是保障重排序不影響單線程程序的正確性削樊，從這個角度出發(fā)，

多線程程序的有序性的保障可以理解為通過某些措施使得貌似串行語義擴(kuò)展到多線程程序兔毒。即重排序要么不發(fā)生漫贞，

要么即使發(fā)生了也不會影響多線程程序的正確性，這樣有序性的保障也可以理解為從邏輯上部分禁止重排序眼刃。

從底層的角度來說绕辖，禁止重排序是通過調(diào)用處理器提供相應(yīng)的指令（內(nèi)存屏障）來實現(xiàn)的。

當(dāng)然擂红，Java作為一個跨平臺的語言仪际，它會替我們與這類指令打交道，而我們只需要使用語言本身提供的機(jī)制即可昵骤。

5.上下文切換

描述

當(dāng)一個進(jìn)程中的一個線程由于其時間片用完树碱，或者因其自身原因（比如稍后再繼續(xù)運(yùn)行）被迫或者主動暫停其運(yùn)行時，另外一個線程（可能是同一個進(jìn)程或者其他進(jìn)程中的一個線程）可以被操作系統(tǒng)（線程調(diào)度器）選中变秦，占用處理器開始或者繼續(xù)其運(yùn)行成榜。這種一個線程被暫停，另外一個線程被選中開始或者繼續(xù)運(yùn)行的過程就叫作線程上下文切換蹦玫。也可簡單地稱為上下文切換赎婚。

5.1刘绣、線程的切入(Switch In)與切出(Switch Out)

一個線程被剝奪處理器的使用權(quán)而被暫停運(yùn)行就被稱為切出，一個線程被操作系統(tǒng)選中占用處理開始或者繼續(xù)其運(yùn)行就被稱為切入挣输。

5.2纬凤、上下文(Context)

切出和切入的時候，操作系統(tǒng)需要保存和恢復(fù)相應(yīng)線程的進(jìn)度信息撩嚼，即切入和切出那一刻相應(yīng)線程所執(zhí)行的任務(wù)狀態(tài)信息（如計算的中間結(jié)果以及執(zhí)行到了哪條指令）停士。這個進(jìn)度信息就被稱為上下文。它一般包括通用寄存器(General Purpose Register)和程序計數(shù)器(Program Counter)中的內(nèi)容完丽。

5.3恋技、Java中線程的暫停與喚醒

一個線程的生命周期狀態(tài)在RUNNABLE狀態(tài)與非RUNNABLE狀態(tài)之間切換的過程就是一個上下文切換的過程。當(dāng)一個線程的生命周期狀態(tài)由RUNNABLE轉(zhuǎn)換為非RUNNABLE（包括BLOCKED逻族、WAITING和TIMED_ WAITING中的任意一狀態(tài)）時蜻底，我們稱這個線程被暫停。而一個線程的生命周期狀態(tài)由非RUNNABLE狀態(tài)進(jìn)入RUNNABLE狀態(tài)時聘鳞，我們就稱這個線程被喚醒朱躺。一個線程被喚醒僅代表該線程獲得了一個繼續(xù)運(yùn)行的機(jī)會，而并不代表其立刻可以占用處理器運(yùn)行搁痛。當(dāng)被喚醒的線程被操作系統(tǒng)選中占用處理器繼續(xù)其運(yùn)行的時候，操作系統(tǒng)會恢復(fù)之前為該線程保存的上下文宇弛，以便其在此基礎(chǔ)上進(jìn)展鸡典。

5.4、上下文切換分類

按照導(dǎo)致上下文切換的因素劃分枪芒，我們可以將上下文切換分為自發(fā)性上下文切換和非自發(fā)性上下切換彻况。

5.4.1、自發(fā)性上下文切換(Voluntary Context Switch)

自發(fā)性上下文切換指線程由于其自身因素導(dǎo)致的切出舅踪。比如當(dāng)前運(yùn)行的線程發(fā)起了I/O操作（如讀取文件）或者等待其他線程持有的鎖纽甘，或在其運(yùn)行過程中執(zhí)行下列任意一個方法。

Thread. sleep(longmillis);

Object.wait();Object.wait(longtimeout);Object.wait(longtimeout,intnanos);

Thread.yield();

Thread.join();Thread.join(longtimeout);

LockSupport.park()

5.4.2抽碌、非自發(fā)性上下文切換(Involuntary Context Switch)

線程由于線程調(diào)度器的原因被迫切出悍赢。導(dǎo)致非自發(fā)性上下文切換的常見因素包括：被切出線程的時間片用完、有一個比被切出線程優(yōu)先級更高的線程需要被運(yùn)行货徙。

從Java平臺的角度來看左权，Java虛擬機(jī)的垃圾回收(Garbage Collect)動作也可能導(dǎo)致非自發(fā)性上下文切換。這是因為垃圾回收器在執(zhí)行垃圾回收的過程中痴颊，可能需要暫停所有應(yīng)用線程才能完成其工作赏迟，比如在主要回收(Major Collection)過程中，垃圾回收器在對Java虛擬機(jī)堆內(nèi)存區(qū)域進(jìn)行整理的

5.5蠢棱、上下文切換的開銷

上下文切換的開銷包括直接開銷和間接開銷锌杀。

?直接開銷：

a.操作系統(tǒng)保存和恢復(fù)上下文所需的開銷甩栈，這主要是處理器時間開銷。

?b.線程調(diào)度器進(jìn)行線程調(diào)度的開銷：比如糕再，按照一定的規(guī)則決定哪個線程會占用處理器運(yùn)行量没。

間接開銷：

?a.處理器高速緩存重新加載的開銷：一個被切出的線程可能稍后在另外一個處理器上被切入繼續(xù)運(yùn)行。由于這個處理器之前可能未運(yùn)行過該線程亿鲜，那么這個線程在其繼續(xù)運(yùn)行過程中需訪問的變量允蜈，仍然需要被該處理器重新從主內(nèi)存或者通過緩存致性協(xié)議從其他處理器加載到高速緩存之中，這是有一定時間消耗的蒿柳。

b.高速緩存內(nèi)容沖刷(Flush)的開銷：?上下文切換也可能導(dǎo)致整個一級高速緩存中的內(nèi)容被沖刷饶套，即一級高速緩存中的內(nèi)容會被寫入下一級高速緩存（如二級高速緩存），或者主內(nèi)存(RAM)中線程的數(shù)量越多垒探，可能導(dǎo)致的上下文切換的開銷也就可能越大妓蛮。也就是說，多線程編程中使用的線程數(shù)量越多圾叼，程序的計算效率可能反而越低蛤克。因此，在設(shè)計多線程程序的時候夷蚊，減少上下文切換也是一個重要的考量因素构挤。

5.6、線程的活性故障(Liveness Failure)

描述

事實上惕鼓，線程并不是一直處于RUNNABLE狀態(tài)筋现，導(dǎo)致一個線程可能處于非RUNNABLE狀態(tài)的因素，除了資源（主要是處理器資源有限而導(dǎo)致的上下文切換）限制之外箱歧，還有程序自身的錯誤和缺陷矾飞。由資源稀缺性或者程序自身的問題和缺陷導(dǎo)致線程一直處于非RUNNABLE狀態(tài)，或線程雖然處于RUNNABLE狀態(tài)呀邢，但是其要執(zhí)行的任務(wù)卻一直無法進(jìn)展洒沦，這種現(xiàn)象被稱為線程活性故障。常見的線程活性故障包括以下幾種：

死鎖(Deadlock)

死鎖只會出現(xiàn)在一組線程集合中价淌，如果集合中的每一個線程都持有其他線程需要的資源申眼，導(dǎo)致所有線程因等待資源而被永暫停，這種現(xiàn)象就稱之為死鎖输钩。死鎖產(chǎn)生的典型場景是線程X持有資源A的時候等待線程Y釋放資源B豺型，同時線程Y在持有資源B的時候卻等待線程X釋放資源A，這就好比鷸蚌相爭故事中的情形买乃。

鎖死(Lockout)

鎖死與死鎖類似姻氨，鎖死是指線程在等待一個永遠(yuǎn)不會發(fā)生的事件；與死鎖不同的是剪验，鎖死的線程可能不持有任何資源肴焊。一個較典型的例子就是信號丟失導(dǎo)致的鎖死前联，比如對CountDownLatch.countDown()方法的調(diào)用沒有放在finally塊中時，可能因為異常拋出導(dǎo)致執(zhí)行CountDownLatch.await()的線程永遠(yuǎn)處于等待狀態(tài)娶眷。

活鎖(Livelock)

指線程一直處于運(yùn)行狀態(tài),但是其任務(wù)卻一直無法進(jìn)展的一種活性故障似嗤。活鎖的一個重要特征就是線程一直處于運(yùn)行狀態(tài)届宠，區(qū)別于死鎖烁落、鎖死的線程處于等待狀態(tài)。同樣以鷸蚌相爭故事為例豌注，不同的是兩者商量好如果同時咬住對方伤塌，則兩者都松開口，但松口后兩者又同時咬住了對方轧铁，于是兩者在不停的咬住與松口每聪，直至累死。

饑餓(Starvation)

線程一直無法獲得其所需的資源而導(dǎo)致其任務(wù)直無法進(jìn)展的一種活性故障齿风。

比如由于當(dāng)前線程的優(yōu)先級極低药薯，導(dǎo)致資源一直被其他線程搶占。

5.7救斑、資源爭用與調(diào)度

線程間的資源共享

由于資源的稀缺性（例如有限的處理器資源）及資源本身的特性（例如打印機(jī)一次 只能打印一個文件）童本，往往需要在多個線程間共享同一個資源。

排他性資源

一次只能夠被一個線程占用的資源被稱為排他性資源脸候，常見的排他性資源包括處理器巾陕、數(shù)據(jù)庫連接、文件等纪他。

資源爭用(Resource Contention)

在一個線程占用一個排他性資源進(jìn)行訪問（讀、寫操作）晾匠，而未釋放其對資源所有權(quán)的時候茶袒，其他線程試圖訪問該資源的現(xiàn)象就被稱為資源爭用，簡稱爭用凉馆。顯然薪寓，爭用是在并發(fā)環(huán)境下產(chǎn)生的一種現(xiàn)象。

爭用程度

同時試圖訪問同個已經(jīng)被其他線程占用的資源的線程數(shù)量越多澜共，爭用的程度就越高向叉，反之爭用的程度就越低。相應(yīng)的爭用就被分別稱為高爭用和低爭用嗦董。

資源調(diào)度

在多個線程申請同一個排他性資源的情況下母谎，決定哪個線程會被授予該資源的獨占權(quán)，即選擇哪個申請者占用該資源的過程就是資源的調(diào)度京革。獲得資源的獨占權(quán)而又未釋放其獨占權(quán)的線程就被稱為該資源的持有線程奇唤。

?????? a幸斥、資源調(diào)度策略

資源調(diào)度的一種常見策略就是排隊。資源調(diào)度器內(nèi)部維護(hù)一個等待隊列咬扇，在存在資源爭用的情況下甲葬，申請失敗的線程會被存入該隊列。通常懈贺，被存入等待隊列的線程會被暫停经窖。當(dāng)相應(yīng)的資源被其持有線程釋放時，等待隊列中的一個線程會被選中并被喚醒而獲得再次申請資源的機(jī)會梭灿。被喚醒的線程如果申請到資源的獨占權(quán)画侣，那么該線程會從等待隊列中移除；否則胎源，該線程仍然會停留在等待隊列中等待再次申請的機(jī)會棉钧，即該線程會再次被暫停。因此涕蚤，等待隊列中的等待線程可能經(jīng)歷若干次暫停與喚醒才獲得相應(yīng)資源的獨占權(quán)宪卿。可見万栅，資源的調(diào)度可能導(dǎo)致上下文切換佑钾。

???? a.1、資源調(diào)度公平性

????????????? 資源調(diào)度策略的一個常見特性就是它能否保證公平性烦粒。

所謂公平性休溶，是指資源的申請者（線程），是否按照其申請（請求）資源的順序而被授予資源的獨占權(quán)扰她。如果資源的任何一個先申請者兽掰，總是能夠比任何一個后申請者先獲得該資源的獨占權(quán)，那么相應(yīng)的資源調(diào)度策略就被稱為是公平的徒役；如果資源的后申請者可能比先申請者先獲得該資源的獨占權(quán)孽尽，那么相應(yīng)的資源調(diào)度策略就被稱為是非公平的。

需要注意的是忧勿，非公平的資源調(diào)度策略往往只是說明它并不保證資源調(diào)度的公平性杉女，即它允許不公平的資源調(diào)度的出現(xiàn)，而不是表示它刻意造就不公平的資源調(diào)度鸳吸。

???? a.2熏挎、公平的調(diào)度策略

公平的調(diào)度策略不允許插隊現(xiàn)象的出現(xiàn)，即只有在資源未被其他任何線程占用晌砾，并且沒有其他活躍線程申請該資源情況下坎拐，隊列中的線程才被允許被喚醒，搶占相應(yīng)資源的獨占權(quán)。其中廉白，搶占成功的申請者獲得相應(yīng)資源的獨占權(quán)个初，而搶占失敗的申請者會進(jìn)入等待隊列。因此猴蹂，公平調(diào)度策略中的資源申請者總是按照先來后到的順序來獲得資源的獨占權(quán)院溺。

????? a.3、非公平的調(diào)度策略

而非公平的調(diào)度策略則允許插隊現(xiàn)象磅轻，即一個線程釋放其資源獨占權(quán)的時候珍逸，等待隊列中的一個線程會被喚醒申請相應(yīng)的資源。而在這個過程中聋溜，可能存在另一個活躍線程與這個被喚醒的線程共同參與相應(yīng)資源的搶占谆膳。因此，非公平調(diào)度策略中被喚醒的線程不一定就能夠成功申請到資源撮躁。因此漱病，在極端的情況下，非公平調(diào)度策略可能導(dǎo)致等待隊列中的線程永遠(yuǎn)無法獲得其所需的資源把曼，即出現(xiàn)饑餓現(xiàn)象杨帽。

????? a.4、對比

從申請者個體的角度來看：使用公平調(diào)度策略時嗤军，申請者獲得相應(yīng)資源的獨占權(quán)所需時間的偏差可能比較小注盈，即每個申請者成功申請到資源所需的時間基本相同；而使用非公平的調(diào)度策略時叙赚，申請者獲得相應(yīng)資源的獨占權(quán)所需時間的偏差可能比較大老客，有的線程很快就申請到資源，而有的線程則要經(jīng)歷若干次暫停與喚醒才成功申請到資源震叮。

從效率上看：在非公平調(diào)度策略中胧砰，資源的持有線程釋放該資源的時候，等待隊列中的一個線程會被喚醒苇瓣，而該線程從被喚醒到其繼續(xù)運(yùn)行可能需要一段時間朴则。在該時間內(nèi)，如果使用非公平的調(diào)度策略钓简，新來的線程（活躍線程）可以先被授予該資源的獨占權(quán)，如果這個新來的線程占用該資源的時間不長汹想，那么它完全有可能在被喚醒的線程繼續(xù)其運(yùn)行前釋放相應(yīng)的資源外邓，從而不影響該被喚醒的線程申請資源。這種情形下古掏，非公平調(diào)度策略可以減少上下文切換的次數(shù)损话。但是，如果多數(shù)（甚至每個）線程占用資源的時間相當(dāng)長，那么允許新來的線程搶占資源不會帶來任何好處丧枪，反而會導(dǎo)致被喚醒的線程需要再次經(jīng)歷暫停和喚醒光涂，從而增加了上下文切換。因此拧烦，多數(shù)線程占用資源的時間相當(dāng)長的情況下不適合使用非公平調(diào)度策略忘闻。

綜上，在沒有特別需要的情況下恋博，我們默認(rèn)選擇非公平調(diào)度策略即可齐佳。在資源的持有線程占用資源的時間相對長，或線程申請資源的平均間隔時間相對長债沮，或?qū)Y源申請所需的時間偏差有所要求（即時間偏差較辛段狻）的情況下可以考慮使用公平調(diào)度策略。