5

pthread を使用して分割統治を実装したいのですが、スレッドにさらにスレッドを作成するとどうなるかわかりません。

私の理解では、マシンに 2 コア プロセッサが搭載されている場合、同時に 2 つのスレッドしか処理できません。2 つ以上のスレッドがある場合は、他のスレッドがリソースを待機する必要があるため、より深く掘り下げてさらに多くのスレッドを作成すると、実際には 2 つのスレッドしか処理できないため、アルゴリズムの速度が向上しない可能性があります。同時に。

私はオンラインでいくつかの調査を行っており、上位レベルのスレッドが非アクティブになる可能性があり、最も深いレベルのスレッドのみがアクティブのままになるようです。これを達成する方法は？また、上糸が使用されていない場合、下糸に影響はありますか?

4

3 に答える 3

6

分離型と結合型の 2 つの基本的なタイプがあります。

結合可能なスレッドは、 を使用して終了を待つ (またはその結果にアクセスする) ことができるスレッドですpthread_join。

コアよりも多くのスレッドを使用すると、プログラムによって異なります。多くの場合、マルチスレッドを使用してリソースの競合を最小限に抑えるか、またはなくすとよいでしょう。プログラムでスローされるスレッドが多すぎると、実際にはプロセスが遅くなる可能性があります。ただし、コアの数がスレッド数と一致し、スレッドの 1 つがディスク IO で待機している場合 (他のプロセスで重要なことが何も起こっていない場合)、アイドル状態の CPU 時間が発生する可能性があります。

上位レベルのスレッドは非アクティブになる可能性があり、最も深いレベルのスレッドのみがアクティブなままです。これを達成する方法は？

結合可能なスレッドを使用すると、概要を説明したネストされたスレッドのアプローチを実現できます。これは、いくつかのチュートリアルで示されています。基本的な流れは、スレッドが 1 つ以上のワーカーを作成し、 を使用してそれらが終了するのを待つというものpthread_joinです。ただし、ほとんどの場合、タスクやスレッド プールなどの代替手段を使用することをお勧めします。

それにもかかわらず、特にプログラムの深さと幅が大きくなるにつれて、ハードウェアおよびスケジューリング操作と (うまく) 相関しないため、このアプローチが実行に最適である可能性は低いです。

上糸が非アクティブのままである場合、下糸には影響しませんか?

はい。ただし、典型的な問題は、作業/スレッドが制限されていないことです。概説したアプローチを使用すると、多くのスレッドを簡単に生成し、限られた数のコアで実行する必要がある作業のために非論理的に多数のスレッドを使用できます。その結果、プログラムはコンテキストの切り替えとスレッドの完了の待機に多くの時間を浪費することになります。多くのスレッドを作成すると、特に存続期間が短い場合やアイドル/待機中の場合、大量のリソースが浪費/予約される可能性があります。

そのため、深く掘り下げながらスレッドをどんどん作成しても、同時に処理できるスレッドは 2 つだけなので、実際にはアルゴリズムの速度は向上しない可能性があります。

これは、このアプローチを使用してスレッドを作成することに欠陥があることを示唆しています。代わりにいくつかのスレッドを作成し、各スレッドがコレクションからタスクを要求して実行するタスク ベースのアプローチを使用することもできます。スレッドの作成には、かなりの時間とリソースが必要です。

于 2012-05-15T10:06:46.720 に答える
2

双方向の分割統治を行おうとしていて、2 つの子を生成して、それらが終了するのを待っている場合は、おそらく次のようなものが必要です。

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  pthread_create (left_child, NULL, routine, left_arg);
  pthread_create (right_child, NULL, routine, right_arg);

  /* wait for 'children' */
  pthread_join (left_child, &left_return_val);
  pthread_join (right_child, &right_return_val);

  /* merge results & return */
}

わずかな改善は次のようになります。スリープする代わりに、「親スレッド」が適切な子のジョブを同期的に実行し、1 つ少ないスレッドを生成します。

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  pthread_create (left_child, NULL, routine, left_arg);
  /* do the right_child's work yourself */
  right_return_val = routine (right_arg);

  /* wait for 'left child' */
  pthread_join (left_child, &left_return_val);

  /* merge results & return */
}

ただし、N レベルの深さまで進むと、かなりの数の子ができます。P得られるスピードアップは、CPU が実際の処理にkP費やす時間と I/O などを待つ時間に大きく依存します。上記のようにスレッドを生成する代わりに、スレッドの「ワーカー プール」を設定し、kPそれらを再利用し続けることができます。このように、kPスレッドが生成されると、それ以上生成されなくなります。

THREAD_POOL pool = new_thread_pool (k * P); /* I made this function up */

void *
routine (void * argument)
{
  /* divide */
  left_arg = f (argument);
  right_arg = f (argument);

  /* conquor */
  left_thread = get_worker (pool); /* Blocks until a thread is free  */
  /* get left_thread to do processing for you */

  right_thread = get_worker (pool); /* Blocks until a thread is free  */
  /* get right_thread to do processing for you */

  /* wait for 'children' */
  pthread_join (left_child, &left_return_val);
  pthread_join (right_child, &right_return_val);

  /* return the workers */
  put_worker (pool, left_thread);
  put_worker (pool, right_thread);

  /* merge results & return */
}
于 2012-05-15T10:45:02.360 に答える
0

システムにあるコアよりも多くのスレッドを作成できるはずです。オペレーティング システムは、すべてのスレッドが CPU の一部として機能するようにします。

ただし、[おそらく] 作成できるスレッドの数には上限があります (OS のドキュメントを確認してください)。

したがって、2 つのコアを持つシステムで 5 つのスレッドを作成すると、すべてのスレッドが (平均で) CPU の約 40% を取得します。別のスレッドが完全に終了するまでスレッドを待たなければならないわけではありません。もちろん、ロックを使用しない限り。

ロックを使用してデータが複数のスレッドによって変更またはアクセスされないように保護すると、多くの問題が発生する可能性があります。典型的な問題は次のとおりです。

  • デッドロック: スレッド 1 は、スレッド 2 によってロックされているものを待機します。スレッド 2 は、スレッド 1 によってロックされているものを待機します
  • ロックコンボイ: 複数のスレッドがすべて同じロックで待機しています
  • 優先順位の逆転: スレッド 1 はスレッド 2 よりも優先されますが、スレッド 2 はほとんどの場合ロックを保持しているため、スレッド 1 はスレッド 2 を待機する必要があります。

このページ ( http://ashishkhandelwal.arkutil.com/index.php/csharp-c/issues-with-multithreaded-programming-part-1/ ) を見つけました。これは、マルチスレッド プログラミングの良い出発点になる可能性があります。

于 2012-05-15T10:10:36.653 に答える