6 ms·

Semaphores are surprisingly versatile (2015)

69 points by bubblehack3r 4y ago

dang 4y ago
Discussed at the time: Semaphores are surprisingly versatile - https://news.ycombinator.com/item?id=9212868 https://news.ycombinator.com/item?id=9212868 - March 2015 (17 comments)
ComputerGuru 4y ago
There are so many more types of semaphores than most people realize, and they're way more versatile than their humble api might make you think. I had a go at implementing Win32-style semaphores in rust and wrote up about it at length; most people coming from the posix world had never experienced the almost "thread pool management" levels of awesomeness you can get from such a tiny api. https://neosmart.net/blog/2022/implementing-truly-safe-semaphores-in-rust/ https://neosmart.net/blog/2022/implementing-truly-safe-semap...
- pantalaimon 4y ago
  I find an 'inverse semaphore' more useful: It blocks until it has been posted n times, where n is the init value. That way you can wait for n threads to finish work.
  - ComputerGuru 4y ago
    Yeah, I’ve published the same (I called it a CountdownEvent) for rust and use it a lot: https://docs.rs/rsevents-extra/latest/rsevents_extra/struct.CountdownEvent.html https://docs.rs/rsevents-extra/latest/rsevents_extra/struct.... Blocks until n threads or n tasks have completed. Latter is useful in a threadpool context.
  - greenbit 4y ago
    Sounds a bit like the java.util.concurrent CyclicBarrier
  - sk5t 4y ago
    This is called a latch or countdown latch in the languages I use most often.
  - manwe150 4y ago
    I believe posix pthreads calls that a barrier
    - gpderetta 4y ago
      A barrier blocks all threads until they all have passed it right? The countdown latch is a bit different.
