引言：

計算機網絡經常是異構的體系。其主要原因是網絡上設施隨著時間不斷地迅速進步，不同時期的最好技術可能在同一網絡中共存。另一個原因是網絡的大小不是固定不變的，隨著時間的流逝網絡也在不斷地擴展，而原有的設備不可能進行同步更新，這就造成了異構性。不論實際從事分布式系統開發人員喜歡與否，計算機網絡的異構性是不可避免的。開發用于分布式系統的應用軟件已是十分困難，而開發一個異構的分布式系統的應用軟件有時幾乎是不可能的事。有鑒于此，計算機界為解決這些問題而提出了中間件概念，在學術界和企業中得到廣泛支持。但是隨后的一些產品如COABA，EJB等并沒有實現系統對實時性的需求。而隨后的實時CORBA規范的出現，昭示著中間件向實時性方向的發展。隨著今年來SOA的興起，基于SOA架構下的中間件技術逐漸向實時性過渡，這是SOA技術發展的一方面客觀需求。

    實時系統（Real-Time Systems）是一類特殊的軟件系統�！皩崟r”是指這些系統通常要滿足交互行為所施加的某些時間上的限制，例如系統必須在外部事件發生后指定時間之內做出反應，或指定操作必須在某個期限內完成等等。實時性和可靠性是實時系統的兩個最為關鍵的問題。Stankovic在1992年的另一個文章中為實時系統給出了一個清晰、被普遍接受的定義，即實時系統是那些正確性不僅取決于計算的邏輯結果，而且取決于結果產生時間的一類特殊系統。這個定義強調了實時系統與非實時系統的本質區別，即時間上的正確性是整個系統正確性的一個重要構成部分。事實上，正是這個特性使得幾十年來實時系統的研究發展成為軟件學科的獨特的理論和方法。

    實時中間件是一個建立在網絡環境上的分布式實時系統，較之傳統的實時系統更為復雜。譬如在一個軍事系統中，雷達捕獲目標信號，將目標信號傳送給目標識別系統識別目標，然后將識別的結果傳送到決策指揮系統，由決策指揮系統指揮相應的作戰單位采取行動。又例如無人機中的自動控制系統，系統中的部分自動控制邏輯是通過消息驅動的，可以通過向控制中心發送消息，實現飛機的導航和遠程控制。這些系統典型實時系統流程，它們的每一個環節都要求很強的實時性，要求實時的通信資源管理和計算資源管理。實時系統具有分布性、實時性、動態性、自治性的特點。

面向服務架構SOA

面向服務架構（Service-Oriented Architecture，SOA）是一種IT架構風格，支持將一個企業的業務轉換為一組相互鏈接的服務或可重復業務任務，可在需要時通過網絡訪問這些服務和任務。這個網絡可以是本地網絡、Internet，也可以分散于各地且采用不同的技術。通過對來自世界各地的服務進行組合，可讓最終用戶感覺似乎這些服務就安裝在本地桌面上一樣�？梢詫�這些服務進行結合，以完成特定的業務任務，從而讓你的業務快速適應不斷變化的客觀條件和需求。

這些服務是自包含的，具有定義良好的接口，允許這些服務的用戶——稱為客戶機或使用者，了解如何與其進行交互。從技術角度而言，SOA 帶來了“松散耦合”的應用程序組件，在此類組件中，代碼不一定綁定到某個特定的數據庫（甚至不一定綁定到特定的基礎設施）。正是得益于這個松散耦合特性，才使得能夠將服務組合為各種應用程序。這樣還大幅度提高了代碼重用率，可以在增加功能的同時減少工作量。服務契約用于定義服務提供者和客戶機之間的交互。所有交互都是基于“服務契約”進行的；通常，使用“基于消息的”技術來實現這些松散耦合的服務。

SOA可以根據需求通過網絡對松散耦合的粗粒度應用組件進行分布式部署、組合和使用。服務層是SOA的基礎，可以直接被應用調用，從而有效控制系統中與軟件代理交互的人為依賴性。

SOA的關鍵是“服務”的概念，W3C將服務定義為：“服務提供者完成一組工作，為服務使用者交付所需的最終結果。最終結果通常會使使用者的狀態發生變化，但也可能使提供者的狀態改變，或者雙方都產生變化”。

