Semaphore Implementation and Atomicity
What you'll learn: How semaphores are actually implemented to guarantee their operations are atomic and uninterruptible.
You've learned that semaphores provide wait() and signal() operations to coordinate access to shared resources. But there's a catch: these operations themselves modify shared data (the semaphore counter). How do we ensure wait() and signal() don't suffer from race conditions?
The Core Challenge
A semaphore's wait() operation does three things: check the counter, potentially decrement it, and possibly block the thread. If two threads execute wait() simultaneously on the same semaphore, they could both read the same counter value, both decrement it, and both proceed—violating mutual exclusion. The semaphore's own operations must be atomic (indivisible).
Implementation Approaches
Hardware Support
Modern processors provide atomic instructions like test-and-set, compare-and-swap, or fetch-and-add. Semaphore operations are built on top of these primitives. The hardware guarantees that even on multicore systems, only one processor can execute the atomic instruction at a time on a given memory location.
Disabling Interrupts
On single-processor systems, a simpler approach is to disable interrupts during semaphore operations. This prevents context switches mid-operation, ensuring atomicity. However, this only works on uniprocessor systems and is generally discouraged because disabling interrupts affects the entire system.
Think of It This Way
Imagine a vending machine (semaphore) where inserting a coin and checking stock must happen together. If two customers could simultaneously insert coins and check stock, both might get the last item. Hardware atomicity is like a physical slot that only accepts one coin at a time—mechanically impossible to interleave.
Key Takeaway: Semaphores rely on hardware atomic instructions or interrupt disabling to ensure their wait() and signal() operations execute indivisibly, preventing race conditions in the synchronization mechanism itself.