第六章—实时系统通信要点.ppt

1、1,第六章,实时系统通信,2,引言,在实施系统的不同设备间进行有效通信对于系统正确运作时至关重要的 嵌入式系统中的通信数据流: 从传感器和控制面板到处理器集群 处理器集群之间 从处理器到执行设备和输出显示设备之间 通信开销增加了计算机的响应时间,3,引言,4,引言,硬实时系统 必须通过采用合适的通信协议从而限制系统在通信过程中的开销，否则就有可能因为通信延迟的问题会引起灾难性的后果。 软实时系统（例如多媒体或视频会议） 信息在传送过程中过多的延迟相当程度上会降低所提供的服务质量 偶尔发生超过信息传输期限的情况并非是致命的,5,引言,通信性能评测指标 传统系统 系统吞吐量： 在一个单位时间内可以

2、把多少数据通过网络从源传输到目标 实时系统 在一个特定的时间限内成功传送报文的概率 丢失报文=传送时间无限 结合了报文的传输速度和丢失概率,6,引言,报文的延迟是由下面的开销造成的 报文的格式化分包 报文排队，如等待进入通信介质 从源到目标发送报文 解格式化报文,7,引言,实时通信一般可以被分为多种报文类型，其中每个类型的特征由其时间限、到达模式和优先级刻画出来 硬实时系统（例如嵌入式系统）：通信时间限是同其所属任务的时间限相关的 软实时系统（例如多媒体应用）：时间限直接同其应用相关,8,引言,大多数实时通信源由以下两种方式发起通信: 固定速率 周期性地产生固定大小的数据包 最容易处理 变速率

3、 无规则时间间隙发送固定大小的数据包 有规则时间间隙发送可变大小的数据包（如视频包） 例如: 声音源包括突发通话 ( 一段时间寂静后的突发数据包),9,引言,通信特征可能由于数据包流过网络上多个中间节点而改变，在这些中间节点处，不同的通信类竞争节点输出端带宽因此相互影响 如右图例子，考虑到一个高优先级的突发通信类（类）在某个节点同一个低优先级的固定速率通信类（类）竞争。由于类在节点处被优先传输，它将导致类在0,a和b,c时间间隔内的传输数据被累积而延迟发送，直接导致该节点处类的传输也具有突发性。,10,通信介质,三种最重要的通信介质: 电介质 光纤 无线,11,通信介质,a. 电介质 双绞线和

4、同轴电缆 双绞线通过 RJ45/RJ11 接入 设备可以通过在同轴电缆上加一个T形连接器接入或使用插头式分接头接入,12,b. 光纤 把电信号转换成光脉冲. 处理速度可以高达 10Gbps ( NOW ?) 接收器接着将光信号转换回电信号 光纤实用于：点到点网络和无源星形网络 . 优点 高速 免受电磁干扰的影响 缺点 很难在没有重大信号损失的情况下用分接头连接光纤 维护成本高,通信介质,13,c. 无线 传输距离取决于: 发送功率 接收器敏感性 噪声级别 使用的差错控制编码类型 使信号衰减的障碍 (墙、隔板、机器设备等等) 优点 通信节点间无需线缆连接 专用的网络可以快速建立和重新配置. 缺点

5、 干扰,通信介质,14,网络拓扑,我们在设计和开发网络的时候必须仔细选择计算机或者分布式系统的网络拓扑结构。因为网络拓扑的优劣将会影响到系统响应的时间和可靠性。 网络拓扑结构分类： 点到点 共享式（或广播式）,15,接口,接口,节点,节点,节点,节点,节点,节点,接口,接口,接口,接口,网络路径,共享网络,点到点网络,网络拓扑,16,1. 点到点拓扑 节点间有专线连接 如果一个节点想发送信息到不和它相邻的节点上，就必须经过中间节点转发 (路由器, 网桥). 2. 共享式（或广播式）拓扑 所有节点都能访问通信信道，不过在任何时候都只能有一个节点在信道上传输信息,网络拓扑,17,最流行的拓扑结构:

6、 1. 总线结构 总线末端都要用匹配阻抗来迅速衰减反射信号. 接口可以是分接头或者转发点 2. 环结构 到达接口输入端的比特被复制到缓存区，经过处理之后（如果需要处理的话），再从接口输出端传送出去,单总线结构,环结构,网络拓扑,18,3.超立方体结构 n维超立方体中有2n个节点 节点按其编码从 0 to 2n 1 编号，并连接那些二进制编号中只有一个比特位不同的节点 两个(n-1)维超立方体如节点般连接在一起就构成了一个n维超立方体,长方形网,10,00,01,11,二维超立方体网络,网络拓扑,19,网络拓扑,20,2 X 2 开关的4种配置,4. 多级网络结构 由开关盒控制 每个开关有4种可

