靜態優先順序調度演算法

❶ 靜態搶占式優先順序調度演算法是如何進行的

按照優先順序值的大小進行調度，選擇優先順序值大的作業優先調度。搶占式是指如果進入的作業的優先順序數大於當前正在執行的作業的優先順序數，就執行進入的作業，搶佔了當前正在執行的作業的資源。
按照到達時間將作業放入就緒隊列，當前作業執行過程中有作業進入，根據作業的優先順序值進行判斷，如果進入的作業的優先順序值小於或等於當前執行的作業的優先順序值，繼續執行當前作業；如果進入的作業的優先順序值大於當前執行的作業的優先順序值，將資源給進入的作業，當前的作業就放入就緒隊列隊尾，此時還需要的服務時間為原服務時間-進入的作業的到達時間。之後，每到達一個作業就與當前執行的作業進行優先順序值比較，優先順序值大的優先執行。當當前執行的作業執行結束後，比較就緒隊列中的作業的優先順序值，優先順序值大的優先執行。如此執行，直到就緒隊列為空，結束調度。

❷ 進程調度的實時系統

最簡單最直觀的進程調度策略是基於優先順序的調度，多數實時系統採用基於優先順序的調度，每個進程根據它重要程度的不同被賦予不同的優先順序，調度器在每次調度時，總選擇優先順序最高的進程開始執行.
首先要考慮的問題是如何分配優先順序，對於進程優先順序的分配可以採用靜態和動態兩種方式，靜態優先順序調度演算法：這種調度演算法給那些系統中得到運行的所有進程都靜態地分配一個優先順序.靜態優先順序的分配可以根據應用的屬性來進行，比如進程的周期，用戶優先順序，或者其它的預先確定的策略.單調率演算法(RM)調度演算法是一種典型的靜態優先順序調度演算法，它根據進程的執行周期的長短來決定調度優先順序，那些具有小的執行周期的進程具有較高的優先順序.動態優先順序調度演算法：這種調度演算法根據進程的資源需求來動態地分配進程的優先順序，其目的就是在資源分配和調度時有更大的靈活性.在實時系統中，最早期限優先演算法(EDF)演算法是使用最多的一種動態優先順序調度演算法，該演算法給就緒隊列中的各個進程根據它們的截止期限(Deadline)來分配優先順序，具有最近的截止期限的進程具有最高的優先順序.
分配好優先順序之後下一個要考慮的問題是何時讓高優先順序進程掌握CPU的使用權，這取決於操作系統的內核，有不可搶占式和可搶占式兩種.
不可搶占式內核要求每個進程自我放棄CPU的所有權，各個進程彼此合作共享一個CPU.非同步事件還是由中斷服務來處理.中斷服務可以使一個高優先順序的進程由掛起狀態變為就緒狀態.但中斷服務以後控制權還是回到原來被中斷了的那個進程，直到該進程主動放棄CPU的使用權時，那個高優先順序的進程才能獲得CPU的使用權.這就出現了響應時間的問題，高優先順序的進程已經進入了就緒狀態但不能執行，這樣進程的響應時間變得不再確定這與實時系統的要求不符，因此一般的實時操作系統都要求是可搶占式的內核，當一個運行著的進程使一個比它優先順序高的進程進入了就緒態，當前進程的CPU使用權就被剝奪了，或者說被掛起了，那個高優先順序的進程立刻得到了CPU的控制權，如果是中斷服務子程序使一個高優先順序的進程進入就緒態，中斷完成時，中斷了的進程被掛起，優先順序高的那個進程開始運行.在這種內核設置下，多個進程可能處於並發的狀態，這就出現了多個進程共享資源的情況，因此我們需要設置信號量來保證臨界資源的正確使用，任何一個想使用臨界資源的進程在進入臨界區之前必須擁有使用臨界資源的信號量，否則不可以執行臨界區代碼.
這樣基於優先順序的可搶占式進程調度策略就基本架構完成，但此時仍然有系統崩潰的危險，假設系統中有3個進程，分別為p1，p2和p3. p1的優先權高於p2，而p2的優先權高於p3.恰在此時p1和p2 因某種原因被阻塞，這時候系統調度p3執行.p3執行一段時間後，p1被喚醒.由於採取的是PBP的調度策略，因此p1搶占 p3的CPU， p1執行.p1執行一段時間後要進入臨界區，但此時p3佔有此臨界資源的信號量.因此p1被阻塞，處於等待狀態，等待p3 釋放此信號量.經過這么一段時間後，p2此時此刻處於就緒狀態.因此系統調度p2執行.如果p3在p2的執行期間一直沒有能夠被調度執行的話，那p1和p3將一直等到p2執行完後才能執行，p1更要等到p3釋放它所把持的信號量才能執行；而這段時間完全有可能超出p1的Deadline，使得p1崩潰.我們看到在這個過程中，由於臨界資源的使用問題使得優先順序低的進程先於優先順序高的進程先執行，這就出現了優先順序反轉的問題，從而造成了系統崩潰，對於這個問題可以採用優先順序繼承的辦法來進行解決.在優先順序繼承方案中，當高優先順序進程在等待低優先順序的進程佔有的信號量時，讓低優先順序進程繼承高優先順序進程的優先順序，即把低優先順序進程的優先權提高到高優先順序進程的優先順序；當低優先順序進程釋放高優先順序進程等待的信號量時，立即把其優先權降低到原來的優先權.採用這種方法可以有效地解決上面所述的優先權反轉的問題.當高優先順序進程p1想要進入臨界區時，由於低優先順序進程p3佔有這個臨界資源的信號量，導致p1被阻塞.這時候，系統把p3的優先權升到p1的優先權，此時優先權處於p1和p3之間的進程p2，即使處於就緒狀態也不可以被調度執行，因為此時p3的優先權已經高於p2，所以p3此時被調度執行.當p3釋放p1需要的信號量時，系統立即把p3的優先權降到原來的高度，來保證p1和p2正常有序執行，有許多實時系統是採用這種方法來防止優先順序反轉的，如VXWORKS. 對於那些具有穩定，已知輸入的簡單系統，可以使用時間驅動的調度演算法，它能夠為數據處理提供很好的預測性.這種調度演算法本質上是一種設計時就確定下來的離線的靜態調度方法.在系統的設計階段，在明確系統中所有的處理情況下，對於各個進程的開始，切換，以及結束時間等就事先做出明確的安排和設計.這種調度演算法適合於那些很小的嵌入式系統，自控系統，感測器等應用環境.這種調度演算法的優點是進程的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有進程需要被執行而 CPU 卻保持空閑的情況.
對於不同要求下的實時系統可以採用不同的進程調度策略來進行設計，也可以將這些方法進行綜合之後得到更適合的調度策略.

