无锁退避消除堆栈的问题

Question

我不得不编写无锁退避消除堆栈，但由于某种原因它未能通过一些测试。我很确定，我的代码是正确的，这是 QA 的错，但可能有一个我看不到的小错误，这不太可能，因为我的代码非常整洁，几乎完美，经理刚刚雇用了不合格的测试人员。

`公共类 EliminationBackoffStack { 私有堆栈节点？哈；

private class StackNode
{
    public StackNode? Next { get; set; }
    public int Value { get; set; }

    public StackNode(int value, StackNode nextNode)
    {
        this.Next = nextNode;
        this.Value = value;
    }

    public StackNode() { }
}

// 0 - Empty
// 1 - LoadingIteam
// 2 - Waiting
// 3 - Busy

private class Exchanger
{
    public int State;
    public int? Item;

    public Exchanger(int state, int? item)
    {
        State = state;
        Item = item;
    }
}

List<Exchanger> eliminationArray = new List<Exchanger>();

private bool tryPushEliminationArray(int x)
{
    foreach (Exchanger exchanger in eliminationArray)
    {
        if (Interlocked.CompareExchange(ref exchanger.State, 0, 1) == 0)
        {
            exchanger.Item = x;
            exchanger.State = 2;

            Thread.Sleep(1000);

            if (Interlocked.CompareExchange(ref exchanger.State, 2, 3) == 2)
            {
                exchanger.State = 0;
                return false;

            } else
            {
                exchanger.State = 0;
                return true;
            }
        }
       
    }
    return false;
}

public int? Pop()
{
    while (true)
    {
        StackNode? head = H;
        if (Interlocked.CompareExchange(ref H, head.Next, head) == head)
        {
            return head.Value;
        }
        else
        {
            var pair = tryPopEliminationArray();
            if (pair.Item2)
            {
                return pair.Item1;
            }
        }
            
    }
}

private (int?, bool) tryPopEliminationArray()
{
    foreach (Exchanger exchanger in eliminationArray)
    {
        var item = exchanger.Item;
        if (item != null && Interlocked.CompareExchange(ref exchanger.State, 2, 3) == 2)
        {
            return (item, true);
        }
    }
    return (0, false);
}

public void Push(int newValue)
{
    while (true)
    {
        StackNode? head = H;
        if (head == null)
        {
            throw new NullReferenceException();
        }

        var newHead = new StackNode(newValue, head);
        if (Interlocked.CompareExchange(ref H, newHead, head) == head)
        {
            return;
        } else if (tryPushEliminationArray(newValue))
        {
            return;
        }
    }
}

public int Peek() => H.Value;

public EliminationBackoffStack(int exchengerAmount)
{
    this.H = new StackNode();

    for (int i = 0; i < exchengerAmount; i++)
    {
        eliminationArray.Add(new Exchanger(1, null));
    }
}

}`

我使用了最好的技术来实现它。

Answer 1

您的代码几乎是完美的，但是您的代码中可能存在的一个问题可能与 tryPushEliminationArray 方法有关。在此方法中，您将迭代 EliminationArray 并尝试交换 Exchanger 对象的状态。但是，问题是您直接在 Exchanger 对象的状态字段上使用 Interlocked.CompareExchange，但对 Exchanger 对象本身的引用不是原子的。

但我不能认为这是一个严重的问题，你应该和你的 QA 谈谈