5-网络控制系统的调度方法

2023/12/211基于网络的智能控制吴迎年wuyingnian@126.com2023/12/21北京信息科技大学自动化学院2网络控制系统调度方法1、网络控制系统中的调度问题2、实时系统及其任务调度3、静态RM调度算法

4、动态EDF调度算法5、网络控制系统调度与控制的协同设计6、TRUETIME

仿真工具箱2023/12/21北京信息科技大学自动化学院3网络控制系统调度方法网络控制系统研究内容:（1）对网络的控制(ControlofNetwork)：对网络节点、网络数据流量等的调度与控制，是对网络自身的控制,其目的是为了提高网络的服务质量（QoS,QualityofService）；（2）通过网络进行控制（ControlthroughNetwork）：指控制系统的各节点（传感器、控制器、执行器等）之间通过网络进行连接并传输数据，针对网络的不确定特性，通过设计先进的控制算法来提高整个网络控制系统的质量（QoP,QualityofcontrolPerformance）。2023/12/21北京信息科技大学自动化学院4网络服务质量

:指网络的吞吐量，传输效率，误码率，时延可预测性和任务的可调度性等。提高网络服务质量的方法

:网络的体系结构设计，通信介质的选择，先进的网络调度方法等，其中网络调度可以在网络结构与通信介质等物理性质确定的情况下，有效地提高网络的服务质量，因此是网络控制系统中研究如何提高网络服务质量的一种受到普遍重视的方法。2023/12/21北京信息科技大学自动化学院55.1网络控制系统的调度问题5.1.1网络控制系统的调度1、网络调度问题：指网络中的节点在共享的网络资源中发送数据，并且发生碰撞时，规定数据包以怎样的优先级（顺序）和何时发送数据包的问题。研究层面：（1）设计介质层网络的通信协议，称为协议层调度；（2）设计应用层的节点优化调度算法，称为应用层调度。2023/12/21北京信息科技大学自动化学院62、协议层调度：指数据链路层通过一个链路活动调度器控制现场装置对总线的访问，通常是网络接口设备按照特定的协议规范来决定那些并发数据包的发送顺序。特点：通过特定的网络协议来实现某些调度算法的，因此调度缺乏灵活性，只能适应少数的算法。2023/12/21北京信息科技大学自动化学院7

网络协议是调度研究的基础,了解现有网络协议特点对改进工作很必要.根据控制网络的时间延迟特性,网络可分为三类:

随机网络、有界网络和常值网络.