目前 ，SOA主要應用于企業的應用開發和服務管理，而SOA的松耦合的特性使得SOA應用到實時系統中而成為實時SOA，現在的一些應用系統，如正在開發中的新一代空中交通管理（Air Traffic Management）系統，是為了調整日益繁忙的航線，并連接各客戶端（比如美國聯邦航空管理局、國防部及國土安全部）的工作。這些系統需要更高的信息帶寬用于追蹤更多的飛行器和更復雜的“自由飛行”軌跡，同時需要更快的信息響應速度以更快地檢測飛行異常。其它方面也有類似的需求，比如醫療保健系統、數據采集與監控（SCADA）系統、網絡監控系統、能源分布系統、運輸系統，以及其它關鍵基礎設施系統。為了滿足這些系統的需求，SOA被越來越多地應用于實現高性能的實時系統，我們稱之為實時SOA。在實時SOA中，我們主要采用的是實時中間件技術。實時系統中要保證實時性，就要通過任務調度來保證的。任務調度是實時系統中的重要問題。

中間件系統的調度

對于實時中間件系統，任務調度是該系統的一個重要組成部分，它主要負責實現對基于優先級的消息任務的排序和任務調度，使得具有實時性要求的任務能夠在給定時間期限內完成。當任務調度模塊從客戶端接收到一系列的實時任務，它就根據這些任務的優先級，把任務插入到對應的任務隊列中，同時任務調度模塊監控處理器的使用情況，讓優先級高的任務搶先占有處理器。本文針對實時中間件系統的調度問題，設計了一個集成了多種調度策略的可擴展的任務調度框架。

    任務調度在實時消息中間件中主要在消息隊列中處理，它的具體結構圖如圖1所示：

                              圖1 ：任務調度模塊

當一個從提交者提交過來的新任務，它傳遞該任務給運行調度模塊，運行調度模塊是任務調度的核心，它判斷任務的相關信息，給任務賦給任務一個優先級，并且把任務插入到相應的優先級隊列中。

運行調度：不單單是簡單的任務優先級設置，然后插入隊列，它還應該實現對任務的調度，根據具體的應用情況修改任務的優先級，或者為了使得任務在指定的時間期限前完成。它不斷的監控任務和修改任務的優先級，時間期限等參數。運行調度的一個重要的目標就是實現任務的實時調度能力，在運行調度中引入實時調度算法，對有時間期限的任務進行有效的實時調度。

任務隊列中是若干事件隊列鏈，如圖1中所示。任務隊列中把相同優先級的任務放在同一個隊列中，這些任務隊列隨著運行調度的控制而變化，并且運行調度隨時向任務隊列中插入新的任務并且搶占式的修改任務的優先級別。

任務模型：

任務模型：在調度方法中的任務模型與處理器時間表類似，為了表示不同的任務類型，我們提供了一個通用的任務模型。這個任務模型既能夠建模周期性任務也能夠建模非周期性任務，如圖2，圖3所示。對于一個任務我們可以用一個元組來表示，S={D_i,P_i,R_i,A_i,T_i}，D_i表示任務的截止期，P_i表示任務的優先級，R_i表示任務最長運行的時間，A_i表示任務的到達時間，T_i對于周期性任務來說表示任務的周期，對于非周期的任務設置為0；

線程池

目前的事件線程派發方式有好多種，有基于優先級的單線程派發，無線程派發和多線程派發。單線程派發要求在新的線程到來之時，必須處理完當前的線程；無線程派發則不適用派發線程，它的特點是簡單，但是該派發方法無法保證實時事件的截止時間；一種比較常用的線程派發方法是多線程派發，它是為每個事件建立一個線程，目前很多種操作系統都支持多線程的處理。線程池模式如下所示：

可擴展的服務調度框架

