DISTRIBUTED STATIC RESOURCE ALLOCATION- A GRAPHICAL APPROACH

Abstract

Distributed static resource allocation problem arises when number of processes contend for access to the available set of distributed resources with each process requiring a fixed subset of resources. Some processes may be able to access a resource concurrently, while other processes may require exclusive acess to the resource. The problem is to design an algorithm that guarantees each process eventual access to its needed resources while satisfying the given resource constraints. The problem is posed as an exclusion graph, with a vertex representing a process and an edge between two vertices indicating that the two corresponding processes must never access their resources concurrently. Two algorithms are presented as a solution to the problem. The first algorithm requires the maintenance of a global queue. The second needs only local communication. The processes in each algorithm communicate via message passing and execute the same code to satisfy the exclusion constraints, as well as freedom from deadlock and starvation. The algorithms are implemented for the case of a completely connected exclusion graph with ten vertices and their relative performance is compared.