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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Comments

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


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

这个比之前那篇的好。cas的竞争只要用全局队列总是避不开的,但是这个设计好的地方是 1 没有单独的工作线程,勉强避免了numa内存的问题 2 还是全局队列,所以按队列理论还是等待时间最优 3 有一个简单的work stealing,避免了一些线程的starving 4 因为调度器分配完了所有的task,所以numa的开销都他负责了,感觉上好像比较好一点

而且这个slot的设计并没有排除以后加更多的slots来避免全局队列的竞争,不过那样的话就是一个比较标准的work stealing实现了。

期待你的benchmark!

优秀,等你实现出炉

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

@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 时,也就是大多数逻辑线程处于休眠状态,活跃的逻辑线程少于工作线程的时候,没必要让工作线程不断竞争。这里会让它们逐步退化成一两个工作线程工作。

唤醒条件是外部消息到来(或所有的任务都处理完毕,为避免处理的不干净,额外唤醒一次)。在此之前,工作线程活跃数量是单调下降的。而不应该频繁"休眠和唤醒"。

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

Post a comment

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