Multithreading: when interlocked operations aren’t enough

In the previous post, we’ve started looking at interlocked operations. As we’ve seen, interlocked operations are great at what they do but they won’t be usable in all scenarios (ie, don’t think that they’ll solve all your locks problems). To show how things might go awry when using interlocks, I’ll reuse a great example written by Raymond Chen a few years ago (I’m updating it to C#):

class Program
{
  private static Object _lock = new Object();
  public static Int64 InterlockedMultiply(
          ref Int64 multiplicand, Int64 multiplier) {
    Int64 result = 0;
    lock (_lock) {
      var aux = multiplicand;
      Thread.Sleep(100);//oops!!!
      result = multiplicand = aux * multiplier;
    }
    return result;
  }
  static void Main(string[] args) {
      Int64 a = 5;
      new Thread(
         () => InterlockedMultiply(ref a, 5)).Start();
      new Thread(() => { 
              Thread.Sleep(50); 
              Interlocked.Increment(ref a); }).Start();
      Thread.Sleep(2000);
      Console.WriteLine(a);
  }
}

The idea is to add a safe multiplier method. As we’ve seen in the previous post, interlocked increments are atomic. That means that they’re executed as a “single” operation by the processor. Since we didn’t had a method that performs the same operation for multiplication, we’ve decided to mimic that behavior by adding a new method which uses a lock to ensure proper multiplication.

If I asked you what Console.WriteLine(a) would print, what would you say? For now, forget those nasty Sleep invocations (they’re there to force the wrong behavior)… I’m guessing that you’d probably say that Console.WriteLine will only write 26 or 30. It will write 26 if InterlockedMultiply “beats” Increment or 30 if Increment is run before InterlockedMultiply. Ah, well,with those nasty sleep instructions,I’ve managed to get 25 here on my machine. Wtf? How? Why?

Well, what happened is logical…Interlocked.Increment will always update the value in a single atomic operation (this means it will load, update and then store the value in a “single” step). However, InterlockedMultiply only ensures that the code wrapped by the lock will only be executed by a thread at a time. Look at that method carefully…can you see a load followed by a store? Those two operations aren’t performed atomically like the one you get through the Interlocked.Increment method!

There is a solution to this problem, but it involves looping until you get a valid result. Take a look at the method updated to work correctly:

public static Int64 InterlockedMultiply(
       ref Int64 multiplicand, Int64 multiplier) {
  Int64 result = 0;
  Int64 aux = 0;
  do {
    aux = multiplicand;
    result = aux * multiplier;
  } while ( Interlocked.CompareExchange(
                ref multiplicand, result, aux) != aux);
  return result;
}    

As you can see, we’re using the Interlocked.CompareExchange method to ensure that multiplicand will only be updated if it hasn’t changed during the  execution of that loop. That happens because the Interlocked.CompareExchange method will always return the value that was stored in multiplicand at the time of the call (recall that CompareExchange always returns the original value of the 1st parameter passed to the method at the time of the call).

As you can see, interlocked operations don’t ensure proper serialization of your code. They only guarantee that the interlocked operation is done atomically. And I guess that’s all for now. Keep tuned for more on multithreading.

~ by Luis Abreu on July 2, 2009.