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

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

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

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

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

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

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

4. 線程讓出cpu的情況：

1. 當前運行線程主動放棄CPU，JVM暫時放棄CPU操作（基于時間片輪轉調(diào)度的JVM操作系統(tǒng)不會讓線程永久放棄CPU，或者說放棄本次時間片的執(zhí)行權），例如調(diào)用yield()方法。
2. 當前運行線程因為某些原因進入阻塞狀態(tài)，例如阻塞在I/O上。
3.當前運行線程結束，即運行完run()方法里面的任務

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. 時間片輪轉法

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

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

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

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

1. 概念及特性

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

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

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

3. ABA 問題

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

四、AQS（抽象的隊列同步器）

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

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

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

同步器的實現(xiàn)是ABS核心，以ReentrantLock為例，state初始化為0，表示未鎖定狀態(tài)。A線程lock()時，會調(diào)用 tryAcquire()獨占該鎖并將 state+1。此后，其他線程再 tryAcquire()時就會失敗，直到A線程unlock()到state=0（即釋放鎖）為止，其它線程才有機會獲取該鎖。當然，釋放鎖之前，A 線程自己是可以重復獲取此鎖的（state 會累加），這就是可重入的概念。但要注意，獲取多少次就要釋放多么次，這樣才能保證state是能回到零態(tài)的。以CountDownLatch以例，任務分為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 實現(xiàn)獨占和共享兩種方式
一般來說，自定義同步器要么是獨占方法，要么是共享方式，他們也只需實現(xiàn) tryAcquiretryRelease、tryAcquireShared-tryReleaseShared 中的一種即可。但 AQS 也支持自定義同步器同時實現(xiàn)獨占和共享兩種方式，如ReentrantReadWriteLock。