The paper describes the Banker’s algorithm for deadlock avoidance in resource allocation systems together with a modification to the algorithm that seeks to reduce its execution time by identifying the conditions under which a process is known to be safe without exhaustive inspection for process termination. The execution time for the Banker’s algorithm applied to n processes and m types of resource is quoted as O(mn2) and that of the modified algorithm as O(mn), which is supported by simulation results.
The modified algorithm is known not to identify safe states successfully under certain conditions that are explicitly given, and the simulation results for a system with many types of resources raise questions about the exact behavior patterns of such systems.
Deadlock avoidance techniques have notoriously heavy run time overheads. This approach and the discussion of its implications are of interest to anyone implementing such methods.
