[C++]C++并发编程实战Chapter7

7 设计无锁数据结构

定义和推论

算法和数据结构中只要采用了互斥、条件变量或future进行同步操作，就称之为阻塞型算法和阻塞型数据结构。操作系统往往会把被阻塞的线程彻底暂停，并将其时间片分配给其他线程，等到有线程执行了恰当的操作，阻塞方被解除。

非阻塞型数据结构

class spinlock_mutex
{
    std::atomic_flag flag;
public:
    spinlock_mutex():
        flag(ATOMIC_FLAG_INIT)
    {}
    void lock()
    {
        while(flag.test_and_set(std::memory_order_acquire));
    }
    void unlock()
    {
        flag.clear(std::memory_order_release);
    }
};

之前实现的自旋锁虽然不存在阻塞调用，但是仍然存在互斥，任何时刻只有一个线程能够锁定。因此，只分析非阻塞/阻塞，无法判断其适用性，需要根据一下条款进行进一步判断：

• 无阻碍（obstruction-free）：假定其他线程全都暂停，则目标线程将在有限步骤内完成自己的操作。
• 无锁（lock-free）：如果多个线程共同操作同一份数据，那么在有限步骤内，其中某一线程能够完成自己的操作。
• 免等（wait-free）：在某份数据上，每个线程经过有限步骤就能完成自己的操作，即便该份数据同时被其他多个线程所操作。

无锁数据结构