❸ 作業調度演算法的優先順序法

優先順序演算法（Priority Scheling）是多級隊列演算法的改進，平衡各進程對響應時間的要求。適用於作業調度和進程調度，可分成搶先式和非搶先式。 作業調度中的靜態優先順序大多按以下原則確定：
由用戶自己根據作業的緊急程度輸入一個適當的優先順序。
由系統或操作員根據作業類型指定優先順序。
系統根據作業要求資源情況確定優先順序。
進程的靜態優先順序的確定原則：
按進程的類型給予不同的優先順序。
將作業的情態優先順序作為它所屬進程的優先順序。 進程的動態優先順序一般根據以下原則確定：
根據進程佔用有CPU時間的長短來決定。
根據就緒進程等待CPU的時間長短來決定。

❹ linux環境下的進程調度演算法有哪些

第一部分： 實時調度演算法介紹

對於什麼是實時系統，POSIX 1003.b作了這樣的定義：指系統能夠在限定的響應時間內提供所需水平的服務。而一個由Donald Gillies提出的更加為大家接受的定義是：一個實時系統是指計算的正確性不僅取決於程序的邏輯正確性，也取決於結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯。

實時系統根據其對於實時性要求的不同，可以分為軟實時和硬實時兩種類型。硬實時系統指系統要有確保的最壞情況下的服務時間，即對於事件的響應時間的截止期限是無論如何都必須得到滿足。比如航天中的宇宙飛船的控制等就是現實中這樣的系統。其他的所有有實時特性的系統都可以稱之為軟實時系統。如果明確地來說，軟實時系統就是那些從統計的角度來說，一個任務（在下面的論述中，我們將對任務和進程不作區分）能夠得到有確保的處理時間，到達系統的事件也能夠在截止期限到來之前得到處理，但違反截止期限並不會帶來致命的錯誤，像實時多媒體系統就是一種軟實時系統。

