Bezamochnye algorithms: model "make, write, (try again)"

The atomic multiplication we implemented last time is an example of a more general model, which Raymond called “make, write, (try again)”.

 for (;;) {
  // take the initial value of the shared variable
  // which we are going to change
  oldValue = sharedVariable;

  ... take the initial values ​​of other parameters ...

  newValue = ... calculate the new value using
                 oldValue and copies of other parameters ...

  // instead of xxx can be Acquire, Release, or nothing
  if (InterlockedCompareExchangeXxx (
             & sharedVariable,
             newValue, oldValue) == oldValue) {
   break;  // write failed
  }

  ... delete newValue ...

 } // try again

We calculate a new value, and then by calling InterlockedCompareExchange write it to a common variable only if its value has not changed. If it has changed, then another stream has preceded us; in this case, we will try to perform the operation in a new way, from the very beginning, in the hope that next time no one will “cut off” us.

It is important to understand that the “make, write, try again” model does not guarantee that the stream that first started updating the variable value will win the “race” first. The “unsuccessful” stream may, at each attempt, again and again yield to faster rivals; it is theoretically possible that he will never complete the operation initiated (but each of the streams that overtake him will complete his own). This feature is typical for lockless algorithms - unlike locks, which, as a rule, implement the waiting queue: the first one came - the first one passed.

The translator dared to come up with his own analogy: the ticket office at McDonalds is a castle, behind which a line of waiting customers lined up. If the customer standing at the cash register’s time rummaging through his pockets in search of small things, then the other customers and the cashier are wasting their time waiting; the system as a whole is idle. On the other hand, the waiter in the restaurant is a non-stop resource. Every client calls him to pay for lunch; but another customer can “meet” and intercept the waiter on the way. It is not known how many times the waiter will be distracted until he finally reaches your table; but on the other hand, if he doesn’t approach you, then now he is serving someone else. In general, the system is not idle.
')

---

The InterlockedMultiply function from the previous post corresponds to the pattern given here almost verbatim: “another parameter” is a multiplier passed to the function parameter; “New meaning” is a work. If the entry of a new value failed, then someone else changed it, and we start the operation again.

The initialization of static variables in the past post also corresponds to the model “make, write, (try again)”, just the stage “try again” is optimized: we know that its result would be the same values ​​that were already written to common variables by the stream overtaking; therefore, this stage can not be performed. In the case of variable initialization, InterlockedCompareExchange used in the Release version, because the new value is valid only with other data in memory (only with a ), and should be recorded only after them.

Another “optimized” version of the model is “make, write, (drop it)”. There is also no cycle in it: if the entry of a new value fails, the function considers the failure fatal, and refrains from further attempts. This is how, for example, TryEnterCriticalSection . It uses InterlockedCompareExchangeAcquire : changes made from within the critical section should not be written into memory before it is written that the section is busy.

If the common variable is not a number, but a pointer, then you need to take care that the already mentioned “ABA problem” does not arise when the same pointer points to a new object. Initialization of static objects does not require additional difficulties: the pointer can change only from NULL to something , and once it has become non-NULL, the pointer no longer changes. If the pointer can change arbitrarily, then, as a rule, this pointer and the “version number” are combined in a common variable, which increases with each pointer change.

In the following example of using the model “make, write, (try again)”, the version number will be stored in a common variable. To begin with, two auxiliary functions:

 LONG InterlockedReadAcquire (__ in LONG * pl, __in LONG lUnlikely)
 {
   return InterlockedCompareExchangeAcquire (pl, lUnlikely, lUnlikely);
 }

 LONG InterlockedReadRelease (__ in LONG * pl, __in LONG lUnlikely)
 {
   return InterlockedCompareExchangeRelease (pl, lUnlikely, lUnlikely);
 }

Unlike reading LONG variables directly, these functions impose restrictions on the order of writing to memory. Since the compared and the new value in the InterlockedCompareExchange operation coincide, the value to be tested does not change for any outcome of the operation. Actions performed are similar to code:

 if (* pl == lUnlikely) * pl = lUnlikely;

As lUnlikely Raymond advises choosing an unlikely value so that in most cases the assignment is not performed and the cache block is not “dirty”. (Not on all processors this helps prevent writing to memory, but such cunning will not be superfluous.)

So, our example:

 LONG g_lColorChange;  // version number of colors

 ...
 case WM_SYSCOLORCHANGE:
  InterlockedIncrement (& g_lColorChange);
  ...

 int CalculateSomethingAboutSystemColors ()
 {
  LONG lColorChangeStart;
  do {
   lColorChangeStart = InterlockedReadAcquire (& g_lColorChange, -1);
   COLORREF clrWindow = GetSysColor (COLOR_WINDOW);
   COLORREF clrHighlight = GetSysColor (COLOR_HIGHLIGHT);
   ... other calculations using GetSysColor (...)
  } while (InterlockedReadRelease (
                        & g_lColorChange, -1)! = lColorChangeStart);
  return iResult;
 }

We take the old value of the version number, and begin our calculations. We take it with an Acquire operation, so the read version number is written into memory before the color values ​​that we use for calculations.
When the calculations are completed, we compare the current version number with the saved one. If they do not match, then the colors have changed in the course of our calculations, so they will have to be redone.
The ABA problem is possible if the colors during the calculations have changed four billion times: because of the overflow of the counter, we will not notice. It is clear that in reality this is unlikely to happen.