Threadsafe двунаправленная ассоциация в 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().getOther() == foo завершится неудачно, когда другой поток выполняет setOther одновременно.
• Последовательное поведение. Если поток выполняет setOther и никакой другой поток не переопределяет значение, getOther немедленно возвращает новое значение для этого потока.
• Нет возврата во времени. Как только поток наблюдалсяновое значение с getOther, оно никогда больше не получит старое значение (если оно не будет установлено снова).

Также приятно иметь:

• Низкая конкуренция,особенно отсутствие глобальной блокировки. Решение должно хорошо масштабироваться.
• Как можно меньше накладных расходов на синхронизацию. Оно должно иметь разумную производительность для одного потока.
• Недостаток памятиrhead.Когда объект имеет 5 ассоциаций, я не хочу 3 дополнительных поля для каждой ассоциации.Локальные переменные в установщиках в порядке.

В моем приложении будет 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 может быть любым объектом, который выхотел бы synchronize вкл.

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

Оказывается, это действительно сложная проблема! (Хорошо!) Использование глобальной блокировки было бы слишком просто и, вероятно, слишком медленно. Я думаю, что у меня есть версия без блокировки, о которой я расскажу ниже, но я бы не поверил, что она идеальна. Трудно рассуждать о всех возможных чередованиях.

Как оказалось, это идеальный вариант использования для транзакционной памяти ! Просто пометьте весь блок как атомарный и измените все, что хотите Вы могли бы посмотреть на Двойка 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);
    }
}

Ключевые моменты:

• Если нет одновременного доступа к любому из затронутых Foos (не более 4), установщик делает один проход через цикл, изменяя соответствующие указатели.
• При наличии одновременных сеттеров некоторые из сеттеров могут выйти из строя и повторить попытку.
• Если несколько потоков одновременно пытаются разорвать отношения, только один поток преуспеет в выполнении x.oRef.compareAndSet(y, null).
• Если f.oRef.compareAndSet(null, f) завершится успешно, никакой другой поток не сможет разорвать наполовину установленную связь в break(). Затем, если oRef.compareAndSet(null, f) успешно, операция завершена. Если это не удается, f.oRef может быть сброшено, и все повторяют попытки.

Answer 4

Я могу представить себе статический элемент для работы в качестве монитора.но, возможно, это то, что вы считаете «глобальной» блокировкой.

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 5

Другой альтернативой является просто сделать ссылку other энергозависимой.Это будет соответствовать вашим требованиям и вашим интересам.

Answer 6

Попробуйте, разрешите чтение, пока запись не выполнена.

ReentrantReadWriteLock