一個計算機系統為了提供對於實時性的支持，它的操作系統必須對於CPU和其他資源進行有效的調度和管理。在多任務實時系統中，資源的調度和管理更加復雜。本文下面將先從分類的角度對各種實時任務調度演算法進行討論，然後研究普通的 Linux操作系統的進程調度以及各種實時Linux系統為了支持實時特性對普通Linux系統所做的改進。最後分析了將Linux操作系統應用於實時領域中時所出現的一些問題，並總結了各種實時Linux是如何解決這些問題的。

1. 實時CPU調度演算法分類

各種實時操作系統的實時調度演算法可以分為如下三種類別[Wang99][Gopalan01]：基於優先順序的調度演算法（Priority-driven scheling-PD）、基於CPU使用比例的共享式的調度演算法（Share-driven scheling-SD）、以及基於時間的進程調度演算法（Time-driven scheling-TD），下面對這三種調度演算法逐一進行介紹。

1.1. 基於優先順序的調度演算法

基於優先順序的調度演算法給每個進程分配一個優先順序，在每次進程調度時，調度器總是調度那個具有最高優先順序的任務來執行。根據不同的優先順序分配方法，基於優先順序的調度演算法可以分為如下兩種類型[Krishna01][Wang99]：

靜態優先順序調度演算法：

這種調度演算法給那些系統中得到運行的所有進程都靜態地分配一個優先順序。靜態優先順序的分配可以根據應用的屬性來進行，比如任務的周期，用戶優先順序，或者其它的預先確定的策略。RM（Rate-Monotonic）調度演算法是一種典型的靜態優先順序調度演算法，它根據任務的執行周期的長短來決定調度優先順序，那些具有小的執行周期的任務具有較高的優先順序。

動態優先順序調度演算法：

這種調度演算法根據任務的資源需求來動態地分配任務的優先順序，其目的就是在資源分配和調度時有更大的靈活性。非實時系統中就有很多這種調度演算法，比如短作業優先的調度演算法。在實時調度演算法中， EDF演算法是使用最多的一種動態優先順序調度演算法，該演算法給就緒隊列中的各個任務根據它們的截止期限（Deadline）來分配優先順序，具有最近的截止期限的任務具有最高的優先順序。

1.2. 基於比例共享調度演算法

雖然基於優先順序的調度演算法簡單而有效，但這種調度演算法提供的是一種硬實時的調度，在很多情況下並不適合使用這種調度演算法：比如象實時多媒體會議系統這樣的軟實時應用。對於這種軟實時應用，使用一種比例共享式的資源調度演算法（SD演算法）更為適合。

比例共享調度演算法指基於CPU使用比例的共享式的調度演算法，其基本思想就是按照一定的權重（比例）對一組需要調度的任務進行調度，讓它們的執行時間與它們的權重完全成正比。

我們可以通過兩種方法來實現比例共享調度演算法[Nieh01]：第一種方法是調節各個就緒進程出現在調度隊列隊首的頻率，並調度隊首的進程執行；第二種做法就是逐次調度就緒隊列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片。

比例共享調度演算法可以分為以下幾個類別：輪轉法、公平共享、公平隊列、彩票調度法（Lottery）等。

