鄭坤

摘要：在實(shí)時(shí)系統(tǒng)中，進(jìn)程調(diào)度算法性能的好壞直接對系統(tǒng)的實(shí)時(shí)性起著決定性的作用。因此，該文介紹實(shí)時(shí)調(diào)度和進(jìn)程調(diào)度算法的相關(guān)定義，對常見的動(dòng)態(tài)優(yōu)先級調(diào)度算法和靜態(tài)優(yōu)先級調(diào)度算法的不足之處進(jìn)行了解析。據(jù)此提出了一種基于優(yōu)先級的動(dòng)態(tài)分配策略（Dynamic allocation strategy based on priority）的進(jìn)程調(diào)度算法。

關(guān)鍵詞：實(shí)時(shí)操作系統(tǒng)；進(jìn)程調(diào)度；調(diào)度算法

中圖分類號：TP316 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）31-7310-03

在實(shí)時(shí)系統(tǒng)的使用中，我們應(yīng)理解它的一些基本特點(diǎn)才能更好的應(yīng)用它。在實(shí)時(shí)系統(tǒng)中，計(jì)算的正確性不僅依賴于程序運(yùn)行的邏輯結(jié)果，還依賴于這個(gè)結(jié)果產(chǎn)生的時(shí)間，在邏輯上和時(shí)間上出現(xiàn)的任何偏差將對系統(tǒng)產(chǎn)生嚴(yán)重后果。實(shí)時(shí)系統(tǒng)主要分為兩種類型：硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)。在硬實(shí)時(shí)系統(tǒng)中，系統(tǒng)要確保進(jìn)程有最壞情況下的處理時(shí)間，即對于各進(jìn)程不僅要執(zhí)行無誤，并且響應(yīng)時(shí)間的截止期限必須得到滿足（即做到準(zhǔn)時(shí)）。在軟實(shí)時(shí)系統(tǒng)中，進(jìn)程能夠得到有確保的處理時(shí)間，能夠在截止期限到來之前得到處理，但違反截止期限并不會(huì)帶來致命的錯(cuò)誤（即允許不準(zhǔn)時(shí)）。實(shí)時(shí)系統(tǒng)的應(yīng)用領(lǐng)域很廣泛，計(jì)算機(jī)系統(tǒng)為了提供對于實(shí)時(shí)性的支持，其操作系統(tǒng)必須對 CPU 和其他資源進(jìn)行有效的調(diào)度和管理。

1 實(shí)時(shí)系統(tǒng)調(diào)度算法

在多任務(wù)實(shí)時(shí)系統(tǒng)中，處理任務(wù)的最終目標(biāo)是通過進(jìn)程調(diào)度算法，在進(jìn)程截止期前執(zhí)行使盡可能多的進(jìn)程，從而提高系統(tǒng)性能。然而，在處理時(shí)間有限的實(shí)時(shí)系統(tǒng)中對多個(gè)進(jìn)程進(jìn)行調(diào)度的決策是很困難的，因?yàn)樵摏Q策會(huì)涉及到大量的實(shí)時(shí)進(jìn)程屬性和實(shí)時(shí)系統(tǒng)相關(guān)參數(shù)。

