数理解析研究所講究録 1325 巻 2003 年 57-62

57

A Highly Concurrent Algorithm for the Group Mutual
Exclusion Problem
高村政孝、 五十嵐善英

群馬大学工学部(Masataka Takamura and Yoshihide Igarashi)
Department of Computer Science, Gunma University
Abstract
Group mutual exclusion is an interesting generalization of the mutual exclusion
problem. This problem was introduced by Joung, and some algorithms for the probhave been proposed by incorporating mutual exclusion algorithms. Group mutual
exclusion occurs naturally in asituation where aresource can be shared by processesof the same grouP, but not by processes of adifferent group. It is also called thecongenial talking philosophers problem. In this paper we propose ahighly concurrent$\mathrm{l}\mathrm{e}\mathrm{m}$algorithm based on ticket orders for the group mutual exclusion problem in the asynchronous shared memory model. It is amodification of the Bakery algorithm for themutual exclusion problem. It uses single writer shared variables together with two
multi-writer shared variables that are never concurrently written. We show that thealgorithm satisfies lockout freedom as well as group mutual exclusion.

1

Introduction

Mutual exclusion is a problem of managing access to asingle indivisible resource that can
only support one user at atime. The -exclusion problem is anatural generalization of
the mutual exclusion problem [2, 3, 12]. The group mutual exclusion problem is anothernatural extension of the mutual exclusion problem. This problem was introduced by Joungin [6], and some algorithms for the problem have been proposed [4, 6, 7, 8]. Group mutual
exclusion is required in asituation where aresource can be shared by processes of thesame group, but not by processes of adifferent group. Acombination of exclusion andgroup mutual exclusion was also studied $[14, 15]$ . The algorithms given in [4, 6, 8, 14, 15]
use multi-writer/multi-reader shared variables in the asynchronous shared memory model.
As described in [6], group mutual exclusion can be described as the congenial talking
philosophers problem. We assume that there are philosophers. They spend their time
thinking alone. When aphilosopher is tired of thinking,attempts to attend aforum
and to talk at the forum. We assume that there is only one meeting room. A philosopher
wishing to attend aforum can do so if the meeting room is empty, or if some philosophersinterested in the same forum as the philosopher in question are already in the meetingroom. The congenial talking philosophers problem is to design an algorithm such that aphilosopher wishing to attends aforum will eventually succeed in doing so. Philosopher
$k$

$k$

$n$

$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$58interested in the same forum as the current forum held in the meeting room should be
encouraged to attend it. This performance is measured as concurrency of attending aforum. In this paper, we propose an algorithms based on ticket orders for the groupmutual exclusion problem in the asynchronous shared memory model.

2Preliminaries
The computational model used in this paper is the asynchronous shared memory model.
It is acollection of processes and shared variables. Processes take steps at arbitrary
speeds, and there is no global clock. Interactions between aprocess and its corresponding
philosopher are by input actions from the philosopher to the process and by output actions
from the process to the philosopher. Each process is considered to be astate machine witharrows entering and leaving the process, representing its input and output actions. All
communication among the processes is via shared memory.
Ashared variable is said to be regular if every read operation returns either the lastvalue written to the shared variable before the start of the read operation or avalue written
by one of the overlapping write operations [10]. Ashared variable is said to be atomic
if it is regular and the additional property that read operations and write operations
behave as if they occur in some total order [10]. In this paper, we assume that all sharedvariables are atomic. The algorithms given in this paper uses single-writer/multi-reader
shared variables, together with two multi-writer/multi-reader shared variables that arenever concurrently written.
Aphilosopher with access to aforum is modeled as being in the talking region. Whenis said to be in the thinking region.
aphilosopher is not involved in any forum,corresponding process executes
In order to gain admittance to the talking region,of the trying protocol to
executionofatrying protocol. The duration from the start
the entrance to the talking region is called the trying region. After the end of talking
corresponding process executes an exit protocol.
by aphilosopher at aforum,
The duration of execution of the exit protocol is called the exit region. These regions
are followed in cyclic order, from the thinking region to the trying region, to the talking
region, to the exit region, and then back again to the thinking region. The congenial
talking philosophers problem is to devise protocols for each philosopher to efficiently andwishes to talk under the conditions that there is only
fairly attend aforum whenasingleforum can be held in the meeting room at atime.
only
one meeting room and that, , ,who spend their time either thinking alone
We assume philosophers,
or talking in aforum. We also assume that there are $m$ different fora. Each philosopher$P_{i}(1\leq i\leq n)$ corresponds to process. The inputs to process from philosopher are$try_{i}(f)$ which means a request by philosopher
for access to the forum $f\in\{1, \ldots,m\}$which means an announcement of the end of talking by . The
to talk there, andwhich means granting attendance at theoutputs from process to philosopher are$think_{i}$thinking
can continue withwhich means thatmeeting room to , andalone without the use of the meeting room. These are external actions of the sharedmemory system. We assume that aphilosopher in aforum spends an unpredictable but
finite amount of time in the fomm. The system to solve the congenial talking philosophers
problem should satisfy the following conditions$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$$\mathrm{h}\mathrm{i}\mathrm{s}/\mathrm{h}\mathrm{e}\mathrm{r}$$\mathrm{h}\mathrm{i}\mathrm{s}/\mathrm{h}\mathrm{e}\mathrm{r}$$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$$P_{1}$$n$$P_{2}$$\ldots$$P_{n}$$i$$i$$P_{i}$$P_{i}$$exit\dot{*}$$i$$P_{i}$$\mathrm{P}\mathrm{i}$$P_{\dot{l}}$$talk_{i}$$P_{i}$$\mathrm{h}\mathrm{i}\mathrm{s}/\mathrm{h}\mathrm{e}\mathrm{r}$59(1) group mutual exclusion: If some philosopher is in a forum, then no other philos0pher can be in adifferent forum at the same time .
(2) lockout freedom: Any philosopher wishing to attend a forum eventually does so
if each philosopher in any forum always leaves the forum.

