Почему операцию чтения ConcurrentHashMap не нужно блокировать?

Java

Мы знаем, что ConcurrentHashmap (1.8), среда параллельного сбора данных, является потокобезопасной. Когда вы увидите операцию получения исходного кода, вы обнаружите, что во всем процессе операции получения нет блокировки. вопрос, обсуждаемый в этом сообщении в блоге - почему его не нужно блокировать?

Введение в ConcurrentHashMap

Я думаю, базовые студенты знают, что в jdk1.7 для реализации используется Segment + HashEntry + ReentrantLock, а в 1.8 заброшен раздутый дизайн Segment, и вместо него используется Node + CAS + Synchronized для обеспечения параллельной безопасности для реализации. . . .

  • Реализация JDK1.8 снижает степень детализации блокировок.Дробность блокировок JDK1.7 основана на сегменте, включая несколько HashEntry, а степень детализации блокировки JDK1.8 — на HashEntry (первый узел).
  • Структура данных версии JDK1.8 стала проще, что сделало работу более четкой и гладкой.Поскольку для синхронизации используется синхронизация, концепция блокировки сегмента не требуется, и структура данных сегмента не требуется.Снижена сложность реализации также увеличилось
  • JDK1.8 использует красно-черное дерево для оптимизации связанного списка.Обход длинного связанного списка является очень длительным процессом, а эффективность обхода красно-черного дерева очень высока.Вместо связанного списка с определенный порог, он формирует оптимального партнера.

получить исходный код операции

  1. Сначала вычислите хеш-значение, найдите позицию индекса таблицы и вернитесь, если первый узел соответствует
  2. Если он сталкивается с расширением, он вызывает метод find флага ForwardingNode, который расширяет узел, находит узел и возвращает значение, если он совпадает.
  3. Если ничего из вышеперечисленного не соответствует, пройдите по узлу вниз и вернитесь, если он соответствует, в противном случае верните null в конце
//会发现源码中没有一处加了锁
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode()); //计算hash
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素
        if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //hash值为负值表示正在扩容，这个时候查的是ForwardingNode的find方法来定位到nextTable来
        //eh=-1，说明该节点是一个ForwardingNode，正在迁移，此时调用ForwardingNode的find方法去nextTable里找。
        //eh=-2，说明该节点是一个TreeBin，此时调用TreeBin的find方法遍历红黑树，由于红黑树有可能正在旋转变色，所以find里会有读写锁。
        //eh>=0，说明该节点下挂的是一个链表，直接遍历该链表即可。
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode，那就往下遍历
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}скопировать код

Если get не заблокирован, как ConcurrentHashMap гарантирует, что считанные данные не являются грязными?

изменчивый дебют

Для наглядности Java предоставляет ключевое слово volatile, гарантирующеевидимость,упорядоченность.но не гарантирует атомарность.
Обычные общие переменные не могут гарантировать видимость, потому что после изменения обычных общих переменных неизвестно, когда они будут записаны в основную память.Когда другие потоки читают их, память может все еще иметь старое значение в это время, поэтому нельзя гарантировать видимость .

  • Изменение ключевого слова volatile для базовых типов может быть согласованным для последующего чтения несколькими потоками, но для ссылочных типов, таких как массивы и компоненты управления данными, гарантируется только видимость ссылки, но видимость содержимого ссылки не гарантируется. .
  • Переупорядочивание инструкций отключено.

Предыстория: Для повышения скорости обработки процессор не связывается с памятью напрямую, а сначала считывает данные из системной памяти во внутренний кэш (L1, L2 или другой) перед выполнением операции, но не знает когда она будет записана после операции в ОЗУ.

  • Если вы пишете в переменную, объявленную volatile，JVM就会向处理器发送一条指令，将这个变量所在缓存行的数据写回到系统内存。 Однако, даже если оно будет записано обратно в память, если значение, закэшированное другим процессором, все еще старое, повторно выполнить операцию вычисления будет проблематично.
  • В многопроцессорных системах для обеспечения согласованности кэшей каждого процессораРеализовать протокол когерентности кэша, когда ЦП записывает данные, если он обнаруживает, что управляемая переменная является общей переменной, он уведомляет другие ЦП о том, что строка кэша переменной недействительна, поэтому, когда другие ЦП читают переменную, если он обнаруживает, что она недействительна, он перезапустится с загрузки данных в основную память.

    подвести итог:
  • Во-первых: использование ключевого слова volatile приводит к немедленной записи измененного значения в основную память;
  • Во-вторых: если используется ключевое слово volatile, то при изменении потока 2 строка кэша переменной кэша в рабочей памяти потока 1 будет недействительной (при отражении на аппаратном уровне соответствующая строка кэша в кэше L1 или L2 ЦП будет недействительным. );
  • Третье: поскольку строка кэша переменной кэша в рабочей памяти потока 1 недействительна, когда поток 1 снова считывает значение переменной, оно переходит в основную память для чтения.

Является ли он изменчивым добавленным в массив?

    /**
     * The array of bins. Lazily initialized upon first insertion.
     * Size is always a power of two. Accessed directly by iterators.
     */
    transient volatile Node<K,V>[] table;скопировать код

Мы знаем, что volatile может изменять массив, но смысл отличается от того, как это выглядит. Например, volatile int array[10] означает, что адрес массива изменчив, а не значение элемента массива изменчиво.

Узел, украшенный volatile

Операция get может быть без блокировки, потому что элемент val и указатель next узла изменяются с помощью volatile.В многопоточной среде поток A виден потоку B, когда он изменяет val узла или добавляет новый узел. из-за конфликта хэшей.

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //可以看到这些都用了volatile修饰
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public final K getKey()       { return key; }
    public final V getValue()     { return val; }
    public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
    public final String toString(){ return key + "=" + val; }
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u; Map.Entry<?,?> e;
        return ((o instanceof Map.Entry) &&
                (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                (v = e.getValue()) != null &&
                (k == key || k.equals(key)) &&
                (v == (u = val) || v.equals(u)));
    }

    /**
     * Virtualized support for map.get(); overridden in subclasses.
     */
    Node<K,V> find(int h, Object k) {
        Node<K,V> e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}скопировать код

Поскольку измененный массив volatile не влияет на операцию получения, какова цель добавления volatile в массив?

Фактически, volatile добавляется, чтобы сделать массив Node видимым для других потоков при расширении его емкости.

Суммировать

  • В версии 1.8 операцию получения ConcurrentHashMap не нужно блокировать во всем процессе, что является одной из причин ее более высокой безопасности и эффективности по сравнению с другими параллельными коллекциями, такими как хэш-таблица и хэш-карта, обернутыми с помощью Collections.synchronizedMap().
  • Всю операцию получения не нужно блокировать, потому что элемент val узла модифицируется с помощью volatile и не имеет ничего общего с массивом с модификацией volatile.
  • Массивы модифицируются с помощью volatile в основном для обеспечения видимости при расширении массива.
Категории