Concurrent coding for fun

Every now and then I like to get stuck into some hairy coding, just for fun. Concurrency and multithreaded objects are always good for a challenge. While waiting for a build yesterday I had a go at writing a Work Queue implementation, which is kind of like a service-orientated approach to thread pooling.

A work queue is simply an object that allows Runnables to be scheduled for execution and contains a number of threads internally that run in a loop, popping tasks off the queue and running them. Synchronisation is fun, as you have to properly manage multiple threads adding and removing tasks from the queue, as well as preventing both busy waiting (where threads spin in a tight loop, taking all your cpu but doing nothing) and excessive blocking (and of course deadlock). Proper use of wait() and notify() is essential.

Some thoughts that occurred: Threads live in methods. All method-level variables are per-thread. So while there might be many threads running the same method, from their perspective they are in glorious isolation. The places where threads go to meet other threads are an object’s fields, and wait() and notify() calls. This is where the fun lies. I tend to imagine calls to wait() as turnstiles, where threads queue up, waiting to be allowed through. When a thread calls notify() on an object other threads are waiting on, one of them is allowed to go through the turnstile and continue executing. Calling notifyAll() is like starting a melee, where all the waiting threads make a dive for the door. Only one can get through at a time, but they’re all going to try. The other important point is that although a waiting thread may have been notified (it’s pushing at the turnstile), it can’t get through until the thread that called notify() leaves the synchronized block. This is why calls to notify() are usually found at the end of synchronized blocks, or right before a call to wait(). One other thing I forgot to mention. When a thread hits a wait() call, it gives up the lock its holding on that object (remember that wait can only be called in a synchronized block), thus allowing other threads to run in that block (or other block synchronized on the same object). Clear as mud?

Some things to remember when writing multi-threaded classes:-

If you call wait(), you must call at least one notify() on the same object.

If you have to wait(long) to avoid deadlock, you probably forgot to notify().

Figuring out which object to synchronise on is important.

Nested synchronized blocks are really easy to deadlock. Avoid if possible.

Don’t synchronise your methods unless its to prevent concurrent modification to your fields. Methods can only be synchronised on their own object. Synchronised blocks can use any variable or field, which can get really hairy, but is much more flexible.

When thinking about threads, time is a variable. Threads (at the same priority) can run at the same speed, overtake one another, one could run from start to finish before the other gets moving, and anything in between. The only way to coordinate the activities of multiple threads is by careful use of synchronized, wait() and notify().

Oh, and forget that ‘synchronisation is slow’ myth. I once wrote a partially synchronized Map of Maps implementation where the main map was a regular hashmap and the submaps were synchronized. The theory was that in a multithreaded system that would allow greater concurrency. Turns out the cost of hashing twice was more expensive than using a simple synchronized map and letting the threads compete for it. Go figure.

Advertisements

2 thoughts on “Concurrent coding for fun

  1. Thread programming is fun and challenging. But there really isn’t a point to writing that kind of stuff yourself.

    Either something like a thread pool, or even creating something simpler like a queue.

    There are packages out there that do this stuff and do it well. Doug Lea’s concurrency package is the best example.

    The problem is you can’t test concurrent programming easily, things happen by chance. Or worse when the system load goes up for the first time.

  2. A couple of thoughts:

    1. wait(long) isn’t necessarily a sign of a missing notify, it’s also very easy to set up a race condition where the notify may happen after the guard and before the wait. Ideally the guard is in your wait sync and all changes are in the notify sync but… usually when you go multi-threaded it’s because you’re dealing with external factors anyway, so it’s not often so simple. Doing a quick check a few times a second is often a small price for avoiding deadlock.

    2. It’s true that the synchronized keyword is much faster than just about any of the tricks to avoid it (such as your Map of Maps) BUT don’t forget multi-CPU servers. An extra hash is a small cost compared to stopping 7 CPUs.

Comments are closed.