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

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

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

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

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

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