web服務的任務同操作系統的任務一樣，有不一樣任務性質，像對傳感器的周期性訪問監控就是周期性的web服務調用，而其他的一些功能性訪問則是偶發的非周期性調用，對于一些關鍵的web服務有實時性的需求，如飛機上的嵌入式系統需要對即時出現的狀況做出快速的反應，而對于其他一些企業應用來說實時性不是很嚴格的要求。由于任務性質的多樣性和對于服務調用實時要求的不定性，我們需要提供一種滿足多種服務調度需要的中間件，也就是在我們的中間件中集成能夠滿足不同需求的調度算法。在中間件中即集成了能夠滿足一般任務的調度算法，也集成了可以滿足實時性任務的調度算法。調度算法的選擇是由中間件的用戶和web服務任務的性質決定的。這里設計了一個策略選擇模塊，通過他可以根據不同的調度算法設定任務的優先級或者滿足任務的實時性需求。該模塊可以與web服務容器通信，通過web服務的wsdl文檔獲取web服務的相關信息，對wsdl文檔進行擴展，相應的加入對調度相關信息的描述如web服務的周期，運行時間，截止期等。根據獲得的web服務信息可以選擇適合的調度策略，反饋給任務調度模塊。任務調度模塊根據不同的調度策略采用不同的優先級策略，對服務調用請求進行優先級分配。

調度算法

目前，實時系統在軟件發展中扮演著重要的角色，社會應用的需求要求我們建立起實時應用系統。實時任務調度是我們消息中間件系統中的一個組件，它主要是根據任務的優先級，任務時間執行期限等參數，對任務進行調度，使得優先級高的任務和時間期限急迫的任務讓處理器優先執行。關于任務調度算法，在很早的時候就已經有很多人在實時調度算法方面做了很多工作，在現有的非實時操作系統中也有對于非實時任務的調度算法，其中比較經典的幾個算法有：

1．RM(Rate Monotonic)法：RM方法的提出主要是用來解決周期性任務的。同一類型的任務會周期性的產生，RM法它對周期性的任務進行時序安排，它僅僅把優先級與任務周期率相關聯。任務出現的頻率越高，則該類型的任務具有比較高的優先級。在1973，Liu 和Laylan 的一個文章中就已經證明了該算法在固定優先級情況下的是最優的；

2．EDF(Earliest Deadline First)[6]：截止期任務優先算法是最為人熟知的實時任務調度算法。它的主要思想是根據任務的執行時間期限來對任務進行調度，為了保證任務的實時性，顯然讓時間期限最早截止的任務優先執行。EDF算法并不強調任務的周期性，它能夠對周期性任務和非周期性的任務進行統一調度。在1974 年，EDF 被證明在一系列可能的時序任務下的調度是最優的；

3．DM（Deadline Monotonic) [7]的提出也是專門來解決周期性任務的，并且它是針對RM 算法在應用中的缺陷而提出的一種解決方案。在RM 中，任務的優先級是和任務的周期關聯的，短周期任務具有比較高的優先級，這樣的優先級設置在一定程度上是非常簡單和實用的，但是它也要求處理器具有獨立性和周期性的處理任務，并且要求處理器的處理周期必須和任務時間期限等長或者更短，這樣對處理器處理任務的要求就非常的苛刻，在某種程度上是一個高要求。為了解決這種約束問題， DM 不僅僅只是為了解決具有周期性的任務，它還能夠對非周期性的任務設定優先級；

4.FCFS（First Come First Served）：按照任務進入系統的先后次序來挑選任務，先進入系統的任務優先被挑選。算法容易實現。但效率不高，只顧及作業等候時間，沒考慮任務要求服務時間的長短。因此優待了長作業而不利于短作業，有利于CPU繁忙的作業，而不利于I/O繁忙的作業。

5．短任務優先(SJF)：目標是減少平均周轉時間。對預計執行時間短的任務優先執行。通常后來的短任務不搶占正在執行的任務。比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業的等待時間。提高系統的吞吐量。缺點：對長作業非常不利，可能長時間得不到執行；未能依據作業的緊迫程度來劃分執行的優先級；難以準確估計作業（進程）的執行時間，從而影響調度性能。

6.最高響應比優先法(HRN，Highest Response Ratio Next):

　　最高響應比優先法(HRN)是對FCFS方式和短任務優先方式的一種綜合平衡。FCFS方式只考慮每個任務的等待時間而未考慮執行時間的長短，而SJF方式只考慮執行時間而未考慮等待時間的長短。因此，這兩種調度算法在某些極端情況下會帶來某些不便。HRN調度策略同時考慮每個任務的等待時間長短和估計需要的執行時間長短，從中選出響應比最高的任務投入執行。響應比R定義如下：R =(W+T)/T=1+W/T。其中T為該任務估計需要的執行時間，W為任務在后備狀態隊列中的等待時間。每當要進行任務調度時，系統計算每個任務的響應比，選擇其中R最大者投入執行。這樣，即使是長任務，隨著它等待時間的增加，W/T也就隨著增加，也就有機會獲得調度執行。這種算法是介于FCFS和SJF之間的一種折中算法。由于長任務也有機會投入運行，在同一時間內處理的任務數顯然要少于SJF法，從而采用HRN方式時其吞吐量將小于采用SJF 法時的吞吐量。另外，由于每次調度前要計算響應比，系統開銷也要相應增加。

