UNIX內(nèi)核－進(jìn)程調(diào)度（1）
 
進(jìn)程調(diào)度（1）
作為多任務(wù)操作系統(tǒng)，進(jìn)程調(diào)度是它的最基本的操作之一。希望在一臺單處理器的機(jī)器上同時運行多個進(jìn)程的時候，必須有某種形式的進(jìn)程調(diào)度。這是明顯的，因為在任何特定的瞬間，機(jī)器只能為一個進(jìn)程執(zhí)行一條命令。為了使機(jī)器上的若干個進(jìn)程同時取得進(jìn)展，必須由準(zhǔn)備好運行的進(jìn)程共享CPU時間。調(diào)度程序的任務(wù)是選擇下一個準(zhǔn)備好運行的進(jìn)程，將CPU時間分配給它。
1. 背景
當(dāng)調(diào)度程序進(jìn)行調(diào)度任務(wù)時，它試圖達(dá)到一些目標(biāo)。我們將看到有些目標(biāo)對調(diào)度程序提出的要求是互相沖突的。調(diào)度程序的最重要的目標(biāo)有：
* 使每個進(jìn)程公平地共享CPU時間。 
* 使CPU的空閑時間達(dá)到最少（即保持CPU處于忙碌狀態(tài)）。 
* 吞吐能力達(dá)到最高。這表明在給定時間內(nèi)完成任務(wù)的進(jìn)程數(shù)達(dá)到最多。 
* 使系統(tǒng)響應(yīng)用戶請求的時間達(dá)到最短。 
似乎應(yīng)該以某種方式優(yōu)先考慮用戶請求，但是這和所有進(jìn)程公平共享CPU時間的目標(biāo)明顯發(fā)生沖突。
一般來說調(diào)度程序直接面對的問題是：當(dāng)它啟動進(jìn)程時，對進(jìn)程的了解很少。如進(jìn)程平均使用多少CPU時間才停下來等待輸入輸出；以及進(jìn)程提出輸入輸出請求后，平均用多長時間進(jìn)行等待等是未知數(shù)。
另一個問題是：對進(jìn)行輸入/輸出前占用很長CPU時間的進(jìn)程應(yīng)該采取什么措施？能讓它獨占CPU一直運行下去？顯然不能、否則這一進(jìn)程可能使所有的其他進(jìn)程都處于停頓狀態(tài)。
這說明在當(dāng)前進(jìn)程運行足夠長的時間后，要有某種方法將CPU切換給另外一個進(jìn)程。但是從哪里著手，又如何進(jìn)行這樣的調(diào)度。
這里有兩種可能。第1種可能使讓進(jìn)程在CPU上運行一段時間后，自愿放棄對CPU的控制。第2種情況是找出某種辦法強(qiáng)制進(jìn)程釋放對CPU的控制。第一種稱為非搶先調(diào)度。第二種稱為搶先調(diào)度。
當(dāng)我們討論線程（thread）時將看到；運行由相互協(xié)調(diào)的程序組成的系統(tǒng)時候，用非搶先調(diào)度進(jìn)行切換是完全行的通的。然而對多用戶環(huán)境下的進(jìn)程調(diào)度來講，更安全的做法是：最好的情況：進(jìn)程間并不知道對方的存在。在最壞的情況：進(jìn)程之間互相競爭CPU的使用。結(jié)果是在多用戶的環(huán)境下幾乎毫無例外地使用搶先調(diào)度。
具體的做法是：給每個進(jìn)程分配一段最長的不間斷的CPU時間，同時系統(tǒng)產(chǎn)生快速和周期性的時鐘計時中斷，用來決定進(jìn)程什么時候擁有它的時間片。
當(dāng)分配給當(dāng)前進(jìn)程的時間片消逝以后，調(diào)度程序投入運行，由它來決定是否還有準(zhǔn)備好運行的進(jìn)程，它是否比剛用完時間片的當(dāng)前進(jìn)程更有資格投入運行。如果有，由新的進(jìn)程取代當(dāng)前的進(jìn)程，如果沒有，讓當(dāng)前進(jìn)程繼續(xù)運行：
從前面的討論可以看到，進(jìn)程有幾種不同的狀態(tài)。隨著不同事件的出現(xiàn)，在這些狀態(tài)間進(jìn)行切換。上圖表示CPU調(diào)度程序控制下的簡化的進(jìn)程狀態(tài)轉(zhuǎn)換圖，而且標(biāo)出了在下列情況下發(fā)生的6種轉(zhuǎn)換。
1.啟動（start)轉(zhuǎn)換。當(dāng)進(jìn)程首次被啟動時（fork()），并沒有讓它直接控制CPU。而是將它置為可運行狀態(tài)，和其他進(jìn)程一起放在一個隊列中。只要給它們分配CPU時間，就立即可以投入運行。
2.將處于可運行狀態(tài)的進(jìn)程轉(zhuǎn)換為運行狀態(tài)。在可運行進(jìn)程隊列中的進(jìn)程，最終將被調(diào)度程序選中，在CPU上執(zhí)行一段時間。
3.有幾種方法使一個在CPU上運行的進(jìn)程轉(zhuǎn)換為其他狀態(tài)。轉(zhuǎn)換3就是其中的一種，將當(dāng)前運行的進(jìn)程放回可運行的進(jìn)程的清單中。當(dāng)在處理器上運行的進(jìn)程種用完了分配的時間片后，就發(fā)生這種轉(zhuǎn)換，使其他進(jìn)程有機(jī)會投入運行。
4.另一種主要方式是當(dāng)運行中的進(jìn)程提出輸入/輸出請求時，它將失去對CPU的控制。機(jī)器的硬設(shè)備對請求作出響應(yīng)之前會有一段時間的延遲。在等待輸入輸出完成時，即使 CPU空閑，進(jìn)程也不能運行。所以當(dāng)進(jìn)程停下等待輸入輸出完成時，它不能被放回可運行進(jìn)程的清單中，而是通過轉(zhuǎn)換4將它設(shè)置為掛起的狀態(tài)，等待輸入輸出的完成。
5.當(dāng)一個掛起的進(jìn)程等待的輸入輸出事件發(fā)生了。它再次成為有資格運行的進(jìn)程。然而并不立即給這個進(jìn)程提供CPU時間片去處理它的輸入輸出，只是將它送到可運行進(jìn)程的清單中，等待再次被調(diào)度程序選中。這是轉(zhuǎn)換5完成的工作。
6.在簡化圖中，最后一種失去對CPU控制的方式發(fā)生在運行的進(jìn)程結(jié)束時，轉(zhuǎn)換6表示導(dǎo)致進(jìn)程結(jié)束的事件。
也許出人意料，不管CPU調(diào)度程序采用什么算法決定下一個應(yīng)該運行的進(jìn)程，一般都能使用這個狀態(tài)轉(zhuǎn)換圖。
CPU調(diào)度程序可以使用許多可能的調(diào)度算法。也有許多關(guān)于在不同環(huán)境下哪種算法最好的理論。這里不準(zhǔn)備對調(diào)度算法進(jìn)行一般性討論，將集中于對某些細(xì)節(jié)做一些說明.........