实时调及实时控制.pptx

《实时调及实时控制.pptx》由会员分享，可在线阅读，更多相关《实时调及实时控制.pptx（49页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、间第2页/共49页周期性任务的调度算法周期性任务的调度算法 RM算法单速率算法 任务的优先级决定于其周期，周期越小的任务优先级越高，由于任务的周期是固定的，所以该算法是基于静态优先级的；T1=5，T2=7C1=2，C2=3第3页/共49页EDF算法最早截止期优先调度算法 任务的优先级决定于其绝对截止期，绝对截止期越小的任务优先级越高，EDF是基于动态优先级的。周期性任务的调度算法周期性任务的调度算法 T1=5，T2=7C1=2，C2=3第4页/共49页RM和EDF在固定优先级和动态优先级算法中分别是最优的。RM算法只能解决任务截止期等于任务周期时的最优调度，当这个条件不满足时，可以证明截止期单

3、调（DM，Deadline Monotonic）算法是最优的。周期性任务的调度算法周期性任务的调度算法 第5页/共49页非周期性任务的调度算法非周期性任务的调度算法 第6页/共49页混和任务的实时调度算法混和任务的实时调度算法 静态调度静态调度 后台调度（后台调度（Background SchedulingBackground Scheduling）:非周期性任务采用先到先服务非周期性任务采用先到先服务FCFSFCFS策略在周期性任务策略在周期性任务执行后的空闲时间片调度。为了提高非周期性任务的响应性能，轮询服务器策略设立一个周执行后的空闲时间片调度。为了提高非周期性任务的响应性能，轮询服务器

4、策略设立一个周期任务服务器，专门用于服务非周期任务，在满足其它周期任务截止期的前提下，尽可能地期任务服务器，专门用于服务非周期任务，在满足其它周期任务截止期的前提下，尽可能地给这个服务器分配服务时间。这种方法实质上是轮询服务。给这个服务器分配服务时间。这种方法实质上是轮询服务。动态调度动态调度 为了克服基于静态优先级方法无法处理突发事件，基于动态优先级方法可以把任何空闲处理为了克服基于静态优先级方法无法处理突发事件，基于动态优先级方法可以把任何空闲处理能力（没有周期任务使用）都用于非周期任务，这样既可以实现非周期任务的快速响应特性，能力（没有周期任务使用）都用于非周期任务，这样既可以实现非周期

5、任务的快速响应特性，又能保证周期任务的实时性。又能保证周期任务的实时性。动态优先级交换服务器和动态零星服务器动态优先级交换服务器和动态零星服务器 第7页/共49页其他问题共享资源互斥的调度共享资源互斥的调度共享资源互斥的调度共享资源互斥的调度 过载处理过载处理过载处理过载处理 多处理器调度或多机调度（多处理器调度或多机调度（MMS:Multi-Machine SchedulingMMS:Multi-Machine Scheduling）不但要解决何时执行任务，而且还要解决在何处执行任务。这就同不但要解决何时执行任务，而且还要解决在何处执行任务。这就同时涉及到任务的分配与调度，也涉及到某一个处理

6、器的资源、网时涉及到任务的分配与调度，也涉及到某一个处理器的资源、网络通信等许多问题，大大增加了问题的难度，已经证明此类调度络通信等许多问题，大大增加了问题的难度，已经证明此类调度多为多为NPNP问题。问题。第8页/共49页二、实时控制二、实时控制 软件领域软件领域n功能测试功能测试n单元测试单元测试n软件设计软件设计控制领域控制领域n性能需求性能需求n模型设计模型设计n算法设计算法设计控制设计控制设计对控制与计算缺乏共同认识对控制与计算缺乏共同认识对控制与计算缺乏共同认识对控制与计算缺乏共同认识第9页/共49页采样周期与性能损失采样周期与性能损失 连续系统的状态方程：控制与状态的不等式约束：

7、终端状态的等式约束：性能指标：离散化后的状态方程：离散化后的性能：性能损失：第10页/共49页指数模型周期分配方法（指数模型周期分配方法（SetoSeto）指数模型(Seto)：多任务优化模型：特点：静态方法，采用了近似的性能指标特点：静态方法，采用了近似的性能指标第11页/共49页弹性任务模型弹性任务模型（EPAA,ButtazzoEPAA,Buttazzo），其中特点：压缩过程中任务的弹性系数始终不变特点：压缩过程中任务的弹性系数始终不变 第12页/共49页动态优先级调整算法动态优先级调整算法(DPAA)(DPAA)将利用率调整区间 划分为 段，逐段对任务利用率进行压缩，压缩过程中任务的弹

