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

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

中圖分類(lèi)號(hào)：TP316.81

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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