3

スレッドセーフな双方向の関連付けを実装する良い方法は何ですか? おそらく良いライブラリまたはコードジェネレーターはありますか?

非スレッドセーフな例を次に示します。

class Foo {

    private Foo other;

    public Foo getOther() {
        return other;
    }

    public void setOther(Foo other) {
        this.setOtherSecretly(other);
        other.setotherSecretly(this);
    }

    void setOtherSecretly(Foo other) {
        if (this.other != null) this.other.other = null;
        this.other = other;
    }
}

スレッドセーフに対する私の要件は次のとおりです。

  • デッドロックなし
  • 結果整合性 (すべてのスレッドがオブジェクトの変更を停止すると、最終的に整合性のある状態に到達します。つまりassert foo.getOther().getOther() == foo、別のスレッドがsetOther同時に実行されている場合に失敗することは許容されます。
  • 順次動作。スレッドが実行setOtherされ、他のスレッドが値をオーバーライドしない場合、getOtherそのスレッドの新しい値をすぐに返します。
  • 時間を遡ることはありません。スレッドが で新しい値を確認するとgetOther、(再度設定されない限り) 古い値を受け取ることはありません。

また、持っているといいです：

  • 競合が少なく、特にグローバル ロックがない。ソリューションは適切にスケーリングする必要があります。
  • 同期のオーバーヘッドをできるだけ少なくします。単一のスレッドに対して妥当なパフォーマンスが得られるはずです。
  • 低メモリ オーバーヘッド。オブジェクトに 5 つの関連付けがある場合、関連付けごとに 3 つのフィールドを追加したくありません。セッターのローカル変数は問題ありません。

私のアプリケーションには、いくつかのクラスの約 5,000 個のオブジェクトで動作する 16 のスレッドがあります。

私はまだ解決策を思いつくことができませんでした (いいえ、これは宿題ではありません)。

4

6 に答える 6

2

Google Guavaがこれを行います: BiMap。

例えば：

BiMap<Integer, String> bimap = Synchronized.biMap(HashBiMap.create(), someMutexObject);
bimap.put(1, "one");
bimap.put(2, "two");

bimap.get(1); // returns "one"
bimap.inverse().get("one") // returns 1

someMutexObjectあなたがしたい任意のオブジェクトにすることができますsynchronize。

于 2011-02-21T19:15:52.390 に答える
1

各オブジェクトをそれぞれのロックに関連付けてから、両方のロックを取得しながら他方を設定できます。例えば。デッドロックを回避するには、ロック順序を使用できます

class Foo extends ReentrantLock {

    private static final AtomicInteger order = new AtomicInteger(0);

    final int id = order.incrementAndGet();

    private Foo other;

    public Foo getOther() {
        return other;
    }

    public void setOther(Foo other) {
        if (id > other.id) {
            other.lock();
            try {
                this.lock();
                try {

                    // assign here
                } finally {
                    this.unlock();
                }
            } finally {
                other.unlock();
            }
        } else if (id < other.id) {
            this.lock();
            try {
                other.lock();
                try {

                    // assign here
                } finally {
                    other.unlock();
                }
            } finally {
                this.unlock();
            }
        }
    }
}
于 2011-02-21T18:59:00.277 に答える
0

これは非常に難しい問題であることがわかりました。(いいですね!) グローバル ロックを使用するのは簡単すぎて、おそらく遅すぎます。私はロックのないバージョンを持っていると思います--これについては以下で説明します--しかし、それが完璧であるとはあまり信じていません. 考えられるすべてのインターリーブについて推論するのは困難です。

結局のところ、これはトランザクショナル メモリの完璧なユース ケースです。ブロック全体をアトミックとしてマークし、必要に応じて変更するだけです! Deuce STMを見るかもしれませんが、どれだけ速いかはわかりません。最高のシステムだけがカスタム ハードウェアを必要としないとしたら...

とにかく、この問題をしばらく考えた後、Java のAtomicReferenceを使用してロックをバイパスするバージョンを思いついたと思います。まず、コード：

class Foo {

    private AtomicReference<Foo> oRef = new AtomicReference<Foo>;

    private static final AtomicInteger order = new AtomicInteger(0);
    private final int id = order.incrementAndGet();

    private static bool break(Foo x, Foo y) {
        if (x.id > y.id)
            return break(y, x);

        return x.oRef.compareAndSet(y, null) &&
               y.oRef.compareAndSet(x, null);
    }

    public void setOther(Foo f) {
        if (f != null && f.id > id) {
            f.setOther(this);
            return;
        }
        do {
            Foo other = oRef.get();
            if (other == f)
                break;

            if (other != null && !break(this, other))
                continue;

            if (f == null)
                break;

            Foo fother = f.oRef.get();
            if (fother != null && !break(f, fother))
                continue;

            if (!f.oRef.compareAndSet(null, this))
                continue;
            if (!oRef.compareAndSet(null, f)) {
                f.oRef.set(null);
                continue;
            }
        } while (false);
    }
}

キーポイント：

  • 影響を受ける Foo (最大 4 つ) への同時アクセスがない場合、setter は関連するポインターを変更するループを 1 回通過させます。
  • 並行セッターが存在する場合、一部のセッターが失敗して再試行する可能性があります。
  • 複数のスレッドが同時に関係を壊そうとした場合、実行に成功するのは 1 つのスレッドだけx.oRef.compareAndSet(y, null)です。
  • がf.oRef.compareAndSet(null, f)成功すると、他のスレッドは で半分確立された関係を破ることができなくなりますbreak()。その後、oRef.compareAndSet(null, f)成功した場合、操作は完了です。失敗した場合は、f.oRefリセットして全員が再試行できます。
于 2011-02-22T06:57:15.653 に答える
0

これを試してみてください。書き込みが行われていないときに読み取りが可能になります。

ReentrantReadWriteLock

于 2011-02-21T18:55:46.263 に答える
0

モニターとして機能する静的メンバーを考えることができます。しかし、おそらくこれは「グローバル」ロックと見なされるものです。

class Foo {

    private static final Object MONITOR = new Object();
    private Foo other;

    public Foo getOther() {
        synchronized(MONITOR){
            return other;
        }
    }

    public void setOther(Foo other) {
        synchronized(MONITOR){
            this.setOtherSecretly(other);
            other.setotherSecretly(this);
        }
    }

    void setOtherSecretly(Foo other) {
        if (this.other != null) this.other.other = null;
        this.other = other;
    }
}
于 2011-02-21T19:11:24.810 に答える
0

もう 1 つの方法は、単純にother参照を揮発性にすることです。それはあなたの要件とあなたの素敵なものを満たします.

于 2011-02-21T19:04:05.823 に答える