递归并发

我有以下功能，在伪代码：递归并发

Result calc(Data data) { 
    if (data.isFinal()) { 
    return new Result(data); // This is the actual lengthy calculation 
    } else { 
    List<Result> results = new ArrayList<Result>(); 
    for (int i=0; i<data.numOfSubTasks(); ++i) { 
     results.add(calc(data.subTask(i)); 
    } 
    return new Result(results); // merge all results in to a single result 
    } 
}

我想并行化，使用线程固定数目的。

我第一次尝试是：

ExecutorService executorService = Executors.newFixedThreadPool(numOfThreads); 

Result calc(Data data) { 
    if (data.isFinal()) { 
    return new Result(data); // This is the actual lengthy calculation 
    } else { 
    List<Result> results = new ArrayList<Result>(); 
    List<Callable<Void>> callables = new ArrayList<Callable<Void>>(); 
    for (int i=0; i<data.numOfSubTasks(); ++i) { 
     callables.add(new Callable<Void>() { 
     public Void call() { 
     results.add(calc(data.subTask(i)); 
     } 
     }); 
    } 
    executorService.invokeAll(callables); // wait for all sub-tasks to complete 
    return new Result(results); // merge all results in to a single result 
    } 
}

不过，这很快就陷入了一种僵局，因为，而前递归级别等待所有线程完成，内部级别也等待线程变得可用...

如何在没有死锁的情况下高效并行我的程序？

来源

2013-02-26 Erel Segal-Halevi

什么问题？ – 2013-02-26 08:15:59

我们在代码中看不到任何同步，所以我们无法帮助您找到死锁。提供的代码与死锁无关。 – ATrubka 2013-02-26 08:17:58

它可能只是，那numOfThreads小于callables.size（）？你应该确保在你的实现中，你有更多的线程比可调参数（在树上）.. – cybye 2013-02-26 08:19:30

您的问题是使用ThreadPoolExecutor进行具有依赖性的任务时的一般设计问题。

我看到两个选项：

1）确保在自下而上的顺序提交任务，所以你永远不会有一个正在运行的任务，取决于这并没有开始一个任务。

2）使用“直接切换”战略（见ThreadPoolExecutor文档）：

ThreadPoolExecutor executor = new ThreadPoolExecutor(poolSize, poolSize, 0, TimeUnit.SECONDS, new SynchronousQueue<Runnable>()); 
executor.setRejectedExecutionHandler(new CallerRunsPolicy());

的想法是使用同步队列，以便任务从来没有在一个真正的排队等候。拒绝处理程序负责处理没有可用线程运行的任务。通过这个特定的处理程序，提交者线程运行被拒绝的任务。

此执行程序配置保证任务永远不会被拒绝，并且由于任务间依赖性，您永远不会发生死锁。

来源

2013-02-26 08:51:35

与2）你是否遇到过这个问题，所有的游泳池都充满了转储组织，所有繁重的工作都将由来电者完成？ – cybye 2013-02-26 08:57:20

@cybye：这种情况下的“调用者”是池中的一个线程，或者其中的很多线程。所以他们不是等待他们的依赖关系，而是实际处理数据。 – 2013-02-26 08:59:34

看起来不错，比期货更容易理解.. – cybye 2013-02-26 09:03:31

你应分两个阶段分割你的做法：

下创建所有的树，直到data.isFinal（）==真
递归收集结果（仅当合并不会产生其他操作/呼叫）

为此，您可以使用[Futures][1]使结果异步。意味着calc的所有结果将是Future类型[结果]。

立即返回Future将释放当前线程并为其他处理提供空间。通过收集结果（新结果（结果）），您应该等待所有结果准备就绪（ScatterGather-Pattern，您可以使用信号灯等待所有结果）。集合本身将会走在树上，检查（或等待结果到达）将在单个线程中发生。

总体而言，您将构建一棵期货结构树，用于收集结果并仅执行线程池中的“昂贵”操作。

来源

2013-02-26 08:42:03 cybye

回答

相关问题