The search functionality is under construction.

The search functionality is under construction.

We propose two lockout-free (starvation-free) mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first algorithm is a modification of the well-known tournament algorithm for the mutual exclusion problem. By the modification we can speed up the original algorithm. The running time of the modified algorithm from the entrance of the trying region to the entrance of the critical region is at most (n-1)c+O(nl), where n is the number of processes, l is an upper bound on the time between successive two steps of each process, and c is is an upper bound on the time that any user spends in the critical region. The second algorithm is a further modification of the first algorithm. It is designed so that some processes have an advantage of access to the resource over other processes.

- Publication
- IEICE TRANSACTIONS on Information Vol.E82-D No.2 pp.368-375

- Publication Date
- 1999/02/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Algorithm and Computational Complexity

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.

Copy

Yoshihide IGARASHI, Hironobu KURUMAZAKI, Yasuaki NISHITANI, "Some Modifications of the Tournament Algorithm for the Mutual Exclusion Problem" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 2, pp. 368-375, February 1999, doi: .

Abstract: We propose two lockout-free (starvation-free) mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first algorithm is a modification of the well-known tournament algorithm for the mutual exclusion problem. By the modification we can speed up the original algorithm. The running time of the modified algorithm from the entrance of the trying region to the entrance of the critical region is at most (n-1)c+O(nl), where n is the number of processes, l is an upper bound on the time between successive two steps of each process, and c is is an upper bound on the time that any user spends in the critical region. The second algorithm is a further modification of the first algorithm. It is designed so that some processes have an advantage of access to the resource over other processes.

URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_2_368/_p

Copy

@ARTICLE{e82-d_2_368,

author={Yoshihide IGARASHI, Hironobu KURUMAZAKI, Yasuaki NISHITANI, },

journal={IEICE TRANSACTIONS on Information},

title={Some Modifications of the Tournament Algorithm for the Mutual Exclusion Problem},

year={1999},

volume={E82-D},

number={2},

pages={368-375},

abstract={We propose two lockout-free (starvation-free) mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first algorithm is a modification of the well-known tournament algorithm for the mutual exclusion problem. By the modification we can speed up the original algorithm. The running time of the modified algorithm from the entrance of the trying region to the entrance of the critical region is at most (n-1)c+O(nl), where n is the number of processes, l is an upper bound on the time between successive two steps of each process, and c is is an upper bound on the time that any user spends in the critical region. The second algorithm is a further modification of the first algorithm. It is designed so that some processes have an advantage of access to the resource over other processes.},

keywords={},

doi={},

ISSN={},

month={February},}

Copy

TY - JOUR

TI - Some Modifications of the Tournament Algorithm for the Mutual Exclusion Problem

T2 - IEICE TRANSACTIONS on Information

SP - 368

EP - 375

AU - Yoshihide IGARASHI

AU - Hironobu KURUMAZAKI

AU - Yasuaki NISHITANI

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E82-D

IS - 2

JA - IEICE TRANSACTIONS on Information

Y1 - February 1999

AB - We propose two lockout-free (starvation-free) mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first algorithm is a modification of the well-known tournament algorithm for the mutual exclusion problem. By the modification we can speed up the original algorithm. The running time of the modified algorithm from the entrance of the trying region to the entrance of the critical region is at most (n-1)c+O(nl), where n is the number of processes, l is an upper bound on the time between successive two steps of each process, and c is is an upper bound on the time that any user spends in the critical region. The second algorithm is a further modification of the first algorithm. It is designed so that some processes have an advantage of access to the resource over other processes.

ER -