基于可调度性与全局延迟的分布嵌入式系统实时通信中的总线访问优化

《基于可调度性与全局延迟的分布嵌入式系统实时通信中的总线访问优化》由会员分享，可在线阅读，更多相关《基于可调度性与全局延迟的分布嵌入式系统实时通信中的总线访问优化（37页珍藏版）》请在装配图网上搜索。

1、基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化摘 要本文在对TTP通信协议进行研究的基础上,发现嵌入式实时系统通信过程中的消息调度算法只考虑消息的可调度性而没有对全局延迟进行考虑的问题,从而提出基于可调度性及全局延迟的实时通信的总线访问优化的研究课题,随后对实时通信总线的访问优化算法进行了研究,其中包括：静态单消息算法、静态多消息算法、动态消息分配算法以及动态数据包分配,并对可调度性的判断依据进行了说明,最后通过研究现有可调度性最优算法,从而给出改进后的算法描述并加以实现。关键字：TTP协议；可调度性；全局延时；嵌入式系统实时通信；总线优化ABSTRACTBased on th

2、e 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 access op

3、timization 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 Allocation

4、 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 opt

5、imization目录第一章 绪论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结点的组合能力和采用的容错机制14第三章 实时通讯总线访问优化算法介绍及改善163.1 消息调度算法简介

6、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第五章 总结3333 / 37第一章 绪论1.1 课题背景随着网络技术以及和数字信息技术的高速发展,在信息家电、医疗仪器、智能汽车、工业控制、通信设备各个领域中,嵌入式系统无处不在。随着网络技术的飞速发展,在许多嵌入式应用中,往往包含许多设备,譬如只能中央空调,这时分布式系统就是实现这

7、种系统最方便、最现实的方法1。由于分布式系统具有如下特点：时间关键的任务放在不同的CPU中可以更容易保证满足它的死线要求；把处理器放在设备级上更便于实现设备之间的接口；如果系统中包含从供应商购买的几个设备或系统,它们之间也含有自己的CPU,或者还包含有通信接口,通常不可能把系统的任务放到这些设备中,或者相反把设备的任务放到系统中；使用几个小CPU比使用一个大CPU更便宜；分布式的系统能够利用本身的高度容错性使得在高性能领域分布式系统系统中具有得天独厚的优势。所以,许多嵌入式系统利用分布式系统实现,在分布的处理器之间利用通讯链路连接起来,数据链路可以是高速并行数据总线紧耦合型,也可以是串行数据链

8、路。但是,随着电控单元的增多、功能日益复杂、网络通信数据量不断增大、要求更高的传输带宽、通信数据传输的高实时性和高可靠性等问题的出现,就需要一种更新、更可靠和更实时的高速通信网络技术来满足上述技术要求。目前,符合高带宽,实时性特点的总线类型有很多,其中TTPTime-Trigger Protocol总线技术是极具发展潜力的总线之一。TTP是分布式嵌入系统的一种总线访问协议,一般使用于对安全性有高要求的分布式嵌入系统中。而对于运行在分布式嵌入系统中的实时任务是否能够在满足时限的前提下完成,这取决于分布式节点间的消息通信情况。在已有文献中,可调度性是衡量实时系统的可预测性指标之一,其值越大则说明该

9、系统的实时任务越不易错失其时限,则其安全性能够得到更好的保障。而运行在分布式嵌入系统上的周期任务集链中第一个任务开始到最后一个任务结束的时间间隔称为该任务集链的全局延迟,该值越小那么说明系统到下一次周期任务集链开始执行时刻的时间间隔越大,而该时间间隔可以用于进行其他操作,如：非周期任务的处理；让系统处于待机状态,达到节能的目的。而在以往的实时通信中的总线访问优化,往往只注重系统中的可调度性或全局延迟的优化,而忽略该优化过程中对另一个指标的影响。如在文献1中基于TTP协议的总线访问优化算法就存在这样的问题。其分布式嵌入系统架构如图1所示2：图1.分布式嵌入系统的节点间通信共享同一总线示意该系统中

10、,所有分布节点间的通信采用TDMATime-Devision-Multiple-access方式进行消息传递。处于N0节点上的实时任务若需要与N1节点上的任务进行通信,则需要先将传输的消息放置发送队列中,当总线的使用时间片轮到N0使用时,N0再依次从消息发送队列中取出消息放置到总线上进行传输。最后,位于总线上的消息被N1节点获取,放置到自己的接受消息缓冲区中进行消息重组,最后在提供给需要使用该消息的任务使用。为了满足实时任务的时限要求,消息传输的调度起到了至关重要的作用。消息传输的调度一方面影响了该系统中实时任务集合的可调度性该定义详见1,同时也影响到了整个实时任务集合在最坏情况下的全局延迟该

11、定义详见5,因此,如何在消息调度过程中,实现任务集合具有最大可调度性的同时,而且还能得到最优或者近优的全局延时WCGD,这是本课题研究的主要容。1.2 国外研究现状计算机控制的发展f6_iol至今主要经历了以下几个阶段:传统的集中式控制系统、七十年代中期发展起来的集散控制系统、八十年代末发展起来的现场总线控制系统、九十年代发展起来的基于以太网的控制系统。网络控制系统中,网络调度就是对网络息的调度。目前网络控制系统息调度的研究主要分为调度与控制的分开设计和调度与控制的协同设计3-5。1.2.1 调度与控制的分开设计在NCS的研究中,一类研究是针对通信网络,研究提高网络服务质量的信息调度方法;另一

