实时调度及实时控制

实时调度及实时控制一、实时任务a：到达时间s:开始执行时间e:执行结束时间d:截止期T:切换时间C:执行时间一、实时任务调度硬截止期硬截止期任务用于保证系统的正确运行,通常是周期性的或者相邻的两个任务实例之间具有一个最小间隔时间固截止期通常是非定期任务,具有不确定的到达时间软截止期通常是非定期任务,具有不确定的到达时间周期性任务的调度算法

RM算法－单速率算法任务的优先级决定于其周期，周期越小的任务优先级越高，由于任务的周期是固定的，所以该算法是基于静态优先级的；T1=5，T2=7C1=2，C2=3EDF算法－最早截止期优先调度算法任务的优先级决定于其绝对截止期，绝对截止期越小的任务优先级越高，EDF是基于动态优先级的。周期性任务的调度算法

T1=5，T2=7C1=2，C2=3RM和EDF在固定优先级和动态优先级算法中分别是最优的。RM算法只能解决任务截止期等于任务周期时的最优调度，当这个条件不满足时，可以证明截止期单调（DM，DeadlineMonotonic）算法是最优的。周期性任务的调度算法

非周期性任务的调度算法

混和任务的实时调度算法

静态调度后台调度（BackgroundScheduling）:非周期性任务采用先到先服务FCFS策略在周期性任务执行后的空闲时间片调度。为了提高非周期性任务的响应性能，轮询服务器策略设立一个周期任务服务器，专门用于服务非周期任务，在满足其它周期任务截止期的前提下，尽可能地给这个服务器分配服务时间。这种方法实质上是轮询服务。

动态调度为了克服基于静态优先级方法无法处理突发事件，基于动态优先级方法可以把任何空闲处理能力（没有周期任务使用）都用于非周期任务，这样既可以实现非周期任务的快速响应特性，又能保证周期任务的实时性。动态优先级交换服务器和动态零星服务器其他问题共享资源互斥的调度

过载处理

多处理器调度或多机调度（MMS:Multi-MachineScheduling）不但要解决何时执行任务，而且还要解决在何处执行任务。这就同时涉及到任务的分配与调度，也涉及到某一个处理器的资源、网络通信等许多问题，大大增加了问题的难度，已经证明此类调度多为NP问题。二、实时控制

软件领域功能测试单元测试软件设计控制领域性能需求模型设计算法设计控制设计对控制与计算缺乏共同认识采样周期与性能损失

连续系统的状态方程：控制与状态的不等式约束：终端状态的等式约束：性能指标：离散化后的状态方程：离散化后的性能：性能损失：指数模型周期分配方法（Seto）

指数模型(Seto)：

多任务优化模型：

特点：静态方法，采用了近似的性能指标弹性任务模型（EPAA,Buttazzo），

其中特点：压缩过程中任务的弹性系数始终不变

动态优先级调整算法(DPAA)

将利用率调整区间划分为段，逐段对任务利用率进行压缩，压缩过程中任务的弹性系数由当前的利用率来确定，这样，对于那些性能衰减速率变化较大的任务，就有可能争取到更多的处理器资源，从而提高系统整体性能。

DPAA算法：动态优先级调整算法仿真结果

任务参数仿真结果DPAA讨论

该算法不一定针对固定模型的实时控制任务，各种性能损失对于利用率的变化率模型已知的任务，在经过优先级映射后，都可以经过该算法统一调整利用率；与指数模型不同的是，除了可以用于动态分配以外，动态优先级算法的性能损失函数可以是非单调的，在应用中只需要对每一个单调区间进行描述；动态优先级算法实际上是弹性任务的分段线性化压缩，每一段的计算复杂度和弹性算法一样，均为。实时系统的设计应考虑计算资源的额外开销，否则就会导致舍本逐末的结果。从这一点考虑，在对任务利用率区间分段时，段数不宜过多，分段具有代表性即可。控制参数根据周期变化的调整

