1、1基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化摘要本文在对 TTP 通信协议进行研究的基础上，发现嵌入式实时系统通信过程中的消息调度算法只考虑消息的可调度性而没有对全局延迟进行考虑的问题，从而提出基于可调度性及全局延迟的实时通信的总线访问优化的研究课题，随后对实时通信总线的访问优化算法进行了研究，其中包括：静态单消息算法、静态多消息算法、动态消息分配算法以及动态数据包分配，并对可调度性的判断依据进行了说明，最后通过研究现有可调度性最优算法，从而给出改进后的算法描述并加以实现。关键字：TTP 协议；可调度性；全局延时；嵌入式系统实时通信；总线优化3ABSTRACTBased o
2、n the communication protocol TTP study, found that the process of embedded real-time system communication message scheduling algorithms can only consider the scheduling of messages without delay to the overall issue to consider in order to propose a delay based on scheduling and Global the bus acces
3、s optimization of real-time communications research, followed by access to real-time communication bus optimization algorithm is studied, including: Static Single message Allocation algorithm, Static Multi-message Allocation algorithms, Dynamic Message Allocation algorithms and Dynamic Packet Alloca
4、tion algorithms , and can scheduling judgments based are described, and finally through the study of optimal scheduling algorithms currently available, and to be implemented in order to describe the algorithm gives improved.Keywords：TTP；Schedulability；WCGD；Embedded real-time communication system；Bus
5、 optimization目录第一章 绪论 .11.1 课题背景 .11.2 国内外研究现状 .31.2.1 调度与控制的分开设计 .31.2.2 调度与控制的协同设计 .51.3 课题研究主要内容 .6第二章 基于 TTP 协议及其消息调度原理简介 .82.1 事件触发系统与时间触发系统 .82.2 基于 TTP/C 的时间触发高可靠嵌入式实时系统的实现机制 .102.2.1 基于 TTP/C 的时间触发高可靠系统的物理实现机制 .102.2.2 TTP/C 所采用的帧类型和作用 .122.2.3 时间触发高可靠嵌入式系统的调度机制 .132.2.4 TTP/C 结点的组合能力和采用的容错机
6、制 .14第三章 实时通讯总线访问优化算法介绍及改善 .163.1 消息调度算法简介 .163.1.1 静态单消息 .163.1.2 静态多消息 .173.1.3 动态消息分配 .183.1.4 动态数据包分配 .203.2 消息调度优化其可调度性 .213.3 消息全局延时优化 .24第四章 算法实现与仿真结果 .264.1 可调度性最优算法 .264.2 全局延迟最优算法 .274.3 可调度性及全局延迟近似最优算法 .294.4 仿真结果 .31第五章 总结 .33基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化1第一章 绪论1.1 课题背景随着网络技术以及和数字信息技术的
7、高速发展，在信息家电、医疗仪器、智能汽车、工业控制、通信设备各个领域中，嵌入式系统无处不在。随着网络技术的飞速发展，在许多嵌入式应用中，往往包含许多设备，譬如只能中央空调，这时分布式系统就是实现这种系统最方便、最现实的方法 1。由于分布式系统具有如下特点：时间关键的任务放在不同的 CPU 中可以更容易保证满足它的死线要求；把处理器放在设备级上更便于实现设备之间的接口；如果系统中包含从供应商购买的几个设备或系统，它们之间也含有自己的CPU，或者还包含有通信接口，通常不可能把系统的任务放到这些设备中，或者相反把设备的任务放到系统中；使用几个小 CPU 比使用一个大 CPU 更便宜；分布式的系统能够
8、利用本身的高度容错性使得在高性能领域分布式系统系统中具有得天独厚的优势。所以，许多嵌入式系统利用分布式系统实现，在分布的处理器之间利用通讯链路连接起来，数据链路可以是高速并行数据总线（紧耦合型） ，也可以是串行数据链路。但是，随着电控单元的增多、功能日益复杂、网络通信数据量不断增大、要求更高的传输带宽、通信数据传输的高实时性和高可靠性等问题的出现，就需要一种更新、更可靠和更实时的高速通信网络技术来满足上述技术要求。目前，符合高带宽，实时性特点的总线类型有很多，其中 TTP（Time-Trigger Protocol）总线技术是极具发展潜力的总线之一。TTP 是分布式嵌入系统的一种总线访问协议，
9、一般使用于对安全性有高要求的分布式嵌入系统中。而对于运行在分布式嵌入系统中的实时任务是否能够在满足时限的前提下完成，这取决于分布式节点间的消息通信情况。在已有文献中，可调度性是衡量实时系统的可预测性指标之一，其值越大则说明该系统的实时任务越不易错失其时限，则其安全性能够得到更好的保障。而运行在分布式嵌入系统上的周期任务集（链）中第一个任务开始到最后一个任务结束的时间间隔称为该任务集（链）的全局延迟，该值越小那么说明系统到下一次周期任务集（链）开始执行时刻的时间间隔越大，而该时间间隔可以用于进行其他操作，如：非周期任务的处理；让系统处于待机状态，达到节能的目的。而在以往的实时通信中的总线访问优化
10、，往往只注重系统中的可调度性或全局延迟的优化，而忽略该优化过程中对另一个指标的影响。如在文献1中基于TTP协议的总线访问优化算法就存在这样的问题。其分布式嵌入系统架构如图1所示 2：图1.分布式嵌入系统的节点间通信共享同一总线示意该系统中，所有分布节点间的通信采用 TDMA（Time-Devision-Multiple-access）方式进行消息传递。处于 N0 节点上的实时任务若需要与 N1 节点上的任务进行通信，则需要先将传输的消息放置发送队列中，当总线的使用时间片轮到 N0 使用时，N0 再依次从消息发送队列中取出消息放置到总线上进行传输。最后，位于总线上的消息被 N1 节点获取，放置到
11、自己的接受消息缓冲区中进行消息重组，最后在提供给需要使用该消息的任务使用。为了满足实时任务的时限要求，消息传输的调度起到了至关重要的作用。消息传输的调度一方面影响了该系统中实时任务集合的可调度性（该定义详见1） ，同时也影响到了整个实时任务集合在最坏情况下的全局延迟(WCGD)（该定义详见5） ，因此，如何在消息调度过程中，实现任务集合具有最大可调度性的同时，而且还能得到最优或者近优的全局延时（WCGD ） ，这是本课题研究的主要内容。基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化31.2 国内外研究现状计算机控制的发展 f6_iol 至今主要经历了以下几个阶段:传统的集中式控
12、制系统、七十年代中期发展起来的集散控制系统、八十年代末发展起来的现场总线控制系统、九十年代发展起来的基于以太网的控制系统。网络控制系统中，网络调度就是对网络中信息的调度。目前网络控制系统中信息调度的研究主要分为调度与控制的分开设计和调度与控制的协同设计 3-5。1.2.1 调度与控制的分开设计 在 NCS 的研究中，一类研究是针对通信网络，研究提高网络服务质量的信息调度方法;另一类研究是在一定的网络信息调度方法基础上，研究提高 NCS 性能的控制方法。因此，信息调度方法对改善 NCS 性能起着很大的作用。根据信息对实时性的要求，信息调度分为静态调度(又称离线调度)、动态调度(又称在线调度)和混
13、合调度。（1） 静态优先级调度目前静态调度算法很多，本文着重介绍以下几种典型的算法以及算法的改进。速率单调静态优先级调度(Rate Monotonic Scheduling Model)算法的调度优先级由任务周期确定，在任务周期等于时限的同步实时任务系统中是最佳静态调度算法。但是该算法具有调度判定具有指数时间复杂度、对任务的执行周期限制的过于严格、只能处理具有固定周期的任务等缺点。鉴于上述缺点Lehoczky 等提出了扩大调度可行性条件的 RM 算法。Sha 等考虑到任务的阻塞，给出了非抢占服务方式下 RM 算法的可调度条件。叶明等基于 RM 算法提出了一种新的实时调度算法(Hard Real
14、-time Communication Scheduler, HRTCS)。文远保等针对任务的周期和调优先级关系不固定的流媒体提出了改进的 RM 算法。截至时间单调调度模型(Deadline Monotonic Scheduling Model)策略的任务优先级由任务时限来决定。该调度算法要防止任务越过其时限而得不到调度，从而影响系统的实时性。当任务周期和时限相同或者所有同步周期性任务时，DM算法都是最佳静态调度算法。由 Hong 等提出的基于时间窗的静态带宽调度算法避免了数据在网络传输过程中产生干扰和数据冲突。Hong 等还将该调度方法应用于循环服务型 NCS和 CAN 网下的 NCS 中。
15、刘鲁源等鉴于该调度方法只限于调度网络中的周期数据，提出基于同步相和异步相的时间窗调度算法，使非周期数据也可以采用该基于时间窗的静态调度算法 6-8。（2） 动态优先级调度在动态优先级调度算法中，任务的时间约束关系并没有完全确定，新任务的到达时间是未知的。下面介绍几种经典的动态优先级调度算法。Liu 和 Layland 提出的时限最早的任务优先调度(Earliest deadline first scheduling，任务优先级是任务时限与任务执行时刻的差，该算法对同步周期任务组是最佳的动态调度算法。鉴于 EDF 是抢占式调度算法，任务间的切换时需要大量开销。B aker 给出了非抢占士服务方式
16、下 EDF 算法的可调度性条件。张惠娟等提出了一种基于 EDF 算法的优先级驱动实时调度算法，较大程度地克服了 EDF 算法在多处理器系统中的调度缺点。刘怀等提出了基于 EDF 算法的容错调度算法。张奇智等采用非中断的 EDF 调度方法来改善周期性数据帧的端到端延迟。洪艳伟等提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。最小松弛优先调度(Least laxity first)和 EDF 算法可看作同类型的调度算法，任务优先级是完成时限和任务执行时刻的差再减去周期任务的执行时间。LLF 算法尽量避免了长周期任务的频繁等待、执行，具有较小的抖动性。最大误差优先一尝试一次丢弃(most
17、 error first-try once discard)是 Walsh 等人提出的基于在线获取的网络诱导传输误差和动态分配网络带宽的调度算法。Otanez 等人提出的基于死区的动态调度在确保系统性能的基础上动态地丢弃一定比率的数据，以减轻网络的负荷。但是当多个获准访问网络的数据包同时竞争网络资源时，该策略不能确定数据包发送的优先级。基于业务平滑的动态调度是 Kewon 等利用业务平滑的技术控制 Ethernet 网的通信量，通过在 Ethernet 网的 UDP( TCP/ IP)层和 MAC 层插入定速率业务平滑器和自适应业务平滑器以限定 MAC 层数据包的到达速率，并且保证网络诱导时基
18、于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化5延的有界性，从而提高网络的服务质量。Cena 等提出的优先级提升一分布式优先级排队调度(PP-DPQ)可以保证实时数据传输最大间隔具有确定上界，非实时数据在传输中公平地竞争网络资源。基于时间窗的动态调度(Dynamic Time Window)是 Raja 对基于时间窗的静态调度算法进行改进，提出优先级循环服务和动态时间窗的带宽分配策略 9-10。模糊动态调度是白涛等将模糊控制理论引入到 NCS 信息调度中，利用基于IF2THEN 规则的模糊逻辑确定数据传输的优先级。（3） 混合调度Zuberi 等针对 CAN 下网络控制系统，提出
19、混合通信调度(MTS) 策略。在设计调度策略时，考虑到数据实时性要求不同，可以分别采用不同的调度策略，以提高网络资源的可调度性。Tabuada 等给出的退火控制任务的事件触发实时调度是基于有反馈事例的事件触发调度器，并且给出了它如何保证系统性能的条件。1.2.2 调度与控制的协同设计 目前关于控制与调度共同设计成为研究热点受到越来越多的重视，大体可分为开环调度和反馈控制实时调度两方面。（1） 开环调度A对 NCS 中各个控制环中数据传输节点采样周期和采样时刻的调度Hong 基于“ 窗口”的概念，给出了一种通过调度采样时间来减少时延的影响并提高网络利用率的调度算法，建立了 NCS 控制系统性能与
20、网络性能间的约束关系。但该算法是基于令牌环系统(token passing system)和轮询系统(polling system)的一维对象的调度，系统中信息类型仅限于周期性信息。Kim 等基于相同思想提出了适用于多维对象的采样时间调度算法。刘鲁源等提出了利用剩余的时间窗口调度非实时数据提高了网络资源利用率的调度算法。B调度优化Seto 针对性能指标是单调递减并且是每一任务频率的凸函数的这样一类控制系统，提出了一种通过改变采样频率使得任务能被 EDF 和 RM 调度的新算法，而且系统的性能在有限计算资源的约束下能达到最优。但该算法没有考虑执行时间的变化与扰动问题。Cervin 考虑了具有时延
21、变化的控制系统采样周期的选择问题，对低于一个采样周期的时延系统的采样周期进行了分析。Ryu 等以稳定状态误差、过冲、上升时间、沉降速度等作为控制性能参数，并将它们表示为采样周期和输入输出延时的函数，在可调度约束条件下用迭代算法对这些性能参数进行优化。何坚强等在上述研究的基础上给出了 NCS 的优化模型并采用遗传算法来求取采样频率。Branicky 和 Zhang 等提出将非抢占 RM 调度算法应用于网络控制系统的调度，并给出了保证系统稳定和网络可调度的充分条件。在此基础上，Branicky 等进一步对网络传输时间进行了分配，给出了网络调度优化方法。（2） 反馈控制实时调度开环调度算法在负载能精
22、确建模的动态或静态系统中可以取得很好的效果，可是在不可测的动态系统中，算法的有效性要极大地降低。近几年来， “闭环”调度由于可以应用于很多实时领域因而引起了很多人的关注。在 Seto 等提出的系统控制和调度离线集成设计的基础上，Cervin 提出一种将控制和调度动态弹性集成的框架，允许在线平衡控制性能和可用的计算资源。Stankovic 等提出了反馈控制实时调度的思想，而且还给出了一种结合 PID 控制和 EDF 调度器的反馈控制实时调度算法 FC-EDF ( Feedback Control- Earliest Deadline First)。汤贤铭等提出了一种将动态死区控制和优先级分配相结
23、合的反馈调度策略，用以解决在工作负载变动的环境中网络控制系统的控制与调度问题。Eker 等开发出了针对线性二次(Linear Quadratic)控制的反馈控制器。在可调度的情况下通过调整控制环频率来优化控制性能。Zhao 提出了一种结合速率单调调度和新的动态调度的动态反馈调度，用于调度预控制器产生的控制信号的传输，该调度算法确保了系统的稳定性，并且保证系统时延不超过保证系统稳定的上限。同网络控制系统其他研究问题相比网络控制系统的调度的研究相对比较薄弱，应有大量的工作需要做。1.3课题研究主要内容第一章主要研究了该课题的背景及其意义，并研究了该方向上的国内外研究现状，通过网络的检索查找一些相关文献，阅读文献并总结其使用方法。第二章主要针对 TTP 协议的通信原理及消息调度的原理进行了介绍，通过