12、类研究是在一定的网络信息调度方法基础上,研究提高NCS性能的控制方法。因此,信息调度方法对改善NCS性能起着很大的作用。根据信息对实时性的要求,信息调度分为静态调度、动态调度和混合调度。（1） 静态优先级调度目前静态调度算法很多,本文着重介绍以下几种典型的算法以及算法的改进。速率单调静态优先级调度算法的调度优先级由任务周期确定,在任务周期等于时限的同步实时任务系统中是最佳静态调度算法。但是该算法具有调度判定具有指数时间复杂度、对任务的执行周期限制的过于严格、只能处理具有固定周期的任务等缺点。鉴于上述缺点Lehoczky等提出了扩大调度可行性条件的RM算法。Sha等考虑到任务的阻塞,给出了非抢占

13、服务方式下RM算法的可调度条件。叶明等基于RM算法提出了一种新的实时调度算法。文远保等针对任务的周期和调优先级关系不固定的流媒体提出了改进的RM算法。截至时间单调调度模型策略的任务优先级由任务时限来决定。该调度算法要防止任务越过其时限而得不到调度,从而影响系统的实时性。当任务周期和时限相同或者所有同步周期性任务时,DM算法都是最佳静态调度算法。由Hong等提出的基于时间窗的静态带宽调度算法避免了数据在网络传输过程中产生干扰和数据冲突。Hong等还将该调度方法应用于循环服务型NCS和CAN网下的NCS中。鲁源等鉴于该调度方法只限于调度网络中的周期数据,提出基于同步相和异步相的时间窗调度算法,使非

14、周期数据也可以采用该基于时间窗的静态调度算法6-8。（2） 动态优先级调度在动态优先级调度算法中,任务的时间约束关系并没有完全确定,新任务的到达时间是未知的。下面介绍几种经典的动态优先级调度算法。Liu和Layland提出的时限最早的任务优先调度Earliest deadline first scheduling,任务优先级是任务时限与任务执行时刻的差,该算法对同步周期任务组是最佳的动态调度算法。鉴于EDF是抢占式调度算法,任务间的切换时需要大量开销。B aker给出了非抢占士服务方式下EDF算法的可调度性条件。惠娟等提出了一种基于EDF算法的优先级驱动实时调度算法,较大程度地克服了EDF算法

15、在多处理器系统中的调度缺点。怀等提出了基于EDF算法的容错调度算法。奇智等采用非中断的EDF调度方法来改善周期性数据帧的端到端延迟。洪艳伟等提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。最小松弛优先调度和EDF算法可看作同类型的调度算法,任务优先级是完成时限和任务执行时刻的差再减去周期任务的执行时间。LLF算法尽量避免了长周期任务的频繁等待、执行,具有较小的抖动性。最大误差优先一尝试一次丢弃是Walsh等人提出的基于在线获取的网络诱导传输误差和动态分配网络带宽的调度算法。Otanez等人提出的基于死区的动态调度在确保系统性能的基础上动态地丢弃一定比率的数据,以减轻网络的负荷。但是

16、当多个获准访问网络的数据包同时竞争网络资源时,该策略不能确定数据包发送的优先级。基于业务平滑的动态调度是Kewon等利用业务平滑的技术控制Ethernet网的通信量,通过在Ethernet网的UDP层和MAC层插入定速率业务平滑器和自适应业务平滑器以限定MAC层数据包的到达速率,并且保证网络诱导时延的有界性,从而提高网络的服务质量。Cena等提出的优先级提升一分布式优先级排队调度可以保证实时数据传输最大间隔具有确定上界,非实时数据在传输中公平地竞争网络资源。基于时间窗的动态调度是Raja对基于时间窗的静态调度算法进行改进,提出优先级循环服务和动态时间窗的带宽分配策略9-10。模糊动态调度是白涛

17、等将模糊控制理论引入到NCS信息调度中,利用基于IF2THEN规则的模糊逻辑确定数据传输的优先级。（3） 混合调度Zuberi等针对CAN下网络控制系统,提出混合通信调度策略。在设计调度策略时,考虑到数据实时性要求不同,可以分别采用不同的调度策略,以提高网络资源的可调度性。Tabuada等给出的退火控制任务的事件触发实时调度是基于有反馈事例的事件触发调度器,并且给出了它如何保证系统性能的条件。1.2.2 调度与控制的协同设计目前关于控制与调度共同设计成为研究热点受到越来越多的重视,大体可分为开环调度和反馈控制实时调度两方面。（1） 开环调度A对NCS中各个控制环中数据传输节点采样周期和采样时刻

18、的调度Hong基于窗口的概念,给出了一种通过调度采样时间来减少时延的影响并提高网络利用率的调度算法,建立了NCS控制系统性能与网络性能间的约束关系。但该算法是基于令牌环系统和轮询系统的一维对象的调度,系统息类型仅限于周期性信息。Kim等基于相同思想提出了适用于多维对象的采样时间调度算法。鲁源等提出了利用剩余的时间窗口调度非实时数据提高了网络资源利用率的调度算法。B调度优化Seto针对性能指标是单调递减并且是每一任务频率的凸函数的这样一类控制系统,提出了一种通过改变采样频率使得任务能被EDF和RM调度的新算法,而且系统的性能在有限计算资源的约束下能达到最优。但该算法没有考虑执行时间的变化与扰动问

