一、背景

VanillaRT 是我们最近正在开发的一款 Minecraft 服务器插件，是一个体素模型光线追踪引擎。这是一张测试时的渲染效果：

最近测试时，发现有些复杂渲染任务会导致服务器崩溃。这是因为渲染场景时需要大量的运算，而 Minecraft 服务器有一个主线程（Server Thread），主线程卡顿会导致玩家体验大幅下降，甚至因为不能及时喂狗（feed）而触发服务器崩溃。因此我们需要保证主线程不卡顿的同时，尽可能大地使用服务器资源。

二、分析

服务器状态通过检测服务器的 TPS（Tick Per Second）感知到。一般地，TPS = 20 时服务器的运行状态良好，TPS < 18 时资源就有些告急，玩家可以感受到卡顿。所以，我们的算法应当保证 TPS 不能降得太低，以避免主线程卡顿和崩溃。

我们通过一种类似 TCP 拥塞控制的算法动态地根据当前 TPS 调整某个限制光线追踪计算资源的变量，我们先将它称为资源限制变量。我们的算法大致的思路是——在提交新任务时，先把需要计算的任务放入一个就绪队列，再调用一个检查并在此时可以提交此任务的函数。此外，在资源限制变量变大，或任意任务结束时，我们也调用上述函数尝试提交新的任务。

三、算法

这个变量应该是什么呢？直觉告诉我们同时计算的任务过多可能导致卡顿，因此我们先限制并发数。

（一）限制并发数

我们将那些已经提交给 CoroutineScope 且尚未退出的协程数定义为并发数，其统计方式类似下面这样：

private val coroutineScope: CoroutineScope
private val concurrentUnits: AtomicInteger

private fun submit(action: suspend CoroutineScope.() -> Unit): Job {
    concurrentUnits.incrementAndGet()
    return coroutineScope.launch {
        try {
            action()
        } finally {
            concurrentUnits.decrementAndGet()
        }
    }
}

当然我们不能简单地把所有提交的任务都通过上述 submit 函数提交，而是需要先放入一个 scheduledUnits 队列里，并在每个任务结束，或并发数提升时检查是否需要提交新的任务。其代码类似下面这样：

private val coroutineScope: CoroutineScope
private val concurrentUnits: AtomicInteger

private fun submit(action: suspend CoroutineScope.() -> Unit): Job {
    concurrentUnits.incrementAndGet()
    return coroutineScope.launch {
        try {
            action()
        } finally {
            concurrentUnits.decrementAndGet()
            trySubmitScheduledUnits()
        }
    }
}

private val scheduledUnits: Deque<suspend CoroutineScope.() -> Unit>

fun schedule(action: suspend CoroutineScope.() -> Unit) {
    scheduledUnits.add(action)
    trySubmitScheduledUnits()
}

fun trySubmitScheduledUnits() {
    while (true) {
        val unit = scheduledUnits.poll() ?: return
        if (canSubmitNow()) {
            submit(unit)
        } else {
            scheduledUnits.addFirst(unit)
            return
        }
    }
}

函数 canSubmitNow 的逻辑我们暂且不谈。让我们注意新增的 trySubmitScheduledUnits，它不断地从 scheduledUnits 取出第一个节点并尝试提交，如果当前资源不足则重新将其加入队列并返回。

值得一提的是，我们实际上不需要同时有多个 trySubmitScheduledUnits 执行，这只会增加队列操作失败重试的次数。所以我们用一个布尔值保证最多只有一个线程调用它：

private val trySubmitScheduledUnitsLock = AtomicBoolean()

fun trySubmitScheduledUnits() {
    if (trySubmitScheduledUnitsLock.compareAndSet(false, true)) {
        // Try submit scheduled units.
        trySubmitScheduledUnitsLock.set(false)
    }
}

（二）限制任务对象数

实际上限制并发数并不能解决服务器卡顿的问题。但是在持续卡顿很长时间后会 OOM，这启发我们卡顿的原因不是并发数太高，而是任务对象占据的资源太多。因此我们打算也限制任务对象数。

具体地，我们希望在任务数足够时 schedule 立即返回，不够时挂起提交任务的协程，直到有任务数时恢复。

TODO