Mutual Exclusion

Definition

Mutual Exclusion (Mutex) is a synchronization principle that ensures only one process/thread can access a shared resource at a time. It prevents race conditions by serializing access to critical sections. Think of it like a single bathroom that only one person can use at a time - others must wait outside.

Need for Mutual Exclusion

The Problem Without Mutual Exclusion

Shared Variable: balance = 1000

Thread 1:                    Thread 2:
read(1000)                   read(1000)
add 100                      subtract 500
write(1100)                  write(500)

Expected: Could be 1100 or 500
Actual: Depends on timing - could be wrong value

The Solution: Mutual Exclusion

Thread 1:
LOCK
read(1000)
add 100
write(1100)
UNLOCK

Thread 2: (waits for lock)
LOCK (now acquired)
read(1100)
subtract 500
write(600)
UNLOCK

Requirements for Mutual Exclusion

Any solution must satisfy three conditions:

1. Safety (Mutual Exclusion)

At most one process in critical section at a time

Time:   0   1   2   3   4   5   6
Thread1:[CS]
Thread2:     [waiting] [CS]
Thread3:              [waiting] [waiting] [CS]

✓ Only one in CS at any time

2. Liveness (No Deadlock/Starvation)

If no process in critical section, waiting process eventually enters

If process wants CS and no one using it
 → It should enter eventually (not wait forever)

If multiple processes waiting
 → All should eventually get turn (no starvation)

3. Fairness (Bounded Waiting)

No process waits infinitely for critical section

If process requests CS, it enters within N requests from other processes
(N = reasonable bound, prevents starvation)

Mutual Exclusion Solutions

Solution 1: Software-Based Locks

Algorithm 1: Disable Interrupts

acquire_lock() {
    disable interrupts;  // Prevent context switching
}

release_lock() {
    enable interrupts;   // Allow context switching
}

Pros:

  • Simple
  • Guaranteed mutual exclusion

Cons:

  • Only works on single CPU
  • Disables interrupts = responsive devices can’t interrupt
  • Unprivileged processes can’t call this
  • System hangs if lock never released

Algorithm 2: Test and Set Lock

Hardware-provided atomic operation: test_and_set()

// Hardware atomic instruction
bool test_and_set(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

// Using it:
acquire_lock() {
    while (test_and_set(&lock)) {
        // Spin if lock taken
    }
}

release_lock() {
    lock = false;
}

Pros:

  • Works on multi-CPU
  • Hardware guarantees atomicity

Cons:

  • Busy waiting (spinning) wastes CPU
  • Unpredictable waiting time
  • Starvation possible if one process keeps spinning

Algorithm 3: Dekker’s Algorithm

First software solution providing all three properties

Uses shared variables and software logic (no hardware support needed)

Complex but proven correct

Algorithm 4: Peterson’s Algorithm

Simpler than Dekker’s, also correct

int interested[2] = {0, 0};
int turn = 0;

// Process 0:
interested[0] = 1;
turn = 1;
while (interested[1] && turn == 1) {
    // Spin (wait for Process 1 to finish)
}
// Critical Section
interested[0] = 0;

// Process 1: Similar with indices swapped

Properties:

  • ✓ Mutual Exclusion
  • ✓ Progress (no deadlock)
  • ✓ Bounded Waiting (fairness)

Limitation: Only works for 2 processes

Solution 2: Hardware Support

Atomic Instructions

CPU provides instructions that execute atomically (can’t be interrupted):

  1. Test-and-Set (TAS)

    Atomic operation: Read value, set to 1, return old value

  2. Compare-and-Swap (CAS)

    If memory == expected, set to new value
Atomic and returns success/failure

  3. Load-Linked and Store-Conditional (LL/SC)

    Read value (with watch)
If watched value changed, store fails

Spin Lock

Using hardware atomic operation:

void acquire() {
    while (test_and_set(&lock))
        ;  // Spin
}

void release() {
    lock = 0;
}

Problem: Spinning wastes CPU cycles!

Solution 3: OS-Level Primitives

Mutex Lock

lock.acquire();  // May sleep if unavailable
// Critical Section
lock.release();  // Wakes up waiting process

Much better than spinning!

Semaphore

Will be covered in detail in separate topic.

Spinlock vs Sleep Lock

Spinlock (Busy Waiting)

acquire() {
    while (!available) {
        // CPU spinning, doing nothing useful
    }
}

Good for:

  • Very short critical sections
  • Multi-CPU systems (other CPU doing useful work)

Bad for:

  • Long critical sections (wasted CPU)
  • Single CPU (other process can’t run while spinning)

Sleep Lock (Blocking)

acquire() {
    if (not available) {
        // Process sleeps, CPU runs other processes
        sleep();
    }
}

Good for:

  • Long critical sections
  • Single CPU
  • Many processes competing

Bad for:

  • Very short critical sections (overhead of sleep/wake)

Practical Mutual Exclusion

In C/Unix (POSIX Threads)

#include <pthread.h>

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);
// Critical section
count = count + 1;
pthread_mutex_unlock(&lock);

In Java

// Method-level synchronization
synchronized void increment() {
    count = count + 1;
}

// Block-level synchronization
synchronized (lock) {
    count = count + 1;
}

In C#

lock (lockObject) {
    count = count + 1;
}

Common Mistakes with Mutual Exclusion

1. Forgetting to Release Lock

acquire_lock();
critical_section();
// Forgot release_lock() - DEADLOCK!

2. Deadlock from Circular Wait

Thread 1: acquire(lockA), acquire(lockB)
Thread 2: acquire(lockB), acquire(lockA)

If Thread 1 has lockA and waits for lockB
And Thread 2 has lockB and waits for lockA
→ Deadlock!

3. Not Using Lock for All Access

if (count > 10) {  // Not protected!
    // Race condition here
}

lock.acquire();
count = count + 1;
lock.release();

4. Protecting Too Much (Low Concurrency)

lock.acquire();
slow_io_operation();  // Why hold lock during I/O?
count = count + 1;
lock.release();

Performance Implications

Mutex Overhead

  1. Time: Lock/unlock operations take time
  2. Complexity: Code becomes harder to understand
  3. Concurrency: Reduced parallelism (only one in CS)

Optimization Trade-offs

  • Fine-grained locking: High concurrency but complex, deadlock risk
  • Coarse-grained locking: Simple but low concurrency

Mutex in Multi-Core Systems

On Single Core

Mutual exclusion prevents one thread from interleaving with another.

On Multi-Core

Mutual exclusion prevents simultaneous execution on different cores.

Core 1: [CS] [CS] [CS]
Core 2: [waiting] [CS] [CS]

Mutual exclusion more critical here because threads truly run in parallel!

Summary

Mutual exclusion ensures only one process accesses shared resource, preventing race conditions. Solutions range from software (Peterson’s Algorithm) to hardware (atomic instructions) to OS-level (mutex locks). Modern systems use OS-level mutexes as they provide good performance and prevent busy-waiting. Proper use of mutual exclusion is essential for correct multi-threaded programs. Key challenge: Balancing correctness with performance and simplicity.