19、题。Cervin考虑了具有时延变化的控制系统采样周期的选择问题,对低于一个采样周期的时延系统的采样周期进行了分析。Ryu等以稳定状态误差、过冲、上升时间、沉降速度等作为控制性能参数,并将它们表示为采样周期和输入输出延时的函数,在可调度约束条件下用迭代算法对这些性能参数进行优化。何坚强等在上述研究的基础上给出了NCS的优化模型并采用遗传算法来求取采样频率。Branicky和Zhang等提出将非抢占RM调度算法应用于网络控制系统的调度,并给出了保证系统稳定和网络可调度的充分条件。在此基础上,Branicky等进一步对网络传输时间进行了分配,给出了网络调度优化方法。（2） 反馈控制实时调度开环调度算

20、法在负载能精确建模的动态或静态系统中可以取得很好的效果,可是在不可测的动态系统中,算法的有效性要极降低。近几年来,闭环调度由于可以应用于很多实时领域因而引起了很多人的关注。在Seto等提出的系统控制和调度离线集成设计的基础上,Cervin提出一种将控制和调度动态弹性集成的框架,允许在线平衡控制性能和可用的计算资源。Stankovic等提出了反馈控制实时调度的思想,而且还给出了一种结合PID控制和EDF调度器的反馈控制实时调度算法FC-EDF 。汤贤铭等提出了一种将动态死区控制和优先级分配相结合的反馈调度策略,用以解决在工作负载变动的环境中网络控制系统的控制与调度问题。Eker等开发出了针对线性

21、二次控制的反馈控制器。在可调度的情况下通过调整控制环频率来优化控制性能。Zhao提出了一种结合速率单调调度和新的动态调度的动态反馈调度,用于调度预控制器产生的控制信号的传输,该调度算法确保了系统的稳定性,并且保证系统时延不超过保证系统稳定的上限。同网络控制系统其他研究问题相比网络控制系统的调度的研究相对比较薄弱,应有大量的工作需要做。1.3 课题研究主要容第一章主要研究了该课题的背景及其意义,并研究了该方向上的国外研究现状,通过网络的检索查找一些相关文献,阅读文献并总结其使用方法。第二章主要针对TTP协议的通信原理及消息调度的原理进行了介绍,通过TTP协议的介绍可以说明在使用该协议进行嵌入式实

22、时通讯是需要注意的问题,及其解决方案。第三章主要针对实时通讯时的消息可调度性和全局延时进行优化,以此为目的说明了四种不同的消息调度优化算法,它们分别为静态单消息、静态多消息、动态数据包分配、动态消息分配四种算法,并在此基础上提出了优化其全局延时来改善并合理利用这些算法。第四章主要是针对第三章所提出的优化算法进行仿真实验,并通过仿真结果的对比来验证其算法的可用性。该章所验证的算是第三章中所描述的消息调度优化算法及在此基础上提出的全局优化。第二章 基于TTP协议及其消息调度原理简介传统用于分布式系统网络互联的协议很多,如RS-232串口通信协议、CAN协议以及与Internet互联的TCP/IP协

23、议等,在嵌入式系统中已得到了广泛的应用。但是,在现代安全至上的高可靠硬实时嵌入式系统safety-critical highly dependable hard real-time embedded system中,这些协议都没法满足系统的高可靠性要求。爱尔兰Limerick大学开发了TTCAN现场总线,采用了时间触发的消息响应调度方式,使现场总线在本质上具有确定性行为,因而可以应用于有严格实时要求的工业控制领域,能满足消息传输时间是实时的、有界的系统的最基本的控制要求11。用于工业测控系统的嵌入式计算机系统的工作环境往往是复杂恶劣的,有的嵌入式系统需要在高温、强辐射、高电磁干扰的恶劣环境下工

24、作。尽管传统上的在容错和抗干扰方面的解决方案取得了较大的成功。但是,在要求严格实时高可靠的现代分布式嵌入式系统应用场合,传统采用的方案就显得不太理想了。当今的嵌入式系统也倾向于采用分布式解决方案,这就涉及到采用何种总线,用何种协议来支持的问题。在安全至上的自动化领域中,特别是在硬实时嵌入式操作系统和安全至上Safety-critical的自动控制系统中,安全可预测的调度算法显得尤为重要12。传统事件触发方式对消息响应时间的有界性有不可忽视的影响,必须在总线协议中采用多种调度策略,使不确定的消息传输时延发生的概率降到最低,但它仍不是适合于安全性要求极高控制场合。本文介绍的TTP/C,最适合于安全

25、硬实时控制领域,在硬实时嵌入式系统中用TTP/C协议开发高可靠的嵌入式应用系统有重要意义。2.1 事件触发系统与时间触发系统于工业系统在向控制对象提供服务时,可以采用两种本质上不同的调度方式：事件触发和时间触发。事件触发结构是系统对控制对象的响应是由某个事件行为决定的,其发生时间具有随机性。也就是说,系统在时间上表现为不可预测性,而时间触发结构则不同,它是通过一个全局时钟进行驱动的,系统的行为不仅在功能上得到确定,而且在时间上也是确定的。两者的异同表现在以下几个方面： 1从对控制对象产生行为的机制上看,在事件触发系统中,控制信号取决于事件的发生如一次中断,是不可预知的。也就是说,系统中的结点没

26、有共同的时间概念,各结点的行为是随机的、不可预测的。而在时间触发结构中,系统控制信号的产生是由时间的推进来触发的,系统中各结点都知道何时何结点在特定时刻将会产生何种活动。因而系统的行为是确定的、可预测的。 2 从状态信息的来源看,时间触发系统的状态信息来源于规定时间的某个条件如在t0时刻读传感器的值；而事件触发系统的状态信息则是当某个条件成立时的状态如流量计超过某个闸值时触发事件的状态。 3 对总线的占用来看,在事件触发系统中,由于子系统之间都是完全的自治系统,它们不知道何时系统会产生何种行为,相互之间共同争用带宽,从而会产生冲突。而在时间触发系统中,系统中的各结点分时复用带宽,各结点对总线的

