Mutual Exclusion

operating-systems concurrency

Definition

Mutual Exclusion

Mutual exclusion is the property that at most one process or thread can execute its critical section or access a shared resource at any given time.

Mutual exclusion prevents race conditions and ensures data consistency. It is orthogonal to condition synchronisation, which concerns ordering of events rather than exclusivity.

Requirements

Any correct mutual exclusion mechanism must satisfy:

Mutual Exclusion

At most one process executes in its critical section at any time.

Progress

If no process is in its critical section and some processes wish to enter, the selection of the next process to enter cannot be postponed indefinitely.

Bounded Waiting

A process waiting to enter its critical section will do so within a bounded number of turns (no starvation).

Mechanisms

Modern operating systems provide several primitives:

Mechanism	Description
Mutex	Low-level lock with ownership semantics
Semaphore	Counter-based signalling primitive
Monitor	High-level construct with condition variables
Message Passing	Exclusion via ownership transfer

Priority Schemes

Basic Priority via Semaphore Wrapper

Processes of type $A$ have priority over type $B$. An additional semaphore $x$ restricts $B$ entry: while multiple $A$ processes may wait on resource semaphore $s$, at most one $B$ process waits on $s$; others block on $x$.

Semaphore s = 1      // resource lock
Semaphore x = 1      // priority control for B

Void processA()
    s.wait()
    /* --- Critical Section --- */
    s.signal()

Void processB()
    x.wait()
        s.wait()
        /* --- Critical Section --- */
        s.signal()
    x.signal()

Strict Priority via Counter

A counter tracks waiting $A$ processes. The first $A$ to arrive blocks all $B$ processes; the last $A$ to leave releases them. No $B$ enters if any $A$ is waiting. This mirrors writer-priority reader-writer logic.