Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linus Torvalds on semaphores (1999)

yarchive.net

Post reply on HN
Print view View original

61–70 of 112 posts

Re: Linus Torvalds on semaphores (1999)

#61

Post by learnstats2 »

viraptor wrote: post #53
learnstats2 wrote: post #44

Earlier quoted context omitted.

> However, the point Linus was making (in a humorous way) was that like most computer scientists / mathematicians, Dijkstra was overly fond of obscure, single-letter names, which nobody ever intuitively understands. If he was making this point, I find it ironic, considering that the purpose of the post is to explain the distinction between two obscure, poorly-named technical words, which nobody ever intuitively under…

Hi, I'm nobody. You use spinlock to spin in place until you can get the lock. You wait at semaphores. Seems very intuitive to me.

semaphore

(ˈsɛməˌfɔː) n 1. (Telecommunications) an apparatus for conveying information by means of visual signals, as with movable arms or railway signals, flags, etc 2. (Telecommunications) a system of signalling by holding a flag in each hand and moving the arms to designated positions to denote each letter of the alphabet vb 3. (Telecommunications) to signal (information) by means of semaphore

which definition fits your understanding that you 'wait'? It's not a good name.

Re: Linus Torvalds on semaphores (1999)

#62

Post by kyberias »

GFK_of_xmaspast wrote: post #48
ANTSANTS wrote: post #46

Earlier quoted context omitted.

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

What do you think an appropriate response is?

The appropriate response is to immediately start thinking why you need to figure out a response to any low-quality joke people make. Maybe, just maybe, there is absolutely no need to make any response whatever. Think about it.

Re: Linus Torvalds on semaphores (1999)

#63

Post by leoc »

roel_v wrote: post #12
Animats wrote: post #10

Here'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…

IIRC the analogy is to the positions of a stop/go safety flag (or an actual railway semaphore https://en.wikipedia.org/wiki/Railway_semaphore_signal !) meant to ensure that only one train is in a railway tunnel at a time. A Dutch-speaker with EWD35 http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD35.PDF should be able to confirm this.

Re: Linus Torvalds on semaphores (1999)

#64

Post by viraptor »

learnstats2 wrote: post #61
viraptor wrote: post #53

Earlier quoted context omitted.

Hi, I'm nobody. You use spinlock to spin in place until you can get the lock. You wait at semaphores. Seems very intuitive to me.

semaphore (ˈsɛməˌfɔː) n 1. (Telecommunications) an apparatus for conveying information by means of visual signals, as with movable arms or railway signals, flags, etc 2. (Telecommunications) a system of signalling by holding a flag in each hand and moving the arms to designated positions to denote each letter of the alphabet vb 3. (Telecommunications) to signal (information) by means of semaphore which definition fit…

There are more meanings for semaphore:

https://en.wikipedia.org/wiki/Railway_semaphore_signal

Edit: Ok, actually that could be within your first meaning. But the practical result for railway semaphores is that one of their uses is to stop trains from entering a blocked segment.

Re: Linus Torvalds on semaphores (1999)

#65

Post by couchand »

viraptor wrote: post #64
learnstats2 wrote: post #61

Earlier quoted context omitted.

semaphore (ˈsɛməˌfɔː) n 1. (Telecommunications) an apparatus for conveying information by means of visual signals, as with movable arms or railway signals, flags, etc 2. (Telecommunications) a system of signalling by holding a flag in each hand and moving the arms to designated positions to denote each letter of the alphabet vb 3. (Telecommunications) to signal (information) by means of semaphore which definition fit…

There are more meanings for semaphore: https://en.wikipedia.org/wiki/Railway_semaphore_signal Edit: Ok, actually that could be within your first meaning. But the practical result for railway semaphores is that one of their uses is to stop trains from entering a blocked segment.

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 to the CS concept.

Re: Linus Torvalds on semaphores (1999)

#66

Post by pkhagah »

xxs wrote: post #37
amelius wrote: post #23

Earlier 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?

STM and message parsing do require the low level primitives: CAS (CompareAndSet/Swap), LL/SC (Load linked/store conditional). Morealso STM doesn't solve the transactional problem that you face with using locks (mutex). Overall STM is just a fancy thing to have but hardly solves the big problem of transaction boundaries. Message passing is easier to reason about due to global ordering but then you need some FIFO queue…

STM with database style transactions like in clojure?

http://clojure.org/refs

Re: Linus Torvalds on semaphores (1999)

#68

Post by jerf »

sz4kerto wrote: post #24
amelius wrote: post #23

Earlier 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?

Message passing doesn't help either. What many programmers don't realize that synchronization problems (deadlocks) are _not_ the consequence of using mutexes or other primitives per se. They're the result of synchronization itself. Message passing can be asynchronous, but on some level, the system might have to synchronize certain operations. If you implement a financial system, you'll certainly have to synchronize s…

The way I like to put it is that using a decent concurrency mechanism like message passing or STM or even just what Go does (enforced by community standards rather than actual limitations) takes concurrent programming from an exponential-complexity problem to a polynomial-complexity problem. It's still hard, it'll never not be hard, but it doesn't have to be the insanely, mind-bendingly broken hard that it was in the 90s. The more you can avoid sharing and the more you can operate in your own little world that communicates with other worlds via immutable messages, the happier you will be, and if you occasionally have to dip a bit into true sharing, it's still easier to manage in a saner world than when you try to share everything, all the time.

There's nothing that "solves" the problem, but there are "things that will summon forth C'thulu" and "things that are merely difficult".

Re: Linus Torvalds on semaphores (1999)

#69

Post by herf »

The "benchmarks game" has a thread ring benchmark which can compare conditions/mutexes/semaphores, because for some applications they're interchangeable:

4-thread x64:

mutex (480s): http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

sem_wait (476s): http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

cond_wait (271s - runs single-threaded?) http://benchmarksgame.alioth.debian.org/u64q/program.php?tes...

1-thread x86:

mutex (136s): http://benchmarksgame.alioth.debian.org/u32/program.php?test...

sem_wait (131s): http://benchmarksgame.alioth.debian.org/u32/program.php?test...

cond_wait (156s): http://benchmarksgame.alioth.debian.org/u32/program.php?test...

Re: Linus Torvalds on semaphores (1999)

#70

Post by viraptor »

couchand wrote: post #65
viraptor wrote: post #64

Earlier quoted context omitted.

There are more meanings for semaphore: https://en.wikipedia.org/wiki/Railway_semaphore_signal Edit: Ok, actually that could be within your first meaning. But the practical result for railway semaphores is that one of their uses is to stop trains from entering a blocked segment.

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.cs.cmu.edu/~410-f03/lectures/L09_Synch.txt

https://www.cs.ucsb.edu/~rich/class/cs170/notes/Semaphores/

Documentations:

https://doc.micrium.com/display/osiiidoc/Semaphores+in+uC-OS...

Articles:

http://realtimepartner.com/articles/semaphores.html

http://lycog.com/distributed-systems/semaphore-mutual-exclus...

If we're going to compare it to any real life object, it may as well be a semaphore. Anything else will have the same issues. Traffic lights: what about yellow / blinking. Stop signs: why do they sometimes stop, sometimes not. etc.

Is there any single word/phrase concept which you'd rather use instead? Is it much more convenient and clear than a semaphore?

Post reply on HN