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

1 基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 摘要 本文在对 现嵌入式实时系统通信过程中的消息调度算法只考虑消息的可调度性而没有对全局延迟进行考虑的问题，从而提出基于可调度性及全局延迟的实时通信的总线访问优化的研究课题，随后对实时通信总线的访问优化算法进行了研究，其中包括：静态单消息算法、静态多消息算法、动态消息分配算法以及动态数据包分配，并对可调度性的判断依据进行了说明，最后通过研究现有可调度性最优算法，从而给出改进后的算法描述并加以实现。 关键字： 调度性；全局延时；嵌入式系统实时通信；总线优化 3 on TP of of to to in to a on of by to is of to be in to 录 第一章 绪论 . 1 题背景 . 1 内外研究现状 . 3 度与控制的分开设计 . 3 度与控制的协同设计 . 5 题研究主要内容 . 6 第二章 基于 议及其消息调度原理简介 . 8 件触发系统与时间触发系统 . 8 于 的时间触发高可靠嵌入式实时系统的实现机制 . 10 于 的时间触发高可靠系统的物理实现机制 . 10 所采用的帧类型和作用 . 12 间触发高可靠嵌入式系 统的调度机制 . 13 结点的组合能力和采用的容错机制 . 14 第三章 实时通讯总线访问优化算法介绍及改善 . 16 息调度算法简介 . 16 态单消息 . 16 态多消息 . 17 态消息分配 . 18 态数据包分配 . 20 息调度优化其可调度性 . 21 息全局延时优化 . 24 第四章 算法实现与仿真结果 . 26 调度性最优算法 . 26 局延迟最优算法 . 27 调度性及全局延迟近似最优算法 . 29 真结果 . 31 第五章 总结 . 33 基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 1 第一章 绪论 题背景 随着网络技术以及和数字信息技术的高速发展，在信息家电、医疗仪器、智能汽车、工业控制、通信设备各个领域中，嵌入式系统无处不在。随着网络技术的飞速发展，在许多嵌入式应用中，往往包含许多设备，譬如只能中央空调，这时分布式系统就是实现这种系统最方便、最现实的方法 1。 由于分布式系统具有如下特点：时间关键的任务放在不同的 可以更容易保证满足它的死线要求；把处理器放在设备级上更便于实现设备之间的接口；如果系统中包含从供应商购买的几个设备或系统，它们之间也含有自己的者还包含有通信接口 ，通常不可能把系统的任务放到这些设备中，或者相反把设备的任务放到系统中；使用几个小 使用一个大 便宜；分布式的系统能够利用本身的高度容错性使得在高性能领域分布式系统系统中具有得天独厚的优势。 所以，许多嵌入式系统利用分布式系统实现，在分布的处理器之间利用通讯链路连接起来，数据链路可以是高速并行数据总线（紧耦合型），也可以是串行数据链路。 但是，随着电控单元的增多、功能日益复杂、网络通信数据量不断增大、要求更高的传输带宽、通信数据传输的高实时性和高可靠性等问题的出现，就需要一种更新、更可靠和更实时 的高速通信网络技术来满足上述技术要求。 目前，符合高带宽，实时性特点的总线类型有很多，其中 线技术是极具发展潜力的总线之一。 分布式嵌入系统的一种总线访问协议，一般使用于对安全性有高要求的分布式嵌入系统中。而对于运行在分布式嵌入系统中的实时任务是否能够在满足时限的前提下完成，这取决于分布式节点间的消息通信情况。在已有文献中，可调度性是衡量实时系统的可预测性指标之一，其值越大则说明该系统的实时任务越不易错失其时限，则其安全性能够得到更好的保障。而运行在 分布式嵌入系统上的周期任务集（链）中第一个任务开始到最后一个任务结束的时间间隔称为该任务集（链）的全局延迟，该值越小那么说明系统到下一次周期任务集（链）开始执行时刻的时间间隔越大，而该时间间隔可以用于进行其他操作，如：非周期任务的处理；让系统处于待机状态，达到节能的目的。而在以往的实时通信中的总线访问优化，往往只注重系统中的可调度性或全局延迟的优化，而忽略该优化过程中对另一个指标的影响。 如在文献 1中基于 分布式嵌入系统架构如图 1所示 2： 图 嵌入系统的节点间通信共享同一总线示意 该系统中，所有分布节点间的通信采用 方式进行消息传递。处于 点上的实时任务若需要与 点上的任务进行通信，则需要先将传输的消息放置发送队列中，当总线的使用时间片轮到 用时， 依次从消息发送队列中取出消息放置到总线上进行传输。最后，位于总线上的消息被 点获取，放置到自己的接受消息缓冲区中进行消息重组，最后在提供给需要使用该消息的任务使用。为了满足实时任务的时限要求，消息传输的调度起到了 至关重要的作用。消息传输的调度一方面影响了该系统中实时任务集合的可调度性（该定义详见 1），同时也影响到了整个实时任务集合在最坏情况下的全局延迟 (该定义详见 5），因此，如何在消息调度过程中，实现任务集合具有最大可调度性的同时，而且还能得到最优或者近优的全局延时（ 这是本课题研究的主要内容。 基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 3 内外研究现状 计算机控制的发展 今主要经历了以下几个阶段 :传统的集中式控制系统、七十年代中期发展起来的集散控制系统、八十年代末发展起来的现场总线控制系统、九十年代发展起来的基 于以太网的控制系统。 网络控制系统中，网络调度就是对网络中信息的调度。目前网络控制系统中信息调度的研究主要分为调度与控制的分开设计和调度与控制的协同设计 3 度与控制的分开设计 在 研究中，一类研究是针对通信网络，研究提高网络服务质量的信息调度方法 ;另一类研究是在一定的网络信息调度方法基础上，研究提高 能的控制方法。因此，信息调度方法对改善 能起着很大的作用。 根据信息对实时性的要求，信息调度分为静态调度 (又称离线调度 )、动态调度 (又称在线调度 )和混合调度。 （ 1） 静态优先级调度 目 前静态调度算法很多，本文着重介绍以下几种典型的算法以及算法的改进。 速率单调静态优先级调度 (法的调度优先级由任务周期确定，在任务周期等于时限的同步实时任务系统中是最佳静态调度算法。但是该算法具有调度判定具有指数时间复杂度、对任务的执行周期限制的过于严格、只能处理具有固定周期的任务等缺点。鉴于上述缺点 提出了扩大调度可行性条件的 法。 考虑到任务的阻塞，给出了非抢占服务方式下 法的可调度条件。叶明等基于 法提出 了一种新的实时调度算法 (文远保等针对任务的周期和调优先级关系不固定的流媒体提出了改进的 法。 截至时间单调调度模型 (略的任务优先级由任务时限来决定。该调度算法要防止任务越过其时限而得不到调度，从而影响系统的实时性。当任务周期和时限相同或者所有同步周期性任务时， 法都是最佳静态调度算法。 由 提出的基于时间窗的静态带宽调度算法避 免了数据在网络传输过程中产生干扰和数据冲突。 。刘鲁源等鉴于该调度方法只限于调度网络中的周期数据，提出基于同步相和异步相的时间窗调度算法，使非周期数据也可以采用该基于时间窗的静态调度算法 6 （ 2） 动态优先级调度 在动态优先级调度算法中，任务的时间约束关系并没有完全确定，新任务的到达时间是未知的。下面介绍几种经典的动态优先级调度算法。 出的时限最早的任务优先调度 (务优先级是任务时限与任务执行时刻的差，该算法对同步周期任务组是最佳的动态调度算法。鉴于 抢占式调度算法，任务间的切换时需要大量开销。 B 出了非抢占士服务方式下 法的可调度性条件。张惠娟等提出了一种基于 法的优先级驱动实时调度算法，较大程度地克服了 怀等提出了基于 法的容错调度算法。张奇智等采用非中断的 度方法来改善周期性数据帧的端到端延迟。洪艳伟等提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。 最小 松弛优先调度 ( 法可看作同类型的调度算法，任务优先级是完成时限和任务执行时刻的差再减去周期任务的执行时间。 法尽量避免了长周期任务的频繁等待、执行，具有较小的抖动性。 最大误差优先一尝试一次丢弃 ( 人提出的基于在线获取的网络诱导传输误差和动态分配网络带宽的调度算法。 人提出的基于死区的动态调度在确保系统性能的基础上动态地丢弃一定比率的数据，以减轻网络的负荷。但是 当多个获准访问网络的数据包同时竞争网络资源时，该策略不能确定数据包发送的优先级。 基于业务平滑的动态调度是 利用业务平滑的技术控制 的通信量，通过在 的 和 插入定速率业务平滑器和自适应业务平滑器以限定 数据包的到达速率，并且保证网络诱导时延的有界性，从而提高网络的服务质量。 提出的优先级提升一分布式优先级排队调度 (以保证实时数据传输最大间隔具有确定上界，非实时数据在传输中公平地竞争网络资源。 基于时间 窗的动态调度 ( 基于时间窗的静态基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 5 调度算法进行改进，提出优先级循环服务和动态时间窗的带宽分配策略 9 模糊动态调度是白涛等将模糊控制理论引入到 息调度中，利用基于则的模糊逻辑确定数据传输的优先级。 （ 3） 混合调度 针对 网络控制系统，提出混合通信调度 (略。在设计调度策略时，考虑到数据实时性要求不同，可以分别采用不同的调度策略，以提高网络资源的可调度性。 给出的退火控制任务的事件触发实时调度是基于有反馈事例的事件触发调度器，并且给出了它如何保证系统性能的条件。 度与控制的协同设计 目前关于控制与调度共同设计成为研究热点受到越来越多的重视，大体可分为开环调度和反馈控制实时调度两方面。 （ 1） 开环调度 A对 各个控制环中数据传输节点采样周期和采样时刻的调度 于“窗口”的概念，给出了一种通过调度采样时间来减少时延的影响并提高网络利用率的调度算法，建立了 制系统性能与网络性能间的约束关系。但该算法是基于令牌环系统 (轮询系统 (一维对象的调度，系统中信息类型仅限于周期性信息。 基于相同思想提出了适用于多维对象的采样时间调度算法。刘鲁源等提出了利用剩余的时间窗口调度非实时数据提高了网络资源利用率的调度算法。 B调度优化 对性能指标是单调递减并且是每一任务频率的凸函数的这样一类控制系统，提出了一种通过改变采样频率使得任务能被 度的新算法，而且系统的性能在有限计算资源的约束下能达到最优。但该算法没有考虑执行时间的变化与扰动问题。 虑了具有时延变化的控制系统采样周期的选择问题，对 低于一个采样周期的时延系统的采样周期进行了分析。 以稳定状态误差、过冲、上升时间、沉降速度等作为控制性能参数，并将它们表示为采样周期和输入输出延时的函数，在可调度约束条件下用迭代算法对这些性能参数进行优化。何坚强等在上述研究的基础上给出了 优化模型并采用遗传算法来求取采样频率。 提出将非抢占 度算法应用于网络控制系统的调度，并给出了保证系统稳定和网络可调度的充分条件。在此基础上，进一步对网络传输时间进行了分配，给出了网络调度优化方法。 （ 2） 反馈控制实 时调度 开环调度算法在负载能精确建模的动态或静态系统中可以取得很好的效果，可是在不可测的动态系统中，算法的有效性要极大地降低。近几年来，“闭环”调度由于可以应用于很多实时领域因而引起了很多人的关注。在 提出的系统控制和调度离线集成设计的基础上， 出一种将控制和调度动态弹性集成的框架，允许在线平衡控制性能和可用的计算资源。 提出了反馈控制实时调度的思想，而且还给出了一种结合 制和 度器的反馈控制实时调度算法 汤贤铭等提出了一种将动态死区控制和优先级分配相结合的反馈调度策略，用以解决在工作负载变动的环境中网络控制系统的控制与调度问题。 开发出了针对线性二次(制的反馈控制器。在可调度的情况下通过调整控制环频率来优化控制性能。 出了一种结合速率单调调度和新的动态调度的动态反馈调度，用于调度预控制器产生的控制信号的传输，该调度算法确保了系统的稳定性，并且保证系统时延不超过保证系统稳定的上限。 同网络控制系统其他研究问题 相比网络控制系统的调度的研究相对比较薄弱，应有大量的工作需要做。 题研究主要内容 第一章主要研究了该课题的背景及其意义，并研究了该方向上的国内外研究现状，通过网络的检索查找一些相关文献，阅读文献并总结其使用方法。 第二章主要针对 议的通信原理及消息调度的原理进行了介绍，通过议的介绍可以说明在使用该协议进行嵌入式实时通讯是需要注意的问题，及其解决方案。 第三章主要针对实时通讯时的消息可调度性和全局延时进行优化，以此为目的说明了四种不同的消息调度优化算法，它们分别为静态单消息、静态多消息、动态数 据包分配、动态消息分配四种算法，并在此基础上提出了优化其全局延时来改善并合理利用这些算法。 基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 7 第四章主要是针对第三章所提出的优化算法进行仿真实验，并通过仿真结果的对比来验证其算法的可用性。该章所验证的算法正是第三章中所描述的消息调度优化算法及在此基础上提出的全局优化。 第二章 基于 议及其消息调度原理简介 传统用于分布式系统网络互联的协议很多，如 口通信协议、议以及与 联的 P 协议等，在嵌入式系统中已得到了广泛的应 用。但是，在现代安全至上的高可靠硬实时嵌入式系统（ ，这些协议都没法满足系统的高可靠性要求。爱尔兰 学开发了场总线，采用了时间触发的消息响应调度方式，使现场总线在本质上具有确定性行为，因而可以应用于有严格实时要求的工业控制领域，能满足消息传输时间是实时的、有界的系统的最基本 的控制要求 11。 用于工业测控系统的嵌入式计算机系统的工作环境往往是复杂恶劣的，有的嵌入式系统需要在高温、强辐射、高电磁干扰的恶劣环境下工作。尽管传统上的在容错和抗干扰方面的解决方案取得了较大的成功。但是，在要求严格实时高可靠的现代分布式嵌入式系统应用场合，传统采用的方案就显得不太理想了。当今的嵌入式系统也倾向于采用分布式解决方案，这就涉及到采用何种总线，用何种协议来支持的问题。在安全至上的自动化领域中，特别是在硬实时嵌入式操作系统和安全至上（ 自动控制系统中，安全可预测 的调度算法显得尤为重要 12。传统事件触发方式对消息响应时间的有界性有不可忽视的影响，必须在总线协议中采用多种调度策略，使不确定的消息传输时延发生的概率降到最低，但它仍不是适合于安全性要求极高控制场合。本文介绍的 ，最适合于安全硬实时控制领域，在硬实时嵌入式系统中用 协议开发高可靠的嵌入式应用系统有重要意义。 件触发系统与时间触发系统 于工业系统在向控制对象提供服务时，可以采用两种本质上不同的调度方式：事件触发和时间触发。事件触发结构是系统对控制对象的响应是由某个事件行为决定的， 其发生时间具有随机性。也就是说，系统在时间上表现为不可预测性，而时间触发结构则不同，它是通过一个全局时钟进行驱动的，系统的行为不基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 9 仅在功能上得到确定，而且在时间上也是确定的。两者的异同表现在以下几个方面： （ 1）从对控制对象产生行为的机制上看，在事件触发系统中，控制信号取决于事件的发生（如一次中断），是不可预知的。也就是说，系统中的结点没有共同的时间概念，各结点的行为是随机的、不可预测的。而在时间触发结构中，系统控制信号的产生是由时间的推进来触发的，系统中各结点都知道何时何结点在特定时刻将会产生何种活动。 因而系统的行为是确定的、可预测的。 （ 2） 从状态信息的来源看，时间触发系统的状态信息来源于规定时间内的某个条件（如在 刻读传感器的值）；而事件触发系统的状态信息则是当某个条件成立时的状态（如流量计超过某个闸值时触发事件的状态）。 （ 3） 对总线的占用来看，在事件触发系统中，由于子系统之间都是完全的自治系统，它们不知道何时系统会产生何种行为，相互之间共同争用带宽，从而会产生冲突。而在时间触发系统中，系统中的各结点分时复用带宽，各结点对总线的占用在设计时就已确定，总线带宽取决于最坏情况下系统的通信 量，因而不会产生带宽争用现象。 （ 4） 从可靠性方面看，事件触发系统中各结点的可靠性取决于相对的优先级，优先级越高，可靠性越高。实验证明 3，当事件率达到 6070%时，优先级低的结点的服务将得不到保证，整个系统是不可靠的。而时间触发系统中各结点的事件都是预先安排好的，每个结点都在自己的时间槽内完成相应的任务，整个系统是可靠的。 （ 5） 从稳定上看，由于事件触发系统中各结点在争用总线时会产生冲突，从而会产生延迟和抖动现象，这在硬实时高可靠系统中危害最大的因素之一，而时间触发系统则不会。 （ 6） 从应用角度上看，事件触发系统广泛用于分时系统，使得系统获得较大的吞吐量和反映的灵活性。而时间触发系统则适用于硬实时高可靠系统，以获得更好的可预测性和可靠性。 由以上区别可以看出，时间触发系统由于其自身的特性，比较适合于硬实时高可靠系统，而对软实时和分时系统来说，这种触发结构就显得不够灵活了。在某些专用领域，如交通工具、医药行业等安全至上的行业，系统的失败可能导致严重后果的场合，使用时间触发系统不失为一种可行方案 13。 于 的时间触发高可靠嵌入式实时系统的实现机制 高可靠实时嵌入式系 统必须具有良好的容错性能、实时性能、抗干扰性能和故障预测性能。在嵌入式分布式系统中，在硬件可靠性得到保证的前提下，如果没有好的协议机制和调度机制，系统的可靠性也是没法保证的，时间触发协议 提供了良好的可靠性保证机制。下面以一个基于 B/S 结构时间触发嵌入式实时系统为例，说明用 时间触发体系结构来设计嵌入式分布式系统的基本框架 14。 于 的时间触发高可靠系统的物理实现机制 工大学的 授的研究小组开发了 协议，它的全称是 C 类时间触发 协议 ()，“ C”表示实时通信协议。 协议由 车工程师协会）定义。 是以开发硬实时高可靠容错嵌入式应用的需求为目标而设计的，它可以用于设计高可靠嵌入式应用系统 15。 一个 结点由主机（ 通信网络接口（ 通信控制器（ C）组成，其功能如图 2 所示。 基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 11 控 制 对 象 I / O 接 口主 机C N 处 理器T T P / C 控 制器 数 据（ M E D L ）总 线 守 护 器驱 动 器 驱 动 器T T P B u 网络的硬件框图 控制对象 I/O 接口是提供主机与环境检测、控制部件的接口。主机负责向控制对象接收信息并进行处理，并可以向控制对象发送控制信息，同时可与通信网络进行交互。网络通信接口 联接主机和 的接口，它位于主机和 控制器都可以互相访问的双端口存储区中，为主机和 控制器会话提供了一个接口，其另一个作用是将主机和 控制器的时序隔离避免干扰。主机可以通过 控制器的操作进行监视，并可通过 令使 控制器执行特定的动作。 为 消息的流动提供一条缓冲路径。 通信控制器是 网络通信的核心，它的内部有一个消息描述表 该表中定义了结点所需要的控制数据，包括结点通信的组织和一轮的消息调度方案，如在某时间点上结点应该发送或接收什么样的数据。该表是在系统投入运行前定义的，在运行时不能更改，一般存储在 息描述表中可包含着多种不同的模式，每种模式分别对应于一种特定的消息调度，在不同的模式下，机群周期内的 数可能是不同的，在具体的 某个时槽应该发送哪一个消息也是随模式的不同而不同的。协议处理器负责控制器内部的逻辑控制。总线守护器是一个具有自己的时钟系统的独立硬件单元，它的作用是保护网络通信使之不受故障结点的干扰。如果某个结点发生故障，它可能与系统时序失去同步而不在自己时间槽规定的时刻发送消息，那么该结点就成了串扰结点。如果不对该结点发送的消息进行屏蔽，就会对总线造成干扰，从而影响其他结点的正常工作。总线守护器存有机群中各结点的时间槽信息，如果结点不按照时间槽规定的时间发送，总线守护器将对它的消息进行屏蔽。它的独立时钟是用于避免因结点失 效而导致时钟失效，从而使总线守护器不能同步计时的情况发生 16。 可以根据 来设计物理层。图 3 为基于 的分布式嵌入式系统组成的总线式网络，一个 机群由多个 结点和一个监视结点组成，由于 务器上的通用操作系统没有实时功能，不能满足机群中的硬实时要求，所以增加一个监视结点对 网络进行数据采集和监控。为了改善人机交互的界面和网上监控功能，可以把 网络通过 务器接入 于本文的重点在于介绍 的网络体 系结构，接入 技术细节不作为重点讲述。 机群采用两条总线进行互联，其中一条是冗余通道，保证系统在一个通道失效的情况下仍能继续工作 17。 主 机C N 主 机C N 主 机C N 数 据 记 录 器 工 作 站W e b 服 务 器T T P / C 机 群图 3 基于 的分布式嵌入式系统组成的总线式网络 所采用的帧类型和作用 通信采用两种不同类型的帧，正常帧（ 初始化帧（ I帧，这两种帧在通信网络中的作用不同，其帧格式如图 3 所示。基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 13 一个 帧由帧头、数据域（或控制域）和 验域组成。帧头有四位，一位为帧类型标志，用于表示是 N帧还是 I帧；其余位用作模式控制位，用于标识模式变化请求。应用数据域可以达到 16 字节， 验位采用 16 位，提供最少 4 位的海明距离 18。 I帧只包含控制器的状态（ C 息，不包含任何数据信息。当帧头的帧类型标志为 示发送的是控制器状态信息。控制器状态信息用于初始化和恢复时间失效的结点，它包含了一个结点在参与通信前需要获得的信息、该时刻在机群周期内的当前位置信息和哪一个结点正在起作用，此 外，控制器状态信息还包含当前的模式编号。如果一个结点因暂时的错误而失效，就要通过侦听 I帧进行恢复，并用 I帧提供的信息与网络进行同步。 用数据的地址在当前的 中。如果时间失效的结点需要某个特定应用的数据以便对网络进行恢复，它可以侦听具体的历史状态（ 息，该消息中携带着所需要的数据，以 N帧（正常帧）的形式传送，历史状态消息的发送是由主机来完成的。 间触发高可靠嵌入式系统的调度机制 协议是一种基于 协议，因而采用的也是基于时间的调度。不同结点的时间槽系列组成一个 （ 不同轮的系列组成一个 群周期 (这样，一个机群周期可能包括一个或多个 。在设计时就给系统中的每个处理结点分配固定的周期性的时间槽。时间触发协议采用绝对时钟进行同步，由一个时间主站周期性地向每个结点广播时钟基准消息，它标志着一个消息交互系列的开始。当结点成功接收到一个消息后，立即初始化结点内部的计时器，此后在整个交 互系列周期内，计时器指示相对于基准消息出现时刻的时间，各结点也将参照接收到的消息，对本结点时间进行设置或调整，以保持所要求的时间同步。计时器记录的一个全程时间即是一个周期时间。 图 4 说明了有 4 个结点的时间触发系统的运作 图，在这种情况下，每一轮总是只有一个发送方和三个接收方，所有结点协议的运行都在先验点上及时得到初始化，以后随着系统的运行，每个结点会根据消息发送的时间和自己 规定的消息到达时刻相对照，据此就可以调整时钟，始终与系统保持同步。全局时间基准通过分布式时钟同步算法而得到实现。当结点 1 的时间槽到 来时，结点 1 成为消息发送结点，此时其余结点都是接收结点，同样，结点 2、 3、 4 也是在自己的时间槽内进行消息发送。 接 收接 收接 收发 送接 收接 收接 收发 送接 收发 送 接 收接 收接 收接 收发 送接 收发 送结 点 1结 点 2结 点 3结 点 4t 1t 2 t 3t 4一 轮图 4 时间触发系统的运作图 要实现高可靠时间触发应用的调度，必须首先算出硬实时应用管理的处理器开销、最坏情况下的内核开销和系统调用开销。在时间触发系统中，所有的活动都是随时间的推进而完成的，这就意味着，除了计时中断外，系统不响应别的中断。轮询 I/O 和诊断 I/O 口这类活动，真接在计时中断例程中产生。时间触发系统一般采用静态调度策略，将它们 在一个周期内的调度信息列成一个表，调度方案就确定了，采用的调度策略只要按照时间的推进进行就可以了。也可以采用改善的时间触发调度策略，在确定了机群周期中的轮数和其中各结点的时间槽之后，可以采用图论的知识将各结点生成一棵树，在保证各个结点实时可靠性的前提下，应用图算法，算出最优调度方案，随着调度的进行，即时更新调度表，然后进行下一轮的调度。有关调度的更详细信 息，请参考文献 7。 由于每个消息有各自的时槽，这种消息的一个最大优点是各消息之间不会产生冲突，能很好地适应于要求硬实时高可靠系统的场合。 结点的组合能力和采用的容错机制 基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 15 （ 1） 的组合能力。在嵌入式分布式系统中，组合能力是一个重要的要求。一个运行良好的控制元件，在组成一个网络后不一定就运行良好。要有可组合性，网络中各控制元件必须满足系统的要求。相对于事件触发系统来说，采用 协议的时间触发系统有比较良好的可组合性。 （ 2）临界瞬时冲突解决机制。事件触发系统由于访问网络的随机性，会产生临界瞬时的冲突，而时间触发 采用 机制，有效地解决了这个问题。 （ 3）时序干扰的容错机制。位于主机和通信控制器之间的 是一个双端口的 了前面介绍的作用外，还有一个重要的作用就是时间防火墙。如图 1 所示， 发送数据时，主机将需要传输到网络的数据写到 双端口存储器中；当接收数据时， 协议处理器把网络上的传输数据也写到 双端口存储器中， 效地隔离了主机与协议控制器的时序行为，解网络和主机间的时序干扰。 第三章 实时通讯总线访问优化算法介绍及改善 息调度算法简介 上一节中具体介绍了 议的使用原理，为了实现高可靠性时间触发应用的调度，提出了采用调度算法来实现其改善时间触发调度的策略，由此本 节将提出具体实现的算法。所提出的算法将考虑到四种不同的 息调度方式。 态单消息 第一种方法为使用的 息调度为静态（离线）形式，且每个消息的时间表加入到 期的时槽内，并对对应节点发送消息。并且认为时槽可以保存进每个最大消息内。这种方法比较适合应用于汽车电子领域，这样的应用环境下，其消息的典型值较短，且比较容易诊断该系统是否达到瓶颈。 当每个时槽只插入一个确定且满足要求的消息，且没有别的干扰消息。当消息 m 错过响应时间时，就必须等待下一个消息对它进行分配才能再次执行。则它的延时时 间就是在一个连贯的时槽里面插入两个相同节点之间的最大时间，并将它表示为图所示。 图 5 静态单消息下最坏环境下所需要的时间 在这种情况下，静态单消息下最坏环境下该消息所需要的时间因此，影响消息调度分析的主要方面为该消息为静态分配的时槽，并得到相应的需要根据静态单消息的连贯节点下发送出来的消息的长度，再加上所使用协议的控制帧和 验位。 当在综合的消息描述表中，设计者必须使用可调度的方式将消息分配到时间槽中。由于调整该过程的可调度性只能通过综合的消息描述表中参数此该参数在设置过程必须是最优的。 根据图 6 所描述的简单例子，可知有三个处理器 该三个处理基于可调度性与全局延迟的分布式嵌入系统实时通信中的总线访问优化 17 都处于运行状态。当处理器 完成一次操作时，向处理器 送消息 且还向处理器 送了消息 图 6a 中提出的 构，只有运行在时间槽中的 理器对于算法的讨论有影响，所以其它在时间槽上的处理器将都以灰色表示。根据图中的表述，将消息 配在时间槽位置的 1 和 4 中，并将消息 配在 2 和 3 中，其中消息 于其任务释放抖动那个而错过了其执行时间段时，故将其安排在位置 2 中。再根据图 6b 中表述的 结构，当消息 配在位置 2 和 4 中，将消息 配在位置 1 和 3 中，这样的形式可以实现将所有消息在规定的时间段内执行。 态多消息 第二种消息调度算法静态多消息算法为第一种的扩展。在该形式中，允许将多个消息插入到时间槽中，并且所有消息将通过在相同的时间槽内打包一起传输。在这种情况下，就不会出现干扰的现象，所以消息 m 的进入延时机制是和第一种消息调度提出的机制一样的，也就是说，在一个连贯的时槽里面插入两个相同节点之间的最大时间也为 图 6 消息调度算法静态单消息和多消息的优化消息描述表 然而，这种方式在综合消息表述表中提供了更多的自定义表述。但在使用这种 方式中，必须先确定在时间槽中有多少个消息且这些消息分别是哪些。这样的方法使得优化参数据这种方式再次来描述下图 6 中的表述，就可以知道使用静态多消息的算法， 结构就可以描述为图 6c 所表述的形式。在该描述中，消息 分配到相同的时间槽的位置 1 和 2 内。因此，在这种情况下，消息可以在最后执行时间内完成，并且释放抖动会比在图6b 中描述的更进一步得减少，虽然在图 6b 中描述的消息在最后执行时间前也能完成，但是 经历了很长的释放抖动。 态消息分配 上述提到的两种算法分别是静态下的以单个消息或多个消息插入到它们相应的时间槽中。而现在提出的第三种算法是当消息产生时将以动态的形式插入到结构中。 这样，当一个消息在发送进程中产生时，它将以优先级的顺序放入到一个消息队列中。根据消息的活跃度，在消息传输的过程中需要从队列的头中获取一个一定数量的消息和结构框架。而这些接受消息需要满足其长度不能超过帧的数据字段的长度的要求。这个长度的限制是由其各自处理器连续的时间槽长度决定的。当这些以动态的形式发送时，必须确定它们以一种确定的方式，即