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 losing much of the nuances, he essentially illustrates the synchronisation using the example of a teacher who needs to find a pupil in a class. When pupils are free to choose a seat, she needs to scan all seats when she is looking for a particular pupil; but when at the same time pupils are free to change seats as she's scanning, there is no guarantee that she will ever find the pupil she's looking for as he might run from the back of the class to the front as soon as she's done scanning the front.
This makes more sense to me.
These documents are available from the Dijkstra archive: http://www.cs.utexas.edu/users/EWD/welcome.html
Here's an important distinction to make: this stuff was well understood in theory, but the practice is a bit different.
Semaphores are a neat theoretical concept but not a very good practical parallel programming paradigm. Semaphores are easy to reason about when writing proofs by induction that a parallel programming algorithm is working correctly, which is why they are still at the core of parallel programming education.
But when writing practical multithreaded programs, mutexes and condition variables are a lot more practical. Typically each mutex is coupled with one or more condition variables to wait/signal for conditions such as "queue not full" and "queue not empty". Incrementing and decrementing numeric counters is a very clumsy way to maintain a state of any kind. Implementing a semaphore requires grabbing a spinlock and doing this several times is unnecessary when you could just grab one mutex, check for the appropriate condition(s) and then wait/signal on the correct condition.
It is rather unfortunate that parallel programming is still primarily being taught in the theoretical manner (at least I was) using primarily semaphores, leaving too little emphasis on the practical implementation. It is important to understand the theory and know how to do the proofs but it is equally important to apply this into practice.
Every time I see someone "implement" a semaphore using a pthread mutex and condition variable, I cry a little. I've seen this several times in production code.
> It's very simple. That's the real use case for P and V. Linus' note indicates that in 1999 he didn't know this.
I'm pretty sure Linus was joking and he did understand what semaphores are used for. Every computer science curriculum has a course on parallel programming with bounded buffer producer consumer/problems, readers/writers problems and other "toy problems" solved using semaphores, followed by proof by induction that the solution is correct. And Linus did, eventually, finish a degree on computer science.
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 can easily do CAS operations on an atomic reference holding an immutable queue of promises. Slightly inefficient under high contention, but non-blocking and gets the job done.
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 example of using semaphores.
However, in the real world, this kind of situation rarely happens in isolation. What happens if you need to terminate the application for whatever reason, and do so cleanly? If you're under contention, you might have a dozen threads waiting for the semaphore go up and your only option is to kill them. Or implement some logic for this case (using another semaphore) to make sure the application hasn't been terminated while we were waiting for the rate limiting semaphore.
You can implement this cleanly using mutexes and conditions, by creating a "killable semaphore" synchronization primitive. While this is similar to a semaphore as an idea, it's very difficult to implement it if semaphores are the only primitive you have. Additionally, you probably want some kind of timeout if the queue is full.
So in practice you need something like:
while(true) {
socket = accept();
int status = rate_limiting_enter(my_rate_limiter);
// NOTE: someone else may call rate_limiting_terminate()
if(status == OK) {
service(socket);
rate_limiting_leave(my_rate_limiter);
} else if(status == TIMEOUT) {
send_busy(socket);
} else if(status == KILLED) {
send_terminate(socket);
break;
}
close(socket); // this must be called or resources leak
}
Now, while this is theoretically very similar to a semaphore, it has other real world priorities (like timeout and termination) which are very difficult to implement using Dijkstra -style semaphores with only P() and V() operations (and you definitely need more than one semaphore).This has been the case in almost every practical multithreaded programming scenario I've had. The solution could be thought of using semaphores (and I frequently do) but in practice, there's always some real world conditions (timing, contention, errors) that must be met.
It is very trivial to implement semaphore-like synchronization primitives using mutexes and conditions but not vice versa.
Semaphores are very good for textbook examples and a mental model but not so much in practical software.
This is a classic problem with bounded buffers, re-invented four decades later.
Semaphores can be implemented in a way that doesn't require a spinlock in the fast path. Still not as fast as you can make a mutex, but a lot better than the pseudocode given in many classes (which is almost always wrong, too.)
(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.)
(FWIW, I think it's fairly normal for macro assemblers to be Turing-complete, although some of them carry it off more gracefully than others.)
http://www.fourmilab.ch/documents/univac/fang/hsource/schedu...
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 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 stuff even if you're using asychronous message passing to implement it -- you will simply implement synchronicity on the top of an asychronous infrastructure.
And when operations start to depend on each other, then you _have_ to think about potential deadlocks, race conditions, etc.
Basically there isn't anything that solves this for you. STM is somewhat different as the danger is not deadlocks but starvation, etc.
There's nothing that "solves" the problem, but there are "things that will summon forth C'thulu" and "things that are merely difficult".
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 memory).
Spinlocks, mutexes and conditions are a "necessary evil", not "considered harmful".
That one was funnier then the orignal pun. Nicely done. :D
goto is harmful when used improperly but fine everywhere else.
fpgeek wasn't actually making a statement about goto
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 queues that are built upon some kind of mutex or spin lock... or Lamport based one (using for single producer-> single consumer one)... or some variant of Michael & Scott queue, etc.
In the end underneath you have to do the metal, so they cannot be 'considered harmful'.
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 what Go calls "channels". Note how simple they are if you have P and V. That code even works on multiprocessors. There's one semaphore for "queue full" and one for "queue empty". PUT does a P on "queue full", puts on an item, and does a V on "queue empty". GET does a P on "queue empty", takes off an item, and does a V on "queue full". It's very simple. That's the real use case for P and V. Linus' note indicates that in 1999 he didn't know this.
(I didn't write those primitives, but I've used that code, and once ported it to a Pascal compiler I adapted to handle concurrency.)
This stuff was all well understood four decades ago. Much of it was forgotten outside the mainframe world, because threads and multiprocessors didn't make it to microprocessors for several more decades. UNIX, for a long time, had very primitive synchronization primitives. Early UNIX didn't have threads, and even after it got threads, it took years before the locking primitives settled down. The DOS/Windows world didn't get them until Windows NT, circa 1993.
It's been amusing to me to see bounded buffers resurface in Go. They're quite useful, and I've been using them in concurrent programs for many years.