比例共享調度演算法的一個問題就是它沒有定義任何優先順序的概念；所有的任務都根據它們申請的比例共享CPU資源，當系統處於過載狀態時，所有的任務的執行都會按比例地變慢。所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般採用一種動態調節進程權重的方法。

1.3. 基於時間的進程調度演算法

對於那些具有穩定、已知輸入的簡單系統，可以使用時間驅動（Time-driven:TD）的調度演算法，它能夠為數據處理提供很好的預測性。這種調度演算法本質上是一種設計時就確定下來的離線的靜態調度方法。在系統的設計階段，在明確系統中所有的處理情況下，對於各個任務的開始、切換、以及結束時間等就事先做出明確的安排和設計。這種調度演算法適合於那些很小的嵌入式系統、自控系統、感測器等應用環境。

這種調度演算法的優點是任務的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有任務需要被執行而CPU卻保持空閑的情況。

2. 通用Linux系統中的CPU調度

通用Linux系統支持實時和非實時兩種進程，實時進程相對於普通進程具有絕對的優先順序。對應地，實時進程採用SCHED_FIFO或者SCHED_RR調度策略，普通的進程採用SCHED_OTHER調度策略。

在調度演算法的實現上，Linux中的每個任務有四個與調度相關的參數，它們是rt_priority、policy、priority（nice）、counter。調度程序根據這四個參數進行進程調度。

在SCHED_OTHER 調度策略中，調度器總是選擇那個priority+counter值最大的進程來調度執行。從邏輯上分析，SCHED_OTHER調度策略存在著調度周期（epoch），在每一個調度周期中，一個進程的priority和counter值的大小影響了當前時刻應該調度哪一個進程來執行，其中 priority是一個固定不變的值，在進程創建時就已經確定，它代表了該進程的優先順序，也代表這該進程在每一個調度周期中能夠得到的時間片的多少； counter是一個動態變化的值，它反映了一個進程在當前的調度周期中還剩下的時間片。在每一個調度周期的開始，priority的值被賦給 counter，然後每次該進程被調度執行時，counter值都減少。當counter值為零時，該進程用完自己在本調度周期中的時間片，不再參與本調度周期的進程調度。當所有進程的時間片都用完時，一個調度周期結束，然後周而復始。另外可以看出Linux系統中的調度周期不是靜態的，它是一個動態變化的量，比如處於可運行狀態的進程的多少和它們priority值都可以影響一個epoch的長短。值得注意的一點是，在2.4以上的內核中， priority被nice所取代，但二者作用類似。

可見SCHED_OTHER調度策略本質上是一種比例共享的調度策略，它的這種設計方法能夠保證進程調度時的公平性--一個低優先順序的進程在每一個epoch中也會得到自己應得的那些CPU執行時間，另外它也提供了不同進程的優先順序區分，具有高priority值的進程能夠獲得更多的執行時間。

對於實時進程來說，它們使用的是基於實時優先順序rt_priority的優先順序調度策略，但根據不同的調度策略，同一實時優先順序的進程之間的調度方法有所不同：

SCHED_FIFO：不同的進程根據靜態優先順序進行排隊，然後在同一優先順序的隊列中，誰先准備好運行就先調度誰，並且正在運行的進程不會被終止直到以下情況發生：1.被有更高優先順序的進程所強佔CPU；2.自己因為資源請求而阻塞；3.自己主動放棄CPU（調用sched_yield）；

SCHED_RR：這種調度策略跟上面的SCHED_FIFO一模一樣，除了它給每個進程分配一個時間片，時間片到了正在執行的進程就放棄執行；時間片的長度可以通過sched_rr_get_interval調用得到；

由於Linux系統本身是一個面向桌面的系統，所以將它應用於實時應用中時存在如下的一些問題：

Linux系統中的調度單位為10ms，所以它不能夠提供精確的定時；

當一個進程調用系統調用進入內核態運行時，它是不可被搶占的；

Linux內核實現中使用了大量的封中斷操作會造成中斷的丟失；