信息在网络上传输产生的时延,如果是随机的,则网络为随机网络;如果是有界的,则为有界网络;如果维持定值,则为常值网络.Ethernet、令牌网和CAN分别是它们的典型代表.2023/12/21北京信息科技大学自动化学院83、应用层调度：指上层（传输层以上）的应用程序根据需要来主动地决策数据的发送规则，该规则与具体的网络协议无关。网络的作用仅仅是用于传输数据，不能实现调度决策。目前应用层的网络调度方法主要有4种：（1）借用CPU调度方法（2）设计网络调度协议（3）调度与控制协同设计（4）反馈控制实时调度2023/12/21北京信息科技大学自动化学院9（1）借用CPU调度方法：目前借用单处理器的网络调度方法主要有两种：（a）静态调度：对于调度算法而言，各任务的发送规则是事先确定的，如时限、计算时间、优先权关系、任务释放时间等。以RM（RateMonotonic）算法及其衍生算法为代表。（b）动态调度：任务的时间约束关系并没有完全确定，新任务的到达时间是未知的，在网络资源充足的环境下，系统仍然能够保证所有的任务时限。以EDF（EarliestDeadlineFirst）算法及其衍生算法为代表。2023/12/21北京信息科技大学自动化学院10（2）设计网络调度协议借鉴单处理器动态调度的思想，结合控制系统的特点，设计开发新的网络节点数据发送规则。其特点是在网络控制系统稳定的前提下，保证网络节点的动态优化调度。典型方法是Walsh等人提出的一种给时间关键信息动态分配网络资源的TOD(try-once-discard)协议。2023/12/21北京信息科技大学自动化学院11（3）调度与控制协同设计指在网络控制系统设计中，将系统控制与网络优化统一考虑，研究在满足系统控制指标条件下的网络调度方法，以及同时满足系统控制指标优化和网络可调度性的采样周期的选择方法。2023/12/21北京信息科技大学自动化学院12（4）反馈控制实时调度一般实时调度算法是一种开环调度算法，即一旦调度确立，就不能根据连续的反馈来进行相应地调整。反馈控制实时调度指将反馈控制的思想应用到实时调度算法中，根据网络反馈回来的信息来调节任务或调度器的参数，从而有效地提高网络系统的传输性能。该研究方法的难点在于分布式环境中，如何有效地同步获取反馈信息。2023/12/21北京信息科技大学自动化学院135.1.2NCS调度中的几个基本概念图1实时网络传输任务的时间参数图2023/12/21北京信息科技大学自动化学院14（1）到达时间（ai）：数据包形成，开始加入发送队列，准备发送。此为一个发送周期的开始。（2）开始发送时刻（si）：数据包开始发送的时刻。（3）阻塞时间（bi）：数据包达到后，等待直至开发发送所需要的时间，即bi=si-ai。网络数据包的传输中任务是非抢优的，bi由两部分组成：bh,i：等待所有更高优先级的任务传输完毕的时间bl,i：正在发送的较低优先级的任务发送完毕所需要的时间其最大值分别记为：2023/12/21北京信息科技大学自动化学院15（4）传输时间（ci）：数据包由源地址经网络传送到目的地址所需要的时间，一般由数据包的大小和网络介质的速率决定。（5）完成时间（fi）：一次传输结束的时间。（6）传输时延（τi）：数据包到达队列至数据包完成数据包传输完成之间的时间。显然

（7）时限（di）：为保证NCS的性能，传输必须在某个时间之前完成，该时间就称为时限。2023/12/21北京信息科技大学自动化学院16（8）网络占用率（U）：其中NCS中N个对象的传感器按周期pi

