« December 2020 | Main

January 22, 2021

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

January 12, 2021

把 skynet 的原子操作换成了 stdatomic

stdatomic 已经是 C11 的标准,并且成为了 C++ 标准的一部分。msvc 也将会支持 stdatomic 。在 skynet 项目开始的时候,还没有这个可以用,所以我采用的是更早一点的 gcc sync 系列的扩展

我想,用 stdatomic 来实现原子操作,会有利于 skynet 未来的发展。上周花了点时间熟悉这套 api 并在 skynet 中实现。同时保留了之前的实现,如果编译器定义了 __STD_NO_ATOMICS__ 就会切换回老版本。

首先,C11 增加了 _Atomic(T) 类型。这在之前的 gcc Atomic builtins 里没有。过去是直接使用已有的原生数据类型的。现在,如果一个 int 是一个原子变量,就需要使用 atomic_int ,它实际上是 _Atomic(int)

原子操作的 api 只接受原子变量,即使是简单的读写原子变量,也必须用 atomic_loadatomic_store 。之前则没有提供相关 api 。这样代码更为严谨,你不必假设系统到底能原子读写多长的字,编译器会做检查。

不过,gcc 似乎并没有严格检查原子操作传入的变量是否是原子类型;而 clang 则严格的多。所以一开始我实现的初版在 clang 上遇到的编译操作,就是因为改漏了一些地方,经过网友提醒,后来才修补完整。


cas 指令 ,即先比较旧值,只有在相等的情况下才做交换。这是无锁结构和一些基本锁实现的基础。例如 CAS(ref, 0, 1) 表示比较 *ref 是否为 0 ,如果不等于 0 就返回失败;等于 0 就返回成功并把 *ref 置为 1 。

这可以在并发操作 *ref 的时候,同时只有一处可以把 *ref 从 0 修改为 1 。

在新标准中, cas 分成了两个版本, atomic_compare_exchange_weakatomic_compare_exchange_strong 。weak 版本允许偶发情况下,即使相等也失败(对于上面的例子来说,允许当 *ref == 0 的时候失败)。我们一般使用这个 weak 版本即可(相对 strong 版本成本可能更低)。

不过让我奇怪的是,新标准的 cas api 的 oval 旧值是用指针传递,而新值用的值传递。这个旧值指针是一个传统指针,不是原子类型。我不太理解这个设计的原因。之前的 atomic builtins 和 windows 的 InterlockedCompareExchange 都是传值的。

之前的 __sync_lock_test_and_set 变成了 atomic_flag_test_and_set ,必须使用 atomic_flag 。这个东西可以用来实现 spinlock 。但让我奇怪的是,C11 标准中没有 atomic_flag_test (在 C++20 中有)。而实现读写锁则需要 test (但不 set),不过没太大关系,我们可以用 cas 指令代替。

在以前的 atomic builtins 中,既有 __sync_fetch_and_add 又有 __sync_add_and_fetch ,区别在于返回值是加之前的还是加之后的。stdatomic 中只保留了 atomic_fetch_and_add ,取消了后者。不过没太大关系,因为,以自增 1 为例,add_and_fectch(ref,1) 等价于 fetch_and_add(ref, 1)+1

最后一个小问题是,指针没有定义 atomic 类型,所以我用 atomic_uintptr_t 替代。但是在用的时候,需要再转换为对应的指针类型。

January 05, 2021

预运算地图寻路的一种方法

上次谈到服务器上寻路算法的优化。文末提到,其实,针对具体需求,我们实际上可以预运算所有的路径,把结果持久化在文件中,运行时用 O(1) 的时间就可以查询到任意路径。

对于半径为 N 的地图网格,选取任意两点作为起点和终点,一共有 N^4 数量级的路径,直接按起点和终点来缓存路径显然不现实。

但实际上,除非整张地图是个复杂的迷宫,大部分路径是重复的。这和人实际上行路是一样的。如果你从家中的卧室去到办公室的工位上,整条路径和你从客厅出发是高度重叠的;仅有出家门前的那一小段略有不同。

在服务器上寻路,通常解决的是 NPC 的小范围内移动绕开障碍(从卧室到家门)的问题,远距离移动的路线(从家到公司)应当在另一个层面去解决。

基于网格寻路无论是用 A star 还是基于图的 dijkstra 算法都非常简单,这里不谈算法,只谈结果的持久化问题。

为了解决起点和终点有 N^2 种可能性,这个数量级太大的问题,我们可以适当的将地图划分成若干区域。如果每个区域都是一个内部没有任何障碍物的凸多边形,那么,当我们的起点和终点都落在同一个区域时,连接两点的直线就是最短路径。

如何划分区域,不是本文的重点。这里只简单说两句。如果障碍物基本上是轴对齐的,那么简单的贴着障碍线对分切割就好了。就是对地图不断的做二分的过程,空间划分用一个 KD tree 划分即可;如果障碍线不是轴对齐的,那么可以用 BSP 树做空间凸集的划分。

现在,我们假设地图已经划分为多个凸多边形了。如果我们的划分不算太畸形(避免出现细细长长的区域),那么基于这个划分方案,我们可以得到一个较优的路径。方法是这样的:

当起点和终点不在同一区域时,首先,我们找到起点到终点所属区域的轮廓任意一点的最短路径。即,最快靠近目标区域;然后,从目标区域的轮廓上的那一点直线通达目的地。

只要区域划分得当,这条路几乎是最优的。即使不算最短路径,也是非常好的结果。

如何找到一点到一个面(轮廓线)的最短路径?我曾经写过一篇 blog 谈我们实际使用过的一个算法

简单说就是,我们在网格图上先把目标区域的格子都涂上 0 ,然后把所有上色的格子的邻近格都加 1 ,逐步把整张图都填上数字。最终,没有数字的格子就是无法抵达的,而每个格子上的数字就是距离那个区域的最短路径的距离。

这张图可以视为一个流图,数字看作高度,当我们处于某个非 0 的格子时,只要向临接的格子中数字最小的走,就能最快的抵达最低点 0 ,整个过程就是最短路径。

任意一个区域中的任意一点到另一个区域的最短路径就可以储存在这么一张图中。图上每个格子都只需要记录一个方向。如果是四边形网格,就是 8 个方向加一个不可抵达标志,一共是 9 个状态,用 4bit 表示即可。当然也可以利用 8bit 记录更多的方向信息。

如果我们只处理划分好的区域中,每个区域的附近(直线距离)的有限个区域,那么就可以用一个非常紧凑的数据结构来保存所有的信息 。注意,临近区域未必是紧挨着的区域,只要空间直线距离不远都算。

首先,我们记录下地图上每个格子自己数据几号区域。然后在区域结构中保存下每个区域附近有那些区域。每个格子中额外记录到附近每个区域最短路径的方向(或不可抵达)。

运行时,我们只要查到目的地所归属的区域,然后在出发格上查询到对应区域的行动方向就可以移动了;或者在同一区域时直接直线移动。每来到一个新的格子时候就重新做一次查询,这个查询是 O(1) 的,且可以共享个服务器所有单位同时使用。这非常适合障碍是静态的,而目的地在不断运动(比如追逐一个移动的对象)的场合。