Delphi [volatile] и InterlockedCompareExchange ненадежны?

Я написал простой стек узлов без блокировки (Delp[hi XE4, Win7-64, 32-разрядное приложение), в котором я могу иметь несколько «стеков» и одновременно извлекать/проталкивать узлы между ними из разных потоков. Он работает в 99,999% случаев, но в конечном итоге дает сбой при стресс-тесте с использованием всех ядер ЦП.

Урезанный, он сводится к этому (не настоящий/скомпилированный код): Узлы:

type      POBNode          = ^TOBNode;
[volatile]TOBNode          = record
                    [volatile]Next   : POBNode;
                              Data   : Int64;
                             end;

Упрощенный стек:

type TOBStack  = class
                  private
                   [volatile]Head:POBNode; 
                  function Pop:POBNode;
                  procedure Push(NewNode:POBNode);
                 end;

procedure TOBStack.Push(NewNode:POBNode);
var zTmp : POBNode;
begin;
    repeat
     zTmp:=InterlockedCompareExchangePointer(Pointer(Head),nil,nil);(memory fenced-read*)
     NewNode.Next:=zTmp;
     if InterlockedCompareExchangePointer(Head,NewNode,zTmp)=zTmp
        then break (*success*)
        else continue;
    until false;
end;

function TOBStack.Pop:POBNode;
begin;
 repeat
  Result:=InterlockedCompareExchangePointer(Pointer(Head),nil,nil);(memory fenced-read*)
  if Result=nil
     the exit;
  NewHead:=Result.Next;
  if InterlockedCompareExchangePointer(Pointer(Head),NewHead,Result)=Result
     then break (*Success*)
     else continue;(*Fail, try again*)
 until False;
end; 

Я пробовал много вариантов этого, но не могу заставить его быть стабильным. Если я создам несколько потоков, у каждого из которых есть стек, и все они отправят/вытолкнут в/из глобального стека, в конечном итоге произойдет сбой, но не быстро. Только когда я напрягаю его в течение нескольких минут подряд из нескольких нитей, в тугих петлях.

У меня не может быть скрытых ошибок в моем коде, поэтому мне нужно больше советов, чем задать конкретный вопрос, чтобы это работало на 100% без ошибок, 24/7. Выглядит ли вышеприведенный код нормально для потокобезопасного стека без блокировок? Что еще я могу посмотреть? Это невозможно нормально отладить, так как ошибки возникают в разных местах, говоря мне, что где-то происходит повреждение указателя или ОЗУ. Я также получаю повторяющиеся записи, что означает, что узел, который был извлечен из одного стека, а затем возвращен в тот же стек, все еще находится поверх старого стека... Невозможно ли это в соответствии с моим алгоритмом? Это заставило меня поверить, что возможно нарушить методы Delphi/Windows InterlockedCompareExchange или есть какие-то скрытые знания, которые мне еще предстоит раскрыть. :) (я также пробовал TInterlocked)

Я сделал полный тестовый пример, который можно скопировать с ftp.true.co.za. Там я запускаю 8 потоков, выполняющих 400 000 push/pops каждый, и он обычно падает (безопасно из-за проверок/созданных исключений) после нескольких циклов этих тестов, иногда много-много тестовых циклов завершается до того, как один из них внезапно падает.

Любой совет будет принят во внимание.

С уважением Антон Е.


person AntonE    schedule 20.01.2014    source источник
comment
InterlockedCompareExchange отлично работает, если вы передаете ему правильно выровненный адрес. Для рабочего безблокировочного стека, очереди и динамической очереди используйте модуль OtlContainers из проекта www.omnithreadlibrary.com.   -  person gabr    schedule 20.01.2014
comment
Известно, что функции InterlockedXXX работают. Проблема в том, что ваш код этого не делает.   -  person David Heffernan    schedule 20.01.2014
comment
Где документация по этому атрибуту [volatile]?   -  person David Heffernan    schedule 20.01.2014
comment
@DavidHeffernan, см. New Delphi Compiler Attributes.   -  person LU RD    schedule 20.01.2014
comment
@LURD Вы знаете об этом больше? Я так понимаю переменные под компиляторами x86 и x64 всегда были [volatile]. Это влияет только на компиляторы ARM?   -  person David Heffernan    schedule 20.01.2014
comment
@DavidHeffernan, больше я ничего не знаю. Возможно, сканирование источника что-то выявит.   -  person LU RD    schedule 20.01.2014
comment
@LURD Ну, это наверняка должен быть источник компилятора, а у нас его нет. Насколько я понимаю, на компиляторах x86 и x64 использование [volatile] не обязательно, да и операции чтения с ограничением памяти в приведенном выше коде не нужны из-за сильной модели памяти x86 и x64.   -  person David Heffernan    schedule 20.01.2014
comment
@DavidHeffernan, в System.Pas атрибут [volatile] используется в TMonitor, TObject и некоторых других классах. Защита переменных FRefCount. Это, вероятно, что-то, что привнесла ARC, но, похоже, затронуты все платформы.   -  person LU RD    schedule 20.01.2014
comment
Насколько я знаю, [volatile] не работает со старым компилятором (необходима цитата). Таким образом, Win32 и Win64 не затронуты этим.   -  person gabr    schedule 20.01.2014
comment
Не тратя много времени, могу сказать, что ваш код страдает как минимум от проблемы ABA (en.wikipedia.org /wiki/ABA_проблема). Пожалуйста, используйте существующий и хорошо протестированный код (например, OmniThreadLibrary), это бесплатно.   -  person gabr    schedule 20.01.2014
comment
@LURD Я уверен, что габр прав. Компиляторы x86 и x64 никогда не оптимизировали нелокальные переменные в регистры.   -  person David Heffernan    schedule 20.01.2014
comment
Как говорит @gabr, использование проверенного кода — хороший ход. Тестировать многопоточный код сложно. Ожидайте, что ваши тесты будут неадекватными. Знаете ли вы, что Windows поставляется с именно тем кодом, который вам нужен: msdn.microsoft.com/en-us/library/windows/desktop/ms684121.aspx   -  person David Heffernan    schedule 21.01.2014
comment
Насколько я понимаю, [изменчивость] связана с видимостью. например в тесном цикле переменная может быть оптимизирована компилятором, чтобы оставаться в регистре. Атрибут volatile говорит ему «не доверять» переменной и всегда читать ее из памяти. Это просто директива компилятора, она не учитывает Windows или модель памяти.   -  person AntonE    schedule 21.01.2014
comment
Спасибо за комментарии об использовании OTL и других, но я работаю над проектом, которому нужен собственный код для будущих планов переноса платформы.   -  person AntonE    schedule 21.01.2014
comment
@David Компиляторы x86 и x64 никогда не оптимизировали нелокальные переменные в регистры. С ключом «нелокальный», но вы имеете в виду внутри метода (локальные переменные стека) или области видимости объекта? Например. когда несколько потоков запускают объектный метод TMyObj.Hello и читают TMyObj.MyVal в тесном цикле, разве это не было бы (возможно) оптимизировано в регистр? Я все равно включу его, это не имеет значения и может понадобиться в следующем компиляторе для параллельного кода. Я полагаю, что это (действительно) необходимо больше в драйверах устройств и т. Д. При использовании «абсолютных» переменных?   -  person AntonE    schedule 21.01.2014
comment
как говорит @gabr, [volatile] не работает в Windows   -  person David Heffernan    schedule 21.01.2014


