7

アトミック操作を行うためにアドレスから 2 つの MSB を盗むにはどうすればよいですか? 私は単一の単語CASをやろうとしています

例

public class Node
{
    long key;
    long value;
    Node lchild; // format is flag1,flag2,address
    Node rchild; // format is flag1,flag2,address
}

public void createNode()
{
    Node n1 = new Node(); //this should create a node with format 0,0,address1
}

public void setFlag1(Node n1)
{
    Now the new address should be in format 1,0,address1
}

public void setFlag2(Node n1)
{
    Now the new address should be in format 0,1,address1
}

AtomicReference追加のフラグが 1 つだけ必要な場合に使用できます。 AtomicStampedReferenceを使用できますが、timeStamp と参照を含む余分なボックスが作成されるため、効率的ではありません。

C での同様の問題は 、ポインターからビットを盗むで説明されています。

4

6 に答える 6

4

おそらく、sun.misc.Unsafe を使用してこれを実装できます。

とりわけ、これには、compareAndSwap任意のオブジェクト内の任意のバイナリ データを処理できる多数のメソッドがあります。

そうは言っても、バイナリ検索ツリーを実装している場合は、不変の永続的なデータ構造を見ることをお勧めします。これらの利点は次のとおりです。

  • それらは不変性のため、定義上スレッドセーフです
  • ロックは必要ありません
  • 構造共有を行う機能は、より複雑なこと (サブツリーのスナップショットなど) を開始すると、パフォーマンスが大幅に向上します。基本的に、防御的なコピーを作成する必要がなくなります。
于 2014-01-31T23:32:41.080 に答える
3

これは、この種の操作をサポートし、フラグ ビットを適切に処理する独自の JVM を実装しないと不可能です (GC を実行する場合など) (この時点ですべての参照を識別する必要があり、コレクターを移動する場合はそれらを変更する必要があります)。それでも、これは明示的な逆参照やポインター演算を含まない Java の設計原則に反しています (参照内のビットの変更をカウントし、逆参照のためにそれらをマスクします)。

代わりに、フラグとノードの新しい複合エッジ タイプを作成することをお勧めします。

public class Node {
    long key;
    long value;
    Child lchild; // child = node reference + flags
    Child rchild;
}

// this is the edge type which should also be used to reference the root node with flags
public class Child {
    Node child;
    BitSet flags;

    public Child(Node node) {
        this.child = node;
        this.flags = new BitSet(2); // we initialize the flags with 00
    }
    public void setFlag(int index) {
        this.flags.set(index); // index would be 0 or 1 here for the two flags
    }
    public boolean isFlagSet(int index) {
        return this.flags.get(index); // index would be 0 or 1 here for the two flags
    }
}
于 2014-02-07T08:46:19.213 に答える
1

Maurice Herlihy と Nir ​​Shavit による本「The art of multiprocessor programming」p.215 からの抜粋のコピー:

プラグマ 9.8.1 で詳しく説明されているように、AtomicMarkableReference オブジェクトは、タイプ T のオブジェクトへの参照とブール マークの両方をカプセル化します。これらのフィールドは、まとめてまたは個別にアトミックに更新できます。各ノードの次のフィールドを AtomicMarkableReference にします。スレッド A は、ノードの次のフィールドにマーク ビットを設定することによって currA を論理的に削除し、add() または remove() を実行する他のスレッドと物理的な削除を共有します。 compareAndSet()) で検出されたすべてのマークされたノード。つまり、 add() および remove() を実行するスレッドは、マークされたノードをトラバースせず、続行する前にそれらを削除します。contains() メソッドは、LazyList アルゴリズムと同じままで、マークされているかどうかに関係なく、すべてのノードをトラバースします。

于 2014-02-07T21:26:31.230 に答える
0

オブジェクト参照変数に使用できるものからビットを取り出すには、独自の JVM を作成する必要があります。

最初に、ビットが実際には使用されていないことを確認する必要があります (たとえば、JVM がオブジェクトを常に 16 バイト境界に揃える場合に参照の下位ビットを取得するなど)。ただし、一部の JVM は 32 ビット参照のすべてのビットを使用します。

次に、関連付けられたオブジェクトにアクセスする前に、参照が読み込まれるたびにコードを挿入して、これらのビットをクリアする必要があります。

次に、ガベージ コレクターに対しても同じことを行う必要があります。

于 2014-02-07T22:55:10.037 に答える
-1

参照からビットを盗むことは許可されていませんが、それを回避する方法があります。AtomicStampedReference を使用すると、参照と整数の両方をアトミックに更新するための比較と交換を行うことができます。整数をステータスとして使用するか、必要に応じて整数の MSB からビットを盗むことができます。Java で整数に対してビット操作を実行できます。これは非常に優れています。

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

AtomicStampedReference の整数から 2 ビットを盗んでステータス ビットとして使用し、残りの 30 ビットの整数をカウンターとして使用して ABA 問題を回避する Java プログラムを作成しました。

于 2015-11-19T22:48:57.270 に答える