News for hackers. Stuff that matters.
Re:Linus Torvalds on semaphores (1999) by amelius on Wednesday December 17, 2014 @05:18AM (#8761788)
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?

Re:Linus Torvalds on semaphores (1999) by sz4kerto on Wednesday December 17, 2014 @05:25AM (#8761798)
Message passing doesn't help either. What many programmers don't realize that synchronization problems (deadlocks) are _not_ the consequence of using mutexes or other primitives per se. They're the result of synchronization itself.

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.

Re:Linus Torvalds on semaphores (1999) by jerf on Wednesday December 17, 2014 @10:08AM (#8762488)
The way I like to put it is that using a decent concurrency mechanism like message passing or STM or even just what Go does (enforced by community standards rather than actual limitations) takes concurrent programming from an exponential-complexity problem to a polynomial-complexity problem. It's still hard, it'll never not be hard, but it doesn't have to be the insanely, mind-bendingly broken hard that it was in the 90s. The more you can avoid sharing and the more you can operate in your own little world that communicates with other worlds via immutable messages, the happier you will be, and if you occasionally have to dip a bit into true sharing, it's still easier to manage in a saner world than when you try to share everything, all the time.

There's nothing that "solves" the problem, but there are "things that will summon forth C'thulu" and "things that are merely difficult".

Re:Linus Torvalds on semaphores (1999) by exDM69 on Wednesday December 17, 2014 @05:48AM (#8761846)
> 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 memory).

Spinlocks, mutexes and conditions are a "necessary evil", not "considered harmful".

Re:Linus Torvalds on semaphores (1999) by kragen on Wednesday December 17, 2014 @01:09PM (#8763410)
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) by fpgeek on Wednesday December 17, 2014 @11:39AM (#8762885)
If you're talking about building blocks, goto is also a necessary evil...
Re:Linus Torvalds on semaphores (1999) by nocman on Wednesday December 17, 2014 @11:57AM (#8762997)
Oh, nice turnaround!

That one was funnier then the orignal pun. Nicely done. :D

Re:Linus Torvalds on semaphores (1999) by xxs on Wednesday December 17, 2014 @11:49AM (#8762947)
You will be surprised at the goto use in the linux kernel...
Re:Linus Torvalds on semaphores (1999) by tonysuper on Wednesday December 17, 2014 @01:21PM (#8763469)
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) by xxs on Wednesday December 17, 2014 @01:44PM (#8763589)
I didn't mean it's a bad thing, it was a reply to some blanket statement.
Re:Linus Torvalds on semaphores (1999) by Dylan16807 on Wednesday December 17, 2014 @02:16PM (#8763756)
I think you missed that fpgeek was turning exDM69's comment around on itself to put goto and spinlock into the same category.

fpgeek wasn't actually making a statement about goto

Re:Linus Torvalds on semaphores (1999) by xxs on Wednesday December 17, 2014 @06:54AM (#8761961)
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 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'.

Re:Linus Torvalds on semaphores (1999) by kragen on Wednesday December 17, 2014 @05:47PM (#8764855)
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) by pkhagah on Wednesday December 17, 2014 @09:49AM (#8762419)
STM with database style transactions like in clojure?

http://clojure.org/refs

Re:Linus Torvalds on semaphores (1999) by xxs on Wednesday December 17, 2014 @01:47PM (#8763601)
STM doesn't buy you much compared to locks - the transaction boundaries are the harder part (database or otherwise).