Ответы (1)


Сначала я скептически отнесся к тому, что это проблема ABA, как указано gabr. Мне казалось, что: если один поток смотрит на текущий Head, а другой поток толкает, то выскакивает; вы счастливы работать с одним и тем же Head таким же образом.

Однако рассмотрите это из вашего метода Pop:

NewHead:=Result.Next;
if InterlockedCompareExchangePointer(Pointer(Head),NewHead,Result)=Result
  • Если поток заменен после первой строки.
  • Значение для NewHead хранится в локальной переменной.
  • Затем другой поток успешно извлекает узел, на который нацелен этот поток.
  • Ему также удается вернуть тот же узел обратно, но с другим значением для Next, прежде чем возобновится первый поток.
  • Вторая строка будет проходить проверку сравнения, позволяя head получить значение NewHead из локальной переменной.
  • Однако текущее значение для NewHead неверно, что повреждает ваш стек.

Есть небольшая вариация этой проблемы, даже не охваченная вашим тестовым приложением. Эта проблема не проверяется в вашем тестовом приложении, потому что вы не уничтожаете узлы до конца теста.

  • Посмотрите на текущую голову
  • Другой поток извлекает несколько узлов.
  • Узлы уничтожаются, а новые узлы создаются и отправляются.
  • К тому времени, когда ваш «ищущий поток» снова станет активным, он может искать совершенно другой узел, который случайно находится по тому же адресу.
  • Если вы выталкиваете, вы можете назначить указатель мусора на Head.

Помимо всего вышеперечисленного...
Глядя на ваше тестовое приложение, вы также увидите очень хитрый код. Например.

Вы генерируете «случайное число»: J:=GetTickCount and 7;(*Get a 'random' number 0..7*).

  • Вы понимаете, насколько быстры компьютеры?
  • Вы понимаете, что GetTickCount будет генерировать множество дубликатов в замкнутом цикле?
  • т.е. числа, которые вы сгенерируете, будут совсем не случайными.
  • А когда комментарии не согласуются с кодом, срабатывает мое паучье чутье.

Вы выделяете память жестко запрограммированного размера: GetMem(zTmp,12);(*Allocate new node*).

  • Почему вы не используете SizeOf?
  • Вы используете многоплатформенный компилятор... Размер этой структуры может варьироваться.
  • Нет абсолютно никаких причин для жесткого кодирования размера структуры.

Прямо сейчас, учитывая эти два примера, я не был бы полностью уверен, что в вашем тестовом коде также нет ошибки.

person Disillusioned    schedule 20.01.2014
comment
Спасибо за хорошо объясненный ответ. В описанном вами сценарии логично, что я вызываю проблему, повторно используя узлы. В реальной ситуации этот стек будет использоваться в основном с «PopAll»), и узлы будут передаваться «вниз по линии», прежде чем возвращаться в «доступный для повторного использования» (предварительно выделенный) кольцевой буфер. Так что повторное использование (достаточного количества) узлов не должно быть проблемой. Я думаю, что мои тестовые тугие петли вызвали проблему, которой не было бы. Спасибо, что указали на это. - person AntonE; 21.01.2014
comment
@AntonE Я бы на это не рассчитывал. Помните, что вы рискуете не только повторным использованием узлов, но и тем, что узлы могут быть созданы по одному и тому же адресу. Могут быть и другие сценарии риска. - person Disillusioned; 21.01.2014