Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Java Collections Framework версии 1.5 и более поздних версий языка программирования Java определяет и реализует исходные обычные однопоточные карты, а также новые потокобезопасные карты, реализующие java.util.concurrent.ConcurrentMapинтерфейс среди других параллельных интерфейсов. В Java 1.6 java.util.NavigableMapинтерфейс был добавлен, расширен java.util.SortedMap, и java.util.concurrent.ConcurrentNavigableMapинтерфейс был добавлен как комбинация подинтерфейсов.

Интерфейсы 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)).

Ктри [ править ]

Проблема одновременного изменения [ править ]

Одной из проблем, решаемых пакетом Java 1.5 java.util.concurrent, является проблема одновременной модификации. Предоставляемые им классы коллекций могут надежно использоваться несколькими потоками.

Для всех совместно используемых потоков непараллельных карт и других коллекций необходимо использовать какую-либо форму явной блокировки, например собственную синхронизацию, чтобы предотвратить одновременную модификацию, или же должен быть способ доказать с помощью логики программы, что одновременная модификация невозможна. Одновременное изменение карты несколькими потоками иногда нарушает внутреннюю согласованность структур данных внутри карты, что приводит к ошибкам, которые проявляются редко или непредсказуемо и которые трудно обнаружить и исправить. Кроме того, одновременная модификация одним потоком с доступом для чтения другим потоком или потоками иногда дает непредсказуемые результаты для читателя, хотя внутренняя согласованность карты не будет нарушена.Использование внешней программной логики для предотвращения одновременной модификации увеличивает сложность кода и создает непредсказуемый риск ошибок в существующем и будущем коде, хотя позволяет использовать непараллельные Коллекции. Однако ни блокировки, ни логика программы не могут координировать внешние потоки, которые могут контактировать с Коллекцией.

Счетчики модификаций [ править ]

Чтобы помочь с проблемой одновременной модификации, не параллельные реализации Map и другие Коллекции используют внутренние счетчики модификации, с которыми консультируются до и после чтения, чтобы следить за изменениями: писатели увеличивают счетчики модификации. Предполагается, что параллельная модификация обнаруживается этим механизмом, вызывая исключение java.util.ConcurrentModificationException, но не гарантируется, что оно произойдет во всех случаях, и на него не следует полагаться. Счетчик обслуживания также снижает производительность. По соображениям производительности счетчики не изменяются, поэтому не гарантируется, что их изменения будут распространяться между потоками.

Collections.synchronizedMap () [ править ]

Одним из решений проблемы одновременной модификации является использование определенного класса-оболочки, предоставляемого фабрикой в ​​Коллекциях: public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)который обертывает существующую не поточно-ориентированную карту с методами, которые синхронизируются на внутреннем мьютексе. Также существуют обертки для других видов Коллекций. Это частичное решение, потому что все еще возможно, что к базовой карте могут непреднамеренно получить доступ потоки, которые сохраняют или получают развернутые ссылки. Кроме того, все Коллекции реализуютjava.lang.Iterableно синхронизированные обернутые Карты и другие обернутые Коллекции не предоставляют синхронизированные итераторы, поэтому синхронизация остается на усмотрение клиентского кода, который является медленным и подверженным ошибкам, и невозможно ожидать дублирования другими потребителями синхронизированной Карты. Также должна быть защищена вся продолжительность итерации. Кроме того, карта, которая дважды обернута в разных местах, будет иметь разные внутренние объекты мьютекса, на которых работают синхронизации, что позволяет перекрывать друг друга. Делегирование снижает производительность, но современные компиляторы Just-in-Time часто сильно встраиваются, что ограничивает снижение производительности. Вот как работает обертка внутри оболочки - мьютекс - это всего лишь последний объект, а m - последняя обернутая карта:

 public  V  put ( K  ключ ,  V  значение )  {  синхронизировано  ( мьютекс )  { return  m . put ( ключ ,  значение );}  }

