常見進程調(diào)度算法的比較與改進

摘 要：在多道程序系統(tǒng)中，有多個進程存在于主存中且其數(shù)目一般多于處理機數(shù)目，這會導(dǎo)致它們互相爭奪處理機。這就需要系統(tǒng)按某種算法，能動態(tài)地把處理機分配給處于就緒隊列中的某一個進程讓其執(zhí)行。采用什么樣的算法把處理機分配給進程便成了進程調(diào)度的核心問題，為此，該文詳細(xì)分析了處理機調(diào)度的各種調(diào)度算法。

關(guān)鍵詞：進程；調(diào)度算法；處理機

中圖分類號：TP316.81

在操作系統(tǒng)中調(diào)度的實質(zhì)是一種資源分配，因而調(diào)度算法[1]是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對于不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。

1 先來先服務(wù)和短作業(yè)（進程）優(yōu)先調(diào)度算法

先來先服務(wù)（FCFS）調(diào)度算法是一種最簡單的調(diào)度算法，既可用于作業(yè)調(diào)度，也可用于進程調(diào)度。如，用于進程調(diào)度時，總是把處理機分配給最先進入就緒隊列的進程，某進程一旦分得處理機，該進程便會一直執(zhí)行下去直到完成或者因為發(fā)生某件事阻塞后才釋放處理機。而短作業(yè)（進程）優(yōu)先調(diào)度算法（SJ（P）F）是通過計算判斷就緒進程隊列中哪一個進程或后備作業(yè)隊列中哪一個或者多個作業(yè)的預(yù)期執(zhí)行時間最短，然后進行調(diào)度。

FCFS調(diào)度算法比較有利于長作業(yè)（進程）而不利于短作業(yè)（進程）。因為短作業(yè)運行時間短，如果讓它較長時間地等待，其帶權(quán)周轉(zhuǎn)時間就會很高。由此可知，F(xiàn)CFS調(diào)度算法有利于CPU繁忙型的作業(yè)，不利于I/O繁忙型的作業(yè)。

兩種算法比較可以看到，采用SJ（P）F調(diào)度算法后，平均周轉(zhuǎn)時間和平均帶權(quán)時間都有較為明顯的改善，說明SJF調(diào)度算法能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量。

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

最高優(yōu)先權(quán)優(yōu)先（FPF）調(diào)度算法是為了照顧緊迫型作業(yè)，讓其在進入系統(tǒng)后便獲得優(yōu)先處理而引入的一種算法。該算法既可用于批處理系統(tǒng)中，也可用于實時系統(tǒng)中。而該算法的關(guān)鍵是：是使用靜態(tài)優(yōu)先權(quán)還是動態(tài)優(yōu)先權(quán)。

（1）靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。靜態(tài)優(yōu)先權(quán)調(diào)度算法簡單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)（進程）長期沒有被調(diào)度的情況。

（2）動態(tài)優(yōu)先權(quán)調(diào)度算法是以就緒隊列中各個進程的優(yōu)先權(quán)為進程調(diào)度的依據(jù)，各個進程的優(yōu)先權(quán)在創(chuàng)建進程時所賦予，可以隨著進程的推進或隨其等待時間的增加而改變。動態(tài)優(yōu)先權(quán)分為剩余時間最短者優(yōu)先和高響應(yīng)比優(yōu)先。其中高響應(yīng)比優(yōu)先，其變化規(guī)律可描述為：回應(yīng)比：W表示等待時間，S表示執(zhí)行時間，R=（W+S）/S=W/S+1，它是當(dāng)前進程執(zhí)行完畢或者需要阻塞等待某時間釋放處理機時，調(diào)度程序選擇就緒隊列的中響應(yīng)比最高的進程執(zhí)行。

