一、Java 中用到的線程調(diào)度

1. 搶占式調(diào)度：

搶占式調(diào)度指的是每條線程執(zhí)行的時間、線程的切換都由系統(tǒng)控制，系統(tǒng)控制指的是在系統(tǒng)某種運(yùn)行機(jī)制下，可能每條線程都分同樣的執(zhí)行時間片，也可能是某些線程執(zhí)行的時間片較長，甚至某些線程得不到執(zhí)行的時間片。在這種機(jī)制下，一個線程的堵塞不會導(dǎo)致整個進(jìn)程堵塞。

2. 協(xié)同式調(diào)度：

協(xié)同式調(diào)度指某一線程執(zhí)行完后主動通知系統(tǒng)切換到另一線程上執(zhí)行，這種模式就像接力賽一樣，一個人跑完自己的路程就把接力棒交接給下一個人，下個人繼續(xù)往下跑。線程的執(zhí)行時間由線程本身控制，線程切換可以預(yù)知，不存在多線程同步問題，但它有一個致命弱點(diǎn)：如果一個線程編寫有問題，運(yùn)行到一半就一直堵塞，那么可能導(dǎo)致整個系統(tǒng)崩潰。

3. JVM 的線程調(diào)度實(shí)現(xiàn)（搶占式調(diào)度）

java 使用的線程調(diào)使用搶占式調(diào)度，Java中線程會按優(yōu)先級分配CPU時間片運(yùn)行，且優(yōu)先級越高越優(yōu)先執(zhí)行，但優(yōu)先級高并不代表能獨(dú)自占用執(zhí)行時間片，可能是優(yōu)先級高得到越多的執(zhí)行時間片，反之，優(yōu)先級低的分到的執(zhí)行時間少但不會分配不到執(zhí)行時間。

4. 線程讓出cpu的情況：

1. 當(dāng)前運(yùn)行線程主動放棄CPU，JVM暫時放棄CPU操作（基于時間片輪轉(zhuǎn)調(diào)度的JVM操作系統(tǒng)不會讓線程永久放棄CPU，或者說放棄本次時間片的執(zhí)行權(quán)），例如調(diào)用yield()方法。
2. 當(dāng)前運(yùn)行線程因?yàn)槟承┰蜻M(jìn)入阻塞狀態(tài)，例如阻塞在I/O上。
3.當(dāng)前運(yùn)行線程結(jié)束，即運(yùn)行完run()方法里面的任務(wù)

二、進(jìn)程調(diào)度算法

1. 優(yōu)先調(diào)度算法

1. 先來先服務(wù)調(diào)度算法（FCFS）

當(dāng)在作業(yè)調(diào)度中采用該算法時，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個或多個最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS 算法時，則每次調(diào)度是從就緒隊(duì)列中選擇一個最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)，特點(diǎn)是：算法比較簡單，可以實(shí)現(xiàn)基本上的公平。

2. 短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法

短作業(yè)優(yōu)先(SJF)的調(diào)度算法是從后備隊(duì)列中選擇一個或若干個估計運(yùn)行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法則是從就緒隊(duì)列中選出一個估計運(yùn)行時間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時再重新調(diào)度。該算法未照顧緊迫型作業(yè)。

2. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法

為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。當(dāng)把該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊(duì)列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時，該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。

1. 非搶占式優(yōu)先權(quán)算法

在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實(shí)時性要求不嚴(yán)的實(shí)時系統(tǒng)中。

2.搶占式優(yōu)先權(quán)調(diào)度算法

在這種方式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。

3．高響應(yīng)比優(yōu)先調(diào)度算法

在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運(yùn)行得不到保證。如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a 提高，則長作業(yè)在等待一定的時間后，必然有機(jī)會分配到處理機(jī)。該優(yōu)先權(quán)的變化規(guī)律可描述為：

