3

私は並行連想コンテナーを探していましたがconcurrent_unordered_map、私のすべてのニーズに合うように思われる Thead Building Blocks から見つけました。ドキュメントを読んでも、消去がどのように機能するかについての例は 1 つも見つかりませんでした。

A concurrent_unordered_map supports concurrent insertion and traversal, but not concurrent erasure. The interface has no visible locking. It may hold locks internally, but never while calling user-defined code. It has semantics similar to the C++11 std::unordered_map except as follows:

これは実際にはどういう意味ですか？単一のスレッドから消去する限り、このマップから消去しても安全ですか? そうでない場合、どうすればこれを行うことができますか?

4

1 に答える 1

5

並行マップの標準化の提案は、なぜ並行コンテナーに がないのかを説明していますerase。(「同時消去がサポートされない理由」セクションを検索してください。)

C++ 標準ライブラリのコンテナーは、その内容の削除を担当します。要素が配列の「中に」あるように、内容はコンテナの「中に」あります。 operator[]含まれているオブジェクトへの参照を返し、参照が返されると、コンテナーは、要求元のスレッドがその参照に「ハングアップ」する期間を認識しません。そのため、別のスレッドが要素の消去を要求した場合、コンテナは要素を安全に削除できるかどうかを判断できません。

この制限を回避する方法をいくつか考えてみましたが、消去の問題について説明すると、さらに大きな問題が生じます。マップに格納されている要素への同時アクセスを保護することは、常に呼び出し側の責任です。

int例: からへの並行マップがfloatあり、これを行うとします。

thread A                   thread B
the_map[99] = 0.0;
                   ...
the_map[99] = 1.0;         if (the_map[99] == 1.0) ...  // data race!!!

これがデータ競合である理由は、式the_map[99]が保護されていても、アクセスが保護されていない参照を返すためです。参照へのアクセスは保護されていないため、参照が指すメモリへの読み取りのみが許可されます。(または、そのメモリへのすべてのアクセスをロックする必要があります)。

これが私が考えることができる最も安価な代替手段です（そしてそれは本当に高価です）：

typedef concurrent_unordered_map<MyKey_t, atomic<MyMapped_t*> > MyContainer_t;

アイテムを検索するとは、次のことを意味します。

MyMapped_t* x = the_map[a_key].load();

アイテムの挿入は次のとおりです。

the_map[a_key].store(ptr_to_new_value);

アイテムの消去とは:

the_map[a_key].store(0);

アイテムが実際にマップ内にあるかどうかをテストするのは次のとおりです。

if (the_map[a_key].load() != 0) ...

最後に、何らかの条件付き消去 (または変更) を行う場合は、次のものよりも複雑にする必要があります。

MyMapped_t* x;
do {
  x = the_map[a_key].load();
} while (condition_for_erasing(x) && !the_map[a_key].compare_exchange_strong(x, 0));

(上記はABA 問題に悩まされているため誤りです。)

それでも、これは基本的なものへの同時変更からあなたを保護するものではなく、MyMapped_tのすべての構築、ストレージ管理、および破壊をMyMapped_t自分で行う必要があります。

:(
于 2013-05-25T15:28:07.263 に答える