Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model

Masataka TAKAMURA; Yoshihide IGARASHI

Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model

Masataka TAKAMURA, Yoshihide IGARASHI

Full Text Views

0

Share
Cite this

Summary :

We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.

Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.2 pp.246-254

Publication Date: 2003/02/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)

Category: Parallel/Distributed Algorithms

Cite this

Copy

Masataka TAKAMURA, Yoshihide IGARASHI, "Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model" in IEICE TRANSACTIONS on Information, vol. E86-D, no. 2, pp. 246-254, February 2003, doi: .
Abstract: We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e86-d_2_246/_p

Copy

@ARTICLE{e86-d_2_246,
author={Masataka TAKAMURA, Yoshihide IGARASHI, },
journal={IEICE TRANSACTIONS on Information},
title={Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model},
year={2003},
volume={E86-D},
number={2},
pages={246-254},
abstract={We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model
T2 - IEICE TRANSACTIONS on Information
SP - 246
EP - 254
AU - Masataka TAKAMURA
AU - Yoshihide IGARASHI
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2003
AB - We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.
ER -