Group mutual exclusion by fetch-and-increment

Alex A. Aravind*, W H Hesselink

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

The group mutual exclusion (GME) problem (also called the room synchronization problem) arises in various practical applications that require concurrent data sharing. Group mutual exclusion aims to achieve exclusive access to a shared resource (a shared room) while facilitating concurrency among non-conflicting requests. The problem is that threads with distinct interests are not allowed to access the shared resource concurrently, but multiple threads with same interest can. In Blelloch et al. (2003), the authors presented a simple solution to the room synchronization problem using fetch&add (F&A) and test-and-set (T&S) atomic operations. This algorithm has O(m) remote memory references (RMRs) in the cache coherent (CC) model, where m is the number of forums. In Bhatt and Huang (2010), an open problem was posed: "Is it possible to design a GME algorithm with constant RMR for the CC model using fetch&addinstructions?" This question is partially answered in this article by presenting a group mutual exclusion algorithm using fetch-and-increment instructions. The algorithm is simple and scalable.
Original languageEnglish
Article number14
Number of pages29
JournalACM Transactions on Parallel Computing
Volume5
Issue number4
DOIs
Publication statusPublished - Feb-2019

Keywords

  • Concurrency
  • algorithms
  • group mutual exclusion
  • constant remote memory access
  • fetch-and-increment
  • concurrent date structure
  • synchronization

Cite this