12

高価な計算の結果をキャッシュするために使用しているコンピューティング マップ(ソフト値) があります。

ここで、特定のキーが次の数秒以内に検索される可能性が高いことがわかっている状況があります。そのキーは、ほとんどのキーよりも計算コストも高くなります。

最小優先度のスレッドで値を事前に計算して、値が最終的に要求されたときに既にキャッシュされているようにして、応答時間を改善したいと思います。

次のようにこれを行う良い方法は何ですか:

  1. 計算が実行されるスレッド (具体的にはその優先度) を制御できます。
  2. 重複作業が回避されます。つまり、計算は 1 回だけ実行されます。計算タスクが既に実行されている場合、呼び出し元のスレッドは、値を再度計算する代わりにそのタスクを待機します (FutureTaskこれを実装します。Guava の計算マップでは、呼び出しのみの場合は true ですがget、呼び出しと組み合わせた場合は異なりますput。)
  3. 「事前に値を計算する」方法は、非同期で冪等です。計算がすでに進行中の場合は、その計算が完了するのを待たずにすぐに戻る必要があります。
  4. 優先度の逆転を回避します。たとえば、優先度の高いスレッドが値を要求し、優先度が中程度のスレッドが無関係なことを行っているが、計算タスクが優先度の低いスレッドでキューに入れられている場合、優先度の高いスレッドを飢えさせてはなりません。おそらくこれは、計算スレッドの優先度を一時的に上げたり、呼び出しスレッドで計算を実行したりすることで実現できます。

関連するすべてのスレッド間でこれをどのように調整できますか?

追加情報
私のアプリケーションでの計算は画像フィルタリング操作です。つまり、すべて CPU バウンドです。これらの操作には、アフィン変換 (50 マイクロ秒から 1 ミリ秒までの範囲) と畳み込み (最大 10 ミリ秒) が含まれます。もちろん、さまざまなスレッドの優先度の有効性は、OS がより大きなタスクをプリエンプトする能力に依存します。

4

4 に答える 4

8

ComputedMap で Future を使用することにより、バックグラウンド計算を「1 回だけ」実行するように調整できます。Future は、値を計算するタスクを表します。future は ComputedMap によって作成され、同時にバックグラウンド実行のためにExecutorServiceに渡されます。エグゼキューターは、優先度の低いスレッドを作成する独自のThreadFactory実装で構成できます。

class LowPriorityThreadFactory implements ThreadFactory
{
   public Thread newThread(Runnable r) {
     Tread t = new Thread(r);
     t.setPriority(MIN_PRIORITY);
     return t;
   }
}

値が必要になると、優先順位の高いスレッドがマップから未来をフェッチし、get() メソッドを呼び出して結果を取得し、必要に応じて計算されるのを待ちます。優先度の逆転を回避するには、タスクにコードを追加します。

class HandlePriorityInversionTask extends FutureTask<ResultType>
{
   Integer priority;  // non null if set
   Integer originalPriority;
   Thread thread;
   public ResultType get() {
      if (!isDone()) 
         setPriority(Thread.currentThread().getPriority());
      return super.get();
   }
   public void run() {
      synchronized (this) {
         thread = Thread.currentThread();
         originalPriority = thread.getPriority();
         if (priority!=null) setPriority(priority);
      } 
      super.run();
   }
   protected synchronized void done() {
         if (originalPriority!=null) setPriority(originalPriority);
         thread = null;
   }

   void synchronized setPriority(int priority) {
       this.priority = Integer.valueOf(priority);
       if (thread!=null)
          thread.setPriority(priority);
   }
}

これにより、タスクが完了していない場合は、タスクの優先度がスレッド呼び出しの優先度まで引き上げられ、get()タスクが正常またはそれ以外の場合に完了したときに優先度が元に戻されます。(簡潔にするために、コードは優先度が実際に大きいかどうかをチェックしませんが、それは簡単に追加できます。)

優先度の高いタスクが get() を呼び出したとき、future はまだ実行を開始していない可能性があります。エグゼキュータ サービスが使用するスレッド数に大きな上限を設定することで、これを回避したくなるかもしれませんが、これは悪い考えかもしれません。各スレッドが高い優先度で実行され、可能な限り多くの CPU を消費する可能性があるからです。 OSはそれを切り替えます。プールはおそらくハードウェア スレッドの数と同じサイズにする必要があります。たとえば、プールのサイズをRuntime.availableProcessors(). タスクの実行が開始されていない場合は、executor がスケジュールを設定するのを待つのではなく (優先度の高いスレッドが優先度の低いスレッドが完了するのを待っているため、これは優先度の逆転の一種です)、タスクをキャンセルすることを選択できます。現在のエグゼキュータを再送信し、優先度の高いスレッドのみを実行しているエグゼキュータで再送信します。

