Local Coteries and a Distributed Resource Allocation Algorithm

概要

論文の詳細を見る
In this paper, we discuss a resource allocation problem in distributed systems. Consider a distributed system consisting of a set of processes and a set of resources of identical type. Each process has access to a (sub)set of the resources. Different processes may have access to different sets of the resources. Each resource must be accessed in a mutually exclusive manner, and processes are allowed to request more than one resource at a time. Since all resources are of identical type, a process requesting k resources does not insist on k particular resources. However, once a resource has been allocated to a process, it cannot be allocated to another process until it is released. The mutual exclusion and k-mutual exclusion problems can be considered as special cases of the resource allocation problem. We first introduce a new class of quorum sets named local coteries as an extension of coteries, to take advantages of the fact that, in general, resources are not shared by all processes. Then, we propose a resource allocation algorithm, using a local coterie, that is both deadlock- and starvation-free. This algorithm allows resources requested by two processes to be allocated without any interference.
一般社団法人情報処理学会の論文
1996-08-15