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();
}

这里的问题是:当达到某个深度时,所有线程都停止在latch.await().我们已经达到线程饥饿的局面.

这可以通过使执行程序服务无限制来轻松解决,但我不喜欢这个选项.我想控制active线程数.在我的例子中,active线程数将等于核心数.拥有更多active线程将引入从一个线程到另一个线程的交换,我想避免这种情况.

怎么解决这个问题？

Answer 1

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

标准答案称为“工作窃取线程池”。我遇到了完全相同的问题，如果没有那个词汇，我需要很长时间才能找到有关我很快发现的任何信息，这是在完全并发递归中执行的任何递归算法中的常见问题。

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

它非常简单，但可能需要您构建自己的线程池类，因为现成的解决方案通常不支持它。

当然，请注意，典型的非平凡递归算法将分解为比并行处理单元更多的子任务。因此，将子任务排队到一定级别，然后在单个线程中执行剩余部分可能是有意义的。

也就是说，除非入队和出队的项目很便宜，否则您可以花时间将项目放入队列中以将其取回。这些操作可以在线程之间串行化并减少并行性。很难使用无锁队列，因为它们通常不允许从队列中间提取（如此处所要求的）。您应该限制平行的深度。

从好的方面来看，请注意，在当前正在执行的线程中执行任务涉及的任务交换开销比停放当前线程和（在操作系统级别）交换另一个工作线程要少。

这是一个 Java 资源，它提供了WorkStealingThreadPool. 请注意，我没有努力评估实施情况，也没有提供任何建议。在这种情况下，我一直在 C++ 中工作，或者很乐意分享我的template.

https://www.jrebel.com/blog/using-java-executors

另请参阅维基百科的内容：https ://en.wikipedia.org/wiki/Work_stealing