內(nèi)核－進程調(diào)度1

1、UNIX內(nèi)核進程調(diào)度（1） 進程調(diào)度（1）作為多任務(wù)操作系統(tǒng)，進程調(diào)度是它的最基本的操作之一。希望在一臺單處理器的機器上同時運行多個進程的時候，必須有某種形式的進程調(diào)度。這是明顯的，因為在任何特定的瞬間，機器只能為一個進程執(zhí)行一條命令。為了使機器上的若干個進程同時取得進展，必須由準備好運行的進程共享CPU時間。調(diào)度程序的任務(wù)是選擇下一個準備好運行的進程，將CPU時間分配給它。1. 背景當調(diào)度程序進行調(diào)度任務(wù)時，它試圖達到一些目標。我們將看到有些目標對調(diào)度程序提出的要求是互相沖突的。調(diào)度程序的最重要的目標有：· 使每個進程公平地共享CPU時間。· 使CPU的空閑時間

2、達到最少（即保持CPU處于忙碌狀態(tài)）。· 吞吐能力達到最高。這表明在給定時間內(nèi)完成任務(wù)的進程數(shù)達到最多。· 使系統(tǒng)響應用戶請求的時間達到最短。似乎應該以某種方式優(yōu)先考慮用戶請求，但是這和所有進程公平共享CPU時間的目標明顯發(fā)生沖突。一般來說調(diào)度程序直接面對的問題是：當它啟動進程時，對進程的了解很少。如進程平均使用多少CPU時間才停下來等待輸入輸出；以及進程提出輸入輸出請求后，平均用多長時間進行等待等是未知數(shù)。另一個問題是：對進行輸入/輸出前占用很長CPU時間的進程應該采取什么措施？能讓它獨占CPU一直運行下去？顯然不能、否則這一進程可能使所有的其他進程都處于停頓狀態(tài)。這說明

3、在當前進程運行足夠長的時間后，要有某種方法將CPU切換給另外一個進程。但是從哪里著手，又如何進行這樣的調(diào)度。這里有兩種可能。第1種可能使讓進程在CPU上運行一段時間后，自愿放棄對CPU的控制。第2種情況是找出某種辦法強制進程釋放對CPU的控制。第一種稱為非搶先調(diào)度。第二種稱為搶先調(diào)度。當我們討論線程（thread）時將看到；運行由相互協(xié)調(diào)的程序組成的系統(tǒng)時候，用非搶先調(diào)度進行切換是完全行的通的。然而對多用戶環(huán)境下的進程調(diào)度來講，更安全的做法是：最好的情況：進程間并不知道對方的存在。在最壞的情況：進程之間互相競爭CPU的使用。結(jié)果是在多用戶的環(huán)境下幾乎毫無例外地使用搶先調(diào)度。具體的做法是：給每個

4、進程分配一段最長的不間斷的CPU時間，同時系統(tǒng)產(chǎn)生快速和周期性的時鐘計時中斷，用來決定進程什么時候擁有它的時間片。當分配給當前進程的時間片消逝以后，調(diào)度程序投入運行，由它來決定是否還有準備好運行的進程，它是否比剛用完時間片的當前進程更有資格投入運行。如果有，由新的進程取代當前的進程，如果沒有，讓當前進程繼續(xù)運行：從前面的討論可以看到，進程有幾種不同的狀態(tài)。隨著不同事件的出現(xiàn)，在這些狀態(tài)間進行切換。上圖表示CPU調(diào)度程序控制下的簡化的進程狀態(tài)轉(zhuǎn)換圖，而且標出了在下列情況下發(fā)生的6種轉(zhuǎn)換。1.啟動（start)轉(zhuǎn)換。當進程首次被啟動時（fork()），并沒有讓它直接控制CPU。而是將它置為可運行狀

5、態(tài)，和其他進程一起放在一個隊列中。只要給它們分配CPU時間，就立即可以投入運行。2.將處于可運行狀態(tài)的進程轉(zhuǎn)換為運行狀態(tài)。在可運行進程隊列中的進程，最終將被調(diào)度程序選中，在CPU上執(zhí)行一段時間。3.有幾種方法使一個在CPU上運行的進程轉(zhuǎn)換為其他狀態(tài)。轉(zhuǎn)換3就是其中的一種，將當前運行的進程放回可運行的進程的清單中。當在處理器上運行的進程種用完了分配的時間片后，就發(fā)生這種轉(zhuǎn)換，使其他進程有機會投入運行。4.另一種主要方式是當運行中的進程提出輸入/輸出請求時，它將失去對CPU的控制。機器的硬設(shè)備對請求作出響應之前會有一段時間的延遲。在等待輸入輸出完成時，即使 CPU空閑，進程也不能運行。所以當進程停下等待輸入輸出完成時，它不能被放回可運行進程的清單中，而是通過轉(zhuǎn)換4將它設(shè)置為掛起的狀態(tài)，等待輸入輸出的完成。5.當一個掛起的進程等待的輸入輸出事件發(fā)生了。它再次成為有資格運行的進程。然而并不立即給這個進程提供CPU時間片去處理它的輸入輸出，只是將它送到可運行進程的清單中，等待再次被調(diào)度程序選中。這是轉(zhuǎn)換5完成的工作。6.在簡化圖中，最后一種失去對CPU控制的方式發(fā)生在運行的進程結(jié)束時，轉(zhuǎn)換6表示導致進程結(jié)束的事件。也許出人意料，不管CPU調(diào)度程序采用什么算法決定下一個應該運行的進程