20

私の現在のシナリオでは速度が不可欠です。複数のスレッドによってのみ読み取られるマップがあり、これは正常に機能します。ここで、マップが他のスレッドによって読み取られている間に、時々静的マップへの書き込みが必要になる可能性があるという要件が発生しました。スレッド セーフのためにマップをロックする必要があるため、これはゲーム チェンジャーだと思います。これは、マップを読み取る複数のスレッド 10 ～ 12 のスレッドがあるため、問題を引き起こします。1 つのマップが (その読み取り以降) マップをロックする場合、何かがマップに書き込まれる可能性があるため、ロックが必要になると思います。とにかく、先に述べたように、1 つのマップが読み取り中の場合、他のマップは以前のようにマップへの並列読み取りアクセスを持ちません。この問題を回避する方法はありますか?

4

6 に答える 6

17

shared_mutexマップの横にあるを使用して、共有または固有のアクセスを取得できます。一般に、書き込み操作には一意のアクセスが必要ですが、読み取り操作には共有アクセスが必要です。

一意のアクセスを保持しているスレッドがない限り、任意の数のスレッドが共有アクセスを取得できます。スレッドが一意のアクセスを取得しようとすると、すべての共有アクセスが解放されるまで待機します。

標準ライブラリと Boost はshared_lock<T>、 とunique_lock<T>の範囲限定の取得を提供しshared_mutexます。

shared_mutexこれらの主張を裏付ける証拠や強力な分析は見たことがありませんが、パフォーマンスが悪いと主張する人がいることに注意してください. あなたにとって重要な場合は、検討する価値があるかもしれません。

于 2013-10-02T17:43:24.463 に答える
8

解決策の 1 つは、そのマップへのポインターを保持し、それを変更する必要がある場合は、コピーを作成し、そのコピーを変更してから、ポインターを新しいインスタンスに原子的に交換することです。このソリューションはより多くのメモリを消費しますが、この方法はロックフリーであるため、多くの読み取りスレッドがある場合はより効率的です。

以下の例では、1 つのスレッドのみがマップを変更できます。これは、一度に 1 つのスレッドを意味するのではなく、データ構造の存続期間中、1 つの同じスレッドを意味します。それ以外の場合は、コード全体を保護するミューテックスを保持しながら変更を行う必要がありますupdateMap。リーダー スレッドはtheData、ロックなしで通常どおりアクセスできます。

typedef std::map<...> Data;

std::atomic<Data *> theData;

void updateMap( ... )
{
   Data *newData = new Data( *theData );
   // modify newData here
   Data *old = theData.exchange( newData );
   delete old;
}
于 2013-10-02T17:48:00.123 に答える
0

必要なのは、Java の ConcurrentHashMap に相当するものです。これにより、基になるハッシュ テーブルへの同時読み取りと書き込みが可能になります。このクラスは、java.util.concurrent パッケージの一部であり、同時読み取りおよび書き込み (同時実行レベルまで、デフォルトは 16) を提供します。

詳細については、javadocを参照してください。ここでjavadocを引用しています：

取得の完全な同時実行性と更新の調整可能な予想同時実行性をサポートするハッシュ テーブル。このクラスは、Hashtable と同じ機能仕様に従い、Hashtable の各メソッドに対応するバージョンのメソッドを含みます。ただし、すべての操作はスレッドセーフですが、取得操作にはロックが必要ではなく、すべてのアクセスを防止する方法でテーブル全体をロックすることはサポートされていません。このクラスは、スレッド セーフに依存しているが同期の詳細には依存していないプログラムで Hashtable と完全に相互運用できます。

于 2013-10-02T17:53:59.787 に答える
0

他の 2 つの回答はまったく問題ありませんが、少し色を追加する必要があると考えました。

Cliff Click はJava でロックフリーの同時ハッシュ マップを作成しました。 それを C++ に適応させることは自明ではありませんが (GC なし、別のメモリ モデルなど)、私が今まで見たロックフリー データ構造の最良の実装です。C++ の代わりに Java を使用できる場合は、これが適している可能性があります。

ロックフリーのバランスのとれた二分木構造については知りません。それは、それらが存在しないという意味ではありません。

代わりにshared_ptrへのアクセスを制御するには、他の 2 つの回答 (一括コピー/アトミック スワップ/何か、またはリーダー/ライター ロック) のいずれかを使用するのがおそらく最も簡単です。map読み取りと書き込みの相対的な量とファイルのサイズに応じて、2 つのうちの 1 つが高速になりmapます。どちらを使用すべきかを確認するためにベンチマークする必要があります。

于 2013-10-02T18:03:31.153 に答える