II - ネットワークコンピューティング学講座

ネットワークコンピューティング論II課題
吉永研究室
1552013 多田昂介
Exercises E. 19
• 問相互結合網におけるデッドロックが存在する 4 つの具体
的な必要条件を示せ。次元順 (dimension-order) ルーティン
グは、これらのどれを取り除いているのか?“escape” ルーティ
ング経路を用いた適応型ルーティングはどれを取り除いてい
るのか?デッドロック回復 (regressive/progressive) 技術を用い
た適応型ルーティングはこれらのどれを取り除いているの
か?自身の解答を説明せよ。
Exercises E. 19
• デッドロックが存在する4つの必要条件は以下の通り
• 相互排除
– 一度に一つのパケットのみが資源を占有できる
• 確保と待機
– 少なくとも一つの資源を確保し、かつ他の持つ資源を獲得しようとして
いる状態のパケットが一つ以上存在する
• 横取り不能
– 資源の横取りは不可能
• 循環待機
– 「確保と待機」で他の資源を獲得しようとしている状態がサイクル的に
循環している
Exercises E. 19
• 次元順 (dimension-order) ルーティング
– X方向に進んでからY方向に進む。Y→Xへの移動は行わない
• 逆の次元に進むと循環待機が発生
– 確保と待機（循環待機）によるデッドロックを防ぐ
X方向
Y方向
Exercises E. 19
• “escape” ルーティング経路を用いた適応型ルーティング
– ネットワーク上のどの位置からも逃げられる「逃げ道」を作る
– 確保と待機（循環待機）によるデッドロックを防ぐ
• デッドロック回復 (regressive/progressive) 技術を用いた適応
型ルーティング
– 発生したデッドロックを検出し、そのパケットを排除し資源を強制的に
解放する
– 横取り不能状態を無くすことによりデッドロックを回避する。

Download Report