常用調(diào)度算法總結(jié)

分類： 操作系統(tǒng) 2013-08-10 17:59 71人閱讀 評論(0) 收藏 舉報

目錄(?)[+]

先來先服務(wù)隊列

最短優(yōu)先優(yōu)先隊列

高優(yōu)先權(quán)優(yōu)先調(diào)度算法

優(yōu)先權(quán)調(diào)度算法的類型

高響應(yīng)比優(yōu)先調(diào)度算法

基于時間片的輪轉(zhuǎn)調(diào)度算法

時間片輪轉(zhuǎn)法

多級反饋隊列調(diào)度算法

電梯調(diào)度算法

調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法，如任務(wù)A在執(zhí)行完后，選擇哪個任務(wù)來執(zhí)行，使得某個因素（如進(jìn)程總執(zhí)行時間，或者磁盤尋道時間等）最小。對于不同的系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。
幾個常用的操作系統(tǒng)進(jìn)程調(diào)度算法。

1 先來先服務(wù)（隊列）

先來先服務(wù)(FCFS)調(diào)度算法是一種最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時，每次調(diào)度都是從后備作業(yè)隊列中選擇一個或多個最先進(jìn)入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊列。在進(jìn)程調(diào)度中采用FCFS算法時，則每次調(diào)度是從就緒隊列中選擇一個最先進(jìn)入該隊列的進(jìn)程，為之分配處理機，使之投入運行。該進(jìn)程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。
缺點：比較有利于長作業(yè)，而不利于短作業(yè)。 有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。

2 最短優(yōu)先（優(yōu)先隊列）

最短優(yōu)先調(diào)度算法是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法則是從就緒隊列中選出一個估計運行時間最短的進(jìn)程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時再重新調(diào)度。
缺點：長作業(yè)的運行得不到保證。

2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法

2.1 優(yōu)先權(quán)調(diào)度算法的類型

為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度算法，還可用于實時系統(tǒng)中。當(dāng)把該算法用于作業(yè)調(diào)度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時，該算法是把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程，這時，又可進(jìn)一步把該算法分成如下兩種。
1) 非搶占式優(yōu)先權(quán)算法
在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴(yán)的實時系統(tǒng)中。
2) 搶占式優(yōu)先權(quán)調(diào)度算法
在這種方式下，系統(tǒng)同樣是把處理機分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進(jìn)程。因此，在采用這種調(diào)度算法時，是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程i 時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j 的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj，原進(jìn)程Pj便繼續(xù)執(zhí)行；但如果是Pi>Pj，則立即停止Pj的執(zhí)行，做進(jìn)程切換，使i 進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。

2.2 高響應(yīng)比優(yōu)先調(diào)度算法

在批處理系統(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)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：

由上式可以看出：
(1) 如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。
(2) 當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。
(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機。
簡言之，該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，不會使長作業(yè)長期得不到服務(wù)。因此，該算法實現(xiàn)了一種較好的折衷。當(dāng)然，在利用該算法時，每要進(jìn)行調(diào)度之前，都須先做響應(yīng)比的計算，這會增加系統(tǒng)開銷。

3 基于時間片的輪轉(zhuǎn)調(diào)度算法

3.1 時間片輪轉(zhuǎn)法

在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把CPU 分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。時間片的大小從幾ms 到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進(jìn)程在一給定的時間內(nèi)均能獲得一時間片的處理機執(zhí)行時間。換言之，系統(tǒng)能在給定的時間內(nèi)響應(yīng)所有用戶的請求。

3.2 多級反饋隊列調(diào)度算法

前面介紹的各種用作進(jìn)程調(diào)度的算法都有一定的局限性。如短進(jìn)程優(yōu)先的調(diào)度算法，僅照顧了短進(jìn)程而忽略了長進(jìn)程，而且如果并未指明進(jìn)程的長度，則短進(jìn)程優(yōu)先和基于進(jìn)程長度的搶占式調(diào)度算法都將無法使用。而多級反饋隊列調(diào)度算法則不必事先知道各種進(jìn)程所需的執(zhí)行時間，而且還可以滿足各種類型進(jìn)程的需要，因而它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。在采用多級反饋隊列調(diào)度算法的系統(tǒng)中，調(diào)度算法的實施過程如下所述。
(1) 應(yīng)設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進(jìn)程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。
(2) 當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當(dāng)一個長作業(yè)(進(jìn)程)從第一隊列依次降到第n隊列后，在第n 隊列便采取按時間片輪轉(zhuǎn)的方式運行。
(3) 僅當(dāng)?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進(jìn)程運行；僅當(dāng)?shù)?～(i-1)隊列均空時，才會調(diào)度第i隊列中的進(jìn)程運行。如果處理機正在第i隊列中為某進(jìn)程服務(wù)時，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進(jìn)程將搶占正在運行進(jìn)程的處理機，即由調(diào)度程序把正在運行的進(jìn)程放回到第i隊列的末尾，把處理機分配給新到的高優(yōu)先權(quán)進(jìn)程。

