воскресенье, 5 июля 2009 г.

Interlocked операции не решают всего

Это перевод Interlocked operations don't solve everything. Автор: Реймонд Чен.

Interlocked-операци являются высоко-производительным способом по атомарному обновлению значений размером DWord или Pointer. Заметьте, однако, что это не означает, что вы можете избежать использования критической секции.

Например, предположим, что у вас есть критическая секция, которая защищает переменную, а в какой-то другой части кода вы хотите атомарно изменить эту переменную. "Ну," - говорите вы, - "это простой инкремент, так что я пропущу критическую секцию и просто вызову InterlockedIncrement. У-ху, я избежал падения производительности для критической секции".

Ну, только вот весь смысл критических секций в том, чтобы гарантировать, что никто не изменит значение защищаемых переменных, пока вы держите критическую секцию. А вы сейчас взяли и изменили значение за спиной у этого кода.

И наоборот, некоторые люди предложили эмуляцию сложных interlocked-операций использованием критической секции, чья работа заключается в том, чтобы защищать переменные.

Например, вы могли бы написать InterlockedMultiply, которая делает следующее:
// Неверно!
function InterlockedMultiply(var plMultiplicand: Integer; lMultiplier: Integer): Integer;
begin
  EnterCriticalSection(SomeCriticalSection);
  try
    plMultiplicand := plMultiplicand * lMultiplier;
    Result := plMultiplicand;
  finally
    LeaveCriticalSection(SomeCriticalSection);
  end;
end;
Хотя этот код действительно защищает вас от одновременного выполнения InterlockedMultiply двумя потоками для одной переменной, он не может защитить от другого кода, выполняющего атомарную операцию с переменной. Рассмотрим такой код:
var
  X: Integer = 2;

procedure TThread1.Execute;
begin
  InterlockedIncrement(X);
end;
 
procedure TThread2.Execute;
begin
  InterlockedMultiply(X, 5);
end;
Если бы InterlockedMultiply была бы на самом деле атомарной, то единственными возможными результатами могли бы быть X = 15 (если interlocked-инкремент выполняется перед interlocked-умножением) или X = 11 (если interlocked-умножение выполняется перед interlocked-инкрементом).

Но поскольку она не по-настоящему атомарна, вы можете получать странные результаты:
Поток 1Поток 2
X = 2 при старте
InterlockedMultiply(X, 5)
EnterCriticalSection
чтение X (читает 2)
InterlockedIncrement(X);
X теперь = 3
* 5 (результат: 10)
запись x (пишет 10)
LeaveCriticalSection
X = 10 в конце

О, нет, наше "interlocked"-умножение получилось ни разу не interlocked!

Как мы можем это исправить?

Если вы хотите выполнить операцию, которая зависит только от некоторого начального значения и своих аргументов (без зависимости от других данных, типа глобальных переменных), вы можете написать свою "функцию в стиле interlocked" с помощью функции InterlockedCompareExchange.
function InterlockedMultiply(var plMultiplicand: Integer; lMultiplier: Integer): Integer;
var
  lOriginal: Integer;
begin
  repeat
    lOriginal := plMultiplicand;
    Result := lOriginal * lMultiplier;
  until (InterlockedCompareExchange(plMultiplicand, Result, lOriginal) = lOriginal);
end;
Чтобы выполнить сложное действие по умножению, мы выполняем три шага.

Во-первых, захватываем значение из памяти:
  lOriginal := plMultiplicand;
Во-вторых, вычисляем желаемый результат по захваченному значению и аргументам функции:
  Result := lOriginal * lMultiplier;
В-третьих, сохраняем результат, но только при условии, что значение не поменялось:
  InterlockedCompareExchange(plMultiplicand, Result, lOriginal)
Если значение поменялось, тогда это означает, что interlocked-операция была неуспешной, потому что кто-то поменял значение, пока мы делали свои вычисления. В этом случае мы повторяем все действия заново.

Если вы пробежитесь по сценарию в табличке выше с новой функцией InterlockedMultiply, то вы увидите, что сразу после выполнения InterlockedIncrement цикл заметит, что значение X изменилось и перезапустится. Поскольку решающее (конечное) обновление "X" производится функцией InterlockedCompareExchange, то результат вычисления будет сохранён только при условии, что "X" не поменял своего значения.

Заметьте, что эта техника работает только если выполняемая операция является чистой функцией (pure function) от начального значения и аргументов функции. Если для выполнения вычислений вы должны получать доступ к другой памяти (к ещё одному значению, например), то эта техника не будет работать!
Потому что эта другая память может быть изменена во время вычислений и вы об этом никак не узнаете, поскольку InterlockedCompareExchange проверяет только память для одного значения.

Если вы не прислушаетесь к этим словам, то получите проблему, известную как "ABA Problem". Я оставляю эту тему для самостоятельного гугления. К счастью, все, кто пишут о этой проблеме, также пишут о том, как решить ABA-проблему, так что я оставлю вам и это тоже.

Когда вы прочитаете о ABA-проблеме и её решении, вы должны быть в курсе, что решение уже реализовано для вас в виде

Interlocked функции SList
.

8 комментариев:

  1. Смешивать Interlocked-ф-ии и критические секции для одной расшаренной области памяти не очень удачная идея ИМХО

    ОтветитьУдалить
  2. Так вроде заметка как раз про это?

    ОтветитьУдалить
  3. TThread1.Create(False)
    TThread2.Create(False)

    у меня 15 получається.

    ОтветитьУдалить
  4. Как получить другой результат?

    ОтветитьУдалить
  5. Поведение потоков зависит от того, как выпадут кубики. В данном случае - как планировщик системы выделит время потокам. Вы не можете повлиять на алгоритм планировщика системы. Итого, ответ на "как это изменить" - никак.

    При этом надо понимать, что:
    1. 15 может превратиться в другое число в другой версии Windows, где алгоритм планировщика реализован иначе.
    2. 15 может превратиться в другое число на этой же системе, если по крайне маловероятному (но возможному) стечению обстоятельств система прервёт поток 2 после чтения X (например, в результате запуска третьего потока с высоким приоритетом именно в этот момент и ни тактом раньше или позже).

    Итого, то, что конкретно в какой-то ситуации получен правильный или неправильный результат - в случае многопоточности ничего не значит. Он может быть правильным в 999 случаях из 1000.

    Как делать правильно в данном конкретном случае - показано в заметке (InterlockedCompareExchange).

    ОтветитьУдалить
  6. Спасибо за розгорнутый ответ

    ОтветитьУдалить
  7. А почему бы при доступе к глобальным пермеменным не воспользоваться более простым и надёжным способом?

    var
    Lock: integer;

    {Lock Initialization}
    Lock := -1;

    {Entering the spin lock}
    while InterlockedIncrement(Lock) > 0 do
    begin
    Dec(Lock);
    Sleep(0);
    end;

    {Leaving the spin lock}
    Dec(Lock);

    © Martin Harvey 2000.

    ОтветитьУдалить
  8. А вы заметку читали? В ней речь идёт о том, что нельзя смешивать Interlocked-операцию с другим механизмом синхронизации. Надо либо одно, либо другое, но не оба сразу. Смысл заметки не меняется, если заменить критическую секцию на любой другой механизм (включая spin-блокировку). Вторая часть заметки говорит, как можно обойтись Interlocked-операциями без привлечения иных механизмов синхронизации.

    ОтветитьУдалить

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку.

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

Ваше сообщение может быть помечено как спам спам-фильтром - не волнуйтесь, оно появится после проверки администратором.

Примечание. Отправлять комментарии могут только участники этого блога.