Coming from embedded systems and MCU RTOS development, mutexes and semaphores are the name of the game.
Linus Torvalds on semaphores (1999)
71–80 of 112 posts
Re: Linus Torvalds on semaphores (1999)
#72nice
Re: Linus Torvalds on semaphores (1999)
#73Semaphore and spinlock sure are different. People rarely use spinlock in user mode programs since there are better synchronizing mechanisms in user mode than busy waiting with spinlock. However, in kernel mode program spinlock is invaluable since it's the only synchronizing mechanism that works in any interrupt level.
Re: Linus Torvalds on semaphores (1999)
#74Nice read, but still some misconceptions and misunderstandings.
If I am in a multiprocessor design, where each processor runs completely independent from each other and there is no central organizational unit like a central OS, like in many embedded designs, there is no such thing as a spinlock. A semaphore is also not used for sending processes to sleep.
Linus explanation makes sense, speaking only about a single OS, which may is comprised of multiple processors. But makes no sense at all for real multi-processor designs. I don't blame him for his narrow view, more his professors that he never experienced real embedded design.
I have worked in the past with multi-processors designs, where one processor was using one OS, like OS9, and the other processor had no OS at all running. Both processors where exchanging data via a dual ported RAM. So basically both processes where competing for the same resource. But even than, using a semaphore does not prevent race-conditions. Even then it is very tricky to use them. Because dual ported RAM allowed real concurrent access to the same resource.
In summary, the semaphore definition is the more broad definition where 2 (or more) processes are competing for a single resource. The naming convention within Linux is more specific for this requirements. The "invented" spinlock is just a renamed version for a fast semaphore, AFAIK. Even a mutex is just a special case of a semaphore.
Re: Linus Torvalds on semaphores (1999)
#75Earlier quoted context omitted.
Well, P and V are considered harmful (pun intended). Systems using these operations are in general not "composable". In other words, it is usually not possible to compose two software systems using semaphores and/or mutexes, without rewriting these systems somehow. Alternatives exist. For example: message passing, and STM (software transactional memory). Anybody know of other alternatives?
> Alternatives exist. For example: message passing, and STM (software transactional memory). Anybody know of other alternatives? It should be noted that spinlocks, mutexes and conditions (and semaphores) are building blocks that are necessary to implement message passing, software transactional memory and other non-trivial parallel programming constructs. (at least until we have practical hardware transactional memor…
If you're talking about building blocks, goto is also a necessary evil...
Re: Linus Torvalds on semaphores (1999)
#76Earlier quoted context omitted.
> Alternatives exist. For example: message passing, and STM (software transactional memory). Anybody know of other alternatives? It should be noted that spinlocks, mutexes and conditions (and semaphores) are building blocks that are necessary to implement message passing, software transactional memory and other non-trivial parallel programming constructs. (at least until we have practical hardware transactional memor…
If you're talking about building blocks, goto is also a necessary evil...
You will be surprised at the goto use in the linux kernel...
Re: Linus Torvalds on semaphores (1999)
#77Earlier quoted context omitted.
> Alternatives exist. For example: message passing, and STM (software transactional memory). Anybody know of other alternatives? It should be noted that spinlocks, mutexes and conditions (and semaphores) are building blocks that are necessary to implement message passing, software transactional memory and other non-trivial parallel programming constructs. (at least until we have practical hardware transactional memor…
If you're talking about building blocks, goto is also a necessary evil...
Oh, nice turnaround!
That one was funnier then the orignal pun. Nicely done. :D
Re: Linus Torvalds on semaphores (1999)
#78Earlier quoted context omitted.
> "Dijkstra was probably a bit heavy on drugs or something (I think the official explanation is that P and V are the first letters in some Dutch words, but I personally find the drug overdose story much more believable)." I personally have made remarks that were WAY more potentially offensive than that, verbally, with friends. But, accusing Dijkstra of being a drug user, on the Linux kernel mailing list, from a @tran…
Technically, you're right. Today, any junior employee that made a joke like that would be crucified and practically blacklisted from the industry. What you should be thinking, however, is not "why does Linus get away with saying things like that?" but rather "why do I consider it normal for someone's livelihood to be permanently destroyed over a stupid joke?"
Gosh, no kidding.
Re: Linus Torvalds on semaphores (1999)
#79Earlier quoted context omitted.
It's actually quite reasonable to complain about the use of the term semaphore here. As you recognize, stopping the train is only one of their uses . Railway signals can convey many different types of information about the state of the track, not just free/blocked. And moreover, a semaphore is just a specific type of railway signal, one with a pivoting arm. It's very hard to see how a pivoting arm is at all related t…
Not sure if it's reasonable to complain really... I mean, it's not covering everything semaphores do, but the basics are there - gives information and stops two trains/threads colliding. References to trains when talking about cs semaphores are all over the place. Universities: http://ro.uow.edu.au/cgi/viewcontent.cgi?article=1027&contex... http://courses.teresco.org/cs432_f02/lectures/07-synch/07-sy... https://www.c…
Is it much more convenient and clear than a semaphore?
My point was simply that the only reason "semaphore" is clear is that you've already heard or read those lectures talking about it. There's nothing about the railroad meaning of the term that would imply the computer science meaning. A counter that can never go below zero is entirely unrelated to a pivoting arm. Once you know the connection it can serve as something of a reminder, but that's different from having an intuitive understanding in the first place.
EDIT: Getting from RR semaphore to CS semaphore requires several leaps of intuition. On the railroad side you need to recognize that it is a signal that's important, and it's irrelevant whether that signal is implemented as a semaphore, an electric signal, or even a flagman. On the computer science side you need to know the difference between a semaphore and the many other types of mutual exclusion mechanisms.
So in that sense "semaphore" is poorly named: it provides insufficient context to distinguish the concept from other similar, yet distinct, ideas.
Re: Linus Torvalds on semaphores (1999)
#80Here's Dijkstra's original paper on P and V (in Dutch), from about 1963. http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EW... Here is a implementation of P and V, the original counted semaphore primitives, from 1972. http://www.fourmilab.ch/documents/univac/fang/ This is UNIVAC 1108 assembly code. Along with P and V is the code for bounded buffers, with the operations "PUT" and "GET". Bounded buffers are w…
For those wondering, P comes from 'Passering', roughly translated 'pass' (as a noun), and V from 'Vrijgave' ('release'). Apparently somehow this terminology comes from train systems but there's not a lot of context on that etymology. As an aside, this paper (it's actually the transcription of a lecture) has some great metaphors that explain problems with concurrence and issues with synchronisation. At the risk of los…
An amusing anecdote I heard about this a few weeks ago: he came up with "P" and "V" when explaining the concept to his students at Eindhoven University. He looked outside the window of the classroom he was teaching in and saw the name of the local soccer club on a nearby stadium which is PSV.