4 電梯調(diào)度算法

高層建筑中電梯請求不斷地到來，控制電梯的計算機能夠很容易地跟蹤顧客按下請求的順序。如果使用先來先服務(wù)算法調(diào)度，同時如果電梯負(fù)載很重，那么大部分時間電梯將停留在電梯的中部區(qū)域，而電梯兩端區(qū)域的請求將不得不等待，直到負(fù)載中的統(tǒng)計波動使得中部區(qū)域沒有請求位置，這樣導(dǎo)致遠(yuǎn)離中部區(qū)域的請求得到的服務(wù)很差。因此獲得最小響應(yīng)時間的目標(biāo)和公平性之間存在著沖突。
大多數(shù)電梯使用電梯算法來協(xié)調(diào)效率和公平性這兩個相互沖突的目標(biāo)。電梯算法電梯保持按一個方向移動，直到在那個方向上沒有請求位置，然后改變方向。
電梯算法(elevation algorithm)需要軟件維護(hù)一個二進(jìn)制位，即當(dāng)前方向位：向上(up)或向下(down)。當(dāng)一個請求處理完成之后，電梯的驅(qū)動程序檢查該位，如果是up，電梯移至下一個更高的未完成的請求。如果更高的位置沒有未完成的請求，則方向位取反。當(dāng)方向位設(shè)置為down時，同時存在一個低位置的請求，則移向該位置。

現(xiàn)在我們明白了，電梯的上下箭頭按鈕是為了告訴電梯你想向上還是向下去），而不是讓電梯向上還是向下。

舉例：電梯在上行，5樓有上召和下召。電梯會停5樓，但它是為上召服務(wù)的，所以下召燈還會保持點亮。然后啟動向上，直到服務(wù)完上行的所有請求。轉(zhuǎn)下行，到五樓時還是會停。這時是服務(wù)5樓下召的。

電梯處理請求規(guī)則：
電梯有移動方向，各樓層的請求有請求方向，這里維護(hù)一個請求表（記錄請求ID，請求方向，該請求的停靠樓層）。因為電梯會按照移動方向移動，直到該方向沒有請求（請求包括請求ID和停靠樓層的請求），所以不會根據(jù)請求方向突然改變電梯的移動方向。因此，電梯在移動過程中只處理與“電梯移動方向”相同的“請求方向”的請求。如電梯向下移動，只處理向下的請求，且該請求的方向也向下（停靠樓層請求無方向）。

具體算法過程舉例如下：

操作系統(tǒng)中的磁盤壁調(diào)度算法（讀寫一個磁盤塊需要的時間主要因素是尋道時間：將磁盤臂移動到適當(dāng)?shù)闹嫠璧臅r間）也運用了電梯算法。

轉(zhuǎn)載于:https://www.cnblogs.com/wanghuaijun/p/6937463.html

總結(jié)

以上是生活随笔為你收集整理的常用调度算法总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。