We present two algorithms for the Group Mutual Exclusion (GME) Problem that satisfy the properties of Mutual Exclusion, Starvation Freedom, Bounded Exit, Concurrent Entry and First Come First Served. Both our algorithms use only simple read and write instructions, have O(N) Shared Space complexity and O(N) Remote Memory Reference (RMR) complexity in the Cache Coherency (CC) model. Our first algorithm is developed by generalizing the well-known Lamport's Bakery Algorithm for the classical mutual exclusion problem, while preserving its simplicity and elegance. However, it uses unbounded shared registers. Our second algorithm uses only bounded registers and is developed by generalizing Taubenfeld's Black and White Bakery Algorithm to solve the classical mutual exclusion problem using only bounded shared registers. We show that contrary to common perception our algorithms are the first to achieve these properties with these combination of complexities.
Takamura and Igarashi also made an attempt in @cite_9 to generalize Lamport’s Bakery Algorithm to solve the GME problem. They presented three different algorithms in that paper. However, all of their algorithms satisfy neither the concurrent entry property nor the FCFS property.
@cite_9
1834123542
In the group mutual exclusion problem [6], which generalizes mutual exclusion [2], a process chooses a session when it requests entry to the Critical Section. A group mutual exclusion algorithm must ensure that the mutual exclusion property holds: If two processes are in the Critical Section at the same time, then they request the same session. In addition to mutual exclusion, lockout freedom, bounded exit and concurrent entering are basic properties that are desirable in any group mutual exclusion algorithm.Hadzilacos in [4] first introduced a fairness condition, called first-come-first-served (FCFS), for group mutual exclusion. The only known FCFS group mutual exclusion algorithm is due to Hadzilacos [4], and requires Θ(N2) bounded shared registers, where N is the number of processes. We present a FCFS group mutual exclusion algorithm that uses only Θ(N) bounded shared registers. (The existence of such an algorithm was posed as an open problem by Hadzilacos.)Next, we demonstrate that the FCFS property does not fully capture our intuitive notion of fairness. We therefore propose an additional fairness property, called first-in-first-enabled (FIFE). Finally, we present a reduction that transforms any "abortable" FCFS mutual exclusion algorithm M into a group mutual exclusion algorithm G. Thus, different group mutual exclusion algorithms can be obtained by instantiating M with different abortable FCFS mutual exclusion algorithms. The group mutual exclusion algorithms so obtained satisfy all of the properties mentioned above: mutual exclusion, lockout freedom, bounded exit, concurrent entering, FCFS, and FIFE. Lamport's Bakery algorithm is among the best known mutual exclusion algorithms. A drawback of Lamport's algorithm is that it requires unbounded registers for communication among processes. By making a small modification to Lamport's algorithm, we remove the need for unbounded registers. The main appeal of our algorithm lies in the fact that it overcomes a drawback of a famous algorithm while preserving its elegance. 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 different groups. It is also called the congenial talking philosophers problem. In this paper we propose three algorithms based on ticket orders for the group mutual exclusion problem in the asynchronous shared memory model. The first algorithm is a simple modification of the Bakery algorithm. It satisfies group mutual exclusion, but does not satisfy lockout freedom. The second and the third algorithms are further modifications from the first one in order to satisfy lockout freedom and to improve the concurrency performance. They use single-writer shared variables, together with two multi-writer shared variables that are never concurrently written. The third algorithm has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader, a process wishing to join the same group as the leader's group can be granted use of the resource in constant time. Group mutual exclusion is a natural problem, formulated by Joung in 1998, that generalises the classical mutual exclusion problem. In group mutual exclusion a process requests a “session” before entering its critical section; processes are allowed to be in the critical section simultaneously provided they have requested the same session. To rule out solutions that cause processes to delay each other even when they all request the same session, group mutual exclusion algorithms must satisfy a property called “concurrent entering”. Joung stated this property only informally. Keane and Moir later gave a precise statement of this property and devised a simple group mutual exclusion algorithm that satisfies it. We argue that Keane and Moir's formulation is not quite as strong as the property Joung described informally. We propose a new precise and simple formulation of concurrent entering that is stronger than Keane and Moir's and properly captures Joung's intention. Keane and Moir's algorithm does not satisfy this stronger property, while Joung's original algorithm does. We present another algorithm that satisfies this stronger property and has some advantages over Joung's.