线程的调度
概述
Windows?實現(xiàn)了一個由優(yōu)先級驅(qū)動，搶占式的調(diào)度系統(tǒng)，也就是最高優(yōu)先級的可運行的（就緒狀態(tài)下的）線程總是先運行。
有一種現(xiàn)象稱之為“處理器親合（processor affinity）”，即線程可能受處理器限制，只運行在那些允許它運行的處理器上。缺省的設(shè)置是線程可運行在任何可用的處理器上，用戶可以通過使用一個Win32的調(diào)度函數(shù)修改處理器的“親合性”。
當一個線程被選擇運行，它所運行的時間稱之為“時間片”。Windows中斷這個線程，去查找是否有別的同優(yōu)先級或更高優(yōu)先級的線程正在等待執(zhí)行，或者這個線程的優(yōu)先級需要被降低，在這之前這個線程運行的時間長度就是一個“時間片”。不同的線程，其時間片的值可以不同，Window 2000專業(yè)版和服務(wù)器版的時間片的值是不同的。然而，因為Windows實現(xiàn)的是一種搶占式的調(diào)度，一個線程可能未完成其時間片。如果另外有一個更高優(yōu)先級的線程就緒，正在運行的這個線程就可能在未完成其時間片前被搶占。事實上，一個線程甚至?xí)谖撮_始其時間片前就被搶占了，而要等待下一次被選擇運行。
Windows的沒有單獨的調(diào)度模塊或程序，調(diào)度的代碼是在內(nèi)核中實現(xiàn)的，廣泛分布在內(nèi)核中那些與調(diào)度相關(guān)的事件發(fā)生的地方。這些負責(zé)調(diào)度的程序被總稱為“內(nèi)核的調(diào)度器”。線程調(diào)度發(fā)生在DPC/Dispatch級別。
以下這些事件發(fā)生時會觸發(fā)線程調(diào)度：
- 變成就緒狀態(tài)的線程。例如：一個新創(chuàng)建的線程，或者從等待狀態(tài)釋放出來的線程。
- 因其時間片結(jié)束而離開運行狀態(tài)的線程，它或者結(jié)束了，或者進入等待狀態(tài)。
- 線程的優(yōu)先級改變了，是因為系統(tǒng)調(diào)用，或者是Windows自己改變了優(yōu)先級。
- 正在運行的線程的處理器親合性改變了。
在每一個上述情況的銜接點，Windows必須決定下一個運行的線程是哪一個。一旦選擇了一個新的線程運行，Windows將對其執(zhí)行一個上下文轉(zhuǎn)換的操作，即保存正在運行的線程的相關(guān)的機器狀態(tài)，裝載另一個線程的狀態(tài)，開始新線程的執(zhí)行。
Windows的調(diào)度是以線程為粒度調(diào)度的。調(diào)度的決策被嚴格限制在以線程為基礎(chǔ)，并不考慮這個線程屬于哪一個進程。當考慮到進程并不運行，而僅為其線程提供資源和運行的上下文環(huán)境時，這種方法就有意義了，例如，進程A有10個可運行的線程，進程B有2個可運行的線程，而且這12個線程的優(yōu)先級別相同，那么，每一個線程將會使用1/12的CPU時間，而不是將CPU 50%的時間分配給進程A，50%?的時間分配給進程B。
為了明白線程調(diào)度算法，必須首先明白Windows所使用的優(yōu)先級別。
線程優(yōu)先級別
如Figure 6-12圖示：Windows內(nèi)部使用32個優(yōu)先級別，從0-31。這些數(shù)值被分成以下幾類：
- 16個實時級別(16-31)
- 15個變化的級別(1-15)
- 1個系統(tǒng)級別(0),?被保留用作0頁線程
線程優(yōu)先級別是從兩個不同的方面來分配的：一個是從Win32應(yīng)用程序編程接口，另一個是從Windows的內(nèi)核。
Win32 API的進程在創(chuàng)建時所分配的優(yōu)先級包括：Real-time, High, Above Normal, Normal, Below Normal, and Idle，進程中各個線程的相關(guān)優(yōu)先級包括：Time-critical, Highest, Above-normal, Normal, Below-normal, Lowest, and Idle。 應(yīng)用程序默認的優(yōu)先級為Normal。
運行在內(nèi)核模式的線程可以被用戶模式的線程搶占掉，這與線程的狀態(tài)無關(guān)，優(yōu)先級是決定性因素。
在Win32 API中，每個線程的優(yōu)先級都是它所屬的進程的優(yōu)先級和自己相關(guān)的線程優(yōu)先級二者的組合。從Win32優(yōu)先級映射到Windows內(nèi)部數(shù)字式的優(yōu)先級如Figure 6-13圖示：
線程的實時優(yōu)先級
在動態(tài)范圍內(nèi)，用戶可以可以升高或降低應(yīng)用程序中線程的優(yōu)先級。但是，如果要將進程升高到實時范圍內(nèi)，就必須擁有升高調(diào)度優(yōu)先級的權(quán)力。如果沒有這個權(quán)力而企圖將一個進程升高到實時優(yōu)先級，操作不會失敗，只是高級級別(High class)將被使用。
很多Windows的重要的內(nèi)核模式的系統(tǒng)線程是在實時優(yōu)先級范圍內(nèi)的，如果用戶進程花費了過多的時間運行在這個范圍內(nèi)，可能會阻礙了重要的系統(tǒng)功能，如內(nèi)存管理器、緩沖管理器、本地和網(wǎng)絡(luò)文件系統(tǒng)，甚至是一些設(shè)備驅(qū)動程序。因為硬件中斷擁有比任何線程都高的優(yōu)先級，所以不會被阻礙。
在實時范圍內(nèi)的線程性能上有一點不同，當它被搶占時，其線程時間量會被重新設(shè)置。
雖然Windows有一套優(yōu)先級稱之為“實時”，但它們并不是通常意義上定義的實時。因為Windows并沒有提供真正的實時操作系統(tǒng)功能，例如確保中斷時間間隔，或者是讓線程得到一個確保的執(zhí)行時間。
時間片（quantum）
前面已經(jīng)提到，“時間片”就是在Windows檢查是否有另外一個同優(yōu)先級的線程要執(zhí)行前，線程運行的時間。如果一個線程結(jié)束了它的時間片，而又沒有另外一個同優(yōu)先級的線程，Windows重新調(diào)度這個線程運行另外一個時間片。每個線程都有一個時間片的數(shù)值，它代表了線程可以運行多長時間，直到時間片屆滿。這個數(shù)值不是一個時間的計時長度，而是一個整數(shù)，我們稱之為“時間片單位（quantum units）”。
缺省的情況下，Windows 2000/XP Professional線程運行2個時鐘周期（6個時間片單位），Windows Server版線程運行12個時鐘周期（36個時間片單位）。每次時鐘中斷，時鐘中斷程序從線程時間片中扣除一個固定的值3（1個時鐘周期）。
Windows Server版設(shè)置了較長的缺省值是為了減少上下文轉(zhuǎn)換。當有客戶請求到來時，服務(wù)器應(yīng)用程序被喚醒后，如果有較長的時間片，它就可以更好的完成這個請求，然后在時間片結(jié)束前返回等待狀態(tài)。
如果線程時間片沒有剩余，時間片結(jié)束處理進程就會被觸發(fā)，然后另外一個線程可能被選擇執(zhí)行。當時鐘中斷發(fā)生時，如果系統(tǒng)正處于DPC/Dispatch級別或者更高，例如正在執(zhí)行一個DPC或者一個中斷服務(wù)程序，在這種情況下，就算當前的線程在整個時鐘中斷間隔都沒有運行，它的時間片仍然會被減少。如果不是這樣做，而設(shè)備中斷或者DPC又總是剛好發(fā)生在時鐘間隔中斷前，線程的時間片可能因此總不減少。
不同的硬件平臺，時鐘間隔的長度是不同的。時鐘中斷的頻率是由HAL（硬件層）負責(zé)，而不是內(nèi)核負責(zé)。例如，大部分x86單處理器的時鐘間隔是10毫秒，大部分x86多處理器的時鐘間隔是15毫秒。
每個時鐘滴答表示3個時間片單位，而不是一個時間片單位，這種表示方法是為了線程在等待完成的時候，其時間片可以被減少一部分。基本優(yōu)先級少于14的線程執(zhí)行了等待的函數(shù)，如WaitForSingleObject?或者WaitForMultipleObjects后，它的時間片就減少1個單位；優(yōu)先級是14或更高的線程等待后，其時間片會被重新設(shè)置。
線程的時間片可以部分被減少的原因是，當線程在時鐘間隔計數(shù)器激發(fā)前進入等待狀態(tài)，如果沒有對其時間片進行調(diào)整，那么有可能這個線程的時間片就從不減少。例如：一個線程運行，然后進入等待狀態(tài)，然后再運行，再進入等待狀態(tài)。但當時鐘間隔計數(shù)器激發(fā)時，卻從來不是當前運行的線程，那么當它運行時其時間片就從不被記賬，也就不會減少。
線程的調(diào)度方案
線程可以處于的不同的執(zhí)行狀態(tài)，圖6-14顯示了是Windows2000/XP中線程的狀態(tài)的互相轉(zhuǎn)變。
線程的狀態(tài)有以下幾種：
| 線程狀態(tài) | 說明 |
| Ready（就緒） | 此狀態(tài)下的線程正在等待執(zhí)行，當調(diào)度程序需要找一個線程來執(zhí)行時，它僅考慮就緒狀態(tài)下的線程池。 |
| Standby（備用） | 已經(jīng)被選中（當前活動線程的后繼），當條件合適時，調(diào)度程序?qū)@個線程執(zhí)行一個上下文轉(zhuǎn)換，備用線程將被切換到某個特定的處理器上運行。對于系統(tǒng)中的每一個處理器，只能有一個線程處于備用狀態(tài)。 |
| Running（運行） | 一旦調(diào)度程序?qū)h(huán)境切換到某個（備用）線程，這個線程就進入運行狀態(tài)并開始執(zhí)行。線程一直執(zhí)行，直到內(nèi)核將其搶占去運行一個更高優(yōu)先級的線程，或者它的時間片到結(jié)束運行或自動進入等待狀態(tài)。 |
| Waiting（等待） | 一個線程可能因為以下幾個原因而進入等待狀態(tài)：（1）自動等待一個對象以便同步它的執(zhí)行。（2）操作系統(tǒng)可以代替該進程進入等待（如為了解決換頁I/O）。(3)環(huán)境子系統(tǒng)引導(dǎo)線程掛起。 線程等待狀態(tài)結(jié)束后，根據(jù)其優(yōu)先級，開始執(zhí)行，或者進入就緒狀態(tài)。 |
| Transition?（轉(zhuǎn)變） | 當一個線程已經(jīng)準備好執(zhí)行，但它的內(nèi)核棧被換出了內(nèi)存，這時線程就進入轉(zhuǎn)變狀態(tài)。一旦它的內(nèi)核棧被換入內(nèi)存，線程就進入就緒狀態(tài)。 |
| Terminated?（終止） | 當一個線程完成執(zhí)行，它就進入終止狀態(tài)。終止后，線程對象可能被刪除，也可能不被刪除，這將取決于對象管理器什么時候刪除對象的策略。如果執(zhí)行體中有一個指針指向線程對象，執(zhí)行體可以對線程對象重新初始化并再次使用它。 |
| Initialized?（初始） | 當一個線程被創(chuàng)建時的狀態(tài)。（內(nèi)部使用） |
Windows在線程優(yōu)先級上是以“誰將得到CPU”為基準的，但這個方法是實際上如何工作的呢？下面的部分將解釋在線程的級別上，由優(yōu)先級驅(qū)動的，搶占式的多任務(wù)的調(diào)度是如何工作的。注意到Windows在處理線程調(diào)度決策上，單處理器系統(tǒng)和多處理器系統(tǒng)是不同的，這將在后續(xù)部分解釋。
（1）自愿切換
線程可能調(diào)用Win32的某些阻塞函數(shù)如WaitForSingleObject、?WaitForMultipleObjects來等待某個對象（如事件、信號量、I/O完成的端口、進程、線程、窗口信息等），從而進入等待狀態(tài)，自動放棄對CPU的占用。該線程進入同優(yōu)先級就緒隊列的末尾，而CPU將上下文切換到就緒隊列中的下一個線程并開始執(zhí)行。
以下就餐的情景能很好的幫助你理解線程的自動切換：在餐廳，你點了一個尚未準備好的漢堡包，為了不阻礙其他的就餐者，你就文明地站到一邊，讓下一個食客點菜。這時候，你的漢堡包正在準備中。漢堡包準備好之前，你站到了其優(yōu)先級的就緒隊列的尾部。這樣似乎有些不公平，因為你先點的，所以當漢堡包準備好了的時候，服務(wù)員一般會先給你端過來。
同樣在操作系統(tǒng)中，為兼顧公平，大部分線程等待的對象受信后，一般會使用一個臨時增強優(yōu)先級，以讓線程可以馬上執(zhí)行。
那么線程剩余的時間片又如何呢？當線程進入等待狀態(tài)時，時間片的值并不重新設(shè)置。實際上，前面已經(jīng)解釋過，當線程的等待狀態(tài)結(jié)束時，它的時間片被減少了1個時間量單位，相當于1/3個時鐘間隔。而優(yōu)先級等于或高于14的線程，等待狀態(tài)結(jié)束后，它們的時間量會被重新設(shè)置。
（2）搶占式調(diào)度
這種調(diào)度情況是指一個低優(yōu)先級的線程被一個較高優(yōu)先級的線程強搶占。有2個原因會導(dǎo)致這種情況的發(fā)生：
l?????????較高優(yōu)先級的線程的等待狀態(tài)結(jié)束，也就是另外一個線程在等待的事件發(fā)生。
l?????????線程的優(yōu)先級被提高或降低。
在上述的任何一個情況下，Windows都必須決定當前運行的線程是否仍然繼續(xù)運行，還是被一個更高優(yōu)先級的線程搶占運行。
注意：用戶模式下的線程可以搶占內(nèi)核模式下的線程。其實，線程運行在什么模式下并沒有關(guān)系。線程的優(yōu)先級才是決定因素。
當線程被搶占，它被放到了它運行的優(yōu)先級的就緒隊列的頭。如果是實時優(yōu)先級的線程，它的時間量會被重置成一個完整的時間片。如果是動態(tài)范圍的優(yōu)先級的線程，它再次運行時，就完成它上次剩余的時間片。
搶占就可以粗略地比喻你的漢堡包已經(jīng)準備好時，突然總統(tǒng)走來要訂一個漢堡包。當總統(tǒng)在拿他的午餐時，并不要求你去隊尾，出于一種尊重，你只需站到一邊。一旦總統(tǒng)離開，你可以馬上獲得漢堡包，立即享用。
（3）時間片用完
當一個運行的線程使用完它的時間量，Windows必須決定是否要降低線程的優(yōu)先級，和是否讓另外一個線程使用處理器。
如果線程的優(yōu)先級被降低，Windows尋找一個更適合的線程進行調(diào)度。一個更適合的線程是指優(yōu)先級比當前運行的線程的新的優(yōu)先級更高的，在就緒隊列中的線程。如果線程的優(yōu)先級沒有被降低，而且又有同樣優(yōu)先級的線程在就緒隊列中，Windows將在隊列中選擇下一個線程，而將先前運行的線程放到了隊列的尾部，并賦予它一個新的時間片值，將其狀態(tài)從運行改為就緒。如果沒有另外一個同樣優(yōu)先級的線程準備好運行，線程將繼續(xù)執(zhí)行它下一個時間片。
（4）終止
當線程調(diào)用了ExitThread從主函數(shù)中返回，或者被TerminateThread殺掉，它都結(jié)束運行，運行狀態(tài)改為終止狀態(tài)。如果該線程對象沒有打開的句柄，就會從進程的線程隊列中被刪除，其相關(guān)的數(shù)據(jù)結(jié)構(gòu)將會釋放并重新被分配。
線程優(yōu)先級的提升
在五種情況下，Windows會提升線程當前優(yōu)先級的值：
- 完成I/O操作時；
- 等待執(zhí)行體事件或者信號量受信后；
- 前臺進程的線程完成等待操作后；
- 因為窗口行為，GUI線程被喚醒時；
- 當線程準備好運行，但卻一直不能運行。（CPU饑餓）
這些調(diào)整的目的是為了提高系統(tǒng)整體的吞吐量和響應(yīng)能力，同時也為了解決潛在的不公平的調(diào)度現(xiàn)象。正象任意的調(diào)度算法一樣，這些調(diào)整并不是完美的，并不是所有的應(yīng)用程序都會從中得到好處。Windows從不提升那些在實時范圍內(nèi)（16-31）的線程的優(yōu)先級。因此，在談到實時范圍內(nèi)的線程時，調(diào)度通常是可預(yù)知的。
?
說明：
本文摘自《Windows Internals》第6章《進程、線程和作業(yè)》6.5《線程調(diào)度》
總結(jié)
- 上一篇： 线程的数据结构
- 下一篇： Win32多线程编程(1) — 基础概念