以前关于brpc写socket的一篇文章 brpc源码解析（三）—— 请求其他服务器以及往socket写数据的机制里讲到了brpc往fd里写数据的一套机制，最近从朋友那得知原来这部分逻辑已经单独抽出来作为bthread一部分了，也就是ExecutionQueue，顾名思义，也就是一个用来执行任务的队列。本来就好久没看过相关代码了，于是最近看了下ExecutionQueue重温一下，这里写一篇文章记录下。

一、概述和特点

ExecutionQueue 为一个多生产者单消费者的队列，提供了异步串行执行的功能，主要特点如下：
（1）异步有序执行: 任务在另外一个单独的线程中执行, 并且执行顺序严格和提交顺序一致。
（2）Multi Producer: 多个线程可以同时向一个ExecutionQueue提交任务。
（3）支持cancel一个已经提交的任务。
（4）支持stop提交的任务。
（5）支持高优任务插队。

该队列主要针对多生产者单消费者场景，有着特别优秀的入队效率，它的入队是wait free的，出队（消费）有概率被短暂阻塞，在原理上不是wait-free也不是lock-free，但在实践中很少出现，对于类似写socket这种单个任务消费耗时较大的场景，这种短暂阻塞的影响微乎其微。入队效率高意味着生产线程可以更快地处理新任务，而消费线程也能每次拿到一批任务批量写出，在大吞吐时容易形成流水线效应而提高效率。同时还支持任务的优先级和任务取消，高优任务入队后不会打断现有任务，但随后会首先被执行。

二、生产和消费基本原理

对于一个生产者消费者队列，核心操作自然是入队（生产）和出队（消费），ExecutionQueue的入队相对简单，直接通过exchange把自己换进去再修改指针即可，而消费则是通过反转链表的方式依次消费队列里的内容。以下是一个典型的生产消费示意图，T1的时候队列只有一个元素，并且队头指针_head指向它，这个时候消费线程就会开始消费，随后在1还在处理的的T2时刻，又有2 和3两个元素入队。T3-T5为反转队列的操作，反转完会挨个消费2和3，随后到了T6，又入队了4和5两个元素。T7则是类似的反转，并且移除了已经消费完的任务节点。

三、典型使用方式

最基本的使用上，首先是调用execution_queue_start来启动一个队列，队列启动后就可以使用execution_queue_execute来提交任务了，一个典型的例子如下：

四、task node和相关内存分配

任务执行的载体是TaskNode，主要是一些任务相关信息，如下：

在执行任务的时候，会通过allocator分配空间后创建tasknode，如下：



这里的空间分配最核心的就是根据提交的任务的数据类型所占用的空间来确定是直接利用node结构里预留的56字节静态空间来分配还是额外动态分配，allocate相关代码如下：

五．启动ExecutionQueue代码解析

execution_queue_start函数有四个参数，id用于定位到这个queue，ExecutionQueueId类型本质上是uint_64，也就是execution_queue_start执行后id保存了队列对应的id，在执行任务的时候作为参数可以直接定位到需要的队列，第二个队列的option，里面只有一个任务执行用的bthread的属性，第三个参数则是核心的执行函数，第四个则是这个队列的meta信息，也就是传给执行函数的第一个参数，可以用于保存一些队列里各个任务都用到的公共数据。其中id和执行函数是必须的。

execution_queue_start里实际调用的是ExecutionQueue的create,是Base (ExecutionQueueBase)里create函数的的封装，base的create函数真正创建了一个queue，主要是从资源池里拿到实例，然后修改一些关键变量完成创建。


execute_func参数传入的是execute_task，也就是封装了一层对用户函数的调用，之所以要多这么一层调用是因为base这一层并不是模板，而clear_task_mem则是用来回收内存的，type_specific_function则是真正的用户函数，执行任务的时候会通过execute_task进行调用。

六、提交、调度和执行相关代码解析

6.1 任务提交调度

任务提交的入口execution_queue_execute有三个版本的重载，分别是最简单的使用队列id和任务不指定option进行执行，指定option的版本以及指定option和handle的版本，handle是用于标记某一个具体的任务，用于取消任务，后面会讲到。

经过execution_queue_execute后调用的是execute，首先是根据task创建任务节点node，内存分配就是前面提到的小数据直接使用static mem，大的才额外分配，在我们的使用示例里传的是个指针，所以直接用static就能满足需求。
然后是设置option和handle，option只有两个，优先级和是否优先本地执行。

