7

リンクされたノードで構成されるデータ構造があります。これは単純な LinkedList と考えることができます。リストの各ノードは、何らかの値と、他のノードを指す次のフィールド、または最後のノードの場合は null で構成されます。最初のノードはルートとして機能し、値はなく、次のノードを指すだけです。他のすべてのノードは実質的に不変であり、特定の状況に関連して構造体が破棄されない限り、一度作成されると値も次のフィールドも存続期間中に変更されません。

1 つ (1 つだけ) のスレッドが新しいノードをリストの先頭に追加します。これは、新しいオブジェクトを構築し、そのフィールドを設定し、次のフィールドをルートが指すオブジェクトに設定し、ルートの次のフィールドをこの新しいノードに設定することによって実現されます。

他のノードは、読み取りのみを実行して構造をブラウズします。ルート ノードへの参照があり、探しているものが見つかるか、リストの最後に到達するまで、他のノードを通過します。

私の質問は、次のフィールドを揮発性にするだけで十分ですか? 私の Java メモリ モデルの理解から、新しいノードを追加するときにメイン スレッド (新しいノードを追加するスレッド) が揮発性書き込みを実行する場合、すべてが正常に同期され、不整合は発生しません。

また、x86 アーキテクチャで揮発性変数の読み取りがパフォーマンスの低下を引き起こさないと仮定するのは正しいですか? 他のスレッドは次のフィールドを読み取る構造体を頻繁にブラウズするため、これがメモリバリアなどなしに自由に実行できることが重要です。

また、もうひとつ気になることがあります。構造をブラウズするスレッドは、いくつかの追加ノードも保持します。これらのノードは完全にスレッド ローカルであり、ノードを作成したスレッドのみが使用し、まったく共有されません。これらの追加ノードでは、次のフィールドが揮発性である必要はありません。さらに、volatile next フィールドを設定すると、望ましくないパフォーマンスの低下を引き起こすメモリ バリアが発生します。これを回避する方法はあるのだろうか。理想的には、次のフィールドが揮発性フィールドとして機能する場合と、通常のフィールドとして機能する場合があります;) または、完全に制御でき、必要なときにいつでも自分でメモリバリアを発行できれば完璧です。

編集：

また、これらすべての書き込みを別の揮発性変数に何らかの方法で同期することは可能でしょうか? たとえば、他の完全に無関係な静的変数はありますか? 揮発性書き込みは保留中のすべての書き込みをフラッシュするため、更新スレッドがすべての作業を行った後に、次のフィールドが揮発性ではなく、代わりに別の揮発性変数が書き込まれる可能性はありませんか?

リレーションの前に発生することはなく、以前の書き込みが並べ替えられる可能性があるため、私にはあまり安全ではないようです。次のフィールドの割り当ては、値フィールドの割り当てで再順序付けされる可能性があり、反復スレッドが一貫性​​のないオブジェクトの状態を観察することにつながります。

しかし、そのような安全なスキームを考え出すことは可能でしょうか? これはどう：

更新スレッドは、最初に新しいオブジェクトを構築し、その値フィールドを初期化し、その次のフィールドをルート ノードが指すノードに設定し、いくつかの静的変数で揮発性書き込みを実行し、ルート ノードの次のフィールドを新しく作成されたノードに設定します。

4

3 に答える 3

8

1.

ここでの発言に基づいて

新しいオブジェクトを構築し、そのフィールドを設定し、次のフィールドをルートが指すオブジェクトに設定してから、ルートの次のフィールドをこの新しいノードに設定します。

次に、はい、次のフィールドを volatile に設定すると、正しく同期されます。その理由を理解することが重要です。ノードオブジェクトへの書き込み、フィールドへの書き込み、次のノードへの書き込みの 3 つのセットがあります (なぜそうしているのか完全にはわかりませんが、何かを理解していない可能性があります)。

つまり、2 + (N 個のフィールド) の書き込みです。この時点では、事前発生の関係はなく、ノードが正常に作成された場合、保証はありません。volatile フィールドに書き込むとすぐに、以前のすべての書き込みも表示されるようになります。

2.

x86 (または任意のキャッシュ コヒーレント) オペレーティング システムでの揮発性読み取り/書き込みには、次の属性があります。

 volatile-read: very close to a normal read
 volatile-write: about 1/3 the time of a synchronization write 
         (whether within intrinsic locking or  j.u.c.Lock locking)

3.

VolatileNode と Node を作成する必要があるようです。Java 7 がFences API を提供するという提案がありました。これは、静的ユーティリティ クラスで実行する読み取り/書き込みのスタイルを指定できますが、そのリリースのようには見えません。

編集：

Thkala は、含める価値があると私が感じる素晴らしい点を指摘しました

ただし、JSR133 より前の JVM (つまり Java < 5.0) には同じセマンティクスがなかったことに注意してください。

したがって、私が書いたことは、Java 1.4 以下で実行されるアプリケーションには当てはまりません。

于 2011-06-29T17:17:49.397 に答える
2

ルート ノードは実際にはノードである必要はありません。最初の「実際の」ノードへの参照のみが必要です。 

public class LinkedList {
  private volatile Node firstNode;
  ...
  addNode(Node node) {
    node.next = firstNode;
    firstNode = node;
  }
}

nextそのため、すべてのノードでフィールドを揮発性にする必要はありません。ノードはまったく同期されていません。最初のノードへの揮発性アクセスのコストを気にしない場合は、非同期リンク リストにそのクラスを使用できます。firstNodeまたは、代わりに、非同期バージョンの不揮発性を使用してクラスを単純に書き直すこともできます。

于 2011-06-29T23:14:13.353 に答える
2

nextフィールドを作成すると、ルート ノードだけでなく、ノード クラスのすべてのvolatileインスタンスにメモリ バリアが課されます。ルートノードで使用するよりも高価になると思います。さらに、JVM はメソッド呼び出しをはるかに最適化できる可能性があります。これとこれも参照してください。synchronizedsynchronized

とはいえ、何が起こるかを確認するには、おそらく と ベンチマーク/プロファイル の両方を試す必要があります。

于 2011-06-29T17:12:00.867 に答える