多進(jìn)程的系統(tǒng)必須擔(dān)負(fù)起調(diào)度進(jìn)程的責(zé)任，不斷地進(jìn)行切換進(jìn)程，以使CPU獲得最大的利用率。當(dāng)有多個(gè)進(jìn)程就緒時(shí)，操作系統(tǒng)必須決定先運(yùn)行那一個(gè)，對CPU訪問權(quán)限裁決的過程被稱為調(diào)度（Scheduling）。本質(zhì)上調(diào)度其實(shí)就是系統(tǒng)根據(jù)調(diào)度算法策略與資源控制協(xié)議的規(guī)則，為一組處于就緒狀態(tài)的進(jìn)程分配資源并選擇符合系統(tǒng)要求的進(jìn)程組成一個(gè)隊(duì)列到處理機(jī)上去依次執(zhí)行，并而在這一過程中要保證所有進(jìn)程對時(shí)限的要求。假如實(shí)時(shí)系統(tǒng)若有m個(gè)周期性進(jìn)程，進(jìn)程i的周期為[Pi]，其中每個(gè)事件進(jìn)程需要[Ci]秒的CPU時(shí)間來處理，則只有滿足以下條件：[i=1mCiPi≤1]才可能處理所有負(fù)載。滿足該條件的系統(tǒng)進(jìn)程集認(rèn)為是可調(diào)度的（Schedulable）。實(shí)時(shí)調(diào)度強(qiáng)調(diào)的是進(jìn)程的時(shí)間約束，尤其是在硬實(shí)時(shí)系統(tǒng)的設(shè)計(jì)中，評價(jià)調(diào)度程序好壞與否不在于調(diào)度的公平性和最小響應(yīng)時(shí)間，而是所有硬實(shí)時(shí)系統(tǒng)中進(jìn)程能否在最后截止期限內(nèi)完成。在實(shí)時(shí)調(diào)度過程中使用的調(diào)度策略方法或資源控制協(xié)議，通常我們稱為實(shí)時(shí)調(diào)度算法。

2 常見的實(shí)時(shí)調(diào)度算法及其不足

實(shí)時(shí)系統(tǒng)必須保證在確定的時(shí)間內(nèi)對事件進(jìn)行處理，因此必須要有一個(gè)良好的進(jìn)程調(diào)度算法，它具有如下特點(diǎn)：①公平；②高效；③響應(yīng)及時(shí)；④利用率高[1]。顯然，在任何一個(gè)操作系統(tǒng)中同時(shí)滿足這幾個(gè)目標(biāo)是不太現(xiàn)實(shí)的，必須在這幾個(gè)方面進(jìn)行相應(yīng)的取舍與折中考慮，從而確定自己的調(diào)度算法。目前在實(shí)時(shí)系統(tǒng)中常見的實(shí)時(shí)調(diào)度算法有單調(diào)速率調(diào)度算法（RMS），最早截止時(shí)間優(yōu)先調(diào)度算法（EDF）等。還有一些在此基礎(chǔ)上進(jìn)行優(yōu)化或者改進(jìn)而成的算法，如截止期限單調(diào)調(diào)度算法（Deadline Monotonic Scheduling， DMS）、最短空閑時(shí)間優(yōu)先調(diào)度算法（Least Laxity First， LLF）等。

1）速率單調(diào)調(diào)度算法

單調(diào)速率調(diào)度（RMS）算法是C. L. Liu和J. W. Layland在1973年提出的一種基于周期和多進(jìn)程的靜態(tài)優(yōu)先級可搶占調(diào)度算法[2]。RMS是針對周期進(jìn)程的優(yōu)先級調(diào)度算法，當(dāng)進(jìn)程的截止時(shí)間等于其周期時(shí)，RMS算法已被證明是靜態(tài)最優(yōu)的調(diào)度算法。C. L. Liu和J . W. Layland給出了RMS算法可調(diào)度的充分非必要條件，[C0T0+C1T1+……+CnTn≤n（21n-1）]，其中C為進(jìn)程，T為周期，n為進(jìn)程個(gè)數(shù)。這種算法執(zhí)行起來開銷很小，可調(diào)度性測試簡單，但最大的局限性就在于該算法不可能總使CPU被完全利用。在最差情況下可調(diào)度的范圍為[Wn=n（21n-1）]。不難看出，當(dāng)系統(tǒng)中只有一個(gè)進(jìn)程運(yùn)行時(shí)，最差的可調(diào)度范圍為100%；當(dāng)系統(tǒng)中有多個(gè)進(jìn)程運(yùn)行時(shí)，可調(diào)度范圍逐漸降低，達(dá)到極限值69.3%左右。所以，當(dāng)系統(tǒng)中的進(jìn)程總量不超過[n（21n-1）]）時(shí)，RMS算法可以調(diào)度執(zhí)行系統(tǒng)所有的進(jìn)程并滿足它們的時(shí)限要求。當(dāng)系統(tǒng)超過此負(fù)載限制時(shí)，系統(tǒng)調(diào)度就有可能出現(xiàn)不能滿足進(jìn)程執(zhí)行時(shí)限的現(xiàn)象。

