電子系統(tǒng)分區(qū)調(diào)度理論研究與分析

通過對分區(qū)調(diào)度機(jī)制進(jìn)行了分析，并對分區(qū)調(diào)度理論進(jìn)行了研究，為確定分區(qū)的周期和容限提供了理論依據(jù)。在此基礎(chǔ)上，進(jìn)行了推理實例分析;實驗表明:當(dāng)任務(wù)的執(zhí)行時間減小，曲線向左移動，則在更小的時間容限或更大的分區(qū)周期下分區(qū)仍然可調(diào)度。

分區(qū)調(diào)度機(jī)制;周期;實例分析;執(zhí)行時間;分區(qū)周期

1 分區(qū)調(diào)度機(jī)制分析

分區(qū)系統(tǒng)的調(diào)度采用兩級調(diào)度機(jī)制，操作系統(tǒng)級負(fù)責(zé)分區(qū)的調(diào)度，分區(qū)級負(fù)責(zé)分區(qū)內(nèi)任務(wù)的調(diào)度。分區(qū)內(nèi)系統(tǒng)的調(diào)度可以采用通用的調(diào)度機(jī)制，如速率單調(diào)，時限優(yōu)先等等。目前在實時系統(tǒng)中常用的調(diào)度算法有以下方式。

1)時鐘驅(qū)動。時鐘驅(qū)動調(diào)度主要用來調(diào)度周期任務(wù)，任務(wù)由四元組表示:其中分別表示為任務(wù)的相位，周期，執(zhí)行時間以及任務(wù)時限。任務(wù)調(diào)度器由時鐘Tick觸發(fā)，任務(wù)的調(diào)度根據(jù)任務(wù)的相位和周期決定觸發(fā)。對于非周期任務(wù)可以采用松弛借用的方法在周期任務(wù)調(diào)度的空閑時間調(diào)度。對于任務(wù)集:

采用時鐘驅(qū)動調(diào)度，調(diào)度過程可以安排成如圖1所示。

圖1 時鐘驅(qū)動調(diào)度

2)處理器共享。處理器共享調(diào)度算法的主要目的是最大限度的共享處理器資源。在商用操作系統(tǒng)或桌面操作系統(tǒng)中，使用較多的處理器共享調(diào)度算法是時間片輪轉(zhuǎn)。

時間片輪轉(zhuǎn)調(diào)度把CPU分配給就緒隊列中的第一個進(jìn)程，并保持quantum個時間單元，quantum是時間量。在quantum個時間單元之后，如果進(jìn)程沒有放棄CPU，那么它將被搶占并被置于就緒隊列尾部。時間片輪轉(zhuǎn)算法主要的問題是時間量的選擇。如果采用quantum=4的時間片輪轉(zhuǎn)調(diào)度算法，任務(wù)的調(diào)度圖如圖2所示。

圖2 時間片任務(wù)調(diào)度圖

3)優(yōu)先級驅(qū)動?？梢哉f，在實時操作系統(tǒng)領(lǐng)域，優(yōu)先級驅(qū)動調(diào)度算法的應(yīng)用遠(yuǎn)遠(yuǎn)超過其他兩類調(diào)度算法。優(yōu)先級驅(qū)動調(diào)度算法根據(jù)任務(wù)的優(yōu)先級在就緒隊列中提取最高優(yōu)先級的任務(wù)進(jìn)行運(yùn)行。

優(yōu)先級驅(qū)動調(diào)度算法分為2種，動態(tài)優(yōu)先級和固定優(yōu)先級。對于動態(tài)優(yōu)先級調(diào)度算法，最有名的要數(shù)最早時限優(yōu)先算法，該算法將時限最接近當(dāng)前時間的任務(wù)設(shè)置為最高優(yōu)先級。

對于固定優(yōu)先級調(diào)度算法，最有名的要數(shù)速率單調(diào)(Rate－Monotonic，簡稱RM)和時限單調(diào)(Deadline－Monotonic，簡稱DM)算法。對于多處理器系統(tǒng)，DM和RM都不是最優(yōu)算法。

對于任務(wù)集:

τ1={0，4，1，4}，τ2={0，5，2，5}

τ3={0，10，2，10}，τ4={0，20，1，20}

采用RM調(diào)度，調(diào)度過程可以安排成如圖3所示:

圖3 速率單調(diào)調(diào)度