于 2010-07-13T18:00:24.050 に答える
2

スレッドの優先順位に注目することで、間違った道を進んでいると思われます。通常、キャッシュが保持するデータは、I/O (メモリー不足データ) と CPU バウンド (論理計算) の計算にコストがかかります。未読の電子メールを見るなど、ユーザーの将来のアクションを推測するためにプリフェッチしている場合、それはあなたの作業が I/O バウンドである可能性が高いことを示しています。これは、スレッドの枯渇が発生しない限り (スケジューラーが許可しない)、スレッドの優先度を使用してゲームをプレイしても、パフォーマンスはあまり向上しないことを意味します。

コストが I/O 呼び出しである場合、バックグラウンド スレッドはデータが到着するのを待ってブロックされ、そのデータの処理はかなり安価になります (逆シリアル化など)。スレッドの優先度を変更しても速度はあまり向上しないため、バックグラウンド スレッドプールで非同期に作業を実行するだけで十分です。キャッシュ ミスのペナルティが高すぎる場合は、複数のキャッシュ レイヤーを使用すると、ユーザーが認識するレイテンシをさらに短縮するのに役立つ傾向があります。

于 2010-07-08T19:46:58.927 に答える
2

このような状況を調整する一般的な方法の 1 つは、値が FutureTask オブジェクトであるマップを用意することです。例として、私の Web サーバーから私が書いたコードを盗みます。重要なアイデアは、特定のパラメーターに対して、FutureTask が既に存在するかどうか (つまり、そのパラメーターを使用した計算が既にスケジュールされていることを意味します) を確認することです。もしそうなら、私たちはそれを待ちます。この例では、別の方法でルックアップをスケジュールしますが、それが望ましい場合は別の呼び出しで別の場所で実行できます。

  private final ConcurrentMap<WordLookupJob, Future<CharSequence>> cache = ...

  private Future<CharSequence> getOrScheduleLookup(final WordLookupJob word) {
    Future<CharSequence> f = cache.get(word);
    if (f == null) {
      Callable<CharSequence> ex = new Callable<CharSequence>() {
        public CharSequence call() throws Exception {
          return doCalculation(word);
        }
      };
      Future<CharSequence> ft = executor.submit(ex);
      f = cache.putIfAbsent(word, ft);
      if (f != null) {
        // somebody slipped in with the same word -- cancel the
        // lookup we've just started and return the previous one
        ft.cancel(true);
      } else {
        f = ft;
      }
    }
    return f;
  }

スレッドの優先度に関して: これであなたの考えが実現するのだろうか? 待機中のスレッドよりもルックアップの優先度を上げることについてのあなたのポイントをよく理解していません。スレッドが待機している場合、他のスレッドの相対的な優先度に関係なく、待機しています...（いくつか見たいと思うかもしれませんスレッドの優先度とスレッドのスケジューリングに関する記事を書いてきましたが、簡単に言うと、優先度を変更することで、期待どおりの結果が得られるかどうかはわかりません。)

于 2010-07-08T15:53:43.320 に答える
1

スレッドの優先順位の代わりに、優先順位の高いタスクが進行中でない場合にのみ、優先順位の低いタスクを実行できます。これを行う簡単な方法は次のとおりです。

AtomicInteger highPriorityCount = new AtomicInteger();

void highPriorityTask() {
  highPriorityCount.incrementAndGet();
  try {
    highPriorityImpl();
  } finally {
    highPriorityCount.decrementAndGet();  
  }
}

void lowPriorityTask() {
  if (highPriorityCount.get() == 0) {
    lowPriorityImpl();
  }
}

あなたのユースケースでは、両方の Impl() メソッドが計算マップで get() を呼び出し、同じスレッドで highPriorityImpl() を呼び出し、別のスレッドで lowPriorityImpl() を呼び出します。

優先度の高いタスクが完了するまで優先度の低いタスクを延期し、優先度の低い同時実行タスクの数を制限する、より洗練されたバージョンを作成できます。

于 2010-07-14T11:50:35.393 に答える