ExecutorService：当在线程中执行同步屏障时，如何防止线程饥饿

Question

我有一个情况，我很难找到一个干净的解决方案。我会尽量详细解释的。

我有一个树状的结构：

NODE A
    NODE A.1
    NODE A.2
        NODE A.2.a
        NODE A.2.b
    NODE A.3
        NODE A.3.a
        NODE A.3.b
        NODE A.3.c
NODE B
    NODE B.1
    NODE B.2

我需要处理根节点：

 public void process(final Node node) { ... }

- some database queries
- the process of all children of these nodes

换句话说，一旦处理了node.2.a和node.2.b，就可以处理node.2。我以递归的方式处理节点，没有什么壮观的。

到目前为止，一切都很好。现在我要声明一个全局执行器服务，它有固定数量的线程。我想并行处理一个节点的子节点。因此，node.2.a和node.2.b可以在各自的线程中进行处理。代码如下所示：

// global executor service, shared between all process(Node) calls
final ExecutorService service = Executors.newFixedThreadPool(4);

public void process(final Node node) {
    // database queries
    ...

    // wait for children to be processed
    final CountDownLatch latch = new CountDownLatch(node.children().size());

    for (final Node child : node.children()) {
        service.execute(() -> {
             process(child);
             latch.countDown();
        });
    }
    latch.await();
}

这里的问题是：当达到一定深度时，锁存器中将停止所有线程。await()。我们已经到了缺线的情况。

Answer 1

从技术上来说，这是一个僵局。我们首先认为死锁是当两个或多个进程等待锁时，但在这种情况下，线程是相互等待的。有趣的是，这是一种产生自我僵局的奇怪野兽的方式。如果您有一个线程池，它将提交任务并等待它们，但从不执行，因为它在等待自己完成以执行它们！

标准答案被称为“工作窃取线程池”。我遇到了完全相同的问题，没有这部分词汇表，我花了很长时间才能找到任何关于我快速得出的结论的信息，这是在完全并发递归中执行的任何递归算法中的一个常见问题。

好的，这是它如何工作的草图。用一个技巧创建一个相当标准的线程池。当一个线程到达一个点时，如果没有排队项的结果，它就不能继续下去，检查该项是否由另一个线程启动，如果它没有在当前线程中执行它（而不是等待），否则等待执行该项的线程完成它。