6

In this talk, Rich Hickey introduces Clojure. He gives an Ants demo and talks about his motivations for implementing a Software Transactional Memory (STM) system.

enter image description here

His reasoning for STM is that "locks are hard to reason about".

I took that to mean that the deadlock situation, where two threads are trying to update the same item and they hold resources that the other thread needs.
So to be atomic one thread has to roll back and retry and the other has to roll forward.

To make this work in an Object Oriented Language, you have to either use an STM framework or roll it yourself by hand.

That's my understanding, but I suspect I've only covered one problem case and I would imagine there is a more general principle that I'm missing. Perhaps the issue is that locks don't compose or something.

My question is: What is the actual reason that locks (sentinels) in OO are hard to reason about?

closed as primarily opinion-based by gnat, user40980, GlenH7, Dan Pichelman, Ampt Oct 31 '14 at 18:28

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • recommended reading: Discuss this ${blog} – gnat Oct 31 '14 at 11:03
  • 3
    This question starts from a false premise, that locks are difficult to understand. Therefor, the question itself is invalid. It would be like asking "why do you drive a blue car?" when the person's car is red. – user22815 Oct 31 '14 at 13:48
  • Exactly what @Snowman said. Rich Hickey is notorious for assuming self-serving but false premises that lead to conclusions that make Clojure look good. STM is very difficult to reason about, especially when you get into non-trivial cases like nested transactions. – Mason Wheeler Oct 31 '14 at 18:27
  • I would like to temper what I said previously with a caveat. Everything in computer science has a learning curve. But I would expect that any expert in the field would have an easy time understanding locking, even if they are not extremely experienced in all the edge cases involved in concurrency. – user22815 Oct 31 '14 at 18:40
  • @Snowman Where shall I meet these programmers who find lock based concurrency easy to understand? – Yakk Nov 7 '14 at 18:51
16

It has nothing to do with OO in particular. The problems are problems with the "explicit locking" paradigm as an approach to concurrency, regardless of other paradigms used in other parts of the problem.

I haven't watched that two hour talk, so I won't comment on Hickey's reasoning. Here are the criticisms of locks I hear most commonly, summarized:

  • Locks are not composable. If you have two pieces of code A and B that work correctly (in particular, atomically) on their own, you can't write A; B to perform the two actions together, atomically. At least not without either mucking around with the locks A and B use (which are often private, for good reasons) or introducing yet another lock and introducing it everywhere it needs to be adhered to.

  • Locks, as usually implemented, are not formalized in what they protect and when they must be acquired. If the system is any good, it will be documented, but programmers get no automated assistance in adhering to the rules.

  • Locks are low-level. To properly understand their interactions and what they mean for synchronization, you have to consider all possible ways the concurrent executions might interleaving, and all possible ways code might be reordered. Flow-dependent reasoning is already tricky for a single thread of execution, but concurrency makes the number of paths to consider explode.

Functional programming advocates like to argue that OOP also needs far more synchronization because it uses far more shared mutable state, but this is beside the point here. How much synchronization is needed is orthogonal to how you choose to synchronize.

  • +1 especially for your 3rd point, which I believe is particularly true. There also tends to be a push to keep locks as fine-grained as possible (speaking generally) for performance reasons - very granular locks would prohibit concurrency. – Daniel B Oct 31 '14 at 12:12
12

It's not the locking that is hard to understand. Locks are easy. They work just like the locks in real life. It's the concurrency that's hard to understand.