由於使用虛擬內存技術，當發生頁出錯時，需要從硬碟中讀取交換數據，但硬碟讀寫由於存儲位置的隨機性會導致隨機的讀寫時間，這在某些情況下會影響一些實時任務的截止期限；

雖然Linux進程調度也支持實時優先順序，但缺乏有效的實時任務的調度機制和調度演算法；它的網路子系統的協議處理和其它設備的中斷處理都沒有與它對應的進程的調度關聯起來，並且它們自身也沒有明確的調度機制；

3. 各種實時Linux系統

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大學（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，為了在Linux系統中提供對於硬實時的支持，它實現了一個微內核的小的實時操作系統（我們也稱之為RT-Linux的實時子系統），而將普通Linux系統作為一個該操作系統中的一個低優先順序的任務來運行。另外普通Linux系統中的任務可以通過FIFO和實時任務進行通信。RT-Linux的框架如圖 1所示：

圖 1 RT-Linux結構

RT -Linux的關鍵技術是通過軟體來模擬硬體的中斷控制器。當Linux系統要封鎖CPU的中斷時時，RT-Linux中的實時子系統會截取到這個請求，把它記錄下來，而實際上並不真正封鎖硬體中斷，這樣就避免了由於封中斷所造成的系統在一段時間沒有響應的情況，從而提高了實時性。當有硬體中斷到來時， RT-Linux截取該中斷，並判斷是否有實時子系統中的中斷常式來處理還是傳遞給普通的Linux內核進行處理。另外，普通Linux系統中的最小定時精度由系統中的實時時鍾的頻率決定，一般Linux系統將該時鍾設置為每秒來100個時鍾中斷，所以Linux系統中一般的定時精度為 10ms，即時鍾周期是10ms，而RT-Linux通過將系統的實時時鍾設置為單次觸發狀態，可以提供十幾個微秒級的調度粒度。

RT-Linux實時子系統中的任務調度可以採用RM、EDF等優先順序驅動的演算法，也可以採用其他調度演算法。

RT -Linux對於那些在重負荷下工作的專有系統來說，確實是一個不錯的選擇，但他僅僅提供了對於CPU資源的調度；並且實時系統和普通Linux系統關系不是十分密切，這樣的話，開發人員不能充分利用Linux系統中已經實現的功能，如協議棧等。所以RT-Linux適合與工業控制等實時任務功能簡單，並且有硬實時要求的環境中，但如果要應用與多媒體處理中還需要做大量的工作。

義大利的RTAI( Real-Time Application Interface )源於RT-Linux，它在設計思想上和RT-Linux完全相同。它當初設計目的是為了解決RT-Linux難於在不同Linux版本之間難於移植的問題，為此，RTAI在 Linux 上定義了一個實時硬體抽象層，實時任務通過這個抽象層提供的介面和Linux系統進行交互，這樣在給Linux內核中增加實時支持時可以盡可能少地修改 Linux的內核源代碼。

3.2. Kurt-Linux

Kurt -Linux由Kansas大學開發，它可以提供微秒級的實時精度[KurtWeb] [Srinivasan]。不同於RT-Linux單獨實現一個實時內核的做法，Kurt -Linux是在通用Linux系統的基礎上實現的，它也是第一個可以使用普通Linux系統調用的基於Linux的實時系統。

Kurt-Linux將系統分為三種狀態：正常態、實時態和混合態，在正常態時它採用普通的Linux的調度策略，在實時態只運行實時任務，在混合態實時和非實時任務都可以執行；實時態可以用於對於實時性要求比較嚴格的情況。

為了提高Linux系統的實時特性，必須提高系統所支持的時鍾精度。但如果僅僅簡單地提高時鍾頻率，會引起調度負載的增加，從而嚴重降低系統的性能。為了解決這個矛盾， Kurt-Linux採用UTIME所使用的提高Linux系統中的時鍾精度的方法[UTIMEWeb]：它將時鍾晶元設置為單次觸發狀態（One shot mode），即每次給時鍾晶元設置一個超時時間，然後到該超時事件發生時在時鍾中斷處理程序中再次根據需要給時鍾晶元設置一個超時時間。它的基本思想是一個精確的定時意味著我們需要時鍾中斷在我們需要的一個比較精確的時間發生，但並非一定需要系統時鍾頻率達到此精度。它利用CPU的時鍾計數器TSC (Time Stamp Counter)來提供精度可達CPU主頻的時間精度。