7．Background Scheduling (BS)：BS是在1997 年提出來的，它[6]主要用來處理弱實時非周期任務與強實時周期任務。BS法把這兩類任務分在不同的隊列中，建立了兩個不同的優先級隊列。BS法通常是根據任務數目來決定優先級，任務數少的賦予較高的優先級經驗表明BS 在解決大工作量的弱實時任務并不具有優越性，但是它具有兩個顯要的優點：它的實現簡單，強實時任務能夠被確保在時間期限內完成；

8．PS（Pooling Server）：PS 通過創建一個線程池服務來存放非周期任務。每個時間間隔T，線程池自身激活處理未解決的任務，如果池中沒有未處理的任務則服務自己掛起直到下一個周期；

9．基于固定優先級：系統提供固定的優先級數，由用戶直接指定其任務的優先級，調度器根據用戶指定的優先級進行任務調度，優先級高的任務先運行。

以上這些調度算法都集成在策略選擇模塊，根據不同調度算法的優缺點和web服務的特點，我們采用不同的調度算法對web服務進行調度，而對外只提供一個策略選擇的接口，從而屏蔽調度算法的具體實現。如果有新的調度算法更適合當前的服務調度，只需實現已經定義好的接口。這樣做有利于調度算法的擴展，所以說可擴展性是該設計的的一個顯著的優點。

結論

中間件技術的研究是一個極為復雜和廣博的研究領域。而實時性的引入，無疑進一步增加了其研究的困難性。隨著分布式實時應用的發展，應用領域提出了越來越多這類的要求，所以出現的問題也越來越復雜，在現在中間件系統中，實時應用和非實時應用并存。對于非實時應用，需要強調公平的原則；而對于實時應用，則強調確定的原則。將這兩者結合起來，需要更好的調度方法，而如何在中間件中集成這些新的調度方法，也需要進一步的研究�？蓴U展的調度框架，既滿足了對于非實時任務調度的需要，又滿足了實時系統的任務調度需求。實時中間件通常應用于分布式實時應用，這同時需要實時通信的支持。動態調度往往需要進行在線可調度性的分析，而將這一操作置于服務器端，必然會占用服務器很大的資源，特別是頻繁地進行動態客戶的接納測試。這將會導致無法保證己經接納的客戶的實時性。如何解決該問題還有待進一步研究。

參考文獻：

[1] REAL-TIME SYSTEM SCHEDULING N. AudsleyA. Burns Department of Computer Science,University of York, UK.

[2] Scheduling Algorithms for Real-Time Systems  Arezou Mohammadi and Selim G. Akl School of Computing Queen’s University Kingston, Ontario Canada

[3] Buttazzo Giorgio. Hard Real-Time Computing Systems. Dordech, Netherlands: KlugerAcademic Publsher, 1997

[4] Binoy Ravindran and Ravi k.Devarase. Adaptive Resource Management Algorithms forPeriodic Tasks in Dynamic Real-Time Distributed Systems. Journal of Parallel and distributedComputing 62, 1527-1547(2002).

 [5] Abeni Luca, Buttazzo Giorgio. Adaptive Bandwidth Reservation for Multimedia Computing.HongKong, China: Proceedings of the IEEE Real-Time Systems Symposium, December 1999

[6]Buttazzo Giorgio.Hard Real-Time Computing Systems.Dordech,Netherlands:Kluger

Academic Publsher,1997

[7]Audsley,N.C.(1990).Deadline-monotonic Scheduling.YCS 146,Dept.of Computer science,

University of York

[8]分布式實時嵌入式中間件的調度體系  微計算機應用 2008 .2

作者簡介：趙博  男  北京航空航天大學北京新技術實驗室研究生 主要從事web服務開發，服務調度和Hoare邏輯理論方面的研究.09825