彭 浩，韓江洪

（合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥 230009）

在復(fù)雜實時嵌入式系統(tǒng)中，多個軟件子系統(tǒng)同時運行在一個硬件平臺上［1－3］。為保證系統(tǒng)的安全性，防止某個軟件子系統(tǒng)中的故障向其他正常運行的子系統(tǒng)蔓延，必須采用資源分區(qū)的方法將其分別隔離，使每個軟件子系統(tǒng)運行在一個獨立的分區(qū)中。分區(qū)結(jié)構(gòu)的實時系統(tǒng)采用包含分區(qū)級調(diào)度和任務(wù)級調(diào)度的2層調(diào)度模型，前者在所有分區(qū)之間尋找優(yōu)先級最高的有可運行任務(wù)的分區(qū)，后者在該分區(qū)內(nèi)尋找優(yōu)先級最高的就緒任務(wù)，并使該任務(wù)占用處理器運行。

為了在開放系統(tǒng)中運行實時應(yīng)用程序而引入分層調(diào)度［4］，分層調(diào)度受到學(xué)術(shù)界廣泛關(guān)注和研究。文獻［5］采用固定延遲分區(qū)模型對分區(qū)獲取資源的情況建模，并分別研究了任務(wù)級采用單調(diào)速率（rate monotonic，RM）和最早截止期優(yōu)先（earliest deadline first，EDF）調(diào)度算法的可調(diào)度性判定條件；文獻［6］在任務(wù)級采用EDF調(diào)度算法的情況下，研究了分區(qū)級采用RM和EDF調(diào)度算法的可調(diào)度性判定條件；文獻［7］在固定優(yōu)先級調(diào)度算法的分層調(diào)度系統(tǒng)可調(diào)度性判定條件下，采用響應(yīng)時間分析法建立了分區(qū)級和任務(wù)級，并且對比了不同的分區(qū)資源補充算法帶來的影響，但該方法不具有模塊化的性質(zhì)，難以在較大規(guī)模的復(fù)雜系統(tǒng)中使用；文獻［8］在EDF調(diào)度算法的分層調(diào)度系統(tǒng)可調(diào)度性判定條件下，采用響應(yīng)時間分析法研究分區(qū)級和任務(wù)級，該方法也難以在復(fù)雜系統(tǒng)中使用。以上研究在分區(qū)級和任務(wù)級都采用了完全可搶占調(diào)度算法。

搶占會帶來額外的系統(tǒng)開銷，例如運行調(diào)度器的開銷，以及Cache內(nèi)容更迭帶來的性能損失等，采用受限搶占調(diào)度可以減少搶占次數(shù)，從而相應(yīng)地降低這些開銷。在分層調(diào)度的系統(tǒng)中，分區(qū)級搶占與任務(wù)級搶占相比，會導(dǎo)致更大的額外開銷。本文建立基于浮動不可搶占區(qū)的延遲搶占分區(qū)模型，在保證實時任務(wù)滿足截止期時間約束的前提下，減少過多的隨意搶占和由此帶來的處理器資源浪費。

1 系統(tǒng)的形式化描述

本文假設(shè)所研究的實時系統(tǒng)包含m個分區(qū)Γ，每個分區(qū)Γi中運行一個軟件子系統(tǒng)，Γi包含ni個任務(wù)，系統(tǒng)的共享資源為處理器，并用運行時間表示處理器資源。分區(qū)之間和軟件子系統(tǒng)內(nèi)均采用固定優(yōu)先級調(diào)度，并假設(shè)分區(qū)和任務(wù)都按照優(yōu)先級降序排列，即下標序號小的分區(qū)或任務(wù)具有高優(yōu)先級。

