高级操作系统advancedoperatingsystem课件

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

1、高级操作系统AdvancedOperatingSystem陈香兰（代）xlanchen@ustc.edu.cn0551_3606864-83中国科学技术大学计算机系第四章分布式路由算法主要内容分布式路由算法导论一般类型网络的最短路径路由算法特殊类型网络的单播算法特殊类型网络中的多播算法虚信道和虚网络完全自适应和无死锁路由算法第四章分布式路由算法主要内容（cont'd）几个自适应和无死锁路由算法容错单播的一般方法网格和圆环中的容错单播算法超立方中的容错单播算法容错组播算法4.1分布式路由算法导论进程间通信类型有效的进程间通

2、信对分布式系统的性能很重要根据目标个数的不同，进程间通信的类型有：一对一（单播）一对多（组播）一对所有（广播）4.1分布式路由算法导论：通信延迟及其原因在基于消息传递的分布式系统中，消息一般在到达目标节点之前可能要通过一个或多个中间节点，故存在通信延迟。分布式系统中的通信延迟依赖于如下四个因素：网络拓扑：通常用图表示定义处理单元（PE）之间是如何连接的路由决定如何选择路径以便将消息传递到目的地。4.1分布式路由算法导论：通信延迟及其原因（cont'd）流量控制流量控制决定在消息沿路径传递时如何分配网络资源，包括：信道缓冲区

3、交换这是一个实际的机制，它决定消息如何从一个输人信道转到一个输出信道。4.1分布式路由算法导论：路由算法类型路由算法类型包括：特殊vs.一般最短vs.非最短确定型vs.适应型源路由vs.目标路由容错型vs.非容错型冗余型vs.非冗余型死锁避免型vs.非死锁避免型4.1分布式路由算法导论：一般型路由和特殊型路由一般型路由算法适合于所有类型的网络但是对于某种特定网络不是很有效特殊型路由算法只对特定的网络类型有效，如超立方、网格等这些算法由于利用了特定网络的拓扑属性，所以效率往往较高。4.1分布式路由算法导论：最短路由算法和非最

4、短路由算法最短路径算法对给定的源-目标对给出一个代价最小的路径路径的代价所有跳步（连接）代价的线性和。缺点：可能会导致网络某一部分的拥塞非最短路由算法可以将消息路由到一个更长的路径从而避免拥塞。在某些情况下，随机路由可能是有效的。4.1分布式路由算法导论：确定型路由和适应型路由确定型路径算法路由路径只在网络的拓扑发生改变时才发生变化，而且它不使用任何有关网络状态的消息。适应型路由算法路径根据网络流量而改变。4.1分布式路由算法导论：容错型路由和非容错型路由容错型路由算法即使出现错误，被路由消息也能保证送到。非容错型路由算法

5、假定路由不会出错路由算法不必动态调整自己的活动。4.1分布式路由算法导论：冗余型路由和非冗余路由冗余型路由算法用几个边分离（或节点分离）的路径向同一个目标发送多个拷贝。只要这些路径中的一个是好的，那么就会至少有一个消息拷贝到达目标。必须保证有且只有一个拷贝被接收非冗余型路由算法对每个目标只需转发消息的一个拷贝。死锁避免型路由和非死锁避免型路由死锁避免型路由算法通过仔细设计的路由算法，保证不发生死锁。非死锁避免型路由算法没有特别的设施来预防或避免死锁。可能发生死锁，也可能不发生死锁。4.1分布式路由算法导论：路由函数路由函

6、数定义一个消息如何从源节点路由到目标节点。每个PE在收到一个消息以后，都将决定：1）把这条消息传送到本地存储器，还是2）转发到一个邻接的PE有许多不同的路由函数的定义，例如依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的等等本章仅使用依赖于目标的路由函数4.2一般类型网络的最短路径路由算法许多分组交换网，如法国的Transpac或美国的ARPAnet都使用最短路径路由本节介绍三个一般类型网络的最短路径路由算法：Dijkstra集中式算法Ford分布式算法ARPAnet路由算法4.2一般类型网络的最短路径路由算法：分布式系

7、统图示一般地，一个分布式系统可以用图来表示：节点代表PE（处理单元）；边代表通信链接；每个链接的数字代表链接代价。右图显示了一个分布式系统的例子4.2.1Dijkstra集中式算法第一种类型的算法以集中式的风格进行路由Dijkstra集中式算法可以发现一个源节点到所有其他节点的最短路径。Dijkstra集中式算法需求：需要了解给定网络的全局拓扑消息，即：网络中所有其他节点的列表；节点之间的所有链接；每个链接的代价。4.2.1Dijkstra集中式算法：算法描述设D(v)是从源s到节点v的距离（沿给定路径的链接的代价

8、的和）l(v,w)是节点v和w之间的代价Dijkstra算法如下：设N={s}；对不在N中的每一个节点v，令D(v)=l(s,v)。对那些没有连接到s的节点赋值为∞。找到不在N中的一个节点w，使D(w)最小并将w加入N；然后对所有不在N中的其它节点计算并更新D(v)：D