面向数控系统的反馈调度算法的研究*

郭凤钊，郭锐锋，丁万夫，，秦承刚，

(1.中国科学院研究生院，北京 100039;2.中国科学院沈阳计算技术研究所高档数控国家工程研究中心，沈阳 110171)

面向数控系统的反馈调度算法的研究*

郭凤钊1，郭锐锋2，丁万夫1，2，秦承刚1，2

(1.中国科学院研究生院，北京 100039;2.中国科学院沈阳计算技术研究所高档数控国家工程研究中心，沈阳 110171)

传统的数控系统使用静态的、开环的任务调度策略，在其运行过程中系统的资源不能被充分地利用。为提高数控系统的资源利用率，论文设计了一种针对软实时任务的闭环反馈调度算法。该反馈调度算法通过监控当前系统的负载和任务的截止期错失率，能够自动调整软实时任务的时间参数，使系统资源可以被充分利用，并使系统在各种负载的情况下都能获得较好的性能。通过实验对该反馈调度算法进行验证，结果表明，该调度算法能够显著提升数控系统的CPU利用率，同时还能保证数控系统的稳定性。

数控系统;实时系统;自适应调度算法;反馈控制

0 引言

随着开放式数控系统概念的引入，具有自适应性质的实时系统引起人们越来越多的研究。在传统的调度模型下，系统的可调度性取决于每一个任务(Task)在最坏情况下的执行时间(WCET，Worst-Case Execution Time)，使用WCET可以简化系统的操作，但由于WCET是在最坏情况下的时间需求，故不能充分利用CPU，对系统资源造成比较大的浪费，并且很多实时程序的WCET是无法被准确预知的［1］。

自适应的实时调度算法可以监控当前系统的负载情况，动态地对实时任务进行时间参数的调整，使系统在无需预知任务时间参数的情况下稳定的工作。文献［1］首次提出了基于EDF算法的反馈模型，其中每个实时任务都拥有多个服务级，每一个服务级都代表着不同的服务质量(QoS，Quality of Service)和执行时间。算法通过检测系统的时限错失率(DMR，Deadline Miss Ratio)和系统负载情况来调整任务的服务级。此反馈模型的缺点是系统无法监测某一任务的错失率是否太大或CPU利用率是否太高。文献［4］中的反馈模型为每一个实时任务分配了一个反馈控制器，监测每一个实时任务的错失率和CPU利用率，然而该模型忽略了任务各自的重要性是不同的。文献［2］为实时任务提出一个重要性参数概念，根据重要性的不同，为每个任务分配不同的周期。文献［2］的缺陷是假定实时任务的执行时间是固定的，只对任务周期进行了调节。

结合数控系统的特点，本文设计了一种针对数控系统中软实时任务的反馈调度算法。该反馈调度算法根据当前系统的负载情况和各个任务的错失率来对任务的服务级别进行调整，每个服务级都有相应的执行时间和任务周期。在调整时，根据各个任务的重要性大小，依次对它们的服务级进行调整。通过这种动态地调整，系统资源得到充分地利用，保证系统在各种负载的情况下都能保证其较好的性能。

1 数控系统的调度模型

1.1 传统数控系统的调度模型

数控系统是一个专用的实时系统。在数控系统中，根据任务对实时性的要求不同，可以把任务分为硬实时任务、软实时任务和非实时任务。硬实时任务指必须满足最后截止时刻限制的任务，否则会给系统带来不可接受的破坏或者致命的错误，体现在数控系统中主要是插补计算、采样控制，软PLC等。一般对硬实时任务的调度算法都会以满足其时限(Deadline)为目的。软实时任务主要包括解释器任务、文件服务通信任务和监测与报警任务。这些任务对实时性的要求不高，偶尔丢失实现并不会对数控的性能造成影响，故可以采用反馈算法对软实时任务的时间参数进行动态地调节。非实时任务包括图形显示、参数管理等对实时性没有要求的任务，此类任务的丢失不会对数控系统的加工质量造成任何影响。

