實時操作系統VxWorks的內核任務調度研究

1、引言
    VxWorks操作系統是WindRiver公司開發的一種高性能的嵌入式實時操作系統。它帶有一個功能強大的集成開發系統環境Tornado。VxWorks具有軟體生成代碼小、實時性強及響應速度快等特點，特別適合於具有實時和多任務要求的系統。VxWorks自20世紀80年代問世以來，以其高性能、高可靠性、高實時性等特點成為實時操作系統中最具特色的系統。自1996年登陸中國，短短几年就已成為國防、工業自動化、網路通信、航空航天、醫療儀器、狀態監控以及消費電子產品等嵌入式實時領域的首選操作系統。由於嵌入式實時操作系統在內核方面具有自身的特點，本文著重對實時內核中任務調度進行了詳細分析。

2、任務調度概述
2.1 調度的概念
    構成應用軟體系統的程序集合中，獨立的、相互作用的程序單元，在其執行時稱之為任務。單個CPU 中，多任務機制製造了一個多個任務同時執行的假象。其實系統只是根據一個多任務調度演算法，將內核插入到這些任務中執行。實時系統VxWorks的一個任務可有多種狀態，但最基本的狀態有以下四種：
1) 就緒態(Ready)：任務只等待系統分配CUP資源。
2) 掛起態(Pend)：任務需等待某些不可利用的資源而被阻塞。
3) 休眠態(Sleep)：如果系統不需要某一個任務工作，則這個任務處於休眠狀態。
4) 延遲態(Delay)：任務被延遲時所處的狀態。
    當系統函數對某一個任務進行操作時，任務從一種狀態躍遷到另一種狀態。處於任一狀態的任務都可被刪除。VxWorks的任務躍遷如圖1所示。
    
     任務由系統內核調度運行一段固定長度的時間，稱為時間片。調度是指為任務分配資源和時間，使系統滿足特定的性能要求。調度演算法的目的是在正常情況下，儘可能滿足所有任務的時限：在峰值負載條件下，保證強實時任務滿足時限。因為時限是區分實時系統和非實時系統的關鍵因素，因此調度演算法是實時系統的基本問題。實時操作系統所具有的運行性能，如吞吐量的大小、周轉時間的長短、相應的及時性和可預測性等在很大程度上都取決於實時調度。

2.2調度的類型
    雖然調度的主要目的都是為了分配處理機，但在不同的OS中所採用的調度方式是完全不同的。在執行調度時所採用的調度演算法也可能不同。因此，常按照調度的層次把調度分成高級、中級和低級調度。
    高級調度又稱長程調度或作業調度，用於決定把外存上處於後備隊列中的哪些作業調入內存，並為它們創建進程、分配必要的資源，然後再將新創建的進程排在就緒隊列上，準備執行。然而在實時系統中，為了能及時響應，用戶通過鍵盤輸入的數據都是直接送入內存，因而實時系統通常不需要作業調度。
    中級調度又稱中程調度，引入它的主要目的是為了提高內存利用率和系統吞吐量。它使那些暫時不能運行的進程不再佔用寶貴的內存空間，而將它們調到外存上去等待，此時的狀態稱為掛起狀態。當這些進程重新具備運行條件，且內存又有空閑，由中級調度決定，將外存上的那些重新具備運行條件的就緒進程重新調入內存，並使它為就緒狀態，掛在就緒隊列上等待進程調度。
    低級調度又稱進程調度。它決定就緒隊列中的哪個進程將獲得處理機，然後由分派程序執行把處理機分配給該進程的操作。進程調度是最基本的一種調度，各種OS中都必須配置這級調度。進程調度可採用下述兩種方式。
1)非搶佔方式。採用這種調度方式，一旦把處理機分配給某進程后，便讓該進程一直執行，直到該進程完成或發生某事件而被阻塞，才再把處理機分配給其他進程，決不允許某進程搶佔已經分配出去的處理機。顯然它難於滿足緊急任務的要求，實時系統中不宜採用這種調度方式。
2)搶佔方式。允許調度程序根據某種原則，去停止某個正在執行的進程，將已分配給該進程的處理機，重新分配給另一進程。搶佔的原則有：
① 時間片原則。各進程按時間片運行，當一個時間片用完后，便停止該進程的執行而重新進行調度。
② 優先權原則。當一個進程到來時，如果其優先順序比正在執行的進程的優先順序高，便停止正在執行的進程，將處理機分配給優先順序高的進程，使之執行。實時系統中一般採用基於優先順序的搶佔式調度和輪轉調度的進程調度和中程調度相結合的調度策略。因此既可具有較大的靈活性，又能獲得極小的調度延遲。

3、任務調度分析
    Wind內核預設調度機製為基於優先順序的搶佔式調度。採用這種機制時，系統把處理機分配給優先順序最高的進程，使之執行。一旦出現了另一個優先順序更高的進程時，進程調度程序剝奪當前任務的執行，將處理機分配給高優先順序任務。而在相同優先順序的多個任務之間，採用時間片輪轉調度機制。採用這種機制時，當一個任務到達時，它被排在輪轉隊列的後面，等待分配給自己的時間片的到來，如果在時間片內沒有結束，則再等待屬於自己的時間片的到來，直到任務完成。
3.1 優先順序搶佔式
    採用基於優先順序的搶佔式調度，系統中每個任務都有一個介於最高0到最低255之間的優先順序。任一時刻，系統內核一旦發現一個優先順序更高的任務轉變為就緒態，內核就保存當前任務的上下文並把當前任務狀態轉換為阻塞態，同時切換到這個高優先順序任務的上下文執行。如圖2，低優先順序的task1被中優先順序的task2搶佔，task2又被高優先順序的task3搶佔。
 
3.2 輪轉調度演算法
    採用輪轉調度演算法，系統讓處於就緒態的優先順序相同的一組任務依次輪流執行預先確定長度的時間片。這是一種處理機平均分配的方法。如果不使用輪轉調度演算法，優先順序相同的一組任務中第一個獲得處理機的任務將不會被阻塞而獨佔處理機，如果沒有阻塞或其他情況發生，它不會放棄處理機的使用權。如圖3，相同優先順序的task1、task2和task3平均分配預先確定的處理機時間片。
 
3.3 搶佔調度與輪轉調度混合方式
    有時，基於優先順序的搶佔式調度可與輪轉調度相結合。當優先順序相同的一組任務依次輪流平均分配處理機時，若有高優先順序的任務轉變為就緒態則可搶佔該組任務。直到再一次符合執行條件時，該組任務才可再次共享處理機。如圖4，相同優先順序的task1、task2和task3輪流佔有處理機時，高於該組優先順序的task4搶佔處理機，等task4執行結束，該組任務再次共享處理機。
 
    為了任務控制的靈活性，wind內核還提供了動態優先順序機制，任務的優先順序在運行期間可動態地變化。同時，為了防止優先順序反轉，還具有優先順序繼承機制，通過使用互斥信號量可以防止高優先順序的任務被迫等待一段不確定時間，直到一個低優先順序任務完成。

4、結論
    任務是代碼運行的一個映像，從系統的角度來看，任務是競爭系統資源的最小運行單元。vxworks內核使任務能快速共享系統的絕大部分資源，同時有獨立的上下文來控制個別線程的執行。內核調度是一個實時系統的核心，它的好壞直接影響整個系統的好壞，通過對這種內核調度分析，可以更深入的理解實時操作系統設計的獨到之處。