普通的固定優(yōu)先策略。每一個(gè)任務(wù)固定分配一個(gè)優(yōu)先級(jí)，每次調(diào)度時(shí)，從就緒隊(duì)列中選最高優(yōu)先級(jí)的那一個(gè)任務(wù)來(lái)運(yùn)行。該算法不需要去追究是誰(shuí)提出的，因?yàn)槠胀ㄈ司�能想到，長(zhǎng)期以來(lái)在計(jì)算機(jī)中實(shí)際采用。如上世紀(jì)PDP-11系列計(jì)算機(jī)中采用的RSX-11M，用的就是該策略，這個(gè)例子當(dāng)代許多大學(xué)生可能都不知道。又如，生于20世紀(jì)90年代且仍大量應(yīng)用的μcos-II及μcos-III操作系統(tǒng)，也采用了該固定優(yōu)先策略[1]。

　　摘要：優(yōu)先，可以說(shuō)這個(gè)世界無(wú)處不有。銀行排隊(duì)的時(shí)候，先來(lái)的客戶應(yīng)該先得到服務(wù)；交錢多的人往往比普通人優(yōu)先；領(lǐng)導(dǎo)較員工優(yōu)先；女士比男人優(yōu)先；孩子比成人優(yōu)先；老人比年青人優(yōu)先，等等例子實(shí)在太多。在信息和計(jì)算機(jī)系統(tǒng)中，尤其是多任務(wù)和/或多用戶環(huán)境中，也常常采用優(yōu)先調(diào)度策略，這些策略的目的在于盡量合理地利用系統(tǒng)資源，以滿足系統(tǒng)的設(shè)計(jì)要求。該文首先回顧和比對(duì)了幾個(gè)經(jīng)典的、代表性的優(yōu)先級(jí)調(diào)度策略，然后詳細(xì)提出并描述了一種新的方案，即限制優(yōu)先次數(shù)的優(yōu)先級(jí)調(diào)度算法。

　　關(guān)鍵詞：優(yōu)先調(diào)度,優(yōu)先級(jí)調(diào)度策略,限制優(yōu)先次數(shù)

　　1代表性的優(yōu)先級(jí)調(diào)度策略回顧

　　RM（RateMonotonic）調(diào)度策略。也是一個(gè)靜態(tài)的、固定的優(yōu)先策略[2]。只不過(guò)按每個(gè)任務(wù)的周期分配其優(yōu)先級(jí)，周期越短，優(yōu)先級(jí)越高，永遠(yuǎn)如此。只要一開(kāi)始排好隊(duì)，就可以一勞永逸地永遠(yuǎn)調(diào)度下去，實(shí)現(xiàn)方便，因此較早地就被吸收進(jìn)Linux中。與上一算法一樣，該算法不能動(dòng)態(tài)地依據(jù)實(shí)際情況調(diào)整優(yōu)先級(jí)。并且，它只根據(jù)固定的周期確定任務(wù)的優(yōu)先級(jí)，難道周期短的任務(wù)一定就該優(yōu)先嗎？現(xiàn)實(shí)世界中并非總是如此。

　　最早截止期優(yōu)先策略。即EDF（EarliestDeadlineFirst）[2]。有別于上面的靜態(tài)優(yōu)先策略，該算法屬動(dòng)態(tài)優(yōu)先策略。它認(rèn)為每一個(gè)任務(wù)的每一次作業(yè)均有一特定時(shí)間點(diǎn)，本次作業(yè)必須在該點(diǎn)之前完成，該時(shí)間點(diǎn)被稱作截止期。算法提出時(shí)主要針對(duì)實(shí)時(shí)系統(tǒng)，即對(duì)時(shí)間有要求的系統(tǒng)，如工業(yè)控制場(chǎng)合。而實(shí)際環(huán)境中，很多其它普通場(chǎng)合，任務(wù)的執(zhí)行時(shí)間同樣是人們所要求或期盼的。例如，要連接某一個(gè)網(wǎng)站瀏覽網(wǎng)頁(yè)時(shí)，如果過(guò)了幾十秒仍未打開(kāi)，多數(shù)人可能無(wú)法忍受，瀏覽器也設(shè)置了一個(gè)超時(shí)時(shí)間限制。因此，EDF思想具有的意義不只是局限在實(shí)時(shí)領(lǐng)域。

