How to deal with Concurrency before you start coding

Question

I'm midway through programming a Java program, and I'm at the stage where I'm debugging far more concurrency issues than I'd like to be dealing with.

I have to ask: how do you deal with concurrency issues when setting out your program mentally? In my case, it's for a relatively simple game, yet issues with threads keep popping up - any quick-fix almost certainly leads to a new issue.

Speaking in very general terms, what techniques should I use when deciding how my application should 'flow' with out all my threads getting in a knot?

Answer 1

It depends what your threads do. Typically programs have a main thread that does the thinking and worker threads to do parallel tasks (timers, handling long computations on a GUI, etc.) But your app may be different - it depends on your design. What do you use threads for? What locks do you have to protect shared datastructures? If you use multiple locks, do you have a single order in which you lock to prevent deadlocks?

Answer 2

The fewer threads you have, the smaller state they share, and the simpler their interaction pattern on this shared state, the simpler your life will be.

You say Lists are throwing ConcurrentModificationException. I take it that your lists are acessed by seperate threads. So the first thing you should ask yourself is whether this is necessary. Is it not possible for the second thread to operate on a copy of the list?

If it is indeed necessary for the threads to access the list concurrently, locking the list during the entire traversal might be an option (Iterators are invalidated if the list is modified by any other means than that iterator). Of course, if you do other things while traversing the list, this traversal might take long, and locking out other threads might threaten the liveness of the system.

Also keep in mind that if the list is shared state, so are its contents, so if you intend to circumwent locking by copying the list, be sure to perform a deep copy, or prove that the objects contained in the list are themselves thread safe.

Answer 3

I use immutable data structures as much as possible. About the only time I do use mutable structures is when I have to such as with a library that will save a boatload of work. Even then I try to encapsulate that library in an immutable structure. If things can't change then there's less to worry about.

I should add that some things to keep in mind on your future endeavors are STM and Actor models. Both of these approaches to concurrency are showing very good progress. While there is some overhead for each, depending on the nature of your program that might not be an issue.

Edit:

Here are a few links to some libraries you could use in your next project. There's Deuce STM which as the name implies is an STM implementation for Java. Then there's the ActorFoundry which as the name implies is an Actor model for Java. However, I can't help but make the plug for Scala with its built in Actor model.

Answer 4

From the design perspective, I've found it useful to draw sequence diagrams where each thread's actions are color coded (that is, each thread has its own color). Using color in this way may be a non-standard use of a sequence diagram, but it's good for giving an overview of how and where threads interract.

As others have mentioned though, reducing the amount of threading in your design to the absolute minimum it needs to work properly will help a lot as well.

Answer 5

Read up on concurrency, or better yet take graduate-level course on concurrent programming if you are still in college. See The Java Tutorials: Lesson: Concurrency. One famous book for Java concurrency is Java Concurrency in Practice. Java has so much built into the framework to deal with concurrency issues, including concurrent collections and synchronized methods.

Answer 6

1. Try to use collections from java.util.concurrent package or even better immutable collections from Google Collections.
2. Read about using synchronized blocks

Answer 7

It's possible that the multi-threaded nature of your application might be a red herring, with respect to the ConcurrentModificationExceptions you mentioned: there are other ways that you can get a ConcurrentModificationException that don't necessarily involve multiple threads. Consider the following:

List<Item> items = new ArrayList<Item>();

//... some code adding items to the list

for (Item item : items) {
    if(item.isTheOneIWantToRemove()) {
        items.remove(item); //This will result in a ConcurrentModificationException
    }
}

Changing your for loop to a loop with an iterator, or an increasing index value solves the problem:

for (Iterator<String> it = items.iterator(); it.hasNext();) {
    if(item.isTheOneIWantToRemove()) {
        it.remove(); //No exception thrown
    }
}

or

for (int i = 0; i < items.size(); i++) {
    if(item.isTheOneIWantToRemove()) {
        items.remove(items.get(i)); //No exception thrown
    }
}

Answer 8

Concurrency boils down to managing shared state.

"All concurrency issues boil down to coordinating access to mutable state. The less mutable state, the easier it is to ensure thread safety." -- Java Concurrency in Practice

So the question you must ask yourself are:

• What is the inherent shared data that the my application will need?
• When can a thread work on a snapshot of the data, that is, it momentary work on a clone of the shared data?
• Can I identify known pattern and use higher-level abstraction rather than low-level locks and thread coordination, e.g. queues, executor, etc. ?
• Think of a global locking scheme as to avoid deadlock and have a consistent acquisition of locks

The simplest approach to manage shared state is to serialize every action. This coarse-grained approach results however into a high lock contention and poor performance. Managing concurrency can be seen an optimization exercise where you try to reduce the contention. So subsequent questions are:

• How would the simplest approach be?
• What are the simple choice that I can make to reduce contention (possibly with fine grained locking) and improve performance without making the solution overly complicated?
• When am I going too fined-grained, that is, the complexity introduced isn't worth the performance gain?

A lot of approach to reduce contention rely on some form of trade-off between what would be necessary to enforce the correct behavior and what is feasible to reduce contention.

• Where can I relax a few constraint and accept that sometimes stuff won't be 100% correct (e.g. a counter) ?
• Can I be optimistic and deal with conflict only when concurrent modifications happen (e.g. using time stamp and retry logic - that's what TM do)?

Note that I never worked on a game, only on server-side part of enterprise apps. I can imagine that it can be quite different.

Answer 9

While designing your application, I'd recommend considering which program resources are shared. THis article gives a good insight into how various Java resources are shared among threads:

http://javatip.com/2010/07/core-java/concurrency/thread-safe-without-synchronization