8、性系数由当前的利用率来确定，这样，对于那些性能衰减速率变化较大的任务，就有可能争取到更多的处理器资源，从而提高系统整体性能。DPAA算法：第13页/共49页动态优先级调整算法仿真结果动态优先级调整算法仿真结果 任务参数任务参数仿真结果仿真结果第14页/共49页DPAADPAA讨论讨论 该算法不一定针对固定模型的实时控制任务，各种性能损失对于利用率的变化率模型已知的任务，在经过优先级映射后，都可以经过该算法统一调整利用率；与指数模型不同的是，除了可以用于动态分配以外，动态优先级算法的性能损失函数可以是非单调的，在应用中只需要对每一个单调区间进行描述；动态优先级算法实际上是弹性任务的分段线性化压缩

9、，每一段的计算复杂度和弹性算法一样，均为 。实时系统的设计应考虑计算资源的额外开销，否则就会导致舍本逐末的结果。从这一点考虑，在对任务利用率区间分段时，段数不宜过多，分段具有代表性即可。第15页/共49页控制参数根据周期变化的调整控制参数根据周期变化的调整 在线设计：需要大量计算时间，不现实离线设计：在控制算法设计阶段，在采样周期允许范围内选取适当具有代表性的周期点，逐点设计控制器参数并保存，当前周期对应的控制器参数通过查表插值来计算，这对于线性系统来说较为有效。第16页/共49页理想控制任务数字实现假设条件理想控制任务数字实现假设条件 采样任务通常被认为很精确地按某个周期进行采样数据就绪后，

10、控制计算立即执行，执行器在接收到控制计算的结果后要么立即执行输出，要么按照与采样时刻固定的延时输出三个任务自身的执行时间为零 第17页/共49页抖动与延迟定义抖动与延迟定义 定义定义 采样抖动:实时控制任务两个相邻实例的采样间隔变化。设任务的采样间隔序列为 ，其中 ，则采样抖动 。定义定义 计算延迟:实时控制任务实例从采样至任务输出执行完成的时间间隔，。第18页/共49页理想控制任务数字实现假设条件理想控制任务数字实现假设条件 两个实时任务共享处理器两个实时任务共享处理器单速率（单速率（RMRM）调度算法）调度算法 第19页/共49页抖动和延迟对控制性能的影响抖动和延迟对控制性能的影响 控制对

11、象：PID控制：调度算法：RM调度 执行时间：1毫秒采样周期：3、4、5毫秒第20页/共49页抖动和延迟静态补偿抖动和延迟静态补偿 1.将非周期任务用周期服务器进行隔离；2.确定周期任务的周期；3.以尽可能减小上下文切换次数为优化目标，将周期任务在某一时间段上进行调度，形成调度队列；4.建立所有任务在一个宏周期内实例的延迟和抖动列表 ，在每个实例进行补偿。第21页/共49页抖动和延迟静态补偿抖动和延迟静态补偿PIDPID例子例子1.采样 ，查询 ，2.；3.误差4.5.输出执行，数据更新 第22页/共49页静态补偿静态补偿PIDPID仿真结果仿真结果控制对象控制对象PD控制器控制器EDF调度调

12、度 第23页/共49页动态补偿动态补偿单任务实时性能指标单任务实时性能指标线性二次型最优控制 完全可控线性连续系统的状态方程：性能指标：LQ最优控制：系统性能：第24页/共49页单任务实时性能指标单任务实时性能指标线性二次型最优控制 离散系统的状态方程：其中 第25页/共49页多任务性能优化模型多任务性能优化模型多任务性能优化模型：u 调整采样周期，修改控制参数；u 减小采样抖动；u 使计算延迟保持在某一固定值附近，以便于从控制算法进行补偿；第26页/共49页子任务调度思想子任务调度思想一个采样周期内的计算时间:控制量的计算时间只占总计算时间的很小部分;采样以及执行输出指令占用的计算时间几乎为

