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

81–90 of 112 posts

Re: Linus Torvalds on semaphores (1999)

#81

Post by AnimalMuppet »

PinguTS wrote: post #74

Nice 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…

You're blaming Linus for not building something that can synchronize with another processor that isn't running Linux? That seems like it is well outside the scope of Linux's intent. (Linux will get you synchronization if both processors are running Linux as one image, but a processor running no OS? Why do you expect the Linux processor to be able to synchronize with that? I'd expect you to have to implement your own synchronization there, since the other processor is completely outside of Linux's control.)

Re: Linus Torvalds on semaphores (1999)

#82

Post by AnimalMuppet »

andrewstuart2 wrote: post #55
outworlder wrote: post #41

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

Dijkstra was Dutch and lived in the Netherlands, where drug policies are either nonexistent or loosely enforced. So perhaps it's less offensive than it seems on the surface.

And Linus, who grew up much closer to the Netherlands than many of us, was probably aware of that. (I had forgotten it until you pointed it out.)

Re: Linus Torvalds on semaphores (1999)

#83

Post by kragen »

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…

I think the UNIVAC implementation of P and V that you meant to link to is in http://www.fourmilab.ch/documents/univac/fang/hsource/schpro....

Re: Linus Torvalds on semaphores (1999)

#84

Post by kragen »

exDM69 wrote: post #30
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?

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

You can implement message passing, STM, BSP, data parallelism, etc., on top of spinlocks, or on top of other implementations of mutexes such as condition variables, or on top of semaphores; but you can also implement them on top of primitives like compare-and-swap, which is arguably even harder to use correctly.

Re: Linus Torvalds on semaphores (1999)

#85

Post by couchand »

mtts wrote: post #80
roel_v wrote: post #12

Earlier quoted context omitted.

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.

That anecdote is amusing, but it seems unlikely things worked exactly like that. They are near each other in the center of town, but the stadium and the university are a kilometer apart and separated by an elevated railway. At the time EWD35 was written (prior to 1963) the stadium had just installed 40 meter lights, so while it's possible the initials were written on the back of these, it seems more likely that this is a fanciful urban legend. Do you have any more information?

Re: Linus Torvalds on semaphores (1999)

#86

Post by tonysuper »

xxs wrote: post #76
fpgeek wrote: post #75

Earlier quoted context omitted.

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

goto is perfectly acceptable in C code. The most common use case is for cleaning up after errors before returning, although they're also used to break out of nested loops cleanly.

goto is harmful when used improperly but fine everywhere else.

Re: Linus Torvalds on semaphores (1999)

#87

Post by caretcaret »

PinguTS wrote: post #74

Nice 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…

You should realize that the post was written in 1999.

Re: Linus Torvalds on semaphores (1999)

#88

Post by xxs »

tonysuper wrote: post #86
xxs wrote: post #76

Earlier quoted context omitted.

You will be surprised at the goto use in the linux kernel...

goto is perfectly acceptable in C code. The most common use case is for cleaning up after errors before returning, although they're also used to break out of nested loops cleanly. goto is harmful when used improperly but fine everywhere else.

I didn't mean it's a bad thing, it was a reply to some blanket statement.

Re: Linus Torvalds on semaphores (1999)

#89

Post by xxs »

pkhagah wrote: post #66
xxs wrote: post #37

Earlier quoted context omitted.

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

STM doesn't buy you much compared to locks - the transaction boundaries are the harder part (database or otherwise).

Re: Linus Torvalds on semaphores (1999)

#90

Post by xxs »

AnimalMuppet wrote: post #82
andrewstuart2 wrote: post #55

Earlier quoted context omitted.

Dijkstra was Dutch and lived in the Netherlands, where drug policies are either nonexistent or loosely enforced. So perhaps it's less offensive than it seems on the surface.

And Linus, who grew up much closer to the Netherlands than many of us, was probably aware of that. (I had forgotten it until you pointed it out.)

Actually, Linus is from Helsinki that's not exactly close to The Netherlands. There is no intrinsic connection between Finland and The Netherlands. Although the drug laws are still famous all over.
Post reply on HN