延遲搶占分區(qū)模型定義為三元組Γi｛Pi，Qi，Xi｝，其中，Pi為分區(qū)的周期，表示分區(qū)獲得資源補充的時間間隔；Qi為分區(qū)在一個周期內(nèi)能夠獲得運行時間的最大值，稱為資源預(yù)算。在每個周期開始時分區(qū)的資源預(yù)算補充到Qi，分區(qū)內(nèi)的任務(wù)運行會同比例消耗該分區(qū)的資源預(yù)算，預(yù)算被消耗完時，分區(qū)進入停止狀態(tài)直到下一個周期開始時再度補充資源預(yù)算。當分區(qū)內(nèi)沒有任務(wù)運行時，預(yù)算不被消耗，同時一個周期未耗盡的預(yù)算在下一周期開始前將被丟棄；Xi為該分區(qū)不可搶占區(qū)的最大值。當分區(qū)Γi獲得處理器開始運行時，系統(tǒng)進入一個長度為Xi的不可被其他分區(qū)搶占的時間段，直到該時間段結(jié)束或分區(qū)內(nèi)沒有可運行任務(wù)，當前運行分區(qū)內(nèi)部的任務(wù)依然完全可搶占。如果分區(qū)在本周期內(nèi)剩余的資源預(yù)算小于Xi，則下一個不可搶占區(qū)長度等于剩余預(yù)算。任務(wù)用三元組τi｛Ti，Ci，Di｝表示，其中，Ti為該任務(wù)釋放的最小時間間隔，對于周期任務(wù)而言即為其周期；Ci為任務(wù)不間斷運行一次所需要的最長運行時間；Di為任務(wù)的相對截止期，Di≤Ti。

2 可調(diào)度性分析

實時系統(tǒng)可調(diào)度是指系統(tǒng)中的所有任務(wù)都能在截止期之前響應(yīng)。在分層調(diào)度模型中，系統(tǒng)可調(diào)度性包含分區(qū)可調(diào)度性和任務(wù)可調(diào)度性2個方面。分區(qū)可調(diào)度是指在最壞情況下，分區(qū)Γi在每個周期都能獲得長度為Qi的處理器運行時間。任務(wù)可調(diào)度是指在分區(qū)的資源供給模型下，分區(qū)內(nèi)的所有任務(wù)都能在截止期之前響應(yīng)。

為了描述分區(qū)獲得資源的情況，文獻［9］首先提出了資源供給模型，即具有延遲上界的虛擬資源模型。文獻［10］提出了周期性資源分區(qū)模型，并使用周期P和預(yù)算Q2個參數(shù)對分區(qū)的周期性行為建模，該模型具有模塊化的優(yōu)點。本文中的延遲搶占資源分區(qū)模型建立在周期性資源分區(qū)模型基礎(chǔ)上，最大不可搶占區(qū)Xi并不影響周期性資源分區(qū)模型的原有屬性，因此繼承了其模塊化的特點，降低了復(fù)雜分區(qū)系統(tǒng)的設(shè)計難度。

分區(qū)模型的資源供給下限函數(shù)sbfΓ（t）表示在任意長度為t的時間段內(nèi)，分區(qū)Γ能夠獲得的運行時間的下限。sbfΓ（t）的計算公式為：

其中，k＝max（（t－（P－Q））/P，1）。

sbfΓ（t）的線性化下限為：

lsbfΓ（t）和sbfΓ（t）的關(guān)系如圖1所示。

圖1 資源供給函數(shù)

2.1 分區(qū)可調(diào)度性

假設(shè)所有分區(qū)都以最大負荷運行，即分區(qū)內(nèi)始終存在可以運行的任務(wù)，這種情況下Γ受到來自高優(yōu)先級分區(qū)的干擾最大，即在相同時間內(nèi)Γ獲得的運行時間最少，并且?？梢钥醋魇且粋€周期為P、運行時間為Q，相對截止期等于P，且具有最大不可搶占區(qū)X的任務(wù)?！?。如果任務(wù)集｛Γi′｜1≤i≤m｝可調(diào)度，則原分區(qū)集是可調(diào)度的。為方便敘述，本文討論虛擬任務(wù)集｛Γi′｜1≤i≤m｝的可調(diào)度性。

定義1Bi為任務(wù)Γi′的最長被阻塞時間，等于所有優(yōu)先級低于Γi′的任務(wù)的不可搶占區(qū)的最大值，即

定義2 設(shè)ε為一任意小的正實數(shù)，任務(wù)Γi′的臨界時刻tc為Γi′和所有優(yōu)先級高于Γi′的分區(qū)同時釋放工作的時刻，并且在tc－ε時系統(tǒng)進入長度為Bi的不可搶占區(qū)。

