线程池 2（第二部分--循环队列）

在考虑如何去设计一个任务容器的时候，其实尝试了很多。最开始的时候直接用的是std::queue容器，主要是看了知乎上面的 “ 基于C++11实现线程池 - 知乎 ”这个帖子，去封装一个安全队列。但是这个操作每次都要上一次锁，实在是太浪费时间了等于每访问一次任务队列，都要所有线程停下来等任务队列操作完，才能继续执行。等于从多线程又回到单线程了。

那么核心问题就是原版STL库不是线程安全的。那么现在的需求就是自己设计一个数据结构，无锁+线程安全。

那么第一反应，c++11的原子操作。

原子操作的原子锁是硬件级别的指令，比mutex快了很多。实际上再线程池中，我们需要保护的内存变量，很少，没有必要用mutex保护整个数据结构和逻辑。

好。现在有了线程安全的解决方向，然后就是数据结构的问题了，用什么数据结构呢。好了，直接去问ChatGPT。

很好的一个思路，循环队列，内部数据类型为函数。

首先设计一个类，去模仿了标准库中vector的实现，三根指针，一个头，一个尾，一个最大容量。

template <typename T>
class BoundedQueue
{
public:using value_type = T;using size_type = uint64_t;public:// 禁用 拷贝赋值运算符 和拷贝构造函数BoundedQueue& operator= (const BoundedQueue& other) = delete;BoundedQueue(const BoundedQueue& other) = delete;BoundedQueue() {}~BoundedQueue();void BreakAllWait();// 初始化   设定队列大小    和   等待策略bool Init(uint64_t size);bool Init(uint64_t size, WaitStrategy* strategy);// 入队操作bool Enqueue(const T& element);// 等待入队操作,当队列满时等待bool WaitEnqueue(const T& elemen);// 出队bool Dequeue(T* element);// 等待出队，当队列为空时，等待出队bool WaitDequeue(T* element);private:// 索引，队里索引下标uint64_t GetIndex(uint64_t num);设定内存对齐方式alignas(64) std::atomic<uint64_t> head_ = { 0 };	// 头alignas(64) std::atomic<uint64_t> tail_ = { 1 };	// 尾alignas(64) std::atomic<uint64_t> commit_ = { 1 };	// 最大容量uint64_t pool_size_ = 0;		// 队列大小T* pool_ = nullptr;		// 当前任务队列的内存指针std::unique_ptr<WaitStrategy> wait_strategy_ = nullptr;volatile bool break_all_wait_ = false;
};

1、首先是防止编译器自动生成默认的复制构造函数和赋值运算符重载函数。在设计一个类的时候必须要考虑到，编译器的默认行为是不是我们必须的。如果不需要就要禁止。

这循环队列只能存在于线程池中，外部是禁止访问的，线程池内也不允许拷贝任务队列。所以该禁止得禁止。

// 禁用 拷贝赋值运算符 和拷贝构造函数BoundedQueue& operator= (const BoundedQueue& other) = delete;BoundedQueue(const BoundedQueue& other) = delete;

2、接下来就是一些需要用到的动作，初始化，入队，出队，任务队列满了等待入队，任务队列空了，等待出队。

public:// 禁用 拷贝赋值运算符 和拷贝构造函数BoundedQueue& operator= (const BoundedQueue& other) = delete;BoundedQueue(const BoundedQueue& other) = delete;BoundedQueue() {}~BoundedQueue();void BreakAllWait();// 初始化   设定队列大小    和   等待策略bool Init(uint64_t size);bool Init(uint64_t size, WaitStrategy* strategy);// 入队操作bool Enqueue(const T& element);// 等待入队操作,当队列满时等待bool WaitEnqueue(const T& elemen);// 出队bool Dequeue(T* element);// 等待出队，当队列为空时，等待出队bool WaitDequeue(T* element);

3、然后就是最关键的

private:// 获取索引，队里索引下标uint64_t GetIndex(uint64_t num);alignas(64) std::atomic<uint64_t> head_ = { 0 };	// 头alignas(64) std::atomic<uint64_t> tail_ = { 1 };	// 尾alignas(64) std::atomic<uint64_t> commit_ = { 1 };	// 最大容量uint64_t pool_size_ = 0;		// 队列大小T* pool_ = nullptr;		// 当前线程池的内存指针std::unique_ptr<WaitStrategy> wait_strategy_ = nullptr;// volatile 关键字告诉编译器在访问该变量时不进行优化，每次都从内存中读取变量的值。// 是否中断所有的等待操作volatile bool break_all_wait_ = false;

这里的这三根指针都是用的原子类去实现的，而且进行了64位的对齐。其实一开始写的时候实际上并没有写内存对齐的逻辑，就直接用的原子类。但是在对整个项目其进行压力测试，然后看看看有什么地方能优化一下，减少一下时间，就发现，整个线程池最耗时间的居然是从任务队列中取出任务这个地方。

然后我们在操作任务队列的时候加了定时器，然后打印出来。发现前几十个任务的访问时间是0.038s，后面就变成了0.121s然后一直都是这个水平，突然这个时间的涨幅3倍多很不正常。然后就看汇编，就一个mov指令，也不应该这么慢啊。源操作数是内存地址，目标操作数是寄存器，从内存地址拷贝数据到一个寄存器，而这个内存数据应该被cache住了，为什么会这么慢呢？

查了一堆资料发现不对劲，是不是出现了内存伪共享了。

当线程A去取出一个任务时，修改了这3个指针的值，同时也让线程B中这3个值也被修改了。虽然当时线程B不关心这3个指针的值，cpu还是重新去内存加载了一遍这个更新后的数据。

发生了线程伪共享！！

线程伪共享：

如果cpu只有一个核，在多线程编程时，每个线程进行切换时，都需要将当前线程的上下文进行保存，然后加载下次要运行的线程的上下文，这就叫做上下文切换。

现代cpu一般都会有多个核，因此实际运行时会有多个线程并行运行，每个核都有独立的缓存，正常情况下并行运行的2个线程如果没有访问或者修改相同内存是不会相互影响。但由于cache line的存在，如果一个线程修改了运行在另外一个核上线程cache line上的某一数据，则此时cpu需要重新加载该cache line上的数据。

为了解决这个问题，使用了内存对齐。

（这个问题我们几个人查了快一个礼拜.....真的是没经验.....）

alignas(64) std::atomic<uint64_t> head_ = { 0 };	// 头
alignas(64) std::atomic<uint64_t> tail_ = { 1 };	// 尾
alignas(64) std::atomic<uint64_t> commit_ = { 1 };	// 最大容量

ps: 不过说实话，要不是压测还真不见得这个问题能被找出来。不过这个地方还真让整个流程，快了差不多0.3s - 0.7s。也算是优化成功了

然后就是每个动作的实现。一组一组的说吧。

1、出队

