Lukas' Notes

Mutual Exclusion

2 min read

operating-systems concurrency

Definition

Mutual Exclusion

Mutual exclusion (Mutex) is a fundamental property in concurrent programming that ensures that only one process or thread can access a shared resource or execute its critical section at any given time.

Mutual exclusion is required to prevent race conditions and maintain data consistency. It is considered an orthogonal concept to condition synchronisation.

Implementation Requirements

Any mechanism used to enforce mutual exclusion must satisfy:

  • Progress: No deadlock in selecting the next process to enter the section.
  • Bounded Waiting: No starvation of processes waiting to enter.

OS Mechanisms

Modern operating systems provide several tools to implement mutual exclusion:

  • Semaphores: Counters used for locking.
  • Monitors: High-level synchronisation constructs.
  • Message Passing: Ensuring exclusion by ownership transfer.

Prioritised Mutual Exclusion

In some systems, certain types of processes must be given priority when competing for a critical section.

Example:

Consider processes of type A and type B competing for a resource, where A processes have priority over B processes.

Basic Priority (Semaphore Wrapper)

A simple solution uses an additional semaphore x to restrict the entry of B processes. While any number of A processes can wait directly on the resource semaphore s, at most one B process can wait on s at a time; others block on x.

var s: semaphore := 1; // Resource mutex
var x: semaphore := 1; // Priority control for B
 
// Process A
wait(s);
// --- Critical Section ---
signal(s);
 
// Process B
wait(x);
    wait(s);
    // --- Critical Section ---
    signal(s);
signal(x);

Strict Priority (Reader-Writer Style)

Using a counter for A processes, the first A process to arrive can block all B processes, and the last A process to leave releases them. This ensures that no B process enters if an A process is waiting (see Writer Priority logic).

Graph View

Backlinks