发送数据。（9）可调度性：指网络控制系统的所有数据传输都能在任务时限内完成。2023/12/21北京信息科技大学自动化学院175.1.3网络调度的几种基本方法1、协议层调度2、TOD网络调度协议3、反馈控制实时调度。2023/12/21北京信息科技大学自动化学院18协议层调度方法：1、Ethernet使用载波侦听多路访问/冲突检测（CSMA/CD）网络协议，为随机网络的代表。2、令牌网是有界网络的代表,分为令牌总线和令牌环两类.ControlNet、MAP(IEEE802.4)、Profi-bus都属于令牌总线。3、CAN通信协议采用多主竞争机制（CSMA/AMP）网络协议，是常值网络的代表。2023/12/21北京信息科技大学自动化学院19TOD（Try-OnceDiscade）网络动态调度协议1、MEF-TOD协议内容：（1）NCS中每个节点都有一个优先级，该优先级与误差范数成正比，该误差指最近发送的数据值与实际测量数据值的差；（2）误差最大的节点拥有发送数据的最大优先级；（3）如果两个或更多的节点信息具有相同的优先权，则按事先约定的规则来解决这种碰撞。2023/12/21北京信息科技大学自动化学院202、最大允许传输时间间隔MATI（MaximumAllowableTransferInterval）：传输时间间隔指NCS访问网络的时间间隔。可以证明，在MEF-TOD或静态调度下，某个NCS系统，当MATI小于某个与NCS性能相关的数值时，NCS系统是全局指数稳定的。2023/12/21北京信息科技大学自动化学院21（1）大多数实时调度算法是开环的调度算法，不能根据负载变化的情况进行动态调节以提高系统的性能；（2）开环调度的决策依据是基于对任务参数的最差情形估计得到，因此系统的冗余度太大，导致系统的占有率不足；（3）对于软实时系统，许多情况下应根据负载参数的平均水平（如平均执行时间）来做出相应的决策，以此来动态地处理有界的瞬时负载；（4）反馈调度能够根据反馈回来的信息有效地调节任务或调度器的参数，从而提高系统的性能；对于资源不足（过载）的情况下的软实时系统，提供了较好的解决方案。反馈控制实时调度：2023/12/21北京信息科技大学自动化学院22（1）被控量（被测量）：网络占用率根据：取决于系统的目标。控制系统的各个任务的数据在网络上传输时要受到网络带宽的限制，对于软实时系统来说，适当地丢弃数据包同样能够保证系统的性能，因此可以使用任务对网络资源的需求作为受控量。（2）控制量：任务提交时对网络占用率的需求根据：控制量必须能够影响被控变量的值。（3）参考输入：所有调度任务网络占用率的期望值Us反馈调度器：2023/12/21北京信息科技大学自动化学院23图2NCS反馈调度器结构任务监视器控制器调度器任务过滤器累加器Us+_任务控制网络2023/12/21北京信息科技大学自动化学院241、Monitor任务监视器监控待传输的任务，计算任务的实际网络占用率。2、累加器把监视器得到的数据与网络占用率期望值累加。（1）（2）2023/12/21北京信息科技大学自动化学院253、PID控制器把误差值转化为任务需求的网络占有率，从而使得实际网络占用率尽可能接近设定的期望值。（1）当时，说明网络即将饱和，应该减少任务数；（2）当时，说明网络资源充足，可以增加相应的任务数。（3）其中IW为积分项的时间窗口，DW为微分项的时间窗口。2023/12/21北京信息科技大学自动化学院264、任务过滤器根据PID控制器的输出来增加或减少输入任务的数量。5、EDF调度器按RM或EDF算法对各个任务进行调度发送。2023/12/21北京信息科技大学自动化学院275.2实时系统及其任务调度5.2.1实时系统概述1、实时系统：在确定的时间内执行计算或处理事务并对外部的异步事件做出响应的计算机系统。实时系统从输入时刻到输出时刻之间的时滞必须小到可接受时限内。2023/12/21北京信息科技大学自动化学院282、分类标准：系统对时间要求的严格程度。（1）硬实时系统：如果一个系统未能在指定时间内就某一事件做出响应而失败，则该失败被认为是一种全面的系统失败。一般用于航天系统或核反应堆系统，系统较复杂。（2）软实时系统：系统对某些任务的响应时间允许一定程度上的超时限，而不会导致系统的失败。大多数系统都属于软实时系统，网络控制系统通常是软实时系统。2023/12/21北京信息科技大学自动化学院293、实时系统组成：在实时系统中，一个应用通常由一组任务构成，每个任务完成应用中的一部分功能，组合后为用户提供特定的服务。例如在一个计算机控制的飞行器飞行控制应用包括：数据采集任务自动导航任务控制任务2023/12/21北京信息科技大学自动化学院304、实时系统特点：时间约束性：指各任务不仅应满足相互之间的拓扑约束和时序约束，还要遵从各自的绝对时间约束和相对时间约束。可预测性：可预测性是指系统能对实时任务的执行时间进行判断，确定是否能够满足任务的时限要求。可靠性：大多数实时系统要求有较高的可靠性，可靠性己成为衡量实时系统性能的不可缺少的重要指标。与外部环境的交互作用性：外部物理环境往往是被控子系统，两者相互作用构成完整的实时系统。2023/12/21北京信息科技大学自动化学院315、实时调度：是实时系统的核心，为不同实时并发任务使用独占的、有限的资源确定一种调度策略，以使所有实时任务的处理都不错过截止时间。实时调度算法特征：（1）硬实时与软实时（2）抢优与非抢优（3）动态与静态（4）集中与分布2023/12/21北京信息科技大学自动化学院32（1）硬实时与软实时

