On-the-fly deadlock prevention

Abstract

This paper reexamines deadlock prevention in the context of multiprocessor or distributed systems. The essential idea is to have a deadlock prevention process that executes “on-the-fly”, i.e. in parallel with processes that use resources. The prevention process determines in advance those requests that could be satisfied. The effect of this approach is to reduce greatly the overhead imposed by deadlock prevention. The contributions of the paper are an efficient algorithm for predicting which requests could be granted and efficient process interaction protocols for on-the-fly prevention. The predictor algorithm is also used for efficient determination of delayed requests that can be granted after a release.