Mutexes vs. Spinlocks: Ensuring Mutual Exclusion

1. From Busy-Waiting to Blocking: The Mutex Lock

The primary drawback of the Test-and-Set loop we studied is busy-waiting. A process stuck in that loop is "spinning"—using its entire CPU time slice to repeatedly check a lock. This is wasteful. If a process can't proceed, it would be far more efficient to take it off the CPU and let another process run.

This is the core idea behind the mutex lock. The name "mutex" is short for mutual exclusion. Like a spinlock, it ensures only one thread can be in a critical section at a time. However, its approach to waiting is different.

Instead of spinning, a thread that tries to acquire a locked mutex is put into a sleeping or blocked state by the operating system. It yields the CPU and is placed in a queue of threads waiting for that specific lock.

Let's watch a short video that introduces this concept.

The Atomicity Requirement

As we've learned, implementing locks is tricky. If we design a mutex with simple, separate instructions for checking the lock and acquiring it, we will face the exact same race condition that plagued our initial software lock attempts.

To illustrate this, let's see what happens when the acquire operation is not atomic.

This failure shows that the core operations of a mutex—acquire() and release()—must themselves be atomic. Modern operating systems implement these operations using the very hardware instructions we discussed in the last lesson, like Test-and-Set or Compare-and-Swap.

A typical implementation of a mutex lock looks like this:

• acquire(): The thread calls acquire(). The OS uses an atomic instruction to check if the lock is free.
  • If free: The OS grants the lock to the thread, and it proceeds into the critical section.
  • If busy: The OS adds the thread to a waiting queue associated with the lock, changes the thread's state to Blocked, and calls the scheduler to run a different thread.
• release(): The thread finishes its critical section and calls release().
  • The OS checks the waiting queue. If it's empty, it simply marks the lock as free.
  • If the queue is not empty, the OS picks a thread from the queue (often in FIFO order), moves it to the Ready state, and marks the lock as held by this newly awakened thread.

The key takeaway is that a mutex avoids wasting CPU cycles by putting waiting threads to sleep. However, this comes at the cost of two context switches: one to put the thread to sleep and another to wake it up later.

2. The Spinlock: A Formal Look at Busy-Waiting

What we previously called "busy-waiting" is the defining feature of a spinlock. It's a lock where a waiting thread repeatedly checks the lock status in a tight loop until it becomes available.

As the previous video mentioned, this mechanism has a name.

A spinlock is implemented exactly as we saw in the previous lesson:

// Shared variable
boolean lock = false;

// Entry section
while (TestAndSet(&lock) == true) {
    // do nothing, just spin
}

// ... Critical Section ...

// Exit Section
lock = false;

The thread does not yield the CPU; it actively spins, consuming processor time.

3. Mutex vs. Spinlock: The Big Trade-Off

Now we have two tools for mutual exclusion. Which one is better? The answer, crucial for GATE questions, is: it depends on the situation.

The core trade-off is between:

• Mutex Overhead: The cost of two context switches (blocking and waking up).
• Spinlock Overhead: The cost of the CPU time wasted while spinning.

This leads to a simple but powerful rule of thumb:

• If the critical section is long (e.g., involves I/O), the time spent holding the lock will likely be much longer than the cost of a context switch. A mutex is better because it frees up the CPU for other tasks.
• If the critical section is very short (e.g., just incrementing a counter), the time spent spinning might be less than the overhead of two context switches. A spinlock can be more efficient.

The following video provides an excellent practical analogy to help you visualize this trade-off.

Deeper Comparison

Let's solidify this comparison by examining a detailed breakdown. The following article provides a concise summary, culminating in a useful comparison table.

Here is a visual summary of these key differences:

System Architecture Matters: Single-Core vs. Multi-Core

The effectiveness of a spinlock is highly dependent on the system's architecture.

• On a single-core system: A spinlock is generally a bad idea. If thread A holds a lock and is preempted, thread B might get scheduled and start spinning. Since there's only one core, thread A cannot run to release the lock. Thread B will spin uselessly for its entire time slice, accomplishing nothing. This is the priority inversion problem we discussed in the last lesson, but it applies even without explicit priorities.
• On a multi-core system: Spinlocks can be very effective. Thread B can spin on one core while Thread A makes progress on another core. If the critical section is short, Thread A will release the lock quickly, and Thread B can acquire it without the overhead of a context switch.

Conclusion

In this lesson, we formalized and compared two fundamental synchronization primitives. Understanding their trade-offs is essential for analyzing the performance of concurrent systems.

Key Takeaways:

• Mutex Lock: A waiting thread is put to sleep (blocked) by the OS and placed in a queue. It does not consume CPU while waiting. This involves context switch overhead. Best for longer critical sections or when I/O is involved.
• Spinlock: A waiting thread busy-waits in a loop, consuming CPU cycles. This avoids context switch overhead. Best for very short critical sections on multi-core systems.
• The Choice is a Trade-Off: The decision between a mutex and a spinlock hinges on comparing the cost of wasted CPU cycles (spinning) against the cost of two context switches (blocking/waking).

We have focused on using locks for mutual exclusion—ensuring only one thread does something at a time. However, synchronization problems are often more complex. For example, in the Producer-Consumer problem, a producer needs to wait if the buffer is full, and a consumer needs to wait if it's empty. A simple lock isn't expressive enough to manage these conditions.

In our next lesson, we will introduce semaphores, a more generalized and powerful synchronization tool that can handle not just mutual exclusion but also these more complex coordination scenarios.