使用ExecutorService和要执行的任务树 [英] Using ExecutorService with a tree of tasks to perform

问题描述

我们遇到了一些问题。 ：）

We had a bit of a problem. :)

我们希望确保只有N个线程可以随时执行后台任务。为此，我们使用了一个固定的线程池执行器。它似乎工作正常。

We want to ensure that only N threads are doing background tasks at any time. To do this, we used a fixed thread pool executor. It seemed to be working fine.

然后我们发现了一个问题。假设你有一个类使用执行程序进行一些并行工作，然后在执行程序线程中调用其他类，这也执行一些并行工作，打算等待它。这是发生的事情：

Then we found an issue. Suppose you have a class which uses the executor to do some parallel work and then it calls some other class while in the executor thread which also does some parallel work, intending to wait on it. Here's what happens:

• 主线程调用第一级方法。


• 此方法认为它可以并行分为16个任务并拆分其工作。


• 将16个任务提交给执行者。


• 主线程开始等待其任务完成。


• 假设有四个线程可用，前四个任务分别被选中并运行。所以队列中还剩下12个任务。


• 现在，其中一个任务调用了其他一些方法。


• 这个新方法认为它可以并行化分为2个任务。让我们说它是并行合并排序的第一步或者沿着这些行的东西。


• 将2个任务提交给执行者。


• 此线程现在开始等待其任务完成。

• Main thread calls the first level method.
• This method thinks it can parallelise into 16 tasks and splits up its work.
• 16 tasks are submitted to the executor.
• Main thread starts waiting for its tasks to complete.
• Supposing there are four threads available, the first four tasks each get picked up and run. So there are 12 tasks left on the queue.
• Now, one of these tasks calls some other method.
• This new method thinks it can parallelise into 2 tasks. Let's say it's the first step in a parallel merge sort or something along those lines.
• 2 tasks are submitted to the executor.
• This thread now starts waiting for its tasks to complete.

呃哦。所以在这一点上，所有四个线程现在都在等待任务完成，但它们正在协同阻止执行者实际运行这些任务。

Uh-oh. So at this point, all four threads will now be waiting for tasks to complete but they are collaboratively blocking the executor actually running those tasks.

此问题的解决方案1是如下：在向执行程序提交新任务时，如果我们已经在运行所有线程，并且我们已经在其中一个执行程序线程上运行，则运行内联任务。这个工作正常10个月，但现在我们遇到了问题。如果它提交的新任务仍然相对较大，那么您可能会遇到新任务阻止该方法将其他任务添加到队列的情况，否则其他工作线程将能够接收该任务。因此，当线程正在处理内联工作时，会出现大量延迟。

Solution 1 to this problem was as follows: on submitting a new task to the executor, if we are already running all our threads, and we are already running on one of the executor threads, run the task inline. This worked fine for 10 months, but now we have hit a problem with it. If the new tasks it is submitting are still relatively large, then you can get into a situation where the new task blocks the method from adding the other tasks to the queue, which would otherwise be able to be picked up by the other worker threads. So you get periods of huge delays while a thread is processing the work inline.

是否有更好的解决方案来执行可能无限制的后台任务树的核心问题？我知道.NET等同于执行程序服务具有从队列中窃取的某种内置能力，这可以防止发生原始死锁问题，据我所知，这是一个理想的解决方案。但是在Java领域呢？

Is there a better solution to the core problem of executing a potentially unbounded tree of background tasks? I understand that .NET's equivalent to the executor service has some kind of in-built ability to steal from the queue which prevents the original deadlock issue from occurring, which as far as I can tell is an ideal solution. But what about over in Java land?

推荐答案

Java 7的概念是 ForkJoinPool 允许任务通过将其提交给同一个Executor来分离另一个任务。然后给它选择稍后尝试帮助加入该任务，如果它还没有运行则尝试运行它。

Java 7 has the concept of a ForkJoinPool that allows a task to "fork" off another task by submitting it tot he same Executor. Then gives it the option of later attempting to "help join" that task by attempting to run it if it has not been run.

我相信可以做同样的事情在Java 6中简单地将 Executor 与 FutureTask 组合在一起。像这样：

I believe the same thing can be done in Java 6 by simple combining an Executor with FutureTask. Like so:

public class Fib implements Callable<Integer> {
    int n;
    Executor exec;

    Fib(final int n, final Executor exec) {
        this.n = n;
        this.exec = exec;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public Integer call() throws Exception {
        if (n == 0 || n == 1) {
            return n;
        }

        //Divide the problem
        final Fib n1 = new Fib(n - 1, exec);
        final Fib n2 = new Fib(n - 2, exec);

        //FutureTask only allows run to complete once
        final FutureTask<Integer> n2Task = new FutureTask<Integer>(n2);
        //Ask the Executor for help
        exec.execute(n2Task);

        //Do half the work ourselves
        final int partialResult = n1.call();

        //Do the other half of the work if the Executor hasn't
        n2Task.run();

        //Return the combined result
        return partialResult + n2Task.get();
    }

}        

这篇关于使用ExecutorService和要执行的任务树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！