Язык программирования Java Java Collections Framework версии 1.5 и более поздних версий определяет и реализует исходные обычные однопоточные карты, а также новые потокобезопасные Карты, реализующие интерфейс java.util.concurrent.ConcurrentMap среди других параллельных интерфейсов. В Java 1.6 был добавлен интерфейс java.util.NavigableMap , расширяющий java.util.SortedMap , а интерфейс java.util.concurrent.ConcurrentNavigableMap был добавлен как комбинация подинтерфейсов.
Содержание
- 1 Интерфейсы Java Map
- 2 Реализации
- 2.1 ConcurrentHashMap
- 2.2 ConcurrentSkipListMap
- 2.3 Ctrie
- 3 Проблема одновременного изменения
- 3.1 Счетчики изменений
- 3.2 Коллекции. synchronizedMap ()
- 3.3 Собственная синхронизация
- 3.4 ReentrantReadWriteLock
- 4 Convoys
- 5 Несколько ядер
- 6 Predictable Latency
- 7 Слабая согласованность
- 8 Методы ConcurrentMap 1.5
- 9 ConcurrentMap 1.8 Методы
- 10 Атомарность без блокировок
- 11 История
- 12 См. Также
- 13 Ссылки
- 14 Внешние ссылки
Интерфейсы Java Map
Схема интерфейса карты версии 1.8 имеет фигура ниже. Наборы можно рассматривать как подварианты соответствующих карт, в которых значения всегда являются определенной константой, которую можно игнорировать, хотя API набора использует соответствующие методы с разными именами. Внизу находится java.util.concurrent.ConcurrentNavigableMap, который представляет собой множественное наследование.
Реализации
ConcurrentHashMap
Для неупорядоченного доступа, как определено в интерфейсе java.util.Map, java.util.concurrent. ConcurrentHashMap реализует java.util.concurrent.ConcurrentMap. Этот механизм представляет собой хеш-доступ к хеш-таблице со списками записей, каждая из которых содержит ключ, значение, хеш-код и следующую ссылку. До Java 8 было несколько блокировок, каждый из которых сериализовал доступ к «сегменту» таблицы. В Java 8 встроенная синхронизация используется в заголовках самих списков, и списки могут видоизменяться в небольшие деревья, когда они угрожают стать слишком большими из-за неудачных коллизий хешей. Кроме того, Java 8 оптимистично использует примитив сравнения и установки для размещения начальных заголовков в таблице, что очень быстро. Производительность - O (n), но иногда возникают задержки, когда требуется повторное хеширование. После расширения хеш-таблица никогда не сжимается, что может привести к «утечке» памяти после удаления записей.
ConcurrentSkipListMap
Для упорядоченного доступа, определенного интерфейсом java.util.NavigableMap, java.util.concurrent.ConcurrentSkipListMap был добавлен в Java 1.6 и реализует java.util.concurrent.ConcurrentMap и также java.util.concurrent.ConcurrentNavigableMap. Это Список пропусков, в котором для построения дерева используются методы блокировки без блокировки. Производительность - O (log (n)).
Ctrie
- Ctrie Блокированное дерево на основе trie.
Проблема одновременной модификации
Одна проблема, решаемая пакетом Java 1.5 java.util.concurrent, заключается в том, что одновременной модификации. Предоставляемые им классы коллекций могут надежно использоваться несколькими потоками.
Для всех совместно используемых потоков непараллельных карт и других коллекций необходимо использовать некоторую форму явной блокировки, такую как собственная синхронизация, чтобы предотвратить одновременное изменение, или же должен быть способ доказать с помощью логики программы, что одновременное изменение не может произойти. Одновременная модификация карты несколькими потоками иногда нарушает внутреннюю согласованность структур данных внутри карты, что приводит к ошибкам, которые проявляются редко или непредсказуемо и которые трудно обнаружить и исправить. Кроме того, одновременное изменение одним потоком с доступом для чтения другим потоком или потоками иногда дает непредсказуемые результаты для читателя, хотя внутренняя согласованность карты не будет нарушена. Использование внешней программной логики для предотвращения одновременной модификации увеличивает сложность кода и создает непредсказуемый риск ошибок в существующем и будущем коде, хотя позволяет использовать непараллельные Коллекции. Однако ни блокировки, ни логика программы не могут координировать внешние потоки, которые могут контактировать с Коллекцией.
Счетчики модификаций
Чтобы помочь с проблемой одновременной модификации, не параллельные реализации Map и другие Коллекции используют внутренние счетчики модификации, с которыми консультируются до и после чтения, чтобы следить за изменениями: авторы увеличивают счетчики модификации. Предполагается, что параллельная модификация обнаруживается этим механизмом, вызывая исключение java.util.ConcurrentModificationException, но это не гарантируется во всех случаях, и на него не следует полагаться. Счетчик обслуживания также снижает производительность. По соображениям производительности счетчики не изменчивы, поэтому не гарантируется, что их изменения будут распространяться между потоками.
Collections.synchronizedMap ()
Одним из решений проблемы одновременной модификации является использование определенного класса оболочки, предоставляемого фабрикой в коллекциях: public static Map synchronizedMap (Карта m), которая обертывает существующую небезопасную карту с методами, которые синхронизируются на внутреннем мьютексе. Есть также обертки для других видов Коллекций. Это частичное решение, потому что все еще возможно, что базовая карта может быть непреднамеренно доступна для потоков, которые сохраняют или получают развернутые ссылки. Кроме того, все коллекции реализуют java.lang.Iterable , но карты с синхронизированной оболочкой и другие оболочки с оболочкой не предоставляют синхронизированные итераторы, поэтому синхронизация остается на усмотрение клиентского кода, который является медленным и подверженным ошибкам. невозможно ожидать дублирования другими потребителями синхронизированной карты. Все время итерации также должно быть защищено. Кроме того, карта, которая дважды обернута в разных местах, будет иметь разные внутренние объекты-мьютексы, с которыми работает синхронизация, что позволяет перекрывать друг друга. Делегирование снижает производительность, но современные компиляторы Just-in-Time часто сильно встраиваются, что ограничивает снижение производительности. Вот как работает упаковка внутри оболочки - мьютекс - это всего лишь последний объект, а m - последняя завернутая карта:
public V put (K key, V value) {synchronized (mutex) {return m.put (key, значение);}}Синхронизация итерации рекомендуется следующим образом, однако она синхронизируется с оболочкой, а не с внутренним мьютексом, позволяя перекрытие:
Map wrappedMap = Collections.synchronizedMap (map);... synchronized (wrappedMap) {for (String s: wrappedMap.keySet ()) {// какая-то, возможно, длинная операция выполняется, возможно, // много раз, задерживая все другие обращения}}
Собственная синхронизация
Любую карту можно безопасно использовать в многопоточной системе, гарантируя, что все обращения к ней обрабатываются механизмом синхронизации Java:
Map map = new HashMap ();... // Поток A // Использование самой карты как блокировки. Вместо этого можно использовать любой согласованный объект. синхронизированный (карта) {map.put ("ключ", "значение"); }.. // Поток B синхронизирован (карта) {String result = map.get ("key");...}... // Поток C синхронизирован (карта) {for (Entry s: map.entrySet ()) {/ * * Возможно, некоторые медленные операции, задерживающие все другие предположительно быстрые операции. * Синхронизация на отдельных итерациях невозможна. * /...}}
ReentrantReadWriteLock
Код, использующий java.util.concurrent.ReentrantReadWriteLock, похож на код для собственной синхронизации. Однако в целях безопасности блокировки должны использоваться в блоке try / finally, чтобы ранний выход, такой как выброс исключения или break / continue, обязательно прошел через разблокировку. Этот метод лучше, чем использование синхронизации, потому что чтения могут перекрывать друг друга, возникает новая проблема при принятии решения о том, как приоритизировать записи по отношению к чтениям. Для простоты вместо него можно использовать java.util.concurrent.ReentrantLock, который не делает различий между чтением и записью. Возможно больше операций с блокировками, чем с синхронизацией, например tryLock ()и tryLock (длительный тайм-аут, единица TimeUnit).
final ReentrantReadWriteLock lock = new ReentrantReadWriteLock (); окончательный ReadLock readLock = lock.readLock (); финальный WriteLock writeLock = lock.writeLock ();.. // Поток A try {writeLock.lock (); map.put («ключ», «значение»);...} наконец {writeLock.unlock (); }... // Поток B try {readLock.lock (); Строка s = map.get («ключ»);..} наконец {readLock.unlock (); } // Поток C try {readLock.lock (); for (Entry s: map.entrySet ()) {/ * * Возможно, некоторые медленные операции, задерживающие все другие предположительно быстрые операции. * Синхронизация на отдельных итерациях невозможна. * /...}} наконец {readLock.unlock (); }Convoys
Взаимное исключение имеет проблему Lock convoy, при которой потоки могут накапливаться на блокировке, в результате чего JVM необходимо поддерживать дорогостоящие очереди официантов и парковать 'ожидающие потоки. Парковать и отменять парковку потока стоит дорого, и может произойти медленное переключение контекста. Для переключения контекста требуется от микросекунд до миллисекунд, в то время как собственные базовые операции карты обычно занимают наносекунды. По мере роста конкуренции производительность может упасть до небольшой доли пропускной способности одного потока. Однако, когда конкуренция за блокировку отсутствует или незначительна, это мало влияет на производительность, за исключением проверки конкуренции блокировки. Современные JVM встраивают большую часть кода блокировки, сокращая его до нескольких инструкций, что очень быстро помогает избежать конфликтов. Однако методы повторного входа, такие как собственная синхронизация или java.util.concurrent.ReentrantReadWriteLock, имеют дополнительный багаж, снижающий производительность при поддержании глубины повторного входа, что также влияет на случай отсутствия конкуренции. Проблема Convoy, похоже, решается с помощью современных JVMS, но ее можно скрыть медленным переключением контекста: в этом случае задержка увеличится, но пропускная способность останется приемлемой. При использовании сотен потоков время переключения контекста 10 мс дает задержку в секундах.
Несколько ядер
Решения по взаимному исключению не могут использовать всю вычислительную мощность многоядерной системы, потому что только один поток разрешен внутри кода карты одновременно. Реализации конкретных параллельных карт, предоставляемые Java Collections Framework и другими, иногда используют преимущества нескольких ядер с помощью методов программирования Lock free. В методах блокировки используются такие операции, как встроенный метод compareAndSet (), доступный во многих классах Java, таких как AtomicReference, для выполнения условных обновлений некоторых внутренних структур карты атомарно. Примитив compareAndSet () дополнен в классах JCF собственным кодом, который может выполнять compareAndSet на специальных внутренних частях некоторых объектов для некоторых алгоритмов (используя «небезопасный» доступ). Методы сложны, часто полагаются на правила межпотокового взаимодействия, обеспечиваемые изменчивыми переменными, отношением «происходит до», специальными видами «циклов повтора» без блокировки (которые не похожи на спин-блокировки тем, что они всегда производят прогресс). CompareAndSet () полагается на специальные инструкции для процессора. Любой код Java может использовать для других целей метод compareAndSet () в различных параллельных классах для достижения одновременного выполнения без блокировки или даже без ожидания, что обеспечивает конечную задержку. Техники без блокировки просты во многих распространенных случаях и с некоторыми простыми коллекциями, такими как стеки.
На диаграмме показано, как синхронизация с использованием Collections.synchronizedMap (), обертывающего обычный HashMap (фиолетовый), может не масштабироваться так же хорошо, как ConcurrentHashMap (красный). Остальные - это упорядоченные ConcurrentNavigableMaps AirConcurrentMap (синий) и ConcurrentSkipListMap (зеленый CSLM). (Плоские места могут быть перехэшированы, создавая таблицы, которые больше, чем Nursery, а ConcurrentHashMap занимает больше места. Обратите внимание, что на оси Y должно быть указано «ставит K». Система - 8-ядерный i7 2,5 ГГц, с -Xms5000m для предотвращения сборки мусора). Расширение процессов GC и JVM значительно меняет кривые, а некоторые внутренние методы Lock-Free генерируют мусор при конкуренции.
Предсказуемая задержка
Еще одна проблема с подходами к взаимному исключению заключается в том, что допущение полной атомарности, сделанное некоторым однопоточным кодом, создает спорадические недопустимо длительные задержки между потоками в параллельной среде. В частности, итераторы и массовые операции, такие как putAll () и другие, могут занимать время, пропорциональное размеру карты, задерживая другие потоки, ожидающие предсказуемо низкой задержки для не массовых операций. Например, многопоточный веб-сервер не может позволить задерживать некоторые ответы из-за длительных итераций других потоков, выполняющих другие запросы, которые ищут определенное значение. С этим связан тот факт, что потоки, которые блокируют карту, на самом деле не имеют никакого требования когда-либо снимать блокировку, а бесконечный цикл в потоке-владельце может распространять постоянную блокировку на другие потоки. Медленные потоки владельца иногда могут быть прерваны. Карты на основе хеширования также подвержены спонтанным задержкам во время повторного хеширования.
Слабая согласованность
Решение пакетов java.util.concurrency для проблемы одновременной модификации, проблемы конвой, проблемы предсказуемой задержки и проблемы многоядерности включает архитектурный выбор, называемый слабым последовательность. Этот выбор означает, что такие операции чтения, как get (), не будут блокироваться, даже когда обновления выполняются, и допустимо даже перекрытие обновлений между собой и с операциями чтения. Слабая согласованность позволяет, например, изменять содержимое ConcurrentMap во время его итерации одним потоком. Итераторы предназначены для использования одним потоком за раз. Так, например, карта, содержащая две взаимозависимые записи, может непоследовательно восприниматься потоком чтения во время модификации другим потоком. Обновление, которое должно изменить ключ Entry (k1, v) на Entry (k2, v) атомарно, должно будет выполнить удаление (k1), а затем put (k2, v), в то время как итерация может пропустить запись или увидеть ее в двух местах. Получения возвращают значение для данного ключа, которое отражает последнее предыдущее завершенное обновление для этого ключа. Таким образом, существует отношение «случилось до».
ConcurrentMaps не может заблокировать всю таблицу. Исключение ConcurrentModificationException невозможно, как при непреднамеренной одновременной модификации несовпадающих карт. Метод size () может занять много времени, в отличие от соответствующих несовпадающих карт и других коллекций, которые обычно включают поле размера для быстрого доступа, потому что им может потребоваться сканирование всей карты каким-либо образом. Когда происходят одновременные модификации, результаты отражают состояние карты в какой-то момент, но не обязательно одно согласованное состояние, поэтому size (), isEmpty () и containsValue () могут лучше всего использоваться только для мониторинга.
Методы ConcurrentMap 1.5
Есть некоторые операции, предоставляемые ConcurrentMap, которых нет в Map, которые он расширяет, чтобы обеспечить атомарность модификаций. Команда replace (K, v1, v2) проверяет наличие v1 в записи, обозначенной K, и только в случае ее обнаружения v1 заменяется на v2 атомарно. Новая замена (k, v) выполнит операцию put (k, v), только если k уже находится на карте. Кроме того, putIfAbsent (k, v) выполнит put (k, v), только если k еще нет на карте, а remove (k, v) удалит запись для v, только если v присутствует. Эта атомарность может быть важна для некоторых сценариев использования с несколькими потоками, но не связана с ограничением слабой согласованности.
Для ConcurrentMaps следующие элементы являются атомарными.
m.putIfAbsent (k, v) является атомарным, но эквивалентен:
if (k == null || v == null) throw new NullPointerException (); если (! m.containsKey (k)) {вернуть m.put (k, v); } else {return m.get (k); }m replace (k, v) является атомарным, но эквивалентным:
if (k == null || v == null) throw new NullPointerException (); if (m.containsKey (k)) {return m.put (k, v); } else {return null; }m.replace (k, v1, v2) является атомарным, но эквивалентен:
if (k == null || v1 == null || v2 == null) throw new NullPointerException (); если (m.containsKey (k) Objects.equals (m.get (k), v1)) {m.put (k, v2); вернуть истину; } else return false; }m.remove (k, v) является атомарным, но эквивалентен:
// если Map не поддерживает нулевые ключи или значения (очевидно независимо) if (k == null || v == null) throw новое исключение NullPointerException (); если (m.containsKey (k) Objects.equals (m.get (k), v)) {m.remove (k); вернуть истину; } else return false; }Методы ConcurrentMap 1.8
Поскольку Map и ConcurrentMap являются интерфейсами, к ним нельзя добавлять новые методы без нарушения реализаций. Однако в Java 1.8 добавлена возможность для реализаций интерфейса по умолчанию и добавлены реализации по умолчанию интерфейса Map некоторых новых методов getOrDefault (Object, V), forEach (BiConsumer), replaceAll (BiFunction), computeIfAbsent (K, Function), computeIfPresent ( K, BiFunction), вычислить (K, BiFunction) и объединить (K, V, BiFunction). Реализации по умолчанию в Map не гарантируют атомарность, но в переопределении ConcurrentMap по умолчанию они используют методы Lock free для достижения атомарности, а существующие реализации ConcurrentMap будут автоматически атомарными. Безблокировочные методы могут быть медленнее, чем переопределения в конкретных классах, поэтому конкретные классы могут выбирать, реализовывать их атомарно или нет и задокументировать свойства параллелизма.
Атомарность без блокировок
Можно использовать методы без блокировок с ConcurrentMaps, потому что они включают методы с достаточно высоким согласованным числом, а именно бесконечностью, что означает, что любой количество потоков может быть согласовано. Этот пример можно реализовать с помощью Java 8 merge (), но он показывает общий шаблон Lock-free, который является более общим. Этот пример не связан с внутренними компонентами ConcurrentMap, а связан с использованием ConcurrentMap клиентским кодом. Например, если мы хотим атомарно умножить значение в Map на константу C:
static final long C = 10; void atomicMultiply (ConcurrentMap map, Long key) {for (;;) {Long oldValue = map.get (ключ); // Предполагается, что oldValue не равно нулю. Это операция «полезная нагрузка», и она не должна иметь побочных эффектов из-за возможного перерасчета конфликта. Long newValue = oldValue * C; если (map.replace (ключ, старое значение, новое значение)) перерыв; }}
putIfAbsent (k, v) также полезен, когда разрешено отсутствие записи для ключа. Этот пример можно реализовать с помощью Compute () Java 8, но он показывает общий шаблон Lock-free, который является более общим. Команда replace (k, v1, v2) не принимает нулевые параметры, поэтому иногда требуется их комбинация. Другими словами, если v1 имеет значение null, то вызывается putIfAbsent (k, v2), иначе вызывается replace (k, v1, v2).
void atomicMultiplyNullable (ConcurrentMap карта, длинный ключ) {for (;;) {Long oldValue = map.get (key); // Это операция "полезная нагрузка", и она не должна иметь побочных эффектов из-за возможного перерасчета конфликта Long newValue = oldValue == null? INITIAL_VALUE: oldValue * C; if (replaceNullable (map, key, oldValue, newValue)) перерыв; }}... статическое логическое значение replaceNullable (ConcurrentMap map, Long key, Long v1, Long v2) {return v1 == null? map.putIfAbsent (ключ, v2) == null: map.replace (ключ, v1, v2); }
История
Структура коллекций Java была спроектирована и разработана в основном Джошуа Блохом и была представлена в JDK 1.2. Первоначальные классы параллелизма взяты из пакета сбора Дуга Ли.
См. Также
Ссылки
- Goetz, Brian; Джошуа Блох; Джозеф Баубир; Дуг Ли; Дэвид Холмс; Тим Пайерлс (2006). Параллелизм Java на практике. Эддисон Уэсли. ISBN 0-321-34960-1. OL 25208908M.
- Ли, Дуг (1999). Параллельное программирование на Java: принципы и шаблоны проектирования. Эддисон Уэсли. ISBN 0-201-31009-0. OL 55044M.
Внешние ссылки
