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

101–110 of 112 posts

Re: Linus Torvalds on semaphores (1999)

#101

Post by tcheard »

couchand wrote: post #79
viraptor wrote: post #70

Earlier quoted context omitted.

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

Since when does a name have to provide sufficient context to distinguish the concept from other similar, yet distinct, ideas?

For example, tree data structures. There are:

2–3 tree, 2–3–4 tree, AA tree, (a,b)-tree, AVL tree, B-tree, B+ tree, B*-tree, Bx-tree, Binary search tree, Optimal binary search tree, Dancing tree, HTree, Interval tree, Order statistic tree, Red–black tree, Scapegoat tree, Splay tree, T-tree, Treap, UB-tree

In many of those the name doesn't provide much context at all to distinguish the concept from another one.

Names of things, at least in CS, are rarely ever named in a way to provide sufficient context of their meaning, without having some level of background context.

That is what the description of the concept is for, not the name. A name is too short to provide this. Usually the name is at the discretion of the original author (aka Dijkstra in this case). If you are trying to determine the complete concept of something, or you are trying to distinguish the concept from other similar ideas, only from the name, you are doing it wrong. Go read the documentation about the concept for that.

Re: Linus Torvalds on semaphores (1999)

#102

Post by Animats »

kragen wrote: post #99
Animats wrote: post #93

Earlier quoted context omitted.

Those are the assembler macros ("procs" in UNIVAC terminology) for calling the functions previously linked. (UNIVAC assemblers were very powerful. Arbitrary computation could be done at assembly time. If you needed some precomputed table, that was the way to do it.)

The previous link just takes me to the FANG homepage frameset, which doesn't have any functions visible on it to me. This is a common problem with linking to framesets. Or is it some kind of problem in my browser, and other people see functions in UNIVAC assembly when they follow that link? (FWIW, I think it's fairly normal for macro assemblers to be Turing-complete, although some of them carry it off more gracefully…

Right, frames. Here's the specific P and V source.

http://www.fourmilab.ch/documents/univac/fang/hsource/schedu...

Re: Linus Torvalds on semaphores (1999)

#103

Post by Animats »

exDM69 wrote: post #39
bad_user wrote: post #34

Earlier quoted context omitted.

Semaphores are useful for rate limiting - for example say you have a connections pool with an upper bound, so naturally the number of threads that can acquire a connection and do things with it is limited by the size of that connections pool. And you don't necessarily need a mutex or to actually put the thread to sleep. Semaphores are also relevant when speaking of asynchronous stuff (e.g. Futures), in which case you…

While I do not disagree with you, I still do think that even these cases mutexes and conditions are more practical. Take the "rate limiting" example you mention (also one of Linus' examples in the OP). You initialize a semaphore to `max_concurrent_connections` and call `semaphore_down()` when you enter the connection handling sequence and `semaphore_up()` when you're done. Now this works fine and is an idiomatic exam…

Termination in queued systems is moderately hard. You have to drain out the queues. In Go, you can close a channel at the write end and wait for the reader to reach EOF. But if the reader is stuck waiting for something, there's a problem. Especially if it's waiting to write another channel. If you close a channel written by another task, that task will panic when it writes to the closed channel. You can't close channels to force shutdown in Go unless a panic is acceptable.

This is a classic problem with bounded buffers, re-invented four decades later.

Re: Linus Torvalds on semaphores (1999)

#104

Post by twic »

icebraining wrote: post #31
sz4kerto wrote: post #25

Earlier quoted context omitted.

There's nothing vintage about them. Understanding these is crucial to understand how and why modern concurrency tools work. As I noted above in another comment, the issues that need mutexes or semaphores have never went away, only you might not realize that they're there. And please, don't come up with async/await, callback/continuation, node.js' async stuff. They are not a replacement for mutual exclusion, etc.

Vintage doesn't mean obsolete.

Vintage means "from a particularly good year, the like of which we have not seen for some time". Seems about right for an invention of EWD's.

Re: Linus Torvalds on semaphores (1999)

#106

Post by couchand »

tcheard wrote: post #101
couchand wrote: post #79

Earlier quoted context omitted.

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

Since when does a name have to provide sufficient context to distinguish the concept from other similar, yet distinct, ideas? For example, tree data structures. There are: 2–3 tree, 2–3–4 tree, AA tree, (a,b)-tree, AVL tree, B-tree, B+ tree, B*-tree, Bx-tree, Binary search tree, Optimal binary search tree, Dancing tree, HTree, Interval tree, Order statistic tree, Red–black tree, Scapegoat tree, Splay tree, T-tree, Tr…

I'm not saying a name has to provide sufficient context. I'm saying a name that provides that context is superior to one that does not.

A red-black tree is named so because those were the colors their laser printer supplied. This is (much like semaphore) a historical accident. Yet, just by the name red-black, you do indeed have enough context to distinguish it from a plain old binary search tree. The defining feature is that you color every node either red or black, thus red-black in the name.

Likewise with splay tree: the defining function is the splay operation, which the name is a vivid reminder of.

Splay tree and red-black tree are Good Names (TM). B tree, B+ tree, B* tree, Bx tree are Bad Names (TM).

Re: Linus Torvalds on semaphores (1999)

#107

Post by kragen »

Animats wrote: post #102
kragen wrote: post #99

Earlier quoted context omitted.

The previous link just takes me to the FANG homepage frameset, which doesn't have any functions visible on it to me. This is a common problem with linking to framesets. Or is it some kind of problem in my browser, and other people see functions in UNIVAC assembly when they follow that link? (FWIW, I think it's fairly normal for macro assemblers to be Turing-complete, although some of them carry it off more gracefully…

Right, frames. Here's the specific P and V source. http://www.fourmilab.ch/documents/univac/fang/hsource/schedu...

Thank you!

Re: Linus Torvalds on semaphores (1999)

#108

Post by kragen »

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…

No, you can build STM on top of mutexes, too; you don't need CAS and LL/SC as low-level primitives. In fact, IIRC, Intel CPUs use a mutex in their cache coherency protocol to implement CAS and LL/SC.

Re: Linus Torvalds on semaphores (1999)

#109

Post by theoh »

leoc wrote: post #63
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…

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.

I think that much is clear, (the railway analogy), but the idea that tunnels are the main use case for semaphore signals is daft. All railways use variations on the principle of block signalling, where only one train is allowed on any section of track, even if successive trains are travelling in the same direction. This ensures safe separation of trains, which take some distance to stop.

Re: Linus Torvalds on semaphores (1999)

#110

Post by darylteo »

Wow I remember some of this class from my OS course 10 years after this was written.

We were just told about mutexes, but I never knew that it stood for Mutual Exclusion. (I did correctly intuit that a mutex was simply a specific use case of semaphore though so I'm happy and managed to pass the course in the end :D)

Post reply on HN