27、占用在设计时就已确定,总线带宽取决于最坏情况下系统的通信量,因而不会产生带宽争用现象。 4 从可靠性方面看,事件触发系统中各结点的可靠性取决于相对的优先级,优先级越高,可靠性越高。实验证明3,当事件率达到6070%时,优先级低的结点的服务将得不到保证,整个系统是不可靠的。而时间触发系统中各结点的事件都是预先安排好的,每个结点都在自己的时间槽完成相应的任务,整个系统是可靠的。 5 从稳定上看,由于事件触发系统中各结点在争用总线时会产生冲突,从而会产生延迟和抖动现象,这在硬实时高可靠系统中危害最大的因素之一,而时间触发系统则不会。 6 从应用角度上看,事件触发系统广泛用于分时系统,使得系统获得较大

28、的吞吐量和反映的灵活性。而时间触发系统则适用于硬实时高可靠系统,以获得更好的可预测性和可靠性。 由以上区别可以看出,时间触发系统由于其自身的特性,比较适合于硬实时高可靠系统,而对软实时和分时系统来说,这种触发结构就显得不够灵活了。在某些专用领域,如交通工具、医药行业等安全至上的行业,系统的失败可能导致严重后果的场合,使用时间触发系统不失为一种可行方案13。2.2 基于TTP/C的时间触发高可靠嵌入式实时系统的实现机制高可靠实时嵌入式系统必须具有良好的容错性能、实时性能、抗干扰性能和故障预测性能。在嵌入式分布式系统中,在硬件可靠性得到保证的前提下,如果没有好的协议机制和调度机制,系统的可靠性也是

29、没法保证的,时间触发协议TTP/C提供了良好的可靠性保证机制。下面以一个基于B/S结构时间触发嵌入式实时系统为例,说明用TTP/C时间触发体系结构来设计嵌入式分布式系统的基本框架14。2.2.1 基于TTP/C的时间触发高可靠系统的物理实现机制Vienna 理工大学的H.Kopetz教授的研究小组开发了TTP/C协议,它的全称是C类时间触发协议,C表示实时通信协议。TTP/C协议由SAEThe Society of Automotive Engineers汽车工程师协会定义。TTP/C是以开发硬实时高可靠容错嵌入式应用的需求为目标而设计的,它可以用于设计高可靠嵌入式应用系统15。 一个TTP/

30、C结点由主机host、通信网络接口CNI、TTP/C通信控制器TTP CC组成,其功能如图2所示。图2.TTP/C网络的硬件框图控制对象I/O接口是提供主机与环境检测、控制部件的接口。主机负责向控制对象接收信息并进行处理,并可以向控制对象发送控制信息,同时可与通信网络进行交互。网络通信接口CNI是联接主机和TTP/C的接口,它位于主机和TTP/C控制器都可以互相访问的双端口存储区中,为主机和TTP/C控制器会话提供了一个接口,其另一个作用是将主机和TTP/C控制器的时序隔离避免干扰。主机可以通过CNI对TTP/C控制器的操作进行监视,并可通过CNI命令使TTP/C控制器执行特定的动作。CNI还

31、为TTP/C消息的流动提供一条缓冲路径。TTP/C通信控制器是TTP/C网络通信的核心,它的部有一个消息描述表MEDLMessage Description List,该表中定义了结点所需要的控制数据,包括结点通信的组织和TDMA每一轮的消息调度方案,如在某时间点上结点应该发送或接收什么样的数据。该表是在系统投入运行前定义的,在运行时不能更改,一般存储在EEPROM或闪存中。消息描述表中可包含着多种不同的模式,每种模式分别对应于一种特定的消息调度,在不同的模式下,机群周期的TDMA轮数可能是不同的,在具体的某个时槽应该发送哪一个消息也是随模式的不同而不同的。协议处理器负责控制器部的逻辑控制。总

32、线守护器是一个具有自己的时钟系统的独立硬件单元,它的作用是保护网络通信使之不受故障结点的干扰。如果某个结点发生故障,它可能与系统时序失去同步而不在自己时间槽规定的时刻发送消息,那么该结点就成了串扰结点。如果不对该结点发送的消息进行屏蔽,就会对总线造成干扰,从而影响其他结点的正常工作。总线守护器存有机群中各结点的时间槽信息,如果结点不按照时间槽规定的时间发送,总线守护器将对它的消息进行屏蔽。它的独立时钟是用于避免因结点失效而导致时钟失效,从而使总线守护器不能同步计时的情况发生16。TTP/C可以根据ISO-11898和TTCAN等来设计物理层。图3为基于TTP/C的分布式嵌入式系统组成的总线式网

33、络,一个TTP/C机群由多个TTP/C结点和一个监视结点组成,由于Web服务器上的通用操作系统没有实时功能,不能满足机群中的硬实时要求,所以增加一个监视结点对TTP/C网络进行数据采集和监控。为了改善人机交互的界面和网上监控功能,可以把TTP/C网络通过Web服务器接入Internet。由于本文的重点在于介绍TTP/C的网络体系结构,接入Internet 的技术细节不作为重点讲述。TTP/C机群采用两条总线进行互联,其中一条是冗余通道,保证系统在一个通道失效的情况下仍能继续工作17。图3基于TTP/C的分布式嵌入式系统组成的总线式网络2.2.2 TTP/C所采用的帧类型和作用TTP/C通信采用

