双参数模糊调度在实时控制系统中的应用

沈  青^{1, 2}，桂卫华¹，熊  英¹，阳春华¹

(1. 中南大学 信息科学与工程学院，湖南 长沙，410083；

2. 国防科学技术大学 指挥军官基础教育学院，湖南 长沙，410003)

摘  要：针对嵌入式多任务实时控制系统，提出模糊调度设计(FSD)算法。该算法基于任务重要性和空闲时间2个特征参数，动态调整任务优先级，使得空闲时间越短且越重要的任务，其优先级越高。FSD算法在资源有限时可以提高关键任务的可调度性和控制性能，在不同系统负载下，通过灵活的模糊调度规则获得满意的系统可调度性能。为评估调度算法，定义性能指标I_VR为任务价值总和与任务重要性之和的比值，若I_VR越大，则系统可调度性越好。仿真结果表明：在正常负载下，FSD算法在保证关键任务可调度性的同时，对非关键任务的可调度性影响较小，任务调度成功率比MIX(加权组合)算法的高；超载时，FSD算法优先保证关键任务在其截止期内完成，避免EDF(截止期优先)算法中易出现的多米诺现象发生，有效提高系统的整体性能。

关键词：控制任务；实时系统；模糊调度；任务优先级

中图分类号：TP273         文献标识码：A         文章编号：1672-7207(2009)02-0441-06

Application of fuzzy scheduling with two characteristic parameters for real-time control systems

SHEN Qing^{1, 2}, GUI Wei-hua¹, XIONG Ying¹, YANG Chun-hua¹

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;

2. School of Basic Education for Officers, National University of Defense Technology, Changsha 410003, China)

Abstract: A FSD (Fuzzy scheduling design) algorithm was presented focusing on the embedded multi-task real-time control systems, the scheduling decision was conduced based on both the importance value and the slack of the tasks, the task priority was dynamically changed such that the slack was shorter or the task was more important, and the priority was higher. The critical tasks’ control index and schedulability were improved within limited resource by FSD algorithm, and the satisfied schedulability of the system was obtained under different workloads by the flexible fuzzy scheduling rules. The performance of the scheduling algorithm I_VR was evaluated by computing the ratio of the cumulative value to the cumulative importance value gained on a task set, and the higher the I_VR was, the better the system’s schedulability was. Simulation results show that, with the proposed FSD algorithm, the influence on the non-critical tasks’ schedulability is smaller during the guarantee of the critical tasks’ schedulability under normal workload, besides, a higher succeeding ratio of task scheduling is achieved compared with that using MIX (Mixed rules) algorithm. Moreover, FSD algorithm guarantees the critical tasks to be completed by their deadlines, avoids the so called domino effect which usually appears in EDF (Earliest deadline first) policy and improves the efficiency of the overall system performance under overload condition.

Key words: control tasks; real-time systems; fuzzy scheduling; task priority