The only reason locking makes people's head spin is that we only ever use it in concurrent systems. But imagine for a moment that we had a highly concurrent system with no synchronization whatsoever; the system's state would over time change to hilariously invalid configurations. Many of those configurations are just as hard to understand; they make people go "Huh? How on Earth could this ever happen?" The reason is that we are not built to understand the weird mix of simultaneous and and alternating changes that modern time-slicing systems yield. Little else in real life works that way, so our brains have a really hard time with it.

  • 2
    I'm torn. It's true that concurrency (with side effects; pure computations can be made concurrent without observable effects) is hard, but on the other hand, formalisms other than locks do make concurrency easier to deal with than locks, so something is certainly wrong with locks. At the very least, they are not the best abstraction for concurrency/synchronization. – user7043 Oct 31 '14 at 11:45
  • 1
    True. I think the trouble with locks is that they are extremely simple - the proverbial "simplest thing that could possibly work", and in this case that's just not good enough. In contrast, STM is like updating a copy of your web server at your leisure and then atomically throwing a switch to redirect all traffic to it. It works better, but it's undeniably much less simple. – Kilian Foth Oct 31 '14 at 11:52
  • Re "Little else in real life works that way": Actually our brains work that way. – Marc van Leeuwen Oct 31 '14 at 13:31
  • I think the concurrency problem is even deeper than suggested. First, in real world concurrency (not computational), the actors are much more intelligent (debatable), able to recover from perceived / observed problems creatively and more independent. Second, we aren't simulating concurrent execution with context switches between threads, we really are acting concurrently (digressions of 'free will' and 'nature or nurture' aside). Finally, moving from abstract reasoning about concurrent behavior to reasoning about behavior of simulations of concurrent behavior (turing machines) is hard. – Kristian H Oct 31 '14 at 14:12
  • 4
    Not sure how I feel about "little else in real life works that way" since everything that happens in real life is inherently concurrent. In my opinion the real issue is that you can't analyze locking-based code in chunks, much like non-structured, global-based spaghetti code. You can only look at it as a whole, in all its gory low-level detail. The whole is far too big, and too many of the details irrelevant to the problem at hand. – Doval Oct 31 '14 at 14:32
6

I don't have any experience with STM but I'll address the locking part.

Getting single threaded code right is hard. It's pretty telling that the prevalent methodology is to create a large battery of unit tests and hope that if they all pass, nothing is wrong. For code that won't result in loss of life or billions of dollars, that's a reasonable approximation, but the point I'm trying to make is that proving code correct is hard. Harder than most people are willing to put effort into.

Now consider concurrent code using locks. To prove it works, you have to prove that you've manually synchronized the threads properly for every possible interleaving/scheduling. That's a monumental task. And if you screw up, because the code is non-deterministic, the buggy behavior is non-deterministic too! It's not unlike manual memory management, except that tracking resources in single-threaded code is easier (yet still too hard to get right).

Even worse code that uses locks isn't composable. Suppose you have two collections, and you make every operation on them thread-safe. Now suppose you want to remove an item from one collection and add it to the other. Just because removing the element is thread-safe and adding the element is thread-safe it doesn't mean the entire operation is thread-safe. If you wrote the code for the thread-safe collections and your coworker is the one that has to write the program, it's on them to make sure whatever combination of actions they do is safe. Contrast that with the single-threaded scenario, where proving that the insertion and deletion code is correct also proves that moving an element between collections is correct. Also compare to manual memory management, where freeing allocated memory is the function caller's job.

I'm not really sure how OO fits into this. Lock-based concurrency is hard no matter what paradigm you choose.

  • I disagree with your assertion that reasoning about [manual] resource management in single-threaded code is difficult. It's just that the prevalence of garbage-collectors has made it unnecessary to do so for the most common case (memory management) and thus many programmers are out of practice or have never learned the skill. In fact, while GC makes the memory management problem mostly disappear, it actually makes all other forms of resource management more difficult because it takes away the best tool for resource management (RAII) and promotes shared ownership, interdependence, etc. – bcrist Oct 31 '14 at 15:24
  • @bcrist For the simple case of scoped lifetime (which is basically what RAII is, and probably the most common case for non-memory resources), all you need is lambda expressions and first-class functions. It's trivial to create a function that takes as arguments: 1) the function for acquiring the resource, 2) the function for releasing the resource, and 3) the function to apply between 1 and 2. It's then trivial to create a specialized version that only requires 3. You could object that your language of choice doesn't have lambdas, but then you have bigger problems than resource management. – Doval Oct 31 '14 at 15:45
  • 1
    @bcrist And if it's not hard to prove that nowhere in any possible execution of the program does resource management go wrong, why do people use Valgrind? – Doval Oct 31 '14 at 15:49
5

The particular issue with OOP and concurrency is that often programmers are tempted to try to hide thread safety implementation away using encapsulation.

When this is done by baking locks right into objects, then it is almost always a leaky abstraction, because of the side effects that locks cause.

  1. If you have a lot of these hidden locks, then you're unlikely to run into race conditions, but it becomes really easy to get deadlocks (which arguably themselves are actually just race conditions, but I think you get my point). So then you have to reason about the order in which you call certain methods to avoid deadlocks. Not easy to reason about. And the encapsulation you wanted simply isn't there.

  2. Or you use locks more sparsely, which makes it easier to avoid deadlocks. But it's also hard to reason about where the locks should be put to avoid weird/unexpected behavior. That also means that you will all too often have to intimately couple the implementation of an object to when (as opposed to just how) it is going to be interfaced by the outside world. So there's also no real encapsulation.