　　如果任務(wù)數(shù)量和周期固定，且每個(gè)任務(wù)作業(yè)的截止期與周期相等，EDF算法已被充分研究，具有不錯(cuò)的性能。但是，對(duì)于任務(wù)數(shù)或參量變動(dòng)的模型，該算法仍然有相當(dāng)?shù)难芯靠臻g和難度。需要指出的是：該算法雖能動(dòng)態(tài)地調(diào)整優(yōu)先級(jí)，但只依據(jù)截止期，與實(shí)際場(chǎng)合的對(duì)應(yīng)非常有限。另外，在實(shí)際編程的時(shí)候，因?yàn)橐�依�?jù)運(yùn)行時(shí)刻來(lái)動(dòng)態(tài)調(diào)整調(diào)度隊(duì)列，需要設(shè)置計(jì)數(shù)器，因此EDF比RM實(shí)現(xiàn)難度要大不少，尤其是系統(tǒng)中任務(wù)數(shù)量較多的時(shí)候。

　　加權(quán)的公平排隊(duì)策略。該策略主要用于網(wǎng)絡(luò)數(shù)據(jù)包發(fā)送。不同來(lái)源端口的數(shù)據(jù)包被分配不同的權(quán)值，依據(jù)權(quán)值的不同，端口數(shù)據(jù)被調(diào)度器賦予不同的服務(wù)時(shí)間。該算法的關(guān)鍵在于權(quán)值的選擇。數(shù)據(jù)量大和/或優(yōu)先級(jí)高（如交錢多的）的用戶，可分配較大的權(quán)值。在類似ATM這種以信元為單位的網(wǎng)絡(luò)中，權(quán)值的大小實(shí)際上就是時(shí)間片的多少。而在以不定長(zhǎng)數(shù)據(jù)包為發(fā)送單位的網(wǎng)絡(luò)上，先是依據(jù)權(quán)值求出各來(lái)源端口數(shù)據(jù)包可能的完成時(shí)刻，然后將這些完成時(shí)刻排隊(duì)，先發(fā)送最早完成時(shí)刻對(duì)應(yīng)的數(shù)據(jù)包。

　　通過(guò)引入不同的權(quán)值，該算法雖然比EDF策略更能反映用戶的身份差別，但也不能包打天下。例如會(huì)出現(xiàn)這樣一種優(yōu)先級(jí)被反轉(zhuǎn)的情況：如果在某一時(shí)刻，優(yōu)先級(jí)高的任務(wù)（設(shè)為任務(wù)A）數(shù)據(jù)包很長(zhǎng)，優(yōu)先級(jí)低的任務(wù)（設(shè)為任務(wù)B）數(shù)據(jù)包很短，那么，即使任務(wù)A的權(quán)值大于任務(wù)B，但如果任務(wù)B的完成時(shí)刻早于任務(wù)A，優(yōu)先級(jí)低的任務(wù)B會(huì)比優(yōu)先級(jí)高的任務(wù)A先得到服務(wù)。