(1) 如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。
(2) 當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。
(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機(jī)。簡言之，該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，不會使長作業(yè)長期得不到服務(wù)。因此，該算法實(shí)現(xiàn)了一種較好的折衷。當(dāng)然，在利用該算法時，每要進(jìn)行調(diào)度之前，都須先做響應(yīng)比的計算，這會增加系統(tǒng)開銷。

3. 基于時間片的輪轉(zhuǎn)調(diào)度算法

1. 時間片輪轉(zhuǎn)法

在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個隊(duì)列，每次調(diào)度時，把CPU 分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個時間片。時間片的大小從幾ms 到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程在一給定的時間內(nèi)均能獲得一時間片的處理機(jī)執(zhí)行時間。

2. 多級反饋隊(duì)列調(diào)度算法

(1) 應(yīng)設(shè)置多個就緒隊(duì)列，并為各個隊(duì)列賦予不同的優(yōu)先級。第一個隊(duì)列的優(yōu)先級最高，第二個隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊(duì)列中進(jìn)程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊(duì)列的時間片要比第一個隊(duì)列的時間片長一倍，……，第i+1個隊(duì)列的時間片要比第i個隊(duì)列的時間片長一倍。
(2) 當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個時間片后仍未完成，再依次將它放入第三隊(duì)列，……，如此下去，當(dāng)一個長作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后，在第n 隊(duì)列便采取按時間片輪轉(zhuǎn)的方式運(yùn)行。
(3) 僅當(dāng)?shù)谝魂?duì)列空閑時，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?1～(i-1)隊(duì)列均空時，才會調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第 1～(i-1)中的任何一個隊(duì)列)，則此時新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。在多級反饋隊(duì)列調(diào)度算法中，如果規(guī)定第一個隊(duì)列的時間片略大于多數(shù)人機(jī)交互所需之處理時間時，便能夠較好的滿足各種類型用戶的需要。

三、CAS（比較并交換-樂觀鎖機(jī)制-鎖自旋）

1. 概念及特性

CAS（Compare And Swap/Set）比較并交換，CAS 算法的過程是這樣：它包含 3 個參數(shù)CAS(V,E,N)。V 表示要更新的變量(內(nèi)存值)，E 表示預(yù)期值(舊的)，N 表示新值。當(dāng)且僅當(dāng) V 值等于E值時，才會將V的值設(shè)為N，如果V值和E值不同，則說明已經(jīng)有其他線程做了更新，則當(dāng)前線程什么都不做。最后，CAS返回當(dāng)前V的真實(shí)值。
CAS 操作是抱著樂觀的態(tài)度進(jìn)行的(樂觀鎖)，它總是認(rèn)為自己可以成功完成操作。當(dāng)多個線程同時使用 CAS 操作一個變量時，只有一個會勝出，并成功更新，其余均會失敗。失敗的線程不會被掛起，僅是被告知失敗，并且允許再次嘗試，當(dāng)然也允許失敗的線程放棄操作?；谶@樣的原理，CAS操作即使沒有鎖，也可以發(fā)現(xiàn)其他線程對當(dāng)前線程的干擾，并進(jìn)行恰當(dāng)?shù)奶幚怼?

.2. 原子包 java.util.concurrent.atomic（鎖自旋）

JDK1.5 的原子包：java.util.concurrent.atomic 這個包里面提供了一組原子類。其基本的特性就是在多線程環(huán)境下，當(dāng)有多個線程同時執(zhí)行這些類的實(shí)例包含的方法時，具有排他性，即當(dāng)某個線程進(jìn)入方法，執(zhí)行其中的指令時，不會被其他線程打斷，而別的線程就像自旋鎖一樣，一直等到該方法執(zhí)行完成，才由 JVM 從等待隊(duì)列中選擇一個另一個線程進(jìn)入，這只是一種邏輯上的理解。相對于對于synchronized 這種阻塞算法，CAS 是非阻塞算法的一種常見實(shí)現(xiàn)。由于一般CPU切換時間比CPU指令集操作更加長，所以J.U.C在性能上有了很大的提升。

3. ABA 問題

CAS 會導(dǎo)致“ABA 問題”。CAS 算法實(shí)現(xiàn)一個重要前提需要取出內(nèi)存中某時刻的數(shù)據(jù)，而在下時刻比較并替換，那么在這個時間差類會導(dǎo)致數(shù)據(jù)的變化。
比如說一個線程 one 從內(nèi)存位置 V 中取出A，這時候另一個線程 two 也從內(nèi)存中取出 A，并且two進(jìn)行了一些操作變成了B，然后two又將V位置的數(shù)據(jù)變成A，這時候線程one進(jìn)行CAS操作發(fā)現(xiàn)內(nèi)存中仍然是A，然后one操作成功。盡管線程one的CAS操作成功，但是不代表這個過程就是沒有問題的。
部分樂觀鎖的實(shí)現(xiàn)是通過版本號（version）的方式來解決ABA問題，樂觀鎖每次在執(zhí)行數(shù)據(jù)的修改操作時，都會帶上一個版本號，一旦版本號和數(shù)據(jù)的版本號一致就可以執(zhí)行修改操作并對版本號執(zhí)行+1 操作，否則就執(zhí)行失敗。因?yàn)槊看尾僮鞯陌姹咎柖紩S之增加，所以不會出現(xiàn) ABA 問題，因?yàn)榘姹咎栔粫黾硬粫p少。

