So, one thing I never really got about semaphores is: what are actual practical uses of initialising it with a count >1? What kind of resource allows concurrent access from N>1 threads but not N+1?
Modules maintainer Luis Chamberlain has recently been working on a problem where the arrival of a large number of requests to load modules in a short time can create difficulties for the memory-management subsystem. After some discussion, he posted a proposal for a mechanism that would simply limit the number of module-load operations that can be underway at any given time. Linus Torvalds quickly answered, reminding Chamberlain that semaphores (”“a classic concurrency limiter””) could be used for that purpose. The patch has since been reworked along those lines.
But it’s not really rate limiting unless you also intentionally stall requests to slow them down, is it? It’s “just” a concurrency limiter which is less common than rate limiting.
In graphics rendering you can use semaphores this way to synchronize shared GPU and CPU access to N buffers. You initialize the semaphore with the value N.
The CPU writes to the buffers and cycles through them, decrementing the semaphore each time it writes. When it hits 0, it stops and waits.
Every time the GPU finishes reading from a buffer, it increments the semaphore.
This setup ensures the CPU does not overwrite data that is either currently being read or has not yet been read.
One example from my recent work is a ring buffer where the producer needs to wait for capacity to be available. The semaphore gets initialized to the capacity of the ring buffer.
I’ve always found semaphores (compared to other concurrency concepts) hard to understand, and not terribly useful. I don’t think I’ve ever actually used one. I don’t doubt that they have their place for certain problems, but they always seemed more like a niche thing, and when reading about concurrency they always seemed to me to get more airtime than they deserved.
I might but the ‘not terribly useful’ bit, since that’s very situational, but why are they hard to understand? They model a bucket full of flags. You want to do a thing, you take a flag. No flags? Wait. You want to allow someone else to do a thing? Put a flag in the bucket. These were used almost 200 years ago to control access to segments of railway lines, you don’t even need to understand anything about computers to understand them.
Interesting. For me it’s the opposite, i never found any concurrency model that I can reason about easier than the original P() and V() introduced by Dijkstra.
Typically one will wrap access to any shared resource in a semaphore to prevent race conditions.
What’s the difference between “wrap[ping] access to any shared resource in a semaphore” and protecting it with a mutex?
A mutex is a specialisation of a mutex with two key properties:
A mutex is a binary semaphore: its value is either 0 (unlocked) or 1 (locked) and begins life in state 1, semaphores in general can have any maximum count and can start with any count value.
A mutex has the additional property that it must be locked by the current lock owner, semaphores in general can be incremented and decremented independently (this is somewhat debatable, some things that are called mutexes don’t enforce this property).
This means that you can trivially use a semaphore for any use case where a mutex is also appropriate, but given its additional restrictions a mutex may be either more efficient or may give better debugging features. Some mutex implementations are thin wrappers around semaphores.
Generally, you want to protect a resource with a semaphore if you don’t want either of these properties. For example:
If you are providing backpressure in a pipeline or are protecting a resource that is passed between threads. In the former case, you may have initialise a semaphore to the number of in-flight tasks that you permit in a pipeline, decrement it when you start processing and increment it at the end. This protects you from unbounded queue growth.
If you allow a small number of concurrent accesses to a resource. This is rare for memory, but it’s useful for things like network connections. For example, you might want to permit up to 10 parallel connections to some server, so you initialise a semaphore with a value of 10, then decrement it every time you start a connection and increment it when you finish one. Any thread that tries to connect will block until either another thread finishes or will time out.
If you have some kind of ownership abstraction that means that you are starting to work on a resource in one thread and finishing in another, a semaphore has an implicit ownership model.
Notably, the Rust MutexGuard type is !Send because some prominent OS mutex implementations will crash the process if a mutex is unlocked on a thread that did not lock it.
Depending on the options used to create it, POSIX says that unlocking a not-owned mutex is either UB or will return an error. On some platforms, normal mutexes default to behaving like error checking ones.
POSIX also has a notion of a ‘recursive’ mutex, which is a mutex that you can lock multiple times from the same thread and unlock the same number of times. To implement this, a mutex needs to contain an owning thread and a lock count. The lock count is typically also used in normal (non-recursive) mutexes, it’s just that you never try to move it up from 1. If you have space for the owner, then on non-recursive mutexes then you basically get error-checking mutexes from the same code paths and the implementations are simpler of recursive, error-checking, and normal mutexes are the same shape. The cost of error-checking mutexes is pretty trivial - it’s one extra load and a compare-and-branch (if you store something like the %gs base there), and the branch is always statically predicted not taken.
I meant them as being equivalent. It’s mostly a matter of what you or your API calls it.
If you just mean using a semaphore like a mutex, that’s probably not the part which people have trouble understanding about semaphores
What else does it do? It just let’s a finite number of concurrent executions access a resource. Often times just one. What is there more to understand? Honest question.
So, one thing I never really got about semaphores is: what are actual practical uses of initialising it with a count >1? What kind of resource allows concurrent access from N>1 threads but not N+1?
There’s one answer in the article itself:
More generally, semaphores are a primitive that can be used for anything that needs rate limiting, as opposed to exclusive access.
Single threaded redis behaves as a global semaphore.
But it’s not really rate limiting unless you also intentionally stall requests to slow them down, is it? It’s “just” a concurrency limiter which is less common than rate limiting.
Requests are stalled when they’re waiting for the semaphore.
I guess I was unclear. A semaphore says that there are e.g. 20 lanes on a road, but it doesn’t constrain the speed at which vehicles use those lanes.
To get rate limiting you’d have to constrain the speed, too.
In graphics rendering you can use semaphores this way to synchronize shared GPU and CPU access to N buffers. You initialize the semaphore with the value N.
The CPU writes to the buffers and cycles through them, decrementing the semaphore each time it writes. When it hits 0, it stops and waits.
Every time the GPU finishes reading from a buffer, it increments the semaphore.
This setup ensures the CPU does not overwrite data that is either currently being read or has not yet been read.
Have a look into The little Book of Semaphores.
One example from my recent work is a ring buffer where the producer needs to wait for capacity to be available. The semaphore gets initialized to the capacity of the ring buffer.
I’ve always found semaphores (compared to other concurrency concepts) hard to understand, and not terribly useful. I don’t think I’ve ever actually used one. I don’t doubt that they have their place for certain problems, but they always seemed more like a niche thing, and when reading about concurrency they always seemed to me to get more airtime than they deserved.
I might but the ‘not terribly useful’ bit, since that’s very situational, but why are they hard to understand? They model a bucket full of flags. You want to do a thing, you take a flag. No flags? Wait. You want to allow someone else to do a thing? Put a flag in the bucket. These were used almost 200 years ago to control access to segments of railway lines, you don’t even need to understand anything about computers to understand them.
I knew a semaphore was a kind of flag irl, but I never realized this is what they had in mind with the abstraction….
Interesting. For me it’s the opposite, i never found any concurrency model that I can reason about easier than the original P() and V() introduced by Dijkstra. Typically one will wrap access to any shared resource in a semaphore to prevent race conditions.
What’s the difference between “wrap[ping] access to any shared resource in a semaphore” and protecting it with a mutex?
If you just mean using a semaphore like a mutex, that’s probably not the part which people have trouble understanding about semaphores.
A mutex is a specialisation of a mutex with two key properties:
This means that you can trivially use a semaphore for any use case where a mutex is also appropriate, but given its additional restrictions a mutex may be either more efficient or may give better debugging features. Some mutex implementations are thin wrappers around semaphores.
Generally, you want to protect a resource with a semaphore if you don’t want either of these properties. For example:
Notably, the Rust MutexGuard type is !Send because some prominent OS mutex implementations will crash the process if a mutex is unlocked on a thread that did not lock it.
Depending on the options used to create it, POSIX says that unlocking a not-owned mutex is either UB or will return an error. On some platforms, normal mutexes default to behaving like error checking ones.
POSIX also has a notion of a ‘recursive’ mutex, which is a mutex that you can lock multiple times from the same thread and unlock the same number of times. To implement this, a mutex needs to contain an owning thread and a lock count. The lock count is typically also used in normal (non-recursive) mutexes, it’s just that you never try to move it up from 1. If you have space for the owner, then on non-recursive mutexes then you basically get error-checking mutexes from the same code paths and the implementations are simpler of recursive, error-checking, and normal mutexes are the same shape. The cost of error-checking mutexes is pretty trivial - it’s one extra load and a compare-and-branch (if you store something like the %gs base there), and the branch is always statically predicted not taken.
I meant them as being equivalent. It’s mostly a matter of what you or your API calls it.
What else does it do? It just let’s a finite number of concurrent executions access a resource. Often times just one. What is there more to understand? Honest question.
For most of my programs, semaphores have been superseded by wallclock-based rate limiters.
You mean something like that? https://stackoverflow.com/a/668327