So it's not that having objects makes dealing with concurrency harder. It's that trying to have object deal with concurrent access to them makes dealing with those objects harder. You can always, for example, have a model that is not the least bit thread safe, and just guarantee that all interaction is routed through a facade that deals with thread safety (e.g. through a reactor pattern). Then said facade has the single responsibility of dealing with concurrency.

  • Yes! The way the dominant OOP systems handle this is to either do nothing or bake locks into the objects. In the latter case, it's often not apparent when this has been done, or how. (Documentation is often too informal to be sufficiently precise, btw.) It's even less apparent how to compose objects with disparate locking implementations: a substantial cognitive burden. So essentially the only "correct" way to do things is have two classes of objects, "infrastructure" and "non-infrastructure," and only the former is allowed to use locks. Good luck getting that right. – ngreen Oct 31 '14 at 16:39
4

To understand the correctness of a given line of lock-based concurrency code, you have to understand the entire program.

Now, you can save on this a bit. If you manage to prove to yourself that everything accessed in that bit of lock-based concurrency code is only accessed within a particular lock, you now only have to understand every bit of code in the program that also accesses that lock, its state when it starts the lock access, and everything it does while holding it.

This is because lock-based concurrency only maintains "thread safety" by locking access to data to limited numbers of threads at once (sometimes 1, sometimes only readers, etc). So you have to understand all of the locking behavior, and behavior while locking, in order to know if you lock system is actually doing what you want it to.

Next, because locks are subject to deadlocks, in order to understand multiple locks you have to understand not only the code in a lock, but every possible sequence you can acquire locks in.

And our languages and type systems do not help all that much with these tasks.

It gets worse. Like the other hard to track down and common errors, the deadlock and race condition problems usually do not happen reliably. You can write the code, do some simple tests, even run it in production, and have it work almost always. Except sometimes it fails spectacularly.

Really rare spectacular failures are hard to debug regardless of how easy they are to reason about. Here we have rare, spectacular failures that are difficult to reason about.

And it gets worse. When learning how to program, people typically run into a number of hurdles. Understanding state/assignment/data flow is a hurdle some don't get over. Understanding conditionals and function calling is another. Recursion and iteration throws some people for a loop. Indirection and pointers cut off an entire set of would-be programmers from becoming useful. Resource management. And concurrency and synchronization is another such hurdle.

We can generate more useful programmers by removing some of these hurdles "in the way" of being productive. There are languages that hide indirection and pointers from the programmer, and handle the big resource management task for you (memory), and you can learn to become a productive programmer in those languages without getting over that hurdle.

In almost every language you can become a "productive programmer" without getting over the concurrency hurdle. You can produce useful code, be a professional developer, graduate from university -- all of them without ever getting concurrency.

The ones that didn't get flow control, data flow and iteration never became professional programmers. The ones who don't get concurrency are productive senior developers at many a company.

0

Locks aren't hard to understand, and concurrency isn't particularly difficult to understand, either (almost everything going on around us in life is concurrent). It is scheduling of the locks that is hard to understand. Almost nothing in real life blocks, but in sequential computing with a single thread everything does, and all we do by splitting threads or processes is to pretend there are several when in fact we are really blocking each other constantly. Scheduling that block is really hard to get right. Its hard to schedule the CPU time for one, and hard to schedule shared, stateful resources as well, but doing both can be a real beast.

Enter things like the Erlang runtime. There concurrency is easy and works the way you expect. This is because the runtime handles the scheduling for you, freeing you up to think about the problem you're actually trying to solve. Scheduling is the big win, not the other stuff that gets hyped all the time. The cost for all that easy concurrency is that no state can be shared. It appears this is not something that most programmers feel comfortable with; there are extremely high incidences of folks doing the "read half a book on Erlang and gave up" dance and winding up right back where they started.

Whatever language or environment you choose to solve problems in it is important to recognize that the nature of the problem is not the locks, the state or the language, it is the scheduling of locks whenever state is shared.

Not the answer you're looking for? Browse other questions tagged or ask your own question.