« 把 skynet 的原子操作换成了 stdatomic | 返回首页 | ltask ：Lua 的多任务库 »

关于 skynet 调度器的一点想法(续)

这篇是继续上次的一些想法。

我最近想重新做一个新的基于消息管道的 N:M 多任务调度器。主要用在我们的客户端上。算是解决在使用 skynet 多年来总结出来的一些问题。

首先，我想改变 skynet 服务直接将待发消息投递到对方消息队列的做法。发出消息会让服务挂起，等待投递。

然后，我设计了一个叫做调度器的模块，用于把带发消息投递到对应的接收管道中。调度器是发送消息的消费者，接收管道的唯一生产者；而每个服务是它自己的发送消息的唯一生产者，接收管道的唯一消费者。这样没有竞争，当消息队列是定长的时候，也无需使用锁（但引入了消息队列满的新状态）。

同时，也遵循 skynet 的约定，send 消息是不会引起服务重入的。所以，因为发送消息而挂起的服务，调度器会尽快处理，给出结果，延续服务的运行。中间不会插入针对这个服务的别的事务。消息投递结果可能是成功，也可能是对方不存在，或对方队列阻塞。如果发送发送阻塞，逻辑层可以决定是重试还是丢弃。

这个方案是实现的重点是这个调度器。我想改变 skynet 现在每个工作线程去抢任务的方案。由（唯一的）调度器去分派任务。这样可以避免全局队列的锁，还可以让服务尽量在同一物理线程上工作。

实现细节我想了不少时间，方案主要是受最近 100+ 小时的异星工厂游戏时间的启发。

我原本想给每个工作线程安排一个工作队列，由调度器根据任务原本所在的工作线程，以及工作负荷均分的原则将任务投递进去。这些工作队列理论上只有工作线程本身单一消费者，和调度器这个唯一生产者。也可以简单实现。

但这里无法解决极端情况：我们无法预知未执行的任务到底需要多长时间。一旦一个任务花了超长的时间，就会导致所属工作线程上的工作队列中的任务全部收到延迟影响。如果再让调度器去检测病态任务，并收回已经分配任务重新分配的话，前面的简单性就不复存在。

所以，我不给工作线程安排工作队列，而只提供一个待处理任务的 slot （也可以视为一个长度为 1 的队列）。用原子指令操作。

调度器每轮的职责只是把待分配任务填到所有空的 slot 中就够了。而工作线程取出自己所属的非空 slot 就将其置空并执行任务。

这里有一个技巧。我们不必用一个独立线程去运行调度器。而把调度器视为一个模块，任何工作线程都可以运行，但运行前，需要先用 cas 指令抢到运行调度的权力。同一时刻，只有一个工作线程可以运行调度器。

如果工作线程在当前任务执行完毕后，发现所属的 slot 中没有下一份任务。那么它就尝试申请调度器的运行权力，如果获得调度权限，优先给自己分配下一个任务，然后把待做任务分到其它的 slot 中。如果没有待做任务，还可以把已经分配到其它 slot 上的任务收回，分给自己。

这样，就保证了只要有一个工作线程未休息，那么待做任务就至少有人会去做。

当工作线程无事可做，又抢不到调度权限时，它可以休息，但会对工作线程总数做原子的计数。如果它发现自己是最后一个准备去休息的工作线程了，那么它就负责把所有工作线程唤醒。这是为了避免边界情况导致有任务没做完但所有工作线程都休眠了。

只有在运行调度器的工作线程发现完全没有任何任务可以分配时，这个时候才真的全体休息，直到有外部消息（网络消息或时钟消息）进来，重新唤醒工作线程。

云风 提交于 January 22, 2021 11:38 AM |

Comments

新的调度模型有没有可能考虑将Timer线程、Socket线程和工作线程一起调度，当前的调度模式实时性不好，在串行请求应答的场景下，socket收到消息必须得等到另一个工作线程唤醒处理，需要一次额外的线程切换。

Posted by: 骷髅X | (10) January 2, 2024 04:36 PM

修改前是单消费者（同一服务的任务队列同一时间只会有一条线程消费） 多生产者模型 修改后调度器的消息队列是否就是全局消息队列，竞争是不是更加激烈，所有消息都要投递到调度器中，再由服务工作线程从全局消息队列分配到服务消息接收管道再进行处理 如果只是为解决投递消息的竞争性能损耗，是否可以考虑采用无锁环形队列来优化多生产者单消费者的性能，只要消费速度大于生产速度，生产者只需要采用cas的方式获取队列索引填入消息，可以大大提高投递消息的速度

Posted by: spark | (9) November 19, 2021 05:01 PM

有点疑问，这样每个服务执行的时候都是和原来一样只能有一个线程在操作吗，但感觉看了这篇文章后没有了这个特性。

Posted by: kanonlee | (8) March 18, 2021 03:28 PM

多线程竞争全局队列任务， 现在不竞争队列任务，而是竞争调度器，， 调度器的任务， 一，给空闲的线程分配一个任务， 二，给自己一个任务。 所以，得给这个调度器加锁。 这样做的好处是，一次性搞定任务分配， --- 相当于，原来一堆人去抢钱。现在是先争老大，再给大家分钱。

Posted by: 李哲 | (7) February 5, 2021 10:52 AM

