1、调度器改造

1.1 原生golang调度器

1.1.1 调度器架构

图1 原生调度器架构

1.1.2 数据结构

runqhead：代表P本地任务队列头指针，获取任务时向前移动，可能会被多个线程同时修改。

runqtail：代表P本地任务队列尾指针，增加任务时向前移动，只能被当前线程修改。

runq：代表P本地任务队列。

runnext：代表下一次将运行的任务。

1.1.3 算法流程

调度器的主要算法集中在处理任务队列变化情况，其中任务队列包括P的本地任务队列和全局任务队列，任务队列的变化主要包括以下几种情况：

新任务添加到P的本地队列中，简化为符号：G -> P；
从P的本地队列获取任务执行，简化为符号：P -> G；
当P的本地队列满时，从P的本地队列迁移任务到全局队列，简化为符号：P -> 全局；
当P的本地队列为空时，从全局队列迁移任务到P的本地队列，简化为符号：全局 -> P；
当P2的本地队列和全局队列为空时，从P1的本地队列迁移任务到P2的本地队列，简化为符号：P1 -> P2。

以下针对上面几种主要的情况，分别详细介绍原生调度器的算法流程：

1. 在G -> P情况下，将新G设置为runnext，如果旧runnext不存在则结束，如果存在，后续针对旧runnext操作，当本地队列满时，切换到情况P -> 全局，当本地队列未满时，旧runnext放入队列尾部，尾部指针加1，如图2所示。

图2 G -> P

2. 在P -> G情况下，如果runnext不为空，返回runnext，如果runnext为空，获取队列中第一个任务，采用CAS原子更新头指针，返回获取到的第一个任务，如图3所示。

图3 P -> G

3. 在P -> 全局情况下，获取本地队列的前一半任务，CAS更新头指针，然后将获取的任务插入全局队列尾部，如图4所示。

图4 P -> 全局

4. 在全局 -> P情况下，从全局队列头部开始取不超过128个任务放入P的本地队列中，G存放到P的本地队列按照情况G -> P，如图5所示。

图5 全局 -> P

5. 在P1 -> P2情况下，获取P1队列的前一半任务，CAS更新P1头指针，如果获取的任务数为1直接返回该任务，接着将获取到的任务追加到P2队列尾部，更新P2尾部指针，返回最后一个任务，如图6所示。

图6 P1 -> P2

1.2 优先级golang调度器

1.2.1 调度器架构

图7 优先级调度器架构

1.2.2 数据结构

priority：指定任务的优先级。

runqhead：这个字段设计为64位整数，低32位保存G队列头指针，高32位保存当前激活队列标志位，标志位取值为0或1，代表runq中哪个是激活队列。这种设计主要是保证在优先级排序情况下能够进行获取任务的原子操作，减少多线程抢占队列资源消耗。

runqtail：这个字段表示G队列尾指针。

runq：采用两个数组表示任务队列，一个是激活队列，一个是空闲队列，主要是在排序过程中避免锁队列操作。

1.2.3 算法流程

与原生调度器类似，主要算法集中在处理任务队列变化的5种情况，以下针对这几种情况分别详细介绍优先级调度器的算法流程：

1. 在G -> P情况下，先通过原子操作获取队列头指针，使用位运算拿到当前激活队列，当激活队列未满时，G放入队列尾部，尾部指针加1，当激活队列满时，切换到情况P -> 全局，如图8所示。

图8 G -> P

2. 在P -> G情况下，先通过原子操作获取队列头指针，使用位运算拿到当前激活队列，然后拷贝激活队列任务到空闲队列，获取空闲队列中优先级最高的任务，接着采用CAS切换激活队列并将头指针加1直至成功，最后返回最高优先级任务，如图9所示。

图9 P -> G

3. 在P -> 全局情况下，先通过原子操作获取队列头指针，使用位运算拿到当前激活队列，然后拷贝激活队列任务到空闲队列，将空闲队列按优先级分为优先级较小的一半和优先级较大的一半，较小的一半将被迁移到全局队列中，较大的一半移动到激活队列后半段，接着采用CAS切换激活队列并将头指针累加到后半段起始点直至成功，最后优先级较小的一半按照优先级倒序插入全局队列中，如图10所示。

图10 P -> 全局

4. 在全局 -> P情况下，从全局队列头部开始取不超过128个任务放入P的本地队列中，G存放到P的本地队列按照情况G -> P，如图11所示。

图11 全局 -> P

5. 在P1 -> P2情况下，先通过原子操作获取P1队列头指针，使用位运算拿到当前激活队列，然后获取队列中前一半任务用于后续插入P2队列中，接着采用CAS技术更新P1队列头指针直至成功，同样的原子操作拿到P2当前激活队列，拷贝P2激活队列和从P1获取的任务队列到P2的空闲队列，取出P2空闲队列中最高优先级任务，并将其他任务整体移动到P2当前空闲队列起始点，接着采用CAS切换P2激活队列直至成功，最后更新P2尾指针并返回最高优先级任务，如图12所示。