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 个附加字段。设置器中的局部变量是可以的。

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

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

4

6 回答 6

2

Google Guava does this for you: BiMap.

For example:

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 can be any object you would want to synchronize on.

于 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

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

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

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

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

试试这个，在不写的情况下允许阅读。

可重入读写锁

于 2011-02-21T18:55:46.263 回答
0

另一种选择是简单地使other引用易变。这将满足您的要求和您的优点。

于 2011-02-21T19:04:05.823 回答