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

摘要

Let n be the number of threads that can compete for a shared resource R. The mutual exclusion problem involves coordinating these n concurrent threads in accessing R 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 5n 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 3n shared bits and the latter algorithms using An shared bits. The resulting algorithms are simple, space-efficient, and highly fair.