
For FullText 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.

Some Modifications of the Tournament Algorithm for the Mutual Exclusion Problem
Yoshihide IGARASHI Hironobu KURUMAZAKI Yasuaki NISHITANI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E82D
No.2
pp.368375 Publication Date: 1999/02/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: asynchronous processes, concurrency, distributed system, lockoutfreedom, mutual exclusion, shared memory,
Full Text: PDF>>
Summary:
We propose two lockoutfree (starvationfree) mutual exclusion algorithms for the asynchronous multiwriter/reader shared memory model. The first algorithm is a modification of the wellknown 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 (n1)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.