四、AQS（抽象的隊(duì)列同步器）

AbstractQueuedSynchronizer 類如其名，抽象的隊(duì)列式的同步器，AQS定義了一套多線程訪問共享資源的同步器框架，許多同步類實(shí)現(xiàn)都依賴于它，如常用的ReentrantLock/Semaphore/CountDownLatch。

它維護(hù)了一個volatile int state（代表共享資源）和一個 FIFO 線程等待隊(duì)列（多線程爭用資源被阻塞時會進(jìn)入此隊(duì)列）。這里volatile 是核心關(guān)鍵詞，具體 volatile 的語義，在此不述。state 的訪問方式有三種:
getState()
setState()
compareAndSetState()
AQS定義兩種資源共享方式
Exclusive 獨(dú)占資源-ReentrantLock
Exclusive（獨(dú)占，只有一個線程能執(zhí)行，如ReentrantLock）
Share 共享資源-Semaphore/CountDownLatch
Share（共享，多個線程可同時執(zhí)行，如Semaphore/CountDownLatch）。
AQS只是一個框架，具體資源的獲取/釋放方式交由自定義同步器去實(shí)現(xiàn)，AQS這里只定義了一個接口，具體資源的獲取交由自定義同步器去實(shí)現(xiàn)了（通過state的get/set/CAS)之所以沒有定義成abstract，是因?yàn)楠?dú)占模式下只用實(shí)現(xiàn) tryAcquire-tryRelease，而共享模式下只用實(shí)現(xiàn)tryAcquireShared-tryReleaseShared。如果都定義成abstract，那么每個模式也要去實(shí)現(xiàn)另一模式下的接口。不同的自定義同步器爭用共享資源的方式也不同。自定義同步器在實(shí)現(xiàn)時只需要實(shí)現(xiàn)共享資源 state 的獲取與釋放方式即可，至于具體線程等待隊(duì)列的維護(hù)（如獲取資源失敗入隊(duì)/喚醒出隊(duì)等），AQS已經(jīng)在頂層實(shí)現(xiàn)好了。自定義同步器實(shí)現(xiàn)時主要實(shí)現(xiàn)以下幾種方法：
1．isHeldExclusively()：該線程是否正在獨(dú)占資源。只有用到condition才需要去實(shí)現(xiàn)它。
2．tryAcquire(int)：獨(dú)占方式。嘗試獲取資源，成功則返回true，失敗則返回false。
3．tryRelease(int)：獨(dú)占方式。嘗試釋放資源，成功則返回true，失敗則返回false。
4．tryAcquireShared(int)：共享方式。嘗試獲取資源。負(fù)數(shù)表示失敗；0 表示成功，但沒有剩余可用資源；正數(shù)表示成功，且有剩余資源。
5．tryReleaseShared(int)：共享方式。嘗試釋放資源，如果釋放后允許喚醒后續(xù)等待結(jié)點(diǎn)返回true，否則返回false。

同步器的實(shí)現(xiàn)是ABS核心（state資源狀態(tài)計數(shù)）

同步器的實(shí)現(xiàn)是ABS核心，以ReentrantLock為例，state初始化為0，表示未鎖定狀態(tài)。A線程lock()時，會調(diào)用 tryAcquire()獨(dú)占該鎖并將 state+1。此后，其他線程再 tryAcquire()時就會失敗，直到A線程unlock()到state=0（即釋放鎖）為止，其它線程才有機(jī)會獲取該鎖。當(dāng)然，釋放鎖之前，A 線程自己是可以重復(fù)獲取此鎖的（state 會累加），這就是可重入的概念。但要注意，獲取多少次就要釋放多么次，這樣才能保證state是能回到零態(tài)的。以CountDownLatch以例，任務(wù)分為N個子線程去執(zhí)行，state也初始化為N（注意N要與線程個數(shù)一致）。這 N 個子線程是并行執(zhí)行的，每個子線程執(zhí)行完后 countDown()一次，state會CAS減1。等到所有子線程都執(zhí)行完后(即state=0)，會unpark()主調(diào)用線程，然后主調(diào)用線程就會從await()函數(shù)返回，繼續(xù)后余動作。
ReentrantReadWriteLock 實(shí)現(xiàn)獨(dú)占和共享兩種方式
一般來說，自定義同步器要么是獨(dú)占方法，要么是共享方式，他們也只需實(shí)現(xiàn) tryAcquiretryRelease、tryAcquireShared-tryReleaseShared 中的一種即可。但 AQS 也支持自定義同步器同時實(shí)現(xiàn)獨(dú)占和共享兩種方式，如ReentrantReadWriteLock。