The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article discute de problème d'exclusion mutuelle généralisée défini par H. Kakugawa et M. Yamashita. Un ensemble de processus partage un ensemble de ressources d'un type identique. Chaque ressource doit être accessible par au plus un processus à la fois. Chaque processus peut avoir différentes ressources accessibles. Si deux processus n'ont pas de ressource commune accessible, il est raisonnable d'assurer une condition dans l'allocation des ressources, appelée indépendance d'allocation dans cet article, c'est-à-dire que l'allocation des ressources à ces processus doit être effectuée sans aucune interférence. Dans cet article, nous définissons une nouvelle structure, coterie de structure de partage. En utilisant une coterie de structure de partage, l'algorithme d'allocation de ressources proposé par H. Kakugawa et M. Yamashita garantit la condition ci-dessus. Nous montrons une condition nécessaire et suffisante de l’existence d’une coterie de structure de partage. La décision de l’existence d’une coterie de structure de partage pour un système distribué arbitraire est NP-complète. De plus, nous montrons un algorithme d'allocation de ressources qui garantit l'exigence ci-dessus pour les systèmes distribués dont les coteries de structure de partage n'existent pas ou sont difficiles à obtenir.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Shao Chin SUNG, Yoshifumi MANABE, "Coterie for Generalized Mutual Exclusion Problem" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 5, pp. 968-972, May 1999, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_5_968/_p
Copier
@ARTICLE{e82-d_5_968,
author={Shao Chin SUNG, Yoshifumi MANABE, },
journal={IEICE TRANSACTIONS on Information},
title={Coterie for Generalized Mutual Exclusion Problem},
year={1999},
volume={E82-D},
number={5},
pages={968-972},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}
Copier
TY - JOUR
TI - Coterie for Generalized Mutual Exclusion Problem
T2 - IEICE TRANSACTIONS on Information
SP - 968
EP - 972
AU - Shao Chin SUNG
AU - Yoshifumi MANABE
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1999
AB - 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.
ER -