34、两种不同类型的帧,正常帧N-Frame和初始化帧I帧,Initialization frame,这两种帧在通信网络中的作用不同,其帧格式如图3所示。一个TTP/C帧由帧头、数据域或控制域和CRC校验域组成。帧头有四位,一位为帧类型标志,用于表示是N帧还是I帧；其余位用作模式控制位,用于标识模式变化请求。应用数据域可以达到16字节,CRC校验位采用16位,提供最少4位的海明距离18。I帧只包含控制器的状态Cstate信息,不包含任何数据信息。当帧头的帧类型标志为I-帧时,表示发送的是控制器状态信息。控制器状态信息用于初始化和恢复时间失效的结点,它包含了一个结点在参与通信前需要获得的信息、该时刻在

35、机群周期的当前位置信息和哪一个结点正在起作用,此外,控制器状态信息还包含当前的模式编号。如果一个结点因暂时的错误而失效,就要通过侦听I帧进行恢复,并用I帧提供的信息与网络进行同步。N-帧用于携带正常操作中的应用数据和发送历史状态消息。应用数据的地址在当前的MEDL表中。如果时间失效的结点需要某个特定应用的数据以便对网络进行恢复,它可以侦听具体的历史状态h-state消息,该消息中携带着所需要的数据,以N帧正常帧的形式传送,历史状态消息的发送是由主机来完成的。2.2.3 时间触发高可靠嵌入式系统的调度机制TTP/C协议是一种基于TDMATime Division Multiple Access的

36、协议,因而采用的也是基于时间的调度。不同结点的时间槽系列组成一个TDMA轮round,不同轮的系列组成一个TDMA机群周期,这样,一个机群周期可能包括一个或多个TDMA轮。在设计时就给系统中的每个处理结点分配固定的周期性的时间槽。时间触发协议采用绝对时钟进行同步,由一个时间主站周期性地向每个结点广播时钟基准消息,它标志着一个消息交互系列的开始。当结点成功接收到一个消息后,立即初始化结点部的计时器,此后在整个交互系列周期,计时器指示相对于基准消息出现时刻的时间,各结点也将参照接收到的消息,对本结点时间进行设置或调整,以保持所要求的时间同步。计时器记录的一个全程时间即是一个周期时间。图4说明了有4

37、个结点的时间触发系统的运作图,在这种情况下,每一轮总是只有一个发送方和三个接收方,所有结点协议的运行都在先验点上及时得到初始化,以后随着系统的运行,每个结点会根据消息发送的时间和自己MEDL中规定的消息到达时刻相对照,据此就可以调整时钟,始终与系统保持同步。全局时间基准通过分布式时钟同步算法而得到实现。当结点1的时间槽到来时,结点1成为消息发送结点,此时其余结点都是接收结点,同样,结点2、3、4也是在自己的时间槽进行消息发送。图4 时间触发系统的运作图要实现高可靠时间触发应用的调度,必须首先算出硬实时应用管理的处理器开销、最坏情况下的核开销和系统调用开销。在时间触发系统中,所有的活动都是随时间

38、的推进而完成的,这就意味着,除了计时中断外,系统不响应别的中断。轮询I/O和诊断I/O口这类活动,真接在计时中断例程中产生。时间触发系统一般采用静态调度策略,将它们在一个周期的调度信息列成一个表,调度方案就确定了,采用的调度策略只要按照时间的推进进行就可以了。也可以采用改善的时间触发调度策略,在确定了机群周期中的轮数和其中各结点的时间槽之后,可以采用图论的知识将各结点生成一棵树,在保证各个结点实时可靠性的前提下,应用图算法,算出最优调度方案,随着调度的进行,即时更新调度表,然后进行下一轮的调度。有关调度的更详细信息,请参考文献7。由于每个消息有各自的时槽,这种消息的一个最大优点是各消息之间不会

39、产生冲突,能很好地适应于要求硬实时高可靠系统的场合。2.2.4 TTP/C结点的组合能力和采用的容错机制1TTP/C的组合能力。在嵌入式分布式系统中,组合能力是一个重要的要求。一个运行良好的控制元件,在组成一个网络后不一定就运行良好。要有可组合性,网络中各控制元件必须满足系统的要求。相对于事件触发系统来说,采用TTP/C协议的时间触发系统有比较良好的可组合性。2临界瞬时冲突解决机制。事件触发系统由于访问网络的随机性,会产生临界瞬时的冲突,而时间触发TTP/C采用TDMA的机制,有效地解决了这个问题。3时序干扰的容错机制。位于主机和通信控制器之间的CNI,是一个双端口的RAM,除了前面介绍的作用

40、外,还有一个重要的作用就是时间防火墙。如图1所示,发送数据时,主机将需要传输到网络的数据写到CNI的双端口存储器中；当接收数据时,TTP/C协议处理器把网络上的传输数据也写到CNI的双端口存储器中,CNI有效地隔离了主机与协议控制器的时序行为,解网络和主机间的时序干扰。第三章 实时通讯总线访问优化算法介绍及改善3.1 消息调度算法简介上一节中具体介绍了FFP协议的使用原理,为了实现高可靠性时间触发应用的调度,提出了采用调度算法来实现其改善时间触发调度的策略,由此本节将提出具体实现的算法。所提出的算法将考虑到四种不同的TTP消息调度方式。3.1.1 静态单消息第一种方法为使用的TTP消息调度为静

