一个任务调度算法引起的性能问题
这两天遇到一个任务调度算法引起的性能问题，花了颇多精力排查和解决。问题出在我写的 ltask 这个 lua 多任务库上。ltask 最初是对 skynet 的一些反思中开始的，最初只是想换一种思路实现 skynet ：做一个库而不是框架、更少的锁竞争、避免服务因为消息队列堆积而过载……
后来、我们游戏引擎开始尝试基于 ltask 利用手机设备上的多核，渐渐的便完善起来，也发展出和 skynet 不同的部分。它最近两年一直是围绕移动设备客户端程序优化，所以网络部分并非重点，也就不需要像 skynet 那样把网络模块做在框架底层，而是以一个独立服务存在。而网络 IO 、文件 IO 、客户端窗口这些部分又不适合于其它渲染相关的服务混在一起，因为它们需要和操作系统直接打交道，所以我在 ltask 中又分出了独占线程和共享工作线程两种不同的线程，可以把不同的服务绑在不同的线程上。甚至对于 iOS ，还必须让窗口线程运行在主线程上，而不得不在 ltask 里做特殊的支持。
最近发现的这个问题也是游戏客户端特有的，它很能说明用于游戏服务器的 skynet 和用于客户端的 ltask 在实现侧重点上的不同。
问题是这样的：我们发现在游戏主逻辑循环中，有一个系统特别简单，但每帧消耗的时间长期统计下来居然达到了 4ms 之多。而我们游戏在此设备上大约每帧 10ms ，也就是占据了 40% 的时长。经过排查后，我发现我们统计时间的函数在 ltask 这种多任务系统下有缺陷，它未能准确统计真实的 cpu 耗时。当我把 skynet 对应的统计函数加到 ltask 后，重新统计发现，这个系统真正的 cpu 开销微不足道，但它在执行过程中让出了控制权，导致主逻辑服务被挂起了很久。
而阅读代码发现，这个系统中并没有阻塞调用其它服务等待回应的代码；而只是对外发送了一个消息（并不需要等待回应）。为什么这样的操作会导致服务的挂起呢？打开 ltask 内置的调度器 log ，记录了上千万条 log 后，通过人肉分析找到了原因。
这要从 ltask 与 skynet 的调度算法差异说起：
在 skynet 中，发送消息给其它服务是非阻塞的。它直接把消息投递给了接收者的消息队列。这儿存在两个问题：其一，发送消息会和其它发送者以及接受者竞争同一个消息队列资源；其二，消息队列是无限长的，只受内存总量的限制，这可能导致服务过载。第一点通常不太所谓，因为竞争是局部的，无论用无锁结构还是 spinlock 去解决都可以，不太影响性能。第二点，一个无限长的队列往往掩盖了真正的设计问题，才是我认为要解决的。
ltask 的设计之初，我就限制了消息接收队列的长度。且不为普通服务准备发送队列。每个普通服务已有一个发送槽位，它待发的消息未被处理，服务就会挂起。而发送消息只有全局唯一的调度器操作，用一把大的全局锁代替众多的小锁。同时，为了减少全局调度器锁的竞争，我同时设计了新的调度器策略，即，任何工作线程都可以竞争调度器，无论是谁竞争到，调度器就会为所有工作线程做好所有后续的工作。这样工作线程只需要尝试获取调度器，即使获取不到也没有关系。这个全局锁实际工作起来就只是一个后备，而并不会在各方抢夺中浪费 CPU 。
每个服务实际的工作流程其实是把自身分割成小的任务片段（用 lua 的 coroutine yield 实现）。调度器主要有两项工作：其一，检查已经完成的任务片段是否产生了待发的消息，若有，就将消息发出，并允许它接受下一个任务片段。其二，调度器为所有空闲的工作线程分配下一个任务。
这两项工作其实和工作线程本身的工作是不相关的，工作线程有两个任务槽位，一个是正在运行的任务，一个是即将运行的任务。调度器可以在任何一个工作线程上工作（排在任务之间），它发送消息、分配下一个任务，都不会影响当前工作线程的运行，所以并发是流畅的，工作线程也几乎不用停顿。它只需要在任务之间尝试抢一下调度器运行一下而已，无所谓谁得到，只要有人可以适时执行一下即可。如果调度器没有被运行，后果就是工作线程无法得到后续的新任务，且自身的代发消息无法发出。但只要有任意一个工作线程有空闲，它就一定会运行调度器的；如果所有工作线程都在忙于做任务，那么也就无所谓下一个任务了。
看似很完美，但这里产生了一个新问题：每个工作线程无法干涉自己的下一个任务是什么。如果我们的目的是尽快完成所有的任务，那么谁先谁后就不那么所谓。而调度器实现的相对公平的话，也不会饿死某个服务。ltask 就是绝对公平的：它用一个循环队列来排列服务。ltask 最大化的消除了工作线程间的竞争，这对手机省电来说是非常有利的。
而这次的问题是什么呢？我们有一个重要的主业务服务，它是所有服务中耗时最多的，也就是说，它的总耗时决定了帧率的上限。每一帧的工作中，必须等待所有服务都完成，才能推进到下一帧。我们一共有 9 个这样的服务，其中第二耗时的是特效（粒子系统）。特效服务的特点是，它在每帧中的开销是波动的，每帧开始时，因为一些状态尚未准备好（比如粒子发射器的位置等），它必须等待；一旦它开始运算，任务不可分割。也就是说，它会占据一个大的时间片不能被打断。这个时间片可以和起他任务并行，但必须在帧末前完成。
最佳的结果是永远把主业务和特效调度到两个不同的工作线程上独立运行，它们会有很多时间是并行的。但意外发生时，主业务服务对外发送了一个消息，它让出了控制权，这时，特效突然被插了进来，变成了同一个工作线程的后续，而随后，主业务又被调度回来，但不幸插在了之后。本来可以并行的两个重头任务串行了。
一开始，我认为尽量安排同一个工作线程执行同一个服务就好了，只要察觉该服务有后序事情要做即可。skynet 就用类似的做法减少竞争：skynet 的某些工作线程会尽可能的处理同一个服务的消息队列，另一些则公平的轮询不同的服务以防止有服务饿死。但 ltask 里做类似的改动却不成立：因为发送消息是和调度器相关的。无法不让出服务的控制权就把消息发送走。btw ，ltask 里有一个绕过这个限制直接投递消息的方法。实现后并没有使用，因为它会启用前面说到的后备锁，增加调度器的竞争。
我昨天的修改是在调度器分配完任务后，检查分配的合理性，让同一个工作线程尽可能的获得同一个服务。但似乎没有解决问题。这和调度器被调度的随机性有关。每个工作线程在完成当前任务时并不一定获取调度器获取下一个任务，它的下一个任务可能是其它人通过调度器给它分配的。而一旦它发现自己有下一个任务，就立刻运行了。当调度器和工作线程并发时，调度器想调整任务可能已经晚了。而只有执行前序任务的那一个工作线程才知道它之后倾向于做什么，它不获取调度器就没办法把这个信息传递出去。
今天我又尝试另一种修改方法：当一个任务完成时，发现自己有对外发送消息，就想办法把自己锁定住，不让别人给自己分配新任务。然后自己抢到调度器，把后续任务设为延续同一个服务。这增加了相当的复杂度（增加了更多的状态，还需要保证线程安全），还增加了竞争。我修改完后，在游戏中偶发死锁，查了几个小时也没有真正定位。果断回退了修改。
最后，我发现问题其实可以从另一个角度解决，那就是对工作线程的休息策略。之前在设计时，我期望不要太频繁的唤醒已经在休息的工作线程。也就是让事情不多时，尽量只激活够用数量的工作线程即可。我们的游戏每帧耗时 10ms ，而锁定 30fps 的话，每间隔 10ms 就有平均 23 ms 的休息时间，只需要一两个工作线程做一些不那么耗时的工作即可。这样可以极大的节省手机的电池。假设有四个服务有任务要处理，我们只需要两个工作线程即可，两个正在运行的服务，和两个待运行的槽位。但，如果我们临时唤醒两个工作线程，它们只要去偷调那两个待运行槽位的话，实时性要高得多。
虽然这么修改没有解决服务对调工作线程的问题：理想情况下，我希望 A 服务永远在 1 号工作线程运行、B 服务永远在 2 号工作线程；但如果调度器把 B 分配给了 1 ，而阻塞了 A 的后续执行，使得 A B 串行。但是，更多的临时唤醒工作线程可以把 A 的后续偷调到新的位置执行。虽然牺牲了一点性能，但减少了延迟。