嵌入式多任务实时控制系统中实时调度是对任务执行过程中占用处理器时间及其他资源进行分配，满足控制任务的截止时间和相应的性能指标^[1-2]。通常嵌入式控制系统中各个调度对象的重要性并不相同，对关键任务，要求其任务作业必须在其规定的截止期内完成，否则有可能导致系统运行失败^[3-5]。经典调度算法通常由任务的1个特征参数来确定任务的优先级，如，EDF(Earliest deadline first)^[6-7]策略将最高优先级指派给截止期最早的任务，LSF(Least slack first)^[8]策略将最高优先级指派给空闲时间最短的任务，尽管在正常的系统负载下这些算法均具有最优性，但是，在超载^[9-10]情况下，系统性能严重降低，使得关键任务失去可调度性，造成嵌入式计算机系统运行失败。考虑任务重要特性的双参数调度算法可以克服单参数调度的缺陷，通过优先执行具有最大价值或最关键的任务尽可能避免系统失效甚至崩溃情况出现。HDF(Highest density first)^[11]算法优先调度执行价值密度(任务的价值与其估计执行时间的比值)最高的任务。MIX(Mixed rules)^[11]加权组合算法通过对任务重要性和截止期2个参数进行加权求和得到优先级参数。二维优先级表算法^[12]在任务调度时综合考虑任务的截止期与价值，从而保证系统在过载情况下能够优雅地降级。这些算法在重载时能较好地保证关键任务的可调度性，但优先执行高价值的任务往往导致正常负载下重要任务仍占用较多资源，许多非关键任务不必要地错失截止期，整个系统的可调度性能降低。此外，上述双参数调度算法均未考虑对任务控制性能的影响。在此，本文作者提出一种双参数模糊调度设计算法FSD(Fuzzy scheduling design)，主要考虑基于时间触发采样的计算机控制系统，研究任务重要性和空闲时间双参数模糊单处理器调度^[13-14]设计问题，构造一个多准则优化调度方法，在正常负载下减少所有任务的截止期丢失率，提高系统的可调度性，在系统超载时保证关键任务稳定^[15]的控制性能。

1  系统模型

1.1  控制任务属性参数

n个周期实时任务集描述为(τ₁, τ₂, …, τ_n)，假定所有任务由1个处理机调度，彼此独立且可被抢占，为描述调度算法，对任务τ_i定义如下任务属性：T_i 定义为任务周期；C_i定义为最大计算时间，即处理机在无干扰情况下执行一个任务作业所需的最长执行时间；D_i定义为绝对截止时间，任务作业必须在该时间前完成才能得到正确执行结果；d_i定义为相对截止时间，即任务到达时间和绝对截止时间之间的间隔时间；R_i定义为任务τ_i在当前时刻之后的剩余执行时间，显然，R_i≤C_i；S_i定义为任务τ_i在t时刻后剩余的空闲时间，即任务在截止期D_i前完成可以等待的时间，S_i=D_i-(t+R_i)；V_i定义为任务重要程度，即在任务集中该任务与其他任务的相对重要性指标(V_i越大，则任务越重要)；f_i定义为任务完成时间，即任务完成作业执行并离开系统时刻；P_i定义为任务优先级，是任务被调度的优先指标，取决于采用的调度策略(这里，假设优先级越小, 优先级等级就越高)；M_i定义为任务截止期错失率，即未能在截止期内完成的任务作业占所有任务作业的比率。

1.2  系统性能指标设定

记一个任务为τ_i(T_i, C_i, V_i)，为评估调度算法性  能^[7]，为每个任务关联一个任务价值v_i，定义如下：

。             (1)

式(1)说明，若所有任务作业均能在其截止期内完成，M_i为0，则该任务价值为V_i，否则，任务价值小于V_i。

对实时系统任务集(τ₁, τ₂, …, τ_n)，在调度算法A下，通过累加所有任务价值得到系统总的价值，定义如下：

。              (2)

为评估调度算法，定义价值率I_VR为任务价值总和与任务重要性之和的比值。若I_VR越大，则系统可调度性越好。当I_VR=1时，系统中所有任务截止期错失率等于0，所有任务均可调度。

。             (3)

定义系统处理机利用率U(System utilization factor)，以检测不同系统负载下的调度结果。任务集可调度是指所有任务均能在其截止期内完成，任务集的处理机利用率≤1，是所有调度算法可调度的必要条件。

1.3  模糊调度系统及策略

本文提出一种新的模糊调度系统，见图1，其中，r₁, r₂, …, r_n为给定信号；u₁, u₂, …, u_n为控制信号；y₁, y₂, …, y_n为输出信号。它由模糊调度器^[16]和多个被调度的控制对象组成。模糊调度器的调度规则是基于模糊条件语句描述的语言控制规则，所以，模糊调度器又称为模糊语言调度器，它的作用是决定多个控制回路的执行优先级。

图1  模糊调度系统

Fig.1  Fuzzy scheduling system

