The shrinking role of semaphores | Hacker News Reader

The shrinking role of semaphores

lwn.net

125 pointssigna1131 comments

> There is, for example, a binary semaphore that persists in the printk() code because mutex_unlock() cannot be called from interrupt context, while up() can.

Interestingly, this oddity is mirrored in userspace, where `sem_post/3` is async-signal-safe, but most other concurrency primitives (e.g. `pthread_mutex_unlock/3` and `pthread_cond_broadcast/3`) are not.

(`write/2` and friends is the other notable async-signal-safe concurrency primitive, e.g. in combination with an eventfd or a pipe.)

I've been working on a fair bit of RTOS/embedded code recently and we've used a decent number of semaphores for exactly this reason: you can signal a semaphore from an interrupt context. Usually this is being done with a ring buffer where only the interrupt context writes to it and only "userland"[1] reads from it. We initialize the semaphore with an initial value of 0 and a max capacity that matches the capacity of the ring buffer. This lets the userland threads sleep until there's something in the ring buffer without having to worry about trying to use a mutex from inside an interrupt context (which is forbidden).

[1] It's not actually userland since it's a Cortex M0 with no MMU, but it's still practical to think of it that way.

I was just wondering when LWN was started, it feels like it's been around forever...

"When LWN was initially designed, at the end of 1997..."

I love the content at LWN and that it's STILL going strong for so damn long. It's hard to beat the content there.

For such a historied site it's maintained great quality, very admirable.

I hope people that admire its quality, and that can afford to, have also chosen to become financial supporters: https://lwn.net/subscribe/

I've been a subscriber for a while now.

They almost shuttered in 2002, it looks like!

https://lwn.net/Articles/5409/

Though invented by Dijkstra, semaphores are ironically the GO TO of synchronization.

"The unbridled use of the go to statement has an immediate consequence that it becomes terribly hard to find a meaningful set of coordinates in which to describe the process progress."

s/go to statement/semaphore/ -> still holds

I would say the are the assembler of concurrency. You should use higher level abstractions, but sometimes, it has its place.

I agree, I don't tend to think they are quite as dangerous as GOTOs have proven to be, but I do understand the criticism. The example provided about their use in interrupt handlers is of particular relevance.

goto isn't that dangerous, or that strange. It has it's place (like inline retries instead of recursion or for-loops) but it's rare to reach for them in most languages.

Semaphores are like a restricted form of goto which lets you branch exactly, say, two lines forward or two lines back. Building concurrency primitives out of semaphores is like using that goto to build control flow.

Sounds more like an if-statement than a goto. I catch your meaning though.

Actually I have to apologize to the GOTO somewhat. Semaphores are worse than GOTO.

Dijkstra didn't understand that GOTO is equivalent to tail recursion. The way you untangle the spaghetti of a GOTO graph with shared variables is to divide it into basic blocks, and turn them into pure tail-calling functions. The assignments to shared variables become argument passing. From there you might be able to identify some meaning in those functions.

The GOTO is also a fundamental block in that you can use conditionals and goto as a target language for higher level constructs --- and this is clear and efficient.

Semaphore API calls are a horrible target language for implementing other synchronization primitives. They are too encapsulated: each semaphore is a tiny mutex protecting only a counter. So then you face an abstraction inversion right away: to protect anything else, you're using a tiny mutex which protects a counter, plus that counter, as a bigger mutex.

I currently work in a codebase which carries its won semaphore, which is used a lot. The implementation is a POSIX mutex, condition variable and counter! Ouch, that hurts. It's more regressive than a tax that takes money from single moms to give a corporation a break.

Goto?

Dangerous?

Proven to be?

The time has shown that anti goto cult was huge overreaction that gained size due to decades long brain washing by academics on inexperienced programming practicioners (students)

Goto in newer languages is not bad and exceptions which arent as criticized are way more powerful in goto-like sense

Original gotos from that infamous paper were more powerful

> Goto in newer languages is not bad

can you clarify that please.

> and exceptions which arent as criticized are way more powerful in goto-like sense

They are less general therefore less powerful, and by that, less capable of being abused.

