操作系統常用調度算法

操作系統常用調度算法

一．先來先服務調度算法

先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用于作業調度，也可用于進程調度。當在作業調度中采用該算法時，每次調度都是從后備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然后放入就緒隊列。在進程調度中采用FCFS算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞后才放棄處理機。

優缺點：FCFS調度算法的特點是算法簡單，但效率低；對長作業比較有利，但對短作業不利（相對SJF和高響應比）；有利于CPU繁忙型作業，而不利于I/O繁忙型作業。

二．短作業優先調度算法

短作業(進程)優先調度算法SJ(P)F，是指對短作業或短進程優先調度的算法。它們可以分別用于作業調度和進程調度。短作業優先(SJF)的調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行并一直執行到完成，或發生某事件而被阻塞放棄處理機時再重新調度。

缺點：需要事先預知作業的運行時間，對長作業非常不利，完全為考慮緊迫程度，因此不能保證緊迫性作業得到及時解決，采用短作業優先調度算法無法實現人機交互。

三．高優先權優先調度算法

1.優先權調度算法類型

（1）非搶占是優先權調度算法

  在這種方式下，系統一旦把處理機分配給就緒隊列中優先權最高的進程后，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度算法主要用于批處理系統中；也可用于某些對實時性要求不嚴的實時系統中。

（2）搶占式優先權調度算法

     在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在采用這種調度算法時，是每當系統中出現一個新的就緒進程i 時，就將其優先權Pi與正在執行的進程j 的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi>Pj，則立即停止Pj的執行，做進程切換，使i 進程投入執行。顯然，這種搶占式的優先權調度算法能更好地滿足緊迫作業的要求，故而常用于要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。

2.高響應比優先調度算法

  在批處理系統中，短作業優先算法是一種比較好的算法，其主要的不足之處是長作業的運行得不到保證。如果我們能為每個作業引入前面所述的動態優先權，并使作業的優先級隨著等待時間的增加而以速率a 提高，則長作業在等待一定的時間后，必然有機會分配到處理機。該優先權的變化規律可描述為：
由于等待時間與服務時間之和就是系統對該作業的響應時間，故該優先權又相當于響應比RP。據此，又可表示為：

有上式可以看出：

(1) 如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利于短作業。

(2) 當要求服務的時間相同時，作業的優先權決定于其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務。

(3) 對于長作業，作業的優先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先級便可升到很高，從而也可獲得處理機。簡言之，該算法既照顧了短作業，又考慮了作業到達的先后次序，不會使長作業長期得不到服務。因此，該算法實現了一種較好的折衷。當然，在利用該算法時，每要進行調度之前，都須先做響應比的計算，這會增加系統開銷。

四．基于時間片的輪轉調度算法

1．時間片輪轉法

1) 基本原理

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

2．多級反饋隊列調度算法

前面介紹的各種用作進程調度的算法都有一定的局限性。如短進程優先的調度算法，僅照顧了短進程而忽略了長進程，而且如果并未指明進程的長度，則短進程優先和基于進程長度的搶占式調度算法都將無法使用。而多級反饋隊列調度算法則不必事先知道各種進程所需的執行時間，而且還可以滿足各種類型進程的需要，因而它是目前被公認的一種較好的進程調度算法。在采用多級反饋隊列調度算法的系統中，調度算法的實施過程如下所述。

(1) 應設置多個就緒隊列，并為各個隊列賦予不同的優先級。第一個隊列的優先級最高，第二個隊列次之，其余各隊列的優先權逐個降低。該算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。

(2) 當一個新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(進程)從第一隊列依次降到第n隊列后，在第n 隊列便采取按時間片輪轉的方式運行。