41、态离线形式,且每个消息的时间表加入到TDMA周期的时槽,并对对应节点发送消息。并且认为时槽可以保存进每个最大消息。这种方法比较适合应用于汽车电子领域,这样的应用环境下,其消息的典型值较短,且比较容易诊断该系统是否达到瓶颈。当每个时槽只插入一个确定且满足要求的消息,且没有别的干扰消息。当消息m错过响应时间时,就必须等待下一个消息对它进行分配才能再次执行。则它的延时时间就是在一个连贯的时槽里面插入两个相同节点之间的最大时间,并将它表示为,如图所示。图5 静态单消息下最坏环境下所需要的时间在这种情况下,静态单消息下最坏环境下该消息所需要的时间就可以表示为。因此,影响消息调度分析的主要方面为该消息为静

42、态分配的时槽,并得到相应的。的值不仅跟相关,还需要根据静态单消息的连贯节点下发送出来的消息的长度,再加上所使用协议的控制帧和CRC校验位。当在综合的消息描述表中,设计者必须使用可调度的方式将消息分配到时间槽中。由于调整该过程的可调度性只能通过综合的消息描述表中参数,因此该参数在设置过程必须是最优的。根据图6所描述的简单例子,可知有三个处理器p1,p2,p3,并该三个处理都处于运行状态。当处理器p1在完成一次操作时,向处理器p2发送消息m1,并且还向处理器p3发送了消息m2。在图6a中提出的TDMA结构,只有运行在时间槽中的p1处理器对于算法的讨论有影响,所以其它在时间槽上的处理器将都以灰色表示

43、。根据图中的表述,将消息m1分配在时间槽位置的1和4中,并将消息m2分配在2和3中,其中消息p2由于其任务释放抖动那个而错过了其执行时间段时,故将其安排在位置2中。再根据图6b中表述的TDMA的结构,当消息m1分配在位置2和4中,将消息m2分配在位置1和3中,这样的形式可以实现将所有消息在规定的时间段执行。3.1.2 静态多消息第二种消息调度算法静态多消息算法为第一种的扩展。在该形式中,允许将多个消息插入到时间槽中,并且所有消息将通过在相同的时间槽打包一起传输。在这种情况下,就不会出现干扰的现象,所以消息m的进入延时机制是和第一种消息调度提出的机制一样的,也就是说,在一个连贯的时槽里面插入两个

44、相同节点之间的最大时间也为。图6 消息调度算法静态单消息和多消息的优化消息描述表然而,这种方式在综合消息表述表中提供了更多的自定义表述。但在使用这种方式中,必须先确定在时间槽中有多少个消息且这些消息分别是哪些。这样的方法使得优化参数更加得灵活。根据这种方式再次来描述下图6中的表述,就可以知道使用静态多消息的算法,TDMA的结构就可以描述为图6c所表述的形式。在该描述中,消息m1和m2被分配到相同的时间槽的位置1和2。因此,在这种情况下,消息可以在最后执行时间完成,并且释放抖动会比在图6b中描述的更进一步得减少,虽然在图6b中描述的消息在最后执行时间前也能完成,但是p3却经历了很长的释放抖动。3

45、.1.3 动态消息分配上述提到的两种算法分别是静态下的以单个消息或多个消息插入到它们相应的时间槽中。而现在提出的第三种算法是当消息产生时将以动态的形式插入到结构中。这样,当一个消息在发送进程中产生时,它将以优先级的顺序放入到一个消息队列中。根据消息的活跃度,在消息传输的过程中需要从队列的头中获取一个一定数量的消息和结构框架。而这些接受消息需要满足其长度不能超过帧的数据字段的长度的要求。这个长度的限制是由其各自处理器连续的时间槽长度决定的。当这些以动态的形式发送时,必须确定它们以一种确定的方式,即当发送至接受进程时该消息是被接受的。因此认为每个消息在其之前必须得加入已知的标志符。当将消息以动态得

46、以列队的形式打包进框架时,消息m在通信通道中的访问延时将根据它之前的列队中消息确定。根据文献17中的分析,在打包列队中的首个消息的优先级将大于消息m,根据这种情况就可以知道,一个消息可以在通信通道通讯前在打包数据分离出来。可以使用相同的原理实现,但是必须添加一定数量的消息来替代这个数据包。因此就需要考虑当消息的长度始终相等时是否会被长度不同的数据包所接受。因此,在窗体w中的消息m之前的更高优先级的消息队列的总长度可以表述为： 其中：为消息的长度。为消息发送过程中的相应时间。为消息的周期由此,就可以计算出在最坏环境下消息m在消息队列中所花费的时间。在一些TDMA机制的环节中,当消息m在传输中被所

47、加入的消息队列移除时,可以表述为： 其中：为消息m的大小。为消息m在时间槽中的大小对于任何消息x,其。这样就可以得到当在最坏的环境下,消息m在消息队列中所花费的时间为： 其中为执行一遍TDMA所花费的时间。接下来就需要确定插入的延时,其可以表述为： 而可以根据任意的截止时间确定,故其为： 应用给出的消息长度可以被充分利用在综合消息描述表中时间槽的长度计算上。将图7a所描述的和图6a中所描述的进行对比,就可以知道时间槽是如何影响消息的调度的。它们的不同之处在于,消息m1的优先级更高于消息m2,并且在它们产生时以动态的形式进行调度。根据图7a中描述的TDMA结构,消息m1首先动态调度到第一个关节上