在传统数控系统中，对于混合任务的调度采用前后台方法，即系统只有在没有硬实时任务就绪的情况下，才会执行软实时或非实时任务。这种方法的优点是易于实现，但也可能出现问题。例如，在数控系统中，解释器对G代码进行解释，然后把解释后的数据放入解释器缓冲区，使插补器可以从解释器缓冲区中取解释数据。由于共享内存空间有限，如果解释器错失率太高，插补任务将可能会产生“数据饥饿”，因等待数据而延缓执行，从而影响到加工的质量［7］。

1.2 任务模型的基本定义

根据任务模型的定义，选取模型任务集为偶发性任务集。偶发任务的释放时间是随机的，但是其相邻作业到达的时间间隔大于等于某个最小值，这个最小值被当做偶发任务集的周期。偶发任务是强时限的，这一模拟任务类型在如数控系统中具有代表性。

本文使用以下符号对任务模型进行描述:

2 反馈调度模型

2.1 反馈模型设计思想

系统中每一个任务都有多个服务级，每一个服务级都代表一个QoS，拥有自己的周期p(Ti)和执行时间e(Ti)，服务级越大代表QoS越好。由p(Ti)和e(Ti)可以确定该服务级的权重，代表该任务名义上对系统利用率的要求［1］。在［1］中，若任务在某一服务级别，系统便使用该服务级的权重作为该任务的估计权重。对于某些实时系统，这样静态地分配估计权重是可行的，但是对于数控系统而言，由于无法事先得知任务的执行时间，故预知一个任务的权重是不现实的。本论文采用动态计算估计权重，而非静态分配任务的估计权重的方法。

本文为反馈模型引入了“重要性参数”概念，认为在实时系统中，软实时任务的“重要性”是不相同的。例如在数控系统中，软实时任务有解释器任务、文件服务通信任务以及监测与报警任务，通常我们认为解释器任务比文件服务通信任务和监测与报警任务更为重要。

在反馈模型中，所有的任务都可以被加载到系统中，系统监测每一个任务的权重和整个系统的负载情况。如果某一任务的估计权重和实际权重相差过大或系统负载过高，则需要对系统进行服务级的调整。在进行调整时，根据它们的重要性参数排序，依次分配每个任务的服务级，给予最重要的任务尽可能高的服务级。模型使用EDF算法，每次调度时选择最高优先级即最早时限的任务进行调度。

反馈模型主要由反馈控制器和优化器(Optimizer)构成，反馈控制器根据当前任务实例的实际权重来计算下一个任务实例的估计权重。优化器用来给系统中的每个实时任务分配合适的服务级别。反馈模型如图1所示。

图1 反馈调度模型

2.2 反馈控制器

实时系统一般而言是非线性时变系统，要对其进行精确的建模是很困难的，但由于闭环反馈控制具有对变化系统模型的健壮性，所以可以采用线性模型来近似一个实时系统，达到简化控制设计的目的。

反馈系统由输入值，输出值，误差以及控制器组成，PID(比例-积分-微分)控制器是在工业控制中运用最广泛的控制器，它由比例单元(P)、积分单元(I)和微分单元(D)组成。其输入Error(t)与输出U(t)的关系为:

