Deadlock Detection Scheduling for Distributed Processes in the Presence of System Failure

摘要

The occurrence of deadlocks should be controled effectively by their detection and resolution, but may sometimes lead to a serious system failure. This fact implies that deadlock detection scheduling should be designed from the view points of not only the performance trade-off between overall message usage and deadlock persistence time but also the prevention of the system failure. In this paper, we reformulate the Ling et al.'s deadlock detection scheduling problem (2006) in the presence of system failures, and derive the optimal deadlock detection time mini­mizing the long-run average cost per unit time. By introducing the message complexities of the deadlock detection and resolution algorithms being used, we investigate the asymptotically optimal frequency of deadlock detection scheduling in terms of the number of distributed processes through the well-known Landau notation.%デッドロックの効率的な検出と解決は分散システムの安全な運用に必要不可欠であり，事実，分散プロセスにおけるデッドロックの累積がシステム障害に至るケースが数多く報告されている．本稿では，分散プロセスにおけるデッドロックがポアソン過程に従って生起し，さらにシステム障害がデッドロック生起頻度に関して幾何分布に従って発生する場合を考える．デッドロックの検出と解決に要するコストを分散プロセス数の関数として見なすことで，定常期待コストを最小にする最適デッドロック検出スケジュールを導出する．さらに，最適デッドロック検出スケジューリングのオーダー解析を行うことで，分散プロセス数とデッドロック検出頻度の漸近的な特性について調べる．