2） 最早截止期限優(yōu)先調(diào)度

最早截止期限優(yōu)先調(diào)度算法（EDF） [3]是一種基于優(yōu)先級的搶占式動(dòng)態(tài)最優(yōu)調(diào)度算法，也稱為死限驅(qū)動(dòng)調(diào)度算法（Deadline Driver Scheduling， DDS）。該算法的進(jìn)程優(yōu)先級初始之時(shí)并不固定，而是隨著啟動(dòng)時(shí)間的變化而動(dòng)態(tài)地改變，以距離最后截止期限時(shí)間的長短來分配優(yōu)先級，具體地說就是距離最后截止期限時(shí)間越短的進(jìn)程越緊急，相應(yīng)的進(jìn)程優(yōu)先級也就越高；距離最后截止期限時(shí)間越長的進(jìn)程對完成截止時(shí)間要求越松弛，該進(jìn)程的優(yōu)先級也就越低。系統(tǒng)每時(shí)每刻總是在就緒隊(duì)列中挑選最早到達(dá)絕對最后截止期限的進(jìn)程在處理機(jī)上執(zhí)行。事實(shí)上，EDF算法是一種最優(yōu)的單處理器調(diào)度算法，對于相對期限等于周期且總資源利用率不大于[n（21n-1）]的周期進(jìn)程集，可由該算法進(jìn)行調(diào)度。實(shí)踐表明，EDF算法的優(yōu)點(diǎn)在于系統(tǒng)負(fù)載較低時(shí)，效率較高，相對容易實(shí)現(xiàn)。缺點(diǎn)在于該算法理論上能對系統(tǒng)可調(diào)度負(fù)載進(jìn)行優(yōu)化，但不能解決系統(tǒng)負(fù)載較重時(shí)，系統(tǒng)性能急劇下降的問題。C. L. Liu和J. W. Layland給出了采用EDF算法可調(diào)度的充分必要條件，[C0T0+C1T1+……+CnTn≤1]，其中C為進(jìn)程，T為周期，n為進(jìn)程個(gè)數(shù)。由于EDF算法在運(yùn)行時(shí)系統(tǒng)開銷較大，特別是在過載情況下，由于大量進(jìn)程錯(cuò)過最后截止期限引發(fā)CPU頻繁的進(jìn)程調(diào)度，消耗了大量的CPU時(shí)間，這時(shí)候系統(tǒng)的性能可能還不如先來先服務(wù)FIFO（First In First out）調(diào)度算法穩(wěn)定。另外EDF算法在實(shí)際應(yīng)用中可能會(huì)出現(xiàn)優(yōu)先級倒置的現(xiàn)象，所以EDF算法在實(shí)際應(yīng)用中還存在一些問題。

3）最短空閑時(shí)間優(yōu)先調(diào)度

