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
Kertas kerja ini membincangkan tentang masalah pengecualian bersama yang umum ditakrifkan oleh H. Kakugawa dan M. Yamashita. Satu set proses berkongsi set sumber daripada jenis yang sama. Setiap sumber mesti diakses oleh paling banyak satu proses pada bila-bila masa. Setiap proses mungkin mempunyai sumber boleh diakses yang berbeza. Jika dua proses tidak mempunyai sumber yang boleh diakses bersama, adalah munasabah untuk memastikan keadaan dalam peruntukan sumber, yang dipanggil kebebasan peruntukan dalam kertas kerja ini, iaitu, peruntukan sumber kepada proses tersebut mesti dilakukan tanpa sebarang gangguan. Dalam kertas ini, kami mentakrifkan struktur baharu, perkongsian struktur coterie. Dengan menggunakan struktur perkongsian bersama, algoritma peruntukan sumber yang dicadangkan oleh H. Kakugawa dan M. Yamashita memastikan keadaan di atas. Kami menunjukkan syarat yang perlu dan mencukupi tentang kewujudan kumpulan struktur perkongsian. Keputusan kewujudan koterie struktur perkongsian untuk sistem teragih sewenang-wenangnya adalah NP-lengkap. Tambahan pula, kami menunjukkan algoritma peruntukan sumber yang menjamin keperluan di atas untuk sistem teragih yang struktur perkongsiannya tidak wujud atau sukar diperoleh.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -