實(shí)時(shí)操作系統(tǒng)VxWorks的內(nèi)核任務(wù)調(diào)度研究

      1、引言
   

       VxWorks操作系統(tǒng)是WindRiver公司開發(fā)的一種高性能的嵌入式實(shí)時(shí)操作系統(tǒng)。它帶有一個(gè)功能強(qiáng)大的集成開發(fā)系統(tǒng)環(huán)境Tornado。

        VxWorks具有軟件生成代碼小、實(shí)時(shí)性強(qiáng)及響應(yīng)速度快等特點(diǎn)，特別適合于具有實(shí)時(shí)和多任務(wù)要求的系統(tǒng)。VxWorks自20世紀(jì)80年代問世以來，以其高性能、高可靠性、高實(shí)時(shí)性等特點(diǎn)成為實(shí)時(shí)操作系統(tǒng)中最具特色的系統(tǒng)。自1996年登陸中國，短短幾年就已成為國防、工業(yè)自動(dòng)化、網(wǎng)絡(luò)通信、航空航天、醫(yī)療儀器、狀態(tài)監(jiān)控以及消費(fèi)電子產(chǎn)品等嵌入式實(shí)時(shí)領(lǐng)域的首選操作系統(tǒng)。由于嵌入式實(shí)時(shí)操作系統(tǒng)在內(nèi)核方面具有自身的特點(diǎn)，本文著重對(duì)實(shí)時(shí)內(nèi)核中任務(wù)調(diào)度進(jìn)行了詳細(xì)分析。

       2、任務(wù)調(diào)度概述

      2.1 調(diào)度的概念
   

       構(gòu)成應(yīng)用軟件系統(tǒng)的程序集合中，獨(dú)立的、相互作用的程序單元，在其執(zhí)行時(shí)稱之為任務(wù)。單個(gè)CPU 中，多任務(wù)機(jī)制制造了一個(gè)多個(gè)任務(wù)同時(shí)執(zhí)行的假象。其實(shí)系統(tǒng)只是根據(jù)一個(gè)多任務(wù)調(diào)度算法，將內(nèi)核插入到這些任務(wù)中執(zhí)行。實(shí)時(shí)系統(tǒng)VxWorks的一個(gè)任務(wù)可有多種狀態(tài)，但最基本的狀態(tài)有以下四種：

      1) 就緒態(tài)(Ready)：任務(wù)只等待系統(tǒng)分配CUP資源。
      2) 掛起態(tài)(Pend)：任務(wù)需等待某些不可利用的資源而被阻塞。
      3) 休眠態(tài)(Sleep)：如果系統(tǒng)不需要某一個(gè)任務(wù)工作，則這個(gè)任務(wù)處于休眠狀態(tài)。
      4) 延遲態(tài)(Delay)：任務(wù)被延遲時(shí)所處的狀態(tài)。
   

       當(dāng)系統(tǒng)函數(shù)對(duì)某一個(gè)任務(wù)進(jìn)行操作時(shí)，任務(wù)從一種狀態(tài)躍遷到另一種狀態(tài)。處于任一狀態(tài)的任務(wù)都可被刪除。VxWorks的任務(wù)躍遷如圖1所示。

        任務(wù)由系統(tǒng)內(nèi)核調(diào)度運(yùn)行一段固定長度的時(shí)間，稱為時(shí)間片。調(diào)度是指為任務(wù)分配資源和時(shí)間，使系統(tǒng)滿足特定的性能要求。調(diào)度算法的目的是在正常情況下，盡可能滿足所有任務(wù)的時(shí)限：在峰值負(fù)載條件下，保證強(qiáng)實(shí)時(shí)任務(wù)滿足時(shí)限。因?yàn)闀r(shí)限是區(qū)分實(shí)時(shí)系統(tǒng)和非實(shí)時(shí)系統(tǒng)的關(guān)鍵因素，因此調(diào)度算法是實(shí)時(shí)系統(tǒng)的基本問題。實(shí)時(shí)操作系統(tǒng)所具有的運(yùn)行性能，如吞吐量的大小、周轉(zhuǎn)時(shí)間的長短、相應(yīng)的及時(shí)性和可預(yù)測(cè)性等在很大程度上都取決于實(shí)時(shí)調(diào)度。

      2.2調(diào)度的類型
   

       雖然調(diào)度的主要目的都是為了分配處理機(jī)，但在不同的OS中所采用的調(diào)度方式是完全不同的。在執(zhí)行調(diào)度時(shí)所采用的調(diào)度算法也可能不同。因此，常按照調(diào)度的層次把調(diào)度分成高級(jí)、中級(jí)和低級(jí)調(diào)度。
   

       高級(jí)調(diào)度又稱長程調(diào)度或作業(yè)調(diào)度，用于決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。然而在實(shí)時(shí)系統(tǒng)中，為了能及時(shí)響應(yīng)，用戶通過鍵盤輸入的數(shù)據(jù)都是直接送入內(nèi)存，因而實(shí)時(shí)系統(tǒng)通常不需要作業(yè)調(diào)度。
   

       中級(jí)調(diào)度又稱中程調(diào)度，引入它的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。它使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存空間，而將它們調(diào)到外存上去等待，此時(shí)的狀態(tài)稱為掛起狀態(tài)。當(dāng)這些進(jìn)程重新具備運(yùn)行條件，且內(nèi)存又有空閑，由中級(jí)調(diào)度決定，將外存上的那些重新具備運(yùn)行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并使它為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。
   

        低級(jí)調(diào)度又稱進(jìn)程調(diào)度。它決定就緒隊(duì)列中的哪個(gè)進(jìn)程將獲得處理機(jī)，然后由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的操作。進(jìn)程調(diào)度是最基本的一種調(diào)度，各種OS中都必須配置這級(jí)調(diào)度。進(jìn)程調(diào)度可采用下述兩種方式。

      1)非搶占方式。

       采用這種調(diào)度方式，一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而被阻塞，才再把處理機(jī)分配給其他進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。顯然它難于滿足緊急任務(wù)的要求，實(shí)時(shí)系統(tǒng)中不宜采用這種調(diào)度方式。

      2)搶占方式。

      允許調(diào)度程序根據(jù)某種原則，去停止某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)，重新分配給另一進(jìn)程。搶占的原則有：

       ① 時(shí)間片原則。各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。
       ② 優(yōu)先權(quán)原則。當(dāng)一個(gè)進(jìn)程到來時(shí)，如果其優(yōu)先級(jí)比正在執(zhí)行的進(jìn)程的優(yōu)先級(jí)高，便停止正在執(zhí)行的進(jìn)程，將處理機(jī)分配給優(yōu)先級(jí)高的進(jìn)程，使之執(zhí)行。實(shí)時(shí)系統(tǒng)中一般采用基于優(yōu)先級(jí)的搶占式調(diào)度和輪轉(zhuǎn)調(diào)度的進(jìn)程調(diào)度和中程調(diào)度相結(jié)合的調(diào)度策略。因此既可具有較大的靈活性，又能獲得極小的調(diào)度延遲。

     3、任務(wù)調(diào)度分析
   

       Wind內(nèi)核缺省調(diào)度機(jī)制為基于優(yōu)先級(jí)的搶占式調(diào)度。采用這種機(jī)制時(shí)，系統(tǒng)把處理機(jī)分配給優(yōu)先級(jí)最高的進(jìn)程，使之執(zhí)行。一旦出現(xiàn)了另一個(gè)優(yōu)先級(jí)更高的進(jìn)程時(shí)，進(jìn)程調(diào)度程序剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給高優(yōu)先級(jí)任務(wù)。而在相同優(yōu)先級(jí)的多個(gè)任務(wù)之間，采用時(shí)間片輪轉(zhuǎn)調(diào)度機(jī)制。采用這種機(jī)制時(shí)，當(dāng)一個(gè)任務(wù)到達(dá)時(shí)，它被排在輪轉(zhuǎn)隊(duì)列的后面，等待分配給自己的時(shí)間片的到來，如果在時(shí)間片內(nèi)沒有結(jié)束，則再等待屬于自己的時(shí)間片的到來，直到任務(wù)完成。

      3.1 優(yōu)先級(jí)搶占式
   

       采用基于優(yōu)先級(jí)的搶占式調(diào)度，系統(tǒng)中每個(gè)任務(wù)都有一個(gè)介于最高0到最低255之間的優(yōu)先級(jí)。任一時(shí)刻，系統(tǒng)內(nèi)核一旦發(fā)現(xiàn)一個(gè)優(yōu)先級(jí)更高的任務(wù)轉(zhuǎn)變?yōu)榫途w態(tài)，內(nèi)核就保存當(dāng)前任務(wù)的上下文并把當(dāng)前任務(wù)狀態(tài)轉(zhuǎn)換為阻塞態(tài)，同時(shí)切換到這個(gè)高優(yōu)先級(jí)任務(wù)的上下文執(zhí)行。如圖2，低優(yōu)先級(jí)的task1被中優(yōu)先級(jí)的task2搶占，task2又被高優(yōu)先級(jí)的task3搶占。

      3.2 輪轉(zhuǎn)調(diào)度算法
   

        采用輪轉(zhuǎn)調(diào)度算法，系統(tǒng)讓處于就緒態(tài)的優(yōu)先級(jí)相同的一組任務(wù)依次輪流執(zhí)行預(yù)先確定長度的時(shí)間片。這是一種處理機(jī)平均分配的方法。如果不使用輪轉(zhuǎn)調(diào)度算法，優(yōu)先級(jí)相同的一組任務(wù)中第一個(gè)獲得處理機(jī)的任務(wù)將不會(huì)被阻塞而獨(dú)占處理機(jī)，如果沒有阻塞或其他情況發(fā)生，它不會(huì)放棄處理機(jī)的使用權(quán)。如圖3，相同優(yōu)先級(jí)的task1、task2和task3平均分配預(yù)先確定的處理機(jī)時(shí)間片。

 
      3.3 搶占調(diào)度與輪轉(zhuǎn)調(diào)度混合方式
   

       有時(shí)，基于優(yōu)先級(jí)的搶占式調(diào)度可與輪轉(zhuǎn)調(diào)度相結(jié)合。當(dāng)優(yōu)先級(jí)相同的一組任務(wù)依次輪流平均分配處理機(jī)時(shí)，若有高優(yōu)先級(jí)的任務(wù)轉(zhuǎn)變?yōu)榫途w態(tài)則可搶占該組任務(wù)。直到再一次符合執(zhí)行條件時(shí)，該組任務(wù)才可再次共享處理機(jī)。如圖4，相同優(yōu)先級(jí)的task1、task2和task3輪流占有處理機(jī)時(shí)，高于該組優(yōu)先級(jí)的task4搶占處理機(jī)，等task4執(zhí)行結(jié)束，該組任務(wù)再次共享處理機(jī)。
 

 
       為了任務(wù)控制的靈活性，wind內(nèi)核還提供了動(dòng)態(tài)優(yōu)先級(jí)機(jī)制，任務(wù)的優(yōu)先級(jí)在運(yùn)行期間可動(dòng)態(tài)地變化。同時(shí)，為了防止優(yōu)先級(jí)反轉(zhuǎn)，還具有優(yōu)先級(jí)繼承機(jī)制，通過使用互斥信號(hào)量可以防止高優(yōu)先級(jí)的任務(wù)被迫等待一段不確定時(shí)間，直到一個(gè)低優(yōu)先級(jí)任務(wù)完成。

     4、結(jié)論
   

      任務(wù)是代碼運(yùn)行的一個(gè)映像，從系統(tǒng)的角度來看，任務(wù)是競(jìng)爭(zhēng)系統(tǒng)資源的最小運(yùn)行單元。vxworks內(nèi)核使任務(wù)能快速共享系統(tǒng)的絕大部分資源，同時(shí)有獨(dú)立的上下文來控制個(gè)別線程的執(zhí)行。內(nèi)核調(diào)度是一個(gè)實(shí)時(shí)系統(tǒng)的核心，它的好壞直接影響整個(gè)系統(tǒng)的好壞，通過對(duì)這種內(nèi)核調(diào)度分析，可以更深入的理解實(shí)時(shí)操作系統(tǒng)設(shè)計(jì)的獨(dú)到之處。