反饋控制下嵌入式實時系統調度算法設計研究

皇甫大雙

(江蘇安全技術職業學院，江蘇 徐州 221000)

0 引言

實時系統的提出，為多個領域的發展創造了有利條件[1]，例如多媒體信息處理、航空航天控制、機械設備控制等系統。這些系統作業與時間的約束密切相關，對任務開始執行、完成等時間要求較高[2]。為了達到任務實時管理目標，必須為其設置一套高效的調度機制。目前，應用比較多的兩種調度機制分別為靜態調度、動態調度，由于前者應用期間需要明確負載模型，確定可調度性，應用靈活性較低，所以應用較少[3-4]。后者雖然具備一定的靈活性，但是應用條件受限，一旦負載超過預期設置，調度耗費的處理器資源就會明顯增加[5]。為了彌補動態調度的不足，本文嘗試提出一種反饋控制下的嵌入式實時系統調度算法，并展開深入探究。

1 反饋控制下的嵌入式實時調度系統

1.1 動態調度存在的問題

目前，實時調度算法的開發主要采取動態調度方法。動態調度方法分為兩種，其中一種為最小松弛時間優先調度算法(Least Slack Time First，LST)，另外一種為最早截止期優先算法(Earliest Deadline First，EDF)[6]。這兩種方法的應用都是建立在已經創建的任務基礎上，根據任務內容要求，按照一定順序執行。存在的不足在于系統負載模型不確定條件下，調度任務過程會對系統運行造成較大影響，部分時段出現大幅度的動蕩[7]。從理論層面而言，系統當前輸入及以前輸入在很大程度上決定了系統輸出，不利于任務調度。

1.2 反饋控制調度系統的提出

一般情況下，工程師采用反饋控制環節改善系統運行穩定性，所以，本文嘗試引入反饋控制方法，進行反饋控制調度系統研究[8]。該系統中，反饋控制器采用的是比例積分微分控制器(Proportional Integral Derivative，PID)，該裝置不僅穩定性能較高，而且結構比較簡單，支持不確定、數學模型精度偏低條件作業，并且控制效果較好[9-10]。根據實時調度需求，設計的反饋控制調度系統結構如圖1所示。

圖1 反饋控制調度系統結構

該結構主要由比例調節器、微分調節器、積分調節器、監視器、任務調度器組成，在執行等級控制器的作用下，下達執行任務，經過多番調節處理，完成相關任務的執行，同時利用監視器觀察任務執行的整個過程。其中，被控變量為任務錯過率，記為MR(t)，控制變量為處理器總利用率調整量，記為ΔCPU。關于控制器PID作業描述如下：

(1)

公式(1)中，KD代表微分系數；KI代表積分系數；Kp代表比例系數。

關于任務錯過率的求解，采用以下公式計算：

MR(t)=n/(n+m)

(2)

公式(2)中，n和m均代表任務數，前者計量的是錯誤時限的數據，后者計量的是在時限范圍內的數據。

一般情況下，運行監視器能夠有效采集任務錯過率相關數據，作業期間，通過調節部分參數數據，控制監視器作業狀態[11]。為了便于控制，設置任務周期，記錄任務執行時間，構建任務關系模型。其中，系統任務總占用率U的求解方法如下：

(3)

公式(3)中，Ti代表任務周期；EXTi代表任務執行時間。為了便于調度控制，本模型對非周期任務采取周期化處理。如果任務隨機化嚴重，或者執行次數為1，那么為Ti賦予截止時間。

2 基于PID反饋控制的LST調度模型的構建

2.1 基于PID反饋控制的LST調度模型結構設計

本文以LST調度算法作為研究基礎，引入PID反饋控制系統，提出一種新的調度模型，即PID-FC-LST(PID-Feedback Control-LST)調度模型[12]。該模型主要調度實時任務，作業效率較高。PID-FC-LST調度模型結構如圖2所示。