其中p，i，d分别为比例参数，积分参数以及微分参数。在很多情况下，并不一定需要全部三个单元，可以取其中的一或两个单元，但比例控制单元是必不可少的。本文使用比例单元(P)和积分单元(I)，没有选取微分单元是因为控制器的微分功能不适合控制实时系统，微分单元可能会放大因为CPU和带宽负载的随机性而造成的系统噪音。由于本反馈系统是周期采样的，是离散系统，故输出Ew()与输入Error(的关系为:

由于本反馈调度模型的传递函数建立在z域内，故可使用离散系统根轨迹方法分析系统的系能。在线性离散系统中，系统的动态性能如连续系统一样主要由闭环特征多项式的根来决定，系统的稳定条件是闭环特征多项式的根都在z域的单位圆内。由反馈模型的闭环传递函数，画出其根轨迹并取闭环极点为p1=0.4613，p2=0.4367。由确定的闭环极点得到PI控制器的参数p=0.102，q=－1.975。由于所选取的闭环极点都是处于z平面上的单位圆内，所以此离散系统是稳定的。

2.3 优化器

每一个任务都有一个用户定义的重要性参数，代表该任务的重要程度，用L来表示，例如用L(Ti)表示Ti的重要程度。在每一次调用优化器的时候，都会根据每个任务的L值对任务进行由大到小的排序，依次给各个任务分配合适的服务级别。

假设系统中有n个任务T1，T2，…，Tn，每个任务都分别有m个服务级，每个服务级对应的估计权重分别为w1，w2，…，wm，设w1＜ w2＜ … ＜ wm。每个任务都有自己的重要性参数，分别为 L(T1)，L(T2)，…，L(Tn)。在调用优化器进行调整时，首先把n个任务的服务级置为1(最低)，之后按照L值从大到小对任务进行排序，设依次为Tl1，Tl2，…，Tln。根据这个次序，在不超过系统带宽上限的情况下，为每个任务分配尽可能大的服务级。

例如，系统中有四个任务 T1，T2，T3，T4.假设每个任务都分别有四个服务级，假设每个服务级对应的估计权重分别为2/5，3/10，1/5，1/10，并且已知L(T1)＞L(T2)＞L(T3)＞T(T4)。调度算法使用EDF算法，系统带宽上限设为1。在进行调整时，把四个任务的服务级置为1(最低)，此时1/10+1/10+1/10+1/10=2/5＜1。依次尝试分配各个任务的服务级，对于T1，2/5+1/10+1/10+1/10=7/10 ＜1可以被调度，故可以T1的服务级从1升为4(最高)。然后对T2进行尝试，2/5+2/5+1/10+1/10=1，可满足T2的最大的权重，把T2的服务级从最低变为最高。之后对于 T3，2/5+2/5+1/5+1/10=11/10＞1，已经超过了系统最大调度能力，故T3的服务级不能提升。同理可计算出T4的服务级仍为最低值，其权重保持为1/10。

3 实验研究与分析

3.1 试验平台

本文使用了蓝天数控系统作为实验平台，该系统采用了基于双内核架构的实时操作系统RTAI(Real-Time Application Interface)。RTAI采用模块化的方式，作为Linux的模块插入到内核运行空间，用以实现了Linux内核的实时扩展。为了实现针对软实时任务的反馈调度器，本文对RTAI的软实时任务的结构定义及其调度函数进行了修改，在Linux内核空间内实现了一个软实时调度器，在此基础上对反馈调度器进行实验测试。

3.2 实验方法及参数选定

模型的基本调度策略使用EDF调度算法，该算法使系统的调度上限可达到100%。

试验参数设置如下，在系统中设定4个软实时任务，每个任务有4个服务级别，设每个任务最高服务级中的时间参数都为其在数控系统中最大QoS下的执行时间和周期。假设服务级别和权重满足线性关系，随着服务级的下降，任务的权重随之变小。线性比例系数由最大QoS下的权重和最小QoS下的权重确定。

假设任务的重要性参数服从［0，1］范围内的均匀分布，随机为任务分配其重要性参数。根据3.2节的分析，置PI控制器参数为p=0.102，q=－1.975。

设定任务估计权重和实际权重之间的最大差值，即Error的上限不超过0.5。如果超过这个值，系统就会调用优化器对任务进行新服务级的分配。

通过实验，本文选择采样周期为20μs，在此采样周期下数控系统具有最好的稳态性能和收敛速度，系统开销也在可以容忍的范围内。

3.3 单个任务的权重表现

图2为其中一个任务在0到20s的时间参数调整的表现。其中Aw为实际权重(ActualWeight)，Ew代表实际权重(EstimateWeight)，Error=Ew－Aw。从粗实线的表现可以看出，在大部分的时间内，Error值都是保持在［－0.2，0.2］之间的。在5.6s的时候，Error值超过其设定上限，系统通过反馈算法对任务的服务级进行调整，降低了该任务的服务级，使Error值迅速恢复到比较小的范围内。降低此任务的服务级之后，该任务实际权重和估计权重都有了相应的下降。在8.1s时，Error过大再次调整服务级，相应地计算新的估计权重，使Error值再次回到可接受的范围内。

图2 单个任务的权重变化

3.4 整个系统的负载情况

根据图3可以看出，传统数控系统的调度算法使用任务的WCET来判断是否可调度，系统的负载在一定时间内稳定在0.76附近，虽然可以稳定工作，但系统的资源无法得到充分利用;使用反馈调度算法，系统的总负载在1的附近波动，当系统负载超过1之后，反馈模型调用优化器迅速调整系统中任务的服务级，使负载下降，保证数控系统不会过载;当系统负载过低时，优化器再次被触发，调整系统中所有任务的服务级，提高任务的CPU利用率，使系统可以得到充分的利用。

图3 整个系统的负载情况

4 结束语

本文根据数控系统的特点，设计了一种针对数控系统中软实时任务的反馈调度模型。该反馈调度算法通过监控当前数控系统的负载情况和各个任务的错失率，来自动调整软实时任务的周期和执行时间。在系统负载不足时，对软实时任务进行时间参数的调整，使系统资源得到充分利用。在系统负载过大时，反馈调节也可以对系统中任务进行调整，从而保证了其稳定性。通过实验对该反馈调度算法的性能进行了验证，通过对比实验的结果，可看出反馈调度算法可以很好地满足数控系统中软实时任务的调度要求，提升系统资源的利用率，并在此基础上保证数控系统的稳定性。

［1］C.Lu，J.Stankovic，G.Tao and S.Son.Feedback Control real-time Scheduling:framework modeling and algorithms［J］.Real-time Systems，2002，23(9):85 －126.

［2］P.Marti，C.Lin，S.Brandt，M.Velasco，and J.Fuertes.Optimal State Feedback Based Resource Allocation for Resource-Constrained Control Tasks［C］.In Proc.of the 25th IEEE Real-Time Systems Symp.，2004:161 －172.

［3］T.Abdelzaher，J.stankovic，C.Lu，R.Zhang，and Y.Lu.Feedback performance control in software services［J］.IEEE Control Systems，2003，23(6):74 －90.

［4］L.Abeni，L.Palopoli，G.Lipari，and J.Walpole.Analysis of a reservation-based feedback scheduler［C］.In Proc.of the 23rd IEEEReal-Time Systems Symp.，2002:71 －80.

［5］A.Block，B.Brandenburg，J.Anderson，and S.Quint.An Adaptive Framework for Multiprocessor Real-Time System［J］.Real-Time Systems，2008(7):23－33.

［6］ G.Buttazzo，L.Abeni.Adaptive workload management through elastic scheduling［J］.Real-time Systems，2002，23(1－2):7－24.

［7］秦承刚，于东，吴文江，等.一种面向数控系统的动态反馈调度模型［J］.小型微型计算机系统，2010，31(4):788－792.

［8］王保胜，吴文江，马跃，等.开放式数控系统任务调度模型［J］.组合机床与自动化加工技术，2010(6):37－42.

(编辑 李秀敏)

An Adaptive Scheduling Algorithm for CNC System

GUO Feng-zhao1，2，GUO Rui-feng2，DINGWan-fu1，2，QIN Cheng-gang1，2
(1.Graduate University of Chinese Academy of Sciences，Beijing 100039，China;2.National Engineering Research Center For High-End CNC，Shenyang Institute of Computing Technology，CAS，Shenyang 110171，China)

Traditional CNC system uses static,open-loop scheduling strategy.The system resources can not be fully utilized.To improve the utilization of CNC system,we present a Feedback Control EDF scheduling algorithm for soft real-time tasks.By monitoring the current system load and themiss rate of each task,the feedback scheduling algorithm automatically adjust the time parameters of the soft realtime tasks.The system resources can be fully utilized,and have a better performance in various conditions.We elaborate some experiments to test the performance of the presented feedback control scheduling,the result illustrate that the algorithm can effective improve the utilization of system,and ensure the stability of the CNC system.

CNC System;real-time system;adaptive scheduling algorithm;feedback control

TH16;TG65

A

1001－2265(2011)06－0044－04

2010－11－12

“高档数控机床与基础制造装备”国家科技重大专项－开放式数控系统支撑技术创新平台建设(2011ZX04016－071)

郭凤钊(1987—)，男，河北邯郸人，中国科学院研究生院硕士研究生，主要研究方向为实时调度算法，(E－mail)guofengzhao@sict.ac.cn;郭锐锋(1968—)，男，沈阳人，中国科学院研究生院博士生导师，主要研究方向数控技术与实时系统，(E－mail):grf@sict.ac.cn。