11

過去の質問で、私は破壊レースなしでpthreadバリアを実装することについて尋ねました：

pthread_barrier_waitが戻るとすぐに、バリアを破棄するにはどうすればよいですか？

そして、Michael Burrから、プロセスローカルバリアの完璧なソリューションを受け取りましたが、プロセス共有バリアでは失敗します。その後、いくつかのアイデアに取り組みましたが、満足のいく結論に達することはなく、リソース障害のケースにさえ入り始めませんでした。

Linuxで、次の条件を満たすバリアを作成することは可能ですか。

  • プロセス共有（任意の共有メモリに作成できます）。
  • バリア待機関数が戻った直後に、任意のスレッドからバリアをマップ解除または破棄しても安全です。
  • リソース割り当ての失敗が原因で失敗することはありません。

プロセス共有のケースを解決しようとするMichaelの試み（リンクされた質問を参照）には、待機時に何らかのシステムリソースを割り当てる必要があるという不幸な性質があります。つまり、待機が失敗する可能性があります。そして、バリア待機が失敗したときに発信者が合理的に何ができるかは不明です。なぜなら、バリアの全体的なポイントは、残りのN-1スレッドがそれに到達するまで続行するのは安全ではないということです...

カーネルスペースソリューションが唯一の方法かもしれませんが、信号が待機を中断し、それを再開する信頼できる方法がない可能性があるため、それでも困難です...

4

3 に答える 3

2

これは Linux の futex API では不可能であり、これも証明できると思います。

ここでは基本的に、N 個のプロセスを 1 つの最終プロセスによって確実に目覚めさせる必要があり、さらに、最終的な目覚めの後にプロセスが共有メモリに触れてはならないというシナリオがあります (非同期で破棄または再利用される可能性があるため)。すべてのプロセスを簡単に目覚めさせることができますが、基本的な競合状態は起床と待機の間にあります。待機の前にウェイクアップを発行すると、ストラグラーは決してウェイクアップしません。

このようなことに対する通常の解決策は、ストラグラーに待機でアトミックにステータス変数をチェックさせることです。これにより、ウェイクアップがすでに発生している場合、スリープをまったく回避できます。ただし、ここではこれを行うことはできません。ウェイクアップが可能になるとすぐに、共有メモリにアクセスするのは安全ではありません!

もう 1 つの方法は、すべてのプロセスがまだスリープ状態になっているかどうかを実際に確認することです。ただし、これは Linux futex API では不可能です。ウェイター数の唯一の指標は、FUTEX_WAKE からの戻り値です。期待した数よりも少ない数のウェイターが返された場合は、まだ寝ていない人がいることがわかります。しかし、ウェイターを十分に目覚めさせていないことがわかったとしても、何かをするには遅すぎます。目覚めたプロセスの 1 つがすでにバリアを破壊している可能性があります。

残念ながら、この種の即時破棄可能なプリミティブは、Linux futex API では構築できません。

1 つのウェイターと 1 つのウェイカーの特定のケースでは、問題を回避できる可能性があることに注意してください。FUTEX_WAKE が 0 を返した場合、実際にはまだ誰も起きていないことがわかり、回復するチャンスがあります。ただし、これを効率的なアルゴリズムにするのは非常に困難です。

これを修正する堅牢な拡張機能を futex モデルに追加するのは難しいことです。基本的な問題は、N 個のスレッドがいつ正常に待機に入ったのかを知る必要があり、それらすべてをアトミックに目覚めさせる必要があることです。ただし、これらのスレッドはいつでもシグナルハンドラーを実行するために待機を終了する可能性があります。実際、ウェイカースレッドもシグナルハンドラーの待機を終了する可能性があります。

ただし、機能する可能性のある 1 つの方法は、NT APIのキー付きイベントモデルの拡張です。キー付きイベントでは、スレッドはペアでロックから解放されます。「待機」のない「リリース」がある場合、「リリース」呼び出しは「待機」をブロックします。

シグナルハンドラの問題により、これだけでは十分ではありません。ただし、'release' 呼び出しでアトミックに起動するスレッド数を指定できるようにすると、これは機能します。バリア内の各スレッドにカウントをデクリメントさせ、そのアドレスのキー付きイベントを「待機」させるだけです。最後のスレッドは N - 1 スレッドを「解放」します。カーネルは、すべての N-1 スレッドがこのキー付きイベント状態になるまで、ウェイク イベントの処理を許可しません。いずれかのスレッドがシグナル (解放スレッドを含む) のために futex 呼び出しを離れた場合、これにより、すべてのスレッドが戻るまで、ウェイクアップがまったく防止されます。

