轉自21ic網
優先級調度作為實時嵌入式系統設計方法，近年來日益受到廣泛關注。
本文假定硬實時系統(hard-real-time system)具有如下特性：包含的進程具有嚴格時序約束且數目相對較多；這些進程具有不同的時序特性和相關性；處理器利用率並不很低，即沒有太多的CPU空閒容量。
進程與調度
為了對復雜硬實時系統的性能進行預估，必須預先了解各進程的主要特性，否則不可能保證得到滿足所有時序約束的優先級條件。
1.周期性進程
周期性進程由反復執行的運算組成，每個固定的時間周期執行一次運算。周期性進程的一個典型應用就是讀取傳感器數據並更新內部變量和輸出的當前狀態。
周期性進程p的四要素是rp, cp, dp, prdp：prdp表示周期；cp表示進程p在最壞情形下的運算時間；dp表示時限，即在每個周期中，從周期起始到進程p執行完畢之間的時間間隔；rp表示釋放時間，即在每個周期中，從周期起始到進程p最早開始執行之間的時間間隔。此外，假定rp, cp, dp, prdp以及其它任何表示時間的參數均為整數。
周期性進程p可包含無數個周期性進程執行p0, p1, p2,...，每個周期執行一次進程。第i個進程執行對應於第i個周期的進程pi，而pi的釋放時間可表示為rpi = rp + prdp × (i-1)；pi的時限可表示為dpi= dp + prdp × (i-1)。
2.異步進程
異步進程由響應內部或外部事件的運算組成，異步進程的典型應用是響應操作人員的請求。盡管無法預知執行異步進程a的精確請求時間，但通常可以預先得到兩個連續請求間的最短時間mina。異步進程a可由三要素ca, da, mina描述：ca 表示進程a在最壞情形下的運算時間；da 表示時限，即從向進程a發出請求到進程a完成執行之間的時間間隔。異步進程a可具有無數個異步進程執行a0, a1, a2, ...,，每個進程執行對應於一個異步請求。對於對應於第i個請求的第i個異步進程執行ai，如果ai的請求時間為rai，則ai的時限為dai = rai + da。
3.調度
下面引入進程執行單元和處理器時間單元的概念。如果周期性進程p或異步進程a的運算時間為cp或ca，那麼假定進程執行pi或ai由cp或ca進程執行單元組成，而且每個處理器都與起始於0的進程時間軸關聯並分成連續的處理器時間單元。
調度能在一個或多個處理器時間軸上，將無數個進程執行單元映射到無數個處理器時間單元上。在0與進程執行中由第一個執行單元所映射的處理器時間單元之間，所存在的處理器時間單元數量被稱為進程執行起始時間；0到進程執行中由最後一個執行單元所映射的處理器時間單元之間，所存在的處理器時間單元數稱為進程執行完成時間。如果調度中，每個進程執行的起始時間大於或等於進程執行的釋放時間或請求時間，並且進程的完成時間小於或等於進程的執行時限，那麼該調度是有效的。
4.進程分段
每個進程p均可由有限的分段序列p[0]、p[1]、...p[n[p]]組成，其中p[0]表示進程p的第一個分段，p[n[p]]則表示進程p的最後一個分段。給定進程p的釋放時間rp、時限dp和進程p中每個分段p[i]的運算時間，可以簡單地計算出每個分段的釋放時間和時限。
5.優先和排斥關系
進程分段有序對之間可以存在各類關系，如優先關系(precedence relation)和排斥關系(exclusion relation)。
如果只有當進程分段i執行完成，進程分段j才能開始執行，則稱進程分段i優先於進程分段j。當某些進程分段需要由其它進程分段產生的信息時，這些進程分段之間就可能存在優先關系。
如果從進程分段i開始執行運算到結束運算之間，不能執行任何進程分段j的運算，則稱進程分段i排斥進程分段j。當某些進程分段必須防止其它進程分段同時訪問共享資源(如數據和I/O設備)時，這些進程分段之間就可能存在排斥關系。
優先級調度和運行前調度概述
下面，本文將簡要介紹優先級調度和運行前調度方法。
1.優先級調度方法
大多數優先級調度方法均遵循兩個基本假定：a)調度在進程運行時執行；b)進程分配有固定的優先級，當兩個進程競爭同一處理器時，具有較高優先級的進程將獲得處理器資源。
速率單調調度(Rate Monotonic Scheduling)是最具代表性的優先級調度方法。該方法假定所有的進程都是周期性的，並且進程的主要特性在運行之前都已確定，即預先了解進程在最壞情形下的執行時間和周期。
設計工程師可根據進程的周期設定固定的優先級：周期越短，優先級越高。任何時候，只要所有進程中具有最高優先級的進程就緒，即可分配到處理器。而且在運行前，還可根據已知的進程特性進行可調度性分析。如果滿足特定的方程，即可在運行中執行實際的調度，並假定運行中可以滿足所有的時限要求。
優先級最高限度協議(Priority Ceiling Protocol)的假定與速率單調調度相同，只是進程可能具有由旗語(semaphores)保護的臨界區，並提供專門的協議來處理這些臨界區。每個旗語均分配一個優先級最高限度值，優先級最高限度與使用該旗語的最高優先級進程具有相等的優先級。具有最高優先級的進程一旦就緒，即可分配到處理器資源。任何進程p進入其臨界區之前，必須首先獲取監控臨界區的旗語S的優先級鎖定。如果進程p的優先級不高於當前除p以外，其它進程鎖定的旗語中具有最高優先級的最高限度，那麼進程p將被阻塞，S上的鎖定將被拒絕。當進程p阻塞了更高優先級的進程，那麼p將繼承被p阻塞的進程的最高優先級。
當p離開臨界區，則進程p將恢復其進入臨界區時的優先級。如果進程p不試圖進入臨界區，並且其優先級(繼承或分配的優先級)高於另一正在執行的進程pi的優先級，則可占先運行。
如果滿足以下條件，則速率單調調度(周期越短，優先級越高)可以調度(即滿足所有時限要求)采用優先級最高限度協議的n個周期性進程：其中Ci 表示執行時間，Ti 表示周期，Bi 表示最壞情形下由較低優先級進程引發的pi阻塞時間。
2.運行前調度方法
采用運行前調度，一般進程的調度是離線計算；同時，該方法還要求能夠預先了解系統中進程的主要特性。
采用運行前調度的方法對周期性進程進行調度是可能的。該方法由調度的離線計算(computing off-line)和調度運行兩部分組成，即離線計算周期值等於給定進程集周期的最小公倍數的全部周期進程的調度，並根據先前計算的調度策略執行周期性進程。
在運行前調度中，對給定的周期可離線地計算多個可選調度，而每個調度都對應於不同的操作“模式”。一個小的運行時間調度器可在對應於外部或內部事件的可選調度中進行選擇，而小的運行時間調度器也可用來為數目較少，且時限極短的異步進程分配資源。
如果預先了解兩個連續請求之間的最短時間，那麼就可將異步進程轉化為等價的周期性進程。因此，也可以采用運行前調度方法調度異步進程。
運行前調度與優先級調度的比較
下面將簡要說明優先級調度方法的缺點。可以看到無論是速率單調調度還是優先級最高限度協議，優先級調度都無法為某類問題提供可行的解決方案，而采用運行前調度的最優算法則可以解決。這些缺點直接源於固定優先級調度方法中固有的基本假定，而不僅僅是基於該調度方法的某個特定運算或公式的特性。因此，這些缺點並不能通過某些設計巧妙的快速修復(quick fix)技術加以彌補。
1. 優先級調度方法難以處理復雜的應用約束問題
文章給出的可調度性分析假定所有的任務都是獨立的，即任務之間不存在優先關系，並且釋放時間等於周期的起始時間。我們很難延伸優先級調度方法的可調度性分析，來考慮那些通常在實時應用中存在的應用約束，如優先約束、釋放時間不等於周期的起始時間、低抖動要求等。主要由於以下兩個原因：
(a)附加的應用約束很可能與分配給進程的優先級相沖突，一般不可能將大型復雜系統中不同應用約束所需的諸多不同進程執行序列映射到嚴格的優先級層次。
對具有進程優先級的附加應用約束進行調整將產生一些細微的誤差。例如，有作者建議采用進程優先級增強優先約束，但優先約束所需的優先級設定可能同其它標准(如進程的周期長度)規定的優先級相沖突。即便不存在任何沖突，僅采用優先級也不足以控制進程的執行順序。假定進程A的優先級高於進程B，如果B比A先到達並要求先執行，且B是當時唯一要求執行的進程，那麼盡管A的優先級比B高，B也將先於A執行。
相反，在運行前調度方法中，調度在運行前進行運算，因而能相對容易地考慮到諸多附加約束，如任意釋放時間、時限和優先約束等。此外，還可通過直接規定進程分段對的優先關系和排斥關系，以避免采用復雜的運行同步機制實現進程同步，並防止同時對共享資源的訪問。例如，A的優先級高於B就可通過在運行前調度中，將A排在B之前，以保證A 總是在B之前執行。
(b)附加的應用約束增加了調度問題的運算復雜度，而一旦進程包含臨界區，調度運算本身已經很復雜了。對於那些具有很高運算復雜度的問題，調度器需要相當長的時間才能找到良好的解決方案。對於優先級調度方法，調度在進程運行中執行，因而調度器缺乏必要的時間以找到良好的解決方案。
相反，運行前調度是離線運算，調度算法的時間效率並不是關心的關鍵內容，因此設計工程師可以任意選用最優的調度算法或其它算法，這在大多數情形下可以更好地滿足所有的時序和資源約束。
由於固定優先級調度模式本身存在的約束(如固定優先級)，並且由於調度在運行時執行，因此考慮附加約束往往導致固定優先級調度只適用於一些非常特殊的情形，或者需要作出極為簡化的假設，這些工作或者本身極為復雜，或者將顯著降低系統的可調度性，從而導致難以分析和預測系統的執行時性能。
2.一般而言，優先級調度方法的處理器利用率低於運行前調度方法
2.1.基於優先級的調度策略是一種直觀推斷算法，與最優的運行前調度算法相比，更難以找到可行的調度。
(a)即便所有的進程都完全可占先(在大型復雜的硬實時系統中，這種情形不大可能出現)，基於優先級的進程調度也不是最優的。例1中，速率單調調度算法不能完全滿足兩個可占先進程A和B的時限，但這兩個進程可以通過采用調度完全可占先進程的最優算法，如最早時限優先算法進行成功調度。
例1．進程A：釋放時間rA = 0；運算時間cA = 3；時限dA = 6；周期prdA = 6；優先級A = 0。進程B：釋放時間rB = 0；運算時間cB = 4；時限dB = 8；周期 prdB = 8；優先級B = 1。
速率單調調度算法生成的調度：B 錯過了首個時限。
最優算法(如EDF)生成的調度：滿足所有的時限。
| A | B | A |B | A |B | A | B |
0 3 7 10 12 15 18 21 24
| A | B | A |B | A |B | A | B |
0 3 7 10 12 15 18 21 24
(b)如果某些進程不可占先，基於優先級的調度進程將更難滿足時限。例如，在下面的情形下，為滿足所有給定的時序約束，即便已存在可執行進程，也必須使處理器處於空閒狀態。如下例所示：
例2．進程A：釋放時間rA = 0；運算時間 cA = 10；時限dA = 12。進程B：釋放時間rB = 1；運算時間cB = 1；時限dB = 2。不允許B占先A。
優先級調度算法可生成如下調度，其中B錯過了時限：
| A |B|
0 10 11
| A |B|
0 10 11
相反，采用最優算法就能找到滿足所有進程時限的可行調度：
|B| A |
1 2 12
|B| A |
1 2 12
時序約束要求處理器在時間0和1之間必須處於空閒狀態，即使進程A的釋放時間為0。因為一旦A開始執行，必將導致B錯過時限。
在大多數實際應用中，會出現因其它進程已進入臨界區而不能占先進程分段的情況。因此，該示例實際上給出了一個很普遍的情形，但基於優先級的策略並不能正確地處理此類情形。
優先級調度方法較難滿足時序約束，因為基於優先級的方案只能為給定的進程集產生非常有限的可能調度子集，這嚴重地限制了優先級驅動策略在運行時滿足時序和資源共享約束的能力。
通常，調度算法生成的調度集越小，找到可行調度的機會就越小，且算法所能實現的處理器利用率水平也就越低。例如，對於例2中給出的進程集，若堅持采用優先級驅動策略，就需要將處理器容量提高為原來的(cA+ cB)/(1+cB) = 11/2倍，並且所實現的處理器利用率遠低於在例2中生成有效調度的最優調度方案。通過采用離線計算調度的最優算法，可實現比采用基於優先級方案更高的資源利用率。因此，采用基於優先級的方案將增加系統成本，從而失去競爭優勢。
實際上，從上述示例中可以注意到：任意優先級調度算法與最優算法的處理器利用率之比可任意降低，如在例2中，通過增加A的運算時間，並將A的時限設定為cA+2，同時保持其它參數不變，即可任意降低處理器利用率。
2.2 在運行中進行進程調度時，必須避免死鎖。在運行時避免死鎖通常要求運行時的同步機制保持恆定，並當運行同步機制阻塞進程時，進程仍能繼續執行而不產生死鎖。如果再結合優先級的使用，處理器利用率將進一步降低。例3顯示了優先級最高限度協議阻礙進程執行並導致進程錯過時限的實例，盡管進程仍能繼續執行並滿足時限而不產生死鎖。
例3. 進程A：在t1時刻就緒，整個進程是受旗語s0監控的臨界區；運算時間cA = t2 - t1；優先級A = 0。進程B：在t3時刻 就緒，整個進程是受旗語s1監控的臨界區；運算時間cB = t5 - t4；時限為t3 + cB；優先級B = 1；進程C：在t2時刻就緒，整個進程是受旗語s0監控的臨界區；運算時間cC = t4 - t2；時限為t5；優先級C = 2。 s0 的優先級最高限度為0； s1 的優先級最高限度為 1。
根據優先級最高限度協議，由於進程A和進程C均使用受同一旗語s0監控的臨界區。因此，當進程C於t2時刻進入臨界區時，它將以優先級0執行，在t3時阻礙進程B，從而導致進程B錯過時限：
|A | C |B |
t1 t2 t3 t4 t5
|A | C |B |
t1 t2 t3 t4 t5
但是進程B可以通過占先進程C來滿足時限，並且不會導致死鎖：
|A |C | B | C |
t1 t2 t3 t5
|A |C | B | C |
t1 t2 t3 t5
上述實例中，為避免在運行時調度進程引發死鎖，需要采用極端保守的策略：即要求進程以相同的旗語監控臨界區的任意進程的最高優先級執行臨界區。
相反，如果采用運行前調度方法，調度將能離線建立，因此調度算法可考慮能構造無死鎖調度的所有可行方法。
這裡應該注意到，任何優先級調度算法與最優算法的處理器利用率之比可以任意降低，如例3中可通過增大cC將處理器利用率降至任意低。
2.3.采用優先級調度方法時，由於調度在運行時建立，因而需要耗費大量的系統資源，即在實時應用之外所消耗的時間大大超過了采用運行前調度方法所需的時間。
(a)優先級調度器需要占用運行時資源進行調度運算，即計算何時執行何進程。而在運行前調度方法中，通常預先確定調度。
(b)由於優先級調度器在運行前並不知道調度，因此需要假定最壞情形，並在每次被另一進程占先時保存/恢復完整的當前信息。在運行前調度方法中，調度在運行前確定，因而可以預先確定需要保存或恢復的最少信息，從而顯著地降低了現場切換所需的時間。
(c)為了實現不同的進程管理功能，如掛起和激活進程、操作進程隊列等，優先級調度器還需占用大量運行時的資源。相反，在運行前調度方法中，由於預先規定了調度，因而可實現自動代碼優化，即通過采用非常簡單的機制(如程序調用)或在無需保存和恢復當前信息的情況下簡單地連接代碼，將處理器執行從一個進程切換至另一進程，從而極大地降低系統的開銷。
如果進程周期相對比較重要，那麼進程周期的最小公倍數(LCM)和運行前調度的長度將會變得相當冗長。然而在實際中，設計工程師往往可以靈活地調整周期長度以得到滿意的進程周期LCM長度。盡管這可能導致處理器利用率降低，但與采用優先級調度導致的處理器利用率降低相比，完全可以忽略不計。
在優先級調度方法中，若存在許多不同的進程周期，則通常需要設定許多優先等級，這無疑極大地增加了執行時調度開銷。如果通過為不同周期的進程子集分配相同的優先級以減少優先級的等級數目，那麼將延長進程的響應時間，並進一步降低可調度性及處理器利用率。
3.與運行前調度方法相比，優先級調度方法的系統運行特性更難進行分析和預測
為實現進程同步並防止多個進程同時訪問共享資源，優先級調度方法要求采用復雜的運行機制，然而精確分析和預測調度器的執行特性將非常困難。例如，在一項利用優先級隊列實現固定優先級調度的研究中，由定時器中斷定期釋放的調度器將使任務在隊列之間進行切換。研究表明，由於時鐘中斷處理程序的優先級高於任何應用任務，因此當較低優先級的任務從一個隊列切換至另一隊列時，即使是高優先級的任務也可能經歷較長的延遲。盡管預先假定系統只含有20項任務且任務不含臨界區，而且優先級也不會發生改變，但在這樣的情形下精確預測調度器的開銷仍然是一項異常復雜的工作，而調度器開銷的預測也相當重要。
相反，在運行前調度方法中，調度在運行前進行計算。因此，可以通過直接定義進程分段對的優先關系和排斥關系以避免使用復雜的運行同步機制，從而實現進程同步並防止多個進程同時訪問共享資源。如上所述，可以通過非常簡單的機制(如程序調用)或在無需保存或恢復當前信息的情形下只通過連接代碼，使處理器執行從一個進程切換至另一進程，這樣不但大大降低了系統的運行時開銷，還能更容易地分析和預測系統執行時的特性。與采用運行時同步機制所需的復雜可調度性分析相比，離線運算調度可以直接檢驗所有滿足時限要求的進程。
據報道，在1997年7月實施的“火星登陸”任務中，飛行器經歷了多次系統重啟，並導致數據丟失。據稱，當采用優先級調度的VxWorks 實時系統內核中的固有優先級機制關閉時，“優先級倒置”就將引發上述問題。報道指出，如果在火星登陸任務中采用運行前調度器，就能避免這些問題。
4.與運行前調度方法相比，優先級調度方法針對變化的應用需求進行系統設計和修改的靈活性較小。
與運行前調度方法相比，優先級調度方法靈活度較小，因為進程分配的嚴格優先級限制了進程的執行順序。而采用運行前調度方法則不存在上述約束，因此設計工程師在軟件開發的任何階段都可以實現從任意運行前調度到任何其它運行前調度的切換。
(a)人們通常認為優先級調度方法比其它方法具有更優越的穩定性，因為對於重要的進程可以分配高優先級以在瞬間系統過載情況下滿足時限要求。速率單調調度方法為周期較短的進程分配較高的優先級，因為實踐表明，如果周期較長的進程分配更高優先級，那麼將嚴重降低整個系統的可調度性。然而，重要的進程並不一定具有較短的周期，因此一些設計工程師建議將重要的進程分割成多個具有較短周期的進程，但這不僅增加了運行時的開銷，還將引發新的人為約束，從而增加了整個系統的復雜度並導致可調度性下降。實時應用中，在不同的情況下可能需要采用不同的進程執行順序，並且有時不同的進程集將成為必要進程。這些問題不能簡單地通過對進程分配嚴格的優先級來解決。
運行前調度方法需要保證重要進程至少應與優先級調度方法相當，或更好。當采用運行前調度方法時，一旦系統出現過載，將會執行另一替代運行前調度，該調度只包含特定條件下的必要進程集。由於在運行前就能詳細設計運行前調度，因此設計工程師可靈活地考慮許多可能出現的不同過載情況，並根據不同的實際情況采取不同的調度策略。
(b)下面給出了一個有關優先級調度方法“靈活度”的實例，即只基於任務集整體處理器利用率信息的優先級調度方法可以進行可調度性分析。這種方法可提供更大的靈活性，因為由增加額外任務而引發的系統可調度性決策只要求對總的可調度性范圍進行重新計算，並決策由新增功能所引發的新利用率問題是否會產生新的超越范圍問題。
在基於可調度性分析的處理器利用率問題中，往往忽略了這樣一個事實，即這樣的分析可能導致系統設計工程師對系統容量的利用不充分。基於分析的處理器利用率總是顯得不盡如人意，因為這種方法只給出了可調度性的充分條件，而不是必要條件。換言之，如果設計工程師希望得到可靠的可調度性分析，就不能采用固定優先級調度算法，並且需要采取措施進一步降低處理器利用率，以滿足由可調度性分析提供的處理器利用率條件，即使是在初始條件下，利用固定優先級調度算法對處理器進行調度這樣的最簡單情形中。
例4.假定系統由20個進程p1、p2...、p20組成，每個進程的執行時間為1，周期為28。
速率單調調度的可調度性分析並不能保證該進程集可調度，因為處理器的總利用率為20×(1/28) = 0.71，大於可調度性分析所需的處理器利用率上限20×(21/20 - 1)。
例4中，因為可調度性分析不能保證進程集可被調度，因此這些進程將被丟棄，盡管速率單調調度算法實際上完全可以滿足這些進程的時限要求：
|p1 |p2 | ... |p20 | | ... | |
0 1 2 19 20 21 27 28
|p1 |p2 | ... |p20 | | ... | |
0 1 2 19 20 21 27 28
需要指出的是，當所有的進程完全可占先時，基於優先級最高限度協議可調度性分析的處理器利用率將完全等同於速率單調調度。因此，該實例也完全適用於優先級最高限度協議。
與基於可調度性分析的處理器利用率相比，靜態優先級調度最壞情形下的響應時間可調度性分析可提供更為寬松的條件。然而，靜態優先級調度最壞情形下的響應時間可調度性分析與基於可調度性分析的處理器利用率具有相同的基本缺點，即只給出可調度性的充分條件，而沒有給出必要條件。盡管靜態優先級調度的最壞情形下響應時間可調度性分析能夠保證例4中極簡單進程集的可調度性，但將捨棄在更早給出的示例中的那些不可調度進程集，即使采用運行前調度方法可以調度這些進程集。
研究表明，運行前調度方法處理異步進程的能力不如優先級調度方法。在Lock的文章[Lock92]中，為了說明循環執行(這是預執行調度方法中一種極為嚴格的形式)的難度，作者采用了循環執行方法處理上述相同的問題，但並未舉例說明固定優先級執行如何解決相同的調度示例問題，而實際上固定優先級執行將面臨相同，甚至更大的困難。在另一篇文章[AuTB93]中，作者試圖表明優先級調度方法也能解決[XuPa90]給出的示例問題，但示例問題的參數有所不同。如果采用本文給出的原始參數，那麼該文章提出的解決方案就完全無能為力。
下面將給出一個反向成立的實例。該實例表明，采用運行前調度方法時，所有的周期性進程的運行前調度一旦確定，執行時調度器就可利用這些信息，通過更有效地調度異步進程實現更高的可調度性。例如，完全可以通過具有較長時限的異步進程避免具有較短時限的周期性進程出現阻塞。
例5.異步進程A：運算時間cA = 3；時限dA = 15；兩個連續請求間的最短時間minA = 15。進程B：釋放時間rB = 0；運算時間cB = 3；時限dB = 3；周期prdB = 8；B不允許占先A。
優先級調度方案不能保證進程A和B總能滿足時限。下面給出的示例表明：無論采用何種優先級調度策略，進程B都將錯過時限。
假定進程A於時間7到達，A的優先級調度方案使A在時間7立即執行，因此，A將阻塞B的第二個實例(instance)並導致B錯過時限。
| B | | A | B |
0 3 7 10 13
| B | | A | B |
0 3 7 10 13
當采用優先級調度策略時，無論可調度性分析是基於整個處理器利用率還是基於最壞情形下的響應時間，可調度性分析都將A和B視為不可調度進程並捨棄。相反，在運行前調度方法中則至少存在兩種有效方法來調度上述進程。
(a)將異步進程A轉換為新的周期性進程newA：釋放時間rnewA = 0；運算時間cnewA = 3；時限dnewA = 8；周期prdnewA = 8。然後，采用[XuPa90]給出的算法建立下述運行前調度，其中周期性進程newA以類似於輪詢的方式模擬異步進程A，從而保證A 和B都不會錯過時限。
| B | newA | |
0 3 6 8
| B | newA | |
0 3 6 8
(b)另一可行的解決方案是采用[XuLa98]提出的方法，即采用[XuPa90]的算法為所有的周期性進程建立運行前調度。本例中，將為進程B建立如下運行前調度：
| B | |
0 3 8
| B | |
0 3 8
在該方法中，運行時間調度器可利用運行前調度的信息對異步進程進行調度。這種情況下，進程A可通過如下方式進行調度：在任何時間t，一旦進程A能立即執行，必然導致進程B錯過時限，即一旦運行前調度中為進程B保留的時隙的最末時刻減t小於進程A和B的運算時間之和；或者一旦周期性進程的時限小於或等於進程A的時限(本例中指當前正在執行的進程B)，進程A將被延遲，直到進程B執行完畢。通過利用運行前調度的信息，設計工程師應當能夠為包含時間間隔[3, 5]的異步進程A構造“安全起始時間間隔”表，並且在運行時對於預執行調度的每個實例，只要允許A在安全起始時間間隔[3, 5]以內開始執行，就能保證進程A和B均滿足時限。利用運行前調度的信息，還能在運行前計算出異步進程在最壞情形下的響應時間。在本例中，當A於時間6到達時，這時給出的是A在最壞情形下的響應時間，於是進程A將延遲直到進程B執行完畢，即進程A於時間14執行完畢。因此，進程A的最壞情形響應時間為14-6＝8，小於初始的時限dA = 15。如果在運行前調度中，進程B總是在保留的時隙內執行，那麼就能保證進程A和B總能滿足時限。
在上述示例中，異步進程子集的運行時間調度集成了周期性進程的運行前調度策略，如果將類似(b)的方法的潛在執行時間開銷與在運行時調度所有任務的優先級調度機制的開銷相比，將會發現：
(1)如果采用集成方法，異步進程調度器需要處理的進程數非常少，因為在大多數實時系統中，大量的運算由周期性進程執行，而具有硬時限(hard deadline)的異步進程數一般非常少。
此外，采用該方法時，大部分異步進程可以轉換為周期性進程。設計工程師可根據每種方法所需的處理器保留容量確定哪些異步進程應當轉換為新的周期性進程，而哪些進程仍保留為異步進程。
(2)異步進程調度器中用於調度決策的絕大部分參數在運行前都是確定的，因而設計工程師可以預先計算那些用作決策的絕大部分條件，這樣就可將運行時進程調度所需的運算量降至最低。與例5(b)類似，在許多情況下，應當能在運行前為每個異步進程構造“安全起始時間間隔”表，這樣異步進程就可以通過簡單的表查詢進行調度，從而大大降低系統的運行時間開銷。
(3)大多數重要的調度決策在運行前就已做出。實際上，當進行運行前調度運算時，在大多數實時應用中占用大量運算的周期性進程的相對順序在進程執行之前就已確定。
采用運行前調度方法的實時系統設計工程師可以自由選擇任意的最優算法構造包含新進程的新運行前調度，並為系統增添新的功能。此外，系統的在線修正也並不復雜，設計工程師可輕松地在運行前調度中插入代碼，這樣當進程被外部信號激活時，處理器執行就能在執行過程中由先前設計的運行前調度轉向新設計的運行前調度。系統設計工程師也無需采用嚴格的進程優先級，這樣在設計新的運行前調度中就具有更大的靈活性，以滿足不斷變化的需求。
綜上所述，在優先級調度方法中，設計工程師除了可以設置優先級以外，在滿足應用要求方面幾乎沒有任何其它選擇。因此在優先級調度方法中，優先級可以重載。設計專家建議，具有如下特征的進程應分配較高的優先級：
a.較短的周期；
b.較高的重要性；
c.較低的抖動要求；
d.優先限制，等。
因此，利用嚴格的優先級以期同時滿足各種不同的應用約束，對於系統設計工程師而言，這幾乎就是不可能的任務。
本文總結
本文解釋並舉例說明了以下事實：
1. 與運行前調度方法相比，優先級調度方法具有以下缺點：
a. 無法有效地處理復雜的應用約束；
b. 處理器利用率較低；
c. 系統開銷較大；
d. 很難分析和預測系統的執行時特性。
2. 相反，采用運行前調度方法具有以下優勢：
a. 更容易保證所有的時限約束及其它約束得到滿足；
b. 設計工程師可以采用那些考慮了各種應用約束的更優算法，並有利於得到可行的調度方案；
c. 大大降低了調度和現場切換所需的運行時間開銷。
3. 形成這些差異的主要原因是：
a. 當采用優先級調度方法時，進程的執行順序受制於嚴格的優先級約束，因此優先級策略只適用於生成非常有限的可行調度子集；
b. 當采用運行前調度方法時，可以離線計算調度，而優先級調度方法則是在線計算調度。
如果一些異步進程滿足如下條件：(a)具有較長的執行間隔，(b)具有較短的時限和運算時間，或(c)具有比大多數周期性進程更長的時限，則可以綜合兩種調度方法並采用較小的運行時間調度器進行調度。盡管運行前調度方法在很多方面比優先級調度方法更具優勢，但在一些情形中“純粹的”運行前調度並不適用，因為極少被調用的異步進程的時限非常短。在這些情況下，將異步進程轉換為周期性進程可能需要極大的處理器容量。優先級最高限度協議中用於防止“優先級倒置”和死鎖的策略也適用於調度任何不能轉換為周期性進程的進程。運行時間調度應當集成運行前調度，從而充分利用已知的進程特性。已知的這些特性可用來確定哪些異步進程在運行時調度，哪些進程可以系統地為異步進程保留處理器容量，從而使這些進程在必要時中斷其它進程以滿足時限要求。
參考文獻
[AuTB93] N. Audsley, K. Tindell and A. Burns, ``The end of the line for static cyclic scheduling,'' Proc. Fifth Euromicro Workshop on Real-Time Systems, 36-41, 1993.
[Lock92]C. D. Locke, ``Software architecture for hard real-time applications: cyclic executives vs. fixed priority executives,'' Journal of Real-Time Systems, 4, 37--53, 1992.
[XuLa98] J. Xu and Kam-yiu Lam, ``Integrating run-time scheduling and pre-run-time scheduling of real-time processes.'' Proc. 23rd IFAC/IFIP Workshop on Real-Time Programming, Shantou, China, June 1998.
[XuPa90] J. Xu and D. L. Parnas, ``Scheduling processes with release times, deadlines, precedence, and exclusion relations,'' IEEE Trans. on Software Engineering, vol. 16, 360-369, Mar. 1990. Reprinted in "Advances in Real-Time Systems," edited by J. A. Stankovic, and K. Ramamrithan, IEEE Computer Society Press, 140-149, 1993. Also reprinted in Software Fundamentals: Collected Papers by David L. Parnas, edited by Daniel M. Hoffman, and David M. Weiss, Addison-Wesley, 439-465, 2001.
作者：Jia Xu
計算機科學系
York大學
EMAIL: [email protected]