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

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

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

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

1 分區(qū)調度機制分析

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

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

采用時鐘驅動調度，調度過程可以安排成如圖1所示。

圖1 時鐘驅動調度

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

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

圖2 時間片任務調度圖

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

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

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

對于任務集:

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

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

采用RM調度，調度過程可以安排成如圖3所示:

圖3 速率單調調度

2 分區(qū)調度理論

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

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

定義3:如果一個調度算法能夠產生一個有效調度，則稱該任務集S在該調度算法下可調度。

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

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

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

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

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

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

3 實例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結束語

為了對分區(qū)系統(tǒng)進行分析，本文論述了分區(qū)系統(tǒng)的調度機制和理論，并進行數學分析。分區(qū)系統(tǒng)的調度采用兩級調度機制，操作系統(tǒng)級負責分區(qū)的調度，分區(qū)級負責分區(qū)內任務的調度。分區(qū)內系統(tǒng)的調度可以采用通用的調度機制，如速率單調，時限優(yōu)先等等。并在論述中分析各參數之間的關系。

［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，Frank 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.

(責任編輯周江川)

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ū)調度理論研究與分析［J］.四川兵工學報，2014(7):125－127.

10.11809/scbgxb2014.07.035

2014－01－27

航空基金(20100718004)。

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

TP3－05