我觉得调度器可以参考 java ForkJoinPool 的实现

Posted by: MoonFruit | (6) January 25, 2021 11:54 AM

这个比之前那篇的好。cas的竞争只要用全局队列总是避不开的，但是这个设计好的地方是 1 没有单独的工作线程，勉强避免了numa内存的问题 2 还是全局队列，所以按队列理论还是等待时间最优 3 有一个简单的work stealing，避免了一些线程的starving 4 因为调度器分配完了所有的task，所以numa的开销都他负责了，感觉上好像比较好一点 而且这个slot的设计并没有排除以后加更多的slots来避免全局队列的竞争，不过那样的话就是一个比较标准的work stealing实现了。 期待你的benchmark！

Posted by: Liu Liu | (5) January 23, 2021 10:47 AM

优秀，等你实现出炉

Posted by: 天高任逍遥 | (4) January 23, 2021 10:24 AM

有点像work stealing的算法吧. 现在常见的多生产者多消费者的任务队列也都用上CAS无锁算法了, 再优化我觉得收效甚微, 平时不太可能发现性能瓶颈在这里. 如果还想更高效, 就只能想办法自己生产的消息立即让自己消费掉, 接近直接调用的效果.

Posted by: dwing | (3) January 22, 2021 11:09 PM

@Cholerae Hu 我不知道你怎么分析得到的这个猜测。下面是我针对 “大量短任务的 workload” 的分析： 1. 短任务有多短？所有的任务都是由消息触发的，无论任务有多短，它都要至少处理一条消息，处理量和消息的长度有关。另外还包括了进出 lua 虚拟机的成本（因为 skynet 是基于 lua 的）。而任务调度器的工作是将任务（这里是服务 id ）逐个填在工作线程的空 slot 中，大致是处理 N 个指针的数据量。这里的 N 是工作线程的数量。 我认为，在处理一个短任务时，如果有额外的任务，调度器来不及把下一个任务分配到它所属槽位的可能性是不高的。这意味着分配任务的成本高于（或相当于）一个任务的处理成本。 2. 大量有多大？可调度任务的总数不会超过 M 。而任务的产生是源于消息，一个外部消息对应着一个任务，而需要回应的内部消息只是继承了任务，即从 A 转移到 B ，A 挂起，B 继续。不需要回应的消息会让一个任务分裂成两个。任务有可能变得大量，但需要一个过程，而不会平白无故的变多。 总的来说，任务总数还是受外部消息的影响，大多数是网络消息，另一部分是 timer 消息。但这两个东西本质上都是串行的。网络消息和 timer 消息，在 skynet 中都是串行发放的。也看不到什么可能做成并行。 3. cas 争用？这里的工作线程在 cas 获取调度器权限的时候，采用的机制是拿不到就退出休息，而不是反复尝试。所以只会尝试一次。为什么会非常剧烈？ 在 N:M 的 M @Cholerae Hu 我不知道你怎么分析得到的这个猜测。下面是我针对 “大量短任务的 workload” 的分析： 1. 短任务有多短？所有的任务都是由消息触发的，无论任务有多短，它都要至少处理一条消息，处理量和消息的长度有关。另外还包括了进出 lua 虚拟机的成本（因为 skynet 是基于 lua 的）。而任务调度器的工作是将任务（这里是服务 id ）逐个填在工作线程的空 slot 中，大致是处理 N 个指针的数据量。这里的 N 是工作线程的数量。 我认为，在处理一个短任务时，如果有额外的任务，调度器来不及把下一个任务分配到它所属槽位的可能性是不高的。这意味着分配任务的成本高于（或相当于）一个任务的处理成本。 2. 大量有多大？可调度任务的总数不会超过 M 。而任务的产生是源于消息，一个外部消息对应着一个任务，而需要回应的内部消息只是继承了任务，即从 A 转移到 B ，A 挂起，B 继续。不需要回应的消息会让一个任务分裂成两个。任务有可能变得大量，但需要一个过程，而不会平白无故的变多。 总的来说，任务总数还是受外部消息的影响，大多数是网络消息，另一部分是 timer 消息。但这两个东西本质上都是串行的。网络消息和 timer 消息，在 skynet 中都是串行发放的。也看不到什么可能做成并行。 3. cas 争用？这里的工作线程在 cas 获取调度器权限的时候，采用的机制是拿不到就退出休息，而不是反复尝试。所以只会尝试一次。为什么会非常剧烈？ 在 N:M 的 M < N 时，也就是大多数逻辑线程处于休眠状态，活跃的逻辑线程少于工作线程的时候，没必要让工作线程不断竞争。这里会让它们逐步退化成一两个工作线程工作。 唤醒条件是外部消息到来（或所有的任务都处理完毕，为避免处理的不干净，额外唤醒一次）。在此之前，工作线程活跃数量是单调下降的。而不应该频繁"休眠和唤醒"。

Posted by: Cloud | (2) January 22, 2021 03:00 PM

目测这个设计，在大量短任务的 workload 下，对调度器的 cas 争用会非常剧烈，另外争抢不到调度器的线程还会频繁休眠和唤醒。

Posted by: Cholerae Hu | (1) January 22, 2021 01:27 PM

Post a comment

非这个主题相关的留言请到：留言本