8

While I was reading a research paper on concurrency named Software and the Concurrency Revolution (html version). I came across following lines:

Unfortunately, although locks work, they pose serious problems for modern software development. A fundamental problem with locks is that they are not composable. You can’t take two correct lock-based pieces of code, combine them, and know that the result is still correct. Modern software development relies on the ability to compose libraries into larger programs, and so it is a serious difficulty that we cannot build on lock-based components without examining their implementations.

  1. I was thinking, how Java guarantee composable concurrency or even there is a way to produce this scenarios.

  2. And how we can synchronize data in one or more libraries? Can a programmer do it from his program or it is up to library to synchronize things.

  3. If not Java then is there any other language which use lock based concurrency and guarantee composable concurrency?

Following is also taken from same paper:

There are at least three major problems with synchronized methods. First, they are not appropriate for types whose methods call virtual functions on other objects (e.g., Java’s Vector and .NET’s SyncHashTable), because calling into third-party code while holding a lock opens the possibility of deadlock. Second, synchronized methods can perform too much locking, by acquiring and releasing locks on all object instances, even those never shared across threads (typically the majority). Third, synchronized methods can also perform too little locking, by not preserving atomicity when a program calls multiple methods on an object or on different objects. As a simple example of the latter, consider a banking transfer: account1.Credit(amount); account2.Debit(amount)...

Note: Paper was published on September 2005

  • This paper cited by... – Erik Eidt Mar 26 '16 at 15:44
  • @ErikEidt paper have 94 Citations – user183296 Mar 26 '16 at 16:20
  • 3
    Not an answer to the question, but you get much more well behaved concurrency when you restrict the interactions to message passing: Processes (full processes, not just threads) communicating through asynchronous message queues. True, it's not as performant as the threat-based model, but if the sending of a message cannot block, you can't deadlock unless you have a real circular data dependency coded into your messages. Most importantly, any message is trivially composed/interpreted as an atomic operation, so all the headaches of consistent state go away. – cmaster Mar 26 '16 at 17:10
  • 1
    Software Transactional Memory is a concurrency construct that is composable. Haskell has a STM library. – comingstorm Mar 28 '16 at 16:42
  • 1
    @penguin: concurrency != parallelism. Javascript (node.js) is a good example of a language with very high concurrency (indeed all I/O are concurrent) but is single threaded. Java has fairly good framework for this in the form of Futures (CompletionStage). Of course, how lock-free your code is depends on implementation but the tools are there for you to develop on. – slebetman Mar 3 '17 at 4:10
7

It's not the Java language. It's the nature of locks (mutexes).

There are better ways to get improved concurrency while still guaranteeing correctness, ways that are language independent:

  1. Using immutable objects, so that you don't need locks.
  2. Using promises and continuation-passing style.
  3. Using lock-free data structures.
  4. Using Software Transactional Memory to share state safely.

All of these techniques allow improved concurrency without using locks. None of them depend on the Java language specifically.

3

I was thinking, how Java guarantee composable concurrency or even there is a way to produce this scenarios.

As the article says, it's not possible to guarantee composability when using locks along with virtual methods (or other similar mechanism, like passing functions as parameters). If a piece of code has access to virtual methods that come from another piece of code and both potentially use locks, then to safely (i.e. without the risk of a deadlock) compose the two pieces of code, you need to inspect the source code of both.

And how we can synchronize data in one or more libraries? Can a programmer do it from his program or it is up to library to synchronize things.

Generally, it's up to the programmer using the libraries to do the synchronization. That way, the programmer knows where all the locks are and they can make sure they do not deadlock.

If not Java then is there any other language which use lock based concurrency and guarantee composable concurrency?

Again, the point of the article is that this is not possible.

  • The paper was published in 2005. Your answer is based on same paper. Languages have evolved a great deal since 2005. Can you give any latest reference or can you reconfirm you answer. – user183296 Mar 26 '16 at 12:43
  • 2
    That paper does not talk about anything that's specific to 2005. It will still be true in 2105 that lock based libraries are not composable. – svick Mar 26 '16 at 12:46
  • Java is constantly updating its locking constructs, your can compare Java concurrency package in Java5 up to Java8. – user183296 Mar 26 '16 at 12:50
  • It does not matter. Java 8 certainly didn't eliminate the possibility of a deadlock when using locks, so nothing changed about this. – svick Mar 26 '16 at 12:51
  • 2
    @penguin - It is impossible to make a language entirely composable once it has non-composable features, because you cannot guarantee that closed modules are not using them in a dangerous way. You can make your code composable, even if you are using locks (although you have to be careful about how you use them in this case), but you cannot be sure that arbitraries libraries and/or system components aren't. – Jules May 30 '16 at 8:55
1

Low-level locking mechanisms are inherently not composable. This is mostly because locks reach underneath the world to affect the machine executing the instructions.

Subsequent Java libraries have added higher and higher level mechanisms for ensuring correct multithreaded operation. They do this by constraining the use of lock() and volatile to certain well-known, and controllable circumstances. For instance, a concurrent queue implementation has very localized behavior and allows reasoning about before and after states. Using higher level mechanisms means you need to read less of the spec or code to get it right. But, and this is a big but, you still need to understand the locking model of any subsystems and how they interact with each other. Also, the changes in Java for concurrency after Java 5 are almost exclusively related to the libraries and not the language.

The major issue with any locking mechanism is that it affects state and operates in the time domain. Neither humans nor computers reason well about either state or time. It's the ability to reason about value and structure that allowed computer scientists to come up with monads, the first thing that comes to my mind with regard to composability in a language.