在线设计：需要大量计算时间，不现实离线设计：在控制算法设计阶段，在采样周期允许范围内选取适当具有代表性的周期点，逐点设计控制器参数并保存，当前周期对应的控制器参数通过查表插值来计算，这对于线性系统来说较为有效。

理想控制任务数字实现假设条件

采样任务通常被认为很精确地按某个周期进行采样数据就绪后，控制计算立即执行，执行器在接收到控制计算的结果后要么立即执行输出，要么按照与采样时刻固定的延时输出三个任务自身的执行时间为零抖动与延迟定义

定义采样抖动:实时控制任务两个相邻实例的采样间隔变化。设任务的采样间隔序列为，其中，则采样抖动。定义计算延迟:实时控制任务实例从采样至任务输出执行完成的时间间隔，。理想控制任务数字实现假设条件

两个实时任务共享处理器单速率（RM）调度算法

抖动和延迟对控制性能的影响

控制对象：

PID控制：调度算法：RM调度

执行时间：1毫秒采样周期：3、4、5毫秒抖动和延迟静态补偿

将非周期任务用周期服务器进行隔离；确定周期任务的周期；

以尽可能减小上下文切换次数为优化目标，将周期任务在某一时间段上进行调度，形成调度队列；建立所有任务在一个宏周期内实例的延迟和抖动列表，在每个实例进行补偿。抖动和延迟静态补偿－PID例子采样，，，查询，，；误差

输出执行，数据更新静态补偿－PID仿真结果控制对象PD控制器EDF调度

动态补偿——单任务实时性能指标线性二次型最优控制

完全可控线性连续系统的状态方程：

性能指标：

LQ最优控制：

系统性能：

单任务实时性能指标线性二次型最优控制

离散系统的状态方程：

其中

多任务性能优化模型多任务性能优化模型：

调整采样周期，修改控制参数；减小采样抖动；使计算延迟保持在某一固定值附近，以便于从控制算法进行补偿；子任务调度思想一个采样周期内的计算时间:

控制量的计算时间只占总计算时间的很小部分;

采样以及执行输出指令占用的计算时间几乎为零;

计算时间的大部分用于执行一些其它功能如数据标记及安全验证等

子任务调度将控制任务划分为控制输出和数据更新两个子任务

子任务引起的截止期错失完整任务调度：RM子任务调度：FP，出现错失缺点：增加了上下文切换

子任务、FP调度，给所有子任务分配，按截止期单调（DM）算法分配任务优先级，任务截止期越小，优先级越高；计算各控制输出子任务的释放时间；返回2，直至所有不再变化。t:=GetSystemTime();SetPriority(P_CO);LOOPReadInput(t,y_value);CalculateOutput(t,y_value);WriteOutput(t,u_value);

SetPriority(P_Up);UpdateState();t:=t+T;

SetPriority(P_CO);SleepUntil(t);END;

子任务、EDF调度t:=GetSystemTime();SetAbsoluteDeadline(t+DCO);LOOPReadInput(t,y_value);CalculateOutput(t,y_value);WriteOutput(t,u_value);

SetAbsoluteDeadline(t+T);SleepUntil(t+DCO)UpdateState();t:=t+T;

SetAbsoluteDeadline(t+DCO);SleepUntil(t);END;

任务的释放时间在EDF调度中很难分析，将数据更新任务推迟到控制输出任务的截止期释放子任务调度仿真结果控制对象：

PID控制：调度算法：FP调度

总执行时间：2.5毫秒采样周期：12、13、14毫秒控制输出时间：0.5毫秒数据更新时间：2毫秒子任务优先级分配结果子任务调度仿真结果计算延迟分布采样间隔分布输出对比三、任务属性调整的意义弥补根据最坏执行时间确定任务属性的不足需要灵活的准入机制