13、零;计算时间的大部分用于执行一些其它功能如数据标记及安全验证等 子任务调度 将控制任务划分为控制输出 和数据更新 两个子任务 第27页/共49页子任务引起的截止期错失子任务引起的截止期错失完整任务调度：RM子任务调度：FP，出现错失缺点：增加了上下文切换 第28页/共49页子任务、子任务、FPFP调度调度，1.给所有子任务分配 ，2.按截止期单调（DM）算法分配任务优先级，任务截止期越小，优先级越高；3.计算各控制输出子任务的释放时间4.；5.返回2，直至所有不再变化。t:=GetSystemTime();SetPriority(P_CO);LOOP ReadInput(t,y_value);

14、CalculateOutput(t,y_value);WriteOutput(t,u_value);SetPriority(P_Up);UpdateState();t:=t+T;SetPriority(P_CO);SleepUntil(t);END;第29页/共49页子任务、子任务、EDFEDF调度调度t:=GetSystemTime();SetAbsoluteDeadline(t+DCO);LOOP ReadInput(t,y_value);CalculateOutput(t,y_value);WriteOutput(t,u_value);SetAbsoluteDeadline(t+T);S

15、leepUntil(t+DCO)UpdateState();t:=t+T;SetAbsoluteDeadline(t+DCO);SleepUntil(t);END;任务的释放时间在EDF调度中很难分析，将数据更新任务推迟到控制输出任务的截止期释放 第30页/共49页子任务调度仿真结果子任务调度仿真结果控制对象：PID控制：调度算法：FP调度 总执行时间：2.5毫秒采样周期：12、13、14毫秒控制输出时间：0.5毫秒数据更新时间：2毫秒子任务优先级分配结果第31页/共49页子任务调度仿真结果子任务调度仿真结果计算延迟分布采样间隔分布输出对比第32页/共49页三、任务属性调整的意义三、任务属性调

16、整的意义1.弥补根据最坏执行时间确定任务属性的不足2.需要灵活的准入机制 实时控制系统的设计中，我们通常希望其鲁棒性能够使其很好地适应任务采样周期和响应时间的变化，控制器可以被设计为能够在不同的工作方式下切换或具有不同的采样间隔，甚至在必要的时候控制器可以牺牲本回路的性能以减小处理器的负荷。第33页/共49页反馈调度系统反馈调度系统l一般来说，反馈调度要解决的问题包括如何选取合适的控制信号、测量信号和设定点，采用何种控制结构以及适用于哪些过程模型。调度器的目标通过调节控制任务的采样频率，使处理器的利用率保持在某一给定值附近。监视器：监视处理器的负荷状态（截止期错过率、处理器利用率等），并将信息

17、反馈到控制器，控制器：根据当前处理器利用率误差，得出估计利用率的变化量（控制量）QoS执行器：调整任务的服务质量。基本调度器：EDF算法或RM算法。第34页/共49页实时控制任务性能与周期分析实时控制任务性能与周期分析控制对象控制对象采样周期：采样周期：2、12毫秒毫秒PD控制器控制器性能指标性能指标第35页/共49页实时控制任务模糊调度实时控制任务模糊调度设想：设想：对于离散控制系统，在不同对于离散控制系统，在不同的控制阶段，给控制回路赋的控制阶段，给控制回路赋予不同的采样周期：当控制予不同的采样周期：当控制回路的误差较大时，给该回回路的误差较大时，给该回路较小的采样周期，使得其路较小的采样

18、周期，使得其性能损失较小；而当该回路性能损失较小；而当该回路进入稳定阶段以后，增大回进入稳定阶段以后，增大回路的采样周期，在几乎不影路的采样周期，在几乎不影响系统性能的前提下，减小响系统性能的前提下，减小了该实时任务的处理器利用了该实时任务的处理器利用率。率。第36页/共49页实时控制任务模糊调度元素实时控制任务模糊调度元素u实时内核包括处理器、基本调度器及各种任务。控制任务、其它周期任务及非周期任务统一由基本调度器调度，基本调度器的调度算法可以采用单速率（RM）或截止期优先（EDF）算法。处理器的负荷状态表现为截止期错过率或处理器估计利用率，该参数将由监视器反馈给准入控制器。u监视器的作用有

19、两点，首先是监测处理器的负荷状态，将监测到的参数反馈给准入控制器。监视器对处理器负荷状态的监测周期（抽样窗大小）取为任务的宏周期（所有任务周期的最小公倍数）。其次是对实时控制任务状态的监测。u准入控制器的目标是保持处理器性能接近于给定值，根据处理器当前负荷状态与给定性能差值得出利用率的变化量，提供给反馈调度器。第37页/共49页实时控制任务模糊调度元素实时控制任务模糊调度元素u反馈调度器根据准入控制器的控制量和实时控制任务的优先级变化对内核中任务的利用率进行调整。两种实现方式：直接采用原反馈调度系统中的QoS执行器，实时控制任务无法建立QoS与利用率间的关系，给系统中所有需要调整利用率的控制任