最短空閑時(shí)間優(yōu)先調(diào)度算法（LLF）也叫最小松弛時(shí)間優(yōu)先調(diào)度算法，是在EDF算法的基礎(chǔ)之上發(fā)展起來的一種動(dòng)態(tài)調(diào)度算法。該算法首先根據(jù)進(jìn)程完成的截止時(shí)間和剩余的執(zhí)行時(shí)間來計(jì)算進(jìn)程的空閑時(shí)間，即空閑時(shí)間=截止時(shí)間-剩余執(zhí)行時(shí)間；然后再根據(jù)進(jìn)程的空閑時(shí)間來動(dòng)態(tài)分配優(yōu)先級，空閑時(shí)間越短，優(yōu)先級越高，空閑時(shí)間越長，優(yōu)先級越低。在執(zhí)行的過程中，隨著時(shí)間的向前推進(jìn)，等待進(jìn)程的空閑時(shí)間越來越短，相應(yīng)的進(jìn)程等待執(zhí)行的緊急程度也就越來越緊迫，因此，等待進(jìn)程隨時(shí)可能會(huì)搶占當(dāng)前執(zhí)行的進(jìn)程，從而造成了進(jìn)程之間的相互競爭，導(dǎo)致了進(jìn)程之間的頻繁切換現(xiàn)象較為嚴(yán)重，大大增加了系統(tǒng)時(shí)間開銷，其實(shí)際應(yīng)用受到了一定的限制。

假設(shè)在開始運(yùn)行時(shí)，實(shí)時(shí)系統(tǒng)的所有進(jìn)程同時(shí)放行，首先獲得系統(tǒng)執(zhí)行權(quán)的是基本優(yōu)先級最高的進(jìn)程。隨著系統(tǒng)運(yùn)行時(shí)間的推移，所有進(jìn)程的優(yōu)先級在動(dòng)態(tài)變化著，其中執(zhí)行進(jìn)程的執(zhí)行緊迫性保持不變，而其剩余價(jià)值密度卻在不斷增加，這就避免了其它進(jìn)程來搶占執(zhí)行進(jìn)程。對于活動(dòng)進(jìn)程和等待進(jìn)程恰好相反，其執(zhí)行緊迫性不斷增加，而剩余價(jià)值密度保持不變，這就為搶占系統(tǒng)執(zhí)行權(quán)提供了機(jī)會(huì)。此外，通過調(diào)節(jié)參數(shù)q和p的取值，可以調(diào)節(jié)進(jìn)程執(zhí)行緊迫性和剩余價(jià)值密度對進(jìn)程動(dòng)態(tài)優(yōu)先級的影響力。若q的值較大時(shí)，可以增加價(jià)值密度低的進(jìn)程參與系統(tǒng)執(zhí)行的機(jī)會(huì)，但使進(jìn)程搶占的概率大大增加，可能會(huì)造成部分價(jià)值密度大的進(jìn)程夭折而降低系統(tǒng)累積價(jià)值收益。若p值較大時(shí)，能提高系統(tǒng)累積價(jià)值收益，能減少執(zhí)行進(jìn)程被搶占而夭折的概率，進(jìn)而減少了進(jìn)程搶占的次數(shù)，提高進(jìn)程的執(zhí)行成功率。

4 總結(jié)

本文綜合了進(jìn)程執(zhí)行緊迫性和剩余價(jià)值密度隨時(shí)間變化的這兩方面因素，提出了基于優(yōu)先級的動(dòng)態(tài)分配策略DAS，通過論證證明該算法可通過改變參數(shù)q和p的取值，調(diào)節(jié)進(jìn)程執(zhí)行緊迫性和剩余價(jià)值密度對進(jìn)程優(yōu)先級影響的權(quán)重，從而提高了算法應(yīng)對不同應(yīng)用需要的靈活性，提高了進(jìn)程的執(zhí)行效率。

參考文獻(xiàn)：

[1] 鄒勇，王青，李明樹.Linux內(nèi)核的實(shí)時(shí)支持的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展，2002，39（4）：466-472.

[2] Liu C L，Layland James W. Scheduling algorithms for multiprogramming in a hard real-time environment[J].Journal of the ACM， 1973，20（1）：46-61

[3] Haritsa J R， Livny M，Carey M J.Earliest deadline scheduling for real-time database systems [C]//Proceedings of the 12th IEEE Real-Time Systems Symposium. San Antonio TX， USA，1991：232-243。

[4] Aldarmi S A，Burns A.Dynamic value-density for scheduling real-time systems[C]//Proceedings of the 11th Euromicro Conference on Real-Time Systems. York， England， UK，1999：270-277.