The Seeds of Wait-free Synchronization

Is this code thread safe?

Class NB_FIFO
{
   volatile FIFONode* mHead;
   volatile FIFONode* mTail;
   void push(Object obj)
   {
      FIFONode* fn = new FIFONode(obj);
      while(true)
      {
         FIFONode* last = mTail;
         FIFONode* next = last.mNext;
         if(last == mTail)
         {
            if(next == NULL)
            {
               if(last.mNext.CompAndSet(next,fn))
               {
                  tail.compareAndSet(last, fn);
                  return;
               }
            }
            else
            {
               tail.compareAndSet(last,next);
            }
         }
      };
   }
}

At first glance, you would assume that this is very much in violation of a thread safe model. But, you're incorrect; Not only is the above code thread safe, it's completely wait-free. But it uses a concept that not many programmers are familiar with : Lazy synchronization. (Which, if you said "No, it's not" don't feel bad)

Wait-free algorithms are becoming more and more needed as multi-core boom starts to hit full stride. The above code combines a number of concepts to remove the need to do locking on a dataset in order to operate on it.

The ultimate goal for wait-free algorithms is the removal of locks and resource contention, and instead replacing it with :

• Atomic Operations
• Memory Barriers
• Crazy ass new ways to look at the dataset.
  

The first two shouldn't be too 'off the wall' for most of us. Atomic operations are a great tool in the programmer tool set for parallel processing. But few have bridged the gap to understand that it can be used to remove locking! And memory barriers, (or the volatile keyword) are a must have for ensuring that our data is consistently valid across multiple thread reads.

Lazy Synchronization is just popping up lately as a means to remove blocking from thread safe containers. The basic idea behind the process is that instead of limiting threads from accessing resources in the data structure, we instead allow them to help out with the work we're doing. Effectively turning the biggest problem, into our biggest benefit. Lazy Synchronization allows accessing threads to encounter 'broken' or 'partial' states in the container traversals, and if such a state is found, the current thread fixes up the problem before moving on. This allows that if the modifying thread has only made partial changes to the structure, but has not yet finished, any other accessing threads won't get invalid data, but will fix the problems and move on. Effectively though, this breaks the ACID model of synchronous computing; specifically the 'don't leave your data in a weird state' one. But patches it up nicely by allowing other threads to fix it for you!

The great thing is, that it doesn't stop there. I've talked before about multi core blowing up, and there's even more proof of it as the days go by, and as that occurs, we'll start needing more wait-free algorithms to help along the process, and reduce resource contention and performance issues from our current hardware memory models. Cliff Click is proposing a nice elegant solution to one view of the problem (although he seems to ignore the 'out of core' versions of the same data containers..) And these guys like to talk about what's wrong with the current threading primitives.

Still don't get the point? Then here it is: Wait free algorithms are coming. They are already here. If you fancy yourself a systems programmer, then you need to learn the full in's and outs of these models. Come another 5 years, Course grain synchronization models will go the way of the dinosaur.

And I can't wait!


~Main