Lock-free algorithms: The try/commit/(try again) pattern

The singleton constructor pattern and the Interlocked­Multiply example we saw some time ago are really special cases of the more general pattern which I'll call try/commit/(try again). I don't know if this pattern has a real name, but that's what I'm calling it for today.

The general form of this pattern goes like this:

for (;;) {

 // capture the initial value of a shared variable we want to update

 originalValue = sharedVariable;

 ... capture other values we need to perform the operation ...

 ... these values must be indepedent of sharedVariable ...

 newValue = ... calculate the desired new result

                based on originalValue and other captured values ...

 // Xxx can be Acquire, Release, or null

 if (InterlockedCompareExchangeXxx(

            &sharedVariable,

            newValue, oldValue) == oldValue) {

  break; // update was successful

 }

 ... clean up newValue ...

} // loop back and try again

We calculate the desired new value based on the initial value, combining it with other values that vary depending on the operation you want to perform, and then use an Interlocked­Compare­Exchange to update the shared value, provided the variable hasn't changed from its initial value. If the value did change, then that means another thread raced against us and updated the value before we could; in that case, we go back and try it again. Maybe the next time through we won't collide against somebody.

Read more: The old new thing

Posted via email from Jasper-net