Java中线程安全的双向关联

Question

实现线程安全双向关联的好方法是什么？是否有一个好的库或代码生成器？

这是一个非线程安全的例子：

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当另一个线程同时执行 setOther 时，
• 如果一个线程执行 setOther 并且没有其他线程覆盖，则 立即返回该线程的新值。
• ().getOther() == foo 失败。一旦线程使用 getOther 观察到新值，getOther 就会 值（除非再次设置）。

还有一个好处：

• 低争用，尤其是没有全局锁时，它
• 具有尽可能小的同步开销。
• 应该 一个对象有 5 个关联，我不希望每个关联有 3 个附加字段。 setter 中的局部变量是可以的。

我的应用程序将有 16 个线程处理多个类的大约 5000 个对象。

我还无法想出解决方案（不，这不是家庭作业），所以欢迎任何输入（想法、文章、代码）。

Answer 1

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 可以是您想要同步的任何对象。

Answer 2

您可以将每个对象关联到它们自己的锁，然后在获取两个锁时设置另一个对象。例如。为了避免死锁，您可以使用锁排序

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();
            }
        }
    }
}

Answer 3

试试这个，将允许在不进行写入的情况下进行读取。

可重入ReadWriteLock

Answer 4

另一种选择是简单地使other引用变得易失。这将满足您的要求和您的必备品。

Answer 5

我可以想到一个静态成员来充当监视器。但也许这就是您所认为的“全局”锁。

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;
    }
}

Answer 6

事实证明这是一个非常困难的问题！ （很好！）使用全局锁太容易了，而且可能太慢。我想我有一个无锁版本——我将在下面介绍——但我不会太相信它是完美的。很难推理出所有可能的交错。

事实证明，这是事务内存的完美用例！只需将整个块标记为原子并修改您想要的任何内容！您可以查看 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 会通过循环修改相关指针。
• 在存在并发 setter 的情况下，某些 setter 可能会失败并重试。
• 如果多个线程尝试同时中断关系，则只有一个线程会成功执行 x.oRef.compareAndSet(y, null)。
• 如果f.oRef.compareAndSet(null, f)成功，则没有其他线程能够打破break()中的半建立关系。然后，如果oRef.compareAndSet(null, f)成功，则操作完成。如果失败，f.oRef 可以重置，每个人都可以重试。