7、能的配置方式,网络拓扑,21,8输入8输出的多级网络,消息传送,22,消息传送,三种普通的消息传送方式: 1. 包交换 消息被分解成标准长度或者可变长度的包 每个包有指定源地址、目标地址和其他可能需要的信息的包头 随后这些包将根据路由选择和流量控制算法被传往目的地 2. 电路交换 需要传送消息的时候，在源地址和目的地址间建立电路连接 其他消息必须等待该消息传输结束后才能传输 3. 蛀洞路由 在中继网中以流水线方式传输包 一不小心就可能造成死锁,23,消息传送,包交换的例子： 在二维超立方体结构网络中，节点00发送一个包到节点11，有两种可能的路径：000111和001011。假定我们选择了前一

8、种路线，节点00就发送包头标注了目标地址的包去节点01，并由节点01据此包头转发该包到目标节点,24,S,消息传送,电路交换的例子： 在前面我们讲到的8输入8输出的多级网络中，如果我们想从S到D发送一条消息，开关被设置成图中粗线所示的链路，在消息传送过程中将一直占用该链路,25,消息传送,蛀洞路由中的死锁方框图,蛀洞路由的死锁： 多个片段序列传输一不小心就可能会引起死锁。如图，序列避免在节点m处转弯，因为序列正在该节点发送中。相似地，节点p，序列在等待序列；在节点q，序列在等待序列；在节点n，序列在等待序列,26,网络体系结构问题,高层体系结构问题 最高层上是由一系列可在互联网络上通信的节点构

9、成 每个节点可能是一个包括应用、系统和网络处理的多处理器，或者是一个共享内存段，也可能是I/O口 网络体系结构应该具备可扩展性、实现简单和可靠性的要求，同时一对一通信的效率也应和一对多通信一样 低层体系结构问题 包括包处理、路由选择和错误/传输流控制. 在分布式实时系统中，可能会同时面临着时间限、时间管理和内务管理等问题 网络处理器 (NP) 设计来处理这些琐事的.,27,网络处理器 (NP) 为从源任务到预期接收者之间的消息传递执行一些必要的操作. 当应用任务想传送一条消息时，它会提供给NP关于预期接收者和消息数据的位置信息 NP 任务 在源和目标节点间建立连接 处理端到端的错误检测和消息重

10、传 选择合适的路径 分配必要的带宽 将信息打包成数据块和数据段 在目标节点重组包,网络体系结构问题,28,Continue 点到点网络: NP 必须选择合适的交换算法 令牌网络: NP 必须选择合适的协议参数保证所有的报文按期到达 NP 还必须实现成帧、同步和包排序,网络体系结构问题,29,I/O 体系结构 为了改进 I/O, 多个 I/O 设备需要被分散开并由相对简单可靠的控制器管理. 多路访问 集成 I/O 设备，并分配控制器管理对每个集群中的设备访问 一个控制器同系统中的三个节点建立链路,0,1,0,3,1,4,2,节点,I/O 控制器,网络体系结构问题,30,协议,协议分类 基于竞争的

11、协议 VTCSMA协议（虚拟时间载波检测多址访问协议） 窗口协议 基于令牌的协议 定时令牌协议 IEEE 802.5 令牌环协议 时行时止中继协议（Stop-and-go Multihop Protocol） 总线登记通信协议（Polled bus protocol） 分层轮询协议（Hierarchical round-robin protocol） 基于时间限的协议（Deadline based protokol） 容错路由（Fault tolerance routing）,31,协议: VTCSMA,VTCSMA (虚拟时间载波检测多址访问) 为单信道广播网络、总线拓扑和环拓扑设计的协议

12、节点先检测信道是否被占用，如果没有则传送报文；如果被占用，就放弃本次传送，等待一段时间再重传 如果许多节点在同一时间内发送数据包，这可能会导致冲突 如果发生碰撞，发送节点将中止，并在通道处于闲置状态后再尝试发送。 CSMA分布式算法, 每个节点能决定其发送数据包的时间. 如何决定呢?,32,协议: VTCSMA,每个节点当中的信息: 信道的状态 ( 空闲或者繁忙 ) 在其传输缓存中等待在网络中传送的包的优先级. 同步时钟的时间 VTCSMA 在每个节点使用两个时钟: 真实的时钟 (RC) 显示“真实的时间”，并且这个时钟与其他节点的时钟同步 虚拟时钟 (VC) 当信道繁忙的时候, VC 停止.

13、 当信道空闲的时候, VC 复位，然后以斜率1来运行. 信道空闲的时候VC 运行比 RC 快，信道忙的时候VC不运行.,33,协议: VTCSMA,34,协议: VTCSMA,35,协议: VTCSMA,首先，我们在这里做一些变量声明： : 从网络一端到另一端的传播时间 AM : 报文(或包)M的到达时间 TM: 发送报文M需要的时间 DM: 报文M被传送到目的地必须遵循的时间限 LM: 为满足时间限要求报文必须被发送的最后时间限 LM= DM TM - ,36,协议: VTCSMA,VSX(M) 数据包M开始传输的虚拟时间，根据后缀的不同分别有以下四个变种,对VTCSMA-A,对VTCSMA