1.3.1  控制任务调度算法及原则

a. 调度算法：

1) 对每个任务τ_i，指定任务重要性V_i。

2) 对每个新的任务作业，采集任务相关属性并计算作业空闲时间R_i，进行论域变换，把连续量R_i离散为[1, 2, 3, 4, 5]中的某一个整数。

3) 输入任务重要性V_i和当前离散任务作业空闲时间R_i到模糊调度系统，模糊调度系统输出的优先级参数P_i作为该任务当前调度的优先级。

4) 按任务优先级对任务作业进行排队，并依次执行。执行完成的任务作业将产生新的控制量，而错失最晚截止期的任务作业将不更新控制量。

b. 调度原则：

1) 任务的空闲时间越小且越重要，则任务的优先级越高。

2) 对任务优先级相同的任务，则空闲时间小者具有更高的优先级。

1.3.2  模糊调度器设计

模糊系统结构见图2，其中，有2个输入变量(I_value, I_idle)和1个输出变量(O_priority)。任务重要性(I_value)由任务特征参数V_i决定，是1个静态变量；空闲时间(I_idle)由任务特征参数R_i决定，在任务作业执行过程中是动态变化的；任务调度优先级(O_priority)决定控制任务执行的优先级顺序P_i。

图2  模糊推理结构图

Fig.2  Fuzzy inference block diagram

a. 确定输入输出模糊变量、模糊状态及论域等级。对应于任务重要性、空闲时间和任务优先级，相应的模糊状态变量分别为I_value，I_idle和O_priority，模糊状态数量选择取决于实际问题的要求，如变量性质和精度等，定义为：

I_value={low, normal, high}；

I_idle={PS, PM, PB, PL}；

O_priority={veryhigh, high, normal, low, verylow}。

每个模糊变量在其论域内可分成若干个等级，定义如下：

{I_value}={1, 2, 3}；

{I_idle}={1, 2, 3, 4, 5}；

{O_priority}={1, 2, 3, 4, 5}。

b. 确定各模糊子集的隶属函数。变量的某个定值“属于”它的某个模糊子集的程度可以用[0, 1]区间的数来表示，这个数为隶属度。任务的重要性、空闲时间和优先级的隶属函数分别如图3~5所示。

I_value: 1—low; 2—normal; 3—high

图3  任务重要性模糊集

Fig.3  Fuzzy sets corresponding to importance

I_idle: 1—PS; 2—PM; 3—PB; 4—PL

图4  任务作业空闲时间模糊集

Fig.4  Fuzzy sets corresponding to idle

O_priority: 1—veryhigh; 2—high; 3—normal; 4—low; 5—verylow

图5  任务作业优先级模糊集

Fig.5  Fuzzy sets corresponding to priority

c. 模糊调度规则。该模糊调度算法给出12条模糊调度规则，在调度规则中优先保证关键任务的可调度性。

If (I_value is high) and (I_idle is PS) then (O_priority is veryhigh)；

If (I_value is high) and (I_idle is PM) then (O_priority is veryhigh)；

If (I_value is high) and (I_idle is PB) then (O_priority is high)；

If (I_value is high) and (I_idle is PL) then (O_priority is high)；

If (I_value is normal) and (I_idle is PS) then (O_priority is high)；

If (I_value is normal) and (I_idle is PM) then (O_priority is high)；

If (I_value is normal) and (I_idle is PB) then (O_priority is normal)；

If (I_value is normal) and (I_idle is PL) then (O_priority is low)；

If (I_value is low) and (I_idle is PS) then (O_priority is high)；

If (I_value is low) and (I_idle is PM) then (O_priority is normal)；

If (I_value is low) and (I_idle is PB) then (O_priority is verylow)；

If (I_value is low) and (I_idle is PL) then (O_priority is verylow)。

d. 模糊推理决策任务优先级。由上述控制规则和隶属函数得到决策三维图，见图6，图6显示了任务调度过程中优先级计算过程，任务优先级分成5个级别，由输入参数任务空闲时间和任务重要性决定。例如：当任务空闲时间最小，任务最重要时，任务优先级最高。

