Highly Concurrent Group Mutual Exclusion Algorithms Based on Ticket Orders

Masataka TAKAMURA  Yoshihide IGARASHI  

IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.2   pp.322-329
Publication Date: 2004/02/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
asynchronous distributed algorithms,  concurrency,  congenial talking philosophers,  group mutual exclusion,  shared memory,  

Full Text: PDF>>
Buy this Article

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.