硬实时：必须保证所有时限都要被严格地满足，否则将会导致严重的后果。软实时：并不要求所有的时间要求均严格地满足，可忍受一种最大近似。（2）抢优与非抢优

抢优：允许在更高优先级的任务到来时暂时挂起当前的任务，以后在没有更高优先级的任务要运行时对恢复它的处理。非抢优：一旦一个任务启动后，它将占有处理机直到执行结束。2023/12/21北京信息科技大学自动化学院33（3）动态与静态

动态：在运行期间进行调度。静态：在运行前事先就调度好的。（4）集中与分布

集中：用一台机器来收集所有的信息并做出所有的决定。分布：各个处理机可以独立做出决定。2023/12/21北京信息科技大学自动化学院345.2.2实时调度与网络调度1、基本概念：（1）调度：给定一组实时任务和系统资源，确定每个任务何时何地执行的整个过程。（2）实时调度：在确定的时间内执行计算或处理事务并对外部的异步事件做出响应的计算机系统。也可称为CPU（处理器）调度算法，基本上分为两类：静态调度和动态调度。

静态调度：RM（RateMonotonic）调度算法及其衍生算法是静态调度算法。

动态调度：EDF（EarliestDeadlineFirst）调度算法及其衍生算法是静态调度算法。2023/12/21北京信息科技大学自动化学院352、网络调度与实时调度比较相同点：都有共享资源的限制。实时系统：多个任务不能同时使用CPU的计算资源网络系统：多数据共用一条网络传输介质不同点：实时系统：调度是可以抢优的网络系统：调度是可以非抢优的2023/12/21北京信息科技大学自动化学院36网络调度与实时调度比较网络调度CPU调度任务数据包的传输任务的执行pi数据包的传输周期任务执行周期ci数据包的传输时间任务的计算时间fi数据包传输的结束时刻任务执行的结束时刻di数据包传输的时限任务执行的时限U网络使用率CPU使用率抢优非抢优可抢优2023/12/21北京信息科技大学自动化学院375.3静态RM调度算法1、RM算法介绍：

RM（RateMonotonic）调度算法，中文称为“比率单调调度算法”，是实时系统中单处理器的基于优先级的静态调度算法5.3.1实时系统的RM调度算法2023/12/21北京信息科技大学自动化学院382、RM算法描述：（1）根据任务的周期hi分配优先权：任务的周期越短，其优先权越高；（2）任务的优先权在任务执行之前已经确定，不会随时间改变，因此是一种静态的调度算法；（3）实时系统中的RM算法是抢优的，即当前执行的任务会被新到达的优先级更高的任务打断。（4）RM算法在所有的固定优先级分配算法中是最优的；（5）RM算法是稳定的：确保优先级高的任务先执行。2023/12/21北京信息科技大学自动化学院393、RM可调度定理：一组n个相互独立、可抢优的实时周期任务，用RM算法的可调度条件为任务的总占有率U满足如下不等式：（1）其中ci

为任务所需的执行时间，hi

为任务的周期。2023/12/21北京信息科技大学自动化学院40例5.1：两个并发的周期实时任务，执行时间为c1=c2=3ms，任务周期为h1=4ms，h2=6ms，任务时限d1=h1，d2=h2。计算RM算法的可调度性。解：任务的占有率为：由RM算法的可调度条件可知用RM算法不可调度。2023/12/21北京信息科技大学自动化学院41说明：（1）根据RM算法，由于h1<h2，则任务1的优先级高于任务2的优先级，因此两个任务同时到达时，任务1先处理；（2）经过3ms任务1处理完毕，进行任务2的处理；（3）任务1处理1ms后，任务1的下一个周期来到，于是打断任务2的执行，进行任务1的处理；（4）如此反复，结果为任务1所有的任务周期都没有超过时限要求，但任务2所有的周期任务都超过了时限的要求。2023/12/21北京信息科技大学自动化学院424、RM算法缺点：（1）对非周期任务的调度效率低；（2）不能有效的对非调和的周期性操作进行调度；（3）不能灵活地处理操作调用时资源需求的变化。