圖2 PID-FC-LST調度模型結構

該模型主要由PID控制器、監視器、任務準入控制器、任務執行等級控制器、LST調度器、處理器組成。開啟監視器作業模式，按照一定周期規律，將系統任務錯過率MR(t)反饋給調度體系，按照接收到的不同等級任務命令，開啟處理器作業模式，采取針對性處理。當PID控制器接收到反饋信息MR(t)后，統計處理器利用率調整量，記為ΔCPU，涉及的計算公式如下：

(4)

公式(4)中，EMR(t)=MR(t)-MR0。其中，MR0代表錯過率對應的校準值。

當ΔCPU<0時，處理器指標中利用率的需求明顯下降；當ΔCPU>0時，處理器指標中利用率的需求明顯上升。當ΔCPU發生變化時，容易對任務執行等級控制器、準入控制器的作業狀態造成影響。假設系統作業期間，為了達到任務調度需求，任務執行等級控制器需要做出一定調整，涉及的調整參數為利用率，記為ΔCPU1。在此基礎上，準入控制器也應做出相應調整。關于利用率的調整計算為ΔCPU0=ΔCPU-ΔCPU1。

考慮到錯過率的修正，需要改變系統負載。所以，本研究嘗試利用執行等級控制器和準入控制器分別對當前任務執行的等級、是否接收新的任務兩項指標進行有效控制，實現系統運行隊列的任務調度，同時處理器的占用率也將隨之改變。在此環境下，系統負載發生改變，錯過率因此得到修正。通常情況下，如果系統錯過率數值偏高，ΔCPU<0，則下調處理器總體利用率；如果系統錯過率數值偏低，ΔCPU>0，則上調處理器總體利用率。

2.2 調度任務執行模型設計

本研究系統作業任務用T，D，A，C，EXT，TYPE，INST來表示，從初級任務開始執行，按照從低到高的順序執行。其中，執行時間由EXT決定，任務關鍵性由C決定。以下為換算公式：

EXL=C×a0-EXT×a1

(5)

公式(5)中，a1代表執行時間系數；a0代表關鍵性系數；EXL代表任務執行等級。從該公式中參數關系可以看出，執行時間與關鍵性之間呈現負相關關系，與任務執行等級之間呈現正相關關系。INST代表任務急迫性，通過調節該參數，能夠對準入任務加以控制。TYPE代表任務類型，主要分為3類，分別是軟實時、固定實時、硬實時。其中，任務關鍵性最強的類型為硬實時，最為薄弱的是軟實時。

本研究中，為了保證較高的時間要求，系統能夠有序調度，避免資源調度混亂問題的發生。系統對各個任務類型的最低優先級的調度順序進行了設定：(1)最高優先級(固定實時任務)<最低高優先級(硬實時任務)；(2)最高優先級(軟實時任務)<最低高優先級(固定實時任務)。

另外，D任務描述的是截止時間；A任務描述的是達到時間；T任務描述的是周期。當實時任務發生改變時，軟實時任務、固定實時任務的執行等級也將發生改變，此情況下T任務和D任務數值也將發生改變。這種任務調度設計方式，可以為控制器作業提供更為足夠空間的同時，根據操控需求及時為其提供資源。3種任務類型中，硬實時任務較為特殊，因其對時間要求較高，所以無法自動提供足夠的數據資源，需要借助調控設備，調整T值和D值。

3 嵌入式可配置操作系統環境下LST調度算法設計

本研究將設計的PID-FC-LST調度模型投入實踐應用，根據操控需求，為其配備嵌入式可配置操作系統，在此系統中開發LST調度算法，使其得以滿足嵌入式操作系統作業環境，從而為多功能操作系統作業提供較為可靠的資源調度控制工具。

3.1 嵌入式任務接口結構設計

