Here's Dijkstra's original paper on P and V (in Dutch), from about 1963.<p><a href="http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD35.html" rel="nofollow">http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EW...</a><p>Here is a implementation of P and V, the original counted semaphore primitives, from 1972.<p><a href="http://www.fourmilab.ch/documents/univac/fang/" rel="nofollow">http://www.fourmilab.ch/documents/univac/fang/</a><p>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.<p>(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.)<p>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.<p>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.
<i>"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><p>Quotes like this are why I always read what Linus has to say, regardless of whether the subject is relevant to my life in the slightest.<p>Edit: Yes people, those Dutch words exist! I get it! I'm sure Linus was well aware of that when he made this remark. 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. Whereas the names "up" and "down" (see the rest of Linus' quote) are far more intuitive. Personally, I would argue that "hold" and "release" convey the intent in a clearer, more abstract way.
Semaphores are basically unused in the kernel these days, abandoned in favor of mutexes. I really recommend reading kernel/locking/mutex.c. You can learn a lot about the details of low-level synchronization, and it's also just a really impressive piece of ruthlessly-optimised code. Tricks like reading the lock's 'owner' field without any sort of synchronization, to decide whether to spin on the lock or to sleep.
it's surprising that Linus answers peacefully and pedagogically ! and thus it's a nice read to refresh the definition of semaphores, spinlocks and mutexes.<p>Maybe you can edit the title and add a little [199] :-)
Link is to a collection of Linus's comments, from between 1999 and 2008, about how to efficiently implement mutex and semaphores in the Linux kernel.<p>Linus is the BDFL of the Linux kernel, and he obviously needs to think about the big picture. And yet in these comments he gets into nitty-gritty assembly language.<p>I love it when a big picture guy also sweats the details.
Nice read, but still some misconceptions and misunderstandings.<p>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.<p>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.<p>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.<p>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.
If you haven't already, follow the 'index' link (to <a href="http://yarchive.net/comp/index.html" rel="nofollow">http://yarchive.net/comp/index.html</a>) and bookmark that. Some very worthwhile reading there.
The possible future improvement that Linus mentions here:<p><pre><code> For example, the per-VM memory management semaphore could very usefully
be a blocking read-write lock, but without heavy thread contention a
mutex semaphore is basically equivalent.
</code></pre>
has actually come to pass: the mm_struct is now protected by struct rw_semaphore mmap_sem.
This is why I <i>LOVE</i> reading what Linus has to say, it's all very practical, and pretty much ignores theory, because he has actual evidence to support his claims.
Ah, semaphores. I recall in my operating systems course we had to implement some simple concurrency patterns using semaphores as an exercise -- for instance synchronize a group of processes so that idle processes gather into groups of N, and when a group is ready, N-1 threads of the group does TaskX(), and 1 thread does TaskY(), and when they're done, they go back to the pool. Then we implemented the same using usual mutexes and condition variables. I encourage everyone to do that, to see how one of the approaches is much more complicated than the other. Linus says that almost all practical uses of semaphores is when they are just used as mutexes, and rightly so -- implementing concurrency patterns based only on semaphores is a total pain.
There's a free book available on the subject of semaphores:<p><i>The Little Book of Semaphores</i>
by Allen Downey<p><a href="http://greenteapress.com/semaphores/" rel="nofollow">http://greenteapress.com/semaphores/</a>
Semaphores make a lot more sense if you know their literal translation of the Spanish word "semaforo", which is a "signal". It's also used in Spanish to describe a traffic light.
Semaphore 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.
Wow I remember some of this class from my OS course 10 years after this was written.<p>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)