读书笔记——C++高性能编程（六）

第六章.并发和性能

阿姆达尔定律

介绍了阿姆达尔定律（Amdahl's Law），这个定律的意义是“系统中对某一部件采用更快执行方式所能获得的系统性能改进程度，取决于这种执行方式被使用的频率”。具体的公式如下：

其中s0是程序并行部分的加速比例，p是程序并行的部分。

举例说明：假设一个程序在8线程下运行，并行运行的比例是50%（8线程可以认为是8倍速度运行）。那么其加速效果是：

而当并行比例提高到80%的时候，加速比例能够达到3.33。这个结果说明这样两个事实：提高并行比例可以让程序运行的更快；多线程程序应该尽量少地访问共享数据。

原子操作

介绍了原子操作关于内存序是和原子操作实现相关的，而且原子操作请求自由内存序也不会使其更快。由于原子操作的指令集极其小，所以有些操作需要通过CAS来实现。原子操作的实现原理来自于CPU对cache-line的独占访问，这也意味着实际上原子操作也是一个不需要经过操作系统的“锁”。

介绍以下wait-free和lock-free:

std::atomic<size_t> count;
...在线程中...
count.fetch_add(1, std::memory_order_relaxed);

上面这个是一个wait-free的代码，仅仅是从代码层面看是不需要等待的（wait-free），但是如上所述，在机器的层面其还是会存在硬件层面的锁定。

std::atomic<size_t> count;
...线程中...
size_t c = count.load(std::memory_order_relaxed);
while (!count.compare_exchange_strong(c, c+1, std::memory_order_relaxed, std::memory_order_relaxed)){}

上面这个是lock-free的代码。这个里面可以看到，从代码层面，线程会有可能被困在while循环中，但是没有用到系统的锁操作，因此称为lock-free。

总结一下：

1）无等待：每个线程都在执行它需要的操作，并始终朝着最终目标前进；无需等待访问，无需重做任何操作。（也就是说不需要“试错-会滚-重做”的操作）

2）无锁：多个线程会共享一个值，但只有一个会成功，其余的将不得不根据原始值丢弃它们已经完成的工作，读取更新后的值，并再次进行计算。但是至少有一个线程总是可以保证提交其工作而不必重做。因此，整个程序总是在向前推进，尽管不一定是全速前进。

3）有锁：一个线程持有锁，但是可以不做任何事情（因为这里锁并没有提交的保证，而原子操作是有提交保证的）。并发发生时候，最多只有一个线程在向前推进，并且即使如此也不能保证它一定前进。

自旋锁

class Spinlock
{
public:
    void lock()
    {
        while(flag_.exchange(1, std::memory_order_acquire));
    }
    void unlock()
    {
        flag_.store(0, std::memory_order_release);
    }
private:
    std::atomic<unsigned int> flag_;
};

上面这个是自旋锁的简单实现，这里要插入讲以下的是内存序。可以看到，加锁用的是acquire，解锁用的是release。acquire会防止本线程的所有读操作移动到该行以后，也就意味着，写操作可以跑到前面去。release操作会保证所有的写操作都在该行之前完成。也就是说，在上锁处，所有的读操作已经完成，在解锁处所有的写操作已经完成。

还有一个知识点，cache-line的独占访问。看一下优化后的加锁代码：

class Spinlock
{
public:
    void lock()
    {
        while ( flag_.load(std::memory_order_relaxed)||flag_.exchange(1, std::memory_order_acquire));
    }
};

这个优化版本只是在原来上锁之前增加了一个load操作，为什么能够起到优化的效果呢？因为load不需要独占访问，上锁线程已经改变该值，各CPU缓存中是最新的值。此时如果调用exchange，则需要各个线程再锁定cache-line，如果有多个等待线程，则所有等待线程的访问不是并行的，而load是读，是可以多个等待线程并行的访问的。（当然我觉得这个优化毫无必要，只是多个线程更快地在自旋中消耗CPU资源，但是这个思想比较有意义）

还有一个细节，就是操作系统的偏好问题。操作系统更偏好于将CPU调度给占用大量CPU的线程，而自旋锁会占用大量的CPU，因此操作系统会更偏向于将CPU调度给正在等待的线程，从而导致等待释放自旋锁的线程没有CPU来执行释放。解决方法就是在尝试数次之后让等待线程sleep 1ns或者调用sched_yield来进行。作者实验是nanosleep效果更好。

作者实验了有锁/wait-free/lock-free/自旋锁，发现自增的情况下自旋锁速度更快。但是自旋锁有其问题，是其忙等消耗CPU的问题。系统锁其上锁成本很高，因此需要长的临界区来均摊上锁和解锁成本，而短且冲突不那么频繁的临界区，自旋锁通常效果更好。

锁和无锁的问题

系统锁会出现死锁/活锁/护送/优先级反转的问题，原子操作不会。但是原子操作的主要问题在于2点：1，上锁浪费大量CPU资源；2，原子操作对于数据同步可能有各种不同的状态，需要保证在所有这些不同的同步状态下程序的处理逻辑都正确。

自旋指针

自旋指针用于多线程访问同一个指针的情况，其原理和自旋锁一样，只不过不是处理数字而是指针。

template<typename T>
class PtrSpinLock
{
public:
    explicit PtrSpinlock(T* p):p_(p){}
    T* lock()
    {
        T*  p_cur = nullptr;
        while (!(p_cur = p_.exchange(nullptr, std::memory_order_acquire)));
        saved_p_ = p_cur;
        return p_cur;
    }
    void unlock()
    {
        p_.store(saved_p_, std::memory_order_release);
    }
private:
    std::atomic<T*> p_;
    T* saved_p_ = nullptr;
};

这个是对原书上的代码进行了一些修改。意思就是说在获取不到指针的时候就一直循环获取，直到获取到后将指针返回，并修改之前的指针值。（扩展一下，无所链表主要难点在于验证其尾指针的同时不能修改其next指针的值。可以用这个自旋指针，这样如果尾指针在修改的时候可以保证pop函数不能弹出其尾指针，从而能够修改其next值并放回）

发布协议

发布协议就是在一个用于保证多个线程访问同一个对象时候必须做到以保证线程安全的操作。考虑单生产者和单消费者，协议包括：

1）生产者独占正在准备的数据；2）使用者使用共享指针访问；3）使用者线程访问数据的唯一途径是通过根指针，并且该指针保持为空，直到生产者线程准备好显示或者发布数据。4）使用者随时通过原子方式查询，生产者在发布后不对发布的数据进行修改。

自己的一点思考：在无锁链表中，会存在头指针获取最后一个元素时尾指针正在插入的情况，是否可以通过发布协议的方式进行优化。

并发编程的智能指针

shared_ptr如果是多个线程的不同副本指向同一个对象则是线程安全的。如果是多个线程共享一个智能指针对象则是不安全的。因为对于同一个智能指针的成员的操作不是线程安全的。我们就想到有一个办法。在C++20中使用std::atomic<std::shared_ptr<T>>来保证复制的安全性，在复制完后在各个线程中的副本就安全了。

在不支持C++20的编译器上可以使用如下代码实现原子共享指针：

/// 设置 ///
std::shared_ptr<T> p_;
T* data = new T;
...完成data初始化...
std::atomic_store_explicit(&p_, std::shared_ptr<T>(data), std::memory_order_release);

/// 获取 ///
std::shared_ptr<T> p_;
const T* data = std::atomic_load_explicit(&p_, std::memory_order_acquire).get();

本章总结：

知道了阿姆达尔定律的意义，对于并行编程而言就是增加并行程度。学习了lock-free和wait-free的区别，这俩都是代码层面的，lock-free是用cas等待，wait-free就是原子操作。学习了共享指针的特性，了解了其效率很低的事实。知道了如何在线程间共享指针。