实时控制系统的设计中，我们通常希望其鲁棒性能够使其很好地适应任务采样周期和响应时间的变化，控制器可以被设计为能够在不同的工作方式下切换或具有不同的采样间隔，甚至在必要的时候控制器可以牺牲本回路的性能以减小处理器的负荷。反馈调度系统一般来说，反馈调度要解决的问题包括如何选取合适的控制信号、测量信号和设定点，采用何种控制结构以及适用于哪些过程模型。调度器的目标通过调节控制任务的采样频率，使处理器的利用率保持在某一给定值附近。监视器：监视处理器的负荷状态（截止期错过率、处理器利用率等），并将信息反馈到控制器，控制器：根据当前处理器利用率误差，得出估计利用率的变化量（控制量）QoS执行器：调整任务的服务质量。基本调度器：EDF算法或RM算法。实时控制任务性能与周期分析控制对象采样周期：2、12毫秒PD控制器性能指标实时控制任务模糊调度设想：对于离散控制系统，在不同的控制阶段，给控制回路赋予不同的采样周期：当控制回路的误差较大时，给该回路较小的采样周期，使得其性能损失较小；而当该回路进入稳定阶段以后，增大回路的采样周期，在几乎不影响系统性能的前提下，减小了该实时任务的处理器利用率。

实时控制任务模糊调度元素实时内核包括处理器、基本调度器及各种任务。控制任务、其它周期任务及非周期任务统一由基本调度器调度，基本调度器的调度算法可以采用单速率（RM）或截止期优先（EDF）算法。处理器的负荷状态表现为截止期错过率或处理器估计利用率，该参数将由监视器反馈给准入控制器。监视器的作用有两点，首先是监测处理器的负荷状态，将监测到的参数反馈给准入控制器。监视器对处理器负荷状态的监测周期（抽样窗大小）取为任务的宏周期（所有任务周期的最小公倍数）。其次是对实时控制任务状态的监测。准入控制器的目标是保持处理器性能接近于给定值，根据处理器当前负荷状态与给定性能差值得出利用率的变化量，提供给反馈调度器。实时控制任务模糊调度元素反馈调度器根据准入控制器的控制量和实时控制任务的优先级变化对内核中任务的利用率进行调整。

两种实现方式：直接采用原反馈调度系统中的QoS执行器，实时控制任务无法建立QoS与利用率间的关系，给系统中所有需要调整利用率的控制任务分配固定带宽的利用率，控制任务根据各自的需求，在固定带宽内竞争处理器资源。所有任务均无QoS与利用率模型，控制任务和其它任务一样，都依赖各自的优先级竞争处理器资源，在多个控制回路同时出现较大扰动时，控制任务能有效地从其它任务中争取到更大的利用率，反之，其它任务也可以从控制任务中获得更多的处理器资源。

模糊控制规则位置型控制器

控制规则表：模糊控制决策表控制决策表

仿真结果控制对象最小采样周期：4毫秒PD控制器性能指标最大采样周期：15毫秒计算时间：1毫秒随机干扰：0.02总利用率：0.26仿真结果性能对比图

采样周期变化图

四、具有切换时间的多机调度问题优化模型火炮联合防空、Agent移动路径规划

GASA混合优化算法

开始设定算法参数和初始温度产生贪心个体初始化种群评估当前种群中的个体GA交叉操作GA变异操作对各个体进行SA搜索产生新个体以某概率接受新个体SA搜索结束？SA退温操作评估当前种群的个体满足结束条件？GA选择、复制操作结束是否是否GASA混合优化算法——编码及初始群体

编码：多个基因串编码方法

P：

211011536

1379

124814

|

734

执行器1执行器2执行器3任务数

初始群体：产生贪心算子个体（计算复杂度小，局部最优）

初始化将任务置于不可调度队列按最小切换时间，处理不可调度队列统计执行器任务数形成第二个基因串结束是否对,找出队列为空？将任务分配给最小切换时间的执行器GASA混合优化算法——选择