48、,同时消息m2将等待,直到消息队列轮到下一个关节时再调度,因此造成了进程p2错过了它的截止时间。然而,如果扩大时间槽,就可以同时调度这两个消息,消息m2就可以不需要等待消息队列的响应而可以向消息m1一样直接通讯。因此,p2可以在截止时间之前完成,它的描述如图7b。然而,在一般情况下,不断增长的时间槽不一定改善其调度性能, 例如当它的延时是由其它关节通讯是产生的时。3.1.4 动态数据包分配动态数据包分配的算法为上一个算法的扩展,这种算法的前提是允许消息以数据包的形式在通信通道进行通讯。因此可以认为每一个时间槽长度都有一个容纳多个数据包的结构的长度。这种算法比较适合应用到拥有较大消息长度的特殊情

49、况,并将它们拆分到数据包中,就可以获得更高利用率的总线并减少释放扰动。然而,由于每个数据包必须确认每一个数据它的消息,并且这些消息必须拆分成发送消息,且在最后进行重组,其消耗将变得比上一个方法更高。图7 消息调度算法动态数据包和消息分配的优化消息描述表根据文献可知公式： 其中：为消息m的数据包的数量为消息m的连续时间槽的大小且 其中：为消息的数据包数量。在上一个算法中,混合消息描述表的优化参数即为时间槽的大小。而根据这节中提出的动态数据包分配算法,可知数据包的大小即为另一个优化参数。根据图7c中所描述的,消息m1和消息m2的长度都为6个字节。在TDMA结构中数据包的大小被认为为4个字节,且相应

50、的时间槽的长度为12个字节3个数据包。当消息m1拥有比消息m2更高的优先级时,它将动态得被分配在时间槽的第一个节点处,并且它需要两个数据包的大小。在剩下的数据包中,开头的4个字节由消息m2调度。因此,消息m2中两个空闲的字节必须等到下一个节点,这样就导致了进程p2错过了其截止时间。不管如何,如果需要将数据包大小改变为3个字节,并且又要保证它的长度在时间槽仍旧为12个字节,就需要处理器p1提供4个数据包。消息m1将第一个被动态分配,并在时间槽的开始位置产生两个数据包。这样的情况就需要使消息m2的同一个位置进行发送,否则它将错过p2的截止时间。3.2 消息调度优化其可调度性根据上述介绍,在消息调度

51、上就出现了一个问题：分析进程的可调度性和基于FFP协议的综合消息描述表的能力。并且根据上述的算法介绍,已知在调度消息上所需要考虑的优化参数。为了优化进程中的消息调度,提出了一个指导优化的功能函数,其模型表述为: 式中：为应用中的进程数量。为进程的响应时间。为进程的截止时间。在上式中,如果进程的运行不可调度,就会至少存在一个超过延迟时间,否则f1的结果即为其绝对值。这样的情况下,该功能函数得到的结果即为f1。然而,如果该进程的运行时可调度的,这样所有的都将小于。在这种情况下,f1即为0,而功能函数的结果即为计算f2的值,而这两种情况都影响to了进程运行的可调度性。作为优化进程可调度性的参数,就需

52、要得到更小的f2 to值,这就意味着必须改善进程的响应时间,因此该应用就可以应用到更便宜的硬件设备上。而释放时间将根据进程的释放扰动的任意截止时间分析、在最坏环境下的执行时间、阻塞时间和更高优先级进程的干扰时间进行计算。根据一个已经提供的应用,可以合成一个可以使得上述功能函数结果最小的消息描述表。还可以估计四种算法在不同环境下的消息调度情况,并且根据它们调度的情况来选择一个最好的方法来应用到平台中。消息描述表的合成问题属于典型的组合问题,因此,可根据其思路能够找到计算合理时间的精确结果的方法。因此提出了一个优化四个算法相应的消息调度。第一个思路是基于单个的贪婪算法的思路。第二个算法基于模拟退火

53、算法使结果接近最优的思路。贪婪算法区别于提出的四种消息调度算法。它的主要思路就是通过不断减少释放扰动来改善其进程调度程度。而减少释放扰动的方法只有静态单消息算法和静态多消息算法,它们通过改善参数来对其进行优化。这种形式主要是通过对消息在时间槽中对位置进行调整来实现的。优化静态单消息的算法在初始化时就得确定每个时间槽的大小。由于其大小确定且无法修改,所以其大小必须能容纳最大消息的长度。因此,定义的时间槽的大小的最小值必须能容纳实现使最大的那个消息的发送节点。然而,这个算法还必须确定时间轮的数量,由此就可以确定消息描述表的大小。由于消息描述表的大小受自身限制,就导致了时间轮的数量也受到了限制。不管

54、如何,在一个应用中这种根据传输消息数量的时间轮最小值是必须确定的。例如,一个进程原本计划在节点N0上发送7个消息,于是就需要决定至少7个时间轮去完成这些消息。几个时间轮将依据算法上从最小时间轮到最大时间轮进行执行。在已知多少个时间轮之后,在初始化时空闲的消息描述表必须用消息进行填充,并令其价值函数达到最小。为了能将这种价值函数能应用到这种调度分析上,提出了一种完成的消息描述表。它将至少包含一个所有消息中的实例,并且该消息能实现不同处理器之间的通讯。一个最小且完整的消息描述表是通过在一个空闲的消息描述表放置一个时间轮构建的,该时间轮是有每一个消息加入到连续且空闲的时间槽中构建的。例如,在图6a中

