Group Mutual Exclusion (GME) problem, introduced by Joung, is a natural generalization of the classical mutual exclusion problem. In GME, when a process leaves the REMAINDER SECTION, it request a "session". Processes can enter the CRITICAL SECTION simultaneously if they have requested the same session. In this thesis, we present algorithms for the GME problem that satisfies the properties of Mutual Exclusion, Starvation Freedom, Bounded Exit, Concur- rent Entry and First-Come-First-Served. Our algorithms have O(N) Shared Space Complexity and O( N) RMR (Remote Memory Reference) Complexity. 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.;When all shared variables are required to be of bounded size, Hadzilacos presented an algorithm, whose shared space is theta(N 2) and whose RMR complexity was claimed to be O( N). Jayanti et al. presented a space efficient adaptation of the above algorithm that uses only theta(N) space and inherited the claim that the RMR complexity is of O(N). We show that both of these algorithms are of RMR complexity of O( N2) and thus demonstrate that the claim of Hadzilacos is erroneous. We then present our second algorithm for the GME problem satisfying all five properties while using only bounded shared variables and only simple read and write instructions. The algorithm is inspired by Taubenfeld's Black-White Bakery Algorithm, which is an elegant algorithm that bounds Lamport's Bakery Algorithm for the classical mutual exclusion problem. To the best of our knowledge, our algorithm is the first such algorithm.
展开▼
