PPT《高级操作系统Advanced Operating System》

d) 通过给每个链接增加两个虚信道可以避免死锁如图,信道被分为高虚信道,和Ch0, Ch1, Ch2, Ch3低虚信道Cl0, Cl1, Cl2, Cl3 4.5虚信道和虚网络虚信道举例(cont'

d) 若源地址大于目标地址,可从任何一个信道开始;

但一旦使用一个高(低)信道,那以后也要使用同一信道若源地址小于目标地址,首先使用高信道,经过节点P3后,高虚信道切换为低虚信道图示为相应的信道依赖图以信道为节点边为信道之间的切换关系 P3 4.5虚信道和虚网络虚网络举例 在上述虚信道方法中,给定的环被分成两个虚环:Vr1和Vr2每个环中都有一个回路. 两个虚环:Vr1:高信道形成的虚环Vr0:低信道形成的虚环 虚环形成的回路.图中,节点内的边表示回路中信道的切换关系 4.5虚信道和虚网络虚网络举例(cont'

d) 要避免虚网络内部的回路,可以在vr1中禁止从Ch0切换到Ch3,和在vr0中禁止从Cl0切换到C13. P3中,Ch0到Ch3的切换被禁止;

Cl0到Cl3的切换也被禁止 4.5虚信道和虚网络虚网络举例(cont'

d) 可在任一步进行从vr1到vr0 的虚网络切换(如图)例如若源地址大于目标地址,如从P2到P0的路由可以从Ch2开始,并在P1切换至Cl1从P3到P0的路由中,可在P2或P1进行切换也可以不切换但若目标地址大于源地址,则必须在节点P3切换,因为在单向环中,若目标地址大于源地址,则必然要经过P3路由两个虚环都不允许在P3进行从Ch0到Ch3 和Cl0到Cl3 的切换.所以在P3只能进行Ch0到Cl3的切换 图中,每个节点都可以进行vr1到vr0的虚网络切换 4.5虚信道和虚网络虚网络举例(cont'

d) 基于虚网络的路由过程比基于虚信道的路由有更强的适应能力.在上例中,虚信道路由仅在P3进行高虚信道到低虚信道的切换虚网络路由允许在任一点进行虚网络切换为了保证从vr1到vr0的切换生成一个合法的路由路径,若Cli是vr0中的切换信道,则i必须不能小于剩余的路由跳跃数. 4.5虚信道和虚网络双环路由 上述每一个单向信道增加一个虚信道的方法叫双环路由形式化地描述双环路由:假定使用n个进程:Pn-1,Pn-2,…P1, P0,信道是Ch或Cl: 4.5虚信道和虚网络双环路由算法 4.5虚信道和虚网络双环路由 在上述算法中,当进程发起路由时,如果i >

des ,可以使用高信道或者低信道.如果i <

des ,则只能使用高信道. 4.6 完全自适应和无死锁路由算法 适应性和无死锁是两个互相矛盾的要求.像2 维网格的XY路由和n维立方的e-立方等决定性的无死锁路由虽然简单,但都不是适应性的.一个决定性路由在存在错误组件(如链接或节点)的系统中有可能失效例如,一个XY路由完成了X方向的路由,但在Y方向上由于错误被阻塞,这个信息就不能被继续转发但没有限制的适应性路由可能引发死锁.因此,必须在不引发死锁的前提下增加适应性 4.6 完全自适应和无死锁路由算法 几乎所有的完全适应性路由都可以通过增加一定数量的虚信道(或虚网络)来避免死锁.例如,一个最小化的适应性的n 维立方路由可以通过加入n个虚信道来避免死锁.每一步都使用比前一个具有更高标记的信道.因为需要n步,所以n个虚信道足以避免虚信道之间的循环等........