Goto in e.g c# doesnt allow you to jump wherever you want

Youre limited by scope, and since we do not write imperative code nowadays everywhere then it is enough to make significant difference

Neither did goto in Pascal. Exceptions are further constrained. You can't do

10: goto 10

With exceptions.

> since we do not write imperative code nowadays

Who's 'we'? I certainly do when appropriate.

In fact you can. In Common Lisp, (go ...) is a dynamic control transfer that performs unwinding and can jump out of a lambda. This is similar to what blub languages call exception handling.

  (tagbody
  10 
    (format t "label 10~%")
    (unwind-protect
      (funcall (lambda () (go 10)))
      (format t "unwinding!~%")))

Output:

  label 10
  unwinding!
  label 10
  unwinding!
  ...

How it works is that (go 10) identifies the surrounding tagbody as an exit point for the exception-like dynamic control transfer. That (go 10) is occurring in a sub-form of tagbody. That entire sub-form is abandoned, with unwinding, and then tagbody catches that control transfer, like an exception handler. tagbody then switches control to the desired label. Effectively, the exception-like control transfer is accompanied by a piece of datum: the label.

tagbody requires lexical visiblity between the go and tagbody; though the label bindings and the control transfer are dynamic, they have to be physically enclosed. That allows compilers to optimize tagbody more. A Common lisp compiler doesn't have to suspect that function (foo) can branch to the label bar in (tagbody (foo) bar) and can conclude that the label is unused, and the tagbody can be entirely optimized away. However, cross-function go does work, as the lambda shows in my example.

is this something to do with call/cc? (which I never understood)

Ehhhhh.

The lowest level of synchronization is atomics + barriers. Semaphores are pretty high level IMO anyway. But not high enough level to be easier to use.

I'd say semaphores are more like the linked list of synchronization. Useful in some circumstances, way more popular 30 years ago and less popular today, still have plenty of legit uses but newer structures (Go's channels, pipes, eventfd, condition variables) have eaten away at the niche it carved out.

You can probably write all your multi threaded code in semaphores alone, proving their versatility. But it won't be the fastest or easiest to understand.

I never understood why semaphore was called a primitive until I've read the original paper. Dijkstra called semaphore a primitive because the controlling part was a mere integer. A Boolean would be even more primitive but probably insufficient. But since a semaphore also has a queue of waiting processes it is of course a rather complex system.

If you have that complex scheduling mechanism with queues and all, about the dumbest thing you can do is build a semaphore with it ... and then use the semaphore to build other primitives.

Why? To me semaphores are the thing you can use to implement a counting producer/consumer thing, a mutex, a critical section, a flag for an interrupt handler.

Are you referring specifically to a counting semaphore as opposed to the other things?

GOTOs are the thing you can use to implement a conditional, a loop, an exception handler.

I see, so the argument is someone should use semaphores to implement higher-level abstractions that are easier to use? That would make some sense.

With a mutex, counter and condition variable you can trivially implement a semaphore and be sure that it's correct at a glance.

Implementing a mutex and condition variable with semaphores is an exercise in Rube Goldberg mousetrap construction.

Semaphores aren't go to because they are lower level building blocks; only in the sense that it's hard to convince yourself that a semaphore-based program is correct.

The premise in this article is false. Linux was never heavily based on semaphores. The main synchronization workhorse in Linux are spinlocks, and the wait queue mechanism: and always have been. Well, spinlocks since SMP was introduced in 1.3; before that, interrupt disabling and enabling.

Wait queues are a close cousin of condition variables.

I've always hated how the operations on semaphores are named, guess I'm too English language oriented.

What I learned many years ago was the dog analogy: to claim a semaphore, P on it.

Does anyone know what the use cases for counting (as opposed to binary) semaphores are in the kernel?

There’s one answer in the article itself:

"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."

I still reach for semaphores (and mutexs) given how simple it is to check an atomic counter. In addition to the linked article (https://lwn.net/Articles/844224/), are their other good articles on moving to more performant locking or coordination mechanisms?

Reply on news.ycombinator.com