55、,可以看到一个拥有四个时间轮的时间槽。为了得到一个最小且完整的消息描述表,可以将消息m2和消息m1分别安排到时间槽的时间轮3和4中,然后使时间轮1和2空闲。然而,这种消息描述表可能不会影响系统的可调度性。这种调度的可调性可以通过在消息描述表中插入有效的替代消息进行改善,由此令参数最小化。上述提到的算法多次提到了加入一个新的替代消息到当前的消息描述表中,一次来实现改善价值函数的值。为了得到这个替代消息,可以使用简单的贪心算法实现。令进程pi为临界状态,这就意味着截止时间和响应时间是不同的,并且要小于其它进程。将该消息加入到消息描述表中,即消息m等于,且该消息通过进程pi进行接收。消息m将在一个时

56、间轮时间,该时间轮为当价值函数为最小值时的时间轮。当消息描述表不能通过添加更多消息来改善其调度效果时,该算法即停止。优化静态多消息的算法通静态单消息的基本一致。它们的主要不同之处在于静态多消息可以在一个时间槽产生多个消息,而在静态单消息只能加入一个最大的消息。还有就是在静态多消息的情况下,必须还得额外注意该时间槽是否能加入最大的消息。而动态的算法实现比静态的更简单,它们分别为动态消息分配算法和动态数据包算法,由于两种算法都只需要确定时间槽的大小,且数据包分配需要确定数据包大小。根据这两种算法,产生的消息都为动态的并且都不影响价值函数的值。而优化动态消息分配算法初始化时,在开始的时间槽中令所有消

57、息的时间槽时间都等于第一个时间槽的大小,并且找出能令价值函数达到最小值时的大小值。并且这个时间槽的大小必须足够大,至少能够容纳最小消息在时间槽上传输的大小,并且通过特殊的基于TTP协议控制器进行确定其边界值。一旦第一个时间槽的大小确定了,那么算法将继续以相同的方式进行下一个时间槽。而优化动态数据包分配算法,除了上述信息需要确定外,还需要确定其数据包的大小。这就需要对每一个数据包在基于TTP协议的控制器上大小进行确认。例如,当初始以两个字节开始,并且在最小的数据单元下能增长到32字节。在这种环境下,时间槽的大小就是多个时间槽大小的和,并且大的最大围也必须根据控制器的大小决定。另外还可以使用另一中

58、模拟退火算法实现对上述四个算法的优化。为了调整算法的参数,必须选择一个需要花费较长时间的进程进行运行测试,并获得其最优解决方案,使每个算法极近最优。根据进一步实验可以确定模拟退火算法中的参数,根据不同大小的消息的实验,最优计算的时间会逐步减少,而最优的结果依旧可以产生。3.3消息全局延时优化上述针对消息调度的可调度性的算法进行了研究,但这些算法在优化其可调度性的过程中,并没有考虑到该消息调度的优化过程过程对WCGD指标的影响。WCGD即为消息调度使的全局延时。所谓的全局延时即为：当程序运行在最坏环境下时,这种情况下通常会出现执行时间远大于原本计算的平均时间,这样就会出现所谓的全局延时。因此,当

59、设计周期性系统时,当程度完成一次完整操作之后,直到下一个周期到来之前的间隔时间,调整全局延时的大小就相对来说比较重要了。在这个时间间隔,进程的空闲时间可以被其它事件利用起来去做别的事件,直到准备好做下一个周期事情时再次调用。因此,与其让它们空闲,还不如利用其这一段空闲时间,即使不使用,也可以关闭处理器,还可以节省能源。所以,能够优化其全局延时对于嵌入式系统的实时通讯总线优化起到了至关重要的作用。如图所示为一个在较困难环境下的应用程序,该应用是由三个任务组成,它们分别在两个处理器上运行。该应用周期性得执行一个周期就相当于最坏换进下的全局延时。在完成最后一次计算后,几个处理器为了节省能源将其关闭,

60、知道下一个周期到了再次运行。因此,在平均情况下,处理器的平局延时和全局延时之间将被切断,并且,由于目标的减少,这样尽可能得减少了电力消耗,并且还可以最大限度得利用好这个时间间隔。图8 一个硬实时系统的例根据上节中的消息调度算法优化仅仅只针对瓶颈任务进行通信调度信息优化,从而达到可调度性最优化的目的。但在该算法的优化过程中,并没有全局延时值的变化,从而可能全局延时很大,从而导致系统的开销浪费。因此,在上节提出的算法的基础上,提出了对于全局延时的优化,从而在保证上述算法中价值函数结果不变的前提下,尽量减少全局延时的开销。因此设计方案如下：1） 采用消息调度算法对瓶颈任务进行优化,使价值函数结果尽量

61、减至最小。2） 检查价值函数结果减少后,全局延时是否增加3） 如果全局延时增加,则在价值函数结果不变的前提下,优化其它非瓶颈任务的消息调度。4） 检查优化之后全局延时值是否增加。以下是对算法优化的程序流程图：第四章 算法实现与仿真结果4.1可调度性最优算法可调度性是衡量实时系统的可预测性指标之一,其值越大则说明该系统的实时任务越不易错失其时限,则其安全性能够得到更好的保障。实时系统的可调度性是通过进程取得消息后进程任务结束时间与进程的有效时间的差值体现的。即由式2-9来衡量。4-1其中,为进程的响应时间,为进程的截止时间。算法流程图图9 可调度性最优算法程序框图算法实现：for each no

62、de Nido / set the slot sizessizeSi = maxend forfor each node Nido / find the min. no. of rounds that can hold.nmi = number of messages sent from Ni/ .all the messages end formin_rounds = max for each message mi/ create a minimal complete MEDL find round in 1.min_rounds that has an empty slot for mi place mi