由于PID-FC-LST調度模型在嵌入式操作系統環境中應用，任務調度功能無法被開啟，所以設計了程序編程接口，對操作系統結構進行了優化，使其得以與其他功能模塊兼容。任務接口結構的設計是以操作系統內核作為基底，利用內核線程API，創建任務API，開發用戶應用程序，從而實現任務接口的連接。

其中，API函數作為接口連接的主要工具，以entry_data為入口函數參數，該參數類型為cyg_addrword_t。運用API函數作為多種類型數據傳遞指針，主要用來傳遞任務中私有部分數據。通過數據傳遞，實現任務數據的擴展。嵌入式變量描述與程序任務數據結構如表1所示。

表1 嵌入式變量描述與程序任務數據結構

系統分別為各個實時任務分配定時器，綁定后操控時間相關數據。其中，擴展數據成員均利用API程序訪問，或者對數據加以修改處理。

3.2 LST調度系統作業設計

為了使資源調度得以有序進行，本系統開發了LST調度作業管理功能模塊。該模塊主要用于實時任務接收的調度控制，利用優先級映射器，排列實時任務執行順序，使任務調度得以有序展開。LST調度器結構如圖3所示。

圖3 LST調度器結構

按照任務關鍵性大小，設置3個優先等級，任務優先級檔次隨著關鍵性的增加而提升。相鄰關鍵性任務調度的處理是以臨界優先級作為調度依據，優先調度關鍵性較高的任務。然后確定任務優先級。按照一定時間間隔，從系統作業任務中獲取松弛時間，運用優先級映射器計算松弛時間，以此確定任務的優先級。其中，松弛時間與任務優先級之間呈現負相關關系。最后，利用多級隊列調度器，控制任務進入系統運行隊列的先后順序。

3.3 任務執行等級控制設計

任務執行等級控制以優先級映射器作業期間產生的時間間隔nTM為依據，根據nTM中的n，確定任務執行等級。當n值偏大時，優先級映射器作業期間占用處理器的資源較少，然而該條件也會導致松弛時間敏感度下降，部分任務執行期間容易錯過時限。當n值偏小時，任務松弛時間不容易受其影響，能夠以較小的松弛時間完成任務執行。通常情況下，這些任務執行關鍵性較高情況下，n的數值越小。因此，可以通過為n賦值，來控制任務執行等級。

4 算法應用測試分析

4.1 應用測試內容與方法

設置90個采樣點，運用LST算法、PID-FC-LST算法控制監視器，從而獲取任務錯過率，并記錄測試結果。同時，利用監視器采集空閑任務條件下的處理器占用率，而后計算處理器占用率。

4.2 測試結果分析

按照測試內容與方法，分別對兩種算法應用期間產生的任務錯過率、處理器總利用率展開測試，結果如表1—2所示。

表1中，LST算法應用期間任務錯過率較高，最小值產生在樣點30處，數值為2.06%。相比之下，PID-FC-LST算法的任務錯過率明顯降低，最大錯過率為0.53%。所以，本文設計的算法能夠有效控制任務錯過問題。

表1 任務錯過率測試結果

表2中，LST算法應用期間，處理器利用率隨著采樣點數量的增加而不斷波動，利用率在99.2%以上，并且采樣點40和采樣點80的利用率達到了100.0%，嚴重超荷。增加反饋控制環節，即運用PID-FC-LST算法，降低了處理器利用率，9組實驗測試中處理器利用率最大值為98.9%。由此看來，本算法的處理器資源利用更加合理。

表2 處理器總利用率測試結果

5 結語

本文針對系統作業實時調度問題展開探究，在LST算法基礎上，增加反饋控制體系，借助嵌入式實時系統作業環境，設計一種新的任務調度算法PID-FC-LST。測試結果顯示，PID-FC-LST算法不僅可以有效降低任務錯過率，而且還能夠合理利用處理器資源，避免處理器作業超荷問題的產生，有助于系統作業實時調度的有序開展。