Implementation of Semaphores in kernel..?

Question

I am reading "Operating System Concepts" to understand Semaphores. An excerpt from the book:

"The critical aspect of semaphores is that they be executed atomically- We must guarantee that no two processes can execute waitO and signal() operations on the same semaphore at the same time. This is a critical-section problem; and in a single-processor environment (that is, where only one CPU exists), we can solve it by simply inhibiting interrupts during the time the wait () and signal () operations are executing. This scheme works in a single- processor environment because, once interrupts are inhibited, instructions from different processes cannot be interleaved. Only the currently running process executes until interrupts are reenabled and the scheduler can regain control.

In a multiprocessor environment, interrupts must be disabled on every processor; otherwise, instructions from different processes (running on differ- ent processors) may be interleaved in some arbitrary way. Disabling interrupts on every processor can be a difficult task and furthermore can seriously dimin- ish performance. Therefore, SMP systems must provide alternative locking techniques—such as spinlocks—to ensure that waitO and signal0 are performed atomically."

My question is that:

How is this spinlock implemented? Using hardware instructions like TestAndSet()? Because, at some point some support from hardware would be needed (either user takes that support or kernel takes that support), because we want an instruction which does testing and setting in one instruction (which can not be interrupted in between).

Though in the book, I can not find any such statement that at some point, some hardware support is needed. It explains semaphore as software technique to achieve synchronization. Is this misleading?

Answer 1

You cannot implement SMP spinlocks without some kind of hardware support, in this case atomic test-and-set and atomic increment operation. See here for a discussion of how it is done on different architectures.

See arch/x86/include/asm/spinlock.h for the Linux/x86 implementation of it.

Answer 2

In theory, with shared memory you don't need atomic operations in order to achieve mutual exclusion. See e.g. Dekker's algorithm. However, although this works, the performance would be hardly hit. That's why most processor architectures support atomic instructions (such as test and set/compare and swap). Another reason can be that things can get even more complicated with cacheing - multiple processors can have different view of the memory. Altogether atomic instructions cause less problems.