multithreading - Delphi [volatile]和InterlockedCompareExchange不可靠吗？

Question

我编写了一个简单的无锁节点堆栈(Delp [hi XE4，Win7-64，32位应用程序])，在其中我可以同时从多个线程中获得多个“堆栈”和pop/push节点。
它可以在99.999％的时间内工作，但最终会在使用所有CPU内核的压力测试下出现毛刺。

简而言之，它可以归结为以下内容(不是真实的/编译的代码):
节点为:

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个线程，每个线程执行40万个push/pop，通常在进行这些测试几个周期后便会崩溃(安全地由于检查/引发异常)，有时很多测试周期会在一次突然崩溃之前完成。

任何意见，将不胜感激。

问候
安东
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的当前值不正确，从而损坏了堆栈。

测试应用程序甚至都无法解决这个问题上的细微变化。在测试应用中不会检查此问题，因为直到测试结束，您才销毁任何节点。

查看当前头部

另一个线程弹出一些节点。

销毁节点，并创建和推送新节点。

当“寻找线程”再次处于 Activity 状态时，它可能正在寻找一个完全不同的节点，该节点恰巧位于同一地址。

如果正在弹出，则可以将垃圾指针分配给Head。

除了上述...
查看您的测试应用程序，还有一些真正的躲避代码。例如。

您生成一个“随机数”:J:=GetTickCount and 7;(*Get a 'random' number 0..7*)。

您知道计算机有多快吗？

您是否知道GetTickCount会在紧密循环中生成大量重复项？

即您生成的数字将不会像随机数。

当注释与代码不一致时，我的 spy 意识就会开始。

您正在分配硬编码大小的内存:GetMem(zTmp,12);(*Allocate new node*)。

为什么不使用SizeOf？

您正在使用多平台编译器。...该结构的大小可能有所不同。

绝对没有理由对结构的大小进行硬编码。

现在，考虑到这两个示例，我不会完全相信您的测试代码中也没有错误。