图6  推理规则决策三维图

Fig.6  Decision surface corresponding to inference rules

2  仿　真

设单个控制任务为：PID控制器控制伺服电机，输入为方波信号r，采样周期为h，比例、微分和积分系数分别为K，T_d和T_i，微分增益为N。对象和控制器如下：

对控制对象，

。

对离散PID控制器，

；

；

；

。

其中：；。取K=0.96，T_d=0.094，T_i=0.12，N=10，h=6 ms。

按照图1所示系统结构，由4个任务τ₁(0.004, 0.001, 1), τ₂(0.005, 0.001, 2), τ₃(0.006, 0.001, 3), τ₄(0.003, C₄, 3)组成单处理机计算机控制系统，τ₁，τ₂和τ₃ 3个任务的周期分别为(0.004, 0.005, 0.006)，重要性分别为(1, 2, 3)，即第3个任务最重要，τ₄为一临时任务，通过改变任务τ₄的执行时间C₄，得到不同的系统处理机利用率。通过仿真分析比较FSD模糊调度设计算法、MIX加权组合算法(取P_i=0.8V_i+(1-0.8)d_i，0.8为加权因子)和经典EDF算法，得到不同系统负载下任务的可调度情况、控制性能和系统价值率。

2.1  超载时关键任务控制性能

假定干扰任务为τ₄(0.003, 0.002 6, 3)，系统负载为

。

当系统处于超载情况时，采用3种调度算法所得关键任务τ₃的控制性能见图7。可见，EDF调度算法无法满足关键任务的可调度性，控制性能明显下降。而FSD和MIX调度算法可以保证关键任务较好的控制性能，这主要是因为双参数调度算法考虑了任务重要性这一特征参数，将更多的处理机资源分配给了重要任务，从而保证关键任务的可调度性在超载时不受或尽可能少受影响。

1—MIX算法；2—EDF算法；3—FSD算法

图7　150%负载下关键任务控制性能

Fig.7  Control performance of critical task under 150% overload

2.2  系统价值率

图8所示为3种调度算法的系统价值率I_VR。可见，当处理机利用率低于0.8时，3种调度算法都能保证系统的可调度性。当处理机利用率为0.8~1.0时，EDF为最优动态调度算法，其I_VR保持为1，是所有调度算法中最高的，FSD通过模糊调度规则配置只造成少量的非关键任务截止期丢失，对非关键任务的可调度性影响较小，其I_VR不低于96%，仍保持较高值，而MIX算法的I_VR相对较低。这主要是因为MIX算法中重要任务占用了更多的处理机资源，造成一些非关键任务截止期丢失，引起整个系统可调度性能降低。超载时(处理机利用率大于1)，采用EDF算法，系统可调度性能急剧下降，I_VR明显降低，FSD算法和MIX算法的I_VR仍能保持较高值。这说明超载情况下采用双参数调度算法可以有效提高系统性能。因此，FSD算法灵活的模糊调度规则可以使I_VR更高。

1—MIX算法；2—EDF算法；3—FSD算法

图8  系统价值率指标

Fig.8  System value ratio performance

3  结 论

a. FSD调度算法综合考虑任务的重要性和任务作业空闲时间这2个特征参数进行模糊调度设计, 通过模糊规则设计灵活调整任务重要性和空闲时间在优先级分配中的权重，使得越重要的任务或空闲时间越短的任务获得的优先级越高。

b. 轻载时(系统负载U≤0.8)，FSD算法可以保证所有任务均可调度，保证系统的可调度性能。

c. 重载时(0.8＜U≤1.0)，FSD算法保证关键任务的截止期错失率为0，而将非重要任务的截止期错失率维持在较低值，与经典MIX算法相比，有效提高了任务调度成功率。