對於實時任務的調度，Kurt-Linux採用基於時間（TD）的靜態的實時CPU調度演算法。實時任務在設計階段就需要明確地說明它們實時事件要發生的時間。這種調度演算法對於那些循環執行的任務能夠取得較好的調度效果。

Kurt -Linux相對於RT-Linux的一個優點就是可以使用Linux系統自身的系統調用，它本來被設計用於提供對硬實時的支持，但由於它在實現上只是簡單的將Linux調度器用一個簡單的時間驅動的調度器所取代，所以它的實時進程的調度很容易受到其它非實時任務的影響，從而在有的情況下會發生實時任務的截止期限不能滿足的情況，所以也被稱作嚴格實時系統（Firm Real-time）。目前基於Kurt-Linux的應用有：ARTS（ATM Reference Traffic System）、多媒體播放軟體等。另外Kurt-Linux所採用的這種方法需要頻繁地對時鍾晶元進行編程設置。

3.3. RED-Linux

RED -Linux是加州大學Irvine分校開發的實時Linux系統[REDWeb][ Wang99]，它將對實時調度的支持和Linux很好地實現在同一個操作系統內核中。它同時支持三種類型的調度演算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

為了提高系統的調度粒度，RED-Linux從RT-Linux那兒借鑒了軟體模擬中斷管理器的機制，並且提高了時鍾中斷頻率。當有硬體中斷到來時，RED-Linux的中斷模擬程序僅僅是簡單地將到來的中斷放到一個隊列中進行排隊，並不執行真正的中斷處理程序。

另外為了解決Linux進程在內核態不能被搶占的問題， RED-Linux在Linux內核的很多函數中插入了搶占點原語，使得進程在內核態時，也可以在一定程度上被搶占。通過這種方法提高了內核的實時特性。

RED-Linux的設計目標就是提供一個可以支持各種調度演算法的通用的調度框架，該系統給每個任務增加了如下幾項屬性，並將它們作為進程調度的依據：

Priority：作業的優先順序；

Start-Time：作業的開始時間；

Finish-Time：作業的結束時間；

Budget：作業在運行期間所要使用的資源的多少；

通過調整這些屬性的取值及調度程序按照什麼樣的優先順序來使用這些屬性值，幾乎可以實現所有的調度演算法。這樣的話，可以將三種不同的調度演算法無縫、統一地結合到了一起。

❺ 什麼是靜態調度演算法

靜態調度演算法是調度之前制定好調度策略，調度過程慶源缺中按照預先制定的策略進行調度，調度過程中不考慮當前各伺服器、網關或鏈路的實際負載情況及可負載的能力。由於調度不隨著當前的負載情況改變而改變，因此稱為靜態調度演算法。演算法特點是譽辯實現簡單、調度快捷。靜態調度演算法主要代表有：輪轉調度演算法、加權輪轉調度演算法、隨機調度演算法、加權隨機調度演算法、基於源地址哈希調度演算法、基於目的地址哈希調度演算法、裂舉基於源地址埠哈希調度演算法。

❻ 什麼rm調度演算法