　　實(shí)時(shí)RR策略和SCHED-OTHER策略。這是Linux中兩個(gè)著名調(diào)度策略，實(shí)時(shí)RR指的是某實(shí)時(shí)任務(wù)用完自己的時(shí)間片之后，將被排到調(diào)度隊(duì)列的尾部，等待下一輪調(diào)度機(jī)會(huì)[3]。SCHED-OTHER主要對(duì)普通任務(wù)，它是依據(jù)任務(wù)的動(dòng)態(tài)優(yōu)先級(jí)來(lái)選擇任務(wù)，實(shí)際上是依據(jù)一個(gè)靜態(tài)值和動(dòng)態(tài)值之和（權(quán)值）進(jìn)行決策。權(quán)值最大的任務(wù)將被投入運(yùn)行。隨著任務(wù)的執(zhí)行，其動(dòng)態(tài)值慢慢減小，當(dāng)其時(shí)間片用完之時(shí)，動(dòng)態(tài)值變?yōu)?。實(shí)時(shí)RR和SCHED-OTHER較好地兼顧了公平性與優(yōu)先級(jí)。但是，它們均是基于時(shí)間片的策略�；�于時(shí)間片設(shè)置計(jì)數(shù)器，在系統(tǒng)中需要一定的開(kāi)銷。況且，以時(shí)間片來(lái)衡量實(shí)際任務(wù)的執(zhí)行時(shí)長(zhǎng)并非總是那么完善。例如，一個(gè)特定任務(wù)很可能在一個(gè)新的時(shí)間片剛到來(lái)后就執(zhí)行完了，時(shí)間片設(shè)置過(guò)長(zhǎng)時(shí)尤其如此。時(shí)間片設(shè)置過(guò)短又會(huì)增加開(kāi)銷。

　　2限制優(yōu)先次數(shù)的優(yōu)先級(jí)調(diào)度算法

　　我們承認(rèn)系統(tǒng)中多任務(wù)的優(yōu)先級(jí)高低有別。有的要先運(yùn)行，有的請(qǐng)等一等。但在許多場(chǎng)合，雖然要盡量保證優(yōu)先級(jí)高的任務(wù)先運(yùn)行，但高優(yōu)先級(jí)的任務(wù)也不應(yīng)該長(zhǎng)期占據(jù)CPU資源，要留給低優(yōu)先級(jí)任務(wù)一定的運(yùn)行時(shí)間。經(jīng)理來(lái)了，員工讓讓步，但讓步的次數(shù)一定要有限度。這便是本算法的基本思想。

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

　　算法1是一個(gè)限制優(yōu)先次數(shù)的優(yōu)先級(jí)調(diào)度算法，如果系統(tǒng)中不是所有任務(wù)均采用該算法，則上述描述仍需進(jìn)一步改進(jìn)，復(fù)雜度將有所增加。

　　與靜態(tài)和固定優(yōu)先策略相比，算法1能動(dòng)態(tài)地進(jìn)行優(yōu)先級(jí)調(diào)整，使低優(yōu)先級(jí)的任務(wù)不至于出現(xiàn)“餓死”的情況，兼顧了公平原則；與EDF算法、RR策略以及SCHED-OTHER策略相比，算法1不是依據(jù)運(yùn)行時(shí)刻來(lái)動(dòng)態(tài)調(diào)整調(diào)度隊(duì)列，實(shí)際開(kāi)銷和實(shí)現(xiàn)難度要小一些。它只在調(diào)度的時(shí)候才進(jìn)行計(jì)數(shù)器減1，不依賴于時(shí)間片的選擇；與加權(quán)的公平排隊(duì)策略相比，算法1不會(huì)出現(xiàn)優(yōu)先級(jí)反轉(zhuǎn)的情況。

　　參考文獻(xiàn)：

　　[1]李承創(chuàng)，陳躍斌，房曉麗，王兵.μC/OS-III在Cortex-M3處理器上的移植[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2012，20（11）：42-48.

　　[2]LiuCL，LaylanJW.SchedulingAlgorithmsforMultiprogramminginaHardReal–TimeEnvironment[J].J.ACM，1973，20（1）：40-61.

　　[3]林闖，單志廣，任豐原.計(jì)算機(jī)網(wǎng)絡(luò)的服務(wù)質(zhì)量（QoS）[M].北京：清華大學(xué)出版社，2004.

轉(zhuǎn)載請(qǐng)注明來(lái)自：http://www.jinnzone.com/jisuanjiwangluolw/28949.html