Simple, space-efficient, and fairness improved FCFS mutual exclusion algorithms

• This paper proposes three new FCFS mutual exclusion algorithms.
• This paper proposes three simple FCFS mutual exclusion algorithms.
• This paper proposes a space optimal FCFS mutual exclusion algorithm.
• This paper proposes the first FCFS mutual exclusion algorithm using safe bits to assure a stronger fairness.

Let nn be the number of threads that can compete for a shared resource RR. The mutual exclusion problem involves coordinating these nn concurrent threads in accessing RR in a mutually exclusive way. This paper addresses two basic questions related to the First-Come-First-Served (FCFS) mutual exclusion algorithms that use only read–write operations: one is regarding the lower bound on the shared space requirement and the other is about fairness.The current best FCFS algorithm using read–write operations requires 5n5n shared bits. Could the shared space requirement be further reduced?The existing FCFS mutual exclusion algorithms assure fairness only among the threads which cross the ‘doorway’ sequentially. In systems with multicore processors, which are becoming increasingly common nowadays, threads can progress truly in parallel. Therefore, it is quite likely that several threads can cross the doorway concurrently. In such systems, the threads which cross the doorway sequentially may constitute only a fraction of all competing threads. While this fraction of threads follow the FCFS order, the rest of the threads have to rely on a biased scheme which always favors threads with smaller identifiers. Is there a simpler way to remove this bias to assure global fairness?This paper answers the above two questions affirmatively by presenting simple FCFS mutual exclusion algorithms using only read–write operations—the first one using 3n3n shared bits and the latter algorithms using 4n4n shared bits. The resulting algorithms are simple, space-efficient, and highly fair.