一個任務的響應時間(response time)是指一個任務請求, 這個任務實際完成的時間跨度. 在靜態調度中, 任務的臨界時刻(critical instant)這個概念被首先提出來. 它被定義為一個特定的時刻, 如果在這個時刻有這個任務的請求, 那麼這個任務就會需要最大的響應時間. 由此得出 定理1: 一個任務的臨界時間就是比這個任務優先順序高的所有任務同時發出請求的時刻. 定理1的價值在於它找到了一個證明一個調度演算法能否調度任一任務集充分必要條件, 那就是所有任務同時請求執行的時的情況下每個任務仍能滿足各自的期限, 那麼這個任務集就可以被這個調度演算法調度. 有了這個推論, 我們就可以證明RM調度的最優性了. 定理2: 如果一個任務集能夠被靜態調度, 那麼RMS演算法就能夠調度這個任務集. 從這個意義上說, RMS是最優的靜態調度演算法. 這個定理的證明方法就是有名的交換法. 證明思路如下: 假設一個任務集S採用其他靜態優先順序演算法可以調度,那麼總有這樣兩個優先順序相鄰的任務i和j, 有Ti>Tj,而Pi≤Pj.把Ti和Tj的優先順序Pi和Pj互換,明顯可以看出這時S仍然可以調度, 因為在所有任務同時請求的情況下, 交換這兩個任務不會影響其它任務的完成時間, 同時這兩個任務都可以在各自期限內完成. 按照這樣的方法,其他任何靜態優先順序調度最終都可以轉換成RM調度. RMS已被證明是靜態最優調度演算法, 開銷小, 靈活性好, 是實時調度的基礎性理論。即使系統瞬時過載, 也完全可預測哪些任務丟失時限。缺點是處理機利用率較低, 最壞的情況下，當n→∞時, 不超過ln2 (≈ 70%)。另外, RMS是充分但非必要條件。而在一般情況下，對於隨機的任務集大約只有88%. 70%或者88%的處理器利用率對於許多實時應用來說是一個嚴重的限制，動態調度演算法如最早截止期最先（earliest deadline first，EDF）或者最少空閑時間最先（least laxity first，LLF）已經被證明是最優的，並且能夠實現100% 的處理器利用率. 具有資源同步約束的RMS調度 當實時任務間共享資源時, 可能出現低優先順序任務不可預測地阻塞高優先順序任務執行的情況, 叫優先順序倒置。這時RMS 演算法不能保證任務集的調度, 必須使用有關協議控制優先順序的倒置時間。常用的協議有優先順序頂級協議和堆資源協議, 使用這些協議可使優先順序的倒置時間最多為一個資源臨界段的執行時間, 並且不會發生死鎖。 基於RMS 的非周期任務的調度 實時系統中的非周期任務可採用延遲伺服器演算法或隨機伺服器演算法進行調度。它們的最大特點是可在周期任務的實時調度環境下處理隨機請求。兩者的基本思想是將非周期任務轉化成周期任務, 再利用RMS演算法進行調度。前者用一個或幾個專用的周期任務執行所有非周期任務, 這種周期任務叫非周期任務伺服器。根據周期大小,伺服器有固定優先順序, 伺服器的執行時間被稱為預算, 它在每個伺服器周期Ts 的起點補充。只要伺服器有充足的預算, 就可在其周期內為非周期任務服務。該演算法實現簡單, 但可調度性分析較難, 有時會出現抖動, 可能發生一個非周期任務在相鄰兩個伺服器周期中連續執行2倍預算的現象, 與RMS理論不符, 需要適當修改RMS演算法。隨機伺服器演算法與延遲伺服器演算法相似, 但預算不是在每個周期起點補充, 而是在預算消耗Ts時間之後再補充。該演算法與RMS分析演算法一致, 但實現復雜。 EDF最早截止時間優先演算法（EDF）也稱為截止時間驅動調度演算法（DDS），是一種動態調度演算法。EDF指在調度時，任務的優先順序更具任務的截止時間動態分配。截止時間越短，優先順序越高。EDF有如下定理： 定理2：如果一個任務集按EDF演算法調度，當且僅當U<=1。 EDF的特點(1) 任務模型: 與RMS 調度相同。 (2) 優先順序分配方法: 動態分配, 距要求時限所剩時間越短優先順序越高。 理論上，EDF和LLF演算法都是單處理器下的最優調度演算法。但是由於EDF和LLF在每個調度時刻都要計算任務的deadline或者空閑時間，並根據計算結果改變任務優先順序，因此開銷大、不易實現，其應用受到一定限制。多處理器實時調度