Синхронизация итерации рекомендуется следующим образом, однако она синхронизируется с оболочкой, а не с внутренним мьютексом, что позволяет перекрывать друг друга: [1]

 Карта < String ,  String >  wrappedMap  =  Коллекции . synchronizedMap ( карта );  ...  synchronized  ( wrappedMap )  {  for  ( String  s  :  wrappedMap . keySet ())  {  // некоторая, возможно, длинная операция выполняется, возможно,  // много раз, задерживая все другие обращения  }  }

Родная синхронизация [ править ]

Любую карту можно безопасно использовать в многопоточной системе, гарантируя, что все обращения к ней обрабатываются механизмом синхронизации Java:

 Карта < String ,  String >  map  =  new  HashMap < String ,  String > ();  ...  // Поток A  // Используем саму карту как блокировку. Вместо этого можно использовать любой согласованный объект.  синхронизировано ( карта )  {  карта . put ( "ключ" , "значение" );  }  ..  // Поток B  синхронизирован  ( карта )  {  String  result  =  map . получить ( "ключ");  ...  }  ...  // Поток C  синхронизирован  ( карта )  {  for  ( Entry < String ,  String >  s  :  map . EntrySet ())  {  / *  * Возможно, некоторые медленные операции, задерживающие все другие предположительно быстрые операции.  * Синхронизация на отдельных итерациях невозможна.  * /  ...  }  }

ReentrantReadWriteLock [ править ]

Код, использующий java.util.concurrent.ReentrantReadWriteLock, похож на код для собственной синхронизации. Однако в целях безопасности блокировки должны использоваться в блоке try / finally, чтобы ранний выход, такой как выброс исключения или break / continue, обязательно прошел через разблокировку. Этот метод лучше, чем использование синхронизации, потому что чтения могут перекрывать друг друга, возникает новая проблема при принятии решения о том, как приоритизировать записи по отношению к чтениям. Для простоты вместо него можно использовать java.util.concurrent.ReentrantLock, который не делает различий между чтением и записью. Возможно больше операций с блокировками, чем с синхронизацией, например, tryLock() и tryLock(long timeout, TimeUnit unit).

 последняя  блокировка ReentrantReadWriteLock  = новая ReentrantReadWriteLock (); final ReadLock readLock = блокировка . readLock (); final WriteLock writeLock = блокировка . writeLock (); .. // Поток А попытка { блокировку записи . замок (); карта . put ( "ключ" , "значение" ); ... } наконец { writeLock . разблокировать (); }                          ...  //  Поток B пытается  {  readLock . замок ();  Строка  s  =  map . получить ( "ключ" );  ..  }  наконец  {  readLock . разблокировать ();  }  //  Поток C пытается  {  readLock . замок ();  for  ( Entry < String ,  String >  s  :  map . entrySet ())  {  / * * Некоторые из них могут работать медленно, задерживая все другие предположительно быстрые операции.  * Синхронизация на отдельных итерациях невозможна.  * /  ...  }  }  наконец  {  readLock . разблокировать ();  }

Конвои [ править ]

Взаимное исключение имеет Локальный конвойпроблема, при которой потоки могут накапливаться на блокировке, в результате чего JVM необходимо поддерживать дорогостоящие очереди официантов и «парковать» ожидающие потоки. Парковать и отменять парковку потока стоит дорого, и может произойти медленное переключение контекста. Для переключения контекста требуется от микросекунд до миллисекунд, в то время как собственные базовые операции карты обычно занимают наносекунды. По мере роста конкуренции производительность может упасть до небольшой доли пропускной способности одного потока. Однако, когда конкуренция за блокировку отсутствует или небольшая, это мало влияет на производительность, за исключением теста конкуренции блокировки. Современные JVM встраивают большую часть кода блокировки, сокращая его до нескольких инструкций, что позволяет очень быстро исключить конфликт. Реентерабельные методы, такие как собственная синхронизация или java.util.concurrent.ReentrantReadWriteLock, однако, имеет дополнительный багаж, снижающий производительность при поддержании глубины повторного входа, что также влияет на случай отсутствия конкуренции. Проблема Convoy, похоже, решается с помощью современных JVMS, но ее можно скрыть медленным переключением контекста: в этом случае задержка увеличится, но пропускная способность останется приемлемой. Для сотен потоков время переключения контекста 10 мс дает задержку в секундах.

Несколько ядер [ править ]

Решения взаимного исключения не могут использовать всю вычислительную мощность многоядерной системы, потому что только один поток разрешен внутри кода карты одновременно. Реализации конкретных параллельных карт, предоставляемых Java Collections Framework и другими, иногда используют преимущества нескольких ядер с помощью Lock freeметоды программирования. В методах блокировки используются такие операции, как встроенный метод compareAndSet (), доступный во многих классах Java, таких как AtomicReference, для выполнения условных обновлений некоторых внутренних структур Map атомарно. Примитив 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 во время его итерации одним потоком. Итераторы предназначены для использования одним потоком за раз. Так, например, карта, содержащая две взаимозависимые записи, может непоследовательно восприниматься потоком-читателем во время модификации другим потоком. Обновление, которое должно изменить ключ записи ( k1, v) к Entry ( k2, v ) атомарно потребуется выполнить удаление ( k1 ), а затем размещение ( 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 ();  if  ( ! m . containsKey ( k ))  {  return  m . положите ( k ,  v );  }  else  {  return  m . получить ( к );  }

m replace (k, v) атомарен, но эквивалентен:

 if  ( k  ==  null  ||  v  ==  null )  throw  new  NullPointerException ();  if  ( m . containsKey ( k ))  {  return  m . положите ( k ,  v );  }  else  {  return  null ;  }

m.replace (k, v1, v2) атомарен, но эквивалентен:

 if  ( k  ==  null  ||  v1  ==  null  ||  v2  ==  null )  throw  new  NullPointerException ();  if  ( m . containsKey ( k )  &&  Objects . equals ( m . get ( k ),  v1 ))  {  m . положите ( k ,  v2 );  вернуть  истину ;  }  иначе  вернуться ложь ;  }

m.remove (k, v) атомарен, но эквивалентен:

 // если карта не поддерживает пустые ключи или значения (очевидно, независимо)  if  ( k  ==  null  ||  v  ==  null )  throw  new  NullPointerException ();  if  ( m . containsKey ( k )  &&  Objects . equals ( m . get ( k ),  v ))  {  m . удалить ( k );  вернуть  истину ;  }  иначе  вернуться ложь ;  }

Методы 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 автоматически станут атомарными. Безблокировочные методы могут быть медленнее, чем переопределения в конкретных классах, поэтому конкретные классы могут решить реализовать их атомарно или нет и задокументировать свойства параллелизма.

Атомарность без блокировок [ править ]

Можно использовать методы Lock-free с ConcurrentMaps, потому что они включают методы с достаточно высоким согласованным числом, а именно бесконечностью, что означает, что любое количество потоков может быть скоординировано. Этот пример может быть реализован с помощью Java 8 merge (), но он показывает общий шаблон Lock-free, который является более общим. Этот пример не связан с внутренними компонентами ConcurrentMap, а связан с использованием ConcurrentMap клиентским кодом. Например, если мы хотим атомарно умножить значение в Map на константу C:

 статический  финал  длинный  C  =  10 ;  void  atomicMultiply ( ConcurrentMap < Long ,  Long >  map ,  Long  key )  {  for  (;;)  {  Long  oldValue  =  map . получить ( ключ );  // Предполагается, что oldValue не равно нулю. Это операция «полезная нагрузка», и она не должна иметь побочных эффектов из-за возможного перерасчета конфликта.  Long  newValue  =  oldValue  *  C ;  если  (карта . replace ( ключ ,  старое значение ,  новое значение ))  перерыв ;  }  }

PutIfAbsent ( k, v ) также полезен, когда разрешено отсутствие записи для ключа. Этот пример может быть реализован с помощью Java 8 compute (), но он показывает общий шаблон Lock-free, который является более общим. Команда replace ( k, v1, v2 ) не принимает нулевые параметры, поэтому иногда требуется их комбинация. Другими словами, если v1 имеет значение null, то вызывается putIfAbsent ( k, v2 ), в противном случае вызывается replace ( k, v1, v2 ).

 void  atomicMultiplyNullable ( ConcurrentMap < Long ,  Long >  map ,  Long  key )  {  for  (;;)  {  Long  oldValue  =  map . получить ( ключ );  // Это операция «полезная нагрузка», и она не должна иметь побочных эффектов из-за возможного перерасчета конфликта  Long  newValue  =  oldValue  ==  null  ?  INITIAL_VALUE  :  oldValue  *  C ;  если  ( replaceNullable( карта ,  ключ ,  старое значение ,  новое значение ))  перерыв ;  }  }  ...  статическое  логическое значение  replaceNullable ( ConcurrentMap < Long ,  Long >  map ,  Long  key ,  Long  v1 ,  Long  v2 )  {  return  v1  ==  null  ?  карта . putIfAbsent ( ключ ,  v2 )  ==  null  :  карта. заменить ( ключ ,  v1 ,  v2 );  }

История [ править ]

Фреймворк коллекций Java был разработан и разработан в основном Джошуа Блохом и был представлен в JDK 1.2 . [2] Оригинальные классы параллельности пришли из Doug Lea «s [3] сбор пакета.

См. Также [ править ]

  • Платформа коллекций Java
  • Контейнер (структура данных)
  • Параллелизм Java
  • Заблокировать бесплатно

Ссылки [ править ]

  1. ^ "java.util.Collections.synchronizedMap" . Java / Java SE / 11 / API / java.base. Справочный центр Oracle . 19 сентября 2018 . Проверено 17 июля 2020 . CS1 maint: обескураженный параметр ( ссылка )
  2. ^ Vanhelsuwé, Laurence (1 января 1999). «Битва контейнерных фреймворков: что лучше использовать?» . JavaWorld . Проверено 17 июля 2020 . CS1 maint: обескураженный параметр ( ссылка )
  3. ^ Ли, Дуг . «Обзор пакета util.concurrent Release 1.3.4» . Проверено 1 января 2011 . CS1 maint: обескураженный параметр ( ссылка )
  • Гетц, Брайан; Джошуа Блох; Джозеф Баубир; Дуг Ли; Дэвид Холмс; Тим Пайерлс (2006). Параллелизм Java на практике . Эддисон Уэсли. ISBN 0-321-34960-1. ПР  25208908М .
  • Ли, Дуг (1999). Параллельное программирование на Java: принципы и шаблоны проектирования . Эддисон Уэсли. ISBN 0-201-31009-0. OL  55044M .

Внешние ссылки [ править ]

  • Коллекции Уроки
  • Учебное пособие по коллекции Java 6 - Якоб Дженков, Кадафи Камфулуса
  • Приручение тигра: рамки коллекций
  • 'The Collections Framework' (документация Oracle Java SE 8)
  • «Учебники по Java - Сборники» Джоша Блоха
  • Какую коллекцию Java мне следует использовать? - Удобная блок-схема для упрощения выбора коллекций
  • «Какую коллекцию Java использовать?» - автор Janeve George