(3) progress for the exit region: If aphilosopher is in the exit region, then at somelater point
enters the thinking region.
$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$Waiting time and occupancy are important criteria to evaluate solutions to the congenial talking philosophers problem. Waiting time is the amount of time from when aphilosopher wishes to attend aforum until
attends the forum. Concurrency isimportant to increase system performance concerning the resource. It is desirable for asolution to the congenial talking philosophers problem to satisfy the following property
called concurrent occupancy [4, 7, 8].
$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$(4) concurrent occupancy: If some philosopher $P$ requests to attend aforum andno philosopher is currently attending or requesting adifferent forum, then $P$ cansmoothly attend the forum without waiting for other philosophers to leave the forum.

3

A Highly Concurrent Algorithm

The following procedure $(n, m)$ -HCGME is amodification of the Bakery algorithm forthe mutual exclusion problem [2, 9, 11], where is the number of philosophers, $m$ is thenumber of different fora, and $N$ is the set of natural numbers. Acapturing technique
is used to improve the concurrency performance of the algorithms for the group mutual
exclusion problem in [6, 7, 8]. The algorithm proposed in this paper uses adoor in
the doorway. Achair is chosen in each current forum. When the chair wishes to leave
the forum,closes the door to prevent other philosophers from entering the same
forum. While the door is open, philosophers wishing to enter the same forum as the current
forum held in the meeting room are allowed to enter it. In this way, concurrency can be
improved. All shared variables, except for door and chair, are single-writer/multi-reader
shared variables. Both door and chair are multi-writer/multi-reader shared variables,
but no concurrency of writing operations occurs concerning either of these two shared$n$$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$variables.
procedure $(n,m)$ -HCGME
shared variables, writable by process and readable by
all processes $j\neq i$ ;checkdw(i)\in {0, 1}, initially 0, writable by process and readable
by all processes $j\neq i$ ;ticket(i)\in N, initially 0, writable by process and readable by
all processes $j\neq i$ ;writable by prooess$\mathrm{i}\}\{1\ldotsn,\}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{y}$$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{y}i\intransit(i)\in\{0,$

$i$

$0$

$i$

$i$

$i\mathrm{m}\mathrm{d}$$forum\mathrm{r}\mathrm{e}A_{\mathrm{a}\mathrm{b}1\mathrm{e}\mathrm{b}\mathrm{y}\mathrm{a}\mathrm{i}\mathrm{i}_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{a}\mathrm{e}e\mathrm{s}j\neq i}}(i\in\{0,1,.,m\},\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{U}\mathrm{y}0,$$/orwm(0)$ , always 0, readable by all processes;$door\in${oPen, dose}, initially open, writable and readable by60,(but never concurrently written);$Chair\in\{0,1,\ldots,n\mathrm{a}11\mathrm{P}^{\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{s}}|_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{a}11\mathrm{y}0,\mathrm{w}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{a}\mathrm{b}1\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}\mathrm{a}\mathrm{b}1\mathrm{e}\mathrm{b}\mathrm{y}\mathrm{a}11\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{s}}^{\mathrm{b}\mathrm{u}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{c}\circ \mathrm{n}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}1\mathrm{y}\mathrm{w}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{n})}$process
input actions {inputs to process from philosopher }:;for every $1\leq f\leq m$ ,output actions {outputs from process to philosopher }:$talking_{i}$ , $thinking_{i;}$
$i$