- csdvrx 4y ago
  > There are so many more types of semaphores than most people realize This. For me, a semaphore is a general way handle states and dependancies with synchronization. Whether it's a file named ".lock" (like a simple traffic signal) or some fancy IPC (like a 4 way intersection between a segment with heavy traffic that gets the green light 99% of time, and one with low traffic, with cameras to detect cars on the small road for the 1% it will be useful, and pedestrian crossings with buttons to request a red ligh), it boils down to the same thing: enforcing states, with synchronization. I'll make you laugh, but recently I used environment variables (!!) to do some basic semaphore without even a .lock file! It may be ugly, but I needed something simple that would work on Windows and Linux. It did the job!
  - askvictor 4y ago
    There are plenty of types of locking mechanisms. A semaphore is a specific type of such. Sure, they might look different on different systems, or have different surfaces, but all should (or at least the ones I've seen) have an integer. Unless the term has been overloaded (sigh) and it's come to mean different things.
    - csdvrx 4y ago
      > all should (or at least the ones I've seen) have an integer. To store integers like "5" with environment variables, I use export VARIABLE=5
      - askvictor 4y ago
        The point of a semaphore though is that it checks the value then modifies it in an atomic operation. If you can't guarantee the operation is atomic, you haven't solved the underlying problem.
- ridiculous_fish 4y ago
  I overall like this article and share your admiration for semaphores; however this part ain't so: > there’s not much theoretical benefit to such a binary semaphore over a mutex – in fact, they’re interchangeable Not interchangeable! A binary semaphore has a superpower over a mutex: the lock-taker ("decrementer") can be disconnected from the lock-releaser ("incrementer"). You may wait for a thing and later be notified of the thing, but the notification comes on another thread, or in a signal handler, etc. But mutexes cannot handle locking in one thread and being unlocked somewhere else. Binary semaphores handle this fine; in this way they share something in common with condvars and also with mutexes. The article calls this the "ugly part": how do you handle release()? But that's the source of a semaphore's power!
  - Salgat 4y ago
    That's a specific type of mutex. Mutexes and single count Semaphores can absolutely be the same thing depending on the implementation. Similar to how some mutexes can be re-entrant but not always.
    - ridiculous_fish 4y ago
      Fascinating. What mutex allows being released from another thread? I believe you they exist, I have just never heard of such a thing.
      - ComputerGuru 4y ago
        Not the one you're replying to, but it depends on what you mean by "allows." If you don't mean "in its spec" but "in practice, as written and most commonly used" then the pthread mutex fits that definition, at least under Linux, as noted in a footnote in the article: > You can see a sample application testing for pthread_mutex_unlock() safety > here [0] and try it out for yourself online here [1]. [0]: https://gist.github.com/mqudsi/5aac71d8177866ba2762bda01a3ff21a https://gist.github.com/mqudsi/5aac71d8177866ba2762bda01a3ff... [1]: https://onlinegdb.com/9hmNhBuEc https://onlinegdb.com/9hmNhBuEc You can literally use it as a binary semaphore, but I can't think of a good reason to do so since pthread semaphores are signal safe while pthread mutexes aren't (which is why many people do the opposite). The only way it can not work that way is to keep track of the owning thread id, which it elides as an optimization and trusts the caller to "use it wisely" instead. Using PTHREAD_MUTEX_ERRORCHECK instead of PTHREAD_MUTEX_NORMAL (which pretty much every platform I've seen defaults to as the value of PTHREAD_MUTEX_DEFAULT) causes that to fail, but when's the last time you ran into a project using PTHREAD_MUTEX_ERRORCHECK? (PTHREAD_MUTEX_RECURSIVE technically has the information required to also validate the unlocking thread, but I haven't tried to see if does in practice.)
marshray 4y ago
Does anyone have any insight into this rationale: For the same reason they’re absent from Boost: a preference for mutexes and condition variables. From the library maintainers’ point of view, conventional semaphore techniques are just too error prone. The link to the Boost FAQ page from the C++ document site is 404.
- aidenn0 4y ago
  I don't know what the Boost FAQ said, but IME, Semaphores are often used to incorrectly implement condition variables. Given traditional semaphores it's not possible to do in a reasonably performant manner, and even with the correct extension to semaphores, the implementation is quite non-obvious. Mutexes can't be properly used for signaling, so they are less likely to be abused in this manner[1]. [edit] From the linked open-std doc: > This paper acknowledges that semaphores should be only used in situations where mutex and condition variable combination can't offer enough performance or the function notifying an event can't be blocked. Because of this, this paper proposes standardizing a semaphore interface that can be optionally implemented by vendors (this is likely to happen in embedded C++ implementations). All embedded and realtime operating systems offer semaphore operations, so this shows the importance of semaphore classes for programming non-blocking critical tasks. The proposed interface is: In terms of "mutex and condition variable combination can't offer enough performance" unless you really know what you're doing, using semaphores instead will give you higher performance at the cost of subtle bugs. 1: Though POSIX mutexes on Linux can be used for signalling (i.e. the thread that acquires and the thread that releases a mutex need not be the same), causing portability issues with some code developed on Linux...
- rerdavies 4y ago
  Semaphores are particularly treacherous on processors with weakly-ordered memory models (ARM and PowerPC notably). Condition variables are much easier to reason about, because there are clear and unambiguous memory barriers around data being shared by sender and receiver threads; and semaphores are trivially implementable using condition variables if that's truly all you need. On processors with weakly-ordered memory models, consecutive writes to memory by one thread may be seen as occurring in a different order on a receiver thread. On processor with a strongly-ordered memory model (Intel), you can sometimes update the state of data being controlled by the semaphore before set, and after wait by relying on strong ordering of reads and writes (although it is insanely easy to make a make mistakes that causes terrible bugs, and infamously difficult to determine whether you haven't made a mistake). On weakly-ordered platforms this doesn't work so you almost always have to update the state of the controlled object before set, and after wait while holding a mutex. But if you're going to use both a mutex AND a semaphore, then you may as well use a condition variable instead. Bottom line: if you use a semaphore on a processor with a weakly-ordered memory model, you are almost definitely doing it wrong; and if you use one on a processor with a strongly-ordered memory model, you are still probably doing it wrong. As to efficiency -- I can't imagine there is a meaningful difference. And even if there is, having a much higher chance of doing it right surely makes up for it.
deleted 4y ago
[deleted]
raphlinus 4y ago
Going through the comments provides another datapoint for what I have observed as an ironclad law: the first version of any code involving tricky atomics and synchronization is always wrong. Reasoning about these things is hard for human brains. I strongly recommend using tools when viable. In Rust a particularly easy-to-use and effective one is loom[1]. Alloy is another good tool that scales well but requires investment. In some cases like the Vulkan memory model, Alloy files are available[2]. [1]: https://docs.rs/loom/latest/loom/ https://docs.rs/loom/latest/loom/ [2]: https://github.com/KhronosGroup/Vulkan-MemoryModel https://github.com/KhronosGroup/Vulkan-MemoryModel
scotty79 4y ago
In Rust there's a thing called Condvar https://doc.rust-lang.org/std/sync/struct.Condvar.html https://doc.rust-lang.org/std/sync/struct.Condvar.html I don't really know how it relates to semaphores but it was exactly what I needed last time when I wanted to parallelize some computation and I needed to pause starved threads and unpause them all of them only after the last one got starved and triggered generation of next data block and moved focus of computation to that new block.
- gpderetta 4y ago
  Cond vars are always coupled with a mutex, they are also stateless and edge triggered, that make them a bit different from semaphores.
epolanski 4y ago
Are those similar to Scala Zio semaphores?

69 points by bubblehack3r 4y ago

dang 4y ago

Discussed at the time: Semaphores are surprisingly versatile - https://news.ycombinator.com/item?id=9212868 https://news.ycombinator.com/item?id=9212868 - March 2015 (17 comments)

ComputerGuru 4y ago

There are so many more types of semaphores than most people realize, and they're way more versatile than their humble api might make you think. I had a go at implementing Win32-style semaphores in rust and wrote up about it at length; most people coming from the posix world had never experienced the almost "thread pool management" levels of awesomeness you can get from such a tiny api. https://neosmart.net/blog/2022/implementing-truly-safe-semaphores-in-rust/ https://neosmart.net/blog/2022/implementing-truly-safe-semap...

pantalaimon 4y ago
I find an 'inverse semaphore' more useful: It blocks until it has been posted n times, where n is the init value. That way you can wait for n threads to finish work.
- ComputerGuru 4y ago
  Yeah, I’ve published the same (I called it a CountdownEvent) for rust and use it a lot: https://docs.rs/rsevents-extra/latest/rsevents_extra/struct.CountdownEvent.html https://docs.rs/rsevents-extra/latest/rsevents_extra/struct.... Blocks until n threads or n tasks have completed. Latter is useful in a threadpool context.
- greenbit 4y ago
  Sounds a bit like the java.util.concurrent CyclicBarrier
- sk5t 4y ago
  This is called a latch or countdown latch in the languages I use most often.
- manwe150 4y ago
  I believe posix pthreads calls that a barrier
  - gpderetta 4y ago
    A barrier blocks all threads until they all have passed it right? The countdown latch is a bit different.
csdvrx 4y ago
> There are so many more types of semaphores than most people realize This. For me, a semaphore is a general way handle states and dependancies with synchronization. Whether it's a file named ".lock" (like a simple traffic signal) or some fancy IPC (like a 4 way intersection between a segment with heavy traffic that gets the green light 99% of time, and one with low traffic, with cameras to detect cars on the small road for the 1% it will be useful, and pedestrian crossings with buttons to request a red ligh), it boils down to the same thing: enforcing states, with synchronization. I'll make you laugh, but recently I used environment variables (!!) to do some basic semaphore without even a .lock file! It may be ugly, but I needed something simple that would work on Windows and Linux. It did the job!
- askvictor 4y ago
  There are plenty of types of locking mechanisms. A semaphore is a specific type of such. Sure, they might look different on different systems, or have different surfaces, but all should (or at least the ones I've seen) have an integer. Unless the term has been overloaded (sigh) and it's come to mean different things.
  - csdvrx 4y ago
    > all should (or at least the ones I've seen) have an integer. To store integers like "5" with environment variables, I use export VARIABLE=5
    - askvictor 4y ago
      The point of a semaphore though is that it checks the value then modifies it in an atomic operation. If you can't guarantee the operation is atomic, you haven't solved the underlying problem.
ridiculous_fish 4y ago
I overall like this article and share your admiration for semaphores; however this part ain't so: > there’s not much theoretical benefit to such a binary semaphore over a mutex – in fact, they’re interchangeable Not interchangeable! A binary semaphore has a superpower over a mutex: the lock-taker ("decrementer") can be disconnected from the lock-releaser ("incrementer"). You may wait for a thing and later be notified of the thing, but the notification comes on another thread, or in a signal handler, etc. But mutexes cannot handle locking in one thread and being unlocked somewhere else. Binary semaphores handle this fine; in this way they share something in common with condvars and also with mutexes. The article calls this the "ugly part": how do you handle release()? But that's the source of a semaphore's power!
- Salgat 4y ago
  That's a specific type of mutex. Mutexes and single count Semaphores can absolutely be the same thing depending on the implementation. Similar to how some mutexes can be re-entrant but not always.
  - ridiculous_fish 4y ago
    Fascinating. What mutex allows being released from another thread? I believe you they exist, I have just never heard of such a thing.
    - ComputerGuru 4y ago
      Not the one you're replying to, but it depends on what you mean by "allows." If you don't mean "in its spec" but "in practice, as written and most commonly used" then the pthread mutex fits that definition, at least under Linux, as noted in a footnote in the article: > You can see a sample application testing for pthread_mutex_unlock() safety > here [0] and try it out for yourself online here [1]. [0]: https://gist.github.com/mqudsi/5aac71d8177866ba2762bda01a3ff21a https://gist.github.com/mqudsi/5aac71d8177866ba2762bda01a3ff... [1]: https://onlinegdb.com/9hmNhBuEc https://onlinegdb.com/9hmNhBuEc You can literally use it as a binary semaphore, but I can't think of a good reason to do so since pthread semaphores are signal safe while pthread mutexes aren't (which is why many people do the opposite). The only way it can not work that way is to keep track of the owning thread id, which it elides as an optimization and trusts the caller to "use it wisely" instead. Using PTHREAD_MUTEX_ERRORCHECK instead of PTHREAD_MUTEX_NORMAL (which pretty much every platform I've seen defaults to as the value of PTHREAD_MUTEX_DEFAULT) causes that to fail, but when's the last time you ran into a project using PTHREAD_MUTEX_ERRORCHECK? (PTHREAD_MUTEX_RECURSIVE technically has the information required to also validate the unlocking thread, but I haven't tried to see if does in practice.)

marshray 4y ago

Does anyone have any insight into this rationale: For the same reason they’re absent from Boost: a preference for mutexes and condition variables. From the library maintainers’ point of view, conventional semaphore techniques are just too error prone. The link to the Boost FAQ page from the C++ document site is 404.

aidenn0 4y ago
I don't know what the Boost FAQ said, but IME, Semaphores are often used to incorrectly implement condition variables. Given traditional semaphores it's not possible to do in a reasonably performant manner, and even with the correct extension to semaphores, the implementation is quite non-obvious. Mutexes can't be properly used for signaling, so they are less likely to be abused in this manner[1]. [edit] From the linked open-std doc: > This paper acknowledges that semaphores should be only used in situations where mutex and condition variable combination can't offer enough performance or the function notifying an event can't be blocked. Because of this, this paper proposes standardizing a semaphore interface that can be optionally implemented by vendors (this is likely to happen in embedded C++ implementations). All embedded and realtime operating systems offer semaphore operations, so this shows the importance of semaphore classes for programming non-blocking critical tasks. The proposed interface is: In terms of "mutex and condition variable combination can't offer enough performance" unless you really know what you're doing, using semaphores instead will give you higher performance at the cost of subtle bugs. 1: Though POSIX mutexes on Linux can be used for signalling (i.e. the thread that acquires and the thread that releases a mutex need not be the same), causing portability issues with some code developed on Linux...
rerdavies 4y ago
Semaphores are particularly treacherous on processors with weakly-ordered memory models (ARM and PowerPC notably). Condition variables are much easier to reason about, because there are clear and unambiguous memory barriers around data being shared by sender and receiver threads; and semaphores are trivially implementable using condition variables if that's truly all you need. On processors with weakly-ordered memory models, consecutive writes to memory by one thread may be seen as occurring in a different order on a receiver thread. On processor with a strongly-ordered memory model (Intel), you can sometimes update the state of data being controlled by the semaphore before set, and after wait by relying on strong ordering of reads and writes (although it is insanely easy to make a make mistakes that causes terrible bugs, and infamously difficult to determine whether you haven't made a mistake). On weakly-ordered platforms this doesn't work so you almost always have to update the state of the controlled object before set, and after wait while holding a mutex. But if you're going to use both a mutex AND a semaphore, then you may as well use a condition variable instead. Bottom line: if you use a semaphore on a processor with a weakly-ordered memory model, you are almost definitely doing it wrong; and if you use one on a processor with a strongly-ordered memory model, you are still probably doing it wrong. As to efficiency -- I can't imagine there is a meaningful difference. And even if there is, having a much higher chance of doing it right surely makes up for it.

deleted 4y ago

[deleted]

raphlinus 4y ago

Going through the comments provides another datapoint for what I have observed as an ironclad law: the first version of any code involving tricky atomics and synchronization is always wrong. Reasoning about these things is hard for human brains. I strongly recommend using tools when viable. In Rust a particularly easy-to-use and effective one is loom[1]. Alloy is another good tool that scales well but requires investment. In some cases like the Vulkan memory model, Alloy files are available[2]. [1]: https://docs.rs/loom/latest/loom/ https://docs.rs/loom/latest/loom/ [2]: https://github.com/KhronosGroup/Vulkan-MemoryModel https://github.com/KhronosGroup/Vulkan-MemoryModel

scotty79 4y ago

In Rust there's a thing called Condvar https://doc.rust-lang.org/std/sync/struct.Condvar.html https://doc.rust-lang.org/std/sync/struct.Condvar.html I don't really know how it relates to semaphores but it was exactly what I needed last time when I wanted to parallelize some computation and I needed to pause starved threads and unpause them all of them only after the last one got starved and triggered generation of next data block and moved focus of computation to that new block.

gpderetta 4y ago
Cond vars are always coupled with a mutex, they are also stateless and edge triggered, that make them a bit different from semaphores.

epolanski 4y ago

Are those similar to Scala Zio semaphores?