Concurrency pitfalls

The software we write constantly increases in complexity as more and more is demanded of our software. For most of us, we are no longer chasing down memory leaks, but with the arrival of multi-core systems comes a new set of challenges.

Preface

In the 'good old days' we had various problems, which stemmed from incidental complexity - most memorable is probably the many vunerabilities in C/C++ programs and especially memory leaks. With the arrival of automated garbage collection, memory leaks quickly became a non-problem and moving into higher-level languages takes away a lot of the pain which is so closely tied to low-level development. So now I guess we can write new quality software with great ease having overcome all the problems of old right? Wrong.

When all of our software was running in a single thread, ensuring data integrity seemed very simple. When you thow concurrency into the mix, suddenly 'time' becomes the ever implicit argument to all functions. How we manage 'time' then becomes crucial to our success.

In this blogpost, I'll try to run through some of the things we need to be mindful of when navigating in concurrent waters.

Locks

Enemy #1 is Locks. And I'm not talking about dead-/livelocks, I'm talking about locks in the user-code. Locking is a way of implementing the 'stop the world' illusion and the great problem with locks is that everyone writes their own.

To determine when and where to place locks requires both high intelligence and a little paranoia - you have to be careful. If you lock too many resources you end up cratering performance and possibly produce a dead-/livelock. If you put too few locks you will struggle with race conditions. I wanted to put together a little video showing the problems associated with locks and also how to resolve those sitations, but then I stumbled upon iMovie, and this happened:

(double click for full-screen - if you're not seeing it, try hitting F5 or using Firefox)

Concurrency Pitfalls from Lau Jensen on Vimeo.

(disclaimer: This is not a bash of Python, any language which defaults to mutability and encourages user-locks for handling multi-threading could have been used for these examples)

The examples

The first Clojure example is shown here:

(defn atomic-swaps []
  (let [x         (atom 0)  ; Async atomic change
        up150k    (fn []
                    (dotimes [i 150000]
                      (swap! x inc)))  ; apply inc to x
        t1        (future (up150k))]  ; future = do work in another thread
    (up150k)
    (deref t1)  ; Make sure t1 has returned
    (println @x)))

The problem with the Python-incrementor, was that between reading X and setting X, X had changed. That left the program with no grounds for decision-making, but since it was blissfully unaware, it set X to a wrong value. The clojure native 'atom' gives me exactly what I need to make my swaps atomic, so between reading and writing X, the second thread doesn't interrupt.

Second example:

(defn synchronized-change []
  (let [x          (ref (range 100))  ; ref = synchronized change
        y          (ref [])
        transfer   (fn []
                     (dosync  ; start a transaction
                      (when (seq @x)  ; Are there items left?
                        (alter y conj (first @x)) ; Append first-x to y
                        (alter x rest))))  ; Remove first x
        t1          (future
                     (while (seq @x)  ; Repeat while there are items
                            (transfer)))]
    (while (seq @x)
           (transfer))
    (deref t1)
    (println @y)))

For the second example we needed more concurrency support as not only the reading/writing of one list needed to be atomic, but the transfer from one list to the other needed to be syncrhonized, so as to eliminate in-between states where an item would be in both lists, or trying to read from an empty list etc. To avoid this race-condition I leverage Clojures STM, which coordiantes the change. The above code is perfectly safe and we're still lock free!

Conclusion

When you handle concurrency by forking processes, how do you share data between those processes? There's no one-answer-fits-all, so the developer has to invent a solution. This type of inter-process-communication is not uniform, it's not effective (compared to threads) and its not portable, in fact its something we usually want to avoid as much as locks. Sure the fears associated with traditional concurrency are valid and there are indeed many pitfalls, but instead of dismissing threads altogether I recommend investigating further how the functional paradigms, immutable datastructures, software transactional memory etc, can help us build better software. Clojure is currently out in version 1.1 and it has an abundance of concurrency support at the language-level, which will keep you perfectly safe even when multi threading.