定義3i級剩余負載loadi（t）表示在時刻t未完成的所有優(yōu)先級高于和等于i的工作剩余運行時間之和。

定義4i級繁忙期是指一段時間間隔（a，b），滿足loadi（a）＝loadi（b）＝0，?t∈（a，b），loadi（t）＞0。

在延遲搶占調(diào)度下，任務(wù)Γi′的最壞情況響應(yīng)時間不一定發(fā)生在臨界時刻之后的第1次工作，而可能發(fā)生在臨界時刻之后的i級繁忙期內(nèi)某一次工作。本文假設(shè)臨界時刻為時間零點，臨界時刻后的i級繁忙期長度L的計算公式為：

迭代計算（4）式直到Ln＝Ln－1，Ln即為所求繁忙期的長度，記為Li。（4）式收斂于Ln＝Ln－1是因為在優(yōu)先級高于和等于i的任務(wù)的總使用率小于1時，i級繁忙期的長度必然是有界的，L0是其最小可能取值，如果在計算中得到Ln－1等于i級繁忙期的長度，則在Ln－1內(nèi)所有任務(wù)的運行時間需求之和也等于i級繁忙期的長度，即有Ln＝Ln－1，如果Ln－1小于i級繁忙期的長度，則在Ln－1內(nèi)所有任務(wù)的運行時間需求之和大于Ln－1，繼續(xù)迭代計算（4）式直至Ln＝Ln－1。在這段時間內(nèi)，Γi′共釋放了Ki＝Li/Pi次工作，Γi′可調(diào)度的充要條件是Ki次工作都是可調(diào)度的。

定義5i級累積負載wi（t）表示從臨界時刻開始的時間段t內(nèi)，優(yōu)先級高于及等于i的任務(wù)釋放的所有工作所需的運行時間的和。

對于第k次工作Γik′（k∈｛［1，Ki］∩N＋｝），如果?t∈（（k－1）Pi，kPi］，則有：

則Γik′是可調(diào)度的。

不等式（6）式只需要驗證Bi＋wi（t）的不連續(xù)點，即t∈｛（（k－1）Pi，kPi］∩｛hPj｜h∈N，j≤i｝｝。

2.2 任務(wù)可調(diào)度性

在完全可搶占固定優(yōu)先級調(diào)度的任務(wù)集中，任務(wù)τi可調(diào)度的充要條件是在臨界時刻釋放的工作在超過截止期Di之前響應(yīng)。臨界時刻是指任務(wù)τi和任務(wù)集中所有優(yōu)先級高于τi的任務(wù)同時釋放1次工作的時間點。本文中假設(shè)臨界時刻為時間零點。

在分區(qū)Γ中，任務(wù)τi可調(diào)度的充要條件是?t0∈（0，Di］，分區(qū)的資源供給大于或等于任務(wù)集的i級累積負載wi（t0），則有：

其中，

其中，t0為任務(wù)的最壞情況響應(yīng)時間。

3 分區(qū)設(shè)計

分區(qū)設(shè)計為在已知軟件子系統(tǒng)內(nèi)所有任務(wù)參數(shù)的情況下，選取合適的分區(qū)參數(shù)，使系統(tǒng)可調(diào)度。本文假設(shè)分區(qū)的周期P為系統(tǒng)設(shè)計階段由設(shè)計人員選取的參數(shù)，分區(qū)設(shè)計過程即求取適當?shù)腝和X。本文提出一種兩階段分區(qū)設(shè)計算法。第1階段根據(jù)任務(wù)參數(shù)計算出滿足軟件子系統(tǒng)資源需求的最小Q；第2階段根據(jù)各個分區(qū)的P和Q計算分區(qū)不可搶占區(qū)的最大值X。

3.1 分區(qū)最小預(yù)算

為了簡化計算，分區(qū)設(shè)計過程采用線性資源供給下限函數(shù)lsbfΓ（t）取代sbfΓ（t）。分區(qū)資源預(yù)算的取值必須滿足分區(qū)內(nèi)每個任務(wù)可調(diào)度性的需求。對于任務(wù)τi，需要滿足如下條件：

同時，如果任務(wù)τi是在截止期Di時刻響應(yīng)，則需要的資源最少［11］，即