d. 过载时(U＞1)，FSD算法可优先保证关键任务的可调度性，避免出现EDF 等经典调度算法中存在的多米诺现象，获得较好的系统性能。

参考文献：

[1] Cervin A. Integrated control and real-time scheduling[D]. Sweden: Lund Institute of Technology, 2003.

[2] 刘 怀, 费树岷. 控制系统中实时任务的动态优化调度算法[J]. 控制与决策, 2005,20(3): 246-250.
LIU Huai, FEI Shu-min. Optimal dynamic scheduling algorithm for real-time tasks in digital control systems[J]. Control and Decision, 2005, 20(3): 246-250.

[3] Stankovic J A. Real-time computing systems: the next generation[M]. Los Alamitos: IEEE Computer Society Press, 1989: 14-37.

[4] Fohler G, Buttazzo G C. Guest editorial: Introduction to the special issue on flexible scheduling[J]. Real-Time Systems, 2002, 22(1/2): 5-7.

[5] Stankovic J, Ramamritham K. The spring kernel: A new paradigm for real-time systems[J]. IEEE Software, 1991, 8(3): 62-72.

[6] Liu C L, Layland J W. Scheduling algorithms for multiprograming in a hard real-time environment[J]. Journal of the Association for Computing Machinery, 1973, 20(1): 41-61.

[7] Haritsa J R, Livny M, Carey M J. Earliest deadline scheduling for real-time database systems[C]//Proceedings of the 12th IEEE Real-Time Systems Symposium. Los Alamitos, 1991: 232-243.

[8] LIU Yun-sheng, HE Xin-gui, TANG Chang-jie, et al. Special type database technology[M]. Beijing: Science Press, 2000.

[9] SHEN Qing, GUI Wei-hua, YANG Chun-hua, et al. Application of predictive control scheduling method to real-time periodic control tasks overrun[J]. Journal of Central South University of Technology, 2007, 14(2): 266-270.

[10] Caccamo M, Buttazzo G, Sha L. Handling execution overruns in hard real-time control systems[J]. IEEE Trans on Computers, 2002, 51(7): 835-849.

[11] Buttazzo G, Spuri M, Sensini F. Value vs. deadline scheduling in overload conditions[C]//Proceedings of the 19th IEEE Real-Time Systems Symposium. Pisa, 1995: 90-99.

[12] 王永炎, 王 强, 王宏安. 基于优先级表的实时调度算法及其实现[J]. 软件学报, 2004, 15(3): 360-370.
WANG Yong-yan, WANG Qiang, WANG Hong-an. A real-time scheduling algorithm based on priority table and its implementation[J]. Journal of Software, 2004, 15(3): 360-370.

[13] Saini G. Application of fuzzy logic to real-time scheduling[C]// Real Time Conference. India, 2005: 113-116.

[14] 金 宏, 王宏安, 唐雪梅, 等. 计算机控制中的模糊调度设计[J]. 计算机学报, 2006, 29(3): 414-422.
JIN Hong, WANG Hong-an, TANG Xue-mei, et al. Fuzzy scheduling design in computer control[J]. Chinese Journal of Computers, 2006, 29(3): 414-422.

[15] Richardson P, Sarkar S. Adaptive scheduling: overload scheduling for mission critical systems[C]//Proceedings of the 5th IEEE Real-Time Technology and Applications. Vancouver, 1999: 14-23.

[16] Sabeghi M, Naghibzadeh M, Taghavi T. Scheduling non- preemptive periodic tasks in soft real-time systems using fuzzy inference[C]//Proceedings of 9th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing. Gyeongju, South Korea, 2006: 27-32.

收稿日期：2008-10-09；修回日期：2008-12-05

基金项目：国家自然科学重点基金资助项目(60634020)；国家自然科学基金资助项目(60874069)

通信作者：沈  青(1965-)，女，浙江临海人，博士研究生，从事实时调度，优化控制与网络控制研究；电话：13974870630；E-mail: s54@21cn.com