7 ms·
Semaphores are nice for text book examples, but should be avoided in practical multi threaded programming in a shared memory environment. A mutex and condition
by exDM69 9y ago
Semaphores are nice for text book examples, but should be avoided in practical multi threaded programming in a shared memory environment. A mutex and condition variables usually provides a cleaner solution that is easier to reason about. In particular, the expression for the condition that's waited on can be arbitrarily complex, not just a single integer like a semaphore's internal state.
A particularly tricky problem is clean program termination when waiting on semaphores. It is much easier to add while(!quit && not_satisfied) cond_wait(lock, is_satisfied); than doing the same with semaphores. You need to add extra synchronization for this case with semaphores. Every call to cond_wait usually needs a check for a "quit" flag.
Semaphores are still useful in other kinds of asynchronous processes such as CPU to GPU synchronization or keeping trains on railways from colliding.
If you encounter a semaphore in multi threaded code that's been written recently, assume it is incorrect. That's the case in the past half a dozen cases where I came across one in the codebase I work on. The most common bug was the program hanging on exit. Replacing them with mutex and condition variables (plural!) was easy, the solution was much simpler to understand and it was correct and the programs now terminated cleanly when exit was requested.
Semaphores should really be removed from the OS class curriculum. Maybe leave them in the advanced parallel/concurrent programming course because they're easy to reason about in formal proofs. But in multi threaded programming, they're almost always the wrong tool for the job.
- sillysaurus3 9y agoLocks in general are super slow. If you use a ringbuffer you can avoid them and use an atomic increment instead.
- exDM69 9y agoThat's a common misconception, obtaining an uncontended mutex (futex) is just a single atomic operation that takes about 25 nanoseconds. Lock-free programming with atomics is even more difficult than reasoning about code with locks. It is best left to very specialized cases where maximum throughput is necessary and contention is high. Most practical use cases don't benefit from that. The key is minimizing the time the locks are held. That drives down contention and keeps performance high.
- sillysaurus3 9y agoIt's not really the locks that end up the problem. The problem is the queues. If you use locks you end up shoving data into queues which kills your performance. Unbounded memory growth is fun whenever your producer makes messages faster than your consumer can pull stuff out of the queue. If you just use a disruptor implementation then there's no need to reason about anything. It's good to go and performant by default.
- exDM69 9y agoHighly contended queues aren't very common, at least in the kind of programming I do. If contention is extremely high and throughput is paramount, then a lockless solution might work. E.g. audio processing or network stacks might have this kind of usage pattern. But in my experience, most queues are empty most of the time. That's when you want a lock so the consumer thread can sleep instead of busy wait.
- lomnakkus 9y agoNot to mention: If you thought $OLD_SOLUTION was hard, then lockless is a whole other level of difficulty. (This is why I would generally advocate for a message-passing style for almost everything, but obviously that's not quite the context of this thread. My reasoning is that you can always start off with message passing and if you discover that that's your bottleneck, you can always transition to a faster alternative[1]. Plus, you could use a lock-free message passing solution, e.g. Aeron.) [1] Plus, by using message passing you've already got pretty good separation of logic.
- bogomipz 9y ago>"That's a common misconception, obtaining an uncontended mutex (futex) is just a single atomic operation that takes about 25 nanoseconds" A futex is just a specific implementation of a mutex though right? Or am I reading your comment wrong? I am curious where the 25 ns comes from. Also isn't what makes a futex so fast is that it's done in user space - hence the name?
- twoodfin 9y agoSemaphores also lack a notion of ownership, which makes tasks like detecting/debugging deadlocks and remedying priority inversion more difficult.
- exDM69 9y agoIndeed. When you have a mutex+condition, you can add instrumentation like logging or timers for debugging, testing and verification purposes.
- jeremiep 9y agoI believe semaphores and condition variables solve different problems. Programs hanging at the exit only means the engineer mostly tested the happy path, not that semaphores are evil. I've seen plenty of deadlocks on mutexes at shutdown as well :)
- exDM69 9y agoThe point is that implementing a semaphore with a mutex and condition is very easy but more versatile. A semaphore only has a single integer internal state, a condition can guard any number of shares variables. I see no reason to use semaphores in multithreaded programming because of this. They have no advantages over mutex and condition but are much more limited.
- pkaye 9y agoAre there any performance benefits of semaphores vs mutex/condition?
- exDM69 9y agoNo. Not really. Programs should be optimized for the uncontended case where a mutex and semaphore are pretty similar. Some textbook toy problems are theoretically faster with semaphores but that's not really the case for practical problems. The overhead of synchronization primitives isn't really a concern in practice.
- bonzini 9y agoThere are two uses of synchronization primitives, those that should never wait (mutexes) and those that should always wait. The example of the latter is a work queue, where work threads need to wake up as fast as possible. In that case, using semaphores or other "exotic" synchronization primitives (my favorite are Windows's manual-reset events) can help eliminate contention. Problems with exiting threads are real. An often sufficient solution is to make the semaphore (or event) waiters "detached" and not care about them, while ensuring that the producers don't exit until their work has been completed. As with other advanced multithreaded programming techniques, discipline is key, together with noticing, documenting and applying recurrent idioms.
- pkulak 9y agoSemaphores are perfect for controlling the amount of concurrency. I use then for this all the time. Sure I could use a mutex and a counter plus comparison and busy wait... but why? As far as I'm concerned, a semaphore is just a more extendable mutex.
- exDM69 9y agoThere's no busy waiting involved with condition variables. The while loop is there to guard against spurious wakeups, and it is not a "busy" loop. A semaphore can be implemented using a mutex and a condition at pretty much the same cost as a "raw" semaphore. It is theoretically 2x faster (1 vs 2 atomics needed) but that isn't worth the handicap from being constrained to a single integer state. If you need two or more semaphores, it's already much worse. And even many textbook examples do (to guarantee clean exit). A semaphore is just a crippled condition variable that had only a single integer as a state. It sort-of works but isn't very practical in real world applications.
- MichaelMoser123 9y agoReminds me of this bug: https://sourceware.org/bugzilla/show_bug.cgi?id=12674 https://sourceware.org/bugzilla/show_bug.cgi?id=12674 Now go and trust anybody after that....