mutualexclusion

Mutual exclusion is a property of concurrent systems that prevents more than one process or thread from executing in a critical section simultaneously. It is used to protect shared data from concurrent modification, which can lead to data races, corruption, or inconsistency.

A critical section is a portion of code that accesses shared resources. The mutual-exclusion problem (often called the critical-section problem) asks how to design a mechanism that guarantees that at most one entrant is inside the critical section at any time, while allowing progress and avoiding indefinite postponement. The standard requirements are mutual exclusion, progress (no deadlock), and bounded waiting (a limit on how many times others can enter before a waiting process enters).

Implementation approaches include hardware synchronization primitives such as test-and-set, exchange, compare-and-swap, and load-linked/store-conditional, which can form spinlocks. Software algorithms for small numbers of processes include Dekker's algorithm and Peterson's algorithm. For general usage, operating systems and languages provide mutexes, semaphores, and monitors. Higher-level techniques include bakery algorithms and ticket locks to improve fairness.

Problems related to mutual exclusion include deadlock, starvation, and priority inversion. Solutions include using fair locks, priority inheritance protocols, and careful ordering of lock acquisition. In practice, mutual exclusion is a building block for many synchronization mechanisms; it does not by itself handle ordering of multiple readers or writers and must be complemented by other coordination strategies when appropriate.

In modern systems, mutual exclusion is implemented by language runtimes and OS kernels, and exposed through APIs such as mutexes, critical sections, and synchronized blocks. While essential for correctness, mutex use involves trade-offs between simplicity, performance, and fairness.