创建好task node后调用start_execute，从这里开始也就进入了真正操作队列的部分。
首先是对node的一些变量做初始化， 如果是高优任务对高优任务计数器加1.然后就是前面说到的把自己换入head，如果前head不为空，说明已经有线程在执行任务了，直接返回就行，否则进入下面的发起执行逻辑

如果优先本地执行则尝试本地执行，本地执行完任务后如果还有未执行的任务再启动bthread继续执行，否则直接启动bthread执行队列里的所有任务。
涉及到执行的三个主要函数：_execute函数是执行单个任务，_execute_tasks是执行队列里的所有任务。_more_tasks是判断队列是否还有更多任务并进行链表反转从而能够继续执行。

我们先来看下_execute_tasks，_execute_tasks的入口是一个待执行的task node，主要逻辑是一个for死循环，只要还有待执行的任务就会一直循环执行，如果当前要执行的节点已经执行，释放后指针后移到下一个任务。
核心逻辑是判断是否有待执行的高优任务，如果有，进行高优任务迭代执行，否则走低优执行，具体执行就是调用int ExecutionQueueBase::_execute(TaskNode* head, bool high_priority, int* niterated)函数。

执行过后释放掉遍历过的任务节点，调用inline bool ExecutionQueueBase::_more_tasks(TaskNode* old_head, TaskNode** new_tail, bool has_uniterated)判断是否有更多任务，如果没有了停止循环，注意destroy_queue这个变量，这个是表明整个队列是否要停止，具体到实现上就是往队列push一个特殊的任务stop task，执行这种任务就是触发队列停止执行任务并回收资源

6.2 执行用户函数

_execute则是真正地调用用户函数进行任务执行，首先判断是不是stop task，如果是，则执行完后返回停止状态码，从而在_exectute_tasks函数里进行队列的销毁相关操作，执行上都是生成迭代器后使用execute_func函数调用用户函数_type_specific_function，其实分别也就是上面介绍过的execute_task和demo_execute。


demo_execute里，如果是正常任务进行相应逻辑处理，如果是stop task则是一些销毁公共meta数据等的操作，因为是根据迭代器执行，所以可以用一个for循环对链表翻转好的部分进行迭代执行。

首先是对自身进行一个bool的判断，bool运算符是重载过的，也就是对是否还要继续迭代的一个判断，上面的for循环的判断里也有用到。

然后就是需要跳过已经遍历过的，而且如果本身是低优迭代器并且有待执行的高优任务就停止。找到下一个要执行的同优先级任务并置已遍历为真后返回。

*运算符也是重载过的，用于获取实际的task指针。

6.3 新任务检查

_execute_tasks函数里的循环在执行当前任务节点后需要进行新任务检查确定是否要继续执行其他任务，其中核心函数就是_more_tasks，负责检查是否有新任务入队以及和链表翻转。先来看下参数，old_head是老的头部，也就是上次执行的那个task node，在我们举的例子里t6时刻的3就是old_head，new_tail用于保存反转后的队尾，has_uniterrated表明old_head是否已经被执行。首先是一个check，正常情况old_head的next一定是null。_head做cas操作如果成功说明head没变，直接返回，返回值则是根据has_uniterrated来确定，即便_head没变（没有新任务）但是当前任务没有执行到还是要返回true，否则false。Cas失败则是后面有新任务插入，这个cas的memory order是acquire是为了和start_execute里对head的release组成release acquire语义确保当前线程看到新_head的时候能看到对应写入的task的相关数据。

接下来就是翻转链表的部分，传入的new_tail保存翻转后的链表尾，也就是当前看到的翻转前的新head，然后一个循环进行单链表翻转，由于任务入队的时候是先exchange head然后再置next指针，所以翻转过程有概率碰到断链的情况，因此用while 和yield等待连上后再继续往下翻转，翻转完返回true。_execute_tasks随后开启新的一轮循环进行任务执行。

6.4 取消任务

ExecutionQueue可以取消提交的任务，使用execution_queue_cancel函数即可，参数则是上面讲到的执行任务时的可选参数handle，如下：

也就是调用tasknode的cancel函数，如果没有执行，就可以成功取消，否则返回取消失败。

参考
brpc源码学习（七）- 无锁mpsc队列ExecutionQueue
ExecutionQueue官方文档