Mutual exclusion is used to coordinate access to shared resources by concurrent processes. k-Exclusion is a variant of mutual exclusion in which up to k processes can simultaneously access the shared resource. We present the first known shared-memory k-exclusion algorithms that use only atomic reads and writes, have bounded remote memory reference (RMR) complexity, and tolerate crash failures. Our algorithms have RMR complexity O(N) in both the cache-coherent and distributed shared-memory models, where N is the number of processes in the system. Additionally, we present a k-exclusion algorithm that satisfies the First-In-First-Enabled (FIFE) fairness property. FIFE requires that processes become "enabled" to enter the CS roughly in the order that they request access to the shared resource. Finally, we present a modification to the FIFE k-exclusion algorithm that works with non-atomic reads and writes. The high-level structure of all our algorithms is inspired by Lamport's famous Bakery algorithm.

We consider the worst-case remote memory reference (RMR) complexity of first-come-first-served (FCFS) mutual exclusion (ME) algorithms for N asynchronous reliable processes that communicate only by reading and writing shared memory. We exhibit an upper bound of O(log N) RMRs for FCFS ME, which is tight, improves on prior results, and matches a lower bound for ME (with or without FCFS).