« August 2022 | Main

September 07, 2022

多线程串行运行 Lua 虚拟机

ltask 是一个功能类似 skynet 的库。我主要将它用于客户端环境。由于比 skynet 后设计,所以我在它上面实验了许多新想法。

最近碰到一个需求:我们的游戏引擎中嵌入的第三方 C/C++ 模块以 callback 形式提供了若干接口。在把这些模块嵌入 ltask 的服务中运行时,这些 callback 函数是难以使用全部 ltask 的特性。比如,我们的 IO 操作全部在一个独立服务中,引擎读取文件时,很可能是通过网络异步远程加载数据的。这些第三方模块通常没有考虑异步 IO 操作,都是以同步 IO 方式给出一个读文件的 callback 函数让使用者填写。

那么,怎样才能在这个 C callback 中挂起当前任务,等待 IO 的异步完成呢?

初看是不可能做到的。框架没有设计成支持异步机制,我们难以从 C 函数中 yield ,挂起当前任务。这样,同一个服务就不可能在 callback 结束前相应外部消息,也就无法利用 ltask 的调度器完成异步 IO 工作。

Lua 虚拟机也并没有(也无必要)设计成多线程安全的,我们不能把这个 C 模块及其 Lua binding 的运行环境放在一个独立线程环境中。所以,callback 中阻塞调用 IO 请求,就意味着整个服务的阻塞。

一个比较简单的解决方法是给 IO 服务额外开通一个 channel ,不走 ltask 内部的消息。在 C callback 中,通过这个额外的 channel 和 IO 服务通讯。


但我仔细思考了这个问题,发现当 C callback 不返回时,未必整个服务必须跟着一起阻塞住。其实,只要 ltask 框架稍做一些支持,我们还是可以让服务继续工作的。

现在的任务调度模型是:由调度器分配一个工作线程运行一个服务的一小段任务(通常是用 lua resume 运行 lua vm 中的一个 coroutine 一个片段),在此期间,服务处于忙状态,别的工作线程无法拿到该服务。这就保证了单个服务不会重入。

当这一段任务执行完毕,而服务的消息队列为空时,调度器将服务设为闲置状态。等有新的消息投递到服务的消息队列后,闲置状态的服务会重新回到调度器中。

如果我们给服务一个新的状态:在 C 函数中挂起。那么,其实我们还是可以让服务重新进入调度器。从 ltask 的调度器视角来看,它冻结了一整个工作线程,但服务内的 Lua 虚拟机其实也处于停滞状态(因为停在了 C Side ),只要它不回到 Lua side ,这个 Lua 虚拟机依旧可以工作。调度器所作的工作只是把服务的忙状态取消即可。这样,其它工作线程就可以正常的调度它了。

但框架还需要多做一些工作。因为 Lua VM 的工作 coroutine 也处于忙状态,我们不能继续在这个 coroutine 在运行新的代码。所以在此时,应该在该 Lua VM 中创建出一个新的 coroutine 并取代服务的工作 coroutine 。然后让 C callback 等待到一个操作系统的条件变量上;直到业务层认为事情已经完成,需要回到一开始挂起的 C Callback 时,再将环境恢复,唤醒操作系统的条件变量,交还执行流。

在这个流程中,服务中的 Lua VM 从未处于并行状态,所以是安全的。但稍显怪异的是,Lua VM 的确工作在多线程环境下,由两个不同的操作系统线程在独立运行不同的 Lua coroutine 。这样,才保证了其中一个 Lua coroutine 可以一直保有自己的 C 调用栈。

这种运行 Lua VM 的方式,我称之为多线程串行运行。需要注意一些原本在 Lua 中成立的约束不成立了。比如,在单线程环境下,如果你运行一个 Lua 函数,该函数没有修改一个全局状态,函数也没有让出,那么可以认为这个全局状态是不会改变的;但现在,这个函数可能在 C side 挂起,而另一个操作系统线程可能从另外一个 lua coroutine 修改这个状态。

在我们的初步实践中发现,对应的 C/C++ 模块最好也能设计成多线程安全的。虽然在这个模型下,C 代码也没有并行的问题,但会多出很多重入问题。即,一个 C 函数运行了一半,有可能挂起,由另外一个系统线程再进入一次。一般非线程安全的 C 模块很可能在这方面考虑不周。(接口中有 callback 的框架更容易出现重入 bug )

我在 ltask 的 taskrun 分支实现了这个特性

September 02, 2022

路网中路径的储存

我们正在制作的游戏中,交通和物流是基于公路网的。公路网其实是以路口为顶点,路为边构成的(无向)图。因为我们有大量的车辆行驶在这个路网中,所以,我需要一个空间高效的方法储存这些车辆的路径。

在大部分情况下,我们的车辆都选择唯一的最短路径,也就是说如果从 A 路口到 B 路口存在一条制定好的路径的话,所有的车都会走这条路。基于这一点,我们可以对多条路径合并储存。

我选择用当前路口 id 和目的地路口 id 做 key ,把下一站路口 id 作为 value ,保存在一张 hash 表中。这样,先用 dijkstra 算法求出起点到终点的最短路线后,再把每一段路线用该结构保存下来即可。

当车辆到达某个路口,只需要用当前路口和它自己的目的地就可以索引到应该往哪个方向开。这个结构很适合保存在 Lua table 中,用元表触发尚未计算过的路径。而且这样一个路径表只是一个 cache ,随时可以清理重建。

如果路网已经稳定,那么还可以选择一个内存更紧凑的结构保存它们。

对于每个路口,连接的路是有限的。在我们的游戏中,其实只有十字路口( 4 叉)和 T 字路口( 3 叉)两种。我们可以对路口连接的路编号为 1-4 。我们用 4 个数组就能储存下所有的路径信息。

驶向同一编号出口的路径可以储存在一起。比如,如果从 42 号路口去向 100 号路口的车需要在 42 号路口的第 2 出口驶出,我们就把 (42,100) 记录在 2 号数组里。

每个数组都是有序的,这样可以用二分查找确定一段路径是否在该数组中。因为最复杂的路口只有四个出口,而车在我们的规则中,不准在路口调头,原路折返。所以在一个路口查询下一阶段的去向,最多只需要做两次二分查找就可以确定(在起点出做四次查询可以知道是否可达)。

当路网固定,不会动态增删时,这四个数组可以储存在一片连续内存中。它储存了在这个路网中,任意两个路口间的最短路径。

以上,我作了一个简单的实现