第六章实时系统通信1引言在实施系统的不同设备间进行有效通信对于系统正确运作时至关重要的 嵌入式系统中的通信数据流: 从传感器和控制面板到处理器集群处理器集群之间从处理器到执行设备和输出显示设备之间通信开销增加了计算机的响应时间2引言3引言 硬实时系统 必须通过采用合适的通信协议从而限制系统在通信过程中的开销，否则就有可能因为通信延迟的问题会引起灾难性的后果。软实时系统（例如多媒体或视频会议） 信息在传送过程中过多的延迟相当程度上会降低所提供的服务质量偶尔发生超过信息传输期限的情况并非是致命的4引言通信性能评测指标l传统系统 系统吞吐量： 在一个单位时间内可以把多少数据通过网络从源传输到目标l实时系统 在一个特定的时间限内成功传送报文的概率丢失报文=传送时间无限结合了报文的传输速度和丢失概率5引言报文的延迟是由下面的开销造成的报文的格式化分包报文排队，如等待进入通信介质从源到目标发送报文 解格式化报文6引言实时通信一般可以被分为多种报文类型，其中每个类型的特征由其时间限、到达模式和优先级刻画出来硬实时系统（例如嵌入式系统）：通信时间限是同其所属任务的时间限相关的软实时系统（例如多媒体应用）：时间限直接同其应用相关7引言大多数实时通信源由以下两种方式发起通信:固定速率周期性地产生固定大小的数据包 最容易处理变速率无规则时间间隙发送固定大小的数据包有规则时间间隙发送可变大小的数据包（如视频包）例如: 声音源包括突发通话 ( 一段时间寂静后的突发数据包)8引言通信特征可能由于数据包流过网络上多个中间节点而改变，在这些中间节点处，不同的通信类竞争节点输出端带宽因此相互影响如右图例子，考虑到一个高优先级的突发通信类（类）在某个节点同一个低优先级的固定速率通信类（类）竞争。由于类在节点处被优先传输，它将导致类在0,a和b,c时间间隔内的传输数据被累积而延迟发送，直接导致该节点处类的传输也具有突发性。9通信介质三种最重要的通信介质:电介质光纤无线10通信介质a. 电介质双绞线和同轴电缆双绞线通过 RJ45/RJ11 接入 设备可以通过在同轴电缆上加一个T形连接器接入或使用插头式分接头接入11b. 光纤把电信号转换成光脉冲. 处理速度可以高达 10Gbps ( NOW ?)接收器接着将光信号转换回电信号光纤实用于：点到点网络和无源星形网络 .优点 高速免受电磁干扰的影响缺点很难在没有重大信号损失的情况下用分接头连接光纤维护成本高通信介质12c. 无线传输距离取决于:发送功率接收器敏感性噪声级别使用的差错控制编码类型使信号衰减的障碍 (墙、隔板、机器设备等等)优点 通信节点间无需线缆连接 专用的网络可以快速建立和重新配置.缺点干扰通信介质13网络拓扑我们在设计和开发网络的时候必须仔细选择计算机或者分布式系统的网络拓扑结构。因为网络拓扑的优劣将会影响到系统响应的时间和可靠性。网络拓扑结构分类：点到点共享式（或广播式）14接口接口节点节点节点节点节点节点接口接口接口接口网络路径共享网络共享网络点到点网络点到点网络网络拓扑151. 点到点拓扑点到点拓扑节点间有专线连接如果一个节点想发送信息到不和它相邻的节点上，就必须经过中间节点转发 (路由器, 网桥).2. 共享式（或广播式）拓扑共享式（或广播式）拓扑所有节点都能访问通信信道，不过在任何时候都只能有一个节点在信道上传输信息网络拓扑16最流行的拓扑结构:1. 总线结构总线末端都要用匹配阻抗来迅速衰减反射信号.接口可以是分接头或者转发点2. 环结构到达接口输入端的比特被复制到缓存区，经过处理之后（如果需要处理的话），再从接口输出端传送出去单总线结构单总线结构环结构环结构网络拓扑173.超立方体结构n维超立方体中有2n个节点节点按其编码从 0 to 2n 1 编号，并连接那些二进制编号中只有一个比特位不同的节点两个(n-1)维超立方体如节点般连接在一起就构成了一个n维超立方体长方形网10000111二维超立方体网络网络拓扑18网络拓扑192 X 2 开关的4种配置 4. 多级网络结构由开关盒控制每个开关有4种可能的配置方式网络拓扑208输入输入8输出的多级网络输出的多级网络消息传送21消息传送三种普通的消息传送方式:1. 包交换包交换消息被分解成标准长度或者可变长度的包每个包有指定源地址、目标地址和其他可能需要的信息的包头随后这些包将根据路由选择和流量控制算法被传往目的地2. 电路交换电路交换需要传送消息的时候，在源地址和目的地址间建立电路连接其他消息必须等待该消息传输结束后才能传输3. 蛀洞路由蛀洞路由在中继网中以流水线方式传输包一不小心就可能造成死锁22消息传送包交换的例子：在二维超立方体结构网络中，节点00发送一个包到节点11，有两种可能的路径：000111和001011。假定我们选择了前一种路线，节点00就发送包头标注了目标地址的包去节点01，并由节点01据此包头转发该包到目标节点23SD建立的链路建立的链路消息传送电路交换的例子：在前面我们讲到的8输入8输出的多级网络中，如果我们想从S到D发送一条消息，开关被设置成图中粗线所示的链路，在消息传送过程中将一直占用该链路24消息传送nmpq蛀洞路由中的死锁蛀洞路由中的死锁方框图蛀洞路由的死锁：多个片段序列传输一不小心就可能会引起死锁。如图，序列避免在节点m处转弯，因为序列正在该节点发送中。相似地，节点p，序列在等待序列；在节点q，序列在等待序列；在节点n，序列在等待序列25网络体系结构问题高层体系结构问题最高层上是由一系列可在互联网络上通信的节点构成每个节点可能是一个包括应用、系统和网络处理的多处理器，或者是一个共享内存段，也可能是I/O口网络体系结构应该具备可扩展性、实现简单和可靠性的要求，同时一对一通信的效率也应和一对多通信一样低层体系结构问题包括包处理、路由选择和错误/传输流控制. 在分布式实时系统中，可能会同时面临着时间限、时间管理和内务管理等问题网络处理器网络处理器 (NP)(NP) 设计来处理这些琐事的.26网络处理器 (NP)为从源任务到预期接收者之间的消息传递执行一些必要的操作.当应用任务想传送一条消息时，它会提供给NP关于预期接收者和消息数据的位置信息NP 任务 在源和目标节点间建立连接处理端到端的错误检测和消息重传 选择合适的路径 分配必要的带宽 将信息打包成数据块和数据段在目标节点重组包网络体系结构问题27Continue点到点网络: NP 必须选择合适的交换算法令牌网络: NP 必须选择合适的协议参数保证所有的报文按期到达NP 还必须实现成帧、同步和包排序网络体系结构问题28I/O 体系结构为了改进 I/O, 多个 I/O 设备需要被分散开并由相对简单可靠的控制器管理.多路访问 集成 I/O 设备，并分配控制器管理对每个集群中的设备访问一个控制器同系统中的三个节点建立链路0103142节点节点I/O 控制器控制器网络体系结构问题29协议协议分类基于竞争的协议VTCSMA协议（虚拟时间载波检测多址访问协议）窗口协议基于令牌的协议定时令牌协议IEEE 802.5 令牌环协议时行时止中继协议（Stop-and-go Multihop Protocol）总线登记通信协议（Polled bus protocol）分层轮询协议（Hierarchical round-robin protocol）基于时间限的协议（Deadline based protokol）容错路由（Fault tolerance routing）30协议: VTCSMAVTCSMA (虚拟时间载波检测多址访问)为单信道广播网络、总线拓扑和环拓扑设计的协议节点先检测信道是否被占用，如果没有则传送报文；如果被占用，就放弃本次传送，等待一段时间再重传 如果许多节点在同一时间内发送数据包，这可能会导致冲突如果发生碰撞，发送节点将中止，并在通道处于闲置状态后再尝试发送。CSMA分布式算法, 每个节点能决定其发送数据包的时间. 如何决定呢?31协议: VTCSMA每个节点当中的信息:信道的状态 ( 空闲或者繁忙 )在其传输缓存中等待在网络中传送的包的优先级. 同步时钟的时间VTCSMA 在每个节点使用两个时钟:真实的时钟 (RC) 显示“真实的时间”，并且这个时钟与其他节点的时钟同步虚拟时钟 (VC) 当信道繁忙的时候, VC 停止. 当信道空闲的时候, VC 复位，然后以斜率1来运行. 信道空闲的时候VC 运行比 RC 快，信道忙的时候VC不运行.32协议: VTCSMA33协议: VTCSMA34协议: VTCSMA首先，我们在这里做一些变量声明：: 从网络一端到另一端的传播时间AM : 报文(或包)M的到达时间TM: 发送报文M需要的时间DM: 报文M被传送到目的地必须遵循的时间限LM: 为满足时间限要求报文必须被发送的最后时间限 LM= DM TM - 35协议: VTCSMAVSX(M)数据包M开始传输的虚拟时间，根据后缀的不同分别有以下四个变种对VTCSMA-A对VTCSMA-T对VTCSMA-L对VTCSMA-D报文M的到达时间发送报文M需要的时间报文必须发送的最后时间报文M传送到目的地必须遵循的时间限36协议: VTCSMA一旦冲突发生每个冲突节点以概率p立即重传M否则（概率1-p）节点根据下面间隔时间I刻画的随机数修改VSX(M)对VTCSMA-A对VTCSMA-T对VTCSMA-L对VTCSMA-D37协议: VTCSMA信道由忙转闲后VC将做如下初始化：对VTCSMA-A对VTCSMA-T对VTCSMA-L和VTCSMA-D38协议: VTCSMA例6.9VTCSMA-L算法；=2；每个包的传输时间TM=15；传播时间=1节点M到达RC时刻DMLM110321622103620332056404420725639协议: VTCSMA=2节点M到达RC时刻DMLM1103216221036203320564044207256注意，尽管有足够的时间成功地传送4个包，M2还是被丢弃了。这是因为信道在RC=0和RC=8之间没有必要地空闲下来的缘故，也就是不足够大的缘故40协议: VTCSMA=4节点M到达RC时刻DMLM1103216221036203320564044207256然而也并不是越大越好。有兴趣的同学可以自行推导一下书上的例6.1041协议: 窗口协议窗口协议含义：窗口协议的命名归因于在每个节点保留的窗口。窗口是个时间间隔，所有节点的窗口是相同的。当包的最晚传输时间（LTTT）在此窗口内并且信道空闲时，该包就有资格传输。如果在同一个节点有多个包有资格被传输，那么节点将基于某个准则（如LTTT）从中选出一个先传输。工作原理：如果一个节点有包要传送，它会先检查总线上是否存在正在进行的数据传输。如果有，它会等到该传输停止，即当检测到总线至少有一个空闲时间片时。随后，节点在下一个时间片开始处传送LTTT值在窗口范围内的报文。如果多于一个节点在相同时间片同时传送数据，则数据包就会发生冲突，一旦监测到此冲突，则会中止所有正进行的传输。这些节点会引发窗口收缩，随后，只有LTTT值在收缩窗口范围内的报文将被传输。如果只剩一个这样的报文，则传输可顺利进行；否则，会产生另外的冲突，并导致窗口再次收缩。如果窗口收缩后总线持续静默，即没有包有在当前窗口内的LTTT值，那么窗口就必须被向右扩大。42协议: 窗口协议窗口协议基于冲突检测.不能保证信息被及时传送以满足其时间限的要求. 适用于软实时系统.系统包含一系列连在总线上的节点.每个节点持续检测总线并接收数据当包的最晚传输时间(LTTT)在此窗口并且信道空闲时，该包就有资格被传输如果一个节点有多个包传输，那么节点将基于某个准则（如LTTT）从中选出一个传输43协议: 令牌环基于令牌的协议令牌 一种许可节点在网络上传送自己的包的授权.只有持有令牌的那个节点才被允许传送数据 适用于总线拓扑结构或者环状拓扑结构44协议: 令牌环SD 起始界限AC 访问控制ED 终止界限FS 帧状态SA 源地址DA 目的地址FS = 00 - 目标节点不可用FS =10 - 目标节点可用，但帧在此节点不能被复制FS =11 - 目标节点成功收到帧发送节点回收已发送的数据帧时，会检查FS字段，并从令牌环上删去该数据帧SD ACED令牌格式数据包格式SDSAACDAEDEDFS消息消息错误控制码错误控制码IEEE802.5令牌环协议45协议: 时行时止协议时行时止中继协议满足严格的包传递时间限分布式算法每个节点不依赖中心控制而独立工作 所有有资格传输的节点在非抢先得优先级顺序下工作在没有包要传送的情况下，节点才会空闲下来帧是该算法的核心。每个帧同一个通信类密切相关。我们把一个同帧类型fi相关的包称为i类包。当每个i类包到达行进路径上的中间节点n时，至少在下一个fi帧实例到达前，节点n将留下该包，并在下一帧中传送此包。46协议: 时行时止协议例6.20 考虑一个只有一进一出两条链路的节点n，只有两种通信类型。在出口链路上，1类帧开始时间在，和时刻，2类帧开始在A，B和C时刻。此处有6个1类包到达，标记为1，2，3，4，5和6，并有4个2类包到达，标记为a，b，c和d。47协议: 总线登记协议总线登记协议假定总线网络是忙总线线路.当一个处理器在总线上广播时，线路将保持高电平当其结束广播后，线路则重置用线的“或”操作就可以简单完成重置.如果有两个信号A 和B 被同时放到线路上, 得到的信号将是 A或者B.48协议: 总线登记协议例6.21假定A=0110011 B=011010049协议: 分层轮询协议所有通信将被恰当地分为n类，每个通信类i用三元组（ni，bi，i）表示同类i相关的帧。假定不考虑一般性损失，且有1 2 . n。单位时间为传输单个数据包花费的时间。i类数据包在任意给定帧内最大可能的传送数量为ni，其中每个源j可能被分配到一个确定的最大值i(j)。由于该i类帧内最多可发送bi个包，如果i类数据包在配额内传送完毕，或者节点上没有i类数据包要传送，则服务程序开始处理（i+1）类包。这里，只要每类通信接收到自己每帧内分配的服务，就没有预先确定的数据包处理顺序。此协议是非工作量守恒的，即使有数据包要发送，发送方仍有可能出于空闲状态。这种情况发生在某类数据包用尽了当前帧下的配额，此时剩下的此类数据包必须等到下一帧发送。 50协议: 分层轮询协议51协议: 基于时间限协议基于时间限的协议抢占式 和 非抢占式在抢占式协议中，如果节点收到比正在发送的数据包时间限更迫近的包，该节点会中断当前的传输，随后马上开始传送此新到数据包。在非抢占式协议中。则不允许中断数据包的传输。52协议Protocol for real time systemProtocolDeadline guaranteeType of networkVTCSMANoBroadcastWindowNoBroadcastTimed tokenYesRingIEEE 802.5YesRingStop-and-goYesPoint-to-pointPolled busNoBusHierarchical round robinYesPoint-to-pointDeadline basedNoPoint-to-point53结束语谢谢大家54