分區(qū)最小資源預(yù)算的方法如下：

（1）利用（8）式計算τi在Di時刻的累積負載wi（Di）。

（2）根據(jù)（10）式和（2）式計算滿足τi可調(diào)度的最小Q，記為Qi。

（3）分別計算所有任務(wù)預(yù)算需求的最小值。

（4）分區(qū)的資源預(yù)算Q＝max｛Qi｝。

3.2 最大不可搶占區(qū)

為方便敘述，將分區(qū)集看作一個對應(yīng)的虛擬任務(wù)集，則所研究的問題轉(zhuǎn)換為求該虛擬任務(wù)集中每個任務(wù)的最大不可搶占區(qū)。

任務(wù)的最大不可搶占區(qū)等于所有高優(yōu)先級任務(wù)能夠忍受的阻塞的最小值，能夠忍受的阻塞是指任務(wù)受到該長度的阻塞后依然可調(diào)度。設(shè)任務(wù)Γi′能夠承受的阻塞為βi，則

任務(wù)Γi′能忍受的阻塞為臨界時刻后i級繁忙期內(nèi)的工作能忍受的阻塞的最小值，即

工作Γik′能忍受的阻塞βik為在（（k－1）Pi，kPi］之間的wi（t）的不連續(xù)點處，處理器能提供的運行時間和累積負載Wi（t）之差的最大值為：

在確定所有任務(wù)的最大不可搶占區(qū)之前，B是未知數(shù)，無法根據(jù)（4）式求取i級繁忙期的長度Li。因此用Li的上限值來代替Li，根據(jù)可調(diào)度性的定義，這一假設(shè)不影響最終求得的最大不可搶占區(qū)的正確性。從（4）式可以看出，Li（Bi）為單調(diào)上升函數(shù)，因此將Bi的上限值代入（4）式計算，即可得Li的上限值。顯然，

同時從（12）式可得：

即可使用第1次工作Γi1′可以忍受的阻塞βi1作為Bi的上限值，代入（4）式可計算Li的上限值。如果Γi1′在Di處響應(yīng)，所需的資源最少，可以忍受最大阻塞，因此有：

最大不可搶占區(qū)算法如下：

（1）根據(jù)（16）式，計算出?！鋓可以忍受的阻塞的上限值βi1。

（2）令Bi＝βi1，根據(jù)（4）式計算出i級繁忙期的上限Li。

（3）令Ki＝Li/Pi，根據(jù)（13）式計算出第k次工作可以忍受的最大阻塞，k∈｛［1，Ki］∩N＋｝ 。

（4）通過（12）式，求得?！鋓可以忍受的最大阻塞βi。

（5）對所有任務(wù)運行步驟（1）～步驟（4），求得每個任務(wù)可以忍受的最大阻塞。

（6）根據(jù)（11）式，求得每個任務(wù)的最大不可搶占區(qū)X。

4 仿真分析

定義u＝C/T為任務(wù)的處理器利用率；U為系統(tǒng)的處理器利用率；等于所有任務(wù)利用率之和，即U＝∑u。本文采用UUniFast算法［12］，根據(jù)給定的系統(tǒng)處理器利用率U生成m個任務(wù)集，再分別根據(jù)每個任務(wù)集的處理器利用率，使用該算法生成不超過n個任務(wù)；分區(qū)的周期P取分區(qū)內(nèi)周期最小任務(wù)的周期的1/4，采用分區(qū)最小資源預(yù)算算法求得Q和X。任務(wù)的運行時間C為50～150的隨機數(shù)，周期通過T＝C/u計算得到。對于每個選定的U，運行以上系統(tǒng)生成算法1 000次，即生成1 000個總處理器利用率為U的使用延遲搶占分區(qū)模型的2層調(diào)度系統(tǒng)。

分別在分區(qū)級采用限制搶占調(diào)度（limited preemption scheduling，LPS）和完全可搶占調(diào)度（fully preemptive scheduling，F(xiàn)PS）策略，仿真運行所生成的每個系統(tǒng)100 000個時間單位，并對比所發(fā)生的分區(qū)級搶占（partition preemption，PP）和任務(wù)級搶占（task preemption，TP）的均值。分區(qū)級搶占指一個分區(qū)在不可搶占區(qū)結(jié)束后仍然有預(yù)算，并且有可執(zhí)行的任務(wù)的狀態(tài)下被更高優(yōu)先級的分區(qū)搶占。任務(wù)級搶占指發(fā)生在一個分區(qū)內(nèi)部高優(yōu)先級任務(wù)對低優(yōu)先級任務(wù)的搶占。

