DIN中的死鎖避免和死鎖恢復

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

圖2 A,B,C,D 4個分組構成一個死鎖

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

直接互連結構在數(shù)據(jù)交換中的應用分析