Highly Concurrent Group Mutual Exclusion Algorithms Based on Ticket Orders

Masataka TAKAMURA; Yoshihide IGARASHI

Highly Concurrent Group Mutual Exclusion Algorithms Based on Ticket Orders

Masataka TAKAMURA, Yoshihide IGARASHI

Full Text Views

0

Share
Cite this

Summary :

Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.

Publication: IEICE TRANSACTIONS on Information Vol.E87-D No.2 pp.322-329

Publication Date: 2004/02/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category

Cite this

Copy

Masataka TAKAMURA, Yoshihide IGARASHI, "Highly Concurrent Group Mutual Exclusion Algorithms Based on Ticket Orders" in IEICE TRANSACTIONS on Information, vol. E87-D, no. 2, pp. 322-329, February 2004, doi: .
Abstract: Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e87-d_2_322/_p

Copy

@ARTICLE{e87-d_2_322,
author={Masataka TAKAMURA, Yoshihide IGARASHI, },
journal={IEICE TRANSACTIONS on Information},
title={Highly Concurrent Group Mutual Exclusion Algorithms Based on Ticket Orders},
year={2004},
volume={E87-D},
number={2},
pages={322-329},
abstract={Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.},
keywords={},
doi={},
ISSN={},
month={February},}

Copy

TY - JOUR
TI - Highly Concurrent Group Mutual Exclusion Algorithms Based on Ticket Orders
T2 - IEICE TRANSACTIONS on Information
SP - 322
EP - 329
AU - Masataka TAKAMURA
AU - Yoshihide IGARASHI
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2004
AB - Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.
ER -