20、务分配固定带宽的利用率，控制任务根据各自的需求，在固定带宽内竞争处理器资源。所有任务均无QoS与利用率模型，控制任务和其它任务一样，都依赖各自的优先级竞争处理器资源，在多个控制回路同时出现较大扰动时，控制任务能有效地从其它任务中争取到更大的利用率，反之，其它任务也可以从控制任务中获得更多的处理器资源。第38页/共49页模糊控制规则模糊控制规则位置型控制器 控制规则表：第39页/共49页模糊控制决策表模糊控制决策表控制决策表 第40页/共49页仿真结果仿真结果控制对象控制对象最小采样周期：最小采样周期：4毫秒毫秒PD控制器控制器性能指标性能指标最大采样周期：最大采样周期：15毫秒毫秒计算时间：计

21、算时间：1毫秒毫秒随机干扰随机干扰：0.020.02总利用率：总利用率：0.260.26第41页/共49页仿真结果仿真结果性能对比图 采样周期变化图 第42页/共49页四、具有切换时间的多机调度问题优化模型四、具有切换时间的多机调度问题优化模型火炮联合防空、Agent移动路径规划 第43页/共49页GASAGASA混合优化算法混合优化算法 开始开始设定算法参数和初始温度设定算法参数和初始温度产生贪心个体初始化种群产生贪心个体初始化种群评估当前种群中的个体评估当前种群中的个体GAGA交叉操作交叉操作GAGA变异操作变异操作对各个体进行对各个体进行SASA搜索搜索产生新个体产生新个体以某概率接受新

22、个体以某概率接受新个体SASA搜索结束？搜索结束？SASA退温操作退温操作评估当前种群的个体评估当前种群的个体满足结束条件？满足结束条件？GAGA选择、复制操作选择、复制操作结束结束是是否否是是否否第44页/共49页GASAGASA混合优化算法混合优化算法编码及初始群体编码及初始群体 u 编码：多个基因串编码方法 P P：2 1 10 11 5 3 62 1 10 11 5 3 6 13 7 913 7 9 12 4 8 1412 4 8 14|7 3 47 3 4 执行器执行器1 1 执行器执行器2 2 执行器执行器3 3 任务数任务数u 初始群体：产生贪心算子个体（计算复杂度小，局部最优）

23、初始化初始化将任务置于不可调度队列将任务置于不可调度队列按最小切换时间，处理不可调度队列按最小切换时间，处理不可调度队列统计执行器任务数统计执行器任务数形成第二个基因串形成第二个基因串结束结束是是否否对对 ,找出找出 队列为空？队列为空？将任务分配给最小切换将任务分配给最小切换 时间的执行器时间的执行器第45页/共49页GASAGASA混合优化算法混合优化算法选择、交叉及变异选择、交叉及变异 u 选择：基于线性排序的适应度分配方法（rank-based fitness assignment）最优保存策略 u 交叉：顺序交叉，保留优良个体的任务间顺序关系 u 变异：第一个基因串的变异 第二个基因

24、串变异对某两个基因位进行随机加减 第46页/共49页模拟退火操作模拟退火操作 生成一个与原个体P完全相同的新个体P，对新个体P的每个基因位产生一个随机数，如果该随机数小于某个给定值，则该基因不变；如果大于某个给定值，则记取该基因位。将所有大于给定值的基因倒序排列，并依次安放到相应位置形成新个体P。对新个体进行评估，计算新个体适应度 ，如果新的适应度大于原个体适应度 ，以新个体替换原个体；如果小于 ，则计算 ，以概率 接受新个体；降温 Step1Step1 Step2Step2 Step3Step3 第47页/共49页模拟结果模拟结果 讨论讨论：贪心算法个体产生的时间大约为0.07秒，约为普通遗传算法迭代1/4次的时间在计算过程中偶然会出现简单遗传算法在局部时间段性能超过混合优化算法的现象当问题的规模比较小时，引入贪心个体GASA混合优化策略性能比简单的遗传算法改进不大，有时候甚至可能要差一些 任务数为40，执行器数为8，群体总数50，PIII633/128M/Win2000 第48页/共49页