For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Coterie for Generalized Mutual Exclusion Problem
Shao Chin SUNG Yoshifumi MANABE
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1999/05/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
distributed system, coterie, resource allocation algorithm,
Full Text: PDF(304KB)>>
This paper discusses the generalized mutual exclusion problem defined by H. Kakugawa and M. Yamashita. A set of processes shares a set of resources of an identical type. Each resource must be accessed by at most one process at any time. Each process may have different accessible resources. If two processes have no common accessible resource, it is reasonable to ensure a condition in resource allocation, which is called allocation independence in this paper, i. e. , resource allocation to those processes must be performed without any interference. In this paper, we define a new structure, sharing structure coterie. By using a sharing structure coterie, the resource allocation algorithm proposed by H. Kakugawa and M. Yamashita ensures the above condition. We show a necessary and sufficient condition of the existence of a sharing structure coterie. The decision of the existence of a sharing structure coterie for an arbitrary distributed system is NP-complete. Furthermore, we show a resource allocation algorithm which guarantees the above requirement for distributed systems whose sharing structure coteries do not exist or are difficult to obtain.