实时控制系统一种基于模型预测控制的反馈调度

　第40卷第5期　2006年5月

上海交通大学学报

J OU RNAL OF SHAN GHA I J IAO TON G UNIV ERSIT Y

Vol.40No.5　

May 2006　

收稿日期:2005206208

作者简介:周平方(19762),男,湖南常宁人,博士生,主要从事实时系统、计算机控制系统等研究,E 2mail :zhoupf @.

谢剑英(联系人),男,教授,博士生导师,电话(Tel.):021*********.

文章编号:100622467(2006)0520838205

实时控制系统一种基于模型预测控制的反馈调度

周平方,　谢剑英

(上海交通大学自动化系,上海200030)

摘　要:提出一种基于模型预测控制(M PC )的反馈调度算法(FS 2M PC ),可以在有限计算资源的

情况下改进实时控制系统的性能.将被控的实时调度过程模型化为受约束的任务集密度控制问题.在FS 2MPC 算法中,约束条件保证任务集在最早截止时限优先(EDF )算法下是可调度的;同时,M PC 的优化目标通过减小控制任务的截止时限使整个任务集的密度尽可能接近100%,从而提高控制任务的优先级,降低输出抖动.仿真结果表明,在有限计算资源的情况下,FS 2M PC 显著地降低了由调度过程引起的控制性能损失.

关键词:实时控制系统;反馈调度;模型预测控制;最早截止时限优先中图分类号:TP 273 文献标识码:A

A Model Predictive Control 2Based Feedback Scheduling

for Real 2T ime Control Systems

Z HOU Pi ng 2f ang ,　X I E J i an 2y i ng

(Dept.of Automation ,Shanghai Jiaotong Univ.,Shanghai 200030,China )

Abstract :A feedback scheduling based on model p redictive control (FS 2M PC )was presented to improve t he cont rol performance of real 2time control system subject to limited comp utational resource.The controlled real 2time scheduling is modelled as a const rained density cont rol p roblem of t he total task set.In t he FS 2M PC ,t he const raint s guarantee t hat t he task set is schedulable by EDF (earliest deadline first )algorit hm.At t he same time ,t he optimization goal of M PC (model p redictive cont rol )makes t he density of t he total task set as clo se to 1as po ssible t hrough shortening cont rol tasks ’deadlines.As a result ,t he cont rol tasks obtain higher p riorities and t he outp ut jitter is reduced.The simulation result s illust rate t hat t he schedu 2ling induced control performance lo ss is reduced greatly by t he FS 2M PC subject to limited comp utational resource.

Key words :real 2time cont rol system ;feedback scheduling (FS );model p redictive control (M PC );earliest deadline first (EDF )

现代实时控制系统(R TCS )通常是基于一个实时内核,多个闭环控制任务在内核的基础上竞争性地使用共享的处理器时间.因此,处理器的时间被当作是一种最重要的资源,需要一定的调度算法来将其分配给各个任务.这样就可能引起控制任务的抖动,尤其是当周期很短、处理器利用率很高的时候.

文献[1,2]中说明了控制任务中由调度引起的抖动的存在降低了R TCS的性能,甚至可能导致系统的不稳定.另外,从控制理论的角度来看,抖动还可以进一步分为采样的抖动(采样时刻的变化)以及输出的抖动(控制量输出时刻的变化).但是,如果A/D 转换是由时间触发的,没有包含在控制任务的内部,则可以认为采样是没有抖动的.这样,只需要考虑输出的抖动.

在实时调度理论方面,一个直接而有效的减小输出抖动的方法就是给任务分配更紧的截止时限,而不是简单地等于其周期,然后按照任务的截止时限来调度任务[3].最近在控制理论方面的成果也证实了有可能通过截止时限分配来限定最大允许时变延迟的边界,并依此提供系统的稳定性保证[4,5].尽管给任务分配一个更小的截止时限有利于减少抖动,却使得整个任务集的可调度性变得较差.文献[6]在此基础上,加入任务集的可调度性约束条件,用线性规划的方法来分配任务的截止时限,但所采用的方法都是离线和静态的.反馈调度[7]的提出使得在线地分配截止时限成为可能,而目前已有的反馈调度方法[7,8]还没有显式地把有限的计算资源当作约束条件来处理.

本文在最早截止时限优先(EDF)[9]算法的框架下,提出了一种基于模型预测控制(M PC)的反馈调度算法(FS2M PC),该算法在满足资源和可调度性约束的范围内动态调节控制任务的截止时限.约束条件保证任务集在EDF算法中是可调度的;同时, M PC的优化目标减小控制任务的截止时限使得任务集的密度尽可能地接近100%.这样,控制任务获得了更高的优先级,从而降低了输出抖动.

1　问题描述

1.1　E DF可调度性条件

考虑单处理器环境下周期性任务的抢占式调度.基本的调度算法为EDF,它是按照绝对截止时限给任务指定优先级,时限越早,任务的优先级越高,并且已经证明是动态的最优调度算法.

以Γ={τ1,τ2,…,τn}代表周期性任务组成的任务集,Γ′<Γ代表Γ中那些对抖动敏感的控制任务组成的子集.其他对抖动不敏感的周期任务,如状态监视任务等,组成Γ′的补集,由Γ′<Γ表示.每个任务τi由(T i,e i,D i)描述,其中,T i、e i和D i分别为任务的周期、最坏情况下执行时间和相对截止时限.

目前使用得最广泛的EDF算法可调度性条件如以下定理[10]所述.

定理　在抢占式单处理器环境中,周期性任务集Γ如果满足6n i=1e i

min(

D i,T i)

≤1,则该任务集是可以被EDF算法所调度的.

在该定理中,e i

min(D i,T i)

被称为任务τi的密度.所有任务密度之和称为整个任务集的密度,由Y 表示.当存在某个D i

1.2　问题描述

对于Γ′中的任务,假定D i=T i.但是对于Γ′中的控制任务,令D i=T i/c,其中c(k)≥1,即所有控制任务截止时限的调节幅度相对于各自的周期是一样的.另外,由事件触发的非周期任务,如告警发布等,被当作是实时调度过程中的扰动.为简便起见,本文通过设置服务器机制将这些事件触发的非周期任务当成周期任务一并处理.

因此整个任务集系统的密度Y由3部分组成:对抖动敏感的控制任务子集Γ′的密度YΓ′,对抖动不敏感的其他周期任务子集Γ′的密度YΓ′以及随时间变化的非周期任务处理器利用率Dist(k).其中, YΓ′等于其处理器利用率因子,YΓ′=UΓ′=6τi∈Γ′e i T i,为常数.选取整个任务系统密度作为输出y(k),控制任务子集密度作为状态变量x(k),截止时限调节因子作为控制量c(k).假定控制量输入c(k)与状态变量x(k)之间的关系为x(k+1)=f(x(k),c(k)).

因此,被控的实时调度过程被模型化为整个任务集的密度控制问题,从而将R TCS中反馈调度的M PC问题描述为:

被控对象

x(k+1)=f(x(k),c(k))

y(k)=x(k)+UΓ′+Dist(k)

(1) 约束条件

c(k)≥1,　y(k)≤1(2) 模型预测控制器的优化目标是使下面目标函数最小化:

V(k)=6P i=1‖y(k+i|k)-r‖2Q+

6M-1i=0‖Δc(k+i|k)‖2R(3)

938

　第5期周平方,等:实时控制系统一种基于模型预测控制的反馈调度