$i$

$P_{i}$$exit_{i}$$try_{\dot{|}}(f)$

$i$

**

$P_{i}$

thinking region **01: $try_{i}(f)$ :09: transit(i) $:=1$ ;03: if door $=close$ then begin
checkdw(i) $:=1$ ;06:;
waitfor door
05:
checkdw(i) $:=0$ end;
06:
07: ticket(i) $:=1+maxj\neq:tiiket(j)$ ;08: forum(i) $:=f$ ;09: transit(i) $:=0$ ;do begin
10: for each j$j)=0$ or checkdw(j) $=1$ or f $=forum(chair)$ ;11:$=0$ or (ticket(i), f, i) $<(ticket(j), f\sigma rum(j),j)$12
chair end;
, icket(j) $=0$ or (ticket(i), f, i) (ticket(j), f orum(j) i)
13: if for each jthen chair $:=i$ ;14: $talking_{i}$ ;$=\mathrm{o}\mathrm{p}\mathrm{e}n$$\neq i$$\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}\mathrm{f}\mathrm{o}\mathrm{r}ticket(j\{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}\mathrm{f}\mathrm{o}\mathrm{r}transit\mathrm{o}\mathrm{r}f=forum$$:$$\neq i$

**

15:
16:
17:

$t$

$<$

talking region **exit:;

23:
24:

if chair $=i$ then begin
door $:=dose$ ;for each $j\neq i$ do begin
waitfor transit(j) $=0$ or checkdw(j) $=1$ ;waitfor $f\neq forum(j)$ or ticket(j) $=0$ end;
chair: $=0$ ;door $:=open$ ;for each $i\neq i$ do
waitfor checkdw(j) $=0$ end;

$25:26$$ticket(\grave{i}.\cdot=.0fo\mathrm{r}umi)\cdot=0_{}$

18:
19:
20:

21:
22:

:
27:

thinkings

Relation $(a, b, c)<(a’, b’, d)$ in the procedure is lexicographical order. The processwith the smallest triple of nonzero ticket number, forum, and its identifier is chosen as
in a forum is not
the chair of the forum held in the meeting room. If a philosopher
ticket(i)byand forum(i).
resettingregiontalking
can smoothly leave thethe chair,must close the door of the
However, when the chair wishes to leave the forum,to leave. After the chairsame
philosophers
in
the
forum
waiting
for
all
and
be
doorway
resigns the chair and opens
observes that all philosophers in the forum have left,
the door in the doorway. Then after confirming that all philosophers waiting at line 05$P_{i}$$P_{i}$$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$61have noticed that the door has opened, the philosopher who resigned the chair leaves theforum. The proof of the next theorem is omitted here due to the page limit.

Theorem 1In any execution by $(n, m)$ -HCGME, shared variable chair is never concurrently written, and once chair is set to be $i(1\leq i\leq n)$ , the contents of chair remains
until it is reset to be 0by process at line 21 of the program. In any execution by$(n, m)$ -HCGME, shared variable door is also never concurrently written.
$i$

$i$

Theorem 2 (n,$m)$ -HCGME guarantees group mutual exclusion, lockout freedom, andprogress for the exit region.

Proof. The current chair is uniquely determined by chair. While aphilosopher is the chair,

only philosophers wishing to attend the same forum as the chair’s forum are allowed tocloses door in the exit
enter the forum. When the chair wishes to leave the forum,
region to prevent anewcomer to the trying region from getting aticket. After observing
that all other philosophers in the forum have left, the chair philosopher resigns the chairand opens door. Hence, group mutual exclusion is guaranteed. The time from whenenters the talking region is bounded byphilosopher enters the trying region until$2tc+O(nt)l$ , where $t= \min\{n, m\}$ , is an upper bound on the time that any philosopher
spends in the talking region, and is an upper bound on the time between two successive
atomic steps by aprocess. Hence, lockout freedom is guaranteed. Progress for the exit
region is obvious.
We can reduce the waiting time for processes wishing to attend the forum of the chairby modifying $(n, m)$ -HCGME. For this purpose, we extend the domain of shared variable
door to {close, 0, 1, ..., $m$ }. If the forum held by the chair is stored into door, then at theforum of interest
beginning of the trying region each philosopher checks whether
wishesis the same as the forum indicated in door. If aphilosopher notices thatticketto attend the same forum as the forum shown in door, the philosopher sets
as forum number to be the same as the ticket number and forum number
number asof the chair, and thenis granted attendance to the forum. In this way, such
philosophers can attend the forum inatomic steps after the entrance to the trying
region. This technique is called smooth admission.
$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$$\mathrm{a}$$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$

$c$

$l$

$\square$$\mathrm{h}\mathrm{i}\mathrm{s}/\mathrm{h}\mathrm{e}\mathrm{r}$$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$$\mathrm{h}\mathrm{i}\mathrm{s}/\mathrm{h}\mathrm{e}\mathrm{r}$$\mathrm{w}\mathrm{e}\mathrm{u}$$\mathrm{h}\mathrm{e}/\mathrm{s}\mathrm{h}\mathrm{e}$$\mathrm{O}(1)$4Concluding Remarks

The algorithm given in this paper, $(n,m)- HCGME$ , uses single-writer shared variables
together with two multi-writer shared variables that are never concurrently written. The
concurrency performance of our algorithm is superior to the algorithms in $[4, 8]$ . The ticket
domain of our algorithm is unbounded as in the Bakery algorithm. At present we do notknow whether we can modify our algorithm using similar techniques given in [1, 5, 13] sothat the ticket domain is bounded. This problem is worthy of further investigation.

References[1] U. Abraham, “Bakery algorithms”, Technical Report, Dept. of Mathematics, Ben
Gurion University, Beer-Sheva, Israel, 2001

62[2] H. Attiya and J. Welch, “Distributed Computing: Fundamentals, Simulations andAdvanced Topics” , McGraw-Hill, New York, 1998.

[3] M. J. Fischer, N. A. Lynch, J. E. Burns, and A. Borodi, “Resource allocation withimmunity to limited process failur\"e, 20th Annual Symposium on Foundations ofComputer Science, San Juan, Puerto Rico: 234-254, 1979.
[4] V. Hadzilacos, “A note on group mutual exclusion”, Proceedings of 12th Annual
ACM Symposium on Principles of Distributed Computing, Newport, Rhode Island,

pp.100-106, 2001.

[5] P. Jayanti, K. Tan, G. Friedland, and A. Katz, ”Bounded Lamport’s bakery algorithm”, Proceedings of SOFSEM’2001, Lecture Notes in Computer Science, vo1.2234,
Springer-Verlag, Berlin, pp.261-270, 2001.
[6] Yuh-Jzer Joung, “Asynchronous group mutual exclusion”, Distributed Computing,vo1.13, pp.189-206, 2000.
[7] Yuh-Jzer Joung, “The congenial talking philosophers problem in computer networks”,
Distributed Computing, vo1.15, pp.155-175, 2002.
[8] P. Keane and M. Moir, ”A simple local-spin group mutual exclusion algorithm”, IEEE
Rmsactions on Parallel and Distributed Systems, vo1.12,2001.

[9] L. Lamport, “A new solution of Dijkstra’s concurrent programming problem”, Communjcations of the ACM, vo1.17, pp.453-455, 1974.

[10] L. Lamport, “The mutual exclusion problem. Part II:Statement and solutions”, J.
of the ACM, vol. 33, pp.327-348, 1986.
[11] N. A. Lynch, “Distributed Algorithms”, Morgan Kaufmann, San Francisco, California, 1996.

[12] M. Omori, K. Obokata, K. Motegi and Y. Igarashi, “Analysis of some lockout avoidance algorithms for -exclusion problem”, Interdisciplinary Information Sciences,
vo1.8, pp. 187-198, 2002.
$k$[13] M. Takamura and Y. Igarashi, “Simple mutual exclusion algorithms based on boundedtickets on the asynchronous shared memory model” , IEICE Transactions on Infomation and Systems, v0l.E86 D, pp.246-254, 2003.

[14] K. Vidyasankar, “A highly concurrent group mutual -exclusion algorithm”, Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing,Monterey, California, p.130, 2002.
$l$[15] K. Vidyasankar, “A simple group mutual -exclusion algorithm”, to appear in Information Processing Letters$l$