《高级操作系统AdvancedOperatingSystem讲课教案》由会员分享，可在线阅读，更多相关《高级操作系统AdvancedOperatingSystem讲课教案（140页珍藏版）》请在金锄头文库上搜索。
1、高级操作系统Advanced Operating System,熊焰 0551_3600689 中国科学技术大学计算机系,第二章 分布式路由算法,分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 虚信道和虚网络 完全自适应和无死锁路由算法 几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法 超立方中的容错单播算法 容错组播算法,2.5 虚信道和虚网络,网络资源 在存储转发交换中，资源是缓冲区； 在虫孔路由中，资源是信道。 网络通信中，若消息在占有资源的前提下可以申请资源，就有可能发生死锁 通过控制路由的自适应性可以预防
2、和避免死锁，同时也保证一定的容错性。 虚信道和虚网络经常用于实现无死锁、自适应和（或）容错的路由。,2.5 虚信道和虚网络通过网络分区避免死锁,通过网络分区可以避免死锁 给定的网络可以分成几个子网。 根据源和目标的位置，消息被路由到不同的子网 举例说明： 3X3网格的适应性双Y信道路由 如图： 在Y方向有两个物理信道（双向）,（a）一个3X3网格的 双Y信道网,2.5虚信道和虚网络虚信道,若网络没有双Y信道，则可用几个虚信道复用一个物理信道 每个虚信道都有自己的缓冲区。 当物理信道被其它虚信道使用时，就用这个缓冲区保存消息 若虚信道间没有循环等待，就可避免死锁。 假设上例改为单Y信道网，那么原
3、来的正、负子网中所有的Y信道都是虚信道。,2.5虚信道和虚网络虚信道（contd）,当两个虚信道共享一个物理信道时，信道利用率大幅提高。 虽然虚信道提供了一个具有多重信道的网络，但仍需仔细设计路由算法。例如， 可以按照信道标记的升序使用虚信道，以便避免虚信道间循环依赖。,2.5虚信道和虚网络虚网络,比虚信道更高一级的虚拟化是虚网络 一个给定的物理网络被分成几个虚网络，每个虚网络包括一系列的虚信道。 虚网络中相邻的节点被映射到物理网络中时也要相邻 一般地，一个虚网络中的虚信道设置应避免信道间的回路。虽然仍有可能存在互相交叉的虚网络回路，但可以通过使虚网络遵循全序或偏序来避回路 前面那个例子中，若
4、使用单Y信道，则前面的正、负子网可认为是两个虚网络。 显然每个网络中都没有回路。因每个路由过程最多只使用一个虚网络，所以不会产生互相交叉的虚网络回路。,2.5虚信道和虚网络,虽然虚网络包含虚信道，二者是完全不同的概念。 一般地，虚信道的使用是与路由过程紧密相连的，包括源和目标的位置。必须合理安排虚信道，以避免死锁。 虚网络通常设计为没有回路，因而路由算法可以不必考虑死锁，除非存在交叉虚网络的依赖性,2.5虚信道和虚网络虚信道举例,考虑一个有四个节点的单向环。如果同时有几个路由进程启动，就会发生死锁。,2.5虚信道和虚网络虚信道举例（contd）,通过给每个链接增加两个虚信道可以避免死锁 如图，
5、信道被分为 高虚信道，和Ch0, Ch1, Ch2, Ch3 低虚信道Cl0, Cl1, Cl2, Cl3,2.5虚信道和虚网络虚信道举例（contd）,若源地址大于目标地址， 可从任何一个信道开始； 但一旦使用一个高（低）信道，那以后也要使用同一信道 若源地址小于目标地址， 首先使用高信道，经过节点P3后，高虚信道切换为低虚信道 图示为相应的信道依赖图 以信道为节点 边为信道之间的切换关系,P3,2.5虚信道和虚网络虚网络举例,在上述虚信道方法中，给定的环被分成两个虚环：Vr1和Vr2 每个环中都有一个回路。,两个虚环： Vr1：高信道形成的虚环 Vr0：低信道形成的虚环,虚环形成的回路。
6、图中，节点内的边表示 回路中信道的切换关系,2.5虚信道和虚网络虚网络举例（contd）,要避免虚网络内部的回路，可以 在vr1中禁止从Ch0切换到Ch3，和 在vr0中禁止从Cl0切换到C13。,P3中， Ch0到Ch3的切换被禁止； Cl0到Cl3的切换也被禁止,2.5虚信道和虚网络虚网络举例（contd）,可在任一步进行从vr1到vr0 的虚网络切换（如图） 例如 若源地址大于目标地址，如 从P2到P0的路由可以从Ch2开始，并在P1切换至Cl1 从P3到P0的路由中，可在P2或P1进行切换 也可以不切换 但若目标地址大于源地址，则必须在节点P3切换，因为 在单向环中，若目标地址大于源地
7、址，则必然要经过P3路由 两个虚环都不允许在P3进行从Ch0到Ch3 和Cl0到Cl3 的切换。 所以在P3只能进行Ch0到Cl3的切换,图中， 每个节点都可以进行 vr1到vr0的虚网络切换,2.5虚信道和虚网络虚网络举例（contd）,基于虚网络的路由过程比基于虚信道的路由有更强的适应能力。在上例中， 虚信道路由仅在P3进行高虚信道到低虚信道的切换 虚网络路由允许在任一点进行虚网络切换 为了保证从vr1到vr0的切换生成一个合法的路由路径， 若Cli是vr0中的切换信道，则i必须不能小于剩余的路由跳跃数。,2.5虚信道和虚网络双环路由,上述每一个单向信道增加一个虚信道的方法叫双环路由 形式
8、化地描述双环路由： 假定使用n个进程：Pn-1,Pn-2,P1, P0，信道是Ch或Cl：,2.5虚信道和虚网络双环路由算法,2.5虚信道和虚网络双环路由,在上述算法中，当进程发起路由时， 如果i des ，可以使用高信道或者低信道。 如果i des ，则只能使用高信道。,2.6 完全自适应和无死锁路由算法,适应性和无死锁是两个互相矛盾的要求。 像2 维网格的XY路由和n维立方的e-立方等决定性的无死锁路由虽然简单，但都不是适应性的。 一个决定性路由在存在错误组件（如链接或节点）的系统中有可能失效 例如，一个XY路由完成了X方向的路由，但在Y方向上由于错误被阻塞，这个信息就不能被继续转发 但没
9、有限制的适应性路由可能引发死锁。 因此，必须在不引发死锁的前提下增加适应性,2.6 完全自适应和无死锁路由算法,几乎所有的完全适应性路由都可以通过增加一定数量的虚信道（或虚网络）来避免死锁。 例如， 一个最小化的适应性的n 维立方路由可以通过加入n个虚信道来避免死锁。 每一步都使用比前一个具有更高标记的信道。 因为需要n步，所以n个虚信道足以避免虚信道之间的循环等待。 然而使用虚信道会引入附加的缓冲区等开销。所以，要尽量限制虚信道的数目。,2.6.1 虚信道类,如前所述，通过引入足够多的虚信道，任何路由都可以保证避免死锁。 当路由开始时，使用虚信道1，vc1。 在第i 步使用虚信道i，vci及
10、相应的链接。 如果一个给定网络的最长路径（也叫直径）是Dmax那么就要用Dmax个虚信道；,2.6.1 虚信道类,为了减少虚信道的数量，可将一个网络分成几个节点的子集，每个子集都不会包含相邻的接点。 例如， 考虑一个形似跳棋盘的2维网格，上面有黑白方格。 黑节点属于个子集，白色节点属于另外一个。 当一个消息从一个白色节点移动到黑色节点时，就将虚信道的标记加一。 如果是从黑色节点向白色节点移动，虚信道标记保持不变。 显然，在2维网格中，节点标记的改变次数最多为路由步数的一半。这样虚信道的总数就缩减了一半。,2.6.1 虚信道类,可以将上述思想一般化： 将给定网络分成k个子集S1, S2, Sk
11、，每个子集都不包含相邻节点 当一个消息从子集Si中的一个节点移动到子集Sj中的一个节点（i j ）时，称之为上移动；反之为负移动。 发生负移动时，虚信道标记加一 假定信道标记从1 开始 从而，所需信道的个数就是一个路由路径中负移动的个数。 目标就是要选择一个合适的k以及一个划分，使路由过程中的负移动个数最小,2.6.2 逃逸信道等待和非等待信道,使用逃逸信道的路由算法中，虚信道被分为 等待信道（又称为逃逸信道）和 若一个等待信道处于繁忙状态，而此时一个消息需要通过该信道，则这个消息必须等待，直到该信道可用 即一个等待信道能够阻塞消息 非等待信道（又称为一般信道） 若一个消息碰到一个处于繁忙状态
12、的非等待信道，它不必被阻塞以等待该信道变得可用，可以选择其他信道 因此，一个消息会首先考虑通过非等待信道到达目标 若所有的非等待信道都繁忙，它就考虑等待信道,2.6.2 逃逸信道混合路由,使用逃逸信道扩展完全适应的概念 例如，可以用两个路由进程实现混合路由： 路由进程1：完全适应性路由，使用标记为非等待的虚信道； 路由进程2：限制性但无死锁路由可能是XY路由或e-立方等决定性路由使用标记为等待的虚信道。,2.6.2 逃逸信道混合路由（contd）,混合路由算法： 开始时，使用完全适应路由，直到阻塞为止； 然后切换到限制性路由。 混合路由是无死锁的 由于等待信道是在无死锁路由中定义的，并且 消息
13、仅仅等待上述等待信道 合理分配等待和非等待信道是关系到混合路由效率的关键问题,2.6.2 逃逸信道混合路由的扩展I,扩展I：当消息发现等待信道被占用时，可以使用非等待信道 扩展I增加灵活性的同时也引入了选定的逃逸信道之间新的依赖性。 通过使用一个或多个中间的一般信道，一个逃逸信道可能间接地依赖于另一个逃逸信道。 因此无回路条件必须包括逃逸信道之间的所有间接依赖。 不幸的是，没有循环依赖只是不发生死锁的一个充分条件；也即，对于一个特定的虫孔网络，若使用某一个路由算法，扩展I太弱，不会得到任何结果。扩展信道依赖图中的一个回路可能表示一个死锁状态，也可能不是。,2.6.2 逃逸信道混合路由的扩展I
14、I,Duato通过使用基于消息目标的逃逸路径进一步扩展了上述思想 对于不同的目标，使用不同的逃逸信道。 在同样的无回路条件下，可以得到一个无死锁的充分必要条件。 然而，在生成扩展信道依赖图的时候，直接依赖、间接依赖、直接交叉依赖（在不同目标的逃逸信道之间）和间接交叉依赖都要被考虑进去。,2.6.2 逃逸信道,上述两个扩展都可用于避免死锁。 为了设计一个无死锁的路由函数，首先创建一个名为R1(x,y)的路由子函数，它的功能是将当前和目标节点映射到当前节点的输出信道的子集。R1(x,y)是连通的，无回路的。可以通过增加信道或者将已有信道分割为虚信道将R1(x,y)扩展为R(x,y)，以便增加可选路
15、径的数目，同时又不会在R1(x,y)的扩展信道依赖图中增加回路。 这一设计规程又被称为Duato协议。,2.6.2 逃逸信道维度逆转路由,如果不要求最小路由，那么虚信道的数量还可以减少。 对于一个k元n维立方（没有环绕连接），有如下的一般非最小无死锁路由： 对每个物理信道，有k个虚信道与之对应 其中一个用于逃逸信道，以便进行无死锁的按维排序的路由 消息可以按照任何方向路由，而不一定是最小路径。 每个消息都有一个维度逆转数DR相对应， DR：记录消息从高维度路由到低维度的次数。,2.6.2 逃逸信道维度逆转路由（contd）,一旦一个消息取得一个信道，它就将该信道标记为当前的DR数。 为了避免死
16、锁，一个DR数为i的消息不能等待一个DR数为j的信道，这里ij。 此时，选用下一层的虚信道。 假定每个未被访问的信道的DR标记为0。 当虚信道的标记达到k时，就使用决定性的按维度排序的路由。,2.7 几个部分适应和无死锁路由算法,很多路由算法的路由适应性仅对一小部分虚信道有效。这种算法属于部分适应性路由 本节讨论三个部分适应性和无死锁路由算法 转弯模型 平面自适应模型 其他部分自适应模型,2.7.1 转弯模型,2维网格的转弯模型提供了一个部分适应性和无死锁的路由。 下图显示了2维网格中的抽象回路。,2.7.1转弯模型基本思想,上图显示了XY路由中所允许的四个转弯（实心箭头所指）。 只允许先X方向路由后Y方向路由 显然，这个条件太严格了，因为可以通过去掉回路中的一个角来打破回路。 转弯模型的基本思想 通过禁止最小数目的转弯来增加适应性，以避免回路。,X方向,Y 方 向,2.7.1 转弯模型正向优先协议和负向优先协议,左下图为一个正向优先路由协议。 可以有6个转弯 从负向到正向的转弯，也即南到东和西到北，被禁止 右下图为一个负向优先路由协议。 可以有6个转弯 从正向到负