The closest we have come is Communicating Sequential Processes. This still requires a high-level mechanism, such as mailboxes and message passing. In my humble opinion, CSP still does not deal adequately with either large systems (the ultimate target of composable software) or time-based reasoning.

  • 1
    This dosen't answer my question. I wanted to know if Java is composable or is there any other language which is? As per two answer i got, Java is not composable but both answers don't provide any concrete evidence. – user183296 Mar 26 '16 at 16:28
  • Did you want a proof that Java using only locks is not composable? Also, if you read the CSP article above, you will see a bunch of languages mentioned that are composable. My comments refer to any language where lock() and volatile are the granularity of thread or process synchronization. – BobDalgleish Mar 26 '16 at 18:10
  • Okay, there is something I am interested about. In your answer you said "The closest we have come..." what do you mean by that. How did you figure out that CSP is the closest one? – user183296 Mar 26 '16 at 19:32
1

First of all I thank all the members who answered this question, especially Robert Harvey whose answer seems very close to mine.

I have been researching on concurrency concepts for two years and according to my findings, no language provide a guarantee that its concurrency constructs are composable. Perfectly good running code using immutable data structures and STM can also produce unexpected results because under the hood, STM uses locks. STM is very good for atomic operations, but if we talk about composability of concurrency contrasts between modules, there is a (very slight) chance that STM may not work as expected.

But still, we can minimize uncertainty by using following (techniques/methods/constructs):

  1. Avoiding locks and synchronization
  2. Using STM
  3. Using persistent (immutable) data structures
  4. Avoiding sharing state
  5. Pure functions
  6. Asynchronous programming style
  7. Avoiding frequent context switching
  8. Multi-threading paradigm and the nature of its environment play major role

Perhaps the most fundamental objection [...] is that lock-based programs do not compose: correct fragments may fail when combined. —Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2

Update

Thanks to Jules, I stand corrected. STM uses various implementations and most of them are lock free. But I still believe that STM is a good solution here, but not the perfect one, and it has drawbacks:

Each read (or write) of a memory location from inside a transaction is performed by a call to an STM routine for reading (or writing) data. With sequential code, these accesses are performed by a single CPU instruction. STM read and write routines are significantly more expensive than corresponding CPU instructions as they, typically, have to maintain bookkeeping data about every access. Most STMs check for conflicts with other concurrent transactions, log the access, and in case of a write, log the current (or old) value of the data, in addition to reading or writing the accessed memory location. Some of these operations use expensive synchronization instructions and access shared metadata, which further increases their costs. All of this reduces single-threaded performance when compared to sequential code. - Why STM can be more than a research toy - page 1

Also see these papers:

These papers are a few years old. Things may have changed/improved but not all.

  • "A perfectly good running code using immutable data structures and STM can also produce unexpected results because under the hood STM use locks." Can you provide an example of such an unexpected result? As far as I'm aware, STM is considered reliable and composable, but perhaps you're aware of something I'm not...? – Jules May 30 '16 at 8:40
  • Also, you state that STM "uses locks", but that's only an implementation detail of some versions of it. STM can be implemented in an entirely lock-free system by using atomic updates; see dl.acm.org/citation.cfm?id=1941579 – Jules May 30 '16 at 8:49
1

I've heard it said by well-respected researchers that any useful synchronization mechanism can be used to construct a deadlock. Transactional Memory (whether hardware or software) is no different. For example, consider this approach to writing a thread barrier:

transaction {
    counter++;
}

while (true) {
    transaction {
        if (counter == num_threads)
            break;
    }
}

(Note: the example is taken from a paper by Yannis Smaragdakis at PACT 2009)

If we ignore the fact that this is not a good way to synchronize a large number of threads, it seems to be correct. But it's not composable. The decision to put the logic into two transactions is essential. If we were to call this from another transaction, such that everything flattened into one transaction, then we'd probably never complete.

The same is true of message passing channels: communication cycles can cause deadlocks. Ad-hoc synchronization with C++ atomics can lead to deadlocks. RCU, sequence locks, readers/writer locks, condition variables, and semaphores can all be used to create deadlocks.

That's not to say that transactions or channels (or locks or RCU) are bad. Rather, it's to say that some things just don't seem possible. Scalable, composable, pathology-free concurrency control mechanisms are probably not possible.

The best way to avoid trouble is not to look for a silver-bullet mechanism, but to rigorously use good patterns. In the world of parallel computing, a good starting point is Structured Parallel Programming: Patterns for Efficient Computation, by Arch Robison, James Reinders, and Michael McCool. For concurrent programming, there are some good patterns (see @gardenhead's comment), but C++ and Java programmers are not likely to use them. One pattern that more people could start using right ways is to replace ad-hoc synchronizations in programs with a multi-producer multi-consumer queue. And TM is definitely better than locks, in that it raises the level of abstraction, so that programmers focus on what needs to be atomic, not how to implement a clever lock protocol to ensure atomicity. Hopefully, as hardware TM improves and languages add more TM support, we'll reach a point where TM supplants locks in the common case.

  • 1
    "For concurrent programming, the patterns aren't as well developed." This is patently false. Concurrent models of computation go back decades. The actor model was invented in the early 70s, and various forms of process calculi have been invented and studied since that time as well. The issue lies not with good models of computation; it lies with programmers unwilling to use those models and possible inefficiencies in their implementation. – gardenhead Mar 2 '17 at 2:44
  • Excellent point, @gardenhead. The models have been developed, it's just that nobody uses them. I'll edit my response. – Mike Spear Mar 3 '17 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy