Spinlocks, Mutexes, and Semaphores: A Comparison

1. Spinlocks: The High-Speed, Busy-Waiting Lock

The first, and simplest, type of lock we'll examine is the spinlock. Its name perfectly describes its behavior: if a thread of execution tries to acquire a spinlock that is already held, it will spin in a tight loop, repeatedly checking the lock's status until it is released. This is also known as "busy-waiting" because the CPU is kept busy doing no productive work.

Key Characteristics of Spinlocks:

• Behavior on Contention: Busy-waits (spins), consuming CPU cycles. It does not yield the CPU.
• Allowed Context: Can be used in any context, including atomic contexts like interrupt handlers, softirqs, and tasklets. Because it doesn't sleep, it's the only option available in these contexts.
• Appropriate Usage: Ideal for protecting critical sections that are very small and where the lock is held for an extremely short time. The overhead of sleeping and waking a task is much higher than a few cycles of spinning.
• The Golden Rule: You must not attempt to sleep while holding a spinlock. If you do, you risk a deadlock. On a single-core system, the task holding the lock would go to sleep, but the spinning code trying to acquire it would monopolize the CPU, preventing the sleeping task from ever being scheduled to release the lock. In an SMP system, this is less of a direct deadlock but is still a severe bug.

As the slides mention, a common pattern is using spin_lock_irqsave(). This is crucial when protecting data shared between process context and an interrupt handler. It atomically acquires the spinlock and disables interrupts on the local CPU. This prevents the interrupt handler from preempting the code holding the lock, which would cause an immediate deadlock.

2. Sleeping Locks: Mutexes and Semaphores

In contrast to spinlocks, the kernel provides a category of locks called "sleeping locks." When a task tries to acquire a contended sleeping lock, instead of wasting CPU time spinning, the kernel puts the task to sleep and adds it to a wait queue for that lock. The scheduler is then free to run a different task. When the lock is released, a waiting task is woken up to acquire it.

This is a fundamental distinction. The official kernel documentation categorizes locks based on this behavior.

The two main types of sleeping locks are mutexes and semaphores.

Mutexes: The Strict and Simple Sleeping Lock

A mutex (short for MUTual EXclusion) is the most common and recommended sleeping lock in the kernel. It is conceptually simple and has a strict set of rules that help catch programming errors.

Key Characteristics of Mutexes:

• Behavior on Contention: The task sleeps, yielding the CPU.
• Allowed Context: Can only be used in process context (or more generally, in a context that is allowed to sleep). It is illegal to use a mutex in an interrupt handler or other atomic context.
• Appropriate Usage: The default choice for locking in process context, especially when the critical section is long or may involve operations that could sleep (e.g., memory allocation with kmalloc, or data transfer with copy_from_user).
• Strict Rules:
  • It is a binary lock; it can only be held by one task at a time.
  • It has strict ownership: the same task that acquires the mutex must be the one to release it.
  • They are not recursive; a task cannot re-acquire a mutex it already holds.

Semaphores: The Flexible, Counting Lock

Semaphores are the original sleeping lock in Linux. They are more flexible than mutexes but are now recommended only for specific scenarios where the strictness of a mutex is too limiting.

Key Characteristics of Semaphores:

• Behavior on Contention: The task sleeps, yielding the CPU.
• Allowed Context: Like mutexes, they can only be used in a context that is allowed to sleep.
• Appropriate Usage:
  • Counting Semaphores: Used to manage access to a finite pool of resources. For example, if you have 4 identical hardware processing units, you can initialize a semaphore to 4. Each of the first four tasks to request a unit will succeed; the fifth will sleep until one is released.
  • Binary Semaphores: Can be used for simple mutual exclusion, but the key difference from a mutex is the lack of strict ownership.
• Flexible Rules:
  • Can be a counting lock, allowing up to 'n' holders simultaneously. A mutex is a special case where n=1.
  • They do not have strict ownership. One task can perform the "acquire" operation (down()) and a completely different task can perform the "release" operation (up()). This makes them suitable for more complex producer-consumer or signaling scenarios.

Due to their stricter rules, mutexes are now heavily preferred over binary semaphores for simple mutual exclusion. The strict ownership helps the kernel's lock validator (lockdep) find bugs more easily.

3. Comparison and Choosing the Right Lock

Now let's put it all together. The choice between these primitives is one of the most common decisions a kernel developer makes.

This diagram visually summarizes the relationship between the lock types. A mutex can be seen as a specialized, "sleepable" spinlock, and both have read-write variants (which we'll cover later).

The following summary table and the slide from the presentation provide a clear decision-making guide.

4. Interview Scenario: Choosing the Right Lock

An interviewer gives you the following scenario:

"I'm writing a driver for a GPS device. The device sends location updates over a serial port, which triggers an interrupt. The interrupt handler reads the data and places it into a shared buffer. A user-space application can then use the read() system call to get the latest location data from that buffer. I need to protect this shared buffer from concurrent access. Should I use a spinlock or a mutex, and why? Be specific about the exact functions you would use."

Your Thought Process:

1. Identify the Execution Contexts:

   • The write side is the interrupt handler (hard IRQ). This is an atomic context.
   • The read side is the file operation read(), which executes in process context on behalf of the user application. This context is preemptible and can sleep.

2. Evaluate the Primitives:

   • Mutex: Can I use a mutex? No. The interrupt handler cannot acquire a mutex because it cannot sleep. Using a mutex here would be a critical bug.
   • Spinlock: Can I use a spinlock? Yes. A spinlock does not sleep, so it is safe to use within an interrupt handler.

3. Refine the Solution:

   • Since the lock is shared between an interrupt context and a process context, a simple spin_lock() is insufficient.
   • If the process context code acquires the lock and is then interrupted by the GPS device, the interrupt handler will try to acquire the same lock and will spin forever, deadlocking the CPU.
   • Therefore, the process context code must disable local interrupts before acquiring the lock. The interrupt handler code can use a simple spinlock because it can't be preempted by itself.

Your Answer:

"You must use a spinlock. A mutex is not an option because one of the accessors is an interrupt handler, which is an atomic context where sleeping is illegal.

Specifically, the implementation should be:

• In the read() system call (process context), you must use spin_lock_irqsave() to acquire the lock and spin_unlock_irqrestore() to release it. spin_lock_irqsave() saves the current interrupt state, disables local interrupts, and then acquires the lock. This prevents the interrupt handler from preempting the critical section and causing a deadlock.
• In the interrupt handler itself, you can use the simpler spin_lock() and spin_unlock(). You don't need the _irq variants here because you are already in an interrupt context, and you are only protecting against concurrency with other CPUs or the process context."

Conclusion

You now have a solid framework for comparing the kernel's primary locking mechanisms. Understanding the fundamental trade-off between spinning and sleeping is the key to making the correct choice.

Key Takeaways:

• Spinlocks are for very short critical sections, especially when you need to lock from an atomic context (like an interrupt handler) where sleeping is forbidden. They busy-wait, consuming CPU.
• Mutexes are the standard choice for locking in process context. They put the task to sleep if the lock is busy, yielding the CPU. They enforce strict ownership, which helps detect bugs.
• Semaphores are also sleeping locks but are more flexible. They should be used for scenarios that require counting resources or where the strict ownership of a mutex is too restrictive.
• The first question you should always ask is: "What context(s) will this lock be acquired from?" If an interrupt handler is involved, the choice is immediately narrowed to a spinlock.

In our next lesson, we will put this knowledge into practice. You will implement a kernel module that correctly synchronizes access to shared data using these appropriate locking primitives, solidifying your theoretical understanding with hands-on coding.