Ready, Set, GO! Putting Threads to Race lightcycles in the JVM. Getting to a lock-free implementation

Lately I have been trying to improve my skills on lock-free algorithms. So I have been studying the literature and the javadoc of the atomic package. But I also felt that I needed to apply them on a concrete programming exercise to actually do progress grasping the important concepts. So I was trying hard to come up with an idea, but for some reason I couldn’t. This changed during last week’s Heinz’s happy hour webinar. At some point a comment by Piotr Findeisen prompted Heinz to talk about “racing threads”, “which thread won and did them all”. All this talk triggered my imagination and I somehow visualized LightCycles from the Movie Tron racing against each other playing chicken. 🙂

This post is about how I implemented a set of program in Java that models this imaginative scenario using two Threads and how I though it through to eventually get to one which uses a lock-free algorithm. I decided to share this for two reasons:

  • One because I found it quite cool to work on this, and would have loved to read it myself! 🙂
  • Secondly I am hoping this will prove helpful to others trying to think on these topics. I had quite some trouble reasoning about this so I will try to explaine how I thought about it and reached a solution that seems to work!

Continue reading