// 出队
template<typename T>
bool BoundedQueue<T>::Dequeue(T* element) {uint64_t new_head = 0;uint64_t old_head = head_.load(std::memory_order_acquire);do{// 计算新值new_head = old_head + 1;// 如果头位置等于了最大容量  出队失败   队列中没有元素可以取出 new_head == commit_if (new_head == commit_.load(std::memory_order_acquire))return false;// 将要取出的元素复制到 element指向的内存中*element = pool_[GetIndex(new_head)];} while (!head_.compare_exchange_weak(old_head, new_head,std::memory_order_acq_rel,  std::memory_order_relaxed));return true;
}// 等待出队，当队列为空时，等待出队
template<typename T>
bool BoundedQueue<T>::WaitDequeue(T* element) {while (!break_all_wait_) {if (Dequeue(element))return true;if (wait_strategy_->EmptyWait()) {continue;}break;}return false;
}

出队采用的是头出法。利用原子类的特性，设计了一种无锁算法，在多线程的环境下保证线程安全。所有的取值都是原子操作。

等待出队的逻辑是：

如果正常出队失败，则进入等待逻辑，等到等待逻辑结束，重复尝试。

2、入队。

/*入队
*/
template<typename T>
bool BoundedQueue<T>::Enqueue(const T& element) {uint64_t new_tail = 0;	//	更新后的队尾uint64_t old_commit = 0;	//	原最大容量// 获取旧值uint64_t old_tail = tail_.load(std::memory_order_acquire);do{// 计算新值new_tail = old_tail + 1;// 若新值等于了原头head_位置，则表示队列已满，插入失败if (GetIndex(new_tail) == GetIndex(head_.load(std::memory_order_acquire))) {return false;}// 进行tail_值 比较和替换，如果tail_ == old_tail，则使用new_tail作为新值，并且重新作为尾结点// 就是{ if (head_ == old_head) head_ = new_head; } 的原子操作。} while (!tail_.compare_exchange_weak(old_tail, new_tail,std::memory_order_acq_rel, std::memory_order_relaxed));// 将新元素插入到队尾，移动到相应为止pool_[GetIndex(old_tail)] = element;do{// 保证最大容量commit_和tail_的值一样old_commit = old_tail;// 交换成功结束循环   } while (cyber_unlikely(!commit_.compare_exchange_weak(old_commit, new_tail,std::memory_order_acq_rel, std::memory_order_relaxed)));// 通知有可能正在等待的线程获取任务wait_strategy_->Notifyone();return true;}/*等待入队
*/
template <typename T>
bool BoundedQueue<T>::WaitEnqueue(const T& element) {while (!break_all_wait_) {// 尝试插入		插入失败则进行等待if (Enqueue(element)) {return true;}/*队列已满，开始等待策略*/if (wait_strategy_->EmptyWait()) {continue;}break;}return false;
}

尾插法。

基本上就是入队逻辑的翻转。

3、返回下标

template<typename T>
inline uint64_t BoundedQueue<T>::GetIndex(uint64_t num) {return num - (num / pool_size_) * pool_size_;  
}

这里的下标计算公式：任务序号 - ( 任务序号 - 任务池大小) ×任务池大小

其实后面可以直接用 % 取模来代替，但是这个返回下标函数，也是高频函数，除法比模运算更快，所有用除法代替取模。

（其实这里在解决线程伪共享时顺带解决的。。。。当时以为是这里的问题。改了稍微好了一点。）

4、初始化

template<typename T>
inline bool BoundedQueue<T>::Init(uint64_t size) {return Init(size, new SleepWaitStratrgy());   // 若不指定等待策略，默认使用睡眠等待策略
}
/*
std::calloc 分配内存来存储元素并且进行初始化
*/
template<typename T>
bool BoundedQueue<T>::Init(uint64_t size, WaitStrategy* strategy){// 保证队列两端各留有一个空闲位置pool_size_ = size + 2;// 在动态内存中分配一片连续的内存空间,将分配的内存空间的起始位置存储在 pool_ 变量中，// 以便后续在线程池中使用。pool_ = reinterpret_cast<T*>(std::calloc(pool_size_, sizeof(T)));if (pool_ == nullptr)return false;// 遍历线程池的每个元素，并通过 new 在对应的内存位置上构造一个类型为 T 的对象for (uint64_t i = 0; i < pool_size_; ++i){new(&(pool_[i])) T();}// 设定等待策略wait_strategy_.reset(strategy);return true;}

设计了两种初始化方式，如果不指定等待策略，默认使用线程睡眠策略。

5、线程唤醒

template<typename T>
inline void BoundedQueue<T>::BreakAllWait() {break_all_wait_ = true;wait_strategy_->BreakAllwait();
}

就直接调用的等待策略里的线程唤醒。

6、析构

// 析构
template<typename T>
BoundedQueue<T>::~BoundedQueue() {if (wait_strategy_) {BreakAllWait();}if (pool_) {for (uint64_t i = 0; i < pool_size_; i++){pool_[i].~T();}std::free(pool_);}
}

到此为止，任务队列算是全部弄完了，接下来就是线程池的设计了。线程池的设计其实不多，最难的就是任务提交，因为要保证多参数的解析，就得用到c++的自动推导类。代码不多但是理解起来稍微有点绕。下一文再总结吧。

参考：基于C++11实现线程池 - 知乎