无锁的数据结构设计

2020-12-29

作为一种无锁数据结构，意味着线程可以并发访问这个数据结构。当一个线程被调度器挂起时，其他线程必须能够完成自己的工作，而无需等待挂起线程。

无锁数据结构时具有比较/交换操作的数据结构。使用比较/交换操作的原因：当有其他线程同时对指定数据的修改时，代码将尝试恢复数据。当其他线程被挂起时，比较/交换操作执行成功，那么这样的代码就是无锁的。当执行失败时，就需要一个自旋锁，且这个结构就是非阻塞-有锁的结构

无等待数据结构：首先时无锁数据结构，并且，每个线程都能在有限的步数内完成操作，暂且不管其他线程时怎么工作的，由于会和别的线程产生冲突，所以算法可以进行无数次尝试，因此并不是无等待的。使用无锁数据接哦古的主要原因时将并发最大化。互斥锁削弱了结构的并发性。使用无锁数据结构的原因就是鲁棒性。也就是稳定性和健壮性。当线程在无锁数据结构上执行操作，在执行到一半死亡时，数据结构上的数据没有丢失，其他线程依旧可以正常执行。

因为没有任何锁，所以不会存在死锁问题。根据定义，无等待的代码不会存在活锁问题，因为其操作执行步骤是由有上限的。所谓活锁就是两个线程同时尝试修改数据，但每个线程所做的修改操作都会让另一个线程重启，所以两个线程就会陷入循环，多次尝试完成自己的操作。不过活锁的存在时间并不久，因为其依赖于线程的调度。

下面是一个无锁的线程安全链表，在设计的时候要考虑到添加数据以及弹出数据的安全性。

对于链表而言是添加结点和删除结点。添加结点的时候分为三步：1.创建一个新的结点，2.让新结点的next指针指向head结点，3.让head结点指向当前新结点。如果在一个线程中执行第二步，另外一个线程中执行第三步，则会发生data race。可以使用原子的比较/交换解决。对于删除头结点可以分为五步：1.读取当前head指针的值，2.读取head->next 3.设置让head为head->next 4.通过索引node ，返回data数据，5 删除索引结点。在删除的时候要注意内存泄漏以及多线程之间的条件竞争。

代码如下：

template  <typename T>
class lock_free_List{
private:
    struct Node{
        std::shared_ptr<T> _data;
        Node* next;
        Node(T const& data) : _data(std::make_shared<T>(data))
        {}
    };
    std::atomic<Node*> head;
public:
    void Push(T const& val){
        Node* const new_node = new Node(val);
        new_node->next = head.load();
        while(!head.compare_exchange_weak(new_node->next,head));
    }
    std::shared_ptr<T> Pop(){
        Node* node = head.load();
        while(node && !head.compare_exchange_weak(node,head));
        return node ? node->_data : std::shared_ptr<T>();
    }
};