2 分區(qū)調(diào)度理論

定義1:如果每個任務(wù)的每個請求時限在一個調(diào)度S下都能得到滿足，則稱調(diào)度S對于這個實時系統(tǒng)的任務(wù)集為有效調(diào)度。

定義2:對于一個任務(wù)集，如果存在一個有效調(diào)度，則稱該任務(wù)集為可行的。

定義3:如果一個調(diào)度算法能夠產(chǎn)生一個有效調(diào)度，則稱該任務(wù)集S在該調(diào)度算法下可調(diào)度。

定理1:如果實時任務(wù)集由n個任務(wù)組成，每個任務(wù)的相對死線等于周期，該實時任務(wù)集由DM或RM可調(diào)度，如果ρk≤n(21/n－1)，則≈ln2=0.69，因此如果一個任務(wù)集采用速率單調(diào)調(diào)度算法，則當(dāng)系統(tǒng)利用率小于0.69時，任務(wù)集一定可調(diào)度。圖4給出在速率單調(diào)算法下，任務(wù)數(shù)和系統(tǒng)可調(diào)度的利用率之間的關(guān)系圖。雖然當(dāng)系統(tǒng)利用率小于0.69時，任務(wù)集一定可調(diào)度。但是如果已知任務(wù)數(shù)，可以通過該圖得到具體的利用率約束。如當(dāng)任務(wù)數(shù)為6時，利用率的上限為0.734 8。

定義5:文獻(xiàn)［103，104］給出了通用系統(tǒng)的調(diào)度需求為

其中任務(wù)按照優(yōu)先級排序τ1＜τ2＜…＜τn，Wi(t)給出一個處理器在［0，t］區(qū)間的累積需求。

對于分區(qū)調(diào)度系統(tǒng)，分區(qū)調(diào)度等價于處理器運(yùn)行在由分區(qū)容限αk為因子的專用處理器上。類似的定義分區(qū)系統(tǒng)的調(diào)度需求:

t∈Hi=lTj|j=1，2，…，i;l=1，2，…，?Di/Tj{ }」

定理2:分區(qū)系統(tǒng)處理器可調(diào)度充要條件為Wi(αk，t)≤t。

3 實例分析

為了滿足分區(qū)的調(diào)度，需要提供什么樣的分區(qū)周期和容限，從而為確定分區(qū)的周期和容限提供了理論依據(jù)?？梢钥闯鯞0(αk)和ηk都是αk的遞增函數(shù)，因此有:

推理1分區(qū)容限αk與最小未激活周期B0(αk)符合如下關(guān)系:

推理2如果增大分區(qū)容限，滿足可調(diào)度的分區(qū)調(diào)度周期也可以增大。

本部分通過一個實例詳細(xì)分析它們之間的關(guān)系。該實例由4個分區(qū)構(gòu)成，利用率分別為0.25，0.15，0.27，0.03，總利用率ρ=0.7?？偫寐市枰∮诘扔?，如下式所示。

分區(qū)內(nèi)采用速率單調(diào)調(diào)度算法。每個分區(qū)由多個周期任務(wù)組成，周期任務(wù)的周期等于其時限，如表1所示。

表1 分區(qū)及任務(wù)表

圖4給出了表1給出的任務(wù)集對應(yīng)的分區(qū)容限α與最小未激活周期的關(guān)系。由圖4可以看出，當(dāng)分區(qū)容限α稍微大于分區(qū)的利用率時，由于分區(qū)中最低優(yōu)先級的任務(wù)剛剛滿足其時限，因此擁有非常小的最小未激活周期。

圖4 分區(qū)容量與最小末激活周期的關(guān)系

圖5 顯示了對于上表顯式的4分區(qū)系統(tǒng)的分區(qū)容限αk與最大分區(qū)周期ηk的關(guān)系。由圖可以看出該系統(tǒng)的一個可行(αk，ηk)分配為(0.32，36)，(0.28，59)，(0.34，28)，(0.06，57)，且

如果調(diào)整分區(qū)1的任務(wù)時限D(zhuǎn)，可以得到在不同時限下的分區(qū)容限αk與最大分區(qū)周期ηk的關(guān)系圖，如圖6所示?？梢钥闯觯S著時限的縮小，曲線向右移動。因此為了滿足系統(tǒng)的可調(diào)度性，需要要么增大分區(qū)的時間容限αk或縮小分區(qū)的調(diào)度周期(增大調(diào)度頻率)。

