本文部分來自博客http://blog.csdn.net/luyafei_89430/article/details/12971171
進程調(diào)度是系統(tǒng)內(nèi)部的低級調(diào)度，進程調(diào)度的策略通常有先來先服務(wù)算法，最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，最短進程優(yōu)先調(diào)度算法等。
先來先服務(wù)(FCFS)調(diào)度算法是一種最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進程調(diào)度。當在作業(yè)調(diào)度中采用該算法時，每次調(diào)度都是從后備作業(yè)隊列中選擇一個或多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。在進程調(diào)度中采用FCFS算法時，則每次調(diào)度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。
算法實現(xiàn)原理圖：
短作業(yè)(進程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先(SPF)調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時再重新調(diào)度。
為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進程調(diào)度算法，還可用于實時系統(tǒng)中。當把該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當用于進程調(diào)度時，該算法是把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程，這時，又可進一步把該算法分成如下兩種。
1) 非搶占式優(yōu)先權(quán)算法
在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進程后，該進程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴的實時系統(tǒng)中。
2) 搶占式優(yōu)先權(quán)調(diào)度算法
在這種方式下，系統(tǒng)同樣是把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止當前進程(原優(yōu)先權(quán)最高的進程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。因此，在采用這種調(diào)度算法時，是每當系統(tǒng)中出現(xiàn)一個新的就緒進程i 時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進程j 的優(yōu)先權(quán)Pj進行比較。如果Pi≤Pj，原進程Pj便繼續(xù)執(zhí)行；但如果是Pi>Pj，則立即停止Pj的執(zhí)行，做進程切換，使i 進程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。
在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運行得不到保證。如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a 提高，則長作業(yè)在等待一定的時間后，必然有機會分配到處理機。該優(yōu)先權(quán)的變化規(guī)律可描述為：由于等待時間與服務(wù)時間之和就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當于響應(yīng)比RP。據(jù)此，又可表示為：
由上式可以看出：
(1) 如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。
(2) 當要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。
(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機。簡言之，該算法既照顧了短作業(yè)，又考慮了作業(yè)到達的先后次序，不會使長作業(yè)長期得不到服務(wù)。因此，該算法實現(xiàn)了一種較好的折衷。當然，在利用該算法時，每要進行調(diào)度之前，都須先做響應(yīng)比的計算，這會增加系統(tǒng)開銷。
1) 基本原理
在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把CPU 分配給隊首進程，并令其執(zhí)行一個時間片。時間片的大小從幾ms 到幾百ms。當執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內(nèi)均能獲得一時間片的處理機執(zhí)行時間。換言之，系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求。
算法實現(xiàn)原理圖：
前面介紹的各種用作進程調(diào)度的算法都有一定的局限性。如短進程優(yōu)先的調(diào)度算法，僅照顧了短進程而忽略了長進程，而且如果并未指明進程的長度，則短進程優(yōu)先和基于進程長度的搶占式調(diào)度算法都將無法使用。而多級反饋隊列調(diào)度算法則不必事先知道各種進程所需的執(zhí)行時間，而且還可以滿足各種類型進程的需要，因而它是目前被公認的一種較好的進程調(diào)度算法。在采用多級反饋隊列調(diào)度算法的系統(tǒng)中，調(diào)度算法的實施過程如下所述。
(1) 應(yīng)設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。
(2) 當一個新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調(diào)度。當輪到該進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第二隊列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(yè)(進程)從第一隊列依次降到第n隊列后，在第n 隊列便采取按時間片輪轉(zhuǎn)的方式運行。
(3) 僅當?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進程運行；僅當?shù)?～(i-1)隊列均空時，才會調(diào)度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務(wù)時，又有新進程進入優(yōu)先權(quán)較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調(diào)度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優(yōu)先權(quán)進程。
CPU調(diào)度算法
1 先到先服務(wù)調(diào)度FCFS（first-come,first-served）當一個進程進入到就需隊列，其pcb就被鏈接到隊列的尾部，當CPU空閑時，CPU被分配給位于隊列頭的進程。接著，該運行進程從隊/列中被刪除。FCFS策略的平均等待時間相當長FCFS調(diào)度算法是非搶占式的。2 最短作業(yè)優(yōu)先調(diào)度SJF（shortest-job-first）SJF算法的真正困難時如何知道下一個CPU請求的長度。SJF調(diào)度經(jīng)常用于長期調(diào)度。3 優(yōu)先權(quán)調(diào)度每個進程都有一個優(yōu)先權(quán)與其關(guān)聯(lián)，具有最高優(yōu)先權(quán)的進程會被分配到CPU。具有相同優(yōu)先權(quán)的進程按FCFS順序調(diào)度。優(yōu)先權(quán)可以通過內(nèi)部或外部方式來定義。優(yōu)先權(quán)調(diào)度可以使可搶占的或者非搶占的。優(yōu)先權(quán)調(diào)度算法的一個主要問題是無窮阻塞。解決辦法是老化，老化是一種技術(shù)，以逐漸增加在系統(tǒng)中等待很長時間的進程的優(yōu)先權(quán)。4 輪轉(zhuǎn)法調(diào)度輪轉(zhuǎn)法（RR）調(diào)度算法是專門為分時系統(tǒng)設(shè)計的。定義一個小時間單元，稱為時間量或時間片。時間片通常為10ms到100ms。就緒隊列作為循環(huán)隊列處理。CPU調(diào)度程序循環(huán)就需隊列，為每個進程分配不超過一個時間片間隔的CPU。如果上下文切換時間約為時間片的10%，那么約10%的CPU時間會浪費在上下文切換上。5 多級隊列調(diào)度（multilevel queue-scheduling algorithm）不同隊列可用于前臺和后臺進程，前臺隊列可能使用RR算法調(diào)度，而后臺隊列可能使用FCFS算法調(diào)度。6 多級反饋隊列調(diào)度對于多級隊列調(diào)度算法，通常進程進入系統(tǒng)時，被永久地分配到一個隊列，進程并不在隊列之間移動。linux提供了兩種獨立進程調(diào)度算法。一種是分時算法，用于在多個進程之間進行公平可搶占調(diào)度，一種是為實時任務(wù)設(shè)計的，linux只允許在用戶模式下運行的進程被搶占第一種調(diào)度類型是用于分時進程的，對于傳統(tǒng)的分時進程，linux使用了優(yōu)先權(quán)的、基于信用度的算法。每個進程都有一定數(shù)量的調(diào)度信用度，黨要選擇一個新任務(wù)運行時，具有最多信用的進程會被選擇。每次出現(xiàn)定時器中斷時，當前運行進程會失去一個信用，黨其信用為0時，它會被暫停且另一個進程會被選擇。inux使用兩種實時調(diào)度類型：先到先處理和輪轉(zhuǎn)。時間片輪轉(zhuǎn)（RR）調(diào)度對于分時系統(tǒng)更為適合。FCFS算法是非搶占的，RR算法是可搶占的。SJF和優(yōu)先級算法可以使可搶占的也可以使非搶占的。多級隊列算法允許多個不同算法用于各種類型的進程，最為常用的是前臺交互隊列（RR）和后臺批處理隊列（FCFS）。多級反饋隊列允許進程在隊列之間遷移。新聞熱點
疑難解答