14、-T,对VTCSMA-L,对VTCSMA-D,报文M的到达时间,发送报文M需要的时间,报文必须发送的最后时间,报文M传送到目的地必须遵循的时间限,37,协议: VTCSMA,一旦冲突发生 每个冲突节点以概率p立即重传M 否则（概率1-p）节点根据下面间隔时间I刻画的随机数修改VSX(M),对VTCSMA-A,对VTCSMA-T,对VTCSMA-L,对VTCSMA-D,38,协议: VTCSMA,信道由忙转闲后 VC将做如下初始化：,对VTCSMA-A,对VTCSMA-T,对VTCSMA-L和VTCSMA-D,39,协议: VTCSMA,例6.9 VTCSMA-L算法；=2； 每个包的传输时间T

15、M=15；传播时间=1,40,协议: VTCSMA,=2,注意，尽管有足够的时间成功地传送4个包，M2还是被丢弃了。这是因为信道在RC=0和RC=8之间没有必要地空闲下来的缘故，也就是不足够大的缘故,41,协议: VTCSMA,=4,然而也并不是越大越好。有兴趣的同学可以自行推导一下书上的例6.10,42,协议: 窗口协议,窗口协议 含义：窗口协议的命名归因于在每个节点保留的窗口。窗口是个时间间隔，所有节点的窗口是相同的。当包的最晚传输时间（LTTT）在此窗口内并且信道空闲时，该包就有资格传输。如果在同一个节点有多个包有资格被传输，那么节点将基于某个准则（如LTTT）从中选出一个先传输。 工作

16、原理：如果一个节点有包要传送，它会先检查总线上是否存在正在进行的数据传输。如果有，它会等到该传输停止，即当检测到总线至少有一个空闲时间片时。随后，节点在下一个时间片开始处传送LTTT值在窗口范围内的报文。如果多于一个节点在相同时间片同时传送数据，则数据包就会发生冲突，一旦监测到此冲突，则会中止所有正进行的传输。这些节点会引发窗口收缩，随后，只有LTTT值在收缩窗口范围内的报文将被传输。如果只剩一个这样的报文，则传输可顺利进行；否则，会产生另外的冲突，并导致窗口再次收缩。如果窗口收缩后总线持续静默，即没有包有在当前窗口内的LTTT值，那么窗口就必须被向右扩大。,43,协议: 窗口协议,窗口协议

17、基于冲突检测. 不能保证信息被及时传送以满足其时间限的要求. 适用于软实时系统. 系统包含一系列连在总线上的节点. 每个节点持续检测总线并接收数据 当包的最晚传输时间(LTTT)在此窗口并且信道空闲时，该包就有资格被传输 如果一个节点有多个包传输，那么节点将基于某个准则（如LTTT）从中选出一个传输,44,协议: 令牌环,基于令牌的协议 令牌 一种许可节点在网络上传送自己的包的授权. 只有持有令牌的那个节点才被允许传送数据 适用于总线拓扑结构或者环状拓扑结构,45,协议: 令牌环,SD 起始界限 AC 访问控制 ED 终止界限 FS 帧状态 SA 源地址 DA 目的地址,FS = 00 - 目

18、标节点不可用 FS =10 - 目标节点可用，但帧在此节点不能被复制 FS =11 - 目标节点成功收到帧,发送节点回收已发送的数据帧时，会检查FS字段，并从令牌环上删去该数据帧,数据包格式,IEEE802.5令牌环协议,46,协议: 时行时止协议,时行时止中继协议 满足严格的包传递时间限 分布式算法 每个节点不依赖中心控制而独立工作 所有有资格传输的节点在非抢先得优先级顺序下工作 在没有包要传送的情况下，节点才会空闲下来,帧是该算法的核心。每个帧同一个通信类密切相关。我们把一个同帧类型fi相关的包称为i类包。当每个i类包到达行进路径上的中间节点n时，至少在下一个fi帧实例到达前，节点n将留下该包，并在下一帧中传送此包。,47,协议: 时行时止协议,例6.20 考虑一个只有一进一出两条链路的节点n，只有两种通信类型。在出口链路上，1类帧开始时间在，和时刻，2类帧开始在A，B和C时刻。此处有6个1类包到达，标记为1，2，3，4，5和6，并有4个2类包到达，标记为a，b，c和d。,48,协议: 总线登记协议,总线登记协议 假定总线网络是忙总线线路. 当一个处理器在总线上广播时，线路将保持高电平