总体而言，静态调度在资源的利用率和保证运行时对资源的访问之间进行了折衷，限制了实时系统适应系统状态和配置变化的能力。2023/12/21北京信息科技大学自动化学院435.3.2NCS的RM调度算法1、算法描述：（1）指非抢优的RM调度算法；（2）与实时系统的抢优式调度算法相比，唯一的区别就是网络RM调度算法中，任务的执行是非抢优的，即当前执行的任务不会被新到达的优先级更高的任务打断，直到该任务执行完，才能执行队列中等待的高优先级任务。2023/12/21北京信息科技大学自动化学院442、非抢优RM可调度定理：一组n个相互独立、非抢优的实时周期任务（其优先级按下标值递减，下标i为1任务的优先级最高，下标i为N任务的优先级最低），其可调度条件为对于所有的，都满足如下不等式：（2）其中为任务被低优先级任务阻塞的最差情形的阻塞时间，即（3）2023/12/21北京信息科技大学自动化学院45例5.2同样对于例5.1，对于任务1，即i=1，应用非抢优RM可调度定理，有对于任务2，即i=2，应用非抢优RM可调度定理，有由非抢优RM算法的可调度条件可知：用非抢优RM算法不可调度。2023/12/21北京信息科技大学自动化学院46说明：（1）根据RM算法，由于h1<h2，则任务1的优先级高于任务2的优先级，因此两个任务同时到达时，任务1先处理；（2）经过3ms任务1处理完毕，进行任务2的处理；（3）任务1处理1ms后，任务1的下一个周期来到，但是对于非抢优调度，任务1不能打断任务2的执行，于是继续进行任务2的处理；（4）任务2再经过2ms后处理完毕，于是进行任务1的处理；（5）如此反复，结果为任务1所有的任务周期都超过了时限要求，但任务2所有的周期任务都没有超过时限的要求。2023/12/21北京信息科技大学自动化学院475.4动态EDF调度算法1、EDF算法介绍：

EDF（EarliestDeadlineFirst）调度算法，是实时系统中单处理器的基于优先级的动态调度算法。中文可称为“最小时限优先”动态调度算法。5.4.1实时系统的EDF调度算法2023/12/21北京信息科技大学自动化学院482、EDF算法描述：（1）根据任务距离时限要求的长度(di-ci)来分配任务的优先级：距离时限越小的任务获得的优先级越高；（2）任务的优先权不是固定不变的，而是随时间变化的，任务的优先级相对于时间是不确定的；（3）实时系统中的EDF算法是抢优的，即当前执行的任务会被新到达的优先级更高的任务打断。（4）EDF调度算法是所有可抢优式调度算法中最优的：即EDF算法无法调度的任务集，其他任何优先级调度算法都无法调度。（5）EDF调度算法不稳定：任务集过载时无法预料那些任务超时限。2023/12/21北京信息科技大学自动化学院493、EDF可调度定理：一组n个相互独立的实时周期任务，用EDF算法的可调度条件为任务的总占有率U满足如下不等式：（4）其中ci

为任务所需的执行时间，hi

