Можно ли в этом случае зайти в тупик с ConcurrentHashMap?

Я читаю исходный код ConcurrentHashMap в JDK8, обратите внимание, что TreeBin использует блокировку «чтение-запись» для предотвращения одновременного чтения и записи.

Потоки чтения будут проходить через TreeNodes, если нет параллельного потока записи, пытающегося изменить древовидную структуру. Когда операция «найти» выполнена, поток чтения может:

(1) «CAS» lockState и «разпарковать» поток ожидания (писателя), если он существует.

Ниже приведен метод find() в исходном коде.

final Node<K,V> find(int h, Object k) {
            if (k != null) {
                for (Node<K,V> e = first; e != null; ) {
                    int s; K ek;
                    if (((s = lockState) & (WAITER|WRITER)) != 0) {
                        if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                        e = e.next;
                    }
                    else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                                 s + READER)) {
                        TreeNode<K,V> r, p;
                        try {
                            p = ((r = root) == null ? null :
                                 r.findTreeNode(h, k, null));
                        } finally {
                            Thread w;
                            // (1)if no more readers, try to unpark the waiter if it exists
                            if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                                (READER|WAITER) && (w = waiter) != null)
                                LockSupport.unpark(w);
                        }
                        return p;
                    }
                }
            }
            return null;
        }

с другой стороны, поток записи может:

  • (2) добавление состояния WAITER к lockState с помощью операции «CAS».

  • (3) установить для себя переменную waiter.

  • (4) сам «парк».

вот код писателя:

        private final void contendedLock() {
            boolean waiting = false;
            for (int s;;) {
                if (((s = lockState) & ~WAITER) == 0) {
                    if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                        if (waiting)
                            waiter = null;
                        return;
                    }
                }
                else if ((s & WAITER) == 0) {
                    if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                        waiting = true;
                        waiter = Thread.currentThread();
                    }
                }
                else if (waiting)
                    LockSupport.park(this);
            }
        }

ВОТ МОЯ КОНСУЛЬТАЦИЯ:

Если четыре описанные выше операции выполняются в следующем порядке (2) (1) (3) (4), операция (1) ничего не распаркует, потому что в этот момент 'waiter' был нулевым.

Тогда официант припаркуется навсегда, и никто не сможет его распарковать.

Все последующие записи будут заблокированы внутренней блокировкой, удерживаемой «припаркованным» потоком.

ЭТО ВОЗМОЖНОСТЬ ТУПИКА?

Я действительно смущен этим. Я думаю, возможно, я что-то пропустил в исходном коде. Нужна ваша помощь, если вы знакомы с ним.


person Kyne Xiao    schedule 23.03.2019    source источник
comment
Кроме того, может кто-нибудь объяснить мне эту строку в find: if (((s = lockState) & (WAITER|WRITER)) != 0)? Почему здесь и в его блоке нет синхронизации?   -  person    schedule 23.03.2019
comment
@dyukha Это означает, что если здесь есть официант или писатель, просто пройдитесь по дереву по «следующим» ссылкам (например, связанный список). Потому что каждый раз, когда вы добавляете узел в связанный список, вы фактически добавляете его в «первое» положение, что не мешает вашим потокам чтения проходить через другие узлы в списке. Так что замки здесь не нужны   -  person Kyne Xiao    schedule 23.03.2019


Ответы (1)


Вопросу больше года. Но это такая милая головоломка. Вот ответ:

После (2) (1) (3) выполнение в contendedLock() продолжается следующим образом:

if (((s = lockState) & ~WAITER) == 0) является верным, потому что (1) было выполнено

if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) также верно, потому что (3) было выполнено до (s = lockState), а не после него

Поскольку waiting было установлено в true перед выполнением (3), третий оператор if также имеет значение true. Поэтому waiter устанавливается равным нулю, и мы выходим из цикла. (4) никогда не выполняется.

Подводя итог: после (2) (1) (3) операция (4) никогда не будет выполнена. Таким образом, нет никаких шансов на взаимоблокировку, и мы все можем без колебаний продолжать использовать ConcurrentHashMap ;-)

person rmunge    schedule 28.05.2020