In Progress
Unit 1, Lesson 21
In Progress

Atomicity

Video transcript & code

I've mentioned once or twice already that threading is hard. Well, today we're going to look at another example demonstrating this truth.

Let's write some dead-simple multi-threaded code. We'll instantiate a counter variable that starts at zero. Then we'll kick off 10 threads. Each thread will increment the counter 100 times, and then terminate.

When all the threads have finished, we look at the ending state of the counter. Since 10 threads have updated it 100 times, we expect the counter to have a value of 1000.

counter = 0

threads = 10.times.collect do
  Thread.new do
    100.times do
      counter += 1
    end
  end
end

threads.each(&:join)
puts counter

…and that's exactly what we see. So far so good.

Now let's run this same code under JRuby, which has somewhat more robust multithreading capabilities.

$ rvm jruby do ruby incr.rb 
670

..that doesn't look right. Worse still, when we run it repeatedly, we see a different answer every time.

$ ruby incr.rb 
772
$ ruby incr.rb 
781

So what's going on here? Let's take a closer look at that code. All each thread does is increment a counter. What could go wrong?

When we look at a line of code like this, it's easy to assume that the operation is atomic: first the counter's value is 0, then the value is 1, and that's all there is to it.

But the way the Ruby VM—or at least the JRuby VM—looks at this code is a little different. It sees it more like this: first, get the value of the counter plus 1. Then, assign that new value to the counter variable. As you can see, this is two steps.

new_val = counter + 1
counter = new_val

Now let's examine what happens when there are two threads in play. Here's one possible way the scenario might play out.

Let's say the counter is currently at 3. Thread 1 calculates the next value, which will be 4. Then the scheduler decided to let Thread 2 go. Thread 2 calculates the counter's next value, and also gets 4, since Thread 1 hasn't actually updated the counter yet. Next, both threads set the counter to their new values. At this point it doesn't matter what order they execute in, because the damage is already done. The counter winds up with a value of 4, even though with two threads incrementing it, it should have gone from 3 to 5.

counter = 3
t1_new_val = counter + 1        # => 4
t2_new_val = counter + 1        # => 4
counter = t1_new_val            # => 4
counter = t2_new_val            # => 4
counter                         # => 4

Of course, this is just one way things could happen. Sometimes everything might execute in the order we expected by pure luck. This is why the answer changed every time we ran the program under JRuby.

We could call this a problem with JRuby, but that wouldn't be accurate. There is no spec saying that Ruby's += operator must behave atomically. And I wouldn't count on MRI's behavior in this scenario staying the same in future versions of Ruby, as the threading implementation matures.

If you've watched the episodes leading up to this one, you probably know how to make this code behave more predictably: we need to synchronize the increment with a mutex.

counter = 0
lock    = Mutex.new

threads = 10.times.collect do
  Thread.new do
    100.times do
      lock.synchronize do counter += 1 end
    end
  end
end

threads.each(&:join)
puts counter

This time when we run it under JRuby, we get the expected result of 1000.

if we are willing to expand our horizons beyond built-in classes, there's another approach we can try. The atomic gem, by Charles Nutter and MenTaLguY, provides truly atomic update semantics in Ruby. Here's how we use it.

We require the atomic library. We change our counter to an Atomic object, with an initial value of zero. Then we update the code that does the increment. Instead of +=, we send the #update message to the counter. With it we supply a block. The block receives the current value of the counter as an argument, and should return the desired new value. We want to increment the value by one, so we return the counter value plus one.

Finally, at the end when we want to access the final value, we send the counter the #value message.

require "atomic"
counter = Atomic.new(0)

threads = 10.times.collect do
  Thread.new do
    100.times do
      counter.update{|c| c + 1}
    end
  end
end

threads.each(&:join)
puts counter.value

Just like the mutex version, this code correctly counts up to 1000 under JRuby.

So what's the advantage of using the atomic gem? On reason is that I think it reads a little bit more clearly than the mutex version. More importantly, since the only way to update the Atomic object is to send it #update, we can't accidentally forget to surround an update in a synchronization block. And there's also the fact that if we added more shared counters, we'd have to add a mutex for each one, and that would get tedious.

Another reason we might choose atomic objects is performance. Here's a script that benchmarks the original thread-unsafe code, the mutex version, and the atomic version. When I run it on my machine, the atomic version shows modest speed improvements over the mutex version. The reason for this is that under the covers, the Java version doesn't use mutexes at all. Instead, it has a "lock-free" implementation that uses an operation called "compare-and-swap". In a nutshell, this operation enables code to attempt to update a variable, and then retry if the update failed because another thread got in the way. In the case where there was no contention from another thread, the update succeeds without the overhead of taking a mutex lock.

OK, that's all for now. Happy hacking!

Responses