(3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1～(i-1)隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。

多級反饋隊列的優勢有：

終端型作業用戶：短作業優先。

短批處理作業用戶：周轉時間較短。

長批處理作業用戶：經過前面幾個隊列得到部分執行，不會長期得不到處理。

五．空閑分區非配算法

     （1）首次適應算法。使用該算法進行內存分配時，從空閑分區鏈首開始查找，直至找到一個能滿足其大小要求的空閑分區為止。然后再按照作業的大小，從該分區中劃出一塊內存分配給請求者，余下的空閑分區仍留在空閑分區鏈中。

    　　該算法傾向于使用內存中低地址部分的空閑分區，在高地址部分的空閑分區很少被利用，從而保留了高地址部分的大空閑區。顯然為以后到達的大作業分配大的內存空間創造了條件。缺點在于低址部分不斷被劃分，留下許多難以利用、很小的空閑區，而每次查找又都從低址部分開始，這無疑會增加查找的開銷。

    　（2）循環首次適應算法。該算法是由首次適應算法演變而成的。在為進程分配內存空間時，不再每次從鏈首開始查找，而是從上次找到的空閑分區開始查找，直至找到一個能滿足要求的空閑分區，并從中劃出一塊來分給作業。該算法能使空閑中的內存分區分布得更加均勻，但將會缺乏大的空閑分區。

    　（3）最佳適應算法。該算法總是把既能滿足要求，又是最小的空閑分區分配給作業。

    　　為了加速查找，該算法要求將所有的空閑區按其大小排序后，以遞增順序形成一個空白鏈。這樣每次找到的第一個滿足要求的空閑區，必然是最優的。孤立地看，該算法似乎是最優的，但事實上并不一定。因為每次分配后剩余的空間一定是最小的，在存儲器中將留下許多難以利用的小空閑區。同時每次分配后必須重新排序，這也帶來了一定的開銷。

    　　（4）最差適應算法。最差適應算法中，該算法按大小遞減的順序形成空閑區鏈，分配時直接從空閑區鏈的第一個空閑分區中分配（不能滿足需要則不分配）。很顯然，如果第一個空閑分區不能滿足，那么再沒有空閑分區能滿足需要。這種分配方法初看起來不太合理，但它也有很強的直觀吸引力：在大空閑區中放入程序后，剩下的空閑區常常也很大，于是還能裝下一個較大的新程序。

    　　最壞適應算法與最佳適應算法的排序正好相反，它的隊列指針總是指向最大的空閑區，在進行分配時，總是從最大的空閑區開始查尋。

    　　該算法克服了最佳適應算法留下的許多小的碎片的不足，但保留大的空閑區的可能性減小了，而且空閑區回收也和最佳適應算法一樣復雜。

六．虛擬頁式存儲管理中的頁面置換算法

    1.理想頁面置換算法(OPT)：這是一種理想的算法，在實際中不可能實現。該算法的思想是：發生缺頁時，選擇以后永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。

    2.先進先出頁面置換算法(FIFO)：選擇最先進入內存的頁面予以淘汰。

    3.最近最久未使用算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

   4.最少使用算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。

七．磁盤調度算法

    1.先來先服務算法（FCFS）First Come First Service

這是一種比較簡單的磁盤調度算法。它根據進程請求訪問磁盤的先后次序進行調度。此算法的優點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。

    2、最短尋道時間優先算法（SSTF） Shortest Seek Time First

該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶的服務請求的響應機會不是均等的，因而導致響應時間的變化幅度很大。在服務請求很多的情況下，對內外邊緣磁道的請求將會無限期的被延遲，有些請求的響應時間將不可預期。

    3、掃描算法（SCAN）電梯調度

掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，掃描算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁道，在當前磁道之內，從而避免了饑餓現象的出現。由于這種算法中磁頭移動的規律頗似電梯的運行，故又稱為電梯調度算法。此算法基本上克服了最短尋道時間優先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優先算法的優點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側磁道被訪問的頻率仍低于中間磁道。

    4、循環掃描算法（CSCAN）

循環掃描算法是對掃描算法的改進。如果對磁道的訪問請求是均勻分布的，當磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少。這是由于這些磁道剛被處理，而磁盤另一端的請求密度相當高，且這些訪問請求等待的時間較長，為了解決這種情況，循環掃描算法規定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構成循環，進行掃描。