BT

InfoQ ホームページ ニュース 並行コレクションの列挙

並行コレクションの列挙

ブックマーク

Parallel Extensions for .NETには、スタックとキューの並行コレクションが2つ入っている。他のコレクションクラスは開発中だが、セマンティクスについてはなかなか解決できない問題がある。とりわけ、1つのスレッドがコレクションを列挙しているときに、別のスレッドがそのコレクションを修正すると、どうなるのだろうか。

シングルスレッドのクラスの場合はどうなるかというと、よく知られているとおり、列挙子が例外処理を実行する。しかし、標準であるはずの並行クラスでは、数種類のオプションが存在する。

オプションの1つは、列挙開始時のありのままのデータをスナップショットを作成することだろう。繰り返しの間、大量のメモリを必要とするが、ひとたび作成がすむと、このスナップショットはロックされない。これがパフォーマンスにどのような影響をもたらすかについては、予測が難しい。 

スナップショットが作成されない場合、コレクションが開発者に提示する可能性のある保証セットがある。そのうちの多数が矛盾しているが、状況によってはすべて適切になる。

  • 削除済みアイテムは常に見える
  • 削除済みアイテムが見えることはない
  • コレクションの末尾にアイテムが追加されると、追加されたアイテムは常に見える
  • アイテムが追加されれば、追加場所がどこでも、常に見える
  • 追加されたアイテムが見えることはない
  • 移動されたアイテムが2度見えることはない
  • アイテムがコレクションの末尾に移動されると、アイテムは2度見える
  • 移動されたアイテムは、その移動先がコレクションの先頭であっても、常に見える
  • コレクションの元々の長さをNとした場合、N個を超えるアイテムが見えることはない

オプションの幅が広いので、Stephen ToubがParallel Extensionsについてフィードバックを求めている(リンク)

  1. .NETに存在する標準的な配列のコレクションを前提として、スレッドセーフのバージョンがあるとした場合、他のスレッドがコレクションを修正中に、同一コレクションを並行列挙できることから何らかの恩恵を受けるシナリオはありますか。すでにわかっているシナリオもありますが、さらに情報を集めたいと思っています。
  2. 1番のシナリオがあると想定して、列挙子で返されたデータが有用になるために必要となるであろう、最小限の保証は何ですか。たとえば、スレッドセーフのディクショナリについて、並行修正(追加/更新/削除)がないなら、ディクショナリにあるとおりのものが列挙で手に入り、並行アクセスがある場合は、ディクショナリになかったものは決して手に入らず、並行追加や並行更新は見えない可能性があり、並行削除されたアイテムはまだ残っていて目にする可能性があります。
  3. 並行修正にもかかわらず、スレッドセーフなコレクションの列挙をサポートしたなら、「修正へのスロー」動作へ戻す機能がそもそも必要でしょうか。
  4. 最後になりますが、スレッドセーフでスケーラブルなコレクションと対を成すコレクションとしたいものの中で、最も重要なコレクションにあたるものは何ですか。

Omer van Kloetenが直列化についてすばらしい質問をしている。

役立つ追加となるのは、バックアップ時にメモリから固定記憶域にそのキャッシュを非同期にダンプする機能で、そのダンプには安全な列挙が必要となるでしょう。(実際この件について考えてみると、 -- 直列化もスレッドセーフなのでしょうか。直列化では、デフォルト動作はどうなるのでしょうか。) 

Rick Brewsterは、機能的なプログラミング概念に方向転換するよう提案している。外部からコレクションをロックするのではなく、コレクションに対する全オペレーションの実行は「Lock(アクション)」メソッドにデレゲートを渡すことによって執り行う。

「Lock」メソッドがロックがけ/ロック解除型のコンストラクトを使って自動的にコールバックを取り囲むというアイデアです。こうすれば、そのクラスが現在呈している原子動作に限定されることもありません。実際、おそらくはLock()がアクションを取る代わりに、Funcを取り、ConcurrentListクラス自体には実のところ、get、set、enumerateするメソッドがまったくないのです。このようにして、ロックされた範囲内でそのクラスにアクセスできるだけです。

原文はこちらです:http://www.infoq.com/news/2008/08/Parallel-Enumerators

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

BT

あなたのプロファイルは最新ですか?プロフィールを確認してアップデートしてください。

Eメールを変更すると確認のメールが配信されます。

会社名:
役職:
組織規模:
国:
都道府県:
新しいメールアドレスに確認用のメールを送信します。このポップアップ画面は自動的に閉じられます。