圖5 分區(qū)容量αk與最大分區(qū)周期ηk的關(guān)系

圖6 不同時限D(zhuǎn)下分區(qū)1的容量αk與最大分區(qū)周期ηk關(guān)系

如果由于系統(tǒng)升級或程序優(yōu)化使得分區(qū)中任務(wù)的執(zhí)行時間C縮小，這種執(zhí)行時間的變化將直接反映在分區(qū)利用率ρk上。圖7給出了在不同利用率下容限αk與最大分區(qū)周期ηk的關(guān)系圖。由圖可以看出，當(dāng)任務(wù)的執(zhí)行時間減小，曲線向左移動，則在更小的時間容限或更大的分區(qū)周期下分區(qū)仍然可調(diào)度。

圖7 不同利用率分區(qū)1容量αk與最大分區(qū)周期ηk

4 結(jié)束語

為了對分區(qū)系統(tǒng)進(jìn)行分析，本文論述了分區(qū)系統(tǒng)的調(diào)度機(jī)制和理論，并進(jìn)行數(shù)學(xué)分析。分區(qū)系統(tǒng)的調(diào)度采用兩級調(diào)度機(jī)制，操作系統(tǒng)級負(fù)責(zé)分區(qū)的調(diào)度，分區(qū)級負(fù)責(zé)分區(qū)內(nèi)任務(wù)的調(diào)度。分區(qū)內(nèi)系統(tǒng)的調(diào)度可以采用通用的調(diào)度機(jī)制，如速率單調(diào)，時限優(yōu)先等等。并在論述中分析各參數(shù)之間的關(guān)系。

［1］John R，Alastair R，Kirk W.Eliminating stack overflow byAbstractinterpretation［J］.ACM Transactions on Embedded Computing Systems(TECS)，2005(4):751－778.

［2］Justin Littlefield－Lawwill，Ramanathan Viswanathan.Advancing Open Standards in Integrated Modular Avionics:An Industry Analysis［J］.26th Digital Avionics Systems Conference(DASC)，2007(2).

［3］HQ AFMC/ENPI.Air Force Open Systems Implementation Guide(DRAFT)［M］.1997.

［4］Logan G T.Integrated Avionics:Past，Present and Future［J］.Aerospace and Electronic Systems Magazine，2007 (22):39－40.

［5］FAA Technical Standard Oder TSO－C153.Integrated Modular Avionics Hardware Elements［M］.2002.

［6］Muhammad M.Latif，RaviRamaseshan，F(xiàn)rank Mueller.Soft Error Protection via Fault－Resilient Data Representations［M］.In Proc.3rd IEEEWorkshop on Silicon Errors，2009.

［7］Federal Aviation Adinistration.Guidance for Integrated Modular Avionics(IMA)That Implement TSO－C153 Authorized Hardware Elements［D］.FAA Advisory Circular AC，2003:20－145.

(責(zé)任編輯周江川)

Research and Analysis of Electronic System Partition Scheduling Theory

YIN Feng－she1，TANG Xiao－ming2
(1.Shaanxi Polytechnic Institute，Xianyang 712000，China;
2.AVIC Xi’an Flight Automatic Control Research Institute，Xi’an 710075，China)

Based on the partition scheduling mechanism，the partition scheduling theory was studied.In order to determine the partition of the cycle and provide a theoretical basis for tolerance，the reasoning analysiswas carried.Experiments show that，when the task execution time decreases，curve shiftingmoves to the left，then tolerance or larger partition cycle in smaller time division still can dispatch.

partition schedulingmechanism;cycle;case analysis;execution time;division cycle

:A

1006－0707(2014)07－0125－03

format:YIN Feng－she，TANG Xiao－ming.Research and Analysis of Electronic System Partition Scheduling Theory［J］.Journal of Sichuan Ordnance，2014(7):125－127.

本文引用格式:殷鋒社，湯小明.電子系統(tǒng)分區(qū)調(diào)度理論研究與分析［J］.四川兵工學(xué)報，2014(7):125－127.

10.11809/scbgxb2014.07.035

2014－01－27

航空基金(20100718004)。

殷鋒社(1976—)，男，碩士研究生，副教授，主要從事計算機(jī)智能化研究。

TP3－05