Semaphores are surprisingly versatile | Hacker News Reader

Semaphores are surprisingly versatile

preshing.com

89 pointsnkurz17 comments

Semaphores are theoretically versatile. However, when they are actually used to construct higher level primitives, the result are "Rube Goldberg devices". It is bad engineering.

Also, note that the examples on this page depend on atomic operations in addition to semaphores, not semaphores alone. If you only use semaphores, you must also use them to protect the accesses that are required to be atomic, which complicates the code.

Let's look at LightWeightMutex. This object is so light weight that we can't even ask it whether it is currently locked, and who the owner is. These features are important for error detection and debugging: real-world requirements that actual mutex implementations satisfy.

Another comment; I find the following completely pointless:

    void lock()
    {
        if (m_contention.fetch_add(1, std::memory_order_acquire) > 0)
        {
            m_semaphore.wait();
        }
    }

A semaphore is already supposed to implement counting. What we have here is an implementation of a counting semaphore, using a semaphore.

That is to say, to implement a light weight lock using a semaphore, we actually need only this:

   void lock() { m_semaphore.wait(); }

The semaphore already has a built in atomic variable equivalent to the m_contention. The atomic increment and test wrapped around this is redundant, and has nothing to do with implementing a lock with a semaphore.

I think the point is that semaphore calls might be expensive, while in the normal case this is a simple one-instruction atomic increment.

My point, on the other hand, is that this one-instruction atomic increment and test, with a conditional wait call is a semaphore (though perhaps a faster one than the underlying semaphore). Whereas the point of the article is that semaphores are very flexible and can be used to implement other primitives.

This could be repaired by reframing the example as "look, slow semaphores, together with an atomic increment/test operation provided by the processor, can be used to implement faster semaphores!"

This is actually a useful case that tends to be overlooked by "primitives X, Y, and Z out of semaphores" tutorials.

If I implement the mutex as you suggest -- by using the native semaphore directly, with no separate counter -- the running time of "testBenaphore" increases from 375 ms to 3 seconds on my Windows PC.

As mentioned in the article, most mutex implementations already use this trick. So you can just use std::mutex, and things are fine.

In the past, though, runtime environments weren't so well-developed, so there definitely [was a point](http://www.haiku-os.org/legacy-docs/benewsletter/Issue1-26.h...).

That looks like some API/kernel call overhead; you've moved the fast path of the semaphore implementation into user space. But what you have there is undeniably a semaphore implementation: atomically tweak a counter, and based on that result, wait or signal.

> you've moved the fast path of the semaphore implementation into user space.

I see now why your original comment was a bit inflammatory. I should have been more clear in the post that by "lightweight", I meant exactly that: "fast path in user space". I guess not everyone shares this vocabulary. I'll improve the post.

You're right that this lightweight mutex is a semaphore, of course. But not every semaphore is a lightweight mutex. So the technique isn't pointless.

Seems like that's what any sane modern user space sync primitives would do: do the atomic ops in user space for the fast path, enter the kernel when it's time to block. Like the "futex" in Linux.

I suppose it is a fair point that the thing you use to enter the kernel doesn't have to be itself a semaphore.

Long ago when developing for the PS2 gaming machine, we used this exact technique to achieve a 10x faster mutex on that platform than using the semaphore directly as a mutex, so it hasn't always been pointless.

Thanks for posting this. I'm often surprised how few people know that almost all synchronization primitives can be implemented with each other. They are effectively equivalent.

However, as you say, some end up being hideously complicated. Some are "closer to the metal" than others - both in terms of the actual instruction set implementation, and kernel mechanisms used.

I've never been a fan of semaphores, because when used with count>1, they tend to be duplicating some other information in the system, which is easy to get out of sync. When used with just count 0 or 1, it's more intuitive (and closer to underlying implementation) to just use a mutex. And as you point out, the various mutex incarnations usually have an easier time of tracking ownership and debugging, by their nature.

> ... almost all synchronization primitives can be implemented with each other

Not to mention that any partial recursive function can be computed by a machine which can move along an unlimited tape, reading or writing a symbol, according to a handful of rules. :)

> And as you point out, the various mutex incarnations usually have an easier time of tracking ownership and debugging

Ownership, whether or not the owning thread died, deadlock detection, recursion detection ... priority inversion handling like priority inheritance ...

It's also difficult to solve problems like priority inversion, where a high-priority task H is blocked on a low-priority task L. Ideally you'd increase L's priority so H can make progress. But a semaphore doesn't track which thread is in the critical section, so you don't know which thread's priority to boost.

Maybe I'm wrong, but by checking the "redundant" atomic counter before trying to acquire the semaphore, he's saving up a system call, which would imply making (unnecessary) context changes.

I think the main source of confusion is that mutexes and semaphores have different semantics, and people tend to forget that. You cannot easily (in userspace) implement mutex with semaphore(s) or semaphore with mutexe(s), because they by design have different semantics, i.e. mutexes have owners and semaphores do not, mutex can be unlocked only by thread who locked it, ant semaphore does not have this feature/limitation - any process/thread who have rights to access semaphore can unlock previously locked (by any thread/process) semaphore, trying this with mutexes will give you undefined behaviour, etc.

I think it's actually pretty easy to implement a mutex with a semaphore. The opposite not so much. If you want extra debug checking, you can wrap the semaphore with another construct that sets the owner field on lock and checks it on unlock.

I believe the atomic add is an optimization. Atomic add can be done with an instruction from user space. The semaphore wait needs to enter the kernel, which has much more overhead.

By the way, as the author points out, we called this construct "Benaphores" in BeOS. Actually, semaphores were the primary kernel synchronization primitive in BeOS; there were no mutexes. Even sleep was implemented as a wait on a semaphore with a timeout. It made the kernel code cleaner because there was only one code path that unblocked threads. From the user space perspective, I found it to be pretty easy to use, especially since BeOS could acquire with a count greater than one. You could pretty easily to make a reader-writer lock with one semaphore (the writer acquired the max count)

The downside, as others pointed out, was that there was no way to do priority inheritance.

I recently found myself in need of a semaphore in go. They're quite easy to make out of channels:

Implementation:

https://github.com/scraperwiki/s4log/blob/master/semaphore.g...

Use:

https://github.com/scraperwiki/s4log/blob/2714f9553880121ad6...

Useful for:

1. Writing a web handler which may use some CPU time and you don't want too many of them in flight at once (to prevent them from all slowing down to mud). (Best combined with something to abort if we had to wait to long before we could even do computation)

2. Execute a parallel upload to S3, but avoid doing too many at once (again, because you don't want very many of them contending on the network connection such that none proceed).

If you're interested in writing concurrent code worth running, Mike Acton has a nice introduction:

http://cellperformance.beyond3d.com/articles/2009/08/roundup...

Reply on news.ycombinator.com