在U＝0.3，m、n取不同值時的實驗結(jié)果如圖2所示，圖2中，m分別為6、4、2，n分別為7、5、3。從圖2可以看出，引入不可搶占區(qū)極大地降低了分區(qū)級搶占的次數(shù)，這正是采用延遲搶占分區(qū)模型所期待的結(jié)果。同時，任務(wù)級搶占的次數(shù)也有較明顯的減少，這是因為在分區(qū)A運行于不可搶占區(qū)時，高優(yōu)先級分區(qū)B內(nèi)可能釋放了多次工作，如果優(yōu)先級低的工作在優(yōu)先級高的工作之前釋放，在完全可搶占調(diào)度下會發(fā)生任務(wù)級搶占，但在延遲搶占分區(qū)模型中，B內(nèi)的任務(wù)調(diào)度在這幾個工作都釋放之后才被允許進行，此時高優(yōu)先級工作最先被調(diào)度運行，這幾個工作之間的搶占也就被消除了。改變U的取值實驗結(jié)果與圖2相同。

圖2 U＝0.3時搶占次數(shù)的對比

5 結(jié)束語

本文針對復(fù)雜實時軟件系統(tǒng)中的2層調(diào)度框架，提出延遲搶占分區(qū)模型，通過在分區(qū)中設(shè)置不可搶占區(qū)，減少了大量不必要搶占，降低了由此引起的運行環(huán)境切換次數(shù)及處理器資源的損失。

［1］Di Natale M，Sangiovanni－Vincentelli A L.Moving from federated to integrated architectures in automotive：the role of standards，methods and tools［J］.Proc of the IEEE，2010，98（4）：603－620.

［2］李傳斌，嚴 剛，劉夢陽，等.FlexRay－CAN網(wǎng)關(guān)中的多隊列消息處理方法［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2011，34（1）：28－32.

［3］陳 康，黃彩虹，何明華.基于工控單片機的嵌入式操作系統(tǒng)核心的設(shè)計［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2010，33（11）：1639－1642.

［4］Deng Z，Liu J W S.Scheduling real－time applications in an open environment［C］//Proc of 18th IEEE Real－Time Systems Symp.San Francisco，CA：IEEE，1997：308－319.

［5］楊 霞，熊光澤，桑 楠，等.Hades高可信架構(gòu)中固定延遲分區(qū)實時調(diào)度 ［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2009，21（11）：1682－1688.

［6］Lorente J L，Palencia J C.An EDF hierarchical scheduling model for bandwidth servers［C］//Proc of 12th IEEE Int Conf on Embedded and Real－Time Computing Systems and Applications.Sydney，Qld：IEEE，2006：261－266.

［7］Davis R I，Burns A.Hierarchical fixed priority pre－emptive scheduling［C］//Proc of 26th IEEE Int Real－Time Systems Symp.Miami，F(xiàn)L：IEEE，2005：389－398.

［8］Zhang F X，Burns A.Analysis of hierarchical EDF pre－emptive scheduling ［C］//Proc of 28th IEEE Int Real－Time Systems Symp.Tucson，AZ：IEEE，2007：423－434.

［9］Mok A K，Xiang F，Chen D.Resource partition for real－time systems［C］//Proc of IEEE Real－Time Technology and Applications Symp.Taipei：IEEE，2001：75－84.

［10］Shin I，Lee I.Compositional real－time scheduling framework with periodic model［J］//ACM Trans on Embedded Computing Systems，2008，7（3）：1－39.

［11］Almeida L，Pedreiras P.Scheduling within temporal partitions：response－time analysis and server design［C］//Proc of 4th ACM Int Conf on Embedded Software.New York，NY：ACM，2004：95－103.

［12］Bini E，Buttazzo G.Measuring the performance of schedulability tests ［J］.Real－Time Systems，2005，30（1/2）：129－152.