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

Question

Я написал простой стековый узел (Delp [hi XE4, Win7-64, 32-битное приложение), где я могу иметь несколько «стеков» и поп/push узлов между ними из разных потоков одновременно. Он работает 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. Выполняет ли этот код превосходный стековый стоп-код? Что еще я могу посмотреть? Это невозможно отлаживать нормально, поскольку ошибки происходят в разных местах, сообщая мне, что где-то происходит коррупция с указателем или RAM. Я также получаю повторяющиеся записи, а это означает, что узел, который был выбит из одного стека, а затем вернулся в тот же стек, все еще находится поверх старого стека ... Невозможно выполнить согласно моему алгоритму? Это заставило меня поверить, что можно нарушать методы Delphi/Windows InterlockedCompareExchange или есть некоторые скрытые знания, которые мне еще предстоит выявить. :) (Я также пробовал TInterlocked)

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

Любые советы будут оценены.

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

Answer 1

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

Однако, считаю, что это из метода Pop:

NewHead:=Result.Next; 
if InterlockedCompareExchangePointer(Pointer(Head),NewHead,Result)=Result 

• Если нить выгружена после первой строки.
• Значение для NewHead хранится в локальной переменной.
• Затем другой поток успешно удаляет узел, этот поток был нацелен.
• Он также удаляет один и тот же узел назад, но с другим значением для Next до возобновления первого потока.
• Вторая строка передает проверку сравнения, позволяющую головке получать значение NewHead из локальной переменной.
• Однако текущее значение для NewHead неверно, тем самым повреждая ваш стек.

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

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

---

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

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

• Вы понимаете, насколько быстрыми являются компьютеры?
• Вы понимаете, что GetTickCount будет генерировать множество дубликатов в узкой петле?
• I.e. номера, которые вы создаете, будут ничего подобного случайных.
• И когда комментарии не согласны с кодом, мои Паучок-смысловые пинки в

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

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

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