DIN中的死鎖避免和死鎖恢復(fù)

由于存在占用資源者申請(qǐng)另一個(gè)資源的情形，在DIN中由于拓?fù)浣Y(jié)構(gòu)本身存在環(huán)狀路徑，所以在DIN中易死鎖。圖2所示，A,B,C,D是4個(gè)分組的路徑(Path)構(gòu)成循環(huán)形成死鎖的情形。文獻(xiàn)[4]討論了互連結(jié)構(gòu)中死鎖的問題，提出了用通道依賴圖(channel dependency graph，CDG)是否存在循環(huán)來判斷是否死鎖。文獻(xiàn)[6]改進(jìn)了這種方法，肯定了CDG圖的充分性和必要性，即動(dòng)態(tài)出現(xiàn)CDG圖循環(huán)時(shí)不死鎖。
解決死鎖的方法可分為兩大類：死鎖避免和死鎖恢復(fù)。死鎖避免是指通過在路由算法設(shè)置禁用某些資源來防止出現(xiàn)路徑環(huán)。文獻(xiàn)[10]通過限制一個(gè)方向上的路由來打破循環(huán)，避免死鎖。本文2中路由算法也都采用死鎖避免策略。死鎖避免是通過限制對(duì)一些資源(緩存或物理通道)的利用來防止死鎖，因此交換結(jié)構(gòu)資源利用率不高。
死鎖恢復(fù)是在發(fā)現(xiàn)結(jié)構(gòu)內(nèi)發(fā)生死鎖后，通過一定的策略來解決死鎖。允許分組使用交換結(jié)構(gòu)中的任何資源，提高交換結(jié)構(gòu)的資源利用率。一般有兩種死鎖恢復(fù)方法。消極死鎖恢復(fù)法，采用丟棄，偏移路由來處理死鎖分組。積極死鎖恢復(fù)法通過分配其他資源來傳送死鎖分組到達(dá)目標(biāo)節(jié)點(diǎn)。對(duì)于死鎖的判決是死鎖恢復(fù)機(jī)制中的一個(gè)難點(diǎn)，特別是在業(yè)務(wù)負(fù)載和分組長(zhǎng)度變化范圍大時(shí)。如何快速區(qū)別分組是阻塞還是死鎖。在文獻(xiàn)[11]中討論了基于等待時(shí)間的死鎖恢復(fù)機(jī)制。文獻(xiàn)[12]介紹了一種分布式死鎖檢測(cè)機(jī)制，它采用判斷阻塞分組中根節(jié)點(diǎn)的方法來降低誤判率。

圖2 A,B,C,D 4個(gè)分組構(gòu)成一個(gè)死鎖

在數(shù)據(jù)交換結(jié)構(gòu)中采用死鎖恢復(fù)機(jī)制更適合在數(shù)據(jù)交換技術(shù)中，整個(gè)結(jié)構(gòu)資源有限，數(shù)據(jù)交換對(duì)于傳送帶寬的要求更高。數(shù)據(jù)恢復(fù)機(jī)制需要結(jié)合自適應(yīng)路由算法來降低死鎖的發(fā)生率。因此分析各種路由算法的死鎖發(fā)生率是十分必要的。

直接互連結(jié)構(gòu)在數(shù)據(jù)交換中的應(yīng)用分析