Detailed explanation of the example of using CAS to implement lock-free algorithm in C#

public static int CompareExchange(ref int location1, int value, int comparand);
public static long CompareExchange(ref long location1, long value, long comparand);
// ...Other overloading methods are omittedpublic static object CompareExchange(ref object location1, object value, object comparand);
public static T CompareExchange<T>(ref T location1, T value, T comparand) where T : class;

while (true)
{
    // Read data    oldValue = ...;
    // Calculate new value    newValue = ...;
    // CAS updates data    result = CompareExchange(ref location, newValue, oldValue);
    // Determine whether CAS is successful    if (result == oldValue)
    {
        // CAS is successful, perform subsequent operations        break;
    }
}

public class Counter
{
    private int _value;

    public int Increment()
    {
        while (true)
        {
            int oldValue = _value;
            int newValue = oldValue + 1;
            int result = (ref _value, newValue, oldValue);
            if (result == oldValue)
            {
                return newValue;
            }
        }
    }
}

internal void EnsureThreadRequested()
{
    //
    // If we have not yet requested #procs threads, then request a new thread.
    //
    // CoreCLR: Note that there is a separate count in the VM which has already been incremented
    // by the VM by the time we reach this point.
    //
    int count = _separated.numOutstandingThreadRequests;
    while (count < )
    {
        int prev = (ref _separated.numOutstandingThreadRequests, count + 1, count);
        if (prev == count)
        {
            ();
            break;
        }
        count = prev;
    }
}

public class ConcurrentQueue<T>
{
    // _head and _tail are two pseudo-nodes, _head._next points to the first node of the queue, and _tail points to the last node of the queue.    // _head and _tail will be modified and accessed by multiple threads, so they need to be modified with volatile.    private volatile Node _head;
    private volatile Node _tail;
    
    public ConcurrentQueue()
    {
        _head = new Node(default);
        // When _tail points to _head, the queue is empty.        _tail = _head;
    }

    public void Enqueue(T item)
    {
        var node = new Node(item);
        while (true)
        {
            Node tail = _tail;
            Node next = tail._next;
            // Determine whether other threads have modified the time when the value is assigned to next            if (tail == _tail)
            {
                // If next is null, it means that no other thread has modified tail._next from the time of assigning tail to assignment to next.                if (next == null)
                {
                    // If tail._next is null, it means that since the tail is assigned here, no other thread has modified tail._next,                    // tail is still the last node in the queue, so we can directly assign node to tail._next.                    if ((ref tail._next, node, null) == null)
                    {
                        // If _tail == tail, it means that from the previous CAS operation, no other thread has modified _tail, that is, no other thread has performed the Enqueue operation.                        // Then the node of the current thread Enqueue is the last node of the queue, and we can directly assign node to _tail.                        (ref _tail, node, tail);
                        break;
                    }
                }
                // If next is not null, it means that other threads have modified tail._next from the time of assigning tail to assigning next.                else
                {
                    // If no other thread has modified _tail, then next is the last node of the queue, and we can directly assign next to _tail.                    (ref _tail, next, tail);
                }
            }
        }
    }

    public bool TryDequeue(out T item)
    {
        while (true)
        {
            Node head = _head;
            Node tail = _tail;
            Node next = head._next;
            // Determine whether _head has been modified            // If it has not been modified, it means that no other thread has performed the Dequeue operation from the time of assigning value to head to next.            if (head == _head)
            {
                // If head == tail, the queue is empty                if (head == tail)
                {
                    // Although the above has determined whether the queue is empty, we will judge it again here                    // This is to prevent other threads from performing Enqueue operations during the period when assigning tail to assigning next.                    if (next == null)
                    {
                        item = default;
                        return false;
                    }

                    // If next is not null, it means that other threads have modified tail._next from the time when assigning tail to assigning next, which means that other threads have performed Enqueue operations.                    // Then next may be the last node of the queue, and we try to assign next to _tail.                    (ref _tail, next, tail);
                }
                // If head != tail, it means that the queue is not empty                else
                {
                    item = next._item;
                    if ((ref _head, next, head) == head)
                    {
                        // If _head has not been modified                        // Instruction: Since assigning the head value to this point, no other thread has performed the Dequeue operation. The item above is the value of the first node of the queue.                        // We can return directly.                        break;
                    }
                    // If _head has been modified                    // Instruction: From assigning the head value to this point, other threads have performed the Dequeue operation, and the item above is not the value of the first node of the queue.                    // We need to re-execute the Dequeue operation.                }
            }
        }

        return true;
    }

    private class Node
    {
        public readonly T _item;
        public Node _next;

        public Node(T item)
        {
            _item = item;
        }
    }
}

using ;

var queue = new ConcurrentQueue<int>();
var results = new ConcurrentBag<int>();
int dequeueRetryCount = 0;

var enqueueTask = (() =>
{
    // Make sure that the dequeueTask has started running before Enqueue    (10);
    ("Enqueue start");
    (0, 100000, i => (i));
    ("Enqueue done");
});

var dequeueTask = (() =>
{
    (10);
    ("Dequeue start");
    (0, 100000, i =>
    {
        while (true)
        {
            if ((out int result))
            {
                (result);
                break;
            }

            (ref dequeueRetryCount);
        }
    });
    ("Dequeue done");
});

await (enqueueTask, dequeueTask);
(
    $"Enqueue and dequeue done, total data count: {}, dequeue retry count: {dequeueRetryCount}");

var hashSet = ();
for (int i = 0; i < 100000; i++)
{
    if (!(i))
    {
        ("Error, missing " + i);
        break;
    }
}

("Done");