動態(tài)優(yōu)先權(quán)調(diào)度算法靈活，優(yōu)先權(quán)初值低的進程在等待了一定的時間后，其優(yōu)先權(quán)可能會升為最高，然后獲得處理機。如此，可防止一些進程一直得不到調(diào)度，也可防止一個長作業(yè)長期壟斷處理機。但該算法每次進行調(diào)度前，都要先做響應(yīng)比的計算，而且要花費相當(dāng)多的執(zhí)行時間，所以系統(tǒng)開銷會比較大。

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

在分時系統(tǒng)中，為了保證能及時響應(yīng)用戶的請求，就需采用基于時間片的輪轉(zhuǎn)高度算法。其基本原理[2]是：將CPU的處理時間劃分成一個個時間片，就緒隊列中的所有進程按所分配的時間片輪流使用CPU資源。當(dāng)分配的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，該進程就被強迫讓出CPU，并被送往就緒隊列的末尾，等待下一次調(diào)度。同時，調(diào)度程序又去選擇就緒隊列中的首進程，分配給它一個時間片，依次循環(huán)。

采用此算法就需確定好時間片的大小，因為它對系統(tǒng)性能有很大的影響。小的時間片有利于短作業(yè)，因為它能較快地完成，但會導(dǎo)致過多的進程切換，從而降低了CPU效率，增加系統(tǒng)開銷；而太長的時間片，雖能使每個進程都能在一個時間片內(nèi)完成，但卻可能引起對短的交互請求的回應(yīng)變差。所以，選擇一個合理的時間片尤為重要，一般時間片略大于一次典型的交互所需的時間是一個比較合理的折衷。

以上的進程調(diào)度算法都具有一定的局限性。目前被公認(rèn)的一種較好的進程調(diào)度算法是多級反饋隊列調(diào)度算法。它可以滿足各種類型進程所需，彌補以上算法的局限性。該算法的示意圖如圖1所示。

該調(diào)度算法的思想[3]是：設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級，不同長度的時間片；第一個隊列的優(yōu)先級最高，進程所執(zhí)行時間片最小。當(dāng)一個新進程進入存儲器后，首先將其放入一個對列末尾，然后按FCFS原則排隊等待調(diào)度，如果在一個時間片結(jié)束時尚未完成，將其轉(zhuǎn)入第二隊列末尾；當(dāng)一個進程從一個對列移至第n個隊列中采用時間片輪轉(zhuǎn)執(zhí)行完。僅當(dāng)時間片空閑時，才調(diào)度第二個隊列中的進程；1～（i-1）空閑時，才調(diào)度i；如果處理機正在第i隊列中運行，又有新進程進入優(yōu)先級較高隊列，則新進程搶占處理機，將正在運行的進程放入第i隊列末尾，將處理機分配給新進程。

多級反饋隊列調(diào)度算法具有較好的性能，能很好地滿足各種類型用戶的需要。如，長批處理作業(yè)用戶，該算法可以為各隊列設(shè)置不同的時間片，再按輪轉(zhuǎn)方式運行，用戶就不必?fù)?dān)心其作業(yè)長期得不到處理。

4 結(jié)束語

處理機是最重要的計算機資源，提高處理機的利用率及改善系統(tǒng)性能，在很大程度上取決于處理機調(diào)度性能的好壞，因此，為滿足系統(tǒng)需求，應(yīng)了解并不斷改進進程調(diào)度算法，從而提高系統(tǒng)性能。

參考文獻：

[1]湯小丹.計算機操作系統(tǒng)（3版）.西安：西安電子科技大學(xué)出版社，2007（91）.

[2]肖建明，張向利.一種改進的時間片輪轉(zhuǎn)調(diào)度算法[J].計算機應(yīng)用，2005.

[3]黃斌.多級反饋隊列調(diào)度策略在Linux中的應(yīng)用和實現(xiàn)[J].計算機工程，2004.

作者簡介：田露飛（1992.11-），女，重慶人，本科在讀，計算機物聯(lián)網(wǎng)專業(yè)。

作者單位：重慶文理學(xué)院，重慶永川 402160