高级操作系统AdvancedOperatingSystem00002

高级操作系统高级操作系统Advanced Operating System熊焰0551_3607394中国科学技术大学计算机系2/83第四章第四章 分布式路由算法分布式路由算法l分布式路由算法导论l一般类型网络的最短路径路由算法 l特殊类型网络的单播算法l特殊类型网络中的多播算法l虚信道和虚网络 l完全自适应和无死锁路由算法l几个自适应和无死锁路由算法 l容错单播的一般方法 l网格和圆环中的容错单播算法l超立方中的容错单播算法l容错组播算法3/834.5 虚信道和虚网络虚信道和虚网络l网络资源l在存储转发交换中，资源是缓冲区；l在虫孔路由中，资源是信道。l网络通信中，若消息在占有资源的前提下可以申请资源，就有可能发生死锁l通过控制路由的自适应性可以预防和避免死锁，同时也保证一定的容错性。l虚信道和虚网络经常用于实现无死锁、自适应和（或）容错的路由。4/834.5 虚信道和虚网络虚信道和虚网络通过网络分区避免死锁通过网络分区避免死锁l通过网络分区可以避免死锁l给定的网络可以分成几个子网。l根据源和目标位置的不同，消息被路由到不同的子网l举例说明：l33网格的适应性双Y信道路由l如图：lY方向有两个物理信道（双向）（a）一个33网格的 双Y信道网5/834.5 虚信道和虚网络虚信道和虚网络通过网络分区避免死锁（通过网络分区避免死锁（contd）l上述网格被分成正、负两个子网（如下图）l如果目标位于源的右侧，则使用正网；l否则将使用负网。l当源和目标同列时，两个子网都不用。l由于两个子网中都没有回路，所以可避免死锁。（b）正网络（c）负网络6/834.5虚信道和虚网络虚信道和虚网络虚信道虚信道l若网络没有双Y信道，则可用几个虚信道复用一个物理信道l每个虚信道都有自己的缓冲区。l当物理信道被其它虚信道使用时，就用这个缓冲区保存消息l若虚信道间没有循环等待，就可避免死锁。l假设上例改为单Y信道网，那么原来的正、负子网中所有的Y信道都是虚信道。7/834.5虚信道和虚网络虚信道和虚网络虚信道虚信道（contd）l当两个虚信道共享一个物理信道时，信道利用率大幅提高。l虽然虚信道提供了一个具有多重信道的网络，但仍需仔细设计路由算法。例如，l可以按照信道标记的升序使用虚信道，以便避免虚信道间循环依赖。8/83l比虚信道更高一级的虚拟化是虚网络l一个给定的物理网络被分成几个虚网络，每个虚网络包括一系列的虚信道。l虚网络中相邻的节点被映射到物理网络中时也要相邻l一个虚网络中的虚信道设置应避免信道间的回路。虽然仍有可能存在互相交叉的虚网络回路，但可以通过使虚网络遵循全序或偏序来避免回路l前面那个例子中，若使用单Y信道，则前面的正、负子网可认为是两个虚网络。l显然每个网络中都没有回路。因每个路由过程最多只使用一个虚网络，所以不会产生互相交叉的虚网络回路。4.5虚信道和虚网络虚信道和虚网络虚网络虚网络9/834.5虚信道和虚网络虚信道和虚网络l虽然虚网络包含虚信道，二者完全不同。l一般，虚信道使用与路由过程紧密相连，包括源和目标的位置。必须合理安排虚信道，以避免死锁。l虚网络通常设计为没有回路，因而路由算法可以不必考虑死锁，除非存在交叉虚网络的依赖性10/834.5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例l考虑一个有四个节点的单向环。如果同时有几个路由进程启动，就会发生死锁。11/834.5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例（contd）l通过给每个链接增加两个虚信道可以避免死锁l如图，信道被分为l高虚信道，和Ch0,Ch1,Ch2,Ch3l低虚信道Cl0,Cl1,Cl2,Cl312/834.5虚信道和虚网络虚信道和虚网络虚信道举例虚信道举例（contd）l若源地址大于目标地址，l可从任何一个信道开始；l但一旦使用一个高（低）信道，那以后也要使用同一信道l若源地址小于目标地址，l首先使用高信道，经过节点P3后，高虚信道切换为低虚信道l图示为相应的信道依赖图l以信道为节点l边为信道之间的切换关系P313/834.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例l在上述虚信道方法中，给定的环被分成两个虚环：Vr1和Vr2l每个环中都有一个回路。两个虚环：Vr1：高信道形成的虚环Vr0：低信道形成的虚环虚环形成的回路。图中，节点内的边表示回路中信道的切换关系14/834.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例（contd）l要避免虚网络内部的回路，可以l在vr1中禁止从Ch0切换到Ch3，和l在vr0中禁止从Cl0切换到C13。P3中，Ch0到Ch3的切换被禁止；Cl0到Cl3的切换也被禁止15/834.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例（contd）l可在任一步进行从vr1到vr0 的虚网络切换（如图）l若源地址大于目标地址，如l从P2到P0的路由可以从Ch2开始，并在P1切换至Cl1l从P3到P0的路由中，可在P2或P1进行切换l也可以不切换l但若目标地址大于源地址，则必须在节点P3切换，因为1.在单向环中，若目标地址大于源地址，则必然要经过P3路由2.两个虚环都不允许在P3进行从Ch0到Ch3 和Cl0到Cl3 的切换。所以在P3只能进行Ch0到Cl3的切换图中，每个节点都可以进行vr1到vr0的虚网络切换16/834.5虚信道和虚网络虚信道和虚网络虚网络举例虚网络举例（contd）l基于虚网络的路由比基于虚信道的路由有更强的适应能力。在上例中，l虚信道路由仅在P3进行高虚信道到低虚信道的切换l虚网络路由允许在任一点进行虚网络切换l为保证从vr1到vr0的切换生成一个合法的路由路径，l若Cli是vr0中的切换信道，则i必须不能小于剩余的路由跳跃数。17/834.5虚信道和虚网络虚信道和虚网络双环路由双环路由l上述每一个单向信道增加一个虚信道的方法叫双环路由l形式化地描述双环路由：l假定使用n个进程：Pn-1,Pn-2,P1,P0，信道是Ch或Cl：18/834.5虚信道和虚网络虚信道和虚网络双环路由算法双环路由算法总是可以走高信道仅当源大于目标时，才可走低信道任选高信道或低信道在非目标节点的情况下，一定切换到低信道只可能从高信道接收消息在非目标节点的情况下，高高，低低19/834.6 完全自适应和无死锁路由算法完全自适应和无死锁路由算法 l适应性和无死锁是两个互相矛盾的要求。l像2维网格的XY路由和n维立方的e-立方等决定性的无死锁路由虽然简单，但都不是适应性的。l一个决定性路由在存在错误组件（如链接或节点）的系统中有可能失效l例如，一个XY路由完成了X方向的路由，但在Y方向上由于错误被阻塞，这个信息就不能被继续转发l但没有限制的适应性路由可能引发死锁。l因此，必须在不引发死锁的前提下增加适应性20/834.6 完全自适应和无死锁路由算法完全自适应和无死锁路由算法l几乎所有的完全适应性路由都可以通过增加一定数量的虚信道（或虚网络）来避免死锁。l例如，一个最小化的适应性的n维立方路由可以通过加入n个虚信道来避免死锁。l每一步都使用比前一个具有更高标记的信道。l因为最多需要n步，所以n个虚信道足以避免虚信道之间的循环等待。l然而使用虚信道会引入附加的缓冲区等开销。所以，要尽量限制虚信道的数目。21/834.6.1 虚信道类虚信道类 l如前所述，通过引入足够多的虚信道，任何路由都可以保证避免死锁。l当路由开始时，使用虚信道1，vc1。l在第i 步使用虚信道i，vci及相应的链接。l如果一个给定网络的最长路径（也叫直径）是Dmax，那么就要用Dmax个虚信道；22/834.6.1 虚信道类虚信道类l为减少虚信道的数量，可将一个网络分成几个节点的子集，每个子集都不会包含相邻的节点。l例如，l考虑一个形似跳棋盘的2维网格，上面有黑白方格。l黑节点属于个子集，白色节点属于另外一个。l当一个消息从一个白色节点移动到黑色节点时，就将虚信道的标记加一。l如果是从黑色节点向白色节点移动，虚信道标记保持不变。l显然，在2维网格中，节点标记的改变次数最多为路由步数的一半。这样虚信道的总数就缩减了一半。23/834.6.1 虚信道类虚信道类l可将上述思想一般化：l将给定网络分成k个子集（前面的例子相当于k=2的情形）S1,S2,Sk，每个子集都不包含相邻节点l当一个消息从子集Si中的一个节点移动到子集Sj中的一个节点（i j）时，称之为上移动；反之为负移动。l发生负移动时，虚信道标记+1l假定信道标记从1 开始l从而，所需信道的个数就是一个路由路径中负移动的个数。l目标就是要选择一个合适的k以及一个划分，使路由过程中的负移动个数最小24/834.6.2 逃逸信道逃逸信道等待和非等待信道等待和非等待信道l使用逃逸信道的路由算法中，虚信道被分为等待信道（又称为逃逸信道）和l若一个等待信道处于繁忙状态，而此时一个消息需要通过该信道，则这个消息必须等待，直到该信道可用l即一个等待信道能够阻塞消息非等待信道（又称为一般信道）l若一个消息碰到一个处于繁忙状态的非等待信道，它不必被阻塞以等待该信道变得可用，可以选择其他信道l因此，一个消息会首先考虑通过非等待信道到达目标l若所有的非等待信道都繁忙，它就考虑等待信道25/834.6.2 逃逸信道逃逸信道混合路由混合路由 l使用逃逸信道来扩展完全适应的概念l例如，可以用两个路由进程实现混合路由：路由进程1：完全适应性路由完全适应性路由，使用标记为非等待的虚信道；路由进程2：限制性但无死锁路由限制性但无死锁路由可能是XY路由或e-立方等决定性路由使用标记为等待的虚信道。26/834.6.2 逃逸信道逃逸信道混合路由混合路由（contd）l混合路由算法：1.开始时，使用完全适应路由，直到阻塞为止；2.然后切换到限制性路由。l混合路由是无死锁的l由于等待信道是在无死锁路由中定义的，并且l消息仅仅等待上述等待信道l合理分配等待和非等待信道是关系到混合路由效率的关键问题27/834.6.2 逃逸信道逃逸信道混合路由的扩展混合路由的扩展Il扩展I：当消息发现等待信道被占用时，可以使用非等待信道l扩展I增加灵活性的同时也引入了选定的逃逸信道之间新的依赖性。l通过使用一个或多个中间的一般信道，一个逃逸信道可能间接地依赖于另一个逃逸信道。l因此无回路条件必须包括逃逸信道之间的所有间接依赖。l不幸的是，没有循环依赖只是不发生死锁的一个充分条件；也即，对于一个特定的虫孔网络，若使用某一个路由算法，扩展I太弱，不会得到任何结果。扩展信道依赖图中的一个回路可能表示一个死锁状态，也可能不是。28/834.6.2 逃逸信道逃逸信道混合路由的扩展混合路由的扩展I IlDuato通过使用基于消息目标的逃逸路径进一步扩展了上述思想 l对于不同的目标，使用不同的逃逸信道。l在同样的无回路条件下，可以得到一个无死锁的充分必要条件。l然而，在生成扩展信道依赖图的时候，直接依赖、间接依赖、直接交叉依赖（在不同目标的逃逸信道之间）和间接交叉依赖都要被考虑进去。29/834.6.2 逃逸信道逃逸信道l上述两个扩展都可用于避免死锁。l为设计一个无死锁的路由函数，首先创建一个名为R1(x,y)的路由子函数，它的功能是将当前和目标节点映射到当前节点的输出信道的子集。R1(x,y)是连通的，无回路的。可以通过增加信道或者将已有信道分割为虚信道将R1(x,y)扩展为R(x,y)，以便增加可选路径的数目，同时又不会在R1(x,y)的扩展信道依赖图中增加回路。l这一设计规程又被称为Duato协议。30/834.6.2 逃逸信道逃逸信道维度逆转路由维度逆转路由 l若不要求最小路由，则虚信道的数量还可减少。l对于一个k元n维立方（没有环绕连接），有如下的一般非最小无死锁路由：l对每个物理信道，有k个虚信道与之对应l其中一个用于逃逸信道，以便进行无死锁的按维排序的路由l消息可以按照任何方向路由，而不一定是最小路径。l每个消息都有一个维度逆转数DR相对应，lDR：记录消息从高维度路由到低维度的次数。31/834.6.2 逃逸信道逃逸信道维度逆转路由维度逆转路由（contd）l一旦一个消息取得一个信道，它就将该信道标记为当前的DR数。l为避免死锁，一个DR数为i的消息不能等待一个DR数为j的信道，这里ij。l此时，选用下一层的虚信道。l假定每个未被访问的信道的DR标记为0。l当虚信道的标记达到k时，就使用决定性的按维度排序的路由。32/834.7 几个部分适应和无死锁路由算几个部分适应和无死锁路由算法法l很多路由算法的路由适应性仅对一小部分虚信道有效。这种算法属于部分适应性路由l本节讨论三个部分适应性和无死锁路由算法l转弯模型l平面自适应模型l其他部分自适应模型33/834.7.1 转弯模型转弯模型 l2维网格的转弯模型提供了一个部分适应性和无死锁的路由。l下图显示了2维网格中的抽象回路。34/834.7.1转弯模型转弯模型基本思想基本思想l上图显示了XY路由中所允许的四个转弯（实心箭头所指）。l只允许先X方向路由后Y方向路由l显然，这个条件太严格了，因为可以通过去掉回路中的一个角来打破回路。l转弯模型的基本思想l通过禁止最小数目的转弯来增加适应性，以避免回路。X方向Y方向35/834.7.1 转弯模型转弯模型正向优先协议和负向优先协议正向优先协议和负向优先协议l左下图为一个正向优先路由协议。l可以有6个转弯l从负向到正向的转弯，也即南到东和西到北，被禁止l右下图为一个负向优先路由协议。l可以有6个转弯l从正向到负向的转弯，也即北到东和东到北，被禁止X方向Y方向X负到Y正Y负到X正X正到Y负Y正到X负正向优先协议负向优先协议36/83正向优先路由协议正向优先路由协议37/834.7.1 转弯模型转弯模型转弯模型的适应性转弯模型的适应性l由于源和目标的位置的不同，转弯模型可能有适应性，也可能没有。l下图显示了源s和目标d的两种不同位置。l若目标位于源的东北或西南方，那么正向优先路由就是完全适应性的，如图al否则，就是决定性的，如图b（a）完全适应性路由（b）确定性路由东北东南OKNot OK38/834.7.1 转弯模型转弯模型转弯模型的平衡性转弯模型的平衡性l某些情况下，上述不平衡的适应可能会导致拥塞或不平衡的工作量。l可以使用虚信道将几种不同的协议结合起来。每个协议都基于转弯模型，但有不同的区域适应性，因而可以得到一种平衡的方法。l例如，若允许使用两个虚信道，就可设计两个具有互补适应性的转弯模型。39/834.7.2 平面自适应模型平面自适应模型 l对应于一般的k元n维立方，Chien和Kim提出了一种部分适应性和无死锁的路由。l基本思想是：l在某一时刻将路由的自由度限制到几个维度以降低对硬件（虚信道）的要求。l例如，若每次只选两个维度，就有A0,A1,An这些平面，其中Ai在维度di和di+1方向扩展。40/834.7.2 平面自适应模型平面自适应模型举例举例l下图显示了三个平面的例子：A0（维度为d0和d1），A1（维度为d1和d2），和A2（维度为d2和d3）平面自适应路由所允许的路径41/834.7.2 平面自适应模型平面自适应模型举例举例l对每个Ai，引入三个虚信道，一个沿着第i 维，两个沿着第（i+1）维。l设di,j是维度j通过维度i的虚信道。lAi使用三个虚信道：di,2、di+1,0和di+1,142/834.7.2 平面自适应模型平面自适应模型l由于每个虚信道都是双向的，可将di,2分成两个单向信道di,2+和di,2-lAi也就被分成两个子网：包含di,2+和di+1,0的正向子网；以及包含di,2-和di+1,1的负向子网l本课开始的正负子网可看成是上述正向和负向子网的例子：l将X和Y视为di和di+1正网络负网络43/834.7.2 平面自适应模型平面自适应模型lAi内部的路由可依据源和目标的位置不同而选用正向或负向子网。l若目标的标识大于源标识，则选用正向子网；l否则，选用负向子网。l注意：l虚信道di,di,0,di,1中的另外两个也用于平面Ai-1，即相邻平面有一个公共维度。l相对于完全适应而言，平面适应方法牺牲了一些路由自由度（适应性），从而大大降低了虚信道的数目。44/834.7.3 其他部分自适应模型其他部分自适应模型lLi出了e-立方路由的一个要求稍低的版本。l对一个超立方中的任意回路，我们总能找出沿着最低维度的两个链接，比如设该维度为i。l其中一个链接是从第i位为0的节点到第i 位为1 的节点（正向链接）l另一个是从第i 位为1的节点到第i位为0 的节点（负向连接）。l为了打破一个回路，只需禁止从较高维度的正向连接向沿着维度i的负向连接转换即可，除非这个转换符合e立方路由。45/834.7.3 其他部分自适应模型其他部分自适应模型l如果e立方路由满足维度递增的顺序，一个沿着维度dim(c1)的信道c1到一个沿着维度dim(c2)的信道c2的转换是允许的当且仅当下述条件中的一个为真：1.dim(c1)0)网中，使用三个虚信道来避免死锁。l对n维圆环，每个环绕信道需要两个虚信道来打破同一个维度中的回路。总之，对n(n0)维圆环需要6 个虚信道。l2 维网格中，使用两个虚信道，网络被分成正/负向两个子网。l类似地，在2 维圆环中，使用4个虚信道。68/834.9.2 基于有限全局信息的路由基于有限全局信息的路由Wu的最优容错路由算法的最优容错路由算法lWu提出了一个有出错块的2维网格的最优容错路由算法。l首先，他证明：设节点(0,0)是源节点，节点(i,j)是目标节点。若没有出错块通过X和Y轴，那至少存在一个始于(0,0)的最优路径，长度为|i|+|j|。l在一给定的2维网格中，上述结果对任意位置的目标节点和任何数目和分布的出错块都成立，相应的源叫做安全的。l上述结果可以进一步扩展：允许X和Y轴有出错块，只要它们到源的距离分别大于|i|和|j|。这样的源节点叫做扩展安全的。69/834.9.2 基于有限全局信息的路由基于有限全局信息的路由Wu的最优容错路由算法的最优容错路由算法l有两个最优和适应性容错的路由算法：l面向目标路由，和l面向源路由。l为简单起见，假定源节点是(0,0)，目标节点是(i,j)，且i,j=0，即路由永远是向东北方向的。70/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目标的路由面向目标的路由l面向目标的路由使用最短路径区域RMP的概念：l对给定的源和目标对，RMP包含最短路径的所有中间节点l为建立RMPl做一条从目标节点(i,j)开始到Y轴结束的线。l遇到出错块时，先向南绕过出错块，然后继续向西l类似地，建立一个从(i,j)开始向南到X轴截止的线。l遇到出错块时，先向西绕过出错块，然后继续向南。l已经证明由向西和向南的线以及X轴和Y轴围起来的区域是RMP。71/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目标的路由面向目标的路由举例举例l下图显示了一个RMP的例子，这里向西的线标记为路径A，向南的线标记为路径B。72/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向目标的路由面向目标的路由l仅当源是扩展安全的，才使用面向目标路由l源通过一个最优或不是最优的路径向目标发一个信号l接到信号后目标发两个信号，一个向西一个向南向西的信号建立RMP的路径A，向南的信号建立RMP的路径B。l一旦源收到来自目标的两个信号，就意味着RMP已建立起来。源就用任何一种适应性最小路由发送路由消息。l遇到路径A（或路径B）的边界时，剩下的路由就要沿着路径A（路径B）发往目标。73/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由l为支持面向源的最优路由，必须把出错块的信息分布到系统中的特定节点上。l举例说明：下图显示了一个出错块L1,L2,L3,L4与出错块的四条线平行x0和y0的区域被分成8 个子区域：R1R8L14上的点可划归任一相邻区域。74/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由（contd）l显然，l可用任一最小路由算法到达R1,R2,R3,R7,R8中的点l可用XY路由（先X后Y）到达R6中的任何点。l可用YX路由（先Y后X）到达R4中的任何点。l用XY路由和YX路由都可到达R5 中的点。75/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由（contd）l当目标节点位于R4或R6时，为达到最优路由，位于L1（位于(x,y)西侧的节点）和L2（位于(x,y)南侧的节点）上的特定节点必须具有这个出错块的信息。这些信息可以用出错块的相应角的位置来编码。l特别地，为每个出错块建立两个概念上的路径l路径1（虚线）：(,y)(x,y)(x,y)(x,y)(-,y)l路径2（实线）：(x,)(x,y)(x,y)(x,y)(x,-)76/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源的最优路由面向源的最优路由（contd）l显然，l目标位于路径1的南侧或东侧的路由消息不能通过路径1。l目标位于路径2的北侧或西侧的路由消息不能通过路径2。l路径1的路径信息存储在(-,y)到(x,y)间的每个节点上l路径2的路径信息存储在点(x,-)到(x,y)间的每个节上l为最小化路径信息，只有每个转弯（出错块的角落）的位置是必要的。l所以(x,y)和(x,y)对路径1是必要的，而(x,y)和(x,y)对路径2是必要的。77/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源路由的步骤面向源路由的步骤l面向源路由的步骤：l首先使用任何一个适应性最小路由，直到遇到出错块的一个（路径1或路径2）为止。1.（遇到路径1的L1）若目标节点在路径1的南/东侧，那消息将一直留在L1直到到达出错块的L1和L4的边界为止；否则将穿过L1。2.（遇到路径2的L2）若目标节点在路径2的北/西侧，那消息将一直留在L2直到到达出错块的L2和L4的边界为止；否则将穿过L2。78/834.9.2 基于有限全局信息的路由基于有限全局信息的路由面向源路由的步骤面向源路由的步骤（contd）l上述方法中，两个虚信道足以避免死锁。l一个简单的方法是为东北和东南方向的路由使用正向子网，对西北和西南方向的路由使用负向子网。79/834.9.3 基于其他故障模型的路由基于其他故障模型的路由Wu的直角凸多边形模型的直角凸多边形模型l虽然矩形出错块很简单，但它引入了很多被禁止的非出错节点，即它们将不会在路由过程中起作用。l但矩形为凸形的特性使得可以用最少的虚信道把路由信息绕过出错区域。l另外一些非矩形的凸形出错块也被引入了。lWu将出错块模型扩展为直角凸多边形模型。l一个凸多边形的定义是：多边形P，P中的任意两点之间的线段都在P内部。l在直角凸多边形中，线段被限制为只能是水平或垂直的。80/834.9.3 基于其他故障模型的路由基于其他故障模型的路由直角凸多边形直角凸多边形l可以将给定的矩形出错块转换为一系列分离的直角凸多边形l这一思想根源于这样一个事实：l可以通过将出错块中的一些非出错节点移出去，从而将它们激活，同时又保持这个区域的凸性。81/834.9.3 基于其他故障模型的路由基于其他故障模型的路由活跃活跃/不活跃节点不活跃节点l与标准出错块中的安全/非安全定义不同，Wu给出了活跃/不活跃节点的概念：l所有出错节点都是非活跃的，所有安全节点都是活跃的。l一个非安全节点开始的时候是非活跃的但如果它有两个或两个以上的活跃邻居，那么它就可以称为活跃的。l因此，对于一个非出错节点，有三种可能情况：1.安全且活跃。2.非安全但活跃。3.非安全且不活跃。82/834.9.3 基于其他故障模型的路由基于其他故障模型的路由活跃活跃/不活跃节点举例不活跃节点举例l下图是将wu的活跃/不活跃规则用于图7-7的出错块的结果。l显然，结果是一个直角凸多边形。