于 2011-09-24T03:32:23.493 に答える
1

SO チャットで bdonlan と長い間話し合った結果、解決策があると思います。基本的に、この問題を、破棄操作とマッピング解除という 2 つの自己同期化解除の問題に分けます。

破棄の処理は簡単ですpthread_barrier_destroy。すべてのウェイターがバリアの検査を停止するまで関数を待機させるだけです。これは、バリアに使用回数を設定し、待機関数の開始/終了時にアトミックにインクリメント/デクリメントし、カウントがゼロになるまで破棄関数をスピン待機させることで実行できます。(使用カウントの上位ビットなどにウェイター フラグを設定すると、回転するだけでなく、ここで futex を使用することもできます。)

マッピング解除の処理も簡単ですが、ローカルではありません。syscall ラッパーにロックを追加することで、バリア ウェイターが終了処理中にフラグを使用して or が発生しないようにしますmunmap。これには、特殊な種類のリーダー/ライター ロックが必要です。最後にバリアに到達したウェイターは、rw ロックの読み取りロックを取得する必要があります。これは、最後のウェイターが終了したときに解放されます (ユーザー カウントをデクリメントするとカウントが 0 になる場合)。また、ライター ロックを再帰的にすることで、再入可能にすることができます (一部のプログラムでは想定されているように、POSIX では必要ありませんが)。実際には、リーダーとライターが完全に対称的であり、各タイプのロックが反対のタイプのロックを除外するが、同じタイプではない一種のロックが最適に機能するはずです。mmapMAP_FIXEDmunmapmunmapmmap

于 2011-09-27T04:56:03.193 に答える
0

うーん、不器用なアプローチでできると思います...

「バリア」をソケットでリッスンする独自のプロセスにします。barrier_wait を次のように実装します。

open connection to barrier process
send message telling barrier process I am waiting
block in read() waiting for reply

N 個のスレッドが待機すると、バリア プロセスはそれらすべてに続行するように指示します。次に、各ウェイターはバリア プロセスへの接続を閉じて続行します。

barrier_destroy を次のように実装します。

open connection to barrier process
send message telling barrier process to go away
close connection

すべての接続が閉じられ、バリア プロセスが終了するように指示されると、終了します。

[編集: 確かに、これは待機操作と解放操作の一部としてソケットを割り当てて破棄します。しかし、そうしなくても同じプロトコルを実装できると思います。下記参照。]

最初の質問: このプロトコルは実際に機能しますか? あると思いますが、要件を理解していない可能性があります。

2 番目の質問: 機能する場合、余分なプロセスのオーバーヘッドなしでシミュレートできますか?

答えは「イエス」だと思います。適切なタイミングで、各スレッドがバリア プロセスの「役割を担う」ことができます。現在バリアプロセスの「役割を担っている」スレッドが保持するマスターミューテックスが必要です。詳細、詳細... わかりましたので、barrier_wait は次のようになります。

lock(master_mutex);
++waiter_count;
if (waiter_count < N)
    cond_wait(master_condition_variable, master_mutex);
else
    cond_broadcast(master_condition_variable);
--waiter_count;
bool do_release = time_to_die && waiter_count == 0;
unlock(master_mutex);
if (do_release)
    release_resources();

ここで、(master_mutexミューテックス)、master_condition_variable(条件変数)、waiter_count(符号なし整数)、N(別の符号なし整数)、およびtime_to_die(ブール値) はすべて、barrier_init によって割り当てられ、初期化される共有状態です。 waiter_countゼロ、time_to_diefalse、およびNバリアが待機しているスレッド数に初期化されます。

その場合、barrier_destroy は次のようになります。

lock(master_mutex);
time_to_die = true;
bool do_release = waiter_count == 0;
unlock(master_mutex);
if (do_release)
    release_resources();

信号処理などの詳細については不明ですが、「最後の 1 つはライトをオフにする」という基本的な考え方は実行可能だと思います。

于 2011-08-04T04:37:16.260 に答える