無鎖編程中的常見技術

一、讀寫鎖（Read-Write Lock）

讀寫鎖允許多個讀取線程同時訪問共享資源，只要沒有線程試圖對資源進行寫操作。當有寫操作時，所有的讀取線程和寫入線程都必須等待寫入完成，然後才能繼續操作。讀寫鎖的方式比互斥鎖的方式更有效，因為多個線程可以同時對共享資源進行讀取操作。

下面是一個使用C++11中std::shared_mutex實現的簡單讀寫鎖：

#include 

std::shared_mutex rwlock;

void readData()
{
    std::shared_lock lock(rwlock);
    // 讀取操作
}

void writeData()
{
    std::unique_lock lock(rwlock);
    // 寫入操作
}

二、無鎖隊列（Lock-Free Queue）

無鎖隊列可以提高並發程序的性能，因為它允許多個線程同時讀取和寫入數據。在無鎖隊列中，每個線程都可以訪問共享資源而不會被阻塞，因此無鎖隊列比鎖的方式更有效。

下面是一個使用C++11中std::atomic實現的簡單無鎖隊列：

#include 
#include 

template
class LockFreeQueue
{
private:
    struct Node
    {
        T data;
        std::atomic next;
    };
    std::atomic head;
    std::atomic tail;

public:
    LockFreeQueue()
    {
        Node* dummy = new Node();
        head.store(dummy);
        tail.store(dummy);
    }

    void enqueue(const T& data)
    {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->next = nullptr;

        Node* prev = tail.exchange(newNode);
        prev->next = newNode;
    }

    bool dequeue(T& result)
    {
        Node* next = head.load()->next.load();
        while(next != nullptr)
        {
            if(head.compare_exchange_strong(next, next->next.load()))
            {
                result = next->data;
                delete next;
                return true;
            }
            next = head.load()->next.load();
        }
        return false;
    }
};

三、CAS算法（Compare and Swap）

CAS算法是無鎖編程中的重要算法之一，它可以保證共享資源被多個線程同時訪問時不會導致錯誤的結果。CAS算法包括三個參數：一個內存位置V、一個期望值A、一個新值B。如果當前內存位置的值等於期望值A，那麼把這個位置的值修改為新值B。否則，將不會修改這個位置，返回當前內存位置的值。

下面是一個使用C++11中std::atomic實現的CAS算法：

template
class Atomic
{
private:
    std::atomic _value;

public:
    Atomic(T value)
    {
        _value.store(value);
    }

    T get()
    {
        return _value.load();
    }

    bool compareAndSet(T expect, T update)
    {
        return _value.compare_exchange_strong(expect, update);
    }
};

四、ABA問題及避免方法

在無鎖編程中，一個常見的問題是ABA問題。當一個線程讀取一個共享資源後，該資源被另一個線程修改，然後又被修改回原來的值，此時該資源的值與之前的值相同，但已經不是同一個對象。如果第一個線程再次寫入該值，就會出現意想不到的錯誤。

為了避免ABA問題，可以使用標記（tag）來對共享資源進行版本控制，以確保寫入的值與讀取的值相同：

class AtomicReference
{
private:
    std::atomic<std::pair> _pair;

    uintptr_t incrementTag(uintptr_t tag)
    {
        return tag + 1;
    }

public:
    AtomicReference(T value, uintptr_t tag = 0)
    {
        _pair.store(std::make_pair(value, tag));
    }

    std::pair get()
    {
        return _pair.load();
    }

    bool compareAndSet(const std::pair& expect, const std::pair& update)
    {
        return _pair.compare_exchange_strong(expect, update);
    }

    bool compareAndSet(T expect, T update, uintptr_t expectTag)
    {
        std::pair expectPair(expect, expectTag);
        std::pair updatePair(update, incrementTag(expectTag));
        return compareAndSet(expectPair, updatePair);
    }
};

五、無鎖計數器（Lock-Free Counter）

無鎖計數器可以使多個線程同時累加計數器變量而不會導致不一致的結果。無鎖計數器包括以下幾個步驟：（1）讀取計數器變量的值；（2）對讀取的值進行累加操作；（3）將累加後的值與讀取的值進行比較，如果相等，則將計數器變量的值更新為累加後的值。

下面是一個使用C++11中std::atomic實現的簡單無鎖計數器：

class LockFreeCounter
{
private:
    std::atomic _count;

public:
    LockFreeCounter()
    {
        _count.store(0);
    }

    void increment()
    {
        long long currentCount = _count.load();
        while(!_count.compare_exchange_weak(currentCount, currentCount + 1));
    }

    long long get()
    {
        return _count.load();
    }
};