  Deadlock detection scheduling is an important, yet often overlooked problem
that can significantly affect the overall performance of deadlock handling.
Excessive initiation of deadlock detection increases overall message usage,
resulting in degraded system performance in the absence of deadlocks; while
insufficient initiation of deadlock detection increases the deadlock
persistence time, resulting in an increased deadlock resolution cost in the
presence of deadlocks. The investigation of this performance tradeoff, however,
is missing in the literature. This paper studies the impact of deadlock
detection scheduling on the overall performance of deadlock handling. In
particular, we show that there exists an optimal deadlock detection frequency
that yields the minimum long-run mean average cost, which is determined by the
message complexities of the deadlock detection and resolution algorithms being
used, as well as the rate of deadlock formation, denoted as $\lambda$. For the
best known deadlock detection and resolution algorithms, we show that the
asymptotically optimal frequency of deadlock detection scheduling that
minimizes the overall message overhead is ${\cal O}((\lambda n)^{1/3})$, when
the total number $n$ of processes is sufficiently large. Furthermore, we show
that in general fully distributed (uncoordinated) deadlock detection scheduling
cannot be performed as efficiently as centralized (coordinated) deadlock
detection scheduling.
