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

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

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

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

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

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

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

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

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

3)優(yōu)先級驅(qū)動。可以說，在實時操作系統(tǒng)領域，優(yōu)先級驅(qū)動調(diào)度算法的應用遠遠超過其他兩類調(diào)度算法。優(yōu)先級驅(qū)動調(diào)度算法根據(jù)任務的優(yōu)先級在就緒隊列中提取最高優(yōu)先級的任務進行運行。

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

對于固定優(yōu)先級調(diào)度算法，最有名的要數(shù)速率單調(diào)(Rate－Monotonic，簡稱RM)和時限單調(diào)(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調(diào)度，調(diào)度過程可以安排成如圖3所示:

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

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

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

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

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

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

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

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

對于分區(qū)調(diào)度系統(tǒng)，分區(qū)調(diào)度等價于處理器運行在由分區(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ù)。可以看出B0(αk)和ηk都是αk的遞增函數(shù)，因此有:

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

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

本部分通過一個實例詳細分析它們之間的關系。該實例由4個分區(qū)構成，利用率分別為0.25，0.15，0.27，0.03，總利用率ρ=0.7。總利用率需要小于等于1，如下式所示。

分區(qū)內(nèi)采用速率單調(diào)調(diào)度算法。每個分區(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)，且

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

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

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

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

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

4 結(jié)束語

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

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

(責任編輯周江川)

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］.四川兵工學報，2014(7):125－127.

10.11809/scbgxb2014.07.035

2014－01－27

航空基金(20100718004)。

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

TP3－05