Реализованное нами в прошлый раз атомарное умножение является примером более общей модели, которую Реймонд назвал «сделай, запиши,(попытайся снова)».
Мы вычисляем новое значение, и затем вызовом
Важно понимать, что модель «сделай, запиши, попытайся снова» не гарантирует, что поток, первым начавший обновлять значение переменной, первым выиграет «гонку». «Неудачливый» поток может при каждой попытке вновь и вновь уступать более быстрым соперникам; теоретически возможно, что он вообще никогда не завершит начатую операцию (зато каждый из обгоняющих его потоков завершит свою). Такая особенность типична для беззамочных алгоритмов — в отличие от замков, реализующих, как правило, очередь ожидания: первый пришёл — первый прошёл.
Переводчик дерзнул придумать собственную аналогию: касса в «Макдональдсе» — замок, за которым выстраивается очередь ожидающих клиентов. Если клиент, стоящий у кассы, битый час роется по карманам в поисках мелочи, то и остальные клиенты, и кассир впустую томятся в ожидании; система в целом простаивает. С другой стороны, официант в ресторане — беззамочный ресурс. Каждый клиент его подзывает, чтобы расплатиться за обед; но другой клиент может «встрять» и перехватить официанта по дороге. Неизвестно, сколько раз официанта отвлекут, пока он дойдёт наконец до вашего столика; но с другой стороны, если он к вам не подходит, значит сейчас он обслуживает кого-то другого. В целом система не простаивает.
Функция
Инициализация статических переменных в прошлом посте также соответствует модели «сделай, запиши,(попытайся снова)», просто этап «попытайся снова» соптимизирован: мы знаем, что его результатом были бы те же значения, что уже записаны в общие переменные обогнавшим потоком; поэтому этот этап можно и не выполнять. В случае с инициализацией переменных,
Другой «соптимизированный» вариант модели — «сделай, запиши,(отчайся)». В нём тоже нет цикла: если запись нового значения не удаётся, функция считает неудачу фатальной, и воздерживается от дальнейших попыток. Так устроена, например,
Если общая переменная — не число, а указатель, — то нужно позаботиться, чтоб не возникло уже упомянутой «проблемы ABA», когда тот же самый указатель указывает на уже новый объект. При инициализации статических объектов не потребуется дополнительных сложностей: указатель может поменяться только с NULL на нечто, и, однажды став не-NULL, указатель больше не меняется. Если же указатель может изменяться произвольным образом, то, как правило, в общей переменной объединяют этот указатель и «номер версии», который увеличивается при каждом изменении указателя.
В следующем примере использования модели «сделай, запиши,(попытайся снова)» в общей переменной как раз будет храниться номер версии. Для начала, две вспомогательных функции:
В отличие от чтения переменных LONG напрямую, эти функции накладывают ограничения на порядок записи в память. Поскольку сравниваемое и новое значение в операции
В качестве
Итак, наш пример:
Мы берём старое значение номера версии, и начинаем наши вычисления. Берём мы его операцией Acquire, так что прочитанный номер версии записан в память прежде, чем значения цветов, которые мы используем для вычислений.
Когда вычисления завершены, мы сравниваем текущий номер версии с сохранённым. Если они не совпадают, значит, цвета поменялись в ходе наших вычислений, так что их придётся переделать.
Проблема ABA возможна, если цвета в ходе вычислений поменялись четыре миллиарда раз: из-за переполнения счётчика мы этого не заметим. Ясно, что в действительности такое вряд ли может произойти.
for (;;) {
// берём начальное значение общей переменной,
// которую мы собираемся изменять
oldValue = sharedVariable;
... берём начальные значения других параметров ...
newValue = ... вычисляем новое значение, используя
oldValue и копии остальных параметров ...
// вместо Xxx может быть Acquire, Release, или ничего
if (InterlockedCompareExchangeXxx(
&sharedVariable,
newValue, oldValue) == oldValue) {
break; // запись удалась
}
... удаляем newValue ...
} // попытаемся снова
Мы вычисляем новое значение, и затем вызовом
InterlockedCompareExchange записываем его в общую переменную только в том случае, если её значение не изменялось. Если оно изменилось, значит другой поток нас опередил; в этом случае попытаемся выполнить операцию по-новой, с самого начала, — в надежде, что в следующий раз никто нас не «подрежет».Важно понимать, что модель «сделай, запиши, попытайся снова» не гарантирует, что поток, первым начавший обновлять значение переменной, первым выиграет «гонку». «Неудачливый» поток может при каждой попытке вновь и вновь уступать более быстрым соперникам; теоретически возможно, что он вообще никогда не завершит начатую операцию (зато каждый из обгоняющих его потоков завершит свою). Такая особенность типична для беззамочных алгоритмов — в отличие от замков, реализующих, как правило, очередь ожидания: первый пришёл — первый прошёл.
Переводчик дерзнул придумать собственную аналогию: касса в «Макдональдсе» — замок, за которым выстраивается очередь ожидающих клиентов. Если клиент, стоящий у кассы, битый час роется по карманам в поисках мелочи, то и остальные клиенты, и кассир впустую томятся в ожидании; система в целом простаивает. С другой стороны, официант в ресторане — беззамочный ресурс. Каждый клиент его подзывает, чтобы расплатиться за обед; но другой клиент может «встрять» и перехватить официанта по дороге. Неизвестно, сколько раз официанта отвлекут, пока он дойдёт наконец до вашего столика; но с другой стороны, если он к вам не подходит, значит сейчас он обслуживает кого-то другого. В целом система не простаивает.
Функция
InterlockedMultiply из прошлого поста соответствует приведённому здесь шаблону почти дословно: «другой параметр» — это множитель, передаваемый параметром функции; «новое значение» — произведение. Если запись нового значения не удалась, значит, кто-то другой его изменил, и мы начинаем операцию снова.Инициализация статических переменных в прошлом посте также соответствует модели «сделай, запиши,(попытайся снова)», просто этап «попытайся снова» соптимизирован: мы знаем, что его результатом были бы те же значения, что уже записаны в общие переменные обогнавшим потоком; поэтому этот этап можно и не выполнять. В случае с инициализацией переменных,
InterlockedCompareExchange используется в варианте Release, потому что новое значение действительно только вместе с другими данными в памяти (только вместе с a), и должно записаться только после них.Другой «соптимизированный» вариант модели — «сделай, запиши,(отчайся)». В нём тоже нет цикла: если запись нового значения не удаётся, функция считает неудачу фатальной, и воздерживается от дальнейших попыток. Так устроена, например,
TryEnterCriticalSection. В ней используется InterlockedCompareExchangeAcquire: изменения, выполненные изнутри критической секции, не должны записаться в память раньше, чем запишется, что секция занята.Если общая переменная — не число, а указатель, — то нужно позаботиться, чтоб не возникло уже упомянутой «проблемы ABA», когда тот же самый указатель указывает на уже новый объект. При инициализации статических объектов не потребуется дополнительных сложностей: указатель может поменяться только с NULL на нечто, и, однажды став не-NULL, указатель больше не меняется. Если же указатель может изменяться произвольным образом, то, как правило, в общей переменной объединяют этот указатель и «номер версии», который увеличивается при каждом изменении указателя.
В следующем примере использования модели «сделай, запиши,(попытайся снова)» в общей переменной как раз будет храниться номер версии. Для начала, две вспомогательных функции:
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);
}
В отличие от чтения переменных LONG напрямую, эти функции накладывают ограничения на порядок записи в память. Поскольку сравниваемое и новое значение в операции
InterlockedCompareExchange совпадают, то при любом исходе операции проверяемое значение не изменяется. Выполняемые действия аналогичны коду:if (*pl == lUnlikely) *pl = lUnlikely;
В качестве
lUnlikely Реймонд советует выбирать маловероятное значение, чтобы в большинстве случаев присваивание не выполнялось, и блок кэша не «пачкался». (Не на всех процессорах это позволяет предотвратить запись в память, но лишней такая хитрость не будет.)Итак, наш пример:
LONG g_lColorChange; // номер версии цветов
...
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);
... прочие вычисления с использованием GetSysColor(...)
} while (InterlockedReadRelease(
&g_lColorChange, -1) != lColorChangeStart);
return iResult;
}
Мы берём старое значение номера версии, и начинаем наши вычисления. Берём мы его операцией Acquire, так что прочитанный номер версии записан в память прежде, чем значения цветов, которые мы используем для вычислений.
Когда вычисления завершены, мы сравниваем текущий номер версии с сохранённым. Если они не совпадают, значит, цвета поменялись в ходе наших вычислений, так что их придётся переделать.
Проблема ABA возможна, если цвета в ходе вычислений поменялись четыре миллиарда раз: из-за переполнения счётчика мы этого не заметим. Ясно, что в действительности такое вряд ли может произойти.
