高级操作系统(3)

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

1、高级操作系统AdvancedOperatingSystem熊焰yxiong@ustc.edu.cn0551_3600689中国科学技术大学计算机系第二章分布式路由算法分布式路由算法导论一般类型网络的最短路径路由算法特殊类型网络的单播算法特殊类型网络中的多播算法虚信道和虚网络完全自适应和无死锁路由算法几个自适应和无死锁路由算法容错单播的一般方法网格和圆环中的容错单播算法超立方中的容错单播算法容错组播算法2.5虚信道和虚网络网络资源在存储转发交换中，资源是缓冲区；在虫孔路由中，资源是信道。网络通信中，若消息在占有资源的前提下可以申请资源，就有可能发生死锁通过控制路由的自适应性可

2、以预防和避免死锁，同时也保证一定的容错性。虚信道和虚网络经常用于实现无死锁、自适应和（或）容错的路由。2.5虚信道和虚网络通过网络分区避免死锁通过网络分区可以避免死锁给定的网络可以分成几个子网。根据源和目标的位置，消息被路由到不同的子网举例说明：3X3网格的适应性双Y信道路由如图：在Y方向有两个物理信道（双向）（a）一个3X3网格的双Y信道网2.5虚信道和虚网络通过网络分区避免死锁（cont'd）上述网格被分成正、负两个子网（如下图）如果目标位于源的右侧，则使用正网；否则将使用负网。当源和目标同列时，两个子网都不用。由于两个子网中都没有回路，所以可避免死锁。（b）正

3、网络（c）负网络2.5虚信道和虚网络虚信道若网络没有双Y信道，则可用几个虚信道复用一个物理信道每个虚信道都有自己的缓冲区。当物理信道被其它虚信道使用时，就用这个缓冲区保存消息若虚信道间没有循环等待，就可避免死锁。假设上例改为单Y信道网，那么原来的正、负子网中所有的Y信道都是虚信道。2.5虚信道和虚网络虚信道（cont'd）当两个虚信道共享一个物理信道时，信道利用率大幅提高。虽然虚信道提供了一个具有多重信道的网络，但仍需仔细设计路由算法。例如，可以按照信道标记的升序使用虚信道，以便避免虚信道间循环依赖。2.5虚信道和虚网络虚网络比虚信道更高一级的虚拟化是虚网络一个给定

4、的物理网络被分成几个虚网络，每个虚网络包括一系列的虚信道。虚网络中相邻的节点被映射到物理网络中时也要相邻一般地，一个虚网络中的虚信道设置应避免信道间的回路。虽然仍有可能存在互相交叉的虚网络回路，但可以通过使虚网络遵循全序或偏序来避回路前面那个例子中，若使用单Y信道，则前面的正、负子网可认为是两个虚网络。显然每个网络中都没有回路。因每个路由过程最多只使用一个虚网络，所以不会产生互相交叉的虚网络回路。2.5虚信道和虚网络虽然虚网络包含虚信道，二者是完全不同的概念。一般地，虚信道的使用是与路由过程紧密相连的，包括源和目标的位置。必须合理安排虚信道，以避免死锁。虚网络通常设计为没有

5、回路，因而路由算法可以不必考虑死锁，除非存在交叉虚网络的依赖性2.5虚信道和虚网络虚信道举例考虑一个有四个节点的单向环。如果同时有几个路由进程启动，就会发生死锁。2.5虚信道和虚网络虚信道举例（cont'd）通过给每个链接增加两个虚信道可以避免死锁如图，信道被分为高虚信道，和Ch0,Ch1,Ch2,Ch3低虚信道Cl0,Cl1,Cl2,Cl32.5虚信道和虚网络虚信道举例（cont'd）若源地址大于目标地址，可从任何一个信道开始；但一旦使用一个高（低）信道，那以后也要使用同一信道若源地址小于目标地址，首先使用高信道，经过节点P3后，高虚信道切换为低虚信道图示为相应的信道依赖

6、图以信道为节点边为信道之间的切换关系P32.5虚信道和虚网络虚网络举例在上述虚信道方法中，给定的环被分成两个虚环：Vr1和Vr2每个环中都有一个回路。两个虚环：Vr1：高信道形成的虚环Vr0：低信道形成的虚环虚环形成的回路。图中，节点内的边表示回路中信道的切换关系2.5虚信道和虚网络虚网络举例（cont'd）要避免虚网络内部的回路，可以在vr1中禁止从Ch0切换到Ch3，和在vr0中禁止从Cl0切换到C13。P3中，Ch0到Ch3的切换被禁止；Cl0到Cl3的切换也被禁止2.5虚信道和虚网络虚网络举例（cont'd）可在任一步进行从vr1到vr0的虚网络切换（如图）例如若

7、源地址大于目标地址，如从P2到P0的路由可以从Ch2开始，并在P1切换至Cl1从P3到P0的路由中，可在P2或P1进行切换也可以不切换但若目标地址大于源地址，则必须在节点P3切换，因为在单向环中，若目标地址大于源地址，则必然要经过P3路由两个虚环都不允许在P3进行从Ch0到Ch3和Cl0到Cl3的切换。所以在P3只能进行Ch0到Cl3的切换图中，每个节点都可以进行vr1到vr0的虚网络切换2.5虚信道和虚网络虚网络举例（cont'd）基于虚网络的路由过程比基于虚信道的路由有更强的适应能力。在上例中，虚信道路由仅