无锁序列系列笔记

下面是常见的一些实现方式：

1、借助智能指针来实现。下面是一篇参考博文

2、借助automic使用CAS(Compare And Swap)原子操作,

std::atomic_flag，不同于所有 std::atomic 的特化，它保证是免锁的，不提供load()与store(val)操作，但提供了test_and_set()与clear()操作，其中test_and_set()就是支持RMW的原子操作，可用std::atomic_flag实现自旋锁的功能

//atomic2.cpp 使用原子布尔类型实现自旋锁的功能

#include <thread>
#include <vector>
#include <iostream>
#include <atomic>
 
std::atomic_flag lock = ATOMIC_FLAG_INIT;       //初始化原子布尔类型
 
void f(int n)
{
    for (int cnt = 0; cnt < 100; ++cnt) {
        while (lock.test_and_set(std::memory_order_acquire))  // 获得锁
             ; // 自旋
        std::cout << n << " thread Output: " << cnt << '\n';
        lock.clear(std::memory_order_release);               // 释放锁
    }
}
 
int main()
{
    std::vector<std::thread> v;     //实例化一个元素类型为std::thread的向量
    for (int n = 0; n < 10; ++n) {
        v.emplace_back(f, n);       //以参数(f,n)为初值的元素放到向量末尾，相当于启动新线程f(n)
    }
    for (auto& t : v) {     //遍历向量v中的元素，基于范围的for循环，auto&自动推导变量类型并引用指针指向的内容
        t.join();           //阻塞主线程直至子线程执行完毕
    }

    getchar();
    return 0;
}

更复杂的数据结构（自定义数据结构）实现五锁化其实只是将颗粒度变小，在最低颗粒度上还是有锁操作，下面是基于CAS实现的一个无锁栈：

//atomic3.cpp 使用CAS操作实现一个无锁栈

#include <atomic>
#include <iostream>

template<typename T>
class lock_free_stack
{
private:
    struct node
    {
        T data;
        node* next;
        node(const T& data) : data(data), next(nullptr) {}
    };
    std::atomic<node*> head;

 public:
    lock_free_stack(): head(nullptr) {}
    void push(const T& data)
    {
        node* new_node = new node(data);
        do{
            new_node->next = head.load();   //将 head 的当前值放入new_node->next
        }while(!head.compare_exchange_strong(new_node->next, new_node));
        // 如果新元素new_node的next和栈顶head一样，证明在你之前没人操作它，使用新元素替换栈顶退出即可；
        // 如果不一样，证明在你之前已经有人操作它，栈顶已发生改变，该函数会自动更新新元素的next值为改变后的栈顶；
        // 然后继续循环检测直到状态1成立退出；
    }
    T pop()
    {
        node* node;
        do{
            node = head.load();
        }while (node && !head.compare_exchange_strong(node, node->next));

        if(node) 
            return node->data;
    }
};
 
int main()
{
    lock_free_stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    std::cout << s.pop() << std::endl;
    std::cout << s.pop() << std::endl;
    
    getchar();
    return 0;
}