![]() I'm pretty sure Linus was joking and he did understand what semaphores are used for. Linus' note indicates that in 1999 he didn't know this. I've seen this several times in production code. It is important to understand the theory and know how to do the proofs but it is equally important to apply this into practice.Įvery time I see someone "implement" a semaphore using a pthread mutex and condition variable, I cry a little. 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. 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. Incrementing and decrementing numeric counters is a very clumsy way to maintain a state of any kind. 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". 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.īut when writing practical multithreaded programs, mutexes and condition variables are a lot more practical. Semaphores are a neat theoretical concept but not a very good practical parallel programming paradigm. Here's an important distinction to make: this stuff was well understood in theory, but the practice is a bit different. Much of it was forgotten outside the mainframe world, because threads and multiprocessors didn't make it to microprocessors for several more decades. > This stuff was all well understood four decades ago. They're quite useful, and I've been using them in concurrent programs for many years. It's been amusing to me to see bounded buffers resurface in Go. The DOS/Windows world didn't get them until Windows NT, circa 1993. Early UNIX didn't have threads, and even after it got threads, it took years before the locking primitives settled down. UNIX, for a long time, had very primitive synchronization primitives. This stuff was all well understood four decades ago. (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.) ![]() GET does a P on "queue empty", takes off an item, and does a V on "queue full". PUT does a P on "queue full", puts on an item, and does a V on "queue empty". There's one semaphore for "queue full" and one for "queue empty". Note how simple they are if you have P and V. ![]() Bounded buffers are what Go calls "channels". Along with P and V is the code for bounded buffers, with the operations "PUT" and "GET". ![]() Here is a implementation of P and V, the original counted semaphore primitives, from 1972. Here's Dijkstra's original paper on P and V (in Dutch), from about 1963. ![]()
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |