电子系统分区调度理论研究与分析

通过对分区调度机制进行了分析，并对分区调度理论进行了研究，为确定分区的周期和容限提供了理论依据。在此基础上，进行了推理实例分析;实验表明:当任务的执行时间减小，曲线向左移动，则在更小的时间容限或更大的分区周期下分区仍然可调度。

分区调度机制;周期;实例分析;执行时间;分区周期

1 分区调度机制分析

分区系统的调度采用两级调度机制，操作系统级负责分区的调度，分区级负责分区内任务的调度。分区内系统的调度可以采用通用的调度机制，如速率单调，时限优先等等。目前在实时系统中常用的调度算法有以下方式。

1)时钟驱动。时钟驱动调度主要用来调度周期任务，任务由四元组表示:其中分别表示为任务的相位，周期，执行时间以及任务时限。任务调度器由时钟Tick触发，任务的调度根据任务的相位和周期决定触发。对于非周期任务可以采用松弛借用的方法在周期任务调度的空闲时间调度。对于任务集:

采用时钟驱动调度，调度过程可以安排成如图1所示。

图1 时钟驱动调度

2)处理器共享。处理器共享调度算法的主要目的是最大限度的共享处理器资源。在商用操作系统或桌面操作系统中，使用较多的处理器共享调度算法是时间片轮转。

时间片轮转调度把CPU分配给就绪队列中的第一个进程，并保持quantum个时间单元，quantum是时间量。在quantum个时间单元之后，如果进程没有放弃CPU，那么它将被抢占并被置于就绪队列尾部。时间片轮转算法主要的问题是时间量的选择。如果采用quantum=4的时间片轮转调度算法，任务的调度图如图2所示。

图2 时间片任务调度图

3)优先级驱动。可以说，在实时操作系统领域，优先级驱动调度算法的应用远远超过其他两类调度算法。优先级驱动调度算法根据任务的优先级在就绪队列中提取最高优先级的任务进行运行。

优先级驱动调度算法分为2种，动态优先级和固定优先级。对于动态优先级调度算法，最有名的要数最早时限优先算法，该算法将时限最接近当前时间的任务设置为最高优先级。

对于固定优先级调度算法，最有名的要数速率单调(Rate－Monotonic，简称RM)和时限单调(Deadline－Monotonic，简称DM)算法。对于多处理器系统，DM和RM都不是最优算法。

对于任务集:

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

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

采用RM调度，调度过程可以安排成如图3所示:

图3 速率单调调度

2 分区调度理论

定义1:如果每个任务的每个请求时限在一个调度S下都能得到满足，则称调度S对于这个实时系统的任务集为有效调度。

定义2:对于一个任务集，如果存在一个有效调度，则称该任务集为可行的。

定义3:如果一个调度算法能够产生一个有效调度，则称该任务集S在该调度算法下可调度。

定理1:如果实时任务集由n个任务组成，每个任务的相对死线等于周期，该实时任务集由DM或RM可调度，如果ρk≤n(21/n－1)，则≈ln2=0.69，因此如果一个任务集采用速率单调调度算法，则当系统利用率小于0.69时，任务集一定可调度。图4给出在速率单调算法下，任务数和系统可调度的利用率之间的关系图。虽然当系统利用率小于0.69时，任务集一定可调度。但是如果已知任务数，可以通过该图得到具体的利用率约束。如当任务数为6时，利用率的上限为0.734 8。

定义5:文献［103，104］给出了通用系统的调度需求为

其中任务按照优先级排序τ1＜τ2＜…＜τn，Wi(t)给出一个处理器在［0，t］区间的累积需求。

对于分区调度系统，分区调度等价于处理器运行在由分区容限αk为因子的专用处理器上。类似的定义分区系统的调度需求:

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

定理2:分区系统处理器可调度充要条件为Wi(αk，t)≤t。

3 实例分析

为了满足分区的调度，需要提供什么样的分区周期和容限，从而为确定分区的周期和容限提供了理论依据。可以看出B0(αk)和ηk都是αk的递增函数，因此有:

推理1分区容限αk与最小未激活周期B0(αk)符合如下关系:

推理2如果增大分区容限，满足可调度的分区调度周期也可以增大。

本部分通过一个实例详细分析它们之间的关系。该实例由4个分区构成，利用率分别为0.25，0.15，0.27，0.03，总利用率ρ=0.7。总利用率需要小于等于1，如下式所示。

分区内采用速率单调调度算法。每个分区由多个周期任务组成，周期任务的周期等于其时限，如表1所示。

表1 分区及任务表

图4给出了表1给出的任务集对应的分区容限α与最小未激活周期的关系。由图4可以看出，当分区容限α稍微大于分区的利用率时，由于分区中最低优先级的任务刚刚满足其时限，因此拥有非常小的最小未激活周期。

图4 分区容量与最小末激活周期的关系

图5 显示了对于上表显式的4分区系统的分区容限αk与最大分区周期ηk的关系。由图可以看出该系统的一个可行(αk，ηk)分配为(0.32，36)，(0.28，59)，(0.34，28)，(0.06，57)，且

如果调整分区1的任务时限D，可以得到在不同时限下的分区容限αk与最大分区周期ηk的关系图，如图6所示。可以看出，随着时限的缩小，曲线向右移动。因此为了满足系统的可调度性，需要要么增大分区的时间容限αk或缩小分区的调度周期(增大调度频率)。

图5 分区容量αk与最大分区周期ηk的关系

图6 不同时限D下分区1的容量αk与最大分区周期ηk关系

如果由于系统升级或程序优化使得分区中任务的执行时间C缩小，这种执行时间的变化将直接反映在分区利用率ρk上。图7给出了在不同利用率下容限αk与最大分区周期ηk的关系图。由图可以看出，当任务的执行时间减小，曲线向左移动，则在更小的时间容限或更大的分区周期下分区仍然可调度。

图7 不同利用率分区1容量αk与最大分区周期ηk

4 结束语

为了对分区系统进行分析，本文论述了分区系统的调度机制和理论，并进行数学分析。分区系统的调度采用两级调度机制，操作系统级负责分区的调度，分区级负责分区内任务的调度。分区内系统的调度可以采用通用的调度机制，如速率单调，时限优先等等。并在论述中分析各参数之间的关系。

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

本文引用格式:殷锋社，汤小明.电子系统分区调度理论研究与分析［J］.四川兵工学报，2014(7):125－127.

10.11809/scbgxb2014.07.035

2014－01－27

航空基金(20100718004)。

殷锋社(1976—)，男，硕士研究生，副教授，主要从事计算机智能化研究。

TP3－05