3 ms·
Though invented by Dijkstra, semaphores are ironically the GO TO of synchronization. "The unbridled use of the go to statement has an immediate consequence tha
by kazinator 4y ago
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
- f1shy 4y agoI would say the are the assembler of concurrency. You should use higher level abstractions, but sometimes, it has its place.
- czscout 4y agoI 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.
- withinboredom 4y agogoto 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.
- kazinator 4y agoSemaphores 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.
- withinboredom 4y agoSounds more like an if-statement than a goto. I catch your meaning though.
- kazinator 4y agoActually 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.
- hardware2win 4y agoGoto? 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
- _a_a_a_ 4y ago> 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.
- hardware2win 4y agoGoto 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
- _a_a_a_ 4y agoNeither 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.
- kazinator 4y agoIn 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.
- dragontamer 4y agoEhhhhh. 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.
- Mikhail_Edoshin 4y agoI 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.
- kazinator 4y agoIf 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.
- zwieback 4y agoWhy? 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?
- yccs27 4y agoGOTOs are the thing you can use to implement a conditional, a loop, an exception handler.
- zwieback 4y agoI see, so the argument is someone should use semaphores to implement higher-level abstractions that are easier to use? That would make some sense.
- kazinator 4y agoWith 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.