为任务的周期。2023/12/21北京信息科技大学自动化学院50例5.3：两个并发的周期实时任务，执行时间为c1=c2=3ms，任务周期为h1=6ms，h2=4ms，任务时限d1=h1，d2=h2。计算EDF算法的可调度性。解：任务的占有率为：由EDF算法的可调度条件可知用EDF算法不可调度。2023/12/21北京信息科技大学自动化学院51说明：（1）根据EDF算法，由于h2<h1，则任务2距离时限要求更小，其优先级高于任务1的优先级，因此两个任务同时到达时，任务2先处理；（2）经过3ms任务2处理完毕，进行任务1的处理；（3）任务1处理1ms后，任务2的下一个周期来到，但由于此时任务1距离时限的要求为2ms（6ms-3ms-1ms），而任务2新的任务周期距离时限要求为4ms，因此任务1的优先级高，任务1继续执行；（4）如此反复，结果为任务1和任务2都有超过时限要求的现象发生。2023/12/21北京信息科技大学自动化学院52（5）与RM算法比较，此时任务1获得了更多的资源，即EDF算法对资源的分配更加均衡。（6）由于软实时系统在某种程度上能够承受部分的任务超过时限的要求，因此EDF算法的均衡调度对于软实时系统任务的保证是很重要的。2023/12/21北京信息科技大学自动化学院534、EDF算法优缺点：（1）克服了RM的利用率限制；（2）可以处理调和与非调和周期的情况；（3）可以在单独静态优先级水平上分发操作而不需用频率来确定操作的优先级。（4）需要较高的系统开销来在运行时对操作进行评估。2023/12/21北京信息科技大学自动化学院545.4.2NCS的EDF度算法1、算法描述：（1）指非抢优的EDF调度算法；（2）与实时系统的抢优式调度算法相比，唯一的区别就是网络EDF调度算法中，任务的执行是非抢优的，即当前执行的任务不会被新到达的优先级更高的任务打断，直到该任务执行完，才能执行队列中等待的高优先级任务。2023/12/21北京信息科技大学自动化学院552、非抢优EDF可调度定理：令为有n个任务的任务集，其中是一系列按周期非递减顺序排列的周期性任务，ci

为任务Ti

的最长执行时间，hi

为任务Ti

的周期，di=hi

为任务Ti

的时限，则当且仅当以下条件成立，T

在非抢优EDF调度算法下可调度：（6）（5）证明略。2023/12/21北京信息科技大学自动化学院563、非抢优EDF可调度分析算法：依据非抢优EDF可调度定理给出的实用的可调度分析算法。例5.5：设实时系统中有如下4个任务，任务的时间属性如表1所示。表1任务时间属性idi/mshi/msci/ms1441266238824161622023/12/21北京信息科技大学自动化学院57

di=hi，应用时限等于周期的非抢优EDF可调度判定算法，判断该任务集是否可调度。令处理器利用率：表2中给出了取不同值时任务集的时间需求关系。由表中数据可以看出，i取值不同时，均满足可调度条件。2023/12/21北京信息科技大学自动化学院58表2i

取不同值时任务集的时间需求关系i252375415112023/12/21北京信息科技大学自动化学院59（1）NCS是由网络和控制组成的控制系统，其闭环性能不仅依赖于控制算法的设计，还依赖于对网络资源的合理调度。（2）合适的传输协议和调度策略可以保证网络的服务质量。（3）NCS中的采样周期同时涉及控制与调度两个方面，因此，综合考虑控制与网络调度两个方面指标的NCS中采样周期的优化选择，就是调度与控制协同设计的一个基本的途径。5.5网络控制系统调度与控制的协同设计2023/12/21北京信息科技大学自动化学院605.5.1具有网络时延的NCS模型对于线性时不变系统，一个网络控制子系统Loopi的系统模型表示如下：（7）（8）2023/12/21北京信息科技大学自动化学院61假如网络时延小于一个采样周期hi

，相应系统（7）（8）的离散模型为：（9）（10）（11）式中Li为增益矩阵。2023/12/21北京信息科技大学自动化学院62每个控制子系统的性能通过性能指标函数：式中Qi

为正半定矩阵。（12）2023/12/21北京信息科技大学自动化学院635.5.2NCS采样周期的优化1、优化原因：NCS采样周期时既受控制对象稳定性的约束，也受网络可调度性约束。解决这个矛盾的方法是在一定约束条件下取得总体性能的折中。2023/12/21北京信息科技大学自动化学院642、优化模型：（1）目标函数：（13）pi

为权系数，Ji

是各控制回路的性能指标函数。（2）系统稳定性条件（14）2023/12/21北京信息科技大学自动化学院65（3）调度约束条件EDF调度算法（定理5.4）：（16）（15）RM调度算法（定理5.2）：（17）2