高级操作系统AdvancedOperatingSystemppt课件.ppt

《高级操作系统AdvancedOperatingSystemppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、操作系统陈香兰（代）第四章分布式路由算法主要内容分布式路由算法导论一般类型网络的最短路径路由算法特殊类型网络的单播算法特殊类型网络中的多播算法虚信道和虚网络完全自适应和无死锁路由算法第四章分布式路由算法主要内容（'）几个自适应和无死锁路由算法容错单播的一般方法网格和圆环中的容错单播算法超立方中的容错单播算法容错组播算法分布式路由算法导论进程间通信类型有效的进程间通信对分布式系统的性能很重要根据目标个数的不同，进程间通信的类型有：一对一（单播）一对多（组播）一对所有（广播）分布式路由算法导论：通信延迟及其原因在基于消息传递的

2、分布式系统中，消息一般在到达目标节点之前可能要通过一个或多个中间节点，故存在通信延迟。分布式系统中的通信延迟依赖于如下四个因素：网络拓扑：通常用图表示定义处理单元（）之间是如何连接的路由决定如何选择路径以便将消息传递到目的地。分布式路由算法导论：通信延迟及其原因（'）流量控制流量控制决定在消息沿路径传递时如何分配网络资源，包括：信道缓冲区交换这是一个实际的机制，它决定消息如何从一个输人信道转到一个输出信道。分布式路由算法导论：路由算法类型路由算法类型包括：特殊.一般最短.非最短确定型.适应型源路由.目标路由容错型.非容错型冗余

3、型.非冗余型死锁避免型.非死锁避免型分布式路由算法导论：一般型路由和特殊型路由一般型路由算法适合于所有类型的网络但是对于某种特定网络不是很有效特殊型路由算法只对特定的网络类型有效，如超立方、网格等这些算法由于利用了特定网络的拓扑属性，所以效率往往较高。分布式路由算法导论：最短路由算法和非最短路由算法最短路径算法对给定的源目标对给出一个代价最小的路径路径的代价所有跳步（连接）代价的线性和。缺点：可能会导致网络某一部分的拥塞非最短路由算法可以将消息路由到一个更长的路径从而避免拥塞。在某些情况下，随机路由可能是有效的。分布式路由算法

4、导论：确定型路由和适应型路由确定型路径算法路由路径只在网络的拓扑发生改变时才发生变化，而且它不使用任何有关网络状态的消息。适应型路由算法路径根据网络流量而改变。分布式路由算法导论：容错型路由和非容错型路由容错型路由算法即使出现错误，被路由消息也能保证送到。非容错型路由算法假定路由不会出错路由算法不必动态调整自己的活动。分布式路由算法导论：冗余型路由和非冗余路由冗余型路由算法用几个边分离（或节点分离）的路径向同一个目标发送多个拷贝。只要这些路径中的一个是好的，那么就会至少有一个消息拷贝到达目标。必须保证有且只有一个拷贝被接收非

5、冗余型路由算法对每个目标只需转发消息的一个拷贝。死锁避免型路由和非死锁避免型路由死锁避免型路由算法通过仔细设计的路由算法，保证不发生死锁。非死锁避免型路由算法没有特别的设施来预防或避免死锁。可能发生死锁，也可能不发生死锁。分布式路由算法导论：路由函数路由函数定义一个消息如何从源节点路由到目标节点。每个在收到一个消息以后，都将决定：）把这条消息传送到本地存储器，还是）转发到一个邻接的有许多不同的路由函数的定义，例如依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的等等本章仅使用依赖于目标的路由函数一般类型网络的最短路径路由

6、算法许多分组交换网，如法国的或美国的都使用最短路径路由本节介绍三个一般类型网络的最短路径路由算法：集中式算法分布式算法路由算法一般类型网络的最短路径路由算法：分布式系统图示一般地，一个分布式系统可以用图来表示：节点代表（处理单元）；边代表通信链接；每个链接的数字代表链接代价。右图显示了一个分布式系统的例子集中式算法第一种类型的算法以集中式的风格进行路由集中式算法可以发现一个源节点到所有其他节点的最短路径。集中式算法需求：需要了解给定网络的全局拓扑消息，即：网络中所有其他节点的列表；节点之间的所有链接；每个链接的代

7、价。集中式算法：算法描述设()是从源到节点的距离（沿给定路径的链接的代价的和）()是节点和之间的代价算法如下：设{}；对不在中的每一个节点，令()()。对那些没有连接到的节点赋值为∞。找到不在中的一个节点，使()最小并将加入；然后对所有不在中的其它节点计算并更新()：()[(),()()]重复步骤，直到所有节点都在中集中式算法：算法举例上述算法作用于如图所示的网络：以为源节点集合只包含源节点即{}。对不在中的节点计算：()()∞；（由于和不与直接相连）()()()()集中式算法：算法举例（'）取

8、()()()()中具最小值的对应节点加入到集合中,{},对不在中的其它节点更新(){()()()}{∞∞}∞,(){()()()}{∞},(){()()()}{}。集中式算法：算法举例（'）取()()()中具最小值的对应节点