public static int CompareExchange(ref int location1, int value, int comparand);
public static long CompareExchange(ref long location1, long value, long comparand);
// ... 省略其他重載方法
public 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)
{
    // 讀取數(shù)據(jù)
    oldValue = ...;
    // 計(jì)算新值
    newValue = ...;
    // CAS 更新數(shù)據(jù)
    result = CompareExchange(ref location, newValue, oldValue);
    // 判斷 CAS 是否成功
    if (result == oldValue)
    {
        // CAS 成功，執(zhí)行后續(xù)操作
        break;
    }
}

public class Counter
{
    private int _value;

    public int Increment()
    {
        while (true)
        {
            int oldValue = _value;
            int newValue = oldValue + 1;
            int result = Interlocked.CompareExchange(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 < Environment.ProcessorCount)
    {
        int prev = Interlocked.CompareExchange(ref _separated.numOutstandingThreadRequests, count + 1, count);
        if (prev == count)
        {
            ThreadPool.RequestWorkerThread();
            break;
        }
        count = prev;
    }
}

public class ConcurrentQueue<T>
{
    // _head 和 _tail 是兩個(gè)偽節(jié)點(diǎn)，_head._next 指向隊(duì)列的第一個(gè)節(jié)點(diǎn)，_tail 指向隊(duì)列的最后一個(gè)節(jié)點(diǎn)。
    // _head 和 _tail 會(huì)被多個(gè)線程修改和訪問(wèn)，所以要用 volatile 修飾。
    private volatile Node _head;
    private volatile Node _tail;
    
    public ConcurrentQueue()
    {
        _head = new Node(default);
        // _tail 指向 _head 時(shí)，隊(duì)列為空。
        _tail = _head;
    }

    public void Enqueue(T item)
    {
        var node = new Node(item);
        while (true)
        {
            Node tail = _tail;
            Node next = tail._next;
            // 判斷給 next 賦值的這段時(shí)間，是否有其他線程修改過(guò) _tail
            if (tail == _tail)
            {
                // 如果 next 為 null，則說(shuō)明從給 tail 賦值到給 next 賦值這段時(shí)間，沒(méi)有其他線程修改過(guò) tail._next，
                if (next == null)
                {
                    // 如果 tail._next 為 null，則說(shuō)明從給 tail 賦值到這里，沒(méi)有其他線程修改過(guò) tail._next,
                    // tail 依舊是隊(duì)列的最后一個(gè)節(jié)點(diǎn)，我們就可以直接將 node 賦值給 tail._next。                                
                    if (Interlocked.CompareExchange(ref tail._next, node, null) == null)
                    {
                        // 如果_tail == tail，則說(shuō)明從上一步 CAS 操作到這里，沒(méi)有其他線程修改過(guò) _tail，也就是沒(méi)有其他線程執(zhí)行過(guò) Enqueue 操作。
                        // 那么當(dāng)前線程 Enqueue 的 node 就是隊(duì)列的最后一個(gè)節(jié)點(diǎn)，我們就可以直接將 node 賦值給 _tail。
                        Interlocked.CompareExchange(ref _tail, node, tail);
                        break;
                    }
                }
                // 如果 next 不為 null，則說(shuō)明從給 tail 賦值到給 next 賦值這段時(shí)間，有其他線程修改過(guò) tail._next，
                else
                {
                    // 如果沒(méi)有其他線程修改過(guò) _tail，那么 next 就是隊(duì)列的最后一個(gè)節(jié)點(diǎn)，我們就可以直接將 next 賦值給 _tail。
                    Interlocked.CompareExchange(ref _tail, next, tail);
                }
            }
        }
    }

    public bool TryDequeue(out T item)
    {
        while (true)
        {
            Node head = _head;
            Node tail = _tail;
            Node next = head._next;
            // 判斷 _head 是否被修改過(guò)
            // 如果沒(méi)有被修改過(guò)，說(shuō)明從給 head 賦值到給 next 賦值這段時(shí)間，沒(méi)有其他線程執(zhí)行過(guò) Dequeue 操作。          
            if (head == _head)
            {
                // 如果 head == tail，說(shuō)明隊(duì)列為空
                if (head == tail)
                {
                    // 雖然上面已經(jīng)判斷過(guò)隊(duì)列是否為空，但是在這里再判斷一次
                    // 是為了防止在給 tail 賦值到給 next 賦值這段時(shí)間，有其他線程執(zhí)行過(guò) Enqueue 操作。
                    if (next == null)
                    {
                        item = default;
                        return false;
                    }

                    // 如果 next 不為 null，則說(shuō)明從給 tail 賦值到給 next 賦值這段時(shí)間，有其他線程修改過(guò) tail._next，也就是有其他線程執(zhí)行過(guò) Enqueue 操作。
                    // 那么 next 就可能是隊(duì)列的最后一個(gè)節(jié)點(diǎn)，我們嘗試將 next 賦值給 _tail。
                    Interlocked.CompareExchange(ref _tail, next, tail);
                }
                // 如果 head != tail，說(shuō)明隊(duì)列不為空
                else
                {
                    item = next._item;
                    if (Interlocked.CompareExchange(ref _head, next, head) == head)
                    {
                        // 如果 _head 沒(méi)有被修改過(guò)
                        // 說(shuō)明從給 head 賦值到這里，沒(méi)有其他線程執(zhí)行過(guò) Dequeue 操作，上面的 item 就是隊(duì)列的第一個(gè)節(jié)點(diǎn)的值。
                        // 我們就可以直接返回。
                        break;
                    }
                    // 如果 _head 被修改過(guò)
                    // 說(shuō)明從給 head 賦值到這里，有其他線程執(zhí)行過(guò) Dequeue 操作，上面的 item 就不是隊(duì)列的第一個(gè)節(jié)點(diǎn)的值。
                    // 我們就需要重新執(zhí)行 Dequeue 操作。
                }
            }
        }

        return true;
    }

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

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

using System.Collections.Concurrent;

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

var enqueueTask = Task.Run(() =>
{
    // 確保 Enqueue 前 dequeueTask 已經(jīng)開(kāi)始運(yùn)行
    Thread.Sleep(10);
    Console.WriteLine("Enqueue start");
    Parallel.For(0, 100000, i => queue.Enqueue(i));
    Console.WriteLine("Enqueue done");
});

var dequeueTask = Task.Run(() =>
{
    Thread.Sleep(10);
    Console.WriteLine("Dequeue start");
    Parallel.For(0, 100000, i =>
    {
        while (true)
        {
            if (queue.TryDequeue(out int result))
            {
                results.Add(result);
                break;
            }

            Interlocked.Increment(ref dequeueRetryCount);
        }
    });
    Console.WriteLine("Dequeue done");
});

await Task.WhenAll(enqueueTask, dequeueTask);
Console.WriteLine(
    $"Enqueue and dequeue done, total data count: {results.Count}, dequeue retry count: {dequeueRetryCount}");

var hashSet = results.ToHashSet();
for (int i = 0; i < 100000; i++)
{
    if (!hashSet.Contains(i))
    {
        Console.WriteLine("Error, missing " + i);
        break;
    }
}

Console.WriteLine("Done");