3

少し問題がありました。:)

常に N スレッドのみがバックグラウンド タスクを実行するようにしたいと考えています。これを行うために、固定スレッド プール エグゼキュータを使用しました。うまく機能しているように見えました。

その後、問題が見つかりました。エグゼキューターを使用していくつかの並列作業を行うクラスがあり、エグゼキューター スレッド内で別のクラスを呼び出し、そのスレッドも並列作業を行い、それを待機しようとしているとします。何が起こるかは次のとおりです。

  • メイン スレッドは、第 1 レベルのメソッドを呼び出します。
  • このメソッドは、16 のタスクに並列化できると考え、作業を分割します。
  • 16 個のタスクがエグゼキューターにサブミットされます。
  • メイン スレッドは、そのタスクが完了するのを待機し始めます。
  • 利用可能なスレッドが 4 つあるとすると、最初の 4 つのタスクがそれぞれ選択されて実行されます。したがって、キューには 12 個のタスクが残っています。
  • ここで、これらのタスクの 1 つが他のメソッドを呼び出します。
  • この新しい方法は、2 つのタスクに並列化できると考えています。それが並列マージソートの最初のステップであるか、それらの線に沿った何かであるとしましょう。
  • 2 つのタスクがエグゼキューターにサブミットされます。
  • このスレッドは、タスクが完了するのを待ち始めます。

ええとああ。そのため、この時点で、4 つのスレッドすべてがタスクの完了を待機していますが、これらのタスクを実際に実行しているエグゼキュータを共同でブロックしています。

この問題の解決策 1 は次のとおりです。エグゼキューターに新しいタスクを送信するときに、すべてのスレッドを既に実行しており、エグゼキューター スレッドの 1 つで既に実行している場合は、タスクをインラインで実行します。これは 10 か月間問題なく機能していましたが、現在問題が発生しています。サブミットしている新しいタスクがまだ比較的大きい場合、メソッドが他のタスクをキューに追加することを新しいタスクがブロックする状況に陥る可能性があります。そうしないと、他のワーカー スレッドによって取得される可能性があります。そのため、スレッドが作業をインラインで処理している間、かなりの遅延が発生します。

バックグラウンド タスクの潜在的に無限のツリーを実行するという中心的な問題に対するより良い解決策はありますか? executor サービスに相当する .NET には、キューから盗む何らかの組み込み機能があり、元のデッドロックの問題が発生するのを防ぎます。これは、私が知る限り、理想的なソリューションです。しかし、Java の土地ではどうでしょうか。

4

3 に答える 3

3

ForkJoinPoolJava 7 には、同じ Executor にサブミットすることで、タスクが別のタスクを「分岐」できるようにするの概念があります。次に、実行されていない場合に実行を試みることで、後でそのタスクの「参加を支援」するオプションを与えます。

と を組み合わせるだけで、Java 6 でも同じことができると思いExecutorますFutureTask。そのようです：

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

}
于 2011-03-10T01:34:15.353 に答える
1

タスクが完了するのをスレッドに待たせる代わりに、コールバックを利用することができます。より多くのタスクを送信するため、タスク自体はコールバックである必要があります。

例えば：

public class ParallelTask implements Runnable, Callback {
  private final Callback mCB;
  private final int mNumChildTasks;
  private int mTimesCalledBack = 0;
  private final Object mLock = new Object();
  private boolean mCompleted = false;
  public ParallelTask(Callback cb) {
    mCB = cb;
    mNumChildTasks = N; // the number of direct child tasks you know this task will spawn
    // only going down 1 generation
    // of course you could figure this number out in the run method (will need to be volatile if so)
   // just as long as it is set before submitting any child tasks for execution
  }

  @Override
  public void run() {
    // do your stuff
    // and submit your child tasks, but don't wait on them to complete
    synchronized(mLock) {
      mCompleted = true;
      if (mNumChildTasks == mTimesCalledBack) {
        mCB.taskCompleted();
      }
    }
  }

  // Callback interface
  // taskCompleted is being called from the threads that this task's children are running in
  @Override
  public void taskCompleted() {
    synchronized(mLock) {
      mTimesCalledBack++;
      // only call our parent back if our direct children have all called us back
      // and our own task is done
      if (mCompleted && mTimesCalledBack == mNumChildTasks) {
        mCB.taskCompleted();
      }
    }
  }
}

メインスレッドで、ルートタスクを送信し、実行するコールバックを登録します。

すべての子タスクは、子が完了を報告するまで完了を報告しないため、すべてが完了するまでルートコールバックを呼び出さないでください。

私はこれをその場で作成しましたが、テストもコンパイルもしていないため、エラーが発生する可能性があります。

于 2011-03-10T02:01:50.113 に答える
0

問題は、タスクもそれ自体を並列化しようとすることであり、リソースの制約を回避することが難しくなっているようです。なぜこれを行う必要があるのですか？サブタスクを常にインラインで実行しないのはなぜですか?

並列化によって既に CPU を十分に活用している場合は、作業を小さなタスクに再度分割することによって達成される全体的な作業に関して、多くを購入することはありません。

于 2011-03-10T01:34:54.227 に答える