实时调度及实时控制ppt课件

实时调度及实时控制,1,一、实时任务,a：到达时间s:开始执行时间e:执行结束时间d:截止期T:切换时间C:执行时间,2,一、实时任务调度,硬截止期硬截止期任务用于保证系统的正确运行,通常是周期性的或者相邻的两个任务实例之间具有一个最小间隔时间固截止期通常是非定期任务,具有不确定的到达时间软截止期通常是非定期任务,具有不确定的到达时间,3,周期性任务的调度算法,RM算法单速率算法任务的优先级决定于其周期，周期越小的任务优先级越高，由于任务的周期是固定的，所以该算法是基于静态优先级的；,T1=5，T2=7C1=2，C2=3,4,周期性任务的调度算法,EDF算法最早截止期优先调度算法任务的优先级决定于其绝对截止期，绝对截止期越小的任务优先级越高，EDF是基于动态优先级的。,T1=5，T2=7C1=2，C2=3,5,周期性任务的调度算法,RM和EDF在固定优先级和动态优先级算法中分别是最优的。RM算法只能解决任务截止期等于任务周期时的最优调度，当这个条件不满足时，可以证明截止期单调（DM，DeadlineMonotonic）算法是最优的。,6,非周期性任务的调度算法,7,混和任务的实时调度算法,静态调度后台调度（BackgroundScheduling）:非周期性任务采用先到先服务FCFS策略在周期性任务执行后的空闲时间片调度。为了提高非周期性任务的响应性能，轮询服务器策略设立一个周期任务服务器，专门用于服务非周期任务，在满足其它周期任务截止期的前提下，尽可能地给这个服务器分配服务时间。这种方法实质上是轮询服务。动态调度为了克服基于静态优先级方法无法处理突发事件，基于动态优先级方法可以把任何空闲处理能力（没有周期任务使用）都用于非周期任务，这样既可以实现非周期任务的快速响应特性，又能保证周期任务的实时性。动态优先级交换服务器和动态零星服务器,8,其他问题,共享资源互斥的调度过载处理多处理器调度或多机调度（MMS:Multi-MachineScheduling）不但要解决何时执行任务，而且还要解决在何处执行任务。这就同时涉及到任务的分配与调度，也涉及到某一个处理器的资源、网络通信等许多问题，大大增加了问题的难度，已经证明此类调度多为NP问题。,9,二、实时控制,软件领域功能测试单元测试软件设计,控制领域性能需求模型设计算法设计,对控制与计算缺乏共同认识,10,采样周期与性能损失,11,指数模型周期分配方法（Seto）,指数模型(Seto)：,多任务优化模型：,特点：静态方法，采用了近似的性能指标,12,弹性任务模型（EPAA,Buttazzo）,，,其中,特点：压缩过程中任务的弹性系数始终不变,13,动态优先级调整算法(DPAA),将利用率调整区间划分为段，逐段对任务利用率进行压缩，压缩过程中任务的弹性系数由当前的利用率来确定，这样，对于那些性能衰减速率变化较大的任务，就有可能争取到更多的处理器资源，从而提高系统整体性能。,DPAA算法：,14,动态优先级调整算法仿真结果,任务参数,仿真结果,15,DPAA讨论,16,控制参数根据周期变化的调整,在线设计：需要大量计算时间，不现实离线设计：在控制算法设计阶段，在采样周期允许范围内选取适当具有代表性的周期点，逐点设计控制器参数并保存，当前周期对应的控制器参数通过查表插值来计算，这对于线性系统来说较为有效。,17,理想控制任务数字实现假设条件,采样任务通常被认为很精确地按某个周期进行采样数据就绪后，控制计算立即执行，执行器在接收到控制计算的结果后要么立即执行输出，要么按照与采样时刻固定的延时输出三个任务自身的执行时间为零,18,抖动与延迟定义,定义采样抖动:实时控制任务两个相邻实例的采样间隔变化。设任务的采样间隔序列为，其中，则采样抖动。定义计算延迟:实时控制任务实例从采样至任务输出执行完成的时间间隔，。,19,理想控制任务数字实现假设条件,两个实时任务共享处理器单速率（RM）调度算法,20,抖动和延迟对控制性能的影响,21,抖动和延迟静态补偿,将非周期任务用周期服务器进行隔离；确定周期任务的周期；以尽可能减小上下文切换次数为优化目标，将周期任务在某一时间段上进行调度，形成调度队列；建立所有任务在一个宏周期内实例的延迟和抖动列表，在每个实例进行补偿。,22,抖动和延迟静态补偿PID例子,采样，查询，；误差输出执行，数据更新,23,静态补偿PID仿真结果,24,动态补偿单任务实时性能指标,25,单任务实时性能指标,线性二次型最优控制,离散系统的状态方程：,其中,26,多任务性能优化模型,多任务性能优化模型：,调整采样周期，修改控制参数；减小采样抖动；使计算延迟保持在某一固定值附近，以便于从控制算法进行补偿；,27,子任务调度思想,一个采样周期内的计算时间:控制量的计算时间只占总计算时间的很小部分;采样以及执行输出指令占用的计算时间几乎为零;计算时间的大部分用于执行一些其它功能如数据标记及安全验证等,子任务调度将控制任务划分为控制输出和数据更新两个子任务,28,子任务引起的截止期错失,完整任务调度：RM,子任务调度：FP，出现错失,缺点：增加了上下文切换,29,子任务、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;,30,子任务、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调度中很难分析，将数据更新任务推迟到控制输出任务的截止期释放,31,子任务调度仿真结果,子任务优先级分配结果,32,子任务调度仿真结果,计算延迟分布,采样间隔分布,输出对比,33,三、任务属性调整的意义,弥补根据最坏执行时间确定任务属性的不足需要灵活的准入机制,实时控制系统的设计中，我们通常希望其鲁棒性能够使其很好地适应任务采样周期和响应时间的变化，控制器可以被设计为能够在不同的工作方式下切换或具有不同的采样间隔，甚至在必要的时候控制器可以牺牲本回路的性能以减小处理器的负荷。,34,反馈调度系统,一般来说，反馈调度要解决的问题包括如何选取合适的控制信号、测量信号和设定点，采用何种控制结构以及适用于哪些过程模型。调度器的目标通过调节控制任务的采样频率，使处理器的利用率保持在某一给定值附近。,监视器：监视处理器的负荷状态（截止期错过率、处理器利用率等），并将信息反馈到控制器，控制器：根据当前处理器利用率误差，得出估计利用率的变化量（控制量）QoS执行器：调整任务的服务质量。基本调度器：EDF算法或RM算法。,35,实时控制任务性能与周期分析,36,实时控制任务模糊调度,设想：对于离散控制系统，在不同的控制阶段，给控制回路赋予不同的采样周期：当控制回路的误差较大时，给该回路较小的采样周期，使得其性能损失较小；而当该回路进入稳定阶段以后，增大回路的采样周期，在几乎不影响系统性能的前提下，减小了该实时任务的处理器利用率。,37,实时控制任务模糊调度元素,实时内核包括处理器、基本调度器及各种任务。控制任务、其它周期任务及非周期任务统一由基本调度器调度，基本调度器的调度算法可以采用单速率（RM）或截止期优先（EDF）算法。处理器的负荷状态表现为截止期错过率或处理器估计利用率，该参数将由监视器反馈给准入控制器。监视器的作用有两点，首先是监测处理器的负荷状态，将监测到的参数反馈给准入控制器。监视器对处理器负荷状态的监测周期（抽样窗大小）取为任务的宏周期（所有任务周期的最小公倍数）。其次是对实时控制任务状态的监测。准入控制器的目标是保持处理器性能接近于给定值，根据处理器当前负荷状态与给定性能差值得出利用率的变化量，提供给反馈调度器。,38,实时控制任务模糊调度元素,反馈调度器根据准入控制器的控制量和实时控制任务的优先级变化对内核中任务的利用率进行调整。,两种实现方式：直接采用原反馈调度系统中的QoS执行器，实时控制任务无法建立QoS与利用率间的关系，给系统中所有需要调整利用率的控制任务分配固定带宽的利用率，控制任务根据各自的需求，在固定带宽内竞争处理器资源。所有任务均无QoS与利用率模型，控制任务和其它任务一样，都依赖各自的优先级竞争处理器资源，在多个控制回路同时出现较大扰动时，控制任务能有效地从其它任务中争取到更大的利用率，反之，其它任务也可以从控制任务中获得更多的处理器资源。,39,模糊控制规则,位置型控制器,控制规则表：,40,模糊控制决策表,控制决策表,41,仿真结果,42,仿真结果,性能对比图,采样周期变化图,43,四、具有切换时间的多机调度问题优化模型,火炮联合防空、Agent移动路径规划,44,GASA混合优化算法,45,GASA混合优化算法编码及初始群体,编码：多个基因串编码方法,P：2110115361379124814|734执行器1执行器2执行器3任务数,初始群体：产生贪心算子个体（计算复杂度小，局部最优）,46,GASA混合优化算法选择、交叉及变异,选择：基于线性排序的适应度分配方法（rank-based