基于μC/OS-Ⅱ的实时分层调度算法研究

0引言

嵌入式实时系统由于自身CPU计算能力较弱和内存容量较低的原因，希望采用复杂度低、系统开销小的调度算法。目前的实时系统通常采用单优先级驱动的抢占式调度算法，根据任务的某一时间特性参数如任务周期或最后截止期等为各个任务分配系统资源[1][2]。这种抢占式调度策略具有灵活性和动态性等优点。但在，实际应用系统中也有一些由不相交的周期任务子集组成，每个子集是系统的一个主要部分，称之为子系统。例如，飞行管理系统包含飞行控制，电子设备和导航式三个子系统。这三个子系统的任务如果按照以前的静态、动态算法实现需要系统开发人员设计很复杂的调度算法，实时控制也相对困难[3][4]。本文按照分层思想在实时操作系统层面上设计调度算法，减轻了解决此类问题系统开发人员的负担，算法的主要思想是：修改内核的任务控制块，增加一个子模块标识来控制分层调度，采用固

定时间轮转算法调度各子系统模块，子系统中的任务按照速率单调算法调度，从而实现两层的调度策略。本文首先定义了分层调度系统的模型，并对分层调度算法的可调度性进行了理论分析；其次，以实时内核μC/OS-Ⅱ为背景，实现了具有分层调度功能的调度器，最后通过实验验证分层调度算法的可行性和正确性。

1 分层调度系统模型的定义

定义1 在不考虑释放抖动的情况下，一个任务集Τ={τ1,τ2,…, τn}中的任务τi 的属性可以用一个五元组（Mi， ,Pi,Di, Ei）来表示。其中，Mi 表示任务属于的模块； 是相位；Pi 表示任务周期，对于非周期任务，取其最小时间间隔作为周期；Di 表示任务完成

的最后期限；Ei 表示任务的最大请求运行时间。

在定义任务属性时，扩展以前任务描述的四元组到五元组[5]，增加了任务所属模块的属性，这一点是为了给子模块的索引表提供一个标志，以便实现任务集按子模块分层调度管理。

定义2 对于任务τi，其各实例从到达时刻至执行完成时刻之间的时间间隔称为该实例的响应时间,各实例响应时间的最大值称为任务τi的最大响应时间 Ri，若 Ri≤Di，则称任务τi可调度。

2 分层调度算法模型的实现

2．1分层模型的可调度性分析

假定：系统中具有n个独立的，可抢占的任务，并且任务的相对时限等于各自的周期。如果系统的总利用率U满足下式：

(该子系统模块1中的任务在最坏的情况下，完成任务的时间分别为：
R11=RL-1+E1=2+0.5=2.5
R12=2*RL-1-(1-E1)+E2=5-0.5+1.2=5.7
R13=3*RL-1-(2-E1-E2)+E3+E1=9-1-0.3+0.8-0.5=9

而按照分层模型可调度性公式(2.2a)迭代计算可知Rij最大响应时间分别如下：

R11(max):初始预设值为t(1)=0.5（即任务的执行时间）,用该值替代t，发现公式(2.2a)左边等于0.5，但右边为0，不满足公式(2.2a),第二次迭代中，t(2)＝ =3,经计算发现针对该t值，公式(2.2a)成立，因此T11的最大响应时间为3，依次可计算第一个子模块中其它两个任务的最大响应时间分别为 R12(max)＝6，R13(max)＝9。

由此可知系统在分层调度情况下，子模块M1中的任务最坏情况下的调度能在最大响应时间内运行完毕。同理，对其它2个模块中的任务逐个检验它的可调度条件，可判别出子系统模块中的任务在最坏情况下的调度能满足最大响应时间的要求，从而保证分层情况下任务的可调度性。

2．2 实现分层调度的μC/OS-Ⅱ内核结构修改和扩展

为了实现分层调度，需要修改和扩展μC/OS-Ⅱ内核结构。创建一个模块控制块MCB，以此作为模块标识，将属于同一模块的任务TCB挂在同一模块任务链上，在调度过程中，子模块按固定时间轮转调度，子模块中任务的调度仍然保持μC/OS-Ⅱ按优先级的抢占式调度策略按RM调度算法进行。为实现分层任务的级联查找，需要创建两级索引表，一级指向子模块，另一级索引子模块中的任务，原内核结构如图2所示，改进后的内核结构如图3所示。

具体的调度算法如下 ：
OS_Layered_Sched(){
OSMCBRdy = "Get a ready submode";/* 控制块就绪指针指向一个子模块*/
if ( OSMCBGetCycle_Piece = =ture ) {/*子模块得到固定时间分配。*/
if (MCBTb[].TaskTcb[].Rdy==ture) /*查看其中是否有就绪的任务，如果有，则调度*/
{OS_ENTER_CRITICAL();
OS_PRIOCYCLE_RDY =(INT8U)(z+(y<<3+)+OS_UnMapTb1[OSRdyTb1[y]];
 /* z是用来确定模块的地址*/     OS_sched(); 
OS_EXIT_CRITICAL()}
else {
   if( MCBTb!= MCBTb[n]) /*判断是否到了最后一个子模块*/
{ MCBTb= MCBTb->next;  }/*是，指向下一个子模块，否，指针回到第一个子模块*/
Else
{ MCBTb = MCBTb[1] }
}
}

3、实验仿真及结果分析

移植μC/OS- Ⅱ实时操作系统到PC机上，以BC++4.5为开发平台，完成分层调度算法下任务的调度执行，结果如图4所示。

实验结果显示，改进后的算法可以实现分层子模块中任务的调度，调度器运转正常，证明了分层调度算法的可行性。在执行多次后，如有任务完成，它就脱离原来的链，重新调整两级索引表，并按调整后的两级索引表引起新的调度。

本算法存在的问题是任务切换的频繁次数增加，增大了调度的时间开销，表1是对图1的任务集在分层前后的调度运行时任务切换次数的比较。

表1 分层调度前、后的任务切换次数对比分析表

4、结束语

本文作者创新点：通过重构μC/OS-Ⅱ内核结构和改进其调度器，达到了μC/OS-Ⅱ支持分层调度的设计目标，其调度功能得到了扩展和加强。改进的μC/OS-Ⅱ内核支持两级的分层调度，在不改变原μC/OS-Ⅱ内核抢占式内核特征下实现了子系统模块的固定时间分配方案的调度策略，使得μC /OS-Ⅱ内核有能力支撑更为复杂的实时应用。理论分析和实验认证证明了扩展μC/OS-Ⅱ内核功能方法的正确性和有效性。

参考文献：
[1]WilliamL.Preemption-threshold. White Paper[Z].Express Logic Inc. 1992.
[2] Wang Y, Saksena M. Scheduling Fixed Priority Tasks with PreemptionThreshold[C]. Proceeding of 6th IEEE Real-time Computing Systemsand Applications Symposium, Hong Kong, 1999: 328-335.
[3]杨博，陈志刚. 一种基于双层进化结构的网格任务调度算[J].计算机工程与应用, 2006(15):4-7.
[4]刘卫，程明霄王晓荣. 实时系统优先级位图调度算法的改进[J].微计算机信息程,2007,23(2):155-157.
[5] Mok,A.K.-L.,and D.Chen